Source-linked AI summary
Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
Ji Liu, Stephen J. Wright
TL;DR
The paper addresses asynchronous composite optimization when processors may read coordinates while other processors write them, a case not captured by prior consistent-read analyses. It proposes AsySPCD, an asynchronous stochastic proximal coordinate-descent algorithm, and proves linear convergence under optimal strong convexity and 1/k convergence for general convex functions. The analysis indicates near-linear speedup when delay and cross-coordinate interactions are sufficiently controlled, with τ varying like n^1/4 in an important setting.
Problem
Prior asynchronous analyses did not account for components being written by some cores while read by others in composite stochastic coordinate descent.
Method
AsySPCD repeatedly samples a coordinate, computes its partial gradient from shared-memory data, and performs an asynchronous proximal coordinate update without locking.
Results
AsySPCD achieves 1/k convergence for general convex functions, linear convergence under optimal strong convexity, and near-linear speedup when τ can vary like n^1/4.
Takeaways & Limitations
The analysis connects attainable parallelism to delay τ and cross-coordinate interactions, and computational experience confirms the predicted linear speedup properties in practice.
Takeaways & Limitations
The analysis requires bounded delays and, for the linear rate, the optimal strong convexity condition; τ corresponds closely to the number of cores.
Abstract
from arXiv · showhide
We describe an asynchronous parallel stochastic proximal coordinate descent algorithm for minimizing a composite objective function, which consists of a smooth convex function plus a separable convex function. In contrast to previous analyses, our model of asynchronous computation accounts for the fact that components of the unknown vector may be written by some cores simultaneously with being read by others. Despite the complications arising from this possibility, the method achieves a linear convergence rate on functions that satisfy an optimal 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/4})$. We describe results from implementation on ten cores of a multicore processor.
1. Introduction.
The paper formulates composite convex optimization and motivates an asynchronous stochastic proximal coordinate-descent method that accommodates inconsistent reads. It establishes linear convergence under optimal strong convexity and 1/k convergence for general convex functions, with near-linear speedup tied to delays and cross-coordinate interactions.
- Problem formulation: The objective combines a smooth convex function f with a separable, closed, convex function g.Separable means g(x) is expressed as a sum of coordinate functions g_i.
- Motivation: Asynchronous stochastic gradient and coordinate methods are motivated by the serial dependence of gradient-based algorithms in data-analysis and machine-learning objectives.Examples include support vector machines, LASSO, and regularized logistic regression.
- Method: AsySPCD repeatedly samples a coordinate, reads shared x, evaluates its partial gradient, and applies a proximal coordinate update without locking.The update accounts for the coordinate regularizer g_i.
- Asynchronous model: Inconsistent reads allow a core’s evaluation vector to differ from the shared vector later updated, while a delay bound τ limits missed component updates.This model permits components to be written while others are reading them.
- Convergence: Linear convergence holds under optimal strong convexity, which is weaker than ordinary strong convexity, while general convex objectives achieve a 1/k rate.The analysis also relates speedup to τ and cross-coordinate interactions in ∇f.
- Coordinate interactions: Λ ≤2 when the quadratic objective’s Hessian is diagonally dominant.Λ quantifies the relationship between the restricted and coordinate Lipschitz constants.
2. Related Work.
Prior work established stochastic coordinate-descent rates and asynchronous methods under differing read models and assumptions. This paper positions AsySPCD as an inconsistent-read composite optimization method distinct from consistent-read analyses and stronger contraction requirements.
- Asynchronous optimization: Fixed-point asynchronous methods obtained linear convergence under maximum-norm contraction, a condition stronger than strong convexity for certain quadratic objectives.Some related schemes appear to require locking to ensure consistent reading and writing.
- Prior asynchronous methods: AsySCD proved analogous rates under essential strong convexity but used a consistent-read asynchronous model.Hogwild! also used consistent reads in the cited comparison.
- Positioning: AsySPCD gives multiple processors shared access to x and has each processor repeatedly perform randomized proximal coordinate descent.The steplength parameter γ is discussed in the convergence analysis.
3. Algorithm.
AsySPCD asynchronously updates randomly selected coordinates using partial gradients computed from potentially inconsistent shared-memory reads. Its global formulation tracks update order, stale component ages, and a bounded delay parameter τ.
- Local algorithm: Each local iteration randomly chooses coordinate i, reads x, evaluates ∇_i f at the read vector, and updates coordinate i.The update uses a step based on Lmax and then applies a proximal operation for g_i.
- Update assumption: The implementation assumes no other process modifies x_i while its proximal update is being computed.A practical implementation assigns each coordinate to one core; compare-and-swap is an alternative.
- Read model: Figure 3.1 contrasts consistent reads, which match a shared-memory state, with inconsistent reads assembled from components read at different times.The inconsistent vector may not have existed in shared memory at any single time.
- Global formulation: The global view indexes updates by j, records updated coordinate i(j), and denotes the gradient-evaluation vector by x̂^j.Components of x̂^j can have different ages relative to the current shared state x^j.
- Delay model: The delay parameter τ bounds the age of components in the evaluation vector and corresponds closely to the number of participating cores when update costs are similar.The stale-coordinate set is empty when the evaluation vector equals the current iterate.
- Convergence analysis: The convergence theorem covers both linear convergence for optimally strongly convex objectives and 1/k convergence for general convex objectives, with rates depending strongly on τ.The proof techniques differ from those used for consistent-read algorithms.
4. Main Results.
The analysis establishes convergence guarantees for asynchronous stochastic proximal coordinate descent under inconsistent reads, with rates governed by delay and cross-coordinate interaction. It also characterizes when near-linear parallel speedup is achievable.
- Algorithmic mechanism: The expected update captures the behavior of the asynchronous coordinate update, while stale gradient information creates a steplength tradeoff.The parameter γ must balance progress against applying gradient information that may be stale when the update occurs.
- Convergence rates: Linear convergence holds when the optimal strong convexity property holds, with rate constants nearly matching short-step proximal full-gradient descent.The result requires suitable choices of ρ and γ satisfying the theorem’s bounds.
- Convergence rates: General smooth convex functions achieve a sublinear 1/k convergence rate.The corresponding bound is stated for the general convex case.
- Parallel speedup: Near-linear speedup is indicated when the delay bound τ is sufficiently small relative to n and the cross-coordinate interaction ratio Λ.The analysis links τ to the number of participating cores and Λ to interactions in ∇f.
- Scope and novelty: The results extend prior constrained AsySCD analysis to composite optimization with an inconsistent-read computation model.The proof techniques differ substantially from those used for consistent-read algorithms.
- Parallel speedup: τ can scale as n^1/4 in important applications without affecting iteration-wise convergence, enabling near-linear speedup in the number of cores.This bound is weaker than the O(n^1/2) core allowance stated for unconstrained AsySCD.
5. Experiments.
Experiments evaluate AsySPCD on synthetic sparse least-squares problems using 1 to 10 shared-memory threads. The computations examine objective progress and speedup across core counts, while recovering the support of the planted sparse solution.
- Setup: The synthetic data use Gaussian A, sparse planted solutions, and noisy measurements b = Ax* + ε.The experiments use σ = 0.01 with dimensions (m,n,s) = (6000,10000,10) and (12000,20000,20) in Figures 5.1 and 5.2.
- Setup: Experiments use 1 to 10 threads on an Intel Xeon machine with shared memory, with Q := A^T A and c := A^T b computed offline.Each thread receives a slice of Q and the corresponding subvector of c.
- Measured outcomes: The final computed solution has nonzeros in the same locations as the planted solution, although noise causes the values to differ.This outcome is reported for the computed sparse solutions.
- Measured outcomes: Figures 5.1 and 5.2 plot objective function versus epochs and obtained speedup against ideal linear speedup for 1, 2, 4, 8, and 10 cores.The figures compare convergence behavior and parallel scaling across core counts.
6. Conclusions.
The paper presents AsySPCD for composite objectives under asynchronous inconsistent reads. It proves sublinear convergence generally, stronger linear convergence under optimal strong convexity, and analyzes conditions for near-linear speedup.
- Contribution: AsySPCD is an asynchronous parallel proximal stochastic coordinate-descent algorithm for composite objectives.The composite objective combines a smooth convex component with a separable convex regularizer.
- Contribution: General convex functions obtain a sublinear 1/k rate, while optimally strongly convex problems obtain linear convergence.The convergence guarantees are part of the paper’s main theoretical contribution.
- Contribution: Near-linear speedup depends on cross-coordinate gradient interactions and the delay bound τ.The computational experience confirms linear speedup up to the reported ten-core implementation, although the passage is truncated before the full statement.
Appendix A. Proofs of Main Results.
This section presents the proofs for the paper’s main convergence results, beginning with preliminaries and proceeding to Theorem 4.1 and Corollary 4.2.
- The section begins by establishing preliminary results for the convergence proofs.
- It then proves Theorem 4.1.
- Finally, it proves Corollary 4.2.
A.1. Preliminaries.
The preliminaries define the random-coordinate notation, asynchronous iterates, and the coordinate-update quantities used in the analysis.
- Randomness: The component indices i(0), i(1), ..., i(j) are independent random variables.Expectations are taken over all random variables, with E_i(j) denoting conditional expectation given previous indices.
- Coordinate update: Only coordinate i(j) changes between xj and xj+1; the remaining coordinates are unchanged.The coordinate update is formulated through a proximal operation for the selected component.
A.2. Proof of Theorem 4.1.
The proof establishes expected-objective monotonicity and derives sublinear convergence for general convex functions and linear convergence under optimal strong convexity.
- Proof mechanism: The delay-dependent induction relies on gradient variation bounds because consecutive iterates differ in only one coordinate.The proof explicitly uses ∥∇f(xj) − ∇f(xj−1)∥ ≤ Lres∥xj − xj−1∥.
- Objective monotonicity: E F(xj+1) ≤ E F(xj) for every j = 0, 1, 2, ... .The expected objective is therefore monotonically decreasing along the asynchronous iterations.
- General convex case: The sublinear convergence expression (4.8) follows by dropping a nonnegative term and rearranging the established inequality.This completes the general convex case after bounding the delay-related terms.
- Optimal strong convexity: The proof of linear convergence uses the optimal strong convexity property together with the previously established bounds.The resulting estimate is obtained by induction and substitution into the definition of Sj.
A.3. Proof of Corollary 4.2.
The corollary verifies that choosing steplength γ = 1/2 satisfies both required bounds and yields the stated specialized expressions.
- Steplength choice: γ = 1/2 satisfies the first bound in (4.5).This is established using the selected parameter relations and the preceding inequalities.
- Resulting bounds: Substituting γ = 1/2 into (4.7) and (4.8) yields expressions (4.11) and (4.12).The same steplength choice is used for both convergence expressions.