放松随机优化的方差假设，提升算法适用性与收敛性分析。
Towards Weaker Variance Assumptions for Stochastic Optimization
- 提出更弱的方差假设，放宽对优化变量增长的限制。
- 实现无需预知迭代次数的即时算法，获得最优最后迭代率。
- 适用于带函数约束或极小极大问题，无需可行集有界。
我们重新审视了经典随机梯度算法分析中的一个假设：允许随机次梯度的平方范数（或光滑问题的方差）随优化变量的平方范数以相同速度增长。从1960年代起源出发，结合近年文献中独立出现的类似设定，阐明其与目前已知最弱方差假设的关系，并探讨其在非Lipschitz非光滑凸优化中的作用。我们基于近期发现的该假设与Halpern迭代的联系，针对凸非光滑及可能随机的优化问题，分析了无时域依赖、支持任意时刻输出的算法，获得最后迭代点的收敛速率。对于超出简单约束优化的问题，如带函数约束的凸问题或正则化凸-凹极小极大问题，所得最优性度量的收敛速率不依赖于可行集的有界性。
原文摘要 · Abstract (English)
We revisit a classical assumption for analyzing stochastic gradient algorithms where the squared norm of the stochastic subgradient (or the variance for smooth problems) is allowed to grow as fast as the squared norm of the optimization variable. We contextualize this assumption in view of its inception in the 1960s, its seemingly independent appearance in the recent literature, its relationship to weakest-known variance assumptions for analyzing stochastic gradient algorithms, and its relevance in deterministic problems for non-Lipschitz nonsmooth convex optimization. We build on and extend a connection recently made between this assumption and the Halpern iteration. For convex nonsmooth, and potentially stochastic, optimization, we analyze horizon-free, anytime algorithms with last-iterate rates. For problems beyond simple constrained optimization, such as convex problems with functional constraints or regularized convex-concave min-max problems, we obtain rates for optimality measures that do not require boundedness of the feasible set.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。