Source-linked AI summary
An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
Ji Liu, Stephen J. Wright, Christopher Ré, Victor Bittorf, Srikrishna Sridhar
TL;DR
The paper addresses asynchronous parallel optimization of smooth convex objectives without synchronization. It proposes stochastic coordinate updates on shared data, proves linear convergence under essential strong convexity and a 1/K rate for general convex functions, and relates near-linear speedup to delays and cross-coordinate interactions.
Problem
Serial gradient and coordinate methods depend on previous iterations, motivating an asynchronous parallel method for unconstrained and separable-constrained convex optimization.
Method
AsySCD repeatedly selects a random coordinate, evaluates its partial gradient from a shared iterate, and applies a scaled update, clipping it when separable constraints require.
Results
The method has linear convergence under essential strong convexity and a sublinear 1/K rate for general convex functions, with near-linear speedup governed by delay and gradient-coordinate interactions.
Takeaways & Limitations
The analysis indicates that asynchronous multicore implementations can achieve near-linear speedup when delays and cross-coordinate interactions are sufficiently controlled.
Takeaways & Limitations
The convergence analysis does not allow inconsistent reads, although the paper discusses their practical rarity and a rule that could avoid them.
Abstract
from arXiv · showhide
We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential strong convexity property and a sublinear rate ($1/K$) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is $O(n^{1/2})$ in unconstrained optimization and $O(n^{1/4})$ in the separable-constrained case, where $n$ is the number of variables. We describe results from implementation on 40-core processors.
1. Introduction
The paper develops AsySCD for convex optimization, using asynchronous coordinate updates without synchronization. Its analysis relates convergence and parallel speedup to essential strong convexity, coordinate interactions, and update delays.
- Scope: The algorithm targets convex objectives arising in data analysis and machine learning, including support vector machines, LASSO, and logistic regression.The paper reports computational experience and organizes convergence analyses for unconstrained and separable-constrained cases.
- Proposed method: AsySCD asynchronously updates one randomly selected coordinate using its partial gradient, with clipping for separable constraints.Processors operate concurrently without synchronization, while update age is bounded by τ.
- Convergence: Linear convergence is available under essential strong convexity, while general convex functions achieve a sublinear 1/K rate.Essential strong convexity is weaker than ordinary strong convexity and permits non-singleton solution sets.
- Parallelism: Near-linear speedup depends on the delay bound τ and a parameter measuring cross-coordinate interactions in the gradient.Nearly diagonal Hessians permit higher degrees of parallelism.
- Analysis quantities: Lres, Lmax, and coordinate-specific Lipschitz constants bound directional nonlinearity and gradient interactions used in the analysis.For diagonally dominant convex quadratics, the ratio Lres/Lmax is at most 2.
2. Related Work
Prior work includes serial stochastic coordinate methods, synchronous parallel schemes, and asynchronous fixed-point or stochastic-gradient methods. AsySCD differs by combining asynchronous coordinate updates with linear convergence under essential strong convexity, without allowing inconsistent reads.
- Serial coordinate methods: Serial stochastic coordinate descent has linear convergence for strongly convex objectives and a sublinear 1/K rate for convex objectives.Nesterov’s method covers unconstrained and separably constrained smooth optimization.
- Synchronous parallel methods: Synchronous parallel methods coordinate concurrent updates, with speedup depending in some approaches on data sparsity or synchronization design.Examples include distributed coordinate, splitting, ADMM, and dual-averaging methods.
- Comparison with prior asynchronous work: Earlier asynchronous fixed-point analysis requires bounded ages and a diagonal-dominance contraction condition stronger than strong convexity.AsySCD instead guarantees linear convergence under essential strong convexity, but does not allow inconsistent reads.
- Asynchronous methods: Hogwild! uses lock-free asynchronous stochastic gradients, whereas AsySCD evaluates one exact randomly selected gradient component per iteration.Hogwild!’s analysis approximately matches the sublinear 1/K rate of its serial counterpart under certain conditions.
- Subsequent work: AsySCD extends the asynchronous coordinate-descent line, with a later work treating smooth-plus-separable composite objectives and emphasizing inconsistent reads.The cited extension is by Liu and Wright (2014).
3. Algorithm
AsySCD runs randomized coordinate-descent updates concurrently on shared x without synchronization. Each processor reads x, computes one partial gradient, and applies a scaled coordinate update subject to feasibility clipping when needed.
- Coordinate update process: Each processor repeatedly chooses a coordinate uniformly at random, reads x, and evaluates the corresponding partial gradient.The selected coordinate is denoted i and the partial gradient is ∇if(x).
- Coordinate update process: The selected component is updated using a step of length γ/Lmax in the partial-gradient direction.The step-length parameter γ is part of the algorithm specification.
- Global iteration model: A global counter j indexes updates, while i(j) records the updated component and k(j) identifies the iterate used to compute that update.The system-wide algorithm tracks these quantities despite concurrent processor execution.
- Global iteration model: The delay satisfies j − k(j) ≤ τ, where τ bounds the age of the iterate used for an update and captures essential parallelism.The paper interprets τ as relating to the number of processors or threads involved.
- Constraint handling: For separable constraints, projection reduces to clipping the updated coordinate; no projection is needed in the unconstrained case.This preserves feasibility with respect to the coordinate-wise feasible interval.
- Implementation distinction: AsySCD updates the latest shared x value rather than an earlier iterate and computes an exact single gradient component, distinguishing it from earlier asynchronous schemes.Processors still operate concurrently, so x can change between the read and update.
4. Unconstrained Smooth Convex Case
In the unconstrained case, AsySCD's convergence depends on delay, steplength control, and essential strong convexity. It achieves linear convergence under essential strong convexity and a 1/K sublinear rate for general convex functions, while permitting near-linear parallel speedup under suitable delay and interaction conditions.
- Parameter choice: The steplength γ balances progress against stale gradient information caused by asynchronous delays.The analysis enforces this tradeoff through a bound involving expected squared gradient norms at successive iterates.
- Convergence guarantees: Linear convergence holds for AsySCD when essential strong convexity is satisfied, while general convex functions achieve a 1/K sublinear rate.The unconstrained convergence theorem covers both regimes; the strongly convex result improves on Hogwild!'s sublinear guarantee under strict convexity.
- Delay and interaction conditions: The analysis uses delay τ, cross-coordinate interaction measures, and the ratio Lmax/Lres to control convergence and allowable parallelism.The constants Lres, Lmax, and Li capture directional nonlinearity and interactions among gradient components.
- Parallel speedup: When the delay condition holds, convergence expressions do not depend on the number of cores, implying that linear speedup can be expected.A small Lres/Lmax ratio indicates greater potential parallelism; near-linear speedup can reach O(√n) cores in the relevant setting.
- Convergence guarantees: High-probability convergence estimates are also established under sufficient conditions on the iteration index.Theorem 3 provides such an estimate for both essentially strongly convex and general convex cases.
5. Constrained Smooth Convex Case
With separable constraints, AsySCD clips coordinate updates to preserve feasibility and analyzes a constraint-specific steplength condition. It obtains convergence guarantees and near-linear speedup under stricter delay conditions than in the unconstrained case.
- Method and parameter choice: For separably constrained problems, AsySCD uses a constraint-specific progress ratio based on expected differences between successive primal iterates.The unconstrained gradient-norm ratio is replaced because constraints make it inappropriate; the full-update vector provides a related but distinct reference.
- Convergence guarantees: Convergence of the expected error to zero is established for separably constrained problems under the stated parameter and delay conditions.The constrained theorem assumes n ≥ 5 and imposes bounds on the steplength parameter γ.
- Convergence guarantees: Linear convergence holds under essential strong convexity, while general smooth convex functions receive the corresponding sublinear guarantee.The constrained results provide separate bounds for the essentially strongly convex and general convex cases.
- Parallel speedup: When the constrained delay condition holds, convergence is not appreciably affected by delay and near-linear multicore speedup can be expected.The condition is more restrictive than in the unconstrained case but still holds for many problems.
- Parallel speedup: If Lres/Lmax is dimension-independently bounded, the maximal supported core count is O(n^1/4), below the unconstrained O(n^1/2) scale.The constrained setting therefore permits a smaller asymptotic number of cores under the stated ratio condition.
- Convergence guarantees: High-probability complexity bounds are also derived for the constrained case under separate sufficient conditions for the two convexity regimes.Theorem 6 covers both essentially strongly convex and general convex cases.
6. Experiments
Experiments evaluate AsySCD through a 40-core implementation on unconstrained, bound-constrained, and graph-derived quadratic problems, measuring convergence, speedup, and solver comparisons. The results indicate near-linear speedup on synthetic quadratic problems, while sparse graph problems are limited mainly by memory contention and global locking is not competitive.
- Implementation: The DW implementation assigns Q slices and x partitions across up to 40 Intel Xeon cores, organizing computation into epochs and reshuffling coordinates every p epochs.Each epoch updates every component once; experiments compare p = 1 and p = 10.
- Convergence and speedup: The total computation needed to reach a given precision is almost independent of core count up to 40 cores, so non-linear speedup is attributed to implementation systems issues rather than convergence degradation.This observation holds across the reported test problems.
- Convergence and speedup: Reshuffling every epoch is slightly faster on synthetic unconstrained QP but slightly slower on Amazon and DBLP than reshuffling every tenth epoch, with comparable epoch-wise convergence overall.Because shuffling becomes expensive for large dimensions, the authors recommend a large p for large-dimensional problems.
- Convergence and speedup: Near-linear speedup is observed for the two synthetic QP problems, whereas graph-derived Problems 3 and 4 reach at most 12-14 speedup and gain little beyond about 12 cores.The authors attribute this degradation mostly to memory contention because the graph problems use sparse Q matrices with a lower computation-to-memory-access ratio.
- Solver comparisons: Global locking is not competitive, while AsySCD outperforms synchronous SynGD and LIBSVM in the reported comparisons.The SynGD comparison shows a high synchronization cost, and the LIBSVM comparison uses 40 cores for kernel SVM.
7. Extension
AsySCD can be extended from single coordinates to coordinate blocks, with the analysis adapted using block-defined smoothness quantities. A steplength redefinition provides another analyzed efficiency variant.
- Block-coordinate extension: AsySCD extends to block-coordinate updates by partitioning coordinates into blocks and modifying the algorithm accordingly.The analysis is extended when Li, Lmax, and Lres are defined in the block sense.
- Block-coordinate extension: The block extension uses block projections and block sizes in defining the relevant smoothness quantities.
- Steplength variant: A more efficient variant redefines the steplength in Algorithm 1, with the existing analysis applied to the modified choice.The supplied passage introduces this variant and indicates that the analysis carries over.
8. Conclusion
The paper proposes asynchronous parallel stochastic coordinate descent for convex objectives in unconstrained and separable-constrained settings. It proves sublinear convergence for general convex functions, stronger linear convergence under essential strong convexity, and analyzes when near-linear parallel speedup is expected.
- AsySCD targets convex objectives in both unconstrained and separable-constrained optimization.
- General convex functions receive a proved sublinear convergence rate of 1/K, while essential strong convexity yields stronger linear convergence.
- The analysis characterizes the extent of near-linear speedup achievable by parallel implementations through a problem-dependent parameter.
Appendix A. Proofs for Unconstrained Case
Appendix A establishes the unconstrained AsySCD convergence results through technical bounds on delayed updates, gradient behavior, and expected objective values. It derives monotonicity and then proves linear or sublinear rates under the corresponding convexity assumptions.
- The appendix develops convergence proofs for AsySCD in the unconstrained case.
- Delay contributes an error term because stale and current gradients differ, while the bounded update age controls this discrepancy.
- The expected objective gap is shown to decrease monotonically.
- Essential strong convexity: Under essential strong convexity, the monotonicity and technical bounds imply the linear convergence claim.
- General convexity: For general smooth convex functions, the same framework completes the proof of the sublinear convergence rate.
- Parameter choice: Choosing γ = 1/ψ satisfies the required bounds and yields the stated specialized rates.
Appendix B. Proofs for Constrained Case
Appendix B proves convergence for the separably constrained case by controlling projected coordinate updates, delay terms, and expected objective changes. It establishes monotonicity, then derives sublinear and linear rates under general convexity and essential strong convexity.
- The constrained proof introduces notation and formulates the coordinate update using projected, feasible iterates.
- The analysis bounds update differences using projection nonexpansiveness and the bounded delay structure.
- The expected objective is proved monotonically decreasing under the steplength bounds.
- General convexity: The constrained smooth convex case receives a proved sublinear convergence rate.
- Error control: The proof controls delay-related terms through bounds on T1, T2, and T3 and their expectations.
- Essential strong convexity: Under essential strong convexity, the additional property combined with the preceding bounds establishes the linear convergence rate.
- Parameter choice: Setting γ = 1/2 produces the specialized constrained convergence bounds.