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.
Figures & tables
Method
Tail behaviors covered
Allows non-uniform dependence on earlier variables
Allows non-uniform dependence on later variables
Tightest constants
Theorem 2.1
General MGF or Orlicz-norm bound
yes
yes
no
Generalized McDiarmid [ 2 ]
General MGF or Orlicz-norm bound
no
yes
no
Entropy method [ 12 ]
sub-Gaussian or sub-exponential
no
no
no
Sub-Gaussian diameter [ 9 ]
sub-Gaussian
no
no
no
McDiarmid’s inequality [ 13 ]
compact support
no
no
yes
Table 1: Comparison of our Theorem 2.1 with the generalized McDiarmid result from [ 2 ] , the entropy-based approach of [ 12 ] , the sub-Gaussian diameter method from [ 9 ] , and McDiarmid’s inequality [ 13 ] .
While algorithmic stability is a central tool for understanding generalization of learning algorithms, existing high-probability guarantees typically rely on uniform boundedness or sub-Gaussian/sub-Weibull tail assumptions, which can be overly restrictive for modern settings with heavy-tailed or unbounded losses. We develop a stability-based framework that requires only a finite Lp moment condition. Our first contribution is sharp concentration inequalities for functions of independent random variables under Lp constraints, extending McDiarmid's bounded-differences techniques beyond the classical regime. Leveraging these results, we derive sharp high-probability generalization bounds across a range of learning paradigms, including empirical risk minimization, transductive regression, and meta-learning. These guarantees show that Lp stability suffices for robust generalization even when boundedness fails, substantially weakening the standard assumptions in the stability literature.
Qianqian Lei, Soham Bonnerjee, Yuefeng Han +1
Department of Statistics, The University of Chicago, Chicago, IL 60637, USA. · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, IN 46556, USA.
Minimax optimization refers to a class of optimization problems with some variables to minimize and other variables to maximize. Biased stochastic gradient methods have shown practical success in solving minimax problems to either improve robustness, enhance communication efficiency, or decrease computational costs. These successes motivate a lot of theoretical works to study the convergence of biased stochastic gradient methods, while their generalization analysis remains untouched. In this paper, we present the first framework to study the stability and generalization of biased stochastic gradient methods for minimax problems. We establish a connection between stability and generalization for minimax problems by relaxing the existing bounded gradient assumption to a bounded second moment condition. We then introduce a generalized Lipschitz-type condition on bias and gradient estimators, and derive a general stability bound to clarify the connection among bias, gradient estimators, and stability. We apply our general analysis to Zeroth-order and Clipped stochastic gradient descent ascent (SGDA), and derive stability bounds that match those of SGDA under appropriate smoothing/clipping parameters. We combine stability and convergence analyses together, and derive optimal excess risk bounds of order 1/n, where n is the sample size.
Shuang Zeng, Yunwen Lei, Yiming Ying
Department of Mathematics, The University of Hong Kong, Hong Kong, China · School of Mathematics and Statistics, The University of Sydney, Sydney, Australia
We establish maximal concentration bounds for the iterates generated by stochastic approximation algorithms with general step sizes, where the noise has a finite-state Markovian component plus a Martingale-difference component. When the Martingale-difference noise is bounded, we show that the tail of the error can be sub-Gaussian, sub-Weibull, or something lighter than any Pareto but heavier than any Weibull, depending on the step size sequence and on whether the random operator is almost surely contractive, almost surely non-expansive, or expansive with positive probability. Our analysis relies on a novel Lyapunov function involving the moment-generating function of the solution to a Poisson equation, together with an auxiliary projected algorithm. We complement the upper bounds with worst-case examples showing that qualitatively sharper bounds are impossible. We further study the case of unbounded Martingale-difference noise when the average operator is contractive, and the step sizes are of order 1/k. In this setting, we show that if the random operator is almost surely non-expansive, then the error tail is at most three times heavier than the noise tail, whereas if the random operator is expansive with positive probability, then the error may have substantially heavier tails. These results are obtained through a novel black-box truncation argument that reduces the unbounded-noise setting to the bounded-noise case.
Shubhada Agrawal, Siva Theja Maguluri, Martin Zubeldia
Indian Institute of Science · Georgia Institute of Technology · University of Minnesota