PreprintCC BY 4.0arXiv
A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization
Abstract
We revisit McDiarmid's inequality, a central tool in statistical learning theory and algorithm analysis. We show that large deviations above the mean are exponentially unlikely for functions of independent random variables that are almost surely bounded above and satisfy a conditional moment assumption of order p∈(1,2]. When p<2, the result applies even when the function has infinite variance. Our proof relies on a new tensorization inequality for the Kullback--Leibler divergence, termed reverse KL tensorization, which may be of independent interest. Applications include concentration of the sample mean and median-of-means estimator, and one-sided uniform risk bounds for unbounded losses.
Related
- Distribution-Dependent Improvements of McDiarmid's Inequality via Rényi Divergence
- A Generalized McDiarmid Inequality: Sample Reuse and Non-Uniform Unbounded Differences
- The reverse Hölder inequality for 𝒜p(·) weights with applications to matrix weights
- Reverse Urysohn inequality for functions and functional Shephard problem
- On the Reverse Projection Inequality
BibTeX
@misc{eshima2026onesided,
title = {{A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization}},
author = {Hanuka Eshima and Amedeo Roberto Esposito and Andrea Paudice},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21103},
eprint = {2610.21103},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21103},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization
AU - Hanuka Eshima
AU - Amedeo Roberto Esposito
AU - Andrea Paudice
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21103
UR - https://arxiv.org/abs/2610.21103
AB - We revisit McDiarmid's inequality, a central tool in statistical learning theory and algorithm analysis. We show that large deviations above the mean are exponentially unlikely for functions of independent random variables that are almost surely bounded above and satisfy a conditional moment assumption of order p∈(1,2]. When p<2, the result applies even when the function has infinite variance. Our proof relies on a new tensorization inequality for the Kullback--Leibler divergence, termed reverse KL tensorization, which may be of independent interest. Applications include concentration of the sample mean and median-of-means estimator, and one-sided uniform risk bounds for unbounded losses.
ER -