Concentration of measure and its applications

May 14-18, 2018, Cargèse, Corsica

Participants

Schedule

Mon 14 Tue 15 Wed 16 Thu 17 Fri 18
09:00-10:00 Roberto Houdré PDF Samson PDF Barthe Strzelecki PDF
10:00-10:30 Coffee break Coffee break Coffee break / Payment Coffee break / Payment Coffee break / Payment
10:30-11:30 Merlevède PDF Oliveira PDF Samson Paouris Paulin PDF
11:30-12:00 Break Break Strzelecka PDF Break / Payment 11:30 Lunch
12:00-14:00 Lunch Lunch Lunch Lunch 12:30 Departure (BUS)
14:00-15:00 Tanguy PDF Oleszkiewicz Free Rio
15:00-16:00 Latała Ben-Hamou Sambale PDF
16:00-16:30 Coffee break Break Coffee break
16:30-17:30 Klartag Raginsky Lemańczyk
17:30-18:30 Tropp Chazottes PDF
18:30 Apéritif 19:00 BBQ

Titles and abstracts

Speaker  Title Abstract
Barthe, Franck Spectral gap for some log-concave measures This work in progress with Bo'az Klartag was initiated by a question on a specific measure related to the LASSO estimator. In a attempt to have a broader view on the question, we investigate Poincaré inequalities for some families of log-concave perturbations of product measures. We use techniques that were developed in order to tackle the famous Kannan-Lovasz-conjecture, which predicts the approximate value of the spectral gap of log-concave measures. Other key ingredients are the notion of Gaussian mixtures and a recent extension of the Gaussian correlation inequality. As an application we can confirm (up to logarithmic terms) the KLS conjecture for sections of proportional dimensions of unit balls of $\ell_p^n$, for $1\le p <2$.
Ben-Hamou, Anna Weighted sampling without replacement In his pioneer 1963 article, Hoeffding showed that the sum induced by uniform samples without replacement in a finite population is smaller, in the convex order, than the sum induced by uniform samples with replacement. In particular, bounds on the Laplace transform known for sampling with replacement automatically apply for sampling without replacement. When the sample size grows, one may expect that samples without replacement concentrate "even better" than samples with replacement, the variance then being of the order of the number of unsampled items. This was verified by Serfling (1974). In this talk, we will be interested in extending those results to the weighted case, in which items are sampled according to heterogeneous weights. This is a joint work with Yuval Peres and Justin Salez.
Chazottes, Jean-René Concentration inequalities for Gibbs random fields We shall review concentration inequalities for Gibbs measures in lattice systems. In the Dobrushin uniqueness regime, we have a Gaussian concentration bound, whereas in the Ising model (and related models) at sufficiently low temperature, one has a stretched-exponential concentration bound. Then we shall present various applications of these inequalities.
Houdré, Christian Asymptotics in Sequences Comparisons Both for random words and random permutations, I will present a panoramic view of recent results on the asymptotic law of the, centered and normalized, length of their longest common (and increasing) subsequences. Tools and results involve concentration inequalities (for geodesics of LCSs paths), Stein' s method as well as maximal eigenvalues of some Gaussian random matrices.
Klartag, Bo'az Concentration for convex Hamiltonians with bounded variables We prove a dimension-free log-Sobolev inequality for probability measures with density exp(-H) under three assumptions: The measure is supported on an n-dimensional cube of constant sidelength ("bounded variables"), the function H is convex, and the second derivatives of H in the coordinate directions d^2 H / dx_i^2 are uniformly bounded.
Latała, Rafał Comparison of weak and strong moments for random vectors We show that for p≥1, the p-th moment of suprema of linear combinations of independent centered random variables are comparable with the sum of the first moment and the weak p-th moment provided that 2q-th and q-th integral moments of these variables are comparable for all q≥2. The latest condition turns out to be necessary in the i.i.d. case. If time permits we will discuss similar results and open problems for log-concave random vectors with dependent coordinates. Talk will be based on the joint work with Marta Strzelecka.
Lemańczyk, Michał A Bernstein-like concentration inequality for Markov chains We present a notion of 1-dependent, stationary processes of random variables and then we prove a counterpart of classical Bernstein inequality for such processes. Furthermore, we derive from this result a Bernstein-like inequality for general Markov chains exploiting a technique called splitting.
Merlevède, Florence On the Wasserstein distance between the empirical and the marginal distributions of weakly dependent sequences In this talk I shall discuss about recent results concerning the behaviour of the Wasserstein distance of order 1 between the empirical distribution and the marginal distribution of real-valued weakly dependent sequences. In particular, some moments inequalities of order p for any p greater than one will be given, and conditions ensuring that the central limit theorem holds will be exhibited. Applications to unbounded functions of expanding maps of the interval with a neutral fixed point at zero will be provided. The given moment inequalities for the Wasserstein distance are similar to the well known von Bahr-Esseen or Rosenthal bounds for partial sums, and seem to be new even in the case of independent and identically distributed random variables. This is a joint work with J. Dedecker.
Oleszkiewicz, Krzysztof On some optimal bound in terms of variance and its applications to the FKN Theorem For independent real random variables $X$ and $Y$, at least one of them symmetric, we will prove the bound $$ \min(\mathrm{Var}(X),\mathrm{Var}(Y)) \leq \frac{16}{7} \mathrm{Var}(|X+Y|), $$ which can be viewed as a concentration inequality in terms of variance (roughly speaking, if X+Y is concentrated around a two-point set then X or Y is concentrated around a constant), and it is easy to see that the constant 16/7 is optimal. We will also show how to apply this estimate to prove the Friedgut-Kalai-Naor Theorem about Boolean functions on the discrete cube.
Imbuzeiro Oliveira, Roberto Concentration in the Chinese restaurant We prove finite sample results for the so-called Generalized Chinese Restaurant Process, or Ewens-Pitman sampling model. This process describes a restaurant where incoming customers either join a preocupied table or sit at an empty table. In the regime where the number of tables grows polynomially, we obtain nonasymptotic results for how the number of parts of given sizes relate to one another. Our analysis is based on simple martingale techniques. Joint with Alan Pereira and Rodrigo Ribeiro (IMPA).
Paulin, Daniel Understanding the efficiency of MAP estimators for high dimensional non-linear filtering based on concentration inequalities In this talk we consider the problem of filtering and smoothing of partially observed chaotic dynamical systems that are discretely observed, with an additive Gaussian noise in the observation. These models are found in a wide variety of real applications. In the context of a fixed observation interval T, observation time step h and Gaussian observation variance σ^2, we show under assumptions that the filter and smoother are well approximated by a Gaussian with high probability when h and σ^2 h are sufficiently small. Based on this result we show that the Maximum-a-posteriori (MAP) estimators are asymptotically optimal in mean square error as σ^2h tends to 0. The proofs are based on concentration inequalities for empirical processes, and matrix concentration inequalities. These allow us to control the deviation of the log-likelihood from a suitably chosen quadratic approximation everywhere in the state space.
Raginsky, Maxim Concentration of measure without independence: a unified approach via the martingale method The concentration of measure phenomenon may be summarized as follows: a function of many weakly dependent random variables that is not too sensitive to any of its individual arguments will tend to take values very close to its expectation. This phenomenon is most completely understood when the arguments are mutually independent random variables, and there exist several powerful complementary methods for proving concentration inequalities, such as the martingale method, the entropy method, and the method of transportation inequalities. The setting of dependent arguments is much less well understood. This talk, based on joint work with Aryeh Kontorovich, focuses on the martingale method for deriving concentration inequalities without independence assumptions. In particular, we use the machinery of so-called Wasserstein matrices to show that the Azuma-Hoeffding concentration inequality for martingales with almost surely bounded differences, when applied in a sufficiently abstract setting, is powerful enough to recover and sharpen several known concentration results for nonproduct measures. Wasserstein matrices provide a natural formalism for capturing the interplay between the metric and the probabilistic structures, which is fundamental to the concentration phenomenon. If time permits, I will also discuss information-theoretic criteria of weak dependence, following recent work by T. Austin.
Rio, Emmanuel About the constants in the Fuk-Nagaev inequalities In this talk we give efficient constants in the Fuk-Nagaev inequalities. Next we derive new upper bounds on the weak norms of martingales from our Fuk-Nagaev type inequality.
Roberto, Cyril Log Hessian estimates and the Talagrand Conjecture Motivated by Talagrand's conjecture about the regularization effect of the Ornstein-Uhlenbeck semi-group, we investigate lower bounds on the log Hessian of a family of diffusion semi-group (essentially perturbation of the Ornstein-Uhlenbeck semi-group) and prove that the conjecture holds. On the other side, we will also investigate similar questions for the (discrete) M/M/infinity queuing process on the integers. Joint work with N. Gozlan, X.-M Li, M. Madiman and P.-M. Samson.
Sambale, Holger Higher Order Concentration of Measure We investigate the higher order concentration of measure phenomenon for functions typically centered at stochastic expansions of order $d-1$ with bounded $d$-th order derivatives or differences, where $d$ is any natural number. The results yield uniform exponential bounds for $|f|^{2/d}$ or $|f|^{1/d}$. Here we consider several situations, including functions of independent as well as weakly dependent random variables, differentiable functions on Euclidean spaces with LSI or Poincaré type measures, and functions on the unit sphere. We also discuss some applications of these bounds. This is joint work with S. Bobkov, F. Götze and A. Sinulis.
Samson, Paul-Marie About the use of "weak" transport costs for concentration properties and functionals inequalities in discrete spaces In the 1990s, K. Marton introduced a weak transport cost to recover and extend to dependent setting some concentration results on product spaces by M. Talagrand, related to the so-called convex-hull method. Then these kind of optimal transport costs have developed to improve some concentration results by different ways. In 2014, we introduced the so-called class of "weak" transport costs (see [2]) for which we prove a main dual Kantorovich Theorem. This class of costs is of particular interest since it appears it several fields of research (concentrations properties [2], Strassen Theorem [2], martingales transport costs [1], Schrödinger minimization problem [4]). In this talk, we will present few recent uses of these weak transport costs to concentration and functional inequalities  and we will mainly focus on discrete spaces (a characterization of a class of weak-transport-entropy inequalities [3], and its applications to product of symmetric measures with log-concave tails [7], some concentration properties on groups of permutations [6], a notion of curvature on discrete spaces [5]). Based on : *[1]* Complete duality for martingale optimal transport on the line. Ann. of Probab. Vol. 45, no 5 (2017) 3327-3405. M. Beiglböck, M. Nutz, N. Touzi. *[2]* Kantorovich duality for general transport costs and applications. J. Funct. Anal. 273 (2017), no. 11, 3327-3405. Joint work with N. Gozlan, C. Roberto et P. Tetali. *[3]* Characterization of a class of weak transport-entropy inequalities on the line. Annales de l’IHP (Accepted in 2017). Joint work with N. Gozlan, C. Roberto, Y. Shu et P. Tetali. *[4]* Lazy random walks and optimal transport on graphs. Ann. of Probab. Vol. 44, no 3 (2016) 1864-1915. C. Léonard. *[5]* On the convexity of the entropy along entropic interpolations. In: Measure Theory in Non-Smooth Spaces, (ed. N. Gigli), Partial Differential Equations and Measure Theory. De Gruyter Open, June 2017, 195-242. C. Léonard *[6]* Transport-entropy inequalities on locally acting groups of permutations. Electron. J. Probab. 22 (2017), no. 62. *[7]* On the convex infimum convolution inequality with optimal cost function. ALEA, Lat. Am. J. Probab. Math. Stat.14, 903–915 (2017). M. Strzelecka, M. Strzelecki, T. Tkocz.
Strzelecka, Marta On the convex infimum convolution inequality with optimal cost function We say that a measure $\mu$ satisfies convex infimum convolution inequality (convex IC for short) with a cost function $\varphi$, if $(\mu, \varphi)$ has property $\tau$ for every convex function bounded below. The smallest (up to a scaling) cost function for which convex IC may hold is the Legendre transform. During the talk we will discuss a sufficient and almost necessary condition under which product measures satisfy convex IC with optimal cost function. We will also see that it leads to a concentration inequality strong enough to imply the comparison of weak and strong moments with constant $1$ at the first strong moment. Based on the joint work with Michał Strzelecki and Tomasz Tkocz.
Strzelecki, Michał On the convex Poincaré inequality We will prove that if a probability measure on $\mathbb{R}$ satisfies the Poincaré inequality for convex functions, then it also satisfies a Bobkov-Ledoux type modified log-Sobolev inequality for convex/concave functions (and consequently certain weak transport-entropy inequalities). This generalizes results by Gozlan et al. and Feldheim et al., concerning probability measures on the real line. Based on joint work with Radosław Adamczak.
Tanguy, Kevin Variance bounds and superconcentration It is well known that concentration of measure is a useful tool which can be applied in various situations. Nevertheless, as noticed by Chatterjee, some functional inequalities linked to the concentration of measure phenomenon can lead to sub-obtimal bounds for particular functionals. In the first part of the talk we will recall some basics examples of superconcentration. In the second part of talk, we will focus on general methods which improve upon classical Poincaré's inequality. In particular, in a Gaussian framework, we will present how semigroup and hypercontractive arguments can be used to improve upon classical concentration of measure for the function maximum. If time permits it, we will also briefly say a few words about inverse, integrated, infinite curvature dimension inequality in a context of Spin Glasses. Then, in order to reach superconcentration outside a Gaussian setting, we will show how monotone rearrangement can be used to obtain weighted Poincaré's inequalities for product measures. These inequalities can be used to obtain superconcentration for various functionals such as Order Statistics or l_p norms of random vector. Finally, we will present some open and challenging questions in superconcentration theory.
Paouris, Grigoris Concentration under convexity assumptions I will present some new concentration inequalities for convex functions with respect to the Gaussian measure. Focus will be on small ball probabilities for norms. Time permitting applications to randomized Dvoretzky's theorem will be discussed. Based on joint work(s) with K. Tikhomirov and P. Valettas.

Organizers