Concentration Inequalities: A Nonasymptotic Theory of Independence
Abstract
Concentration inequalities deal with deviations of functions of independent random variables from their expectation. In the last decade new tools have been introduced making it possible to establish simple and powerful inequalities. These inequalities are at the heart of the mathematical analysis of various problems in machine learning and made it possible to derive new efficient algorithms. This text attempts to summarize some of the basic tools.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Under Assumptions 2-5, for any slack β ∈ (0, 1/2 - α), with probability at least 1 - exp(-N β^2/2), at least (1 - α - β)N of the N judge outputs lie within distance ρ = σ(C1√d + (1/c) log(2(1-α)/β)) of y⋆.
“For convenience, we recall Lemma 2: under Assumptions 2-5, for any slack β ∈ (0, 1/2 -α), with probability at least 1 -exp(-N β 2 /2), at least (1 -α -β)N of the N judge outputs lie within distance ρ = σ C 1”
From RoPoLL: Robust Panel of LLM Judges (2026) · cites this paper as Boucheron et al., 2013
Cites
A Probabilistic Theory of Pattern Recognition
Devroye, L., Györfi, L., & Lugosi, G. (1996) · Stochastic Modelling and Applied Probability · doi:10.1007/978-1-4612-0711-5 · Cited by 3,274 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
The Privacy Blanket of the Shuffle Model
Balle, B., Bell, J., Gascón, A., & Nissim, K. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-26951-7_22 · Cited by 214 · see citing works
Inference under information constraints I: Lower bounds from chi-square contraction
Acharya, J., Canonne, C. L., & Tyagi, H. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3028440 · Cited by 59 · see citing works
Uncertainty quantification in the Bradley–Terry–Luce model
Gao, C., Shen, Y., & Zhang, A. Y. (2023) · Information and Inference: A Journal of the IMA · doi:10.1093/imaiai/iaac032 · Cited by 18 · see citing works
Dynamics-Aligned Latent Imagination in Contextual World Models for Zero-Shot Generalization
Röder, F., Benad, J., Eppe, M., & Banerjee, P. (2025) · Advances in Neural Information Processing Systems 38 · doi:10.52202/085713-2438
RoPoLL: Robust Panel of LLM Judges
Acharya, A., Pan, K. W., & Verkhovsky, B. (2026) · arXiv · doi:10.48550/arxiv.2606.30931
Dynamics-Aligned Latent Imagination in Contextual World Models for Zero-Shot Generalization
Röder, F., Benad, J., Eppe, M., & Banerjee, P. K. (2025) · arXiv
“By the bounded log-likelihood assumption, | Z i | ≤ M . probability For independent Z i , Hoeffding’s inequality [Boucheron et al., 2013] bounds the tail for bounded random variables: Since τ t is β -mixing with β ( K ) ≤ Ce − λK , the dependence adds an error β ( K ) , as β ( K ) bounds the…”
Large-scale methods for distributionally robust optimization
Levy, D., Carmon, Y., Duchi, J. C., & Sidford, A. (2020) · arXiv · doi:10.48550/arxiv.2010.05893 · Cited by 52 · see citing works
- Authors
- Boucheron, S., Lugosi, G., & Massart, P.
- Affiliations
- Université Paris-Sud (FR)
- Universitat Pompeu Fabra (ES)
- Venue
- Oxford University Press eBooks
- Publisher
- Oxford University Press
- Published
- 2013-02-07
- Pages
- 481
- OpenAlex
- W4245577611
- Cited by
- 1,768
- References
- 1
- Citations by year
- 2026: 112 · 2025: 148 · 2024: 169 · 2023: 164 · 2022: 179 · 2021: 197 · 2020: 233 · 2019: 189 · 2018: 113 · 2017: 87 · 2016: 69 · 2015: 70 · 2014: 24 · 2013: 10 · 2012: 3
- FWCI
- 12.31
- Type
- book
- Language
- en
- Open access
- closed
- Locations
- Oxford University Press eBooks (publishedVersion)
- HAL (submittedVersion)
- Max Planck Institute for Plasma Physics (submittedVersion)
- MPG.PuRe (Max Planck Society) (submittedVersion)
- Topics
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Keywords
- concentration inequalities, independent random variables, machine learning analysis, efficient algorithms, probability inequalities
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
