The concentration of measure phenomenon

By Michel Ledoux. 2001

2,392 citations recorded by the source corpus.

Subfields: Numerical Analysis, Statistical and Nonlinear Physics, Signal Processing, Pure Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Numerical Analysis

In Statistical and Nonlinear Physics

In Signal Processing

In Pure Mathematics

Citations in the corpus

Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, methodology): “, to prove the isoperimetric inequality for the Gaussian measure Ledoux (2005). 19”
Constrained Few-shot Class-incremental Learning (2022, background): “This phenomenon is known as concentration of measure [28], with the peculiar property that pseudo-orthogonality converges to exact orthogonality with increasing dimensionality.”
Exact Matrix Completion via Convex Optimization (2008, background): “Talagrand [33] proved a concentration inequality about Y (cid:63) , see also [22, Corollary 7.8]. where σ 2 = sup f ∈F ni =1 E f 2 ( Y i ) , and K is a numerical constant.”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “Note that by isoperimetry property [28] and union bounding over i ∈ [n], we have”
Telling cause from effect based on high-dimensional observations (2009, background): “To show this, we need the following result (Ledoux, 2001):”
Introduction to the non-asymptotic analysis of random matrices (2010, background): “34 (Concentration in Gauss space, see [43]).”
Are adversarial examples inevitable? (2018, neutral): “The result below about the unit cube is analogous to Proposition 2.8 in Ledoux (2001), except with tighter constants.”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, background): “Finally, the following lemma states an useful concentration inequality on Haar measure [48].”
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, background): “For the references and more examples we refer the reader to excellent sources (Ledoux 2001; Giannopoulos and Milman 2001; Milman and Schechtman 1986).”
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks (2017, background): “…that if v 1 , . . . , v k are chosen i.i.d. from N ( 0 , cI ) , then by standard concentration arguments, for any (cid:15) > 0 and high enough dimension d (depending on k, (cid:15) ), it holds with probability at least 1 − exp( − Ω( for all i, i (cid:48) ∈ { 1 , . . . , k } (see Ledoux [2005]).”
Uncertainty Principles and Vector Quantization (2006, neutral): “The concentration inequality (see e.g. [29] Section 1.3) then implies that this function is well concentrated about its average value E : Choosing u = t n/N completes the proof.”
Sharp thresholds for high-dimensional and noisy recovery of sparsity (2006, background): “centration of measure for Lipschitz functions [ 24 , 27], we conclude that for any η > 0, it holds that”
Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees (2011, background): “h when the underlying graph is a general tree. In particular, Theorem 1.2 proves that τcov exhibits an exponential concentration (which was observed for the supremum of a Gaussian process (see, e.g., [31], Theorem 7.1, Equation (7.4)) and its standard deviation is bounded from above by the geometric”
For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution (2006, background): “By concentration of measure for Gaussian variables [18], (3.”