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

DOI10.1007/S10107-015-0864-7zbMATH Open1333.65070DBLPjournals/mp/NeedellSW16arXiv1310.5715OpenAlexW2162287622WikidataQ29027877 ScholiaQ29027877MaRDI QIDQ5962728FDOQ5962728

D. Needell, Nathan Srebro, Rachel Ward

Publication date: 23 February 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1310.5715

Recommendations

• Batched Stochastic Gradient Descent with Weighted Sampling
• Non-asymptotic guarantees for sampling by stochastic gradient descent
• Stochastic semidefinite optimization using sampling methods
• Adaptive sampling for incremental optimization using stochastic gradient descent
• Sampling Gaussian distributions in Krylov spaces with conjugate gradients
• A stochastic multiple gradient descent algorithm
• Boosted sampling
• Subgradient and sampling algorithms for \(\ell_1\) regression
• The approximation of generalized stochastic gradients of random regular functions

zbMATH Keywords

Kaczmarz methodimportance samplingnumerical examplesexponential convergencelinear convergencestochastic gradient descentweighted least squares problemdistribution reweighting

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Existence theories for optimal control problems involving partial differential equations (49J20) Existence of optimal solutions to problems involving randomness (49J55) Random operators and equations (aspects of stochastic analysis) (60H25)

Cites Work

• A randomized Kaczmarz algorithm with exponential convergence
• Fundamentals of Computerized Tomography
• Title not available (Why is that?)
• Introductory lectures on convex optimization. A basic course.
• A Stochastic Approximation Method
• Robust Stochastic Approximation Approach to Stochastic Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Randomized Algorithms for Matrices and Data
• Sparse Legendre expansions via \(\ell_1\)-minimization
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Graph Sparsification by Effective Resistances
• Stable and Robust Sampling Strategies for Compressive Imaging
• Title not available (Why is that?)
• Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Strong underrelaxation in Kaczmarz's method for inconsistent systems
• Projection method for solving a singular system of linear equations and its applications
• Randomized extended Kaczmarz for solving least squares
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• Randomized Kaczmarz solver for noisy linear systems
• Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
• Large-Scale Machine Learning with Stochastic Gradient Descent
• Title not available (Why is that?)
• Block-iterative methods for consistent and inconsistent linear equations
• Two-subspace projection method for coherent overdetermined systems
• On the acceleration of Kaczmarz's method for inconsistent linear systems
• Block-projections algorithms with blocks containing mutually orthogonal rows and columns
• A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
• Two Algorithms Related to the Method of Steepest Descent
• On Kaczmarz's projection iteration as a direct solver for linear least squares problems
• Title not available (Why is that?)
• Augmented \(\ell_1\) and nuclear-norm models with a globally linearly convergent algorithm
• Title not available (Why is that?)

Cited In (91)

• Multilevel Stochastic Gradient Methods for Nested Composition Optimization
• An attention algorithm for solving large scale structured \(l_0\)-norm penalty estimation problems
• Sampling Gaussian distributions in Krylov spaces with conjugate gradients
• Non-asymptotic guarantees for sampling by stochastic gradient descent
• Randomized Kaczmarz with averaging
• Title not available (Why is that?)
• A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval
• An accelerated variance reducing stochastic method with Douglas-Rachford splitting
• Surrounding the solution of a linear system of equations from all sides
• On the regularizing property of stochastic gradient descent
• Enhancement of the Kaczmarz algorithm with projection adjustment
• On variance reduction for stochastic smooth convex optimization with multiplicative noise
• Unified analysis of stochastic gradient methods for composite convex and smooth optimization
• A weighted randomized Kaczmarz method for solving linear systems
• Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
• Randomized Kaczmarz Converges Along Small Singular Vectors
• On Adaptive Sketch-and-Project for Solving Linear Systems
• Randomized numerical linear algebra: Foundations and algorithms
• A Randomized Algorithm for Multivariate Function Approximation
• On data preconditioning for regularized loss minimization
• Title not available (Why is that?)
• Stability of the Kaczmarz reconstruction for stationary sequences
• On stochastic Kaczmarz type methods for solving large scale systems of ill-posed equations
• Adaptive Sampling for Incremental Optimization Using Stochastic Gradient Descent
• Stochastic gradient algorithm with random truncations
• Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation
• Stochastic accelerated alternating direction method of multipliers with importance sampling
• Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
• Accelerating mini-batch SARAH by step size rules
• The dual Kaczmarz algorithm
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• Title not available (Why is that?)
• Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
• Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization
• A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
• Subgradient and sampling algorithms for \(\ell_1\) regression
• Regularized Kaczmarz Algorithms for Tensor Recovery
• On the Kaczmarz methods based on relaxed greedy selection for solving matrix equation \(A X B = C\)
• Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
• Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
• Title not available (Why is that?)
• Data-driven algorithm selection and tuning in optimization and signal processing
• The Kaczmarz algorithm, row action methods, and statistical learning algorithms
• On the linear convergence of the stochastic gradient method with constant step-size
• Approximate Solutions of Linear Systems at a Universal Rate
• On block Gaussian sketching for the Kaczmarz method
• Nonlinear Kaczmarz algorithms and their convergence
• Stochastic Gradients for Large-Scale Tensor Decomposition
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Randomized Extended Average Block Kaczmarz for Solving Least Squares
• Bridging the gap between constant step size stochastic gradient descent and Markov chains
• Worst-case recovery guarantees for least squares approximation using random samples
• A Kaczmarz algorithm for sequences of projections, infinite products, and applications to frames in IFS \(L^2\) spaces
• Iterative Methods for Solving Factorized Linear Systems
• A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
• Auxiliary Gradient-Based Sampling Algorithms
• A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
• Stochastic Markov gradient descent and training low-bit neural networks
• Block Kaczmarz method with inequalities
• On fast greedy block Kaczmarz methods for solving large consistent linear systems
• Batched Stochastic Gradient Descent with Weighted Sampling
• Minimizing finite sums with the stochastic average gradient
• Analysis of biased stochastic gradient descent using sequential semidefinite programs
• Randomized Kaczmarz for tensor linear systems
• Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
• Linear convergence of the randomized sparse Kaczmarz method
• Fractional-based stochastic gradient algorithms for time-delayed ARX models
• A stochastic variance reduced gradient method with adaptive step for stochastic optimization
• Title not available (Why is that?)
• On adaptive stochastic heavy ball momentum for solving linear systems
• A fast non-monotone line search for stochastic gradient descent
• The accelerated tensor Kaczmarz algorithm with adaptive parameters for solving tensor systems
• Sampled limited memory methods for massive linear inverse problems
• Max-affine regression via first-order methods
• Quasi-Newton methods for machine learning: forget the past, just sample
• Improving sampling accuracy of stochastic gradient MCMC methods via non-uniform subsampling of gradients
• A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
• Stochastic Steffensen method
• An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
• The greedy randomized extended Kaczmarz algorithm for noisy linear systems
• Randomized Kaczmarz algorithm with averaging and block projection
• Two stochastic optimization algorithms for convex optimization with fixed point constraints
• Importance sampling in signal processing applications
• Reconstructing the Thermal Phonon Transmission Coefficient at Solid Interfaces in the Phonon Transport Equation
• A multivariate adaptive gradient algorithm with reduced tuning efforts
• Randomized Kaczmarz with geometrically smoothed momentum
• Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations
• Title not available (Why is that?)
• Targeted deep learning: framework, methods, and applications
• A block-randomized stochastic method with importance sampling for CP tensor decomposition

This page was built for publication: Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962728)