Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming

By Saeed Ghadimi, Guanghui Lan. 2013

1,919 citations recorded by the source corpus.

In this paper, we introduce a new stochastic approximation (SA) type algorithm, namely the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming (SP) problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this method possesses a nearly optimal rate of convergence if the problem is convex. We discuss a variant of the algorithm which consists of applying a post-optimization phase to evaluate a short list of solutions generated by several independent runs of the RSG method, and show that such modification allows to improve significantly the large-deviation properties of the algorithm. These methods are then specialized for solving a class of simulation-based optimization problems in which only stochastic zeroth-order information is available.

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

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

In Optimization & Training

Citations in the corpus

Stochastic Training of Graph Convolutional Networks (2017, methodology): “This proof is a modification of Ghadimi & Lan (2013), but using biased stochastic gradients instead.”
Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “Since the optimal stepsize for steadily-decreasing SGD is 1 / ( L p k + 1) , where L is the global Lipschitz constant [13], it is pretty clear that ⌘ should be decreased over training for optimal converge (as L effectively increases).”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “A common technique to guarantee convergence to the exact optimum is to use a decreasing step-size (Robbins and Monro, 1951; Ghadimi and Lan, 2013; Gower et al., 2019; Nemirovski et al., 2009; Karimi et al., 2016).”
Large Batch Optimization for Deep Learning: Training BERT in 76 minutes (2019, background): “Note that such assumptions are typical in the analysis of stochastic ﬁrst-order methods (cf. (Ghadimi & Lan, 2013a; Ghadimi et al., 2014)).”
Federated Optimization in Heterogeneous Networks (2018, background): “…as SGD: Under the bounded variance assumption, for small , if we replace B with its upper-bound in Corollary 10 and choose µ large enough, the iteration complexity of FedProx when the subproblems are solved exactly and Fk(·)’s are convex is O(L∆ + L∆σ2 2 ), the same as SGD (Ghadimi & Lan, 2013).”
Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, neutral): “Algorithm Non-convex μ-Strongly convex Assumptions SERVER-ONLY SGD [8] G 2 S 2 + L G2 μS + L μ G(2)-BGD MVR [4] ( G √ S ) 3 2 + L – G(2)-BGD FEDAVG 1 FedSGD [15] G 2 S 2 + G 3/2 + L G2 μS + G μ √ + L μ G(2)-BGD MIME 2 MimeSGD G 2 S 2 + δ G2 μS + δ μ G(2)-BGD, δ-BHD MimeMVR ( G √ S ) 3 2 + δ – G(2)-B”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “To analyze the convergence rate of Algorithm 3, the next lemma(which originates from [59] but we use a version adapted from [18]) builds the connection between distributed SGD and mean estimation.”
Fair Resource Allocation in Federated Learning (2019, methodology): “In particular, to optimize q - FFL in a scalable fashion, we rely on gradient-based methods, where the step-size inversely depends on the Lipchitz constant of the function’s gradient, which is often unknown and selected via grid search [14, 29].”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, methodology): “With N parallel workers, parallel mini-batch SGD can solve problem (1) withO(1/ √ NT ) convergence, which is N times faster1 than the O(1/ √ T ) convergence attained by SGD over a single node (Ghadimi & Lan, 2013; Lian et al., 2015).”
cpSGD: Communication-efficient and differentially-private distributed SGD (2018, positive): “Similar (and stronger) results can be obtained for (strongly) convex functions using results in [16] and [29].”
D2: Decentralized Training over Decentralized Data (2018, background): “The SGD approahces [Ghadimi and Lan, 2013, Moulines and Bach, 2011, Nemirovski et al., 2009] is quite powerful for solving large-scale machine learning problems.”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “Note that if T = 0 and n = 1 the proposed AD-PSGD reduces to the vanilla SGD algorithm (Nemirovski et al., 2009; Moulines and Bach, 2011; Ghadimi and Lan, 2013).”
ZOO: Zeroth Order Optimization Based Black-box Attacks to Deep Neural Networks without Training Substitute Models (2017, background): “The convergence of these zeroth order methods has been proved in optimization literature [11, 25, 32], and under mild assumptions (smoothness and Lipschitzian gradient) they can converge to a stationary point with an extra error term which is related to gradient estimation and vanishes when h → 0.”