Title: Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory,
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.