Randomized Methods for Linear Constraints: Convergence Rates and Conditioning

By D. Leventhal, A. S. Lewis. Mathematics of Operations Research, 2008

381 citations recorded by the source corpus.

We study randomized variants of two classical algorithms: coordinate descent for systems of linear equations and iterated projections for systems of linear inequalities. Expanding on a recent randomized iterated projection algorithm of Strohmer and Vershynin (Strohmer, T., R. Vershynin. 2009. A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15 262–278) for systems of linear equations, we show that, under appropriate probability distributions, the linear rates of convergence (in expectation) can be bounded in terms of natural linear-algebraic condition numbers for the problems. We relate these condition measures to distances to ill-posedness and discuss generalizations to convex systems under metric regularity assumptions.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/0a043a5f666b4785245bf8f79f96b3543cbdedc6

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 Numerical Analysis

Citations in the corpus

Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds (2016, background): “Our results can be viewed as a generalization of the results from [6] to more general optimization problems (2.”
A new perspective on randomized gossip algorithms (2016, methodology): “If Sk is chosen randomly from the set of unit coordinate/basis vectors inRm, then the dual method (3) is randomized coordinate descent [19, 20], and the corresponding primal method (5) is RK.”
Randomized Extended Kaczmarz for Solving Least Squares (2012, background): “Towards explaining such an empirical evidence, Strohmer and Vershynin proposed a simple randomized variant of the Kaczmarz method that has exponential convergence in expectation [SV09] assuming that the linear system is solvable; see also [LL10] for extensions to linear constraints.”
Stabilization of Stochastic Iterative Methods for Singular and Nearly Singular Linear Systems (2014, background): “[14], and Leventhal and Lewis [35] on randomized versions of coordinate descent and iterated projection methods for overdetermined least squares problems and the series of papers by Drineas et al.”
Inexact Coordinate Descent: Complexity and Preconditioning (2013, methodology): “For instance, a randomized variant of the Kaczmarz method for solving linear systems has recently been studied, equipped with iteration complexity bounds [21, 22, 16, 37], and found to be surprisingly efficient.”
Revisiting Asynchronous Linear Solvers: Provable Convergence Rate through Randomization (2013, methodology): “Consider the following more general Randomized Gauss-Seidel iteration (also due to Leventhal and Lewis [11]): γ̃j = (y?”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “(2.21) For β = 0 and ω = 1 the method is equivalent with randomized coordinate descent of Leventhal and Lewis [104], which was shown to converge with iteration complexity Previous best result: O ( Trace(A) λmin(A) log(1/ ) ) .”
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection (2015, methodology): “…[Fercoq and Richt´arik, 2013], for primal-dual rates of dual coordinate ascent [Shalev-Shwartz and Zhang, 2013], for successive projection methods [Leventhal and Lewis, 2010], for boosting algorithms [R¨atsch et al., 2001], and for scenarios without strong-convexity under general error bounds…”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “The first randomized coordinate descent method, for linear systems, was analyzed by Lewis and Leventhal [97], and subsequently generalized in various ways by numerous authors (we refer the reader to [140] and the references therein).”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, methodology): “Kaczmarz algorithms [55, 35, 41, 40] for overdetermined linear systems, as in Example 4, are effective, solving feasible systems Ax = b (where A ∈ Rm×n,m ≥ n) using careful stochastic gradient steps on the objective ‖Ax− b‖22 to achieve fast convergence.”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, background): “a Gauss-Seidel for linear systems) and its block variant, Randomized Block Coordinate Descent we suggest [25, 36, 44, 45, 40, 41, 43, 7, 24, 14, 1, 54].”
Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method (2012, methodology): “ when the linear system is inconsistent [Nee10]. Zouzias and Freris [ZF12] exhibit a randomized procedure, based on ideas from [Pop98], that can reduce the size of the residual e. Leventhal and Lewis [LL10] provide an analysis of a randomized iteration for solving least-squares problems with polyhed”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “It can be shown,[26, 48], that if Sk is chosen randomly from the set of unit coordinate/basis vectors in Rm, then the dual method (50) is randomized coordinate descent [38, 72], and the corresponding primal method is RK (5).”
Randomized First-Order Methods for Saddle Point Optimization (2014, neutral): “This paper is also motivated by the currently active research on block coordinate descent methods (see, e.g., [17, 11, 18, 20, 1, 13, 3]) for solving problems with a separable feasible set.”
Parallel coordinate descent methods for big data optimization (2012, methodology): “Stochastic/randomized CDMs, that is, methods where the coordinate to be updated is chosen randomly, were rst analyzed for quadratic objectives [17, 2], later independently generalized to L1-regularized problems [16] and smooth block-structured problems [7], and nally uni ed and re ned in [12, 13].”
On the complexity analysis of randomized block-coordinate descent methods (2013, background): “Nesterov [11] analyzed some RBCD methods for minimizing a smooth convex function over a closed block-separable convex set and established its iteration complexity, which in effect extends and improves upon some of the results in [2,5,18] in several aspects.”