Invited speakers

Pierre Alquier
Theoretical Guarantees for Approximate Bayesian Inference

While Bayesian methods are extremely popular in statistics and machine learning, their application to massive datasets is often challenging, when possible at all. Indeed, the classical MCMC algorithms targeting the exact posterior are prohibitively slow when both the model dimension and the sample size are large or when the likelihood is not tractable. Fast algorithms were proposed, at the price of targeting approximations of the posterior. In this talk, I will discuss two approaches. The first approach is an approximate Metropolis-Hastings algorithm (MH). In MH, a simulation from the transition kernel P requires a computation of the likelihood that might be expensive. We propose an approximation Q of P leading to a fast algorithm. We control explicity the total variation distance (TV) between the posterior and the distribution of the simulations. This algorithm was proposed in Alquier, Friel, Everitt and Boland (Statistics and Computing, 2016) under the name "Noisy-MCMC". I will also mention recent results by Rudolf and Schweizer (2018) who relaxed the assumptions of our results by using the Wasserstein distance instead of TV. The second approach is Variational Bayesian inference (VB). VB aims at approximating the posterior by a distribution in a tractable family. Thus, MCMC are replaced by an optimization algorithm which is orders of magnitude faster. VB methods have been applied in such computationally demanding applications as including collaborative filtering, NLP and text processing... However, despite nice results in practice, the theoretical properties of these approximations are usually not known. I will present conditions ensuring the asymptotic concentration of the variational approximation of the posterior around the true parameter. These results are taken from our recent works: Alquier and Ridgway (2017) and Chérief-Abdellatif and Alquier (2018).

Dömötör Pálvölgyi
(Eötvös Loránd University)
News about the chromatic number of the plane

At least how many colors do we need to color all the points of the plane such that every pair of points at unit distance receive different colors? This question is known as the Hadwiger-Nelson problem and until one year ago it was only known that 4 colors are needed and 7 are enough. Then in April 2018 gerontologist de Grey showed in a breakthrough result that 4 colors are not enough. His proof was computer assisted, and a collaborative Polymath project was started to find a human-verifiable proof. I will give a short introduction to the classical results, then talk about the current ongoing research with plenty of open problems.

Csaba Toth
(CSUN and Tufts University)
Online Unit Clustering and Covering in Euclidean Space

Given a set of n points in a metric space, that arrive one by one, the Unit Clustering problem consists of partitioning the points into the minimum number of clusters (subsets) of diameter at most one; while the Unit Covering problem consists of covering all points by the minimum number of balls of unit radius. In this talk, we explore how the competitive ratio of online algorithms depend on the diemension in Euclidean spaces. Under the L infinity norm, we show that the competitive ratio of any online algorithm (deterministic or randomized) for Unit Clustering is \Omega(d). We also give a randomized online algorithm with competitive ratio O(d^2) for Unit Clustering of integer points. The competitive ratio of any deterministic online algorithm for Unit Covering under L infinity is at least 2^d; and this ratio is the best possible. Under the L_2 norm, we describe an online deterministic algorithm with competitive ratio O(1.321^d) for Unit Covering, improving on the earlier record by an exponential factor; and give a lower bound of d+1 for the competitive ratio of any algorithm for d \geq 1. (Joint work with Adrian Dumitrescu and Anirban Ghosh.)


9h30-10h30Pierre Alquier
11h-12hDömötör Pálvölgyi
12h-13hCsaba Tóth


As long as there is available space, inscription is free, but obligatory. Please subscribe to this workshop by sending an email to Monika Csikos.

Monika Csikos and Nabil H. Mustafa (LIGM, ESIEE Paris). The workshop is supported by ANR grant SAGA.


CouprieMichelESIEE / LIGM
CoustyJeanESIEE / LIGM
KenmochiYukikoCNRS / LIGM
CsikosMonika LIGM, ESIEE Paris
MeunierFrédéricEcole des Ponts ParisTech
MustafaNabil H. LIGM, ESIEE Paris
RomonPascalLIGM, UPEM
BiswasRanitaInstitute of Science and Technology, Austria
MelnikovaAleksandraMasaryk University, Czech Republic
NormandNicolasLS2N/Université de Nantes
KrzysztofCiesielskiWVU and MIPG, UPenn
ComicLidijaUniversity of Novi Sad
BataviaDarshanTU Wien
TóthCsaba D.California State University Northridge
SongHaominUniversity of Liverpool
NagyBenedekEastern Mediterranean University
FrosiniAndreaUniversità di Firenze
JiménezMaría JoséUniversidad de Sevilla
Colin de VerdiereEricLIGM, CNRS
MulzerWolfgangFU Berlin
HubardAlfredoLIGM, UPEM