| |
| |
| |
Introduction | |
| |
| |
| |
Sums of Independent Random Variables and the Martingale Method | |
| |
| |
| |
The Concentration-of-Measure Phenomenon | |
| |
| |
| |
The Entropy Method | |
| |
| |
| |
The Transportation Method | |
| |
| |
| |
Reading Guide | |
| |
| |
| |
Acknowledgments | |
| |
| |
| |
Basic Inequalities | |
| |
| |
| |
From Moments to Tails | |
| |
| |
| |
The Cram�r-Chernoff Method | |
| |
| |
| |
Sub-Gaussian Random Variables | |
| |
| |
| |
Sub-Gamma Random Variables | |
| |
| |
| |
A Maximal Inequality | |
| |
| |
| |
Hoeffding's Inequality | |
| |
| |
| |
Bennett's Inequality | |
| |
| |
| |
Bernstein's Inequality | |
| |
| |
| |
Random Projections and the Johnson-Lindenstrauss Lemma | |
| |
| |
| |
Association Inequalities | |
| |
| |
| |
Minkowski's Inequality | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
Bounding the Variance | |
| |
| |
| |
The Efron-Stein Inequality | |
| |
| |
| |
Functions with Bounded Differences | |
| |
| |
| |
Self-Bounding Functions | |
| |
| |
| |
More Examples and Applications | |
| |
| |
| |
A Convex Poincar� Inequality | |
| |
| |
| |
Exponential Tail Bounds via the Efron-Stein Inequality | |
| |
| |
| |
The Gaussian Poincar� Inequality | |
| |
| |
| |
A Proof of the Efron-Stein Inequality Based on Duality | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
Basic Information Inequalities | |
| |
| |
| |
Shannon Entropy and Relative Entropy | |
| |
| |
| |
Entropy on Product Spaces and the Chain Rule | |
| |
| |
| |
Han's Inequality | |
| |
| |
| |
Edge Isoperirnetric Inequality on the Binary Hypercube | |
| |
| |
| |
Combinatorial Entropies | |
| |
| |
| |
Han's Inequality for Relative Entropies | |
| |
| |
| |
Sub-Additivity of the Entropy | |
| |
| |
| |
Entropy of General Random Variables | |
| |
| |
| |
Duality and Variational Formulas | |
| |
| |
| |
A Transportation Lemma | |
| |
| |
| |
Pinsker's Inequality | |
| |
| |
| |
Birg�'s Inequality | |
| |
| |
| |
Sub-Additivity of Entropy: The General Case | |
| |
| |
| |
The Brunn-Minkowski Inequality | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
Logarithmic Sobolev Inequalities | |
| |
| |
| |
Symmetric Bernoulli Distributions | |
| |
| |
| |
Herbst's Argument: Concentration on the Hypercube | |
| |
| |
| |
A Gaussian Logarithmic Sobolev Inequality | |
| |
| |
| |
Gaussian Concentration: The Tsirelson-Ibragimov-Sudakov Inequality | |
| |
| |
| |
A Concentration Inequality for Suprema of Gaussian Processes | |
| |
| |
| |
Gaussian Random Projections | |
| |
| |
| |
A Performance Bound for the Lasso | |
| |
| |
| |
Hypercontractivity: The Bonami-Beckner Inequality | |
| |
| |
| |
Gaussian Hypercontractivity | |
| |
| |
| |
The Largest Eigenvalue of Random Matrices | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
The Entropy Method | |
| |
| |
| |
The Bounded Differences Inequality | |
| |
| |
| |
More on Bounded Differences | |
| |
| |
| |
Modified Logarithmic Sobolev Inequalities | |
| |
| |
| |
Beyond Bounded Differences | |
| |
| |
| |
Inequalities for the Lower Tail | |
| |
| |
| |
Concentration of Convex Lipschitz Functions | |
| |
| |
| |
Exponential Inequalities for Self-Bounding Functions | |
| |
| |
| |
Symmetrized Modified Logarithmic Sobolev Inequalities | |
| |
| |
| |
Exponential Efron-Stein Inequalities | |
| |
| |
| |
A Modified Logarithmic Sobolev Inequality for the Poisson Distribution | |
| |
| |
| |
Weakly Self-Bounding Functions | |
| |
| |
| |
Proof of Lemma 6.22 | |
| |
| |
| |
Some Variations | |
| |
| |
| |
Janson's Inequality | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
Concentration and Isoperimetry | |
| |
| |
| |
L�vy's Inequalities | |
| |
| |
| |
The Classical Isoperirnetric Theorem | |
| |
| |
| |
Vertex Isoperirnetric Inequality in the Hypercube | |
| |
| |
| |
Convex Distance Inequality | |
| |
| |
| |
Convex Lipschitz Functions Revisited | |
| |
| |
| |
Bin Packing | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
The Transportation Method | |
| |
| |
| |
The Bounded Differences Inequality Revisited | |
| |
| |
| |
Bounded Differences in Quadratic Mean | |
| |
| |
| |
Applications of Marton's Conditional Transportation Inequality | |
| |
| |
| |
The Convex Distance Inequality Revisited | |
| |
| |
| |
Talagrand's Gaussian Transportation Inequality | |
| |
| |
| |
Appendix: A General Induction Lemma | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
Influences and Threshold Phenomena | |
| |
| |
| |
Influences | |
| |
| |
| |
Some Fundamental Inequalities for Influences | |
| |
| |
| |
Local Concentration | |
| |
| |
| |
Discrete Fourier Analysis and a Variance Inequality | |
| |
| |
| |
Monotone Sets | |
| |
| |
| |
Threshold Phenomena | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
Isoperimetry on the Hypercube and Gaussian Spaces | |
| |
| |
| |
Bobkov's Inequality for Functions on the Hypercube | |
| |
| |
| |
An Isoperimetric Inequality on the Binary Hypercube | |
| |
| |
| |
Asymmetric Bernoulli Distributions and Threshold Phenomena | |
| |
| |
| |
The Gaussian Isoperimetric Theorem | |
| |
| |
| |
Lipschitz Functions of Gaussian Random Variables | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
The Variance of Suprema of Empirical Processes | |
| |
| |
| |
General Upper Bounds for the Variance | |
| |
| |
| |
Nemirovski's Inequality | |
| |
| |
| |
The Symmetrization and Contraction Principles | |
| |
| |
| |
Weak and Wimpy Variances | |
| |
| |
| |
Unbounded Summands | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
Suprema of Empirical Processes: Exponential Inequalities | |
| |
| |
| |
An Extension of Hoeffding's Inequality | |
| |
| |
| |
A Bernstein-Type Inequality for Bounded Processes | |
| |
| |
| |
A Symmetrization Argument | |
| |
| |
| |
Bousquet's Inequality for Suprema of Empirical Processes | |
| |
| |
| |
Non-Identically Distributed Summands and Left-Tail Inequalities | |
| |
| |
| |
Chi-Square Statistics and Quadratic Forms | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
The Expected Value of Suprema of Empirical Processes | |
| |
| |
| |
Classical Chaining | |
| |
| |
| |
Lower Bounds for Gaussian Processes | |
| |
| |
| |
Chaining and VC-Classes | |
| |
| |
| |
Gaussian and Rademacher Averages of Symmetric Matrices | |
| |
| |
| |
Variations of Nemirovski's Inequality | |
| |
| |
| |
Random Projections of Sparse and Large Sets | |
| |
| |
| |
Normalized Processes: Slicing and Reweighting | |
| |
| |
| |
Relative Deviations for L<sub>2</sub> Distances | |
| |
| |
| |
Risk Bounds in Classification | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
�-Entropies | |
| |
| |
| |
�-Entropy and its Sub-Additivity | |
| |
| |
| |
From �-Entropies to �-Sobolev Inequalities | |
| |
| |
| |
�-Sobolev Inequalities for Bernoulli Random Variables | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
| |
Moment Inequalities | |
| |
| |
| |
Generalized Efron-Stein Inequalities | |
| |
| |
| |
Moments of Functions of Independent Random Variables | |
| |
| |
| |
Some Variants and Corollaries | |
| |
| |
| |
Sums of Random Variables | |
| |
| |
| |
Suprema of Empirical Processes | |
| |
| |
| |
Conditional Rademacher Averages | |
| |
| |
| |
Bibliographical Remarks | |
| |
| |
| |
Exercises | |
| |
| |
References | |
| |
| |
Author Index | |
| |
| |
Subject Index | |