On McDiarmid's Inequality under Dependence via Approximate Tensorization of Entropy
Provides a unified framework and sharper concentration inequalities for dependent data, benefiting statisticians and learning theorists working with non-i.i.d. observations.
The paper shows that approximate tensorization of entropy (ATE) implies McDiarmid's inequality and derives new dependent McDiarmid inequalities for non-isotropic Gaussians and strongly log-concave measures. These yield improved Dvoretzky-Kiefer-Wolfowitz-type inequalities with $1/\\sqrt{n}$ rate under weak dependence, resolving a question on concentration of sign(X) and improving prior $n^{-1/3}$ rates.
We argue that dependent versions of McDiarmid's inequality are a useful but underutilized tool in mathematical statistics, learning theory and theoretical computer science. To make this point, we first highlight that approximate tensorization of entropy (ATE) implies McDiarmid's via the Entropy Method. Second, we derive McDiarmid's inequality for non-isotropic Gaussian random vectors $X \sim \mathcal N(μ, Σ)$ through ATE with a constant of the order of the condition number of $Σ$. We both independently obtain this ATE through a simple application of stochastic localization and also discuss how a more general ATE for the Gibbs sampler due to Ascolani et al., 2026 generalizes McDiarmid's-like concentration to strongly log-concave and log-smooth probability measures. We then apply the resulting concentration inequalities to resolve a question on the concentration of $\operatorname{sign}(X)$ posed by Simone Bombari, investigate Erdős-Rényi graphs under dependence and prove a Dvoretzky-Kiefer-Wolfowitz-type inequality for observations from a joint measure fulfilling ATE and continuous marginal CDFs. For the class of strongly log-concave and log-smooth measures, this result improves upon a prior Dvoretzky-Kiefer-Wolfowitz-type inequality for non-i.i.d. observations due to Bobkov and Götze, 2010, by establishing the expected $1/\sqrt{n}$-rate of convergence under weak dependence instead of $n^{-1/3}$.