| |
| |
| |
| 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 | |