Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

By Deanna Needell, Rachel A. Ward, Nati Srebro. 2013

621 citations recorded by the source corpus.

We obtain an improved finite-sample guarantee on the linear convergence of stochastic gradient descent for smooth and strongly convex objectives, improving from a quadratic dependence on the conditioning (L/μ)2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(L/\mu )^2$$\end{document} (where L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L$$\end{document} is a bound on the smoothness and μ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu $$\end{document} on the strong convexity) to a linear dependence on L/μ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L/\mu $$\end{document}. Furthermore, we show how reweighting the sampling distribution (i.e. importance sampling) is necessary in order to further improve convergence, and obtain a linear dependence in the average smoothness, dominating previous results. We also discuss importance sampling for SGD more broadly and show how it can improve convergence also in other scenarios. Our results are based on a connection we make between SGD and the randomized Kaczmarz algorithm, which allows us to transfer ideas between the separate bodies of literature studying each of the two methods. In particular, we recast the randomized Kaczmarz algorithm as an instance of SGD, and apply our results to prove its exponential convergence, but to the solution of a weighted least squares problem rather than the original least squares problem. We then present a modified Kaczmarz algorithm with partially biased sampling which does converge to the original least squares solution with the same exponential convergence rate.

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, methodology): “The main algorithm in this literature is the celebrated randomized Kaczmarz (RK) method (Kaczmarz, 1937; Strohmer & Vershynin, 2009) which can be seen as special case of SGD for solving least square problems (Needell et al., 2016).”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “• We obtain the same condition on the step size for linear convergence to -accuracy of Hogwild as previous analysis for serial Sgd (e.g. Needell et al., 2014) – given τ ≤ 1/γµ.”
Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “The non-uniform sampling techniques used in the work of Nesterov (2012); Needell et al. (2014); Zhao & Zhang (2015) use Lipschitz constants of partial derivatives to obtain the sampling probabilities.”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “[38] have analyzed sampling according to theLipschitz constant in the context of SG iterations.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “Our re-sults show that in overparametrized settings no drift effects occur and linear convergence can be achieved similar as to the centralized setting (Schmidt & Roux, 2013; Needell et al., 2016; Ma et al., 2018).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “Such a result is derived from the analysis by Dieuleveut et al. (2017), combining the approach of Bach and Moulines (2013) with the correct upper bound for smooth strongly convex SGD (Needell et al., 2014), and controlling similarly higher order moments.”
Mitigating Sybils in Federated Learning Poisoning (2018, methodology): “FoolsGold reweighs clients in federated learning and is similar to importance sampling, which has been applied to SGD algorithms [26].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “For a theoretical analysis for convex functions we refer the reader to [66, 64, 65] and [87, 93] for SVM problems.”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, methodology): “We can refine our analysis by avoiding the uniform bound on ‖g(x, s)‖, through a simple application of the co-coercivity lemma as it was used in [26]; in this case, our derivations would only require a uniform bound on ‖g(x∗, s)‖.”
SGD: General Analysis and Improved Rates (2019, methodology): “This sampling is the same as the partially biased sampling in (Needell et al., 2016).”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “ng the ﬁrst algorithms developed for solving stochastic optimization problems [6]. Recently, these methods have received signiﬁcant attention due to their simplicity and effectiveness (see, e.g., [7]–[13]). In particular, Nemirovski et. al. [7] demonstrated that for nonsmooth stochastic convex optim”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “We consider the following generic optimization problem associated with regularized loss minimization of linear predictors.”
Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields (2015, methodology): “Our experiments show this method already improves on state of the art methods for training CRFs by a substantial margin, but we found we could obtain improved performance for training CRFs using the following simple NUS scheme for SAG: as in Needell et al. [2014], with probability 0.”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “The randomized Kaczmarz method is equivalent to SGD with a specific stepsize choice [30], [31].”
Coupling Adaptive Batch Sizes with Learning Rates (2016, background): “We note that another recent line of work on non-uniform sampling of training samples with the goal of variance reduction (including, but not limited to, [18, 27, 24, 4]) is orthogonal to our work, since it is concerned with the composition of batches rather than their size.”