PaperlayerView exact revision on arXiv

Source-linked AI summary

Perturbed Iterate Analysis for Asynchronous Stochastic Optimization

Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, Michael I. Jordan

arXiv:1507.06970v2stat.MLcs.DCcs.DScs.LGmath.OC

TL;DR

The paper addresses the difficulty of analyzing asynchronous stochastic optimization under realistic, unsynchronized execution. It models asynchrony as bounded perturbations of stochastic iterates, analyzes Hogwild!, ASCD, and sparse SVRG, and reports nearly-linear speedups with sparse parallel SVRG sometimes more than four orders of magnitude faster than standard SVRG.

  • Problem

    Existing asynchronous stochastic-optimization analyses are difficult, rely on simplifying assumptions, and often study algorithms simpler than those used in practice.

  • Method

    The paper models asynchronous algorithms as serial stochastic methods operating on inputs perturbed by bounded noise, then applies the framework to Hogwild!, ASCD, and KroMagnon sparse SVRG.

  • Results

    The framework yields simpler analyses with relaxed assumptions and improved bounds in some cases, while asynchronous parallel sparse SVRG achieves nearly-linear speedups and is sometimes four orders of magnitude faster than standard SVRG.

  • Takeaways & Limitations

    The framework provides elementary convergence analyses for asynchronous first-order methods without assuming consistent reads and supports full stochastic-gradient updates.

  • Takeaways & Limitations

    The authors identify open needs for tighter function-value bounds and convergence analyses using coordinate-wise Lipschitz constants.

Abstract

from arXiv · show

We introduce and analyze stochastic optimization methods where the input to each gradient update is perturbed by bounded noise. We show that this framework forms the basis of a unified approach to analyze asynchronous implementations of stochastic optimization algorithms.In this framework, asynchronous stochastic optimization algorithms can be thought of as serial methods operating on noisy inputs. Using our perturbed iterate framework, we provide new analyses of the Hogwild! algorithm and asynchronous stochastic coordinate descent, that are simpler than earlier analyses, remove many assumptions of previous models, and in some cases yield improved upper bounds on the convergence rates. We proceed to apply our framework to develop and analyze KroMagnon: a novel, parallel, sparse stochastic variance-reduced gradient (SVRG) algorithm. We demonstrate experimentally on a 16-core machine that the sparse and parallel version of SVRG is in some cases more than four orders of magnitude faster than the standard SVRG algorithm.

1 Introduction

Asynchronous stochastic optimization can achieve strong practical speedups but is difficult to analyze with realistic execution behavior. The paper introduces a unified perturbed-iterate framework and applies it to several asynchronous algorithms.

  • Asynchronous lock-free stochastic methods have demonstrated near-linear speedups on common machine-learning tasks, including non-convex settings without statistical-accuracy loss.
  • Existing analyses require lengthy derivations and assumptions that may not reflect realistic systems, often simplifying the algorithms being run.
  • The framework models asynchrony as bounded noise perturbing stochastic iterates, allowing asynchronous algorithms to be analyzed as serial methods on noisy inputs.
  • The authors analyze Hogwild!, asynchronous stochastic coordinate descent, and KroMagnon, a sparse asynchronous SVRG method.
  • On a 16-core machine, asynchronous parallel sparse SVRG achieves nearly-linear speedups and is sometimes four orders of magnitude faster than dense SVRG.

2 Perturbed Stochastic Gradients

The perturbed-iterate analysis represents asynchronous stochastic updates as serial stochastic iterations evaluated at noisy inputs. A recursive error decomposition then supports elementary convergence analyses under smoothness, strong convexity, and independence conditions.

  • The framework studies asynchronous iterative algorithms for minimizing convex L-smooth, m-strongly convex functions over shared-memory variables.
  • First-order stochastic methods use unbiased noisy gradient estimates, whose lower computational cost motivates replacing true gradients with stochastic updates.
  • Asynchrony breaks the ordinary iterate model because processors read stale or inconsistent shared-memory variables without a global synchronization clock.
  • The perturbed variant treats the read input as a noisy estimate, separating the update recursion into stochastic-gradient decay, iterate mismatch, and mismatch-gradient projection errors.
  • Independence between the noisy iterate and the sampled randomness enables the expectation step connecting stochastic gradients to the true gradient at the noisy iterate.
  • Bounding the recursion’s error terms yields O(log(1/ε)/ε) convergence for Hogwild! and linear convergence for asynchronous SCD and sparse SVRG.

3 Analyzing Hogwild!

The Hogwild! analysis models sparse shared-memory updates through sampled hyperedges, inconsistent reads, and conflict structure. Sampling-time ordering preserves uniformity and enables convergence guarantees for the full-update algorithm under bounded delays and gradient assumptions.

  • Each hyperedge identifies the coordinates used by a function term, while the induced conflict graph records term pairs sharing at least one coordinate.
  • The convergence recursion depends on conflict degree, overlap delays, and bounded stochastic gradients, with system randomness representing delays, overlaps, and computation times.
  • Hogwild! samples a hyperedge uniformly, reads its coordinates, computes the corresponding stochastic gradient, and adds the update without synchronization or locks.
  • Unlike prior analyses, this work handles full hyperedge updates, inconsistent reads, and arbitrary processing-time distributions.
  • Ordering samples by sampling time preserves uniformity, whereas completion-time ordering can bias the conditional sample distribution toward smaller hyperedges.
  • The analysis defines noisy iterates from the coordinates actually read and does not assume consistent reads while those coordinates are being collected.
  • When overlap satisfies the theorem’s bound, Hogwild! matches serial SGM’s iteration bound up to constants, implying linear speedup; the delay bound can be nearly linear in the number of terms.
  • The resulting delay bound can be orders of magnitude better than an earlier bound based on maximum conflict degree.

4 Asynchronous Stochastic Coordinate Descent

The paper analyzes asynchronous stochastic coordinate descent (ASCD) through perturbed iterates, relating asynchronous updates to serial coordinate descent while bounding errors from stale reads. Under stated concurrency and smoothness conditions, ASCD achieves linear convergence and a corresponding linear speedup.

  • Algorithm and framework: The perturbed-iterate analysis treats ASCD as a serial method operating on noisy inputs and tracks mismatch, gradient-step, and related error terms.The framework introduces recursive bounds for these errors to connect asynchronous iterates with the serial recursion.
  • Algorithm and framework: ASCD samples coordinates uniformly, computes a coordinate gradient update using a possibly stale read, and atomically updates one shared-memory coordinate.Its iterate is written as xj+1 = xj −γ · d · [∇f(ˆxj)]sj esj = xj −γ · g(ˆxj, sj).
  • Convergence result: The required step size and concurrency bounds depend on smoothness, strong convexity, dimension, and condition number, with the more restrictive τ bound left potentially loose.The paper states that the tightness of the bound remains an open question and remarks that sparsity might improve the τ^2 factor to τ in some regimes.
  • Convergence result: Theorem 5 establishes linear convergence when the concurrency proxy τ satisfies the stated condition, allowing ASCD to match serial SCD accuracy in the same number of steps.The paper concludes that this condition implies a linear speedup relative to the simple convergence bound, while noting that refined coordinate-descent analyses may yield better function-value bounds.
  • Error control: The analysis bounds stale-read discrepancies by coordinate updates occurring within index windows of at most 2rτ + 1 nearby iterations.The set around j contains indices within rτ steps, and the discrepancy between a fake iterate and a read value is expressed through updates in that interval.

5 Sparse and Asynchronous SVRG

This section develops sparse SVRG and its asynchronous implementation, KroMagnon, using a variance bound and perturbed-iterate analysis to obtain linear convergence guarantees.

  • 5.1 Serial Sparse SVRG: Sparse SVRG restricts each update to the support of g(y, s_j), avoiding dense updates that increase shared-memory costs and asynchronous conflicts.The update is normalized with D_sj so its expectation remains the full gradient.
  • 5.1 Serial Sparse SVRG: The sparse SVRG gradient estimator has the same convergence-rate upper bound as dense SVRG because a non-negative quadratic term can be discarded.The variance analysis therefore transfers the dense-SVRG rate bound to the sparse method.
  • 5.1 Serial Sparse SVRG: With epoch length 8κ^2, the expected squared distance contracts by a factor of 0.75 per epoch.The stated contraction is E∥y_k − x*∥^2 ≤ 0.75^k · E∥y_0 − x*∥^2.
  • 5.1 Serial Sparse SVRG: Serial sparse SVRG reaches accuracy ǫ after O(log(a_0/ǫ)) epochs using step size O(1)/(Lκ) and epoch size O(1)κ^2.Here a_0 is the initial squared distance to the optimum.
  • 5.2 KroMagnon: Asynchronous Parallel Sparse SVRG: KroMagnon asynchronously applies sparse SVRG updates to inconsistent reads and analyzes them as perturbed iterates with unbiased gradient recursion.Its convergence proof generalizes the ASCD analysis and controls errors from overlapping updates.
  • 5.2 KroMagnon: Asynchronous Parallel Sparse SVRG: KroMagnon attains the same asymptotic iteration bound as serial sparse SVRG, implying a linear speedup under the stated overlap conditions.The analysis uses an overlap parameter τ and notes that its second bound is more restrictive; the authors also state that this bound is loose and may be tightened.

6 Empirical Evaluation of KroMagnon

The experiments compare KroMagnon with dense SVRG and Hogwild! on sparse machine-learning tasks using up to 16 threads, finding major speed advantages over dense SVRG and comparable speedup scaling to Hogwild!.

  • Experimental setup: On three sparse tasks, the evaluation compares KroMagnon, dense SVRG, and Hogwild! using up to 16 threads over 50 epochs.The tasks include linear regression, logistic regression, and vertex cover.
  • Comparison with dense SVRG: KroMagnon is one-two orders of magnitude faster than dense SVRG, while both methods attain similar optima.Dense SVRG could not run on the url and eswiki-2013 datasets because of their large numbers of features.
  • Comparison with dense SVRG: On 16 threads, KroMagnon can be up to four orders of magnitude faster than serial dense SVRG and can outperform dense SVRG running on a single thread.This comparison concerns runtime to comparable objective values.
  • Speedups: KroMagnon has speedups comparable to Hogwild! across all evaluated datasets, whereas dense SVRG shows better speedup scaling.Speedups were measured relative to each algorithm’s single-thread runtime at 99.9% and 99.99% of its minimum achieved objective.

7 Conclusions and Open Problems

The paper presents a perturbed-iterate framework for asynchronous stochastic optimization and applies it to Hogwild!, ASCD, and KroMagnon. Experiments report strong comparative performance, while the conclusion identifies unresolved limits involving convexity, sparsity, bounds, and algorithmic scope.

  • The framework uses elementary analyses, relaxes assumptions such as consistent reads, and analyzes full stochastic gradient updates.
  • KroMagnon is significantly faster than parallel and dense SVRG on synthetic linear and logistic regression, while both achieve better objective values than constant-step-size Hogwild!.
  • The analyses leave open tighter convergence bounds, improved upper bounds on τ, applicability beyond sparse settings, and extensions to more stochastic gradient methods.
  • The framework fundamentally relies on strong convexity, leaving its extension to simply convex, smooth, or nonconvex objectives open.
  • KroMagnon on a single thread is 3-4 orders of magnitude faster than dense SVRG on wordassociation-2011, while dense SVRG could not run on eswiki-2013.
  • The perturbed-iterate viewpoint may apply beyond stochastic optimization, including asynchronous graph clustering and other iterative algorithms.

A Removing the Independence Assumption

This appendix section removes the independence assumption used in the main Hogwild! analysis by imposing smoothness conditions and reworking the expectation bounds. It obtains a convergence result with a narrower allowable range of overlap τ.

  • The analysis lifts the independence assumption between the read variable and sampled data when each function term is sufficiently smooth.
  • The revised derivation uses strong convexity, smoothness, and a recursion for the sequence a_j to bound asynchrony error terms.
  • The resulting Hogwild! theorem reaches E∥x_k − x*∥^2 ≤ ε after T ≥ O(1)M^2 log(a_0/ε) iterations under a bounded-overlap condition on τ.
  • Compared with the main result, the revised analysis guarantees speedup for a smaller range of τ, with analogous ideas potentially applicable to ASCD and KroMagnon.

B Omitted Proofs

The omitted proofs bound recursive error quantities by repeatedly substituting inequalities and controlling sparsity- and asynchrony-dependent terms. The resulting estimates combine into bounds used in the convergence analysis.

  • The proof rewrites bounds on G_r and Δ_r as a recursive inequality involving A, B, C, and G_{r+1}.
  • Repeatedly applying the recursive inequality ℓ times yields an expansion for bounding R_j.
  • Choosing τ so the relevant sum is small bounds BC through θ^2 and controls the resulting series terms.
  • The proof combines the bounds on R_j^0, R_j^1, and R_j^2 to control the total error contribution.
  • Factorial and terminal-term bounds imply G_1 = O(1)(dL^2a_j + θ^{2ℓ}dM^2), which contributes to the bound on R_j.

B.1.2 Bounding Rj

The proof exploits update sparsity by rewinding to an iterate independent of the sampled coordinates, then uses smoothness and expectation bounds to control correlated gradient terms. The authors note that the resulting τ bound may be improvable.

  • The indicator 1(s_i = s_j) encodes gradient-step sparsity and is separated from inner products using an earlier iterate independent of s_i and s_j.
  • Smoothness bounds the mismatch between the rewound iterate and the asynchronous iterates appearing in the gradient products.
  • Cauchy-Schwarz and iterated expectations bound terms containing gradient norms and the sparsity indicator.
  • The proof uses dLγ ≤ θ and κ ≥ 1 to simplify polynomial factors in τ.
  • The authors believe the restrictive upper bound on τ can be significantly improved.

B.2.1 Bounding Rj

This section bounds the KroMagnon error terms Rj 0 and Rj 1 using rewritten inequalities, gradient-step assumptions, and parameter choices involving γ and τ.

  • B.2.1 Bounding Rj: The KroMagnon error terms Rj 0 and Rj 1 satisfy upper-bound inequalities derived from the preceding analysis.
  • B.2.1 Bounding Rj: γ is chosen proportional to the serial SVRG step-size, while the assumption on τ makes the relevant sum significantly small.
  • B.2.1 Bounding Rj: The analysis assumes a uniform upper bound M > 0 on the expected squared size of gradient steps.
  • B.2.1 Bounding Rj: The derivation concludes by applying analogous bounds to obtain the stated result.

B.2.2 Bounding Rj

This section bounds another KroMagnon error term using gradient-step sparsity, smoothness, and delayed-iterate substitutions, then notes that the resulting τ restriction may be improved.

  • B.2.2 Bounding Rj: The random variable 1(si ∩sj ≠ ∅) encodes whether gradient steps overlap in their sparsity patterns.
  • B.2.2 Bounding Rj: The proof replaces delayed iterates with ˆxj−3τ, uses x0 when j < 3τ, and applies L-smoothness to bound the resulting terms.
  • B.2.2 Bounding Rj: The expectation of the product of gradient-step norms and the overlap indicator is upper bounded within the proof.
  • B.2.2 Bounding Rj: The conclusion follows under a condition stated as τ = O(...), while the remark identifies the bound on τ as restrictive.
  • B.2.2 Bounding Rj: Using the same bounding technique on Rj 0 and Rj 1 should significantly improve KroMagnon’s restrictive τ bound.
Loading 1507.06970v2…