Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization

By Saeed Ghadimi, Guanghui Lan, Hongchao Zhang. 2013

565 citations recorded by the source corpus.

This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are taken at each iteration depending on the total budget of stochastic samples allowed. The RSPG algorithm also employs a general distance function to allow taking advantage of the geometry of the feasible region. Complexity of this algorithm is established in a unified setting, which shows nearly optimal complexity of the algorithm for convex stochastic programming. A post-optimization phase is also proposed to significantly reduce the variance of the solutions returned by the algorithm. In addition, based on the RSPG algorithm, a stochastic gradient free algorithm, which only uses the stochastic zeroth-order information, has been also discussed. Some preliminary numerical results are also provided.

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

Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, background): “The Asynchronous Parallel Stochastic Gradient Descent ( A-PSGD ) [Agarwal and Duchi, 2011, Feyzmah-davian et al., 2016, Paine et al., 2013, Recht et al., 2011] breaks the synchronization in S-PSGD.”
Trajectory-wise Control Variates for Variance Reduction in Policy Gradient Methods (2019, background): “For example, the number of iterations for mirror descent to converge to an -approximate stationary point is O((Tr (Var[G]) + 1)/ (2)), increasing as the problem becomes more noisy [10].”
Stochastic model-based minimization of weakly convex functions (2018, methodology): “The second contribution removes the well-known “mini-batching” requirements common to [36, 67], while the ﬁrst signiﬁcantly expands the class of functions for which the rate of convergence of the stochastic proximal subgradient method is known.”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, methodology): “(2) Assumptions 1 (ii) (iii) are used in the analysis of Section 5, which are standard assumptions made in the literature of stochastic non-convex optimization [6, 7, 8].”
Complexity of finding near-stationary points of convex functions stochastically (2018, background): “5]), commonly used in convergence analysis of proximal gradient methods [7, 13].”
Fast Stochastic Methods for Nonsmooth Nonconvex Optimization (2016, methodology): “[7]: The number of IFO and PO calls made by ProxSgd , i.e., iteration (4) , to reach (cid:15) close to a stationary point is O (1 / 2 ) and O (1 /(cid:15) ) respectively.”
A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning: Principals, Recent Advances, and Applications (2020, methodology): “• ZO-PSGD [43]: By letting Π X be the Euclidean distance based projection operation, the point updating step (11) is given by • ZO-SMD [21]: Upon deﬁning a Bregman divergence D h ( x , y ) with respect to a strongly convex and differentiable function h , D h ( x , y ) = h ( x ) − h ( y ) − ( x − y )”
Analysis of nonsmooth stochastic approximation: the differential inclusion approach (2018, background): “fforts, at least in the smooth case (f gradient Lipschitz and g≡0); see forexample[23, 1] and the referencestherein. For the nonsmoothand nonconvex case, the results are still partial. Ghadimi et al. [24] considered the case where f is differentiable but possiblynonconvexandg is non-differentiablebu”
On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization (2019, methodology): “…the computation complexity, which is also known as the convergence rate, is measured by the decay law of the solution error with respect to the number of access of the stochastic first-order oracle (SFO) that provides sampled stochastic gradients (Nemirovsky & Yudin, 1983; Ghadimi et al., 2016).”
Adaptive Methods for Nonconvex Optimization (2018, background): “[9] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang.”
Dash: Semi-Supervised Learning with Dynamic Thresholding (2021, methodology): “Finally, we will prove that with a probability 1 − (4 t + 1) δ , we have To this end, using the notation of A and B , we can rewrite g t as where g at = using concentration inequality in Lemma 4 of [Ghadimi et al., 2016], we have with a probability 1 − 5 δ , ≤ 4 G 2 δa 0 mγ t − 1 .”
Convergence Rate of Frank-Wolfe for Non-Convex Objectives (2016, background): “Ghadimi et al. (2016) considers instead the norm of the gradient mapping as a measure of non-stationarity.”
Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions (2018, methodology): “In this regard, we improve in two fundamental ways on the results in the seminal papers [9,10,25]: first, we allow g to be nonsmooth and second, we do not require the variance of our stochastic estimator for ζt to decrease as a function of t.”
Stochastic Frank-Wolfe methods for nonconvex optimization (2016, background): “In the nonconvex setting, most of the work on stochastic methods focuses on SGD [8], [9] and analyzes convergence to stationary points.”
Stochastic Gradient Descent for Nonconvex Learning Without Bounded Gradient Assumptions (2019, background): “The first nonasymptotical convergence rate of nonconvex SGD was established in [5], which was extended to stochastic variance reduction [6] and stochastic proximal gradient descent [7].”