Lower bounds for finding stationary points I

By Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford. 2017

348 citations recorded by the source corpus.

We prove lower bounds on the complexity of finding ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-stationary points (points x such that ‖∇f(x)‖≤ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Vert \nabla f(x)\Vert \le \epsilon $$\end{document}) of smooth, high-dimensional, and potentially non-convex functions f. We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives of f at a query point x. We show that for any (potentially randomized) algorithm A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {A}$$\end{document}, there exists a function f with Lipschitz pth order derivatives such that A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {A}$$\end{document} requires at least ϵ-(p+1)/p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon ^{-(p+1)/p}$$\end{document} queries to find an ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-stationary point. Our lower bounds are sharp to within constants, and they show that gradient descent, cubic-regularized Newton’s method, and generalized pth order regularization are worst-case optimal within their natural function classes.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “[8] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford.”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, background): “The O (1/N) rate for GD is the best possible worst-case dimensionfree rate of convergence for any algorithm (Carmon et al., 2019); faster convergence rates in the noiseless setting are available under the mild assumption of additional smoothness (Agarwal et al.”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, background): “This is due to the fact that for general non-convex smooth problems, finding an ε–stationary solution requires at least Ω(ε−2) gradient evaluations [7, 47].”
Complexity of finding near-stationary points of convex functions stochastically (2018, result): “This rate is in sharp contrast to the blackbox optimal complexity of O(ε−2) in smooth nonconvex optimization [2], trivially achieved by gradient descent.”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “For smooth deterministic non-convex functions (σ = 0), Carmon et al. (2017) show a lower bound of Ω(1/ǫ) for exact gradient methods to reach an ǫ stationary point.”
FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data (2020, methodology): “The proof is related to techniques developed from the classical and recent works that characterize lower bounds for first-order methods, in both centralized [27, 28] and decentralized [29] settings.”
Lower bounds for non-convex stochastic optimization (2019, methodology): “In contrast, in the non-convex case the noiseless complexity L −2 [15] and the estimation complexity σ 2 −2 multiply rather than add.”
L ] 1 0 A pr 2 01 9 AdaGrad-Norm convergence over nonconvex landscapes AdaGrad stepsizes : sharp convergence over nonconvex landscapes , from any initialization (2019, methodology): “It is becoming common to define an ε-approximate stationary point as ‖∇F (x)‖ ≤ ε (Agarwal et al., 2017; Carmon et al., 2018, 2017a; Fang et al., 2018; Zhou et al., 2018; Allen-Zhu, 2018), but we use the convention ‖F (x)‖2 ≤ ε (Lei et al., 2017; Bottou et al., 2018) to most easily compare our…”
Understanding the acceleration phenomenon via high-resolution differential equations (2018, methodology): “On a related note, given the centrality of the problem of finding an approximate stationary point in the nonconvex setting [16], it is worth using the high-resolution ODE framework to explore possible applications of the faster rate for minimizing the squared gradient norm that we have uncovered.”
Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity (2019, background): “We follow the notation from Carmon et al. (2017).”
Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, methodology): “[13] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford.”
Lower Bound for Randomized First Order Convex Optimization (2017, background): “We would like to thank the authors of [1] Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford for pointing out a mistake with our original proof of Lemma 3, which has since been corrected.”
The Complexity of Making the Gradient Small in Stochastic Convex Optimization (2019, background): “It is possible to extend the lower bound to randomized algorithms; see discussion in Carmon et al. (2017b).”
Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective (2019, background): “Computing lower bounds in zeroth order non-convex optimization is still an open problem (Carmon et al., 2017a,b).”
Minibatch vs Local SGD for Heterogeneous Distributed Learning (2020, neutral): “[5] and define: Definition 1 (Distributed zero-respecting algorithm).”
Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms (2018, methodology): “Our proof combines ideas from the classical proof in Nesterov [16], as well as two recent constructions [11] (for centralized problems) and [8] (for strongly convex distributed problems).”
Adaptive norms for deep learning with regularized Newton methods (2019, methodology): “These rates are optimal for second-order Lipschitz continuous functions (Carmon et al., 2017; Cartis et al., 2012a) and they can be retained even when only sub-sampled gradient and Hessian information is used (Kohler & Lucchi, 2017; Yao et al.”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “We emphasize that Assumptions 1, 2, and 3 are standard for non-convex stochastic optimization (Agarwal et al., 2017; Carmon et al., 2017b; Jin et al., 2017a; Xu et al., 2017; Allen-Zhu & Li, 2018).”
Rényi Fair Inference (2019, background): “More-over, this rate of convergence matches the oracle lower bound for general non-convex optimization; see Carmon et al. (2019).”