|
|
Problems in Stochastic Analysis
December 1, 2016 16:00–18:00, Moscow, Skolkovo Innovation Center, Technopark, Building 3, 148
|
|
|
|
|
|
Stochastic reformulations of linear systems and efficient randomized algorithms
P. Richtarik University of Edinburgh
|
Number of views: |
This page: | 225 | Materials: | 113 |
|
Abstract:
We propose a new paradigm for solving linear systems with a very large number of equations. In our
paradigm, the system is first reformulated into a stochastic problem, and then solved with a suitable
(typically randomized) algorithm. Our stochastic reformulation is flexible as it depends on a userdefined
parameter in the form of a distribution defining an ensemble of random matrices. The
choice of the distribution directly influences the “condition number” of the reformulation, which
leads to the novel concept of “randomized preconditioning”. We give necessary and sufficient
conditions for the reformulation to be exact, i.e., for the solution set of the stochastic problem to be
identical to the solution set of the linear system. We also show that the reformulation can be
equivalently seen as a stochastic optimization problem, stochastically preconditioned linear system,
stochastic fixed-point problem and as a probabilistic intersection problem. For instance, the
condition number of the reformulation is equal to the condition number of the stochastically
preconditioned linear system, and to the condition number of associated with the Hessian of the
objective function appearing the stochastic optimization reformulation.
Supplementary materials:
stochastic_reformulations.pdf (491.4 Kb)
,
peter_richtarik_.pdf (708.5 Kb)
|
|