Concentration of Lipschitz Functions — A Guided Tour of Modern Statistics

ΣModern Statistics

5.4 Concentration of Lipschitz Functions

PDF ↓

Contents

I · Chapter 1: Classical Theory

1Probability Theory and Stochastic Processes 1.1Probability Space and Random Variables 1.2Convergence 1.3The Law of Large Numbers and the Central Limit Theorem 1.4Stochastic Processes 2Parameter Estimation 2.1Fundamentals 2.2Methods of Estimation 2.3Large Sample Theory 3Hypothesis Testing 3.1Fundamentals 3.2Multiple Testing and Error Rate Control 3.3Causal Inference 3.4Conformal prediction 3.5Application: Watermark Detection 4Classical Statistical Model 4.1Regression 4.2Classification 4.3Trees and Weak Learners 4.4Cross-Validation 4.5Time Series

II · Chapter 2: High-Dimensional Statistics

5Concentration Inequalities 5.1Basic Concentration Inequalities 5.2Random Vectors 5.3Random Matrices 5.4Concentration of Lipschitz Functions 5.5Martingale Concentration Inequalities 6Function Spaces 6.1Rademacher Complexity 6.2Metric Entropy Method 6.3Glivenko-Cantelli Theorem and Donsker Theorem 6.4Information Theory 7High-Dimensional Statistics 7.1Concentration of Sample Covariance 7.2Sparse Linear Regression 7.3High-Dimensional Principal Component Analysis 7.4Low-Rank Matrix Recovery 7.5Non-Parametric Estimation 8Random Matrix Theory 8.1Density of Eigenvalues in Classical Ensembles of Random Matrices 8.2Semi-Circle Law and Marchenko–Pastur Law 8.3BBP Transition 8.4CLT for Eigenvalues 8.5Spectrum Separation 8.6Replica Method

III · Chapter 3: Other Topics in Statistics

9Computational Statistics 9.1Numerical Linear Algebra 9.2Numerical Analysis 9.3Optimization 9.4Sampling Methods and Simulation 9.5Optimal Transport 10Deep Learning Theory 10.1Approximation Theory 10.2Optimization Theory 10.3Classic Models for Learning Theory References

Notes / Concentration Inequalities

5.4 Concentration of Lipschitz Functions

Theorem 5.46 (Gaussian Concentration). Let \(X_1, X_2, \ldots , X_n \overset {\mathrm {iid}}{\sim } \mathcal {N}(0, 1)\) and \(f : \mathbb {R}^n \to \mathbb {R}\) such that \(f\) is \(L\)-Lipschitz in \(\|\cdot \|_2\), i.e. \[ |f(x) - f(y)| \leq L \|x - y\|_2 \qquad \forall x, y \in \mathbb {R}^n. \] Then

1.: \(f(X_{1:n}) - \mathbb {E}[f(X_{1:n})]\) is \(\mathrm {sG}(L)\).
2.: \[ \mathbb {P}(|f(X_{1:n}) - \mathbb {E}[f(X_{1:n})]| \geq t) \leq 2 \exp \!\left ( -\frac {t^2}{2 L^2} \right ). \]

Theorem 5.47 (Concentration of Convex Lipschitz Functions). Suppose that

1.: \(f\) is \(L\)-Lipschitz and convex: \[ \nabla ^2 f(x) \succ 0 \quad \text {if } \nabla ^2 f \text { exists} \]
2.: \((X_i)_{i \in [n]}\) independent with \(X_i \in [a, b]\) a.s.

Then \(f(X_{1:n}) - \mathbb {E}[f]\) is \(\mathrm {sG}(L(b-a))\), so \[ \mathbb {P}(|f(X_{1:n}) - \mathbb {E}[f(X_{1:n})]| \geq t) \leq 2 \exp \left ( -\frac {t^2}{2L^2(b-a)^2} \right ). \]

← PreviousRandom Matrices Next →Martingale Concentration Inequalities

On this page

Concentration of Lipschitz Functions

Search definitions, theorems, and topics across the notes.