Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization
This work addresses a bottleneck in optimization algorithms for non-convex learning, offering improved efficiency for researchers and practitioners in machine learning, though it is incremental as it builds on existing continuized acceleration methods.
The paper tackles the problem of inefficient gradient evaluations in accelerated algorithms for quasar convex functions in non-convex optimization by applying continuized Nesterov acceleration, achieving the optimal bound with high probability. It also broadens applicability by showing that training generalized linear models satisfies quasar convexity and that accelerated linear rates are possible for certain function classes under quasar convexity.
Quasar convexity is a condition that allows some first-order methods to efficiently minimize a function even when the optimization landscape is non-convex. Previous works develop near-optimal accelerated algorithms for minimizing this class of functions, however, they require a subroutine of binary search which results in multiple calls to gradient evaluations in each iteration, and consequently the total number of gradient evaluations does not match a known lower bound. In this work, we show that a recently proposed continuized Nesterov acceleration can be applied to minimizing quasar convex functions and achieves the optimal bound with a high probability. Furthermore, we find that the objective functions of training generalized linear models (GLMs) satisfy quasar convexity, which broadens the applicability of the relevant algorithms, while known practical examples of quasar convexity in non-convex learning are sparse in the literature. We also show that if a smooth and one-point strongly convex, Polyak-Lojasiewicz, or quadratic-growth function satisfies quasar convexity, then attaining an accelerated linear rate for minimizing the function is possible under certain conditions, while acceleration is not known in general for these classes of functions.