Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
From MaRDI portal
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 (where is a bound on the smoothness and on the strong convexity) to a linear dependence on . 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.
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 _1 regression
- The approximation of generalized stochastic gradients of random regular functions
Cites work
- A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
- A Kaczmarz-Kovarik algorithm for symmetric ill-conditioned matrices
- A randomized Kaczmarz algorithm with exponential convergence
- A statistical perspective on algorithmic leveraging
- A Stochastic Approximation Method
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- An improved approximation algorithm for the column subset selection problem
- Augmented _1 and nuclear-norm models with a globally linearly convergent algorithm
- Block-iterative methods for consistent and inconsistent linear equations
- Block-projections algorithms with blocks containing mutually orthogonal rows and columns
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
- Fundamentals of Computerized Tomography
- Graph sparsification by effective resistances
- scientific article; zbMATH DE number 4001918 (Why is no real title available?)
- scientific article; zbMATH DE number 1569104 (Why is no real title available?)
- Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
- Large-scale machine learning with stochastic gradient descent
- On Kaczmarz's projection iteration as a direct solver for linear least squares problems
- On the acceleration of Kaczmarz's method for inconsistent linear systems
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Projection method for solving a singular system of linear equations and its applications
- Randomized Algorithms for Matrices and Data
- Randomized extended Kaczmarz for solving least squares
- Randomized Kaczmarz solver for noisy linear systems
- Revisiting the Nyström method for improved large-scale machine learning
- Robust Stochastic Approximation Approach to Stochastic Programming
- Sparse Legendre expansions via _1-minimization
- Stable and Robust Sampling Strategies for Compressive Imaging
- Strong underrelaxation in Kaczmarz's method for inconsistent systems
- Two Algorithms Related to the Method of Steepest Descent
- Two-subspace projection method for coherent overdetermined systems
Cited in
(only showing first 100 items - show all)- Stochastic gradient algorithm with random truncations
- Stochastic accelerated alternating direction method of multipliers with importance sampling
- Linear convergence of the randomized sparse Kaczmarz method
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- Stability of the Kaczmarz reconstruction for stationary sequences
- Analysis of biased stochastic gradient descent using sequential semidefinite programs
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Data-driven algorithm selection and tuning in optimization and signal processing
- Nonlinear Kaczmarz algorithms and their convergence
- Stochastic Markov gradient descent and training low-bit neural networks
- Randomized Kaczmarz for tensor linear systems
- Accelerating mini-batch SARAH by step size rules
- 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
- A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval
- Bridging the gap between constant step size stochastic gradient descent and Markov chains
- Enhancement of the Kaczmarz algorithm with projection adjustment
- On block Gaussian sketching for the Kaczmarz method
- Accelerating the distributed Kaczmarz algorithm by strong over-relaxation
- Worst-case recovery guarantees for least squares approximation using random samples
- Non-asymptotic guarantees for sampling by stochastic gradient descent
- The dual Kaczmarz algorithm
- On the linear convergence of the stochastic gradient method with constant step-size
- Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization
- An accelerated variance reducing stochastic method with Douglas-Rachford splitting
- Randomized Kaczmarz with averaging
- On fast greedy block Kaczmarz methods for solving large consistent linear systems
- Adaptive sampling for incremental optimization using stochastic gradient descent
- On data preconditioning for regularized loss minimization
- Sampling Gaussian distributions in Krylov spaces with conjugate gradients
- Subgradient and sampling algorithms for _1 regression
- Iterative Methods for Solving Factorized Linear Systems
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Experience selection in deep reinforcement learning for control
- scientific article; zbMATH DE number 6982318 (Why is no real title available?)
- Weighted SGD for _p regression with randomized preconditioning
- Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification
- Weighted SGD for \(\ell_p\) regression with randomized preconditioning
- Batched Stochastic Gradient Descent with Weighted Sampling
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- Multilevel stochastic gradient methods for nested composition optimization
- Stochastic modified equations and dynamics of stochastic gradient algorithms. I: Mathematical foundations
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
- On the regularizing property of stochastic gradient descent
- The Kaczmarz algorithm, row action methods, and statistical learning algorithms
- A weighted randomized Kaczmarz method for solving linear systems
- Auxiliary Gradient-Based Sampling Algorithms
- Randomized Kaczmarz Converges Along Small Singular Vectors
- Surrounding the solution of a linear system of equations from all sides
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Sampled limited memory methods for massive linear inverse problems
- On stochastic Kaczmarz type methods for solving large scale systems of ill-posed equations
- A Kaczmarz Algorithm for Solving Tree Based Distributed Systems of Equations
- Reconstructing the thermal phonon transmission coefficient at solid interfaces in the phonon transport equation
- Stochastic gradients for large-scale tensor decomposition
- Quasi-Newton methods for machine learning: forget the past, just sample
- Quantile-based iterative methods for corrupted systems of linear equations
- Randomized extended average block Kaczmarz for solving least squares
- The error-feedback framework: SGD with delayed gradients
- Minimizing finite sums with the stochastic average gradient
- A randomized algorithm for multivariate function approximation
- Importance sampling in signal processing applications
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
- Two stochastic optimization algorithms for convex optimization with fixed point constraints
- Kalman-based stochastic gradient method with stop condition and insensitivity to conditioning
- Regularized Kaczmarz Algorithms for Tensor Recovery
- An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm
- Randomized numerical linear algebra: Foundations and algorithms
- Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation
- A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems
- Fractional-based stochastic gradient algorithms for time-delayed ARX models
- Approximate Solutions of Linear Systems at a Universal Rate
- Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
- Unified analysis of stochastic gradient methods for composite convex and smooth optimization
- A block-randomized stochastic method with importance sampling for CP tensor decomposition
- Improving sampling accuracy of stochastic gradient MCMC methods via non-uniform subsampling of gradients
- Randomized Kaczmarz algorithm with averaging and block projection
- A multivariate adaptive gradient algorithm with reduced tuning efforts
- Targeted deep learning: framework, methods, and applications
- A stochastic variance reduced gradient method with adaptive step for stochastic optimization
- A fast non-monotone line search for stochastic gradient descent
- On adaptive stochastic heavy ball momentum for solving linear systems
- The accelerated tensor Kaczmarz algorithm with adaptive parameters for solving tensor systems
- Max-affine regression via first-order methods
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Stochastic Steffensen method
- The greedy randomized extended Kaczmarz algorithm for noisy linear systems
- Randomized Kaczmarz with geometrically smoothed momentum
- Quantile-RK and double quantile-RK error horizon analysis
- The quaternion relaxed greedy randomized Kaczmarz method with adaptive parameters for solving quaternion matrix equation
- Kernel-algorithms in frame-approximations
- Deterministic and randomized Kaczmarz methods for AXB=C with applications to color image restoration
- On stochastic block methods for solving nonlinear equations
- Homogenization of SGD in high-dimensions: exact dynamics and generalization properties
- Randomly sparsified Richardson iteration: a dimension-independent sparse linear solver
- Randomized Kaczmarz methods for t-product tensor linear systems with factorized operators
- Randomized iterative methods for generalized absolute value equations: solvability and error bounds
- On a nonlinear fast deterministic block Kaczmarz method for solving nonlinear equations
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)
