REVIEW 5 cited by
Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization
read the original abstract
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.
Forward citations
Cited by 5 Pith papers
-
Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization
A new step size rule lets boosted stochastic Frank-Wolfe match ordinary stochastic Frank-Wolfe rates on nonconvex and quasar-convex problems and deliver faster empirical convergence on sparse logistic regression and q...
-
Quasar-Convex Optimization: Fundamental Properties and High-Order Proximal-Point Methods
Quasar-convex functions admit high-order proximal algorithms with linear convergence for p=2 and superlinear for p>2 under suitable conditions.
-
Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
A continuized zeroth-order Nesterov method achieves O(d/√ε) function-evaluation complexity for smooth quasar-convex minimization, with improved dimension dependence under a 1-norm mirror step when the solution is sparse.
-
Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case
Proximal point algorithm achieves O(ε^{-1}) complexity for quasar-convex functions and linear convergence with O(ln(ε^{-1})) for strongly quasar-convex functions.
-
Robust Learning Meets Quasar-Convex Optimization: Inexact High-Order Proximal-Point Methods
Robust learning problems are formulated as quasar-convex optimization, and HiPPA is proposed as an inexact high-order proximal method with global and superlinear convergence guarantees.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.