首次实现流形上非光滑非凸随机优化的有限时间分析，性能可期。
Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds
- 引入Riemann流形上的Goldstein驻点作为优化指标，设计RO2NC算法
- 在$O(ε^{-3}δ^{-1})$样本复杂度下找到$(δ,ε)$-驻点，达到最优
- 无梯度版本ZO-RO2NC同样具备相同复杂度，适合梯度不可用场景
本文研究流形约束下的随机非光滑非凸优化的有限时间分析。将Goldstein驻点概念拓展至Riemann流形，作为非光滑优化的性能度量。提出Riemannian Online to NonConvex（RO2NC）算法，并证明其在$O(ε^{-3}δ^{-1})$样本复杂度下可找到$(δ,ε)$-驻点。该结果是首个针对完全非光滑、非凸流形优化的有限时间保证，且与欧氏空间最优复杂度一致。当梯度信息不可用时，进一步构建了零阶版本ZO-RO2NC算法，同样达到相同复杂度。数值实验验证了理论分析，并展示了算法的实际有效性。
原文摘要 · Abstract (English)
This work addresses the finite-time analysis of nonsmooth nonconvex stochastic optimization under Riemannian manifold constraints. We adapt the notion of Goldstein stationarity to the Riemannian setting as a performance metric for nonsmooth optimization on manifolds. We then propose a Riemannian Online to NonConvex (RO2NC) algorithm, for which we establish the sample complexity of $O(ε^{-3}δ^{-1})$ in finding $(δ,ε)$-stationary points. This result is the first-ever finite-time guarantee for fully nonsmooth, nonconvex optimization on manifolds and matches the optimal complexity in the Euclidean setting. When gradient information is unavailable, we develop a zeroth order version of RO2NC algorithm (ZO-RO2NC), for which we establish the same sample complexity. The numerical results support the theory and demonstrate the practical effectiveness of the algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。