Research map / Learning theory and algorithms / Sample complexity
Concentration Inequalities for General Functions of Heavy-Tailed Random Variables
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives bounded-difference-type concentration inequalities for general functions of independent heavy-tailed variables (finite variance), combining the entropy method with truncation, and applies them to vector concentration, Rademacher complexity and algorithmic stability.
Problem
McDiarmid-type bounded difference inequalities require bounded conditional ranges, and MGF-based unbounded extensions fail for heavy-tailed variables whose MGF does not exist; concentration for general functions of heavy-tailed independent variables is thus lacking.
Approach
Uses the entropy method together with truncation of the centered conditional versions, with the right tail of each conditional version captured by a generic function h(t); this yields a mixed sub-Gaussian/heavy-tail bound with a transition threshold t(eta) and covers sub-exponential, sub-Weibull and polynomially decaying tails under finite variance.
Key results
- Theorem 3.3 gives, for sub-exponential conditional tails, a sub-Gaussian regime 2exp(-t^2/(2n*alpha)) below threshold t(eta) and a sub-exponential regime 2exp(-ct/4) above it (Corollary 3.4).
- Extends the Maurer & Pontil (2021) sub-exponential bounded-difference result to sub-Weibull and polynomially decaying (c>2) right tails, covering all finite-variance distributions.
- Applications extend vector-valued concentration, Rademacher generalization bounds and algorithmic stability bounds for Lipschitz/metric settings to heavy-tailed inputs with finite variance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use truncation with the entropy method for heavy-tailed conditional versions | Bounded-difference concentration for general functions · Independent variables with finite variance | tail probability | Helped |
| Allow sub-exponential rather than bounded conditional ranges | Bounded-difference concentration · Sub-exponential conditional tails | tail probability: 2 exp (−t²/(2nα)); 2 exp (−1/4 ct) | Helped |
| Allow sub-Weibull conditional tails | Bounded-difference concentration · Sub-Weibull conditional tails | tail probability: exp (−t²/(2nΛ(t, η))) + exp (−max{ct, 1/2}ηcθt¹/θ) + n exp(−cθt¹/θ) | Helped |
| Allow polynomially decaying conditional tails | Bounded-difference concentration · Polynomially decaying conditional tails with c > 2 | tail probability: exp (−t²/(2nΛ(t, η))) + n/(tηc max{ct,0.5}) + n/tc | Helped |
| Use a sufficiently large truncation parameter | Theorem 3.1 concentration bound for sub-Weibull tails · Sub-Weibull conditional tails (θ > 1) | tail probability: exp (−t²/(2n(σ²+δ))) + n exp (−t(η)²/(ηn(σ²+δ))) | Helped |
Surprising findings
- The polynomial-tail result requires c > 2/(1-eta) to keep the variance-proxy bound finite; the case c <= 2 is stated as open.
Limitations
- Cannot handle infinite-variance distributions; the proof needs bounded Lambda.
- Dimension dependence n inherited from bounded-difference-type inequalities; sub-Gaussian bound is weaker than optimal for Gaussian/Lipschitz functions.
- Assumes uniform tail of conditional versions across all x; polynomial case with c <= 2 left open.
Experimental setup
Baselines: Maurer & Pontil 2021 Kontorovich 2014 Latała 1997 Bakhshizadeh et al. 2023
Builds on: McDiarmid's bounded difference inequality Maurer & Pontil 2021 unbounded bounded-difference inequality Bakhshizadeh et al. 2023 truncation technique entropy method (Maurer 2012)
Closest papers by meaning
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.86)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.85)
- A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers (NeurIPS 2024 · similarity 0.85)
- Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.85)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.84)
- Regularized least squares learning with heavy-tailed noise is minimax optimal (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.