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

DOI10.1007/s10107-015-0864-7zbMath1333.65070arXiv1310.5715OpenAlexW2162287622WikidataQ29027877 ScholiaQ29027877MaRDI QIDQ5962728

Deanna Needell, Nathan Srebro, Rachel Ward

Publication date: 23 February 2016

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

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

zbMATH Keywords

importance samplingnumerical exampleslinear convergenceexponential convergencedistribution reweightingKaczmarz methodstochastic gradient descentweighted least squares problem

Mathematics Subject Classification ID

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

Related Items (74)

Stochastic Gradients for Large-Scale Tensor Decomposition ⋮ An Optimal Scheduled Learning Rate for a Randomized Kaczmarz Algorithm ⋮ An attention algorithm for solving large scale structured \(l_0\)-norm penalty estimation problems ⋮ Accelerating mini-batch SARAH by step size rules ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation ⋮ On data preconditioning for regularized loss minimization ⋮ Stochastic accelerated alternating direction method of multipliers with importance sampling ⋮ Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods ⋮ 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 ⋮ Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations ⋮ Randomized Kaczmarz with averaging ⋮ A new randomized Kaczmarz based kernel canonical correlation analysis algorithm with applications to information retrieval ⋮ Block Kaczmarz method with inequalities ⋮ 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 ⋮ An accelerated variance reducing stochastic method with Douglas-Rachford splitting ⋮ Bridging the gap between constant step size stochastic gradient descent and Markov chains ⋮ Importance sampling in signal processing applications ⋮ Improving sampling accuracy of stochastic gradient MCMC methods via non-uniform subsampling of gradients ⋮ Randomized Kaczmarz algorithm with averaging and block projection ⋮ Enhancement of the Kaczmarz algorithm with projection adjustment ⋮ On fast greedy block Kaczmarz methods for solving large consistent linear systems ⋮ Batched Stochastic Gradient Descent with Weighted Sampling ⋮ 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 ⋮ Linear convergence of the randomized sparse Kaczmarz method ⋮ On block Gaussian sketching for the Kaczmarz method ⋮ Multilevel Stochastic Gradient Methods for Nested Composition Optimization ⋮ Accelerating the distributed Kaczmarz algorithm by strong over-relaxation ⋮ Randomized Extended Average Block Kaczmarz for Solving Least Squares ⋮ On variance reduction for stochastic smooth convex optimization with multiplicative noise ⋮ On the regularizing property of stochastic gradient descent ⋮ Worst-case recovery guarantees for least squares approximation using random samples ⋮ Minimizing finite sums with the stochastic average gradient ⋮ Stability of the Kaczmarz reconstruction for stationary sequences ⋮ Analysis of biased stochastic gradient descent using sequential semidefinite programs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods ⋮ The Kaczmarz algorithm, row action methods, and statistical learning algorithms ⋮ A weighted randomized Kaczmarz method for solving linear systems ⋮ Data-driven algorithm selection and tuning in optimization and signal processing ⋮ Improved asynchronous parallel optimization analysis for stochastic incremental methods ⋮ Nonlinear Kaczmarz algorithms and their convergence ⋮ The dual Kaczmarz algorithm ⋮ On the linear convergence of the stochastic gradient method with constant step-size ⋮ Randomized Kaczmarz Converges Along Small Singular Vectors ⋮ Adaptive Sampling for Incremental Optimization Using Stochastic Gradient Descent ⋮ Stochastic Markov gradient descent and training low-bit neural networks ⋮ Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization ⋮ Surrounding the solution of a linear system of equations from all sides ⋮ On Adaptive Sketch-and-Project for Solving Linear Systems ⋮ A Kaczmarz algorithm for sequences of projections, infinite products, and applications to frames in IFS \(L^2\) spaces ⋮ Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin ⋮ Unnamed Item ⋮ Sampled limited memory methods for massive linear inverse problems ⋮ Unnamed Item ⋮ Iterative Methods for Solving Factorized Linear Systems ⋮ Regularized Kaczmarz Algorithms for Tensor Recovery ⋮ 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 ⋮ A Randomized Algorithm for Multivariate Function Approximation ⋮ Randomized Kaczmarz for tensor linear systems ⋮ Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse Legendre expansions via \(\ell_1\)-minimization
• Two-subspace projection method for coherent overdetermined systems
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• On Kaczmarz's projection iteration as a direct solver for linear least squares problems
• Block-iterative methods for consistent and inconsistent linear equations
• On the acceleration of Kaczmarz's method for inconsistent linear systems
• Randomized Kaczmarz solver for noisy linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
• Strong underrelaxation in Kaczmarz's method for inconsistent systems
• Block-projections algorithms with blocks containing mutually orthogonal rows and columns
• Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
• Introductory lectures on convex optimization. A basic course.
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Projection method for solving a singular system of linear equations and its applications
• Fundamentals of Computerized Tomography
• Randomized Extended Kaczmarz for Solving Least Squares
• Augmented $\ell_1$ and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Randomized Algorithms for Matrices and Data
• Large-Scale Machine Learning with Stochastic Gradient Descent
• Robust Stochastic Approximation Approach to Stochastic Programming
• Stable and Robust Sampling Strategies for Compressive Imaging
• Two Algorithms Related to the Method of Steepest Descent
• A Stochastic Approximation Method
• Graph Sparsification by Effective Resistances

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