Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes

By Ohad Shamir, Tong Zhang. 2012

637 citations recorded by the source corpus.

Stochastic Gradient Descent (SGD) is one of the simplest and most popular stochastic optimization methods. While it has already been theoretically studied for decades, the classical analysis usually required non-trivial smoothness assumptions, which do not apply to many modern applications of SGD with non-smooth objective functions such as support vector machines. In this paper, we investigate the performance of SGD without such smoothness assumptions, as well as a running average scheme to convert the SGD iterates to a solution with optimal optimization accuracy. In this framework, we prove that after T rounds, the suboptimality of the last SGD iterate scales as O(log(T)/√T) for non-smooth convex objective functions, and O(log(T)/T) in the non-smooth strongly convex case. To the best of our knowledge, these are the first bounds of this kind, and almost match the minimax-optimal rates obtainable by appropriate averaging schemes. We also propose a new and simple averaging scheme, which not only attains optimal rates, but can also be easily computed on-the-fly (in contrast, the suffix averaging scheme proposed in Rakhlin et al. (2011) is not as simple to implement). Finally, we provide some experimental illustrations.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, 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 Statistics and Probability

In Optimization & Training

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “Besides smoothness and convexity, several papers (Shamir and Zhang, 2013; Recht et al., 2011; Hazan and Kale, 2014; Rakhlin et al., 2012) assume that the variance of the stochastic gradient is bounded; that is there exists a c such that Ei‖∇fi(x)‖2 ≤ c.”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “We compare our novel Frank-Wolfe approach to existing algorithms for training structural SVMs on the OCR dataset (n = 6251, d = 4028) from Taskar et al. (2003) and the CoNLL dataset (n = 8936, d = 1643026) from Sang & Buchholz (2000).”
Privacy Amplification by Decentralization (2020, methodology): “We can for instance rely on a classic result by [48] (Theorem 2 therein) which shows that SGD-type algorithms applied to a convex function and bounded convex domain converge in O(1/ √ T ) as long as gradients are unbiased with bounded variance.”
Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs (2020, methodology): “In particular, we use the following result from [SZ13].”
Privacy Amplification via Random Check-Ins (2020, positive): “One can view this line of reasoning to be analogous to privacy-preserving deep learning research, in that the theoretical guarantees for convex models acted as guiding principles for non-convex (deep learning) models [9, 1, 29].”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “The most widely used algorithms are stochastic gradient descent (SGD), a.k.a. Robbins-Monro algorithm (Robbins and Monro, 1951), and some of its modifications based on averaging of the iterates (Polyak and Juditsky, 1992; Ruppert, 1988; Shamir and Zhang, 2013).”
Local SGD Converges Fast and Communicates Little (2018, methodology): “Similar as in [15, 28, 34] we define a suitable averaging scheme for the iterates {x̄t}t≥0 to get the optimal convergence rate.”
On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization (2017, neutral): “Similar averaging approaches have been proposed (see Zhang et al. [2016]) in the literature, but their convergence behavior is not well understood, and it is unclear how they compare with ASGD approaches.”
The Value of Collaboration in Convex Machine Learning with Differential Privacy (2019, methodology): “This is based on the developments of [2] with appropriate changes in the averaging step to suit the ML problem with DP gradient queries.”
To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout (2015, background): “Theorem 12 (Convergence of expected stochastic gradient descent Shamir and Zhang [2013]) .”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, methodology): “For Lipschitz and strongly convex functions we use the following result by [43].”
Sparsified SGD with Memory (2018, methodology): “In contrast to [17] that use linearly increasing weights, we use quadratically increasing weights, as for instance [34, 36].”
Introduction to Online Convex Optimization (2016, background): “Tight convergence rates of SGD for strongly convex and non-smooth functions were only recently obtained in [57],[86],[102].”
An asynchronous parallel stochastic coordinate descent algorithm (2013, methodology): “gradient methods for regularized objectives (Beck and Teboulle, 2009), and stochastic gradient methods (Nemirovski et al., 2009; Shamir and Zhang, 2013).”
SGD: General Analysis and Improved Rates (2019, background): “Shamir & Zhang (2013) extended the analysis of SGD to convex non-smooth optimization (including the strongly convex case).”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, background): “Stochastic optimization has been extensively studied in the machine learning community [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”