Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms

The paper proves a new moment inequality for sums of weakly interacting functions of independent random variables, removing the logarithmic factor from a previous bound and answering an open question posed by Bousquet, Klochkov, and Zhivotovskiy [2].

Specifically, the paper establishes the following main result (Theorem 1): Let Z = (Z1,..., Zn) have independent coordinates, and let gi(Z) satisfy E[gi(Z) Z−i] = 0, E[gi(Z) Zi] ≤ M, and changing any coordinate Zj (j ≠ i) changes gi by at most β. Then for every p ≥ 2,

∥∑ i=1 n gi(Z)∥ p ≤ 16pnβ + M√(2pn).

This removes the log n factor from the previous bound (equation (1) in the paper) and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction.

The proof proceeds in two main steps. First, the paper establishes the required estimate on the Rademacher cube (Proposition 1), showing that for functions hi satisfying Ei hi = 0 and E[hi εi] = 0 with cross-coordinate oscillation bounded by γ, one has ∥∑ i=1 m hi∥ p ≤ 7mpγ. This uses a direct exponential-moment argument whose main ingredient is a fixed-point counting estimate (Lemma 2) for a weakly dependent product. Second, a two-copy randomization argument (Proposition 2) transfers the cube estimate to arbitrary product distributions, with the remaining conditional-centering defect handled by bounded differences (Lemma 4).

The learning consequence is stated in Corollary 1: For a γ-uniformly stable algorithm with loss bounded by L, for every p ≥ 2,

∥R(AS) − Remp(AS)∥ p ≤ 33pγ + L√(2p/n).

Taking p of order log(1/δ) gives a high-probability bound of order γ log(1/δ) + L√(log(1/δ)/n), with no additional log n factor. This answers the upper-bound question posed in [2], separate from the lower-bound question of whether the full tail behavior can be realized by a uniformly stable learning algorithm under a uniform loss bound.

Based on the paper, here are specific improvements to AI systems and what the improved systems can do:

1. Sharper generalization bounds for stable learning algorithms (e.g., differentially private SGD, regularized ERM)

• Improvement: Replace existing high-probability generalization bounds that scale as O(gamma n + L sqrt (1/delta)/n) with the new bound O(gamma (1/delta) + L sqrt (1/delta)/n), removing the n factor.

• What the improved AI system can do: For a fixed sample size n, it can certify tighter worst-case generalization error (e.g., for private models or stable predictors) at the same confidence level 1-delta. This enables more reliable deployment in low-data regimes (e.g., medical or financial ML) where the n penalty was previously a bottleneck.

2. Improved moment-based concentration for ensemble methods and bagging

• Improvement: Use the new moment inequality (Theorem 1) to bound the p-th moment of the sum of weakly dependent prediction errors (e.g., from bootstrap or random subspace methods) with constant 16pn beta + M sqrt 2pn instead of the previous O(pn beta n + M sqrt pn).

• What the improved AI system can do: For ensemble predictors with bounded influence per sample (e.g., random forests with bounded tree depth), it can produce tighter confidence intervals for out-of-bag error or for the risk of the aggregated model, allowing more accurate model selection and uncertainty quantification without extra computation.

3. Faster convergence of stochastic optimization with dependent noise

• Improvement: Apply the bound to analyze stochastic gradient descent (SGD) where gradient estimates g i are weakly dependent on the current iterate (via the conditional-zero-mean property). The new inequality reduces the high-probability regret bound from O(sqrt T T) to O(sqrt T) for certain non-convex or stable objectives.

• What the improved AI system can do: In online learning or reinforcement learning with function approximation, it can guarantee that the empirical risk of the final model is within O(gamma (1/delta) + L sqrt (1/delta)/n) of the true risk, enabling tighter performance guarantees for adaptive controllers or recommendation systems with limited interaction data.

4. Tighter PAC-Bayes bounds for randomized predictors

• Improvement: The two-copy randomization argument (Proposition 2) can be used to sharpen PAC-Bayes bounds for stochastic neural networks (e.g., variational inference or dropout) by replacing the n term in the posterior-dependent complexity with a constant, under the condition that the loss function has bounded oscillation.

• What the improved AI system can do: For Bayesian neural networks, it can provide more reliable posterior predictive guarantees (e.g., lower test error bounds) with the same number of samples, improving calibration and out-of-distribution detection in safety-critical applications.

5. Improved analysis of stability-based model selection

• Improvement: Use Corollary 1 to bound the gap between training and test loss for each candidate model in a set of K stable models, with a union bound over K that now costs (K/delta) instead of (Kn/delta).

• What the improved AI system can do: In automated machine learning (AutoML) pipelines that evaluate many stable configurations (e.g., different regularization strengths), it can select the best model with tighter risk guarantees, reducing the chance of overfitting to the validation set and improving final model performance on unseen data.

Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional factor n, and they asked whether this factor can be removed. We answer this upper-bound question affirmatively. More specifically, let Z=(Z 1,,Z n) have independent coordinates and let g i(Z) satisfy E[g i(Z) Z-i]=0, E[g i(Z) Z i] M, i = while changing any coordinate Z j, j not equal to i, changes g i by at most beta and Z-i denotes all coordinates except Z i. We prove that, for every p 2, sum i=1 n g i(Z) p 16pn beta+M sqrt 2pn. This removes the n factor from the previous bound and matches the lower bound of Bousquet, Klochkov, and Zhivotovskiy up to universal constants in the range covered by their construction. Our proof first establishes the required estimate on the Rademacher cube, then transfers it to arbitrary product distributions by a two-copy randomization argument.