Lower bounds for non-convex stochastic optimization

DOI10.1007/S10107-022-01822-7MaRDI QIDQ6038643zbMATH OpenOpenAlexFDO

Authors Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, Blake Woodworth

Publication date 2 May 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.02365

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Analysis of algorithms and problem complexity (68Q25) Nonconvex programming, global optimization (90C26) Stochastic programming (90C15) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We lower bound the complexity of finding $epsilon$-stationary points (with gradient norm at most $epsilon$) using stochastic first-order methods. In a well-studied model where algorithms access smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance, we prove that (in the worst case) any algorithm requires at least $epsilo{n}^{-4}$ queries to find an $epsilon$ stationary point. The lower bound is tight, and establishes that stochastic gradient descent is minimax optimal in this model. In a more restrictive model where the noisy gradient estimates satisfy a mean-squared smoothness property, we prove a lower bound of $epsilo{n}^{-3}$ queries, establishing the optimality of recently proposed variance reduction techniques.

Recommendations

• Lower bounds for finding stationary points I
• Lower bounds for finding stationary points II: first-order methods
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Stochastic nested variance reduction for nonconvex optimization
• Accelerated methods for nonconvex optimization

Cites work

• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• scientific article; zbMATH DE number 1064667 (Why is no real title available?)
• scientific article; zbMATH DE number 1149836 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• A geometric analysis of phase retrieval
• Black-Box Complexity of Local Minimization
• Complexity bounds for second-order optimality in unconstrained optimization
• Convergence of estimates under dimensionality restrictions
• Cubic regularization of Newton method and its global performance
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Information-Based Complexity, Feedback and Dynamics in Convex Programming
• Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
• Introductory lectures on convex optimization. A basic course.
• Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
• Lower bounds for finding stationary points I
• Lower bounds for finding stationary points II: first-order methods
• Lower bounds for parallel and randomized convex optimization
• On parallel complexity of nonsmooth convex optimization
• On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems
• Optimization methods for large-scale machine learning
• Some NP-complete problems in quadratic and nonlinear programming
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Stochastic dual coordinate ascent methods for regularized loss minimization
• Stochastic nested variance reduction for nonconvex optimization
• Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization

Cited in

(13)

• Accelerated doubly stochastic gradient descent for tensor CP decomposition
• Stochastic nested variance reduction for nonconvex optimization
• How to trap a gradient flow
• Oracle lower bounds for stochastic gradient sampling algorithms
• scientific article; zbMATH DE number 7370566 (Why is no real title available?)
• Stochastic inexact augmented Lagrangian method for nonconvex expectation constrained optimization
• Lower bounds for finding stationary points I
• High probability bounds on AdaGrad for constrained weakly convex optimization
• scientific article; zbMATH DE number 7626728 (Why is no real title available?)
• Convergence rates for stochastic approximation: biased noise with unbounded variance, and applications
• scientific article; zbMATH DE number 7625189 (Why is no real title available?)
• Asymptotic optimality in stochastic optimization
• The stochastic lower bound

This page was built for publication: Lower bounds for non-convex stochastic optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038643)