Accelerated, Parallel and Proximal Coordinate Descent

Olivier Fercoq; Peter Richtárik

Source-linked AI summary

Accelerated, Parallel and Proximal Coordinate Descent

Olivier Fercoq, Peter Richtárik

arXiv:1312.5799v2Dec 20, 2013math.OCcs.DCmath.NAstat.ML

TL;DR

Very large optimization problems motivate coordinate methods that decompose computations and exploit sparsity, but accelerated methods can incur full-vector-operation costs. The paper proposes APPROX, a stochastic coordinate descent method combining acceleration, parallelism, and proximal updates, with ESO-based stepsizes using average separability. It reports O(1/k^2) convergence and an implementation that avoids forming full-dimensional vectors for a supported subclass, while noting a case where earlier stepsizes may be better.

Problem
Very large optimization problems require decomposition and parallel computation, while existing accelerated coordinate methods can be bottlenecked by full-dimensional vector operations.
Method
APPROX combines accelerated, parallel, and proximal stochastic coordinate descent with new ESO-based stepsizes based on data-weighted average separability.
Results
O(1/k^2) convergence is reported, and full-dimensional vector operations can be avoided for a supported subclass of problems.
Takeaways & Limitations
Average-separability-based stepsizes can produce larger steps for some problems, and the resulting method can be implemented without forming full-dimensional iterates in supported cases.
Takeaways & Limitations
For a case that can occur with logistic regression, the Richtárik–Takáč stepsizes may be better than the proposed stepsizes.

Abstract

from arXiv · show

We propose a new stochastic coordinate descent method for minimizing the sum of convex functions each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel and PROXimal; this is the first time such a method is proposed. In the special case when the number of processors is equal to the number of coordinates, the method converges at the rate $2\barω\bar{L} R^2/(k+1)^2 $, where $k$ is the iteration counter, $\barω$ is an average degree of separability of the loss function, $\bar{L}$ is the average of Lipschitz constants associated with the coordinates and individual functions in the sum, and $R$ is the distance of the initial point from the minimizer. We show that the method can be implemented without the need to perform full-dimensional vector operations, which is the major bottleneck of existing accelerated coordinate descent methods. The fact that the method depends on the average degree of separability, and not on the maximum degree of separability, can be attributed to the use of new safe large stepsizes, leading to improved expected separable overapproximation (ESO). These are of independent interest and can be utilized in all existing parallel stochastic coordinate descent algorithms based on the concept of ESO.

1 Introduction

APPROX is introduced to address massive optimization problems that require decomposition and parallel computation, combining acceleration, parallel updates, and proximal steps. Its analysis uses average separability-aware stepsizes and targets O(1/k^2) convergence while addressing full-vector-operation bottlenecks.

Motivation: Large-scale optimization problems increasingly require decomposition because full-vector iterative methods are difficult to use at extreme problem sizes.Coordinate descent exploits smaller pieces and sparsity, while parallel architectures motivate parallel and distributed variants.
Contributions: APPROX is presented as the first stochastic coordinate descent method that is simultaneously accelerated, parallel, and proximal.The paper states that prior accelerated coordinate-descent results were neither proximal nor parallel.
Contributions: O(1/k^2) convergence is the paper’s stated acceleration guarantee, with k denoting the iteration counter.The authors relate this rate to accelerated gradient methods and accelerated stochastic coordinate descent.
Contributions: New ESO-based stepsizes use a data-weighted average separability degree ¯ω rather than the maximum degree ω.For some problem classes, including quadratic component functions, these stepsizes can be much larger than earlier PCDM stepsizes.
Implementation: The method identifies a subclass where accelerated full-vector operations can be eliminated, extending ideas for convex quadratics to block-sparse scalar-function compositions.The paper’s implementation discussion specifically addresses avoiding formation of the convex-combination iterate yk.

2 Stepsizes for parallel coordinate descent methods

The section develops ESO-based stepsizes for parallel coordinate descent, with complexity informed by blockwise separability and sampling. It also gives conditions for deriving these constants and compares resulting stepsizes with prior methods.

ESO framework: The ESO framework combines uniform block sampling with an inequality that determines coordinate updates and supports complexity analysis.The sampling selects blocks randomly with equal inclusion probability, while computable weights provide the ESO constants.
ESO framework: When only τ coordinates are selected, updates lie in a random low-dimensional subspace where gradients may vary more slowly than in the full space.This can yield larger steps for sparse or partially separable functions, especially when τ is much smaller than n.
New stepsizes: The proposed stepsizes account for all individual degrees of separability ωj rather than only the maximum ω.The resulting average quantity is a data-weighted average of the values {ωj}, with weights summing to n.
New stepsizes: For functions satisfying block-Lipschitz gradient assumptions, the paper derives an ESO inequality for τ-nice sampling and extends it to the full objective.The τ-nice sampling chooses a uniformly random subset of cardinality τ, and the theorem supplies corresponding ESO constants.
Computing constants: For compositions fj(x) = φj(aTj x), block-Lipschitz constants Lji can be computed from the Lipschitz derivative constant of φj and the corresponding matrix block.The resulting constants certify that each component satisfies the required block-Lipschitz condition.
Computing constants: The derived stepsizes are reported as better than prior proposals for quadratic objectives, while the compared norm bounds coincide at τ = 1 or τ = n depending on the bound.The table comparison concerns elementary blocks with Bi = 1 for the quadratic objective.

3 Accelerated parallel coordinate descent

APPROX is a stochastic coordinate descent method for regularized convex optimization that combines acceleration, parallel block updates, and proximal steps. Its analysis gives complexity bounds using new ESO-based stepsizes, while covering deterministic full-block updates and separability-dependent parallel speedup.

APPROX minimizes a regularized convex objective with a possibly nonsmooth block-separable convex regularizer.
The algorithm combines accelerated updates, random parallel block sampling, and parallel proximal subproblem solves.It maintains xk, yk, and zk sequences, samples blocks Sk, and updates selected blocks in parallel.
APPROX is both proximal and parallel, unlike existing accelerated coordinate descent methods identified by the authors.The method reduces to proximal gradient descent when n = 1 and to a serial accelerated coordinate method when τ = 1 and ψ ≡ 0.
When all blocks are updated, the method becomes deterministic and its bound simplifies to the advertised rate involving average separability and average Lipschitz quantities.There is no expectation in this full-block case.
The new ESO-based stepsizes produce complexity that can improve substantially when the average separability degree is much smaller than the maximum degree.The improvement is attributed to incorporating all block-dependence values rather than only their maximum.
The authors report linear speedup in the number of parallel updates or processors, with average separability decoupled from τ.They state that separability can remain beneficial for large parallel update counts.

4 Complexity analysis

The complexity analysis establishes convergence through lemmas on the acceleration sequence, convex-combination structure, and stochastic block-gradient mappings. These ingredients are combined by total expectation and recurrence unrolling to prove the main result.

The analysis begins by establishing properties of the sequence θk used in APPROX.The sequence is decreasing and satisfies the stated upper bound involving k, n, and τ.
Each iterate xk is represented as a convex combination of z0 through zk with nonnegative coefficients summing to one.The coefficients are defined recursively and the representation is proved inductively.
The Euclidean nature of the block norms is required only in the lemma applying a standard proximal-gradient result.
A technical lemma connects the deterministic gradient mapping that produces z̃k+1 with the stochastic block-gradient mapping that produces zk+1.The connection is expressed through conditional expectation over the sampled block set Sk.
The proof combines convexity, identities involving yk and zk, and bounds on the expected next iterate.The resulting inequality is rearranged and used in the recurrence argument.
Applying total expectation and unrolling the recurrence yields the convergence guarantee for the iterates of Algorithm 1.The proof uses the initial conditions x0 = z0 and the bound on θk−1.

5 Implementation without full-dimensional vector operations

The paper rewrites APPROX into an equivalent implementation that avoids forming dense full-dimensional vectors during iterations. Maintaining residuals and exploiting block sparsity reduces per-iteration work to processor-local block-scale computation in favorable settings.

The direct algorithm can require O(N) arithmetic operations because yk is a convex combination of generally dense xk and zk.This full-dimensional operation is identified as a bottleneck of accelerated coordinate methods.
Algorithm 2 rewrites Algorithm 1 into an equivalent form designed for efficient implementation.Proposition 1 states that the corresponding xk, yk, and zk sequences are identical.
The efficient implementation avoids explicitly forming xk and computes the needed block gradients without forming yk when residuals can be maintained.It expresses yk using uk and z̃k, accesses yk only through sampled block gradients, and updates residual vectors.
Maintaining residuals makes block-gradient computation depend on local sparsity, with average cost proportional to the nonzero incidence of the sampled blocks.The stated block derivative cost is O(|Di|Ni).
For equal block size b = N/n, small |Di| and small τ yield low work; in the stated practical regime, each processor performs work proportional to one block per iteration.The paper gives total work per iteration as C = τ × O(b) when m ≤ n and average separability is O(1).
The implementation applies to convex quadratics, logistic regression, and a smooth approximation of the ℓ1 residual objective when derivative evaluation is constant-time.

6 Numerical experiments

Experiments compare APPROX with existing coordinate and gradient methods across sparse regression and SVM problems. APPROX benefits from its accelerated rate and new stepsizes, while results also expose setting-specific limitations.

6.1 The effect of new stepsizes: 5× speedup is achieved by the new stepsizes on an extreme sparsity distribution, while the intermediate distribution yields a 25% complexity improvement for τ = 1000.Uniform sparsity produces identical results because vfr = vrt; the extreme instance is artificially constructed.
6.1 The effect of new stepsizes: n× speedup is possible for APPROX over vrt on artificially constructed matrices containing both dense and maximally sparse rows.For τ = n, the complexity ratio can reach θ = n.
6.4 Training linear support vector machines: APPROX is slower initially but faster afterward than PCDM on KDDB, whose unknown optimum prevents direct actual-accuracy comparison.Both methods converge quickly, and each PCDM iteration is half as expensive at the beginning.
6.3 Lasso: APPROX does not directly promote sparsity in x; obtaining a sparse solution may require post-processing with a sparsity-oriented method.Only the z variable receives proximal steps that encourage sparsity.
6.4 Training linear support vector machines: APPROX is about twice as fast as SDCA on the Malicious URL dual SVM instance when comparing decreases in the duality gap.The experiment uses a single processor because the dataset is not particularly suited to parallel coordinate descent.

7 Conclusion

The conclusion presents APPROX as a stochastic coordinate descent method combining acceleration, parallelism, proximal updates, improved stepsizes, and implementation without full-vector operations.

7 Conclusion: APPROX achieves an O(1/k2) convergence rate and is better able to obtain high-accuracy solutions on non-strongly convex instances.The accelerated rate is one of the four strategies summarized in the conclusion.
7 Conclusion: APPROX is parallel, enabling better use of modern parallel computing architectures while addressing the problem dimension n.Parallelism is identified as a distinct acceleration strategy.
7 Conclusion: New longer stepsizes provide faster convergence when the degree of separability ω exceeds the average degree of separability ¯ω.This strategy is presented as part of APPROX’s combined acceleration design.
7 Conclusion: APPROX can be implemented without full-dimensional vector operations.This removes a computational requirement associated with accelerated methods.

A Proof of Proposition 1 (equivalence)

The proof establishes equivalence between the algorithm’s represented variables through initialization, induction over selected and unselected coordinates, and the resulting update relations.

A Proof of Proposition 1 (equivalence): The equivalence statement holds at k = 0 because all initialized representations are equal.The proof then proceeds by induction.
A Proof of Proposition 1 (equivalence): The induction handles coordinates inside and outside the sampled set before combining the two cases.This case split is used to derive the next-iteration relation.
A Proof of Proposition 1 (equivalence): The resulting relations are matched to Algorithm 2’s steps, completing the equivalence proof.The proof concludes after comparing the derived expressions with the algorithm updates.