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

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

Authors: 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?)
• A statistical perspective on algorithmic leveraging
• 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
• Revisiting the Nyström method for improved large-scale machine learning
• 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
• A Kaczmarz-Kovarik algorithm for symmetric ill-conditioned matrices
• 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
• An improved approximation algorithm for the column subset selection problem
• Augmented \(\ell_1\) and nuclear-norm models with a globally linearly convergent algorithm
• Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling

Cited In (93)

• 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?)
• Randomized extended average block Kaczmarz for solving least squares
• 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
• Stochastic gradients for large-scale tensor decomposition
• Surrounding the solution of a linear system of equations from all sides
• A sampling Kaczmarz-Motzkin algorithm for linear feasibility
• 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
• On data preconditioning for regularized loss minimization
• Stability of the Kaczmarz reconstruction for stationary sequences
• 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
• 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
• 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
• Multilevel stochastic gradient methods for nested composition optimization
• Data-driven algorithm selection and tuning in optimization and signal processing
• A randomized algorithm for multivariate function approximation
• 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
• Weighted SGD for \(\ell_p\) regression with randomized preconditioning
• On block Gaussian sketching for the Kaczmarz method
• Experience selection in deep reinforcement learning for control
• Kalman-based stochastic gradient method with stop condition and insensitivity to conditioning
• Nonlinear Kaczmarz algorithms and their convergence
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Stochastic modified equations and dynamics of stochastic gradient algorithms. I: Mathematical foundations
• 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
• Auxiliary Gradient-Based Sampling Algorithms
• Stochastic primal-dual coordinate method for regularized empirical risk minimization
• 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
• Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification
• 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
• Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
• 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
• Adaptive sampling for incremental optimization using stochastic gradient descent
• 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
• Quantile-based iterative methods for corrupted systems of linear equations
• Improving sampling accuracy of stochastic gradient MCMC methods via non-uniform subsampling of gradients
• Weighted SGD for \(\ell_p\) regression with randomized preconditioning
• On stochastic Kaczmarz type methods for solving large scale systems of ill-posed equations
• 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
• A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
• 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
• A multivariate adaptive gradient algorithm with reduced tuning efforts
• Randomized Kaczmarz with geometrically smoothed momentum
• Targeted deep learning: framework, methods, and applications
• Reconstructing the thermal phonon transmission coefficient at solid interfaces in the phonon transport equation
• 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)