Stochastic reformulations of linear systems: algorithms and convergence theory
From MaRDI portal
(Redirected from Publication:5112239)
iterative methodslinear systemsrandom pursuitrandomized coordinate descentrandomized fixed pointrandomized Kaczmarzrandomized Newtonstochastic methods
Linear equations (linear algebraic aspects) (15A06) Random matrices (algebraic aspects) (15B52) Iterative numerical methods for linear systems (65F10) Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs (65N75) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Quadratic programming (90C20)
Abstract: We develop a family of reformulations of an arbitrary consistent linear system into a stochastic problem. The reformulations are governed by two user-defined parameters: a positive definite matrix defining a norm, and an arbitrary discrete or continuous distribution over random matrices. Our reformulation has several equivalent interpretations, allowing for researchers from various communities to leverage their domain specific insights. In particular, our reformulation can be equivalently seen as a stochastic optimization problem, stochastic linear system, stochastic fixed point problem and a probabilistic intersection problem. We prove sufficient, and necessary and sufficient conditions for the reformulation to be exact. Further, we propose and analyze three stochastic algorithms for solving the reformulated problem---basic, parallel and accelerated methods---with global linear convergence rates. The rates can be interpreted as condition numbers of a matrix which depends on the system matrix and on the reformulation parameters. This gives rise to a new phenomenon which we call stochastic preconditioning, and which refers to the problem of finding parameters (matrix and distribution) leading to a sufficiently small condition number. Our basic method can be equivalently interpreted as stochastic gradient descent, stochastic Newton method, stochastic proximal point method, stochastic fixed point method, and stochastic projection method, with fixed stepsize (relaxation parameter), applied to the reformulations.
Recommendations
- Randomized iterative methods for linear systems
- Randomized methods for linear constraints: convergence rates and conditioning
- Vector Monte Carlo stochastic matrix-based algorithms for large linear systems
- Stochastic Matrices and Lp Norms : New Algorithms for Solving Ill-conditioned Linear Systems of Equations
- Stochastic iterative projection methods for large linear systems
Cites work
- A fast randomized algorithm for overdetermined linear least-squares regression
- A randomized Kaczmarz algorithm with exponential convergence
- A Stochastic Approximation Method
- Accelerated, parallel, and proximal coordinate descent
- An accelerated randomized Kaczmarz algorithm
- An Algorithm for Restricted Least Squares Regression
- An improved data stream summary: the count-min sketch and its applications
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
- Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
- Distributed coordinate descent method for learning with big data
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- scientific article; zbMATH DE number 3973706 (Why is no real title available?)
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 2171469 (Why is no real title available?)
- scientific article; zbMATH DE number 2086663 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 6253925 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Linear Recursive Sequences
- LSRN: A parallel iterative solver for strongly over- or underdetermined systems
- Minimizing finite sums with the stochastic average gradient
- Monotone Operators and the Proximal Point Algorithm
- Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- On optimal probabilities in stochastic coordinate descent methods
- On Projection Algorithms for Solving Convex Feasibility Problems
- Optimization of convex functions with random pursuit
- Parallel coordinate descent methods for big data optimization
- Parallel stochastic Newton method
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Random algorithms for convex minimization problems
- Randomized algorithms for analysis and control of uncertain systems. With applications
- Randomized algorithms for probabilistic robustness with real and complex structured uncertainty.
- Randomized extended Kaczmarz for solving least squares
- Randomized iterative methods for linear systems
- Randomized Kaczmarz solver for noisy linear systems
- Randomized methods for linear constraints: convergence rates and conditioning
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Revisiting Asynchronous Linear Solvers
- Robust Stochastic Approximation Approach to Stochastic Programming
- Semi-stochastic coordinate descent
- Stochastic algorithms for exact and approximate feasibility of robust LMIs
- Stochastic dual coordinate ascent methods for regularized loss minimization
- Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Understanding machine learning. From theory to algorithms
Cited in
(48)- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- Randomized Kaczmarz for tensor linear systems
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Block sampling Kaczmarz-Motzkin methods for consistent linear systems
- A doubly stochastic block Gauss-Seidel algorithm for solving linear equations
- On stochastic linear systems with zonotopic support sets
- Randomized Kaczmarz with averaging
- On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- scientific article; zbMATH DE number 5606150 (Why is no real title available?)
- scientific article; zbMATH DE number 4140952 (Why is no real title available?)
- An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
- On Adaptive Sketch-and-Project for Solving Linear Systems
- Adaptively sketched Bregman projection methods for linear systems
- Sketched Newton-Raphson
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Randomized extended average block Kaczmarz for solving least squares
- Faster randomized block Kaczmarz algorithms
- scientific article; zbMATH DE number 5230276 (Why is no real title available?)
- Convergence analysis of inexact randomized iterative methods
- Convergence and semi-convergence of a class of constrained block iterative methods
- A Deterministic Kaczmarz Algorithm for Solving Linear Systems
- Randomized numerical linear algebra: Foundations and algorithms
- PLSS: A Projected Linear Systems Solver
- Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification
- Randomized Block Adaptive Linear System Solvers
- Faster randomized block sparse Kaczmarz by averaging
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems
- The method of randomized Bregman projections for stochastic feasibility problems
- Randomized Kaczmarz algorithm with averaging and block projection
- Solving, tracking and stopping streaming linear inverse problems
- On adaptive stochastic heavy ball momentum for solving linear systems
- A stochastic iteratively regularized Gauss-Newton method
- Efficient randomized block Kaczmarz method for linear feasibility
- Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
- On pseudoinverse-free randomized methods for linear systems: unified framework and acceleration
- Fine-grained analysis and faster algorithms for iteratively solving linear systems
- A fast Bregman projection method for linearly constrained optimization problems
- Mismatched adjoint random Kaczmarz with averaging
- Convergence analysis of two-level methods with general coarse solvers
- The equivalence of the randomized extended Gauss-Seidel and randomized extended Kaczmarz methods
- A novel stochastic conjugate gradient algorithm based on a stochastic differential equation perspective
- Theoretical Analysis of Thermodynamic Matrix Inversion: First-order Equivalence to Preconditioned Gradient Descent and Implications for Analog Computing
- Subspace-constrained randomized coordinate descent for linear systems with good low-rank matrix approximations
- Convergence analysis of a frozen stochastic iteratively regularized Gauss-Newton method
This page was built for publication: Stochastic reformulations of linear systems: algorithms and convergence theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5112239)
