首次实现带约束的拟凸优化加速算法，突破原有理论瓶颈。
Smooth Quasar-Convex Optimization with Constraints
- 设计不精确加速近端点算法解决带约束拟凸优化问题
- 达成最优复杂度˜O(1/(γ√ε))次一阶查询，优于现有方法
- 适用于流形优化、线性系统等场景，适合优化研究者参考
拟凸函数是一类广泛存在的非凸函数，应用于线性动力系统、广义线性模型及黎曼优化等领域。现有几乎最优算法仅适用于仿射空间，因一般凸约束导致自由度损失而无法推广。本文通过设计一种不精确加速近端点算法，并结合一阶方法，首次实现了在带一般凸约束条件下对γ-拟凸光滑函数的˜O(1/(γ√ε))次一阶查询的加速，解决了Martínez-Rubio（2022）与Lezane、Langer、Koolen（2024）提出的开放问题。该方法改进了此前基于测地线的黎曼优化加速解法复杂度。我们还分析了投影梯度下降与Frank-Wolfe算法在此设定下的表现。据我们所知，这是首个针对带一般凸约束的拟凸光滑函数的一阶方法分析。
原文摘要 · Abstract (English)
Quasar-convex functions form a broad nonconvex class with applications to linear dynamical systems, generalized linear models, and Riemannian optimization, among others. Current nearly optimal algorithms work only in affine spaces due to the loss of one degree of freedom when working with general convex constraints. Obtaining an accelerated algorithm that makes nearly optimal $\widetilde{O}(1/(γ\sqrt{\varepsilon}))$ first-order queries to a $γ$-quasar convex smooth function \emph{with constraints} was independently asked as an open problem in Martínez-Rubio (2022); Lezane, Langer, and Koolen (2024). In this work, we solve this question by designing an inexact accelerated proximal point algorithm that we implement using a first-order method achieving the aforementioned rate and, as a consequence, we improve the complexity of the accelerated geodesically Riemannian optimization solution in Martínez-Rubio (2022). We also analyze projected gradient descent and Frank-Wolfe algorithms in this constrained quasar-convex setting. To the best of our knowledge, our work provides the first analyses of first-order methods for quasar-convex smooth functions with general convex constraints.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。