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.

Machine Learning (stat.ML); Machine Learning (cs.LG)

arXiv:2610.17159 [stat.ML]

(or arXiv:2610.17159v1 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2610.17159 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.