Lower bounds for non-convex stochastic optimization

By Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nati Srebro, Blake E. Woodworth. 2019

476 citations recorded by the source corpus.

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 $$\epsilon ^{-4}$$ ϵ - 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 $$\epsilon ^{-3}$$ ϵ - 3 queries, establishing the optimality of recently proposed variance reduction techniques.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

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 Statistics and Probability

Citations in the corpus

Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “References [1] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth.”
Momentum Improves Normalized SGD (2020, background): “However, it has recently been shown that the O (1 /T / 4 ) rate is optimal in the worst-case (Arjevani et al., 2019), and so improvements must either make more assumptions about the problem setting, or provide an algorithm that can somehow interpolate between a worst-case and non-worst-case problem.”
Learning from History for Byzantine Robust Optimization (2020, methodology): “In contrast, current theory claims that gradient descent (without momentum) is already optimal for non-convex optimization (Arjevani et al., 2019).”
Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function (2020, background): “As indicated in [2], our O ( ε−3 ) oracle complexity is optimal under the considered assumptions.”
Why are Adaptive Methods Good for Attention Models? (2020, background): “…f with stochastic gradients satisfying Assumption 1 for any given σ ≥ c 1 (cid:112) ( f (0) − f ∗ ) L such that the output x k of the algorithm A after processing k stochastic gradients has an error Theorem 6, proven in Appendix G, extends the recent work of [2, Theorem 1] to heavy-tailed noise.”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, background): “The standard convergence theory for SGD (Robbins and Monro, 1951; Nemirovski and Yudin, 1978, 1983; Shalev-Shwartz et al., 2007; Nemirovski et al., 2009; Arjevani et al., 2019; Hardt et al., 2016) in the smooth nonconvex setting shows slow sub-linear convergence to a stationary point.”
Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, background): “It is obvious that the lower bound complexity of finding an O(ε)-stationary point of Φ is no smaller than that of finding an O(ε)-stationary point of g, which requires at least O(ε−3) stochastic gradient evaluations [6].”
Personalized Federated Learning with Theoretical Guarantees: A Model-Agnostic Meta-Learning Approach (2020, background): “This is the classic result for stochastic gradient descent for nonconvex functions, and we recover the lower bounds [42].”