arXiv：cs.LG· Mingyi Li, Taira Tsuchiya, Kenji Yamanishi·· 3 小时前
复合在线到非凸转换：最优 Oracle 复杂度
Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity
AI 导读
研究者将在线到非凸转换框架扩展到含凸正则项的复合非光滑非凸优化场景，通过为在线学习器设计包含正则项本身的新损失函数，使算法在 O(δ⁻¹ε⁻³) 次随机梯度查询或 O(dδ⁻¹ε⁻³) 次函数值查询内找到 Goldstein 型稳定点。该复杂度与非复合情形的最优值一致，表明额外的凸正则项不会增加 oracle 复杂度。论文还给出了光滑情形的速率并进行了数值实验。
正文
Abstract:We consider stochastic nonsmooth nonconvex composite optimization, which includes several important problems such as constrained optimization and the regularized training of neural networks. The objective is the sum of a possibly nonsmooth nonconvex Lipschitz function and a convex regularizer, and the function is accessed through stochastic gradients or function values. The goal is to find a point that satisfies a Goldstein-type stationarity condition designed for composite objectives. To our knowledge, no oracle complexity bound for this setting is known under first-order access, and existing complexities under zeroth-order access are suboptimal. To handle this issue, we employ the framework of online-to-nonconvex conversion, which chooses update directions by an online learner and is known to achieve optimal rates for noncomposite problems. We extend the framework to our composite scenario by introducing new losses for the learner, which contain the regularizer itself rather than its linearization and for which a variant of online mirror descent achieves low regret. We show that the resulting algorithm finds such a point with $O(\delta^{-1}\varepsilon^{-3})$ stochastic gradient queries or $O(d\delta^{-1}\varepsilon^{-3})$ function-value queries, where $\delta$ is the Goldstein radius, $\varepsilon$ is the stationarity tolerance, and $d$ is the dimension. These rates match the optimal ones for noncomposite nonsmooth nonconvex optimization, demonstrating that the additional convex regularizer does not worsen the oracle complexity. We also give rates for the smooth case and present numerical experiments.
| Comments: | 27 pages, 3 figures, 2 tables |
| Subjects: | Machine Learning (cs.LG); Optimization and Control (math.OC); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.12328 [cs.LG] |
| (or arXiv:2610.12328v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.12328 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Mingyi Li [view email]
[v1]
Thu, 8 Oct 2026 17:08:11 UTC (7,336 KB)
来源：arXiv：cs.LG · arxiv.org