Concentration Inequalities: A Nonasymptotic Theory of Independence

By Stéphane Boucheron, Gábor Lugosi, Pascal Massart. 2013

3,340 citations recorded by the source corpus.

Subfields: Geometry and Topology, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

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

In Geometry and Topology

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

PAC-Bayesian Theory Meets Bayesian Inference (2016, neutral): “As mentioned by Zhang [2006], Catoni [2007], Germain et al. [2009], Lever et al.”
Rethinking LDA: Moment Matching for Discrete ICA (2015, neutral): “A high probability bound could be derived using concentration inequalities for Poisson random variables [14]; but the expectation already gives the right order of magnitude for the error (for example via Markov’s inequality).”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, methodology): “…where V 1 , . . . , V k/ 2 are independent and distributed uniformly over {− 1 , +1 , so that we can bound the decoupled chi-square ﬂuctuation using Hoeffding’s Lemma ( cf. [12]) as Thus, Lemma III.6 implies that Ω( √ k/ε 2 ) samples are needed for testing (in particular, for uniformity testing).”
Distributed Simulation and Distributed Inference (2018, methodology): “To that end, we use the following bound which can be obtained by combining the transportation lemma with Marton’s transportation-cost inequality (cf. [BLM13, Chapter 8]).”
Collecting Telemetry Data Privately (2017, methodology): “We have Proof: Clearly, for every i ∈ [ n ] , we have Applying the Chernoff-Hoeffding bound [6, Theorem 2.8] to independent { 0 , 1 } -random variables { b i ( t ) } i ∈ n , for all t > 0 , we have Combining (6) and (5) we get Combining (7), (3), and (2) we conclude Thus setting t = θn · e (cid:15)…”
Adaptive Personalized Federated Learning (2020, background): “Deﬁne Then, plugging back Lemma 1 in (31) yields: Now, a simple application of the Hoeﬀding’s inequality Boucheron et al. (2013) gives where .”
Certifying Some Distributional Robustness with Principled Adversarial Training (2017, methodology): “Thus, the functional θ 7→ F n ( θ ) satisﬁes bounded diﬀerences [14, Thm. 6.2], and applying standard results on Rademacher complexity [1] and entropy integrals [64, Ch. 2.2] gives the result.”
The hardness of conditional independence testing and the generalised covariance measure (2018, background): “3 Related work Our hardness result for conditional independence contributes to an important literature on impossibility results in statistics and econometrics starting with the work of Bahadur and Savage [2] which shows that there is no non-trivial test for whether a distribution has mean zero.”
On the Error of Random Fourier Features (2015, methodology): “The introduction of α ε is by replacing Hoeffding’s inequality with that of Bern-stein (1924) when it is tighter, using the variance from (5).”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, background): “Since r (s, a) and r̂ (s, a) is bounded, we can also obtain high-probability deviation bounds using standard concentration inequalities [5].”
Variance-based Regularization with Convex Objectives (2016, background): “Bounds that trade between risk and variance are known in a number of cases in the empirical risk minimization literature [15, 22, 2, 1, 6, 3, 7, 12], which is relevant when one wishes to achieve “fast 2”
Adversarially Robust Generalization Requires More Data (2018, background): “7 in [6] for a reference of this standard result.”
On Exact Computation with an Infinitely Wide Neural Net (2019, background): “10 (Gaussian chaos of order 2 [Boucheron et al., 2013]).”
Consistency of Random Forests (2014, background): “Thus, for some positive constant C , (see, e.g., Chapter 1 in Boucheron et al., 2013).”
The landscape of empirical risk for nonconvex losses (2016, background): “[BLM13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, Concentration inequalities: A nonasymptotic theory of independence, OUP Oxford, 2013.”
Just Interpolate: Kernel "Ridgeless" Regression Can Generalize (2018, background): “digits pair [i,j] [2,5] [2,6] [2,7] [2,8] [2,9] [3,5] [3,6] [3,7] [3,8] [3,9] [4,5] [4,6] [4,7] [4,8] [4,9]”