A Generalized McDiarmid Inequality: Sample Reuse and Non-Uniform Unbounded Differences
Abstract
We develop a novel generalization of McDiarmid's concentration inequality and use it to obtain a uniform law of large numbers result and error bounds on stochastic optimization problems which simultaneously incorporate two key features: 1) They capture the benefit of training sample reuse in algorithms that also employ easily-sampled auxiliary random variables. 2) They allow for one-component mean-difference bounding functions which are both unbounded in the component of interest and have non-uniform dependence on another component. We demonstrate the utility of our method by deriving concentration inequalities for score-based generative modeling. This application naturally leverages both key features of our new tools: 1) It utilizes auxiliary Gaussian random variables in conjunction with the training samples; accounting for training sample reuse results in tighter error bounds by effectively integrating out the dependence on the auxiliary random variables. 2) The ability to handle non-uniform mean-difference bounding functions allows us to treat unbounded score models and data distributions with unbounded support.
Related
- A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization
- Distribution-Dependent Improvements of McDiarmid's Inequality via Rényi Divergence
- A motivic Vojta inequality for non-CM elliptic curves with unbounded height
- Uniform-in-N Log-Sobolev Inequality for the Mean-Field Langevin Dynamics with Convex Energy
- Uniform many-particle spectral gap inequality and heat kernel bounds for strong attractive interactions
BibTeX
@misc{birrell2026generalized,
title = {{A Generalized McDiarmid Inequality: Sample Reuse and Non-Uniform Unbounded Differences}},
author = {Jeremiah Birrell},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17159},
eprint = {2610.17159},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17159},
}
RIS
TY - UNPB
TI - A Generalized McDiarmid Inequality: Sample Reuse and Non-Uniform Unbounded Differences
AU - Jeremiah Birrell
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17159
UR - https://arxiv.org/abs/2610.17159
AB - We develop a novel generalization of McDiarmid's concentration inequality and use it to obtain a uniform law of large numbers result and error bounds on stochastic optimization problems which simultaneously incorporate two key features: 1) They capture the benefit of training sample reuse in algorithms that also employ easily-sampled auxiliary random variables. 2) They allow for one-component mean-difference bounding functions which are both unbounded in the component of interest and have non-uniform dependence on another component. We demonstrate the utility of our method by deriving concentration inequalities for score-based generative modeling. This application naturally leverages both key features of our new tools: 1) It utilizes auxiliary Gaussian random variables in conjunction with the training samples; accounting for training sample reuse results in tighter error bounds by effectively integrating out the dependence on the auxiliary random variables. 2) The ability to handle non-uniform mean-difference bounding functions allows us to treat unbounded score models and data distributions with unbounded support.
ER -