标题： Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations 显示英文标题

标题： Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations

摘要： 基于STOchastic Recursive Momentum (STORM)的算法已被广泛开发，用于解决一至$K$级($K \geq 3$)的随机优化问题。 具体而言，它们使用估计器来缓解有偏梯度问题，并实现接近最优的收敛结果。 然而，关于它们泛化性能的研究相对较少，特别是在从一至$K$级优化情境过渡时尤为明显。 本文对三种典型的基于STORM的算法：STORM、COVER和SVMR，在凸和强凸设置下，针对一、二和$K$级随机优化问题进行了全面的泛化分析。 首先，我们定义了$K$级优化的稳定性，并将其与泛化联系起来。 然后，我们详细阐述了三种突出的基于STORM的算法的稳定性结果。 最后，我们通过平衡稳定性结果与优化误差推导出它们的过量风险界。 我们的理论结果为完善基于STORM的算法提供了有力证据：(1) 每个估计器可能由于方差而降低其稳定性，这取决于其估计目标。 (2) 每增加一级可能会加剧泛化误差，这受到其累积随机梯度与真实梯度之间稳定性与方差的影响。 (3) 增加初始估计器计算的批量大小可以带来有利的权衡，从而提高泛化性能。 显示英文摘要

摘要： STOchastic Recursive Momentum (STORM)-based algorithms have been widely developed to solve one to $K$-level ($K \geq 3$) stochastic optimization problems. Specifically, they use estimators to mitigate the biased gradient issue and achieve near-optimal convergence results. However, there is relatively little work on understanding their generalization performance, particularly evident during the transition from one to $K$-level optimization contexts. This paper provides a comprehensive generalization analysis of three representative STORM-based algorithms: STORM, COVER, and SVMR, for one, two, and $K$-level stochastic optimizations under both convex and strongly convex settings based on algorithmic stability. Firstly, we define stability for $K$-level optimizations and link it to generalization. Then, we detail the stability results for three prominent STORM-based algorithms. Finally, we derive their excess risk bounds by balancing stability results with optimization errors. Our theoretical results provide strong evidence to complete STORM-based algorithms: (1) Each estimator may decrease their stability due to variance with its estimation target. (2) Every additional level might escalate the generalization error, influenced by the stability and the variance between its cumulative stochastic gradient and the true gradient. (3) Increasing the batch size for the initial computation of estimators presents a favorable trade-off, enhancing the generalization performance.