Smooth Quasar-Convex Optimization with Constraints
This solves a theoretical bottleneck in optimization for applications like linear dynamical systems and generalized linear models, though it is incremental in advancing known methods.
The paper tackles the problem of optimizing quasar-convex smooth functions with general convex constraints, which was an open problem, and presents an inexact accelerated proximal point algorithm achieving a nearly optimal rate of Õ(1/(γ√ε)) first-order queries, improving upon prior work in Riemannian optimization.
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ε))$ 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.