Stability and Generalization for Stochastic (Compositional) Optimizations

Xiaokang Pan, Jin Liu, Hulin Kuang, Youqi Li, Lixing Chen, Zhe Qu

This research, recently published for IJCAI-25, explores the intricate relationship between gradient estimation techniques during training and the resulting model performance on unseen data. While the machine learning community has traditionally focused on accelerating algorithmic convergence, this study asks a critical follow-up: does faster training always translate to better generalization?

Introduction

In modern machine learning, pure Stochastic Gradient Descent (SGD) is rarely used in isolation. Instead, practitioners employ advanced algorithms that use estimators—mathematical tools like momentum or variance reduction (VR)—to smooth noise and reach minima faster. However, most research focuses on convergence rates rather than generalization.

The authors specifically investigate Stochastic Compositional Optimization (SCO), where the objective function is nested (e.g., $f(g(x))$). This structure is prevalent in Model-Agnostic Meta-Learning (MAML) and Reinforcement Learning, where obtaining unbiased gradients is notoriously difficult, making the choice of estimator highly impactful.

Methods

The researchers analyze the problem through three primary avenues:

  1. A Generalized Framework: They propose a unified algorithmic framework for SCO that encompasses popular algorithms like SCGD, SCSC, and COVER, allowing for a direct comparison of different estimation strategies.
  2. New Stability Definitions: Generalization is often studied through "algorithmic stability." The authors introduce a novel definition specifically for non-convex SCO, focusing on the gradient of the objective rather than just the function value.
  3. Excess Risk Decomposition: They provide a new method to break down "excess risk" into generalization error and optimization error, specifically tailored for the non-convex settings common in deep learning.

Key Insights and Ideas

The STORM Paradox

In non-convex settings, the STORM algorithm (which uses recursive momentum) converges faster and generalizes better than SGD. However, in convex settings, this trend reverses: SGD actually maintains superior generalization despite being theoretically "slower" in convergence.

Figure 2: Comparison of Train and Test Loss for SGD and STORM in non-convex stochastic optimization. STORM shows faster convergence and better generalization.

Estimator Overkill and Noise Sensitivity

In convex SCO problems, the authors found that complex estimators for the gradient of the inner function are often unnecessary. A "vanilla" stochastic gradient can be used for that component without sacrificing generalization performance, significantly reducing computational overhead.

Crucially, generalization is highly sensitive to the estimation error of the inner function $g(x)$. If the estimator for the inner function is noisy, the generalization error compounds rapidly, as shown in the linear upward trend of error metrics.

Key Results

The paper provides a quantitative validation of these trade-offs:

  • COVER emerged as the strongest performer for non-convex SCO, achieving a convergence rate of $O(T^{-1/3})$ and the best generalization bounds among compared compositional algorithms.
  • STORM achieves an excess error bound of $O(n^{-1/4})$ in convex settings, while SGD maintains $O(n^{-1/2})$, explaining why SGD remains the gold standard for simpler convex tasks.
  • Sensitivity Analysis: Simulations explicitly show that as the "Estimation Error" of the inner function increases, the "Generalization Error" follows a nearly linear upward trend, confirming the theoretical stability bounds.
Figure 5: Generalization Error as a function of Estimation Error in Convex SCO. The linear relationship confirms the sensitivity of generalization to inner-function noise.

Conclusion

The findings suggest that while faster convergence generally aids generalization, the choice of estimator must be carefully matched to the problem's convexity. The authors suggest that future work should use these stability guidelines to design "generalization-aware" SCO algorithms that optimize for the most stable path to a solution, rather than just the fastest one.

Summary updated

Abstract

The use of estimators instead of stochastic gradients for updates has been shown to improve algorithm convergence rates of, but their impact on generalization remains under-explored. In this paper, we investigate how estimators influence generalization. Our focus is on two widely studied problems: stochastic optimization (SO) and stochastic compositional optimization (SCO), both under convex and non-convex settings. For SO problems, we first analyze the generalization error of the STORM algorithm as a foundational step. We then extend our analysis to SCO problems by introducing an algorithmic framework that encompasses several popular algorithmic approaches. Through this framework, we conduct a generalization analysis, uncovering new insights into the impact of estimators on generalization. Subsequently, we provide a detailed analysis of three specific algorithms within this framework: SCGD, SCSC, and COVER, to explore the effects of different estimator strategies. Furthermore, in the context of SCO, we propose a novel definition of stability and a new decomposition of excess risk in the non-convex setting. Our analysis indicates two key findings: (1) In SCO problems, eliminating the estimator for the gradient of the inner function does not impact generalization performance while significantly reducing computational and storage overhead. (2) Faster convergence rates are consistently associated with better generalization performance.
BibTeX
@inproceedings{pan2025stability,
  author = {Xiaokang Pan and Jin Liu and Hulin Kuang and Youqi Li and Lixing Chen and Zhe Qu},
  title = {{Stability and Generalization for Stochastic (Compositional) Optimizations}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/672},
}
Figure