The Complexity of Making the Gradient Small in Stochastic Convex Optimization

By Dylan J. Foster, Ayush Sekhari, Ohad Shamir, Nati Srebro, Karthik Sridharan, Blake E. Woodworth. 2019

60 citations recorded by the source corpus.

We give nearly matching upper and lower bounds on the oracle complexity of finding $\epsilon$-stationary points ($\| \nabla F(x) \| \leq\epsilon$) in stochastic convex optimization. We jointly analyze the oracle complexity in both the local stochastic oracle model and the global oracle (or, statistical learning) model. This allows us to decompose the complexity of finding near-stationary points into optimization complexity and sample complexity, and reveals some surprising differences between the complexity of stochastic optimization versus learning. Notably, we show that in the global oracle/statistical learning model, only logarithmic dependence on smoothness is required to find a near-stationary point, whereas polynomial dependence on smoothness is necessary in the local stochastic oracle model. In other words, the separation in complexity between the two models can be exponential, and that the folklore understanding that smoothness is required to find stationary points is only weakly true for statistical learning. Our upper bounds are based on extensions of a recent "recursive regularization" technique proposed by Allen-Zhu (2018). We show how to extend the technique to achieve near-optimal rates, and in particular show how to leverage the extra information available in the global oracle model. Our algorithm for the global model can be implemented efficiently through finite sum methods, and suggests an interesting new computational-statistical tradeoff.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

A Group-Theoretic Framework for Data Augmentation (2019, background): “We thank Dylan Foster for telling us about the results from Foster et al. (2019). This work was supported in part by NSF BIGDATA grant IIS 1837992 and NSF TRIPODS award 1934960.”
Lower bounds for non-convex stochastic optimization (2019, background): “A similar lower bound appeared in [27], but the result we prove here is slightly stronger because it holds even for dimension d = 1.”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “cannot be improved using acceleration. We believe that the iteration complexity of O(τ/ǫ) shown here is optimal. However, the second term stochastic rate of O(σ2/ǫ2) is probably suboptimal. Recently, Foster et al. (2019) show how to minimize the gradient norm at a rate of O(σ2/ǫ) for convex function”