Concentration inequalities: a nonasymptotic theory of independence

Cover......Page 1
Contents......Page 8
1 Introduction......Page 12
 1.1 Sums of Independent Random Variables and the Martingale Method......Page 13
 1.2 The Concentration-of-Measure Phenomenon......Page 15
 1.3 The Entropy Method......Page 20
 1.4 The Transportation Method......Page 23
 1.5 Reading Guide......Page 24
 1.6 Acknowledgments......Page 27
2 Basic Inequalities......Page 29
 2.1 From Moments to Tails......Page 30
 2.2 The Cramér–Chernoff Method......Page 32
 2.3 Sub-Gaussian Random Variables......Page 35
 2.4 Sub-Gamma Random Variables......Page 38
 2.5 A Maximal Inequality......Page 42
 2.6 Hoeffding’s Inequality......Page 45
 2.7 Bennett’s Inequality......Page 46
 2.8 Bernstein’s Inequality......Page 47
 2.9 Random Projections and the Johnson–Lindenstrauss Lemma......Page 50
 2.10 Association Inequalities......Page 54
 2.11 Minkowski’s Inequality......Page 55
 2.12 Bibliographical Remarks......Page 56
 2.13 Exercises......Page 57
3 Bounding the Variance......Page 63
 3.1 The Efron–Stein Inequality......Page 64
 3.2 Functions with Bounded Differences......Page 67
 3.3 Self-Bounding Functions......Page 71
 3.4 More Examples and Applications......Page 74
 3.5 A Convex Poincaré Inequality......Page 77
 3.6 Exponential Tail Bounds via the Efron–Stein Inequality......Page 79
 3.7 The Gaussian Poincaré Inequality......Page 83
 3.8 A Proof of the Efron–Stein Inequality Based on Duality......Page 84
 3.9 Bibliographical Remarks......Page 87
 3.10 Exercises......Page 89
4 Basic Information Inequalities......Page 94
 4.1 Shannon Entropy and Relative Entropy......Page 95
 4.2 Entropy on Product Spaces and the Chain Rule......Page 96
 4.3 Han’s Inequality......Page 97
 4.4 Edge Isoperimetric Inequality on the Binary Hypercube......Page 98
 4.5 Combinatorial Entropies......Page 100
 4.6 Han’s Inequality for Relative Entropies......Page 102
 4.7 Sub-Additivity of the Entropy......Page 104
 4.8 Entropy of General Random Variables......Page 107
 4.9 Duality and Variational Formulas......Page 108
 4.10 A Transportation Lemma......Page 112
 4.11 Pinsker’s Inequality......Page 113
 4.12 Birgé’s Inequality......Page 114
 4.13 Sub-Additivity of Entropy: The General Case......Page 116
 4.14 The Brunn–Minkowski Inequality......Page 118
 4.15 Bibliographical Remarks......Page 121
 4.16 Exercises......Page 123
5 Logarithmic Sobolev Inequalities......Page 128
 5.1 Symmetric Bernoulli Distributions......Page 129
 5.2 Herbst’s Argument: Concentration on the Hypercube......Page 132
 5.3 A Gaussian Logarithmic Sobolev Inequality......Page 135
 5.4 Gaussian Concentration: The Tsirelson–Ibragimov–Sudakov Inequality......Page 136
 5.5 A Concentration Inequality for Suprema of Gaussian Processes......Page 138
 5.6 Gaussian Random Projections......Page 139
 5.7 A Performance Bound for the Lasso......Page 143
 5.8 Hypercontractivity: The Bonami–Beckner Inequality......Page 150
 5.9 Gaussian Hypercontractivity......Page 157
 5.10 The Largest Eigenvalue of Random Matrices......Page 158
 5.11 Bibliographical Remarks......Page 163
 5.12 Exercises......Page 165
6 The Entropy Method......Page 179
 6.1 The Bounded Differences Inequality......Page 181
 6.2 More on Bounded Differences......Page 185
 6.3 Modified Logarithmic Sobolev Inequalities......Page 186
 6.4 Beyond Bounded Differences......Page 187
 6.5 Inequalities for the Lower Tail......Page 189
 6.6 Concentration of Convex Lipschitz Functions......Page 191
 6.7 Exponential Inequalities for Self-Bounding Functions......Page 192
 6.8 Symmetrized Modified Logarithmic Sobolev Inequalities......Page 195
 6.9 Exponential Efron–Stein Inequalities......Page 196
 6.10 A Modified Logarithmic Sobolev Inequality for the Poisson Distribution......Page 199
 6.11 Weakly Self-Bounding Functions......Page 200
 6.12 Proof of Lemma 6.22......Page 207
 6.13 Some Variations......Page 210
 6.14 Janson’s Inequality......Page 215
 6.15 Bibliographical Remarks......Page 218
 6.16 Exercises......Page 220
 7.1 Lévy’s Inequalities......Page 226
 7.2 The Classical Isoperimetric Theorem......Page 229
 7.3 Vertex Isoperimetric Inequality in the Hypercube......Page 233
 7.4 Convex Distance Inequality......Page 235
 7.5 Convex Lipschitz Functions Revisited......Page 240
 7.6 Bin Packing......Page 241
 7.7 Bibliographical Remarks......Page 243
 7.8 Exercises......Page 244
8 The Transportation Method......Page 248
 8.1 The Bounded Differences Inequality Revisited......Page 250
 8.2 Bounded Differences in Quadratic Mean......Page 252
 8.3 Applications of Marton’s Conditional Transportation Inequality......Page 258
 8.4 The Convex Distance Inequality Revisited......Page 260
 8.5 Talagrand’s Gaussian Transportation Inequality......Page 262
 8.6 Appendix: A General Induction Lemma......Page 267
 8.7 Bibliographical Remarks......Page 270
 8.8 Exercises......Page 271
9 Influences and Threshold Phenomena......Page 273
 9.1 Influences......Page 274
 9.2 Some Fundamental Inequalities for Influences......Page 275
 9.3 Local Concentration......Page 282
 9.4 Discrete Fourier Analysis and a Variance Inequality......Page 284
 9.5 Monotone Sets......Page 288
 9.6 Threshold Phenomena......Page 290
 9.7 Bibliographical Remarks......Page 297
 9.8 Exercises......Page 298
10 Isoperimetry on the Hypercube and Gaussian Spaces......Page 301
 10.1 Bobkov’s Inequality for Functions on the Hypercube......Page 302
 10.2 An Isoperimetric Inequality on the Binary Hypercube......Page 308
 10.3 Asymmetric Bernoulli Distributions and Threshold Phenomena......Page 309
 10.4 The Gaussian Isoperimetric Theorem......Page 314
 10.5 Lipschitz Functions of Gaussian Random Variables......Page 318
 10.6 Bibliographical Remarks......Page 319
 10.7 Exercises......Page 320
11 The Variance of Suprema of Empirical Processes......Page 323
 11.1 General Upper Bounds for the Variance......Page 326
 11.2 Nemirovski’s Inequality......Page 328
 11.3 The Symmetrization and Contraction Principles......Page 333
 11.4 Weak and Wimpy Variances......Page 338
 11.5 Unbounded Summands......Page 341
 11.6 Bibliographical Remarks......Page 346
 11.7 Exercises......Page 347
12 Suprema of Empirical Processes: Exponential Inequalities......Page 352
 12.2 A Bernstein-Type Inequality for Bounded Processes......Page 353
 12.3 A Symmetrization Argument......Page 355
 12.4 Bousquet’s Inequality for Suprema of Empirical Processes......Page 358
 12.5 Non-Identically Distributed Summands and Left-Tail Inequalities......Page 362
 12.6 Chi-Square Statistics and Quadratic Forms......Page 364
 12.7 Bibliographical Remarks......Page 365
 12.8 Exercises......Page 366
13 The Expected Value of Suprema of Empirical Processes......Page 373
 13.1 Classical Chaining......Page 374
 13.2 Lower Bounds for Gaussian Processes......Page 377
 13.3 Chaining and VC-Classes......Page 382
 13.4 Gaussian and Rademacher Averages of Symmetric Matrices......Page 385
 13.5 Variations of Nemirovski’s Inequality......Page 388
 13.6 Random Projections of Sparse and Large Sets......Page 390
 13.7 Normalized Processes: Slicing and Reweighting......Page 398
 13.8 Relative Deviations for L[sub(2)] Distances......Page 402
 13.9 Risk Bounds in Classification......Page 403
 13.10 Bibliographical Remarks......Page 406
 13.11 Exercises......Page 408
 14.1 Φ-Entropy and its Sub-Additivity......Page 423
 14.2 From Φ-Entropies to Φ-Sobolev Inequalities......Page 430
 14.3 Φ-Sobolev Inequalities for Bernoulli Random Variables......Page 434
 14.4 Bibliographical Remarks......Page 438
 14.5 Exercises......Page 439
15 Moment Inequalities......Page 441
 15.1 Generalized Efron–Stein Inequalities......Page 442
 15.2 Moments of Functions of Independent Random Variables......Page 443
 15.3 Some Variants and Corollaries......Page 447
 15.4 Sums of Random Variables......Page 451
 15.5 Suprema of Empirical Processes......Page 454
 15.6 Conditional Rademacher Averages......Page 457
 15.7 Bibliographical Remarks......Page 458
 15.8 Exercises......Page 460
References......Page 462
 F......Page 484
 O......Page 485
 Z......Page 486
 D......Page 488
 I......Page 489
 L......Page 490
 S......Page 491
 W......Page 492