Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory

By Peter Richtárik, Martin Takác. 2017

106 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, methodology): “Our approach is inspired by recently proposed stochastic reformulations of standard optimization problems, like the empirical risk minimization in Gower et al. [2019] and linear systems in Richtárik and Takác [2020], Loizou and Richtárik [2020a,b].”
SGD: General Analysis and Improved Rates (2019, background): “(5) Similar but different stochastic reformulations were recently proposed by Richt´arik & Tak´aˇc (2017) and further used in (Loizou & Richt ´ arik, 2017) for the more special problem of solving linear systems, and by Gower et al. (2018) in the context of variance-reduced methods.”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “onding to a discrete distribution over unit coordinate vectors in Rm. However, the exibility of being able to choose Darbitrarily allows for numerous generalizations of the randomized Kaczmarz method [64]. Likewise, provably faster variants of the randomized Kaczmarz method (for instance, by utilizi”
Better Theory for SGD in the Nonconvex World (2020, methodology): “In order to develop a general theory of SGD for a wide array of subsampling strategies, we follow the stochastic reformulation formalism pioneered by Richt´arik & Tak´aˇc (2017); Gower et al. (2018) in the form proposed in (Gower et al., 2019).”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “Later, Richtárik and Takáč (2017) showed that this procedure can be accelerated to achieve rates that depend on the square root of an appropriate condition number; see also Gower, Hanzely, Richtarik and Stich (2018).”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, methodology): “It was developed using the stochastic reformulation approach (whence the “SR”) pioneered in (Richtárik and Takáč, 2017) in a numerical linear algebra setting, and later extended to develop the JacSketch variance-reduction technique for finite-sum optimization (Gower et al.”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “The sketch-and-project algorithm [25, 73] for solving a consistent linear system Ax = b has the form”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, background): “, 2020), consistent linear systems (Gower and Richtárik, 2015; Richtárik and Takác, 2020; Loizou and Richtárik, 2017, 2019) and multi-class classification using deep networks (Vaswani et al.”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “nd other equivalent reformulations (e.g., stochastic xed point problem, probabilistic intersection problem, and stochastic linear system). Best Approximation Problem and Sketch and Project Method: In [46,29], it has been shown that for the case of consistent linear systems with multiple solutions, S”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In this thesis we design and analyze randomized iterative methods (stochastic optimization algorithms) for solving the stochastic convex quadratic minimization reformulation proposed in [168].”
One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods (2019, background): “This process can be seen as SGD applied to a certain quadratic stochastic optimization problem [33, 8].”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, background): “(43) It is easy to see from (23) and (32) that 10 A similar relation to (43) holds for the stochastic optimization reformulation of linear systems studied by Richtárik and Takáč [26].”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, methodology): “Richtárik and Takáč [25] adopt a new point of view through a theory of stochastic 59 reformulations of linear systems.”