Source-linked AI summary
Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
D. Leventhal, A. S. Lewis
TL;DR
The paper studies how randomized versions of coordinate descent and iterated projections can be analyzed through conditioning measures and error bounds. It develops appropriate randomization schemes for linear equations and inequalities and relates their expected linear convergence rates to these quantities. The analysis also connects conditioning to ill-posedness and extends to convex systems under metric regularity assumptions.
Problem
Classical algorithms have known linear convergence, but the paper investigates how randomized versions can obtain rates directly in natural condition measures for linear equations and inequalities.
Method
The paper analyzes probability-weighted coordinate descent and randomized iterated projections, using residual-based error bounds and metric regularity to establish convergence.
Results
The paper shows that appropriate randomization yields expected linear convergence rates expressible through traditional conditioning measures, including relative condition numbers and Hoffman constants.
Takeaways & Limitations
Randomization provides a framework for simplifying convergence analysis in terms of natural linear-algebraic condition measures and links those measures to distances to ill-posedness.
Takeaways & Limitations
The convex-system extension uses metric regularity assumptions, while the coordinate-descent discussion includes positive-semidefinite cases where consistency is equivalent to the objective being bounded below.
Abstract
from arXiv · showhide
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 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.
1 Introduction
The paper connects condition measures and error bounds to algorithmic convergence, developing randomized coordinate descent and iterated projection analyses with rates expressed through natural conditioning quantities.
- Condition numbers measure solution sensitivity to small perturbations in input data.
- Eckart-Young relates the distance to singular matrices to the inverse-norm condition measure, with E {∥E∥: A + E is singular} = 1 ∥A−1∥.
- Error bounds relate distance to a specified set to a computable residual, supporting stopping rules and convergence proofs.
- For nonsingular Ax = b, the solution distance is bounded by the residual ∥Ax −b∥ using the same constant linked to conditioning and distance to infeasibility.
- The paper shows appropriately randomized coordinate descent and iterated projections have expected linear convergence rates expressed through conditioning measures and Hoffman error bounds.
- Randomization is used theoretically to simplify convergence analysis through relative condition numbers, Hoffman constants, and metric regularity moduli.
2 Notation
This section establishes notation for Euclidean geometry, projections, matrix norms, inverse-related quantities, condition numbers, and positive-definite or semidefinite matrices.
- The Euclidean norm on Rn is denoted by ∥· ∥, and ei denotes the ith standard basis vector.
- For an m-by-n matrix, the spectral norm is ∥A∥2 := max∥x∥=1 ∥Ax∥ and the Frobenius norm is defined from the matrix entries.
- The inverse-related quantity ∥A−1∥2 is the reciprocal of the smallest singular value and equals the spectral norm of A−1 when A is invertible.
- The relative condition number is k(A) := ∥A∥2∥A−1∥2, while the scaled condition number is κ(A) := ∥A∥F∥A−1∥2.
- For a nonempty closed convex set S, PS(x) is the nearest-point projection of x onto S, while distance measures separation from S.
- The projection inequality ∥y −x∥2 −∥PS(y) −x∥2 ≥∥y −PS(y)∥2 holds for x ∈S and y ∈Rn.
3 Randomized Coordinate Descent
The paper randomizes coordinate descent for positive-semidefinite and general linear systems, obtaining expected linear convergence through residual-based error bounds. The method also extends to inconsistent systems, where it converges to a least-squares solution while retaining low per-iteration cost.
- For positive-definite systems, randomized coordinate search yields a convergence rate expressible in terms of the relative condition number, unlike successive cyclic coordinate updates.Each coordinate-direction search uses 2n + 2 arithmetic operations in the positive-definite setting.
- Algorithm 3.3 selects coordinate directions independently with probability proportional to the corresponding diagonal entry, P{i = k} = a_kk / tr A.The matrix may be singular, provided the selected coordinates have positive diagonal entries almost surely.
- The proof obtains expected linear convergence by making the expected distance decrease by a residual term and applying an error bound relating distance to residual.This proof strategy drives the remaining convergence results in the paper.
- The coordinate update minimizes the residual along the selected coordinate direction, with the step size computed from the current residual and column norm.The resulting iteration can be performed in O(n) time after the initial residual and column norms are computed.
- Algorithm 3.5 applies randomized coordinate descent directly to Ax = b and converges in expectation to a least-squares solution even when the system is inconsistent.It avoids explicitly forming the normal-equations matrix A^T A while producing the same iterates as Algorithm 3.3 on that system.
- In Gaussian computational examples with 500 × n matrices and n from 50 to 200, the theoretical bound predicts the algorithm’s observed behavior reasonably well.
4 Randomized Iterated Projections
The paper extends randomized iterated projections from linear equations to systems of linear inequalities. Using Hoffman error bounds and distance to infeasibility, it derives expected linear convergence rates tied to conditioning measures.
- The algorithm’s probability distribution is chosen to express convergence rates through linear-algebraic condition measures rather than only geometric properties of the projection hyperplanes.This extends the conditioning-based perspective introduced by the randomized method of Strohmer and Vershynin.
- Hoffman’s bound controls the distance to the feasible region by the a posteriori error, with the minimum valid constant called the Hoffman constant.For linear equations, this constant equals the reciprocal of the smallest nonzero singular value of A.
- Randomized iterated projections are generalized from linear equations to systems of linear inequalities by selecting constraints independently according to an appropriate probability distribution.The new algorithm projects the current iterate onto the selected constraint’s hyperplane or related feasible set.
- Algorithm 4.6 converges linearly in expectation whenever the inequality system has a nonempty feasible region.The convergence proof combines the randomized projection decrease with Hoffman’s bound.
- Computational examples use 500 × n Gaussian inequality systems with nonempty interiors for n = 50, 100, 150, and 200.
- The paper also derives a convergence bound in terms of Renegar’s distance to infeasibility, although it may be weaker than the Hoffman-based bound.The distance-to-infeasibility argument is presented for inequality systems initialized at x0 = 0.
5 Metric Regularity and Local Convergence
The paper extends randomized projection analysis to convex feasibility systems, expressing local convergence through metric regularity. It also shows that averaged projections inherit the randomized method’s expected linear rate under corresponding assumptions.
- Metric regularity: Metric regularity locally bounds distance to the solution set by a residual, generalizing prior error bounds while restricting guarantees to neighborhoods.For linear maps, its modulus corresponds to ||Φ^-1||; for smooth maps, it is the reciprocal of the Jacobian’s minimum singular value.
- Metric regularity: The mapping Φ(x)=(S1−x,…,Sm−x) converts feasibility in intersecting convex sets into the condition 0∈Φ(x).This set-valued formulation supports local convergence analysis for randomized projections.
- Randomized projections: Under metric regularity with modulus γ, uniformly randomized projections converge linearly in expectation from sufficiently near initial points.The theorem permits any γ̄>γ and requires the initial point to be sufficiently close to the reference solution.
- Randomized projections: The refined randomized algorithm selects each projection uniformly from sets other than the previously selected one and has a corresponding local expected linear-convergence result.The method prevents consecutive projections onto the same set by construction.
- Averaged projections: Averaged projections apply every set projection and average the results; under the theorem’s assumptions, they converge no more slowly than uniformly random projections.Their convergence rate is no larger than 1 − 1/(mγ̄^2).