A New Breakthrough in McDiarmid Inequalities for Heavy Tails: Reverse KL Tensorization

Introduction: When Classical Concentration Inequalities Meet Heavy-Tailed Data

In statistical learning theory and algorithm analysis, the McDiarmid inequality is a core tool for studying concentration phenomena of functions of independent random variables. It tells us that if a function is insensitive to changes in each of its input variables, then the probability that the function's value deviates from its expectation decays exponentially. However, the classical McDiarmid inequality relies on the bounded difference assumption and typically requires random variables to have finite variance—which often fails when dealing with heavy-tailed distributions (such as financial returns, network traffic, or word frequencies in natural language).

A recent research paper from rss, "A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization," reexamines this classical problem. The authors propose a one-sided McDiarmid-type inequality tailored to heavy-tailed scenarios and introduce a new tool called "reverse KL tensorization." This work not only extends the applicability boundary of concentration inequalities but may also provide theoretical support for high-dimensional heavy-tailed data analysis.

Background on Concentration Inequalities and the McDiarmid Inequality

Concentration inequalities are fundamental tools in probability theory and statistical learning theory, used to characterize upper bounds on the probability that a random variable deviates from its expectation. Common examples include Hoeffding's inequality, Chernoff bounds, and Bernstein's inequality, which typically assume bounded random variables or finite variance to obtain exponentially decaying tail probabilities. The McDiarmid inequality (also known as the bounded difference inequality) is a generalization of Hoeffding's inequality to multivariate functions: if a function $f$ changes by at most $c_i$ when the $i$-th coordinate is altered, then the probability that $f(X_1,\dots,X_n)$ deviates from its expectation is at most $2\exp(-2t^2/\sum c_i^2)$. This inequality is widely used to analyze generalization error, sample complexity, and properties of random graphs in randomized algorithms. However, its bounded difference assumption implicitly requires finite sensitivity of each variable, making it unable to directly handle heavy-tailed distributions or functions sensitive to extreme values.

Core Contribution: One-Sided Concentration and Exponential Decay Under Infinite Variance

The core conclusion of the paper is: for a function of independent random variables, if the function is almost surely upper-bounded and satisfies a conditional moment assumption of order $p\in(1,2]$, then the deviation of the function value above its mean remains exponentially unlikely. When $p<2$, this conclusion holds even when the function has infinite variance.

The key to this result is "one-sidedness"—it only concerns upper-tail deviations rather than two-sided symmetric deviations. In many practical scenarios, we care more about upper bounds on risk (e.g., worst-case algorithm performance) than lower bounds. One-sided inequalities allow for tighter bounds under weaker assumptions.

Compared to the classical McDiarmid inequality, the new result replaces the bounded difference condition with a conditional moment assumption and replaces two-sided boundedness with a one-sided upper bound. This means that for heavy-tailed distributions, we no longer need artificial truncation or assumptions of finite variance; as long as the moment condition is satisfied, exponential concentration can be achieved.

Heavy-Tailed Distributions and Conditional Moment Assumptions

Heavy-tailed distributions refer to distributions whose tail probabilities decay slower than exponentially, such as Pareto distributions, Student's t-distributions, and log-normal distributions. Higher-order moments of such distributions may not exist or may diverge, leading to infinite variance. Heavy-tailed phenomena are ubiquitous in finance, networks, and natural language. Classical concentration inequalities typically require finite variance or exponential moments, thus failing for heavy-tailed data. The $p$-th order conditional moment assumption ($p\in(1,2]$) adopted in this paper states: conditional on the other variables, the $p$-th central moment of the $i$-th variable is controlled by some constant, but the variance is allowed to diverge. This condition is weaker than finite variance, yet it suffices to guarantee exponential decay of one-sided deviations. When $p<2$, the variance is infinite, but the $p$-th moment is finite, which is enough to derive non-trivial concentration bounds.

Reverse KL Tensorization: The Core Engine of the Proof

To prove the above inequality, the authors developed a new tensorization inequality called "reverse KL tensorization." Tensorization is a common technique in concentration inequality proofs that extends a property from a single variable to a product space of multiple variables. Classical methods typically use Hoeffding's lemma or the chain rule for KL divergence.

Reverse KL tensorization focuses on a certain reverse form of the Kullback-Leibler divergence. Specifically, it provides how the reverse KL divergence under a product distribution can be controlled by the reverse KL divergences of the marginal distributions. This tool may have value independent of the paper's main conclusion—for example, in variational inference, information geometry, or high-dimensional statistics, where reverse KL divergence often appears in expectation propagation and moment matching methods.

The authors point out that this tensorization inequality allows them to bypass the traditional bounded difference assumption and instead leverage the conditional moment condition. This provides a new pathway for handling heavy-tailed distributions.

KL Divergence and Tensorization Techniques

The Kullback-Leibler (KL) divergence is an information-theoretic measure of the difference between two probability distributions, defined as $D_{KL}(P|Q)=\int \log(dP/dQ)dP$. The reverse KL divergence swaps the positions of P and Q, i.e., $D_{KL}(Q|P)$, and is commonly used in variational inference for expectation propagation and moment matching because it tends to find approximate distributions that cover all modes. Tensorization is a technique for extending univariate inequalities to product spaces, with classical examples including Hoeffding's lemma (for bounded variables) and the chain rule. The reverse KL tensorization inequality proposed in this paper gives an upper bound relationship between the reverse KL divergence under a product distribution and the reverse KL divergences of the marginals, enabling inductive proofs using conditional moment conditions without relying on the bounded difference assumption. This tool may have independent value for information geometry and variational inference.

Applications: From Sample Means to Unbounded Risk

The paper demonstrates several applications of the new inequality:

Sample Mean and Median-of-Means Estimators: For heavy-tailed distributions, concentration of the sample mean typically requires finite variance. The new result provides a one-sided exponential bound under only a $p$-th moment condition. The median-of-means estimator is a robust mean estimation method for heavy-tailed data, and the new inequality provides sharper upper bounds on its deviation.

One-Sided Uniform Risk Bounds for Unbounded Losses: In statistical learning theory, when the loss function is unbounded, uniform risk bounds typically require complex conditions. The new result allows obtaining uniform risk bounds for unbounded losses under one-sided upper bounds and conditional moment assumptions. This is quite important for analyzing convergence of learning algorithms under heavy-tailed noise.

These applications show that the new inequality not only possesses theoretical elegance but can also directly serve algorithm analysis.

Median-of-Means Estimators

The median-of-means (MoM) estimator is a robust mean estimation method for heavy-tailed distributions. The basic idea is to divide the sample into several groups, compute the mean of each group, and then take the median of these means. Compared to the sample mean, the MoM estimator achieves exponential concentration under only finite variance or even lower-order moments, and is therefore widely used in statistical inference and machine learning under heavy tails. The new inequality in this paper provides sharper one-sided upper bounds on the deviation of the MoM estimator, especially when only $p$-th moments ($p<2$) are available, exponential decay is still guaranteed. This helps analyze convergence of learning algorithms under heavy-tailed noise.

Comparison with Classical Results and Potential Impact

The classical McDiarmid inequality requires the function to satisfy a bounded difference condition, i.e., changing any variable changes the function value by at most a constant $c_i$. This essentially requires the function to be Lipschitz in each variable and the random variables to be bounded. The new result relaxes the conditions to: the function is almost surely upper-bounded and satisfies a conditional $p$-th moment assumption. When $p=2$, it degenerates to the finite variance case; when $p<2$, infinite variance is allowed.

The cost of this relaxation is obtaining only a one-sided bound rather than a two-sided bound. But in many applications, a one-sided bound suffices—for example, when we only care that the risk does not exceed a certain threshold.

From an information-theoretic perspective, reverse KL tensorization provides a new analytical paradigm. Traditional concentration inequalities are often proved via moment generating functions or entropy methods, whereas reverse KL divergence is more natural in variational inference. This work may promote further integration of concentration inequalities with information-theoretic methods.

Summary and Outlook

This paper takes a meaningful step in the field of heavy-tailed concentration inequalities. By introducing reverse KL tensorization, the authors prove that under only one-sided boundedness and conditional moment assumptions, one-sided large deviations of functions of independent random variables still decay exponentially. This extends the applicability boundary of the McDiarmid inequality and provides a new tool for risk analysis with unbounded losses.

Future directions may include: extending the results to weakly dependent settings, exploring applications of reverse KL tensorization to other concentration phenomena, and studying the specific algorithmic implications of this inequality in online learning or high-dimensional statistics. For researchers working in statistical learning theory or heavy-tailed data analysis, this work is worth reading in depth.