Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm

Abstract

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/\mu {)}^2$ (where $L$ is a bound on the smoothness and $\mu$ on the strong convexity) to a linear dependence on $L/\mu$. 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.

22 pages, 6 figures

References in corpus (9)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
• Randomized algorithms for matrices and data
• Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
• A Statistical Perspective on Algorithmic Leveraging
• Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
• Gradient methods for convex minimization: better rates under weaker conditions
• Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
• An Asynchronous Parallel Randomized Kaczmarz Algorithm

Cited by in corpus (10)

• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Online Censoring for Large-Scale Regressions with Application to Streaming Big Data
• Stochastic Optimization with Importance Sampling
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Learning a Metric Embedding for Face Recognition using the Multibatch Method
• Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
• Rows vs Columns for Linear Systems of Equations - Randomized Kaczmarz or Coordinate Descent?
• An arithmetic-geometric mean inequality for products of three matrices
• Targeted Deep Learning: Framework, Methods, and Applications