TY - JOUR

T1 - Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory

AU - Richtarik, Peter

AU - Takãč, Martin

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2020/4/21

Y1 - 2020/4/21

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/626554

UR - http://arxiv.org/abs/1706.01108v2

UR - http://www.scopus.com/inward/record.url?scp=85084938172&partnerID=8YFLogxK

U2 - 10.1137/18M1179249

DO - 10.1137/18M1179249

M3 - Article

SN - 1095-7162

VL - 41

SP - 487

EP - 524

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 2

ER -