PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems

Yin Tat Lee, Aaron Sidford

arXiv:1305.1922v1cs.DSmath.NA

TL;DR

The paper addresses how to accelerate randomized coordinate descent without increasing per-iteration asymptotic cost. It generalizes and efficiently implements Nesterov’s method, then applies it to obtain faster linear-system solvers, including an improved SDD runtime.

  • Problem

    The central problem is obtaining faster convergence from sublinear-time coordinate updates without sacrificing efficient implementation.

  • Method

    The paper generalizes Nesterov’s accelerated coordinate descent method and implements its iterations at the same asymptotic cost as coordinate descent.

  • Results

    The framework outperforms conjugate gradient for broad symmetric positive definite systems, improves randomized Kaczmarz guarantees, and accelerates SDD solvers.

  • Takeaways & Limitations

    The approach provides a framework that strengthens and unifies coordinate-descent results across multiple linear-system settings.

  • Takeaways & Limitations

    The conjugate-gradient comparison assumes somewhat uniform nonzero entries per row, and CG may be asymptotically faster when eigenvalues form clusters.

Abstract

from arXiv · show

In this paper we show how to accelerate randomized coordinate descent methods and achieve faster convergence rates without paying per-iteration costs in asymptotic running time. In particular, we show how to generalize and efficiently implement a method proposed by Nesterov, giving faster asymptotic running times for various algorithms that use standard coordinate descent as a black box. In addition to providing a proof of convergence for this new general method, we show that it is numerically stable, efficiently implementable, and in certain regimes, asymptotically optimal. To highlight the computational power of this algorithm, we show how it can used to create faster linear system solvers in several regimes: - We show how this method achieves a faster asymptotic runtime than conjugate gradient for solving a broad class of symmetric positive definite systems of equations. - We improve the best known asymptotic convergence guarantees for Kaczmarz methods, a popular technique for image reconstruction and solving overdetermined systems of equations, by accelerating a randomized algorithm of Strohmer and Vershynin. - We achieve the best known running time for solving Symmetric Diagonally Dominant (SDD) system of equations in the unit-cost RAM model, obtaining an O(m log^{3/2} n (log log n)^{1/2} log (log n / eps)) asymptotic running time by accelerating a recent solver by Kelner et al. Beyond the independent interest of these solvers, we believe they highlight the versatility of the approach of this paper and we hope that they will open the door for further algorithmic improvements in the future.

1 Introduction

The paper develops an efficient accelerated coordinate descent framework and applies it to obtain faster or improved linear-system algorithms across several settings.

  • Motivation: The approach targets iterative methods that use partial function or gradient information and support efficient asynchronous or parallel computation.The motivation is both practical, due to distributed data, and theoretical, due to sublinear-time update steps.
  • Contributions: The paper generalizes Nesterov’s ACDM and implements iterations with the same asymptotic runtime as non-accelerated coordinate updates.It also proves numerical stability, finite-precision implementability, and optimality under certain assumptions.
  • Contributions: ACDM improves convergence rates for coordinate-descent algorithms, including methods with skewed sampling probabilities.The generalization was essential for the paper’s later applications.
  • Linear-system solvers: ACDM can outperform conjugate gradient for a general class of symmetric positive definite systems under mild assumptions.The paper also claims asymptotic optimality for general systems in certain regimes.
  • Linear-system solvers: Accelerating randomized Kaczmarz yields improved asymptotic performance for overdetermined systems, with potential relevance to image reconstruction.The method recasts randomized Kaczmarz as coordinate descent before applying ACDM.
  • Linear-system solvers: Directly applying ACDM to a Kelner et al. solver produces a faster SDD solver with unit-cost RAM runtime ˜O(m log1.5 n log 1/ε).The paper presents this as approaching the fastest known runtime obtained in a less restrictive computational model.

2 Preliminaries

The preliminaries define the convex optimization setting, first-order convergence, smoothness parameters, and coordinate-wise quantities used to analyze coordinate descent and linear-system examples.

  • Optimization setting: The paper studies unconstrained minimization of a continuously differentiable convex function and defines f* and x* as its minimum value and an attaining point.Many results can be generalized to constrained, non-Euclidean, and block-coordinate settings, but the paper focuses on the Euclidean unconstrained case.
  • First-order methods: First-order methods generate iterates using only evaluations of f and ∇f, and convergence rate r means f(x_k) − f* ≤ O((1 − r)^k).The algorithms otherwise use only global function parameters defined in the section.
  • Function parameters: Convexity parameter σ and gradient Lipschitz constant L provide lower and upper bounds on f and characterize the information used by first-order methods.For twice differentiable functions, these parameters can be related to Hessian properties.
  • Coordinate parameters: Coordinate analysis introduces standard basis vectors, partial derivatives, and component-wise Lipschitz constants Li satisfying |fi(x + t·ei) − fi(x)| ≤ Li|t|.The aggregate quantity Sα plays a role for coordinate descent analogous to L for gradient descent.
  • Linear-system examples: For quadratic objectives from positive definite systems, σ and L are the smallest and largest eigenvalues of A, while S1 = tr(A).For least-squares objectives, σ and L correspond to the extreme eigenvalues of A^T A, and S1 equals the squared Frobenius norm of A.

3 Review of Previous Iterative Methods

This section reviews gradient, accelerated gradient, and coordinate descent methods for smooth convex minimization. It motivates estimate sequences and randomized single-coordinate updates as routes to faster convergence with limited information.

  • Gradient Descent: Gradient descent greedily minimizes a worst-case upper estimate built from the current function value and gradient.The method updates from the current point using a step size and gradient information.
  • Accelerated Gradient Descent: Accelerated gradient descent uses estimate sequences to build computable approximations rather than relying on the worst-case upper envelope at each step.An estimate sequence is an approximate lower bound that remains slightly above the optimum.
  • Accelerated Gradient Descent: Estimate sequences combine lower envelopes at evaluation points, with parameters tuned to obtain accelerated gradient descent.The method is optimal up to constants in the number of function and gradient queries among first-order methods.
  • Coordinate Descent: Coordinate descent updates one randomly selected coordinate using that coordinate’s gradient and a coordinate-wise Lipschitz constant.Its analysis uses a weighted norm, dual norm, inner product, and convexity parameter.
  • Coordinate Descent: The expected improvement from each coordinate update can be bounded, yielding a convergence guarantee for randomized coordinate descent.The guarantee relies on coordinate-wise Lipschitz constants.

4 General Accelerated Coordinate Descent

The paper develops a general accelerated coordinate descent method whose convergence improves on coordinate descent without increasing asymptotic iteration cost. It establishes convergence, numerical stability, efficient implementation, and optimality under stated assumptions.

  • General Method: ACDM improves the asymptotic convergence rate of coordinate-descent algorithms without paying an asymptotic cost for querying or updating coordinates.The framework generalizes Nesterov’s method and requires changes for the α = 1 case used in the applications.
  • Probabilistic Estimate Sequences: Probabilistic estimate sequences construct randomized minimization methods using partial derivatives instead of full gradient computations.This can reduce the information required for fast convergence in appropriate cases.
  • Algorithm: The method samples coordinates according to probabilities proportional to modified coordinate smoothness quantities and updates the iterates using coordinate gradients.The displayed algorithm defines y_k, x_{k+1}, v_{k+1}, and coefficient recurrences for each iteration.
  • Probabilistic Estimate Sequences: The convergence proof chooses x, y, and θ to satisfy the estimate-sequence condition and derives an iteration bound strictly better than coordinate descent.The paper states that the resulting rate is optimal up to constants for the considered algorithm class.
  • Algorithm: A sampling modification avoids small probabilities that would otherwise obstruct the optimal convergence rate, although an alternative distribution makes the algorithm more complicated and potentially more expensive.This is a stated implementation trade-off associated with the sampling choice.
  • Numerical Stability: Numerical stability results bound update and coefficient errors, showing that O(log n) bits of precision suffice under the theorem’s conditions.The stability theorem provides estimates for objective error and residual distance, with mild dependence on the initial objective error.
  • Efficient Implementation: Efficient ACDM iterations run in O(1) time plus one oracle call under assumptions on Sα and σ1−α, avoiding the naive O(n) vector-update cost.The oracle may evaluate a coordinate gradient at a linear combination of two vectors without explicitly forming the sum.

5 Faster Linear System Solvers

ACDM accelerates coordinate-descent formulations of linear-system solvers while preserving efficient iterations, yielding faster asymptotic runtimes for SPD, Kaczmarz, and SDD systems.

  • Overview: ACDM applies coordinate descent to linear systems and targets faster asymptotic runtimes than state-of-the-art methods in several settings.The section covers comparisons with conjugate gradient, accelerated randomized Kaczmarz, and an SDD solver.
  • Symmetric Positive Definite Systems: ACDM has a better asymptotic running time than conjugate gradient under mild assumptions, especially when the numerical rank r(A) is o(n).The comparison uses eigenvalue-dependent convergence bounds; in extreme cases, conjugate gradient requires O(n) iterations.
  • Symmetric Positive Definite Systems: ACDM solves SPD systems by minimizing an equivalent unconstrained quadratic under a uniform row-sparsity assumption.The assumption holds trivially for dense matrices and finite-difference matrices.
  • Accelerated Randomized Kaczmarz: Randomized Kaczmarz is recovered as coordinate descent after transforming x = A^T y, enabling an accelerated variant with altered row sampling and extra O(1) work per iteration.The accelerated method preserves the coordinate-descent interpretation while changing the sampling distribution.
  • Accelerated Randomized Kaczmarz: The Kaczmarz formulation is not strongly convex in the ordinary norm because A^T may have a nontrivial null space.The analysis remedies this by using a seminorm associated with the orthogonal complement of the null space.

6 Towards the Optimality of Accelerated Coordinate Descent

This section establishes an ACDM lower bound for iterative methods under a locality assumption and explains the boundary of the optimality claim.

  • Optimality Framework: ACDM is proved optimal when an iterative method generates its sequence under the specified assumption (15).The lower-bound framework restricts how iterates and coordinate information are produced.
  • Scope: The authors do not know whether assumption (15) is necessary for the lower bound.They note that random directional function and derivative access would require at least O(n^2) iterations to obtain full local second-order information.
  • Lower Bound: Theorem 12 assumes uniformly random coordinate choices and constructs a strongly convex function with total component-wise Lipschitz constant S1.The theorem applies when S1 > 4σn > 0.
  • Lower-Bound Construction: The hard-instance argument keeps early iterates sparse because moving from Rk to Rk+1 requires querying the next partial derivative.The resulting analysis tracks the probability that many coordinates remain zero when k is small.

A Proof of Probabilistic Estimate Sequence Form

The probabilistic estimate-sequence proof constructs quadratic surrogates whose expected values contract toward the objective under strong convexity and randomized coordinate selection.

  • Setup: The general construction applies to a positive semidefinite matrix A when f is strongly convex in the induced norm.The framework permits randomized coordinate choices with probabilities p_i.
  • Estimate Sequence: The process maintains quadratic estimate functions φ_k(x) parameterized by recursively updated coefficients and centers.The initial estimate has the form φ_0(x) = φ_0* + ζ_0/2 ||x − v_0||_A^2.
  • Convergence Proof: The inductive proof shows E[φ_k(x)] ≤ (1 − η_k)f(x) + η_k E[φ_0(x)] for every x.The base case follows from η_0 = 1, and the induction uses randomized coordinate expectations and strong convexity.
  • Updates: The update formulas determine the next center v_{k+1} from the gradient and the quadratic form represented by A.Applying A† yields the desired center update in the semidefinite setting.

B Bounding ACDM Coefficients

This section bounds the recursively defined ACDM coefficients by analyzing the growth of γ_k, β_k, α_k, a_k, and b_k.

  • Coefficient Relations: The coefficient bounds are established through relationships among α_k, β_k, γ_k, a_k, and b_k.The lemma provides the estimates required for the main convergence theorem.
  • Monotonicity: β_k decreases while b_k and a_k are nondecreasing under the stated parameter inequalities.The bounds use 2 S̃_α n ≥ σ^(1−α).
  • Growth Bounds: The growth rates of a_k and b_k follow from recursive relations and are proved by induction.The analysis first bounds b_k and then uses the definitions to control a_k.
  • Growth Bounds: A lower bound on γ_k is obtained through an upper bound on β_k, using b_{k+1} = b_k √β_k.This relation drives the subsequent estimate of α_k.

C Proof of Numerically Stable ACDM

The proof establishes convergence through a sequence of coefficient, gradient, lower-envelope, and expectation bounds, then shows that ACDM's coefficient updates are numerically stable and efficiently computable.

  • Convergence proof: The proof controls errors from approximate updates using the convexity parameter, Lipschitz condition, expectation bounds, and specially chosen coefficients.These ingredients are combined to bound perturbation effects and maintain the desired inequalities through iteration k.
  • Convergence proof: Theorem 5 is proved by combining coefficient-growth claims, gradient-norm bounds, lower-envelope estimates, and summed inequalities.The argument invokes Lemma 14 and derives the theorem after solving a resulting quadratic equation.
  • Numerical stability and implementation: ACDM Step 3a admits explicit coefficient formulas and can be implemented with O(log n) bits of precision.The coefficient-stability lemma states that this precision suffices to obtain the required polynomial accuracy.
  • Numerical stability and implementation: The coefficient recurrence is a contraction because 0 ≤ f ′(γ) ≤ 1 − γσ1−α / ˜Sα < 1, so accumulated computation error remains bounded.The paper concludes that O(log n) bits of precision suffice despite error accumulation over k steps.
Loading 1305.1922v1…