PaperlayerView exact revision on arXiv

Source-linked AI summary

ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

Zhimin Peng, Yangyang Xu, Ming Yan, Wotao Yin

arXiv:1506.02396v5math.OCcs.DCstat.ML

TL;DR

The paper addresses how to solve broad fixed-point problems in parallel without synchronization while retaining convergence guarantees. It proposes ARock, which uses asynchronous random coordinate updates based on possibly stale reads, and proves almost-sure convergence with stronger and linear guarantees under additional conditions. The framework is instantiated across several computational applications and evaluated on sparse logistic regression.

  • Problem

    Parallel computation is needed for rapidly growing large-scale data, but asynchronous algorithms are harder to analyze and ensure convergence for generic nonexpansive fixed-point problems.

  • Method

    ARock is an asynchronous framework in which multiple agents randomly select and update coordinates using local reads, with step sizes and selection-probability normalization.

  • Results

    With probability one, ARock converges to a fixed point under bounded step sizes when the nonexpansive operator has a fixed point; it also provides strong and linear convergence in stronger settings.

  • Takeaways & Limitations

    ARock supports asynchronous fixed-point algorithms for linear systems, convex optimization, machine learning, distributed and decentralized problems, with preliminary experiments illustrating high efficiency versus synchronous algorithms.

  • Takeaways & Limitations

    ARock is worthwhile only when a coordinate update is much cheaper than a full update, and reported performance depends on granularity, sparsity, compiler settings, cache behavior, memory contention, and load imbalance.

Abstract

from arXiv · show

Finding a fixed point to a nonexpansive operator, i.e., $x^*=Tx^*$, abstracts many problems in numerical linear algebra, optimization, and other areas of scientific computing. To solve fixed-point problems, we propose ARock, an algorithmic framework in which multiple agents (machines, processors, or cores) update $x$ in an asynchronous parallel fashion. Asynchrony is crucial to parallel computing since it reduces synchronization wait, relaxes communication bottleneck, and thus speeds up computing significantly. At each step of ARock, an agent updates a randomly selected coordinate $x_i$ based on possibly out-of-date information on $x$. The agents share $x$ through either global memory or communication. If writing $x_i$ is atomic, the agents can read and write $x$ without memory locks. Theoretically, we show that if the nonexpansive operator $T$ has a fixed point, then with probability one, ARock generates a sequence that converges to a fixed points of $T$. Our conditions on $T$ and step sizes are weaker than comparable work. Linear convergence is also obtained. We propose special cases of ARock for linear systems, convex optimization, machine learning, as well as distributed and decentralized consensus problems. Numerical experiments of solving sparse logistic regression problems are presented.

1 Introduction

ARock is an asynchronous random-coordinate framework for solving fixed-point problems involving nonexpansive operators. It provides almost-sure convergence guarantees under bounded delays and step sizes, including strong and linear convergence in stronger settings.

  • Big-data applications motivate parallel methods, and ARock introduces asynchronous parallel computing with convergence guarantees.
  • Asynchronous agents avoid waiting for the slowest worker but may perform updates using information that is not current.This trades synchronization delays for disordered iterations and potentially stale reads.
  • ARock lets multiple agents asynchronously update randomly selected coordinates of x to solve a nonexpansive fixed-point problem.The coordinates lie in component Hilbert spaces, and the framework includes special forms for several applications.
  • ARock applies coordinate updates to possibly inconsistent local reads, with the update scaled by step sizes and coordinate-selection probabilities.The normalization factor m p_i^-1 handles nonuniform selection probabilities, while uniform selection simplifies the update.
  • With probability one, ARock converges weakly to a fixed point for nonexpansive operators with fixed points, and convergence is strong in finite dimensions or under demicompactness.For quasi-strongly monotone I − T, the fixed point is unique and the expected squared distance converges linearly.
  • The framework requires bounded step sizes, random coordinate selection, and finite maximal delay, while coordinate updates must be cheaper than full updates to be worthwhile.The paper also notes disadvantages of random selection, including global data storage or communication and random-number-generation overhead.
  • ARock is presented as a stochastic framework for nonexpansive operators, with special cases for linear systems, splitting methods, distributed optimization, and decentralized computing.The contributions include a new metric, stochastic Fejér monotonicity, almost-sure convergence, linear convergence, and application-specific asynchronous algorithms.

2 Applications

ARock specializes the fixed-point framework for applications where coordinate updates are cheaper than full operator evaluations, including linear systems. For linear equations, it yields asynchronous randomized row updates with convergence guarantees and linear convergence under a contraction condition.

  • Framework: ARock applies its uniform-coordinate update to special cases of the fixed-point problem, including linear equations and other applications.The applications use the simpler update with p1 = · · · = pm = 1/m.
  • Linear equations: For Ax = b, Jacobi iteration is represented by T(x) = D^-1(b − Rx), with T nonexpansive when ∥M∥2 ≤ 1.Here A = D + R, M = −D^-1R, and S = I − T.
  • Linear equations: The linear-equation specialization selects a coordinate uniformly at random and updates it asynchronously using the corresponding row computation.Each update involves the selected row of M and the corresponding entry of D^-1b.
  • Linear equations: If ∥M∥2 < 1, the linear-equation algorithm converges linearly because S is (1 − ∥M∥2)-strongly monotone.The strong monotonicity follows from T being ∥M∥2-Lipschitz continuous.

2.2 Minimize convex smooth function

ARock applies to minimizing convex smooth functions by converting the optimization problem into a fixed-point iteration involving a scaled gradient. Convergence is guaranteed under bounded step sizes, with linear convergence under restricted strong convexity.

  • Problem formulation: A convex differentiable minimization problem is expressed through S := (2/L)∇f, whose zeros are exactly the minimizers of f.The gradient is assumed L-Lipschitz continuous, and T ≡ I − S is nonexpansive.
  • ARock iteration: ARock updates one coordinate using ∇_ik f(ˆxk), requiring structure that makes the selected partial gradient cheap to compute.Examples include quadratic programs and sums of sparsely supported functions.
  • Convergence: ηk ∈ [ηmin, 1/(2τ/√m + 1)) guarantees convergence for the smooth convex optimization iteration.The result is stated for the asynchronous coordinate updates under the paper’s delay setting.
  • Convergence: Restricted strong convexity makes S quasi-strongly monotone, yielding linear convergence when the step size also satisfies Theorem 4’s condition.The modulus is µ > 0 in the stated inequality involving ∇f.
  • Comparison: Compared with cited prior work, ARock analyzes distance to the solution set and permits a step-size order O(1/τ) rather than a faster-decaying order.The comparison passage contrasts ARock with objective-error guarantees and subsequence convergence in earlier methods.

2.3 Decentralized consensus optimization

ARock extends to decentralized consensus optimization by combining local gradients with communication through a symmetric doubly stochastic mixing matrix. Poisson agent activations provide the random coordinate-selection scheme needed by the framework.

  • Problem formulation: Decentralized optimization minimizes the sum of privately held convex differentiable functions fi over a shared variable x.Each agent i has access to its own function fi, whose gradient is Li-Lipschitz continuous.
  • Consensus formulation: The consensus iteration combines mixing, xk+1 = Wxk − γ∇f(xk), with local gradient computations and communication among connected agents.The mixing matrix W is symmetric and doubly stochastic, and its nonzero off-diagonal entries define communication links.
  • ARock implementation: ARock represents the decentralized method through S based on (I − W)/γ, so each coordinate computation uses a local gradient and the corresponding mixed value.The resulting Lipschitz parameter is L = maxi Li + (1 − λmin(W))/γ.
  • ARock implementation: Computing the selected coordinate requires only neighboring entries of the asynchronously read state, while each agent can store its own coordinate locally.This reduces the communication needed for the coordinate update to the selected agent’s neighbors.
  • Asynchronous activation: Independent Poisson activations with rates λi select agent i with probability λi/Σp λp, matching ARock’s random-sampling requirement.The paper states that ARock therefore applies naturally to this decentralized setting.

2.4 Minimize smooth + nonsmooth functions

The section applies ARock to composite minimization with a smooth, Lipschitz-differentiable term and a nonsmooth convex term. Separability of the nonsmooth function enables coordinate-friendly proximal updates and convergence guarantees.

  • Problems with a closed proper convex f and convex L-Lipschitz differentiable g include support vector machines, regularized least-squares, and regularized logistic regression.
  • TFBS is α-averaged for α ∈[2/3, 1), and ARock applies when f is separable across coordinates.
  • Separable choices include the ℓ1 norm, squared ℓ2 norm, Huber function, and box-constraint indicators, whose proximal maps are simple.
  • Under strong convexity of g, the forward-backward operator is quasi-contractive and ARock achieves linear convergence.

2.5 Minimize nonsmooth + nonsmooth functions

The section treats nonsmooth-plus-nonsmooth problems through Peaceman-Rachford splitting. ARock inherits convergence from nonexpansiveness, while strong convexity yields linear convergence and implementation depends on coordinate structure.

  • For convex f and g, the Peaceman-Rachford operator combines their reflective-proximal maps and is nonexpansive.
  • ARock applied to Peaceman-Rachford splitting converges, and strong convexity of either f or g gives linear convergence.
  • The limit z* is not itself a solution; the solution is recovered as x* = proxγg z*.
  • The order of proximal operators affects both the iterates and whether coordinate-wise updates can be computed efficiently.

2.6 Async-parallel ADMM

The section derives asynchronous ADMM special cases for constrained, consensus, and decentralized optimization. Favorable block or graph structure lets agents update local variables with limited computation and communication.

  • Async-parallel ADMM: ARock applies ADMM updates to the Lagrange dual of constrained problems minimize f(x)+g(y) subject to Ax+By=b.
  • Async-parallel ADMM: When A and B are block diagonal and f and g are block separable, only the selected block’s computations are needed.
  • Consensus optimization: For consensus optimization, the resulting asynchronous ADMM algorithm applies to distributed applications.
  • Decentralized consensus: The decentralized formulation introduces edge variables yij so neighboring local variables satisfy xi = yij and xj = yij.
  • Decentralized consensus: The decentralized algorithm activates one agent at a time, uses one-sided communication, and permits delayed receipt of updated dual variables.
  • Decentralized consensus: The method differs from an asynchronous ADMM scheme that activates an edge and both associated agents, requiring two-sided communication.

3 Convergence

The convergence analysis establishes almost-sure convergence of ARock under nonexpansiveness, fixed-point existence, and bounded step sizes. Stronger operator conditions provide strong or linear convergence, while allowable step sizes depend on coordinate probabilities and delays.

  • Assumptions: The analysis assumes every coordinate has positive selection probability and selections are independent of the history, with Prob(ik=i)=pi.
  • Proof framework: ARock’s convergence proof uses a never-computed full update, an augmented history state, and a positive-definite delay-weighted metric.
  • Operator conditions: Nonexpansiveness of T is equivalent to 1/2-cocoercivity of S = I −T, which underpins the convergence analysis.
  • Step sizes: In the uniform-selection case, the step-size bound is 1/(1+2τ/√m), becoming O(1) when τ = O(√m).
  • Almost sure convergence: With properly bounded step sizes, ARock converges weakly almost surely to a fixed point; convergence is strong in finite dimensions.
  • Almost sure convergence: If T is demicompact at 0, the sequence converges strongly almost surely to a fixed point.
  • Linear convergence: Quasi-strong monotonicity with a suitable constant step size yields linear convergence, and under stated conditions η = O(1), enabling linear speedup.

4 Experiments

Experiments evaluate ARock on sparse logistic regression using real datasets and compare async-parallel and sync-parallel implementations. ARock scales nearly linearly, while synchronization suffers from sparsity-driven load imbalance.

  • Experimental setup: Experiments evaluate ARock for ℓ1 regularized logistic regression on the rcv1 and news20 datasets.The study compares single-threaded, sync-parallel, and async-parallel implementations.
  • Experimental setup: The experiments use 1 to 32 threads on a 32-core machine with 64 GB of RAM, implemented in C++ and OpenMP.
  • Scope: Running times and speedup ratios depend on granularity, sparsity, compiler flags, cache behavior, and memory-access contention.The paper does not report results for all combinations of these factors.
  • Experimental setup: Each coordinate holds roughly 50 features, coordinates are selected uniformly at random, the step size is η_k = 0.9, and tests stop after 100 epochs.
  • Load imbalance: The datasets exhibit widely varying coordinate sparsity, creating load imbalance because assigned coordinates contain different numbers of nonzeros.Figure 3 relates the sparsity distribution to poor sync-parallel performance.

5 Conclusion

The paper proposes ARock for asynchronous coordinate updates in fixed-point problems and establishes convergence and speedup results under assumptions. Numerical experiments on real data illustrate efficiency relative to sync-parallel algorithms.

  • ARock is an asynchronous parallel framework for finding fixed points of nonexpansive operators through coordinate updates.
  • The framework establishes almost sure weak and strong convergence, a linear convergence rate, and almost-linear speedup under certain assumptions.
  • Preliminary real-data experiments illustrate high efficiency compared with traditional sync-parallel algorithms.

A Derivation of certain updates

This appendix derives update formulas used by ARock from convex-analytic and proximal-operator relationships. It also shows how coordinate-specific quantities reduce the computation required for updates.

  • Updates in (16): The appendix derives updates in (16) from the relevant formulation, including a consensus constraint represented through a function g.
  • Coordinate implementation: Because only coordinate i_k is updated, the implementation needs only the corresponding cached quantities rather than the full vectors.
  • Dual derivation: The Lagrangian and convex conjugate transform yield the dual problem corresponding to the formulation in (18).
  • Proximal derivation: A proximal-operator identity obtains z+ = prox_γ·d_g(z) from the auxiliary minimization, with the analogous formula for f obtained by substitution.
  • Final update: The final update formula (21) follows by substituting the derived expressions into the general scheme (15).

B Derivation of async-parallel ADMM for decentralized optimization

This appendix derives async-parallel ADMM updates for decentralized optimization on a network. Edge activations involve neighboring agents, allow overlap under delay, and reduce to an existing algorithm when overlap is absent.

  • Model structure: For the decentralized model, g(y) and b vanish, while constraints x_i = y_ij and x_j = y_ij determine the relevant matrix rows.
  • Model structure: The coefficients 1 correspond to x_i and x_j, while coefficients −1 correspond to y_ij in the constraint matrix.
  • ADMM updates: The variables and dual quantities are updated through equations (28a)–(28c), with z_i obtained from (28a) and auxiliary variables updated from (28b) and (28c).
  • Edge activation: When an edge (i, j) is activated, agents i and j compute local read values before collaboratively updating their associated variables.
  • Asynchrony: Adjacent edges may activate with overlapping updates; when τ = 0, the method reduces to the algorithm in [56].
Loading 1506.02396v5…