A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization

arXiv:2610.21103 · math.ST, cs.IT, math.IT, math.PR, stat.ML, stat.TH · Submitted 2026-10-15 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization".

Jane: The gist: This work establishes a heavy-tailed extension of McDiarmid’s inequality for one-sided deviations, providing exponential concentration for nonlinear functions even when they have infinite variance.

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So this paper, titled "A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization," is looking at extending a classic tool in statistics. It takes McDiarmid's inequality, which is really useful for bounding the deviation of functions of independent random variables, and makes it work better when the data has heavier tails than usual.

Jane: That's right. The main point they are making here is that they can get exponential concentration bounds even when the function we're looking at doesn't have a finite variance, which is a big deal for many machine learning problems.

Lu: They show that if you have independent random variables and you satisfy a specific condition on their conditional moments, specifically Assumption three point one where V is finite, then this theorem gives an exponential upper-tail concentration > <ref:2610.21103#pg3> P(f(X) − E

f(X): ≥ t) ≤ exp − p − one/p t p/(p−one) V(one/(p−one)) <ref:2610.21103#pg1>

Meng: Exponential decay is powerful, but what I want to know is how this applies practically. It’s about concentration of the sample mean and median-of-means estimator, right? If we can get these strong guarantees on the deviation probabilities, that means our estimators are more reliable when dealing with messy data.

Tom: Exactly. And the paper claims they achieve this by using a new tensorization inequality for the Kullback–Leibler divergence called reverse KL tensorization > P(f(X) − E

f(X): ≥ t) exp(−O (t p *)) ✓

Jane: That reverse KL tensorization seems to be the key technical trick they are using to bridge that gap, especially since they mention it might be of independent interest for other things. It's a way to get these bounds through a Chernoff argument >

Lu: The authors are using this technique to decompose the centered tilted density by conditioning successively on independent random variables and averaging over all possible orderings >

Conclusion: Tom: So, summarizing what we've seen with this paper, "A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization," they've managed to establish an exponential upper-tail concentration inequality for functions of independent random variables under one-sided boundedness and suitable moment assumptions >

Jane: What this really means is that we can get these strong tail bounds for non-negative losses or returns, even when those losses are heavy-tailed, as long as we meet their moment assumption of order p in the range of one to two >

Meng: For production systems, this suggests that if you use estimators like the median-of-means estimator, you can have much tighter confidence intervals than before when your loss function is unbounded or has infinite variance >

Lu: The reverse KL tensorization technique itself is the core technical contribution they are making, and it's a novel way to get these concentration bounds without relying on the standard entropy method which they say gives worse tail bounds for general p in the range of one to two >

Tom: It’s interesting because they are comparing their result against previous concentration results, and it shows that even when you have finite L p moment conditions for the coordinatewise differences, you can still get an exponential upper-tail bound even when the function has infinite variance >

Haruka Eshima, Amedeo Roberto Esposito, Andrea Paudice

Okinawa Institute of Science and Technology · Department of Computer Science, Aarhus University

math.ST, cs.IT, math.IT, math.PR, stat.ML, stat.TH

Submitted: 2026-10-15

Updated: 2026-10-15

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: The gist: This work establishes a heavy-tailed extension of McDiarmid’s inequality for one-sided deviations, providing exponential concentration for nonlinear functions even when they have infinite

Key concepts

McDiarmid's Inequality: A fundamental tool in statistics that provides concentration guarantees for functions of independent random variables based on the boundedness of their differences. It helps bound how far a function's output can stray from its expected value, typically under conditions requiring bounded differences.
Reverse KL Tensorization: A new mathematical technique used to handle the Kullback-Leibler divergence in this context. It works by swapping the roles of the two arguments compared to standard tensorization methods. This allows researchers to derive concentration bounds via a Chernoff argument, bypassing limitations found in previous entropy-based approaches.
Heavy Tails and Infinite Variance: This refers to data where extreme values occur much more frequently than in distributions with finite variance. When a function has infinite variance, standard concentration inequalities often fail. This paper addresses this challenge by developing a new inequality that still provides exponential concentration guarantees under specific moment conditions.
One-Sided Concentration: Instead of bounding deviations in both the positive and negative directions (two-sided), this focuses only on the upper tail, i.e., bounding $P(f(X) - E[f(X)] ext{ is large and positive})$. This specific focus is useful when analyzing scenarios like risk bounds or estimating estimators where only upward deviations are of primary concern.

Summary

The gist: This work establishes a heavy-tailed extension of McDiarmid’s inequality for one-sided deviations, providing exponential concentration for nonlinear functions even when they have infinite variance.

Background and Motivation

Concentration inequalities are fundamental tools in statistical learning theory, and McDiarmid’s inequality is widely studied due to its distribution-free guarantees <ref:2610.21103#pg2>. However, McDiarmid’s inequality requires a bounded-differences condition which limits its direct applicability to learning problems with unbounded loss functions <ref:2610.21103#pg2>. This limitation is particularly relevant in applications where data exhibit heavy tails or the loss itself may be heavy-tailed, potentially with infinite variance <ref:2610.21103#pg2>. The empirical mean is particularly sensitive to heavy tails, and robust mean estimators cannot generally guarantee sub-Gaussian deviation rates under weaker moment assumptions <ref:2610.21103#pg3>.

Main Result: Theorem 3.1

The core contribution is establishing a one-sided McDiarmid-type inequality for functions of independent random variables <ref:2610.21103#pg2>. Under Assumption 3.1, which requires the uniform bound on the sum of the conditional p-th moments of these gaps, i.e., V:= ∑k=1∥Dk(X)∥p L p(X) < ∞, Theorem 3.1 yields an exponential upper-tail concentration <ref:2610.21103#pg3>. Specifically, for every t > 0, P(f (X) − E[f (X)] ≥ t) ≤ exp − p − 1/p t p/(p−1) V(1/(p−1)) <ref:2610.21103#pg3>. This result is significant because it provides exponential upper-tail concentration even when the function has infinite variance, provided that 1

Key Technical Tools

The proof relies on a novel tensorization of the Kullback–Leibler divergence termed reverse KL tensorization (Theorem 3.4) <ref:2610.21103#pg2>. This technique interchanges the two arguments of the divergence relative to the classical entropy tensorization, bypassing Herbst’s argument and allowing for concentration bounds via a Chernoff argument <ref:2610.21103#pg2>. The proof decomposes the centered tilted density by conditioning successively on independent random variables and averaging over all possible orderings <ref:2610.21103#pg2>. This leads to an inequality bounding the centered log-moment generating function, which is then used to derive the concentration inequality <ref:2610.21103#pg2>.

Applications

The inequality has been illustrated through three applications <ref:2610.21103#pg3>:

Recovering existing bounds for additive functions <ref:2610.21103#pg3>.
Establishing concentration of the median-of-means (MoM) estimator around its own expectation <ref:2610.21103#pg3>. This is achieved via Corollary 3.9, which provides a bound on P(mubMoM − EmubMoM ≥ t) <ref:2610.21103#pg2>.
Bounding the population risk uniformly over a class of nonnegative, possibly unbounded losses <ref:2610.21103#pg3>. Corollary 3.14 establishes a uniform risk bound in terms of the expected Rademacher complexity, which applies to possibly infinite classes with finite Rademacher complexity <ref:2610.21103#pg2>.

Comparison with Existing Work

The paper compares its results against previous concentration bounds <ref:2610.21103#pg4>. For instance, while Lei et al. (2026) provide polynomial tail bounds for functions of independent inputs under finite L p moment conditions on coordinatewise differences, this work establishes an exponential upper-tail bound even when the function has infinite variance <ref:2610.21103#pg2>. Furthermore, the analysis shows that the reverse KL tensorization is necessary because a naive application of the entropy method provides a tail bound that is worse than Theorem 3.1 for general p in (1, 2] <ref:2610.21103#pg3>.

Conclusion

The work successfully establishes an exponential upper-tail concentration inequality for functions of independent random variables under one-sided boundedness and suitable moment assumptions, providing a powerful tool for analyzing stochastic optimization with median-of-means gradient estimators and stability-based generalization bounds with heavy-tailed losses.

Improvements for AI systems

Bold Header: Concentration for Heavy-Tailed Random Variables

This inequality allows bounding exponential upper-tail concentration even when its second moment is infinite (Theorem 3.1), specifically for functions of independent inputs where the deviation from coordinatewise essential suprema has uniformly bounded conditional moments, which is crucial for heavy-tailed loss settings.

Bold Header: Concentration of Median-of-Means Estimator

The result provides an exponential concentration bound around the estimator's expectation, stating that P(mubMoM − EmubMoM ≥ t) ≤ exp − (p − 1) / p t p / (p−1) V1/(p−1) (Corollary 3.9), which is applicable even when blocks have unequal sizes or when observations are not identically distributed.

Bold Header: Uniform Risk Bounds for Unbounded Losses

The corollary establishes a uniform risk bound for possibly infinite classes of losses, stating that for every h ∈ H, R(h) ≤ Rbn(h) + 2Rn(L) + M1/p p p-1 ln(1/delta) n (p-1)/p (Corollary 3.14), which is valuable for bounding population risk when losses are unbounded but satisfy finite moment assumptions.

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 in(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.