PaperlayerView exact revision on arXiv

Source-linked AI summary

An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization

Hamid Reza Feyzmahdavian, Arda Aytekin, Mikael Johansson

arXiv:1505.04824v1math.OCcs.SYeess.SYstat.ML

TL;DR

The paper considers stochastic optimization methods whose gradient computations are inherently serial. It proposes asynchronous mini-batch optimization for smooth-loss problems and reports O(1/T) convergence for strongly convex regularization, with an asymptotically negligible asynchrony penalty and expected near-linear speedup.

  • Problem

    The described stochastic optimization methods compute gradients on a single processor with access to the whole dataset.

    Source: §I · p. 2

  • Method

    The paper proposes an asynchronous mini-batch algorithm for regularized stochastic optimization with smooth loss functions.

    Source: §VI · p. 13

  • Results

    For strongly convex regularization on closed and convex constraint sets, the algorithm achieves O(1/T), and its convergence-rate penalty from asynchrony is asymptotically negligible.

    Source: §VI · p. 13

  • Takeaways & Limitations

    The authors conclude that near-linear speedup in the number of processors can be expected.

    Source: §VI · p. 13

Abstract

from arXiv · show

Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art parallel mini-batch algorithms assume synchronous operation or cyclic update orders. When worker nodes are heterogeneous (due to different computational capabilities or different communication delays), synchronous and cyclic operations are inefficient since they will leave workers idle waiting for the slower nodes to complete their computations. In this paper, we propose an asynchronous mini-batch algorithm for regularized stochastic optimization problems with smooth loss functions that eliminates idle waiting and allows workers to run at their maximal update rates. We show that by suitably choosing the step-size values, the algorithm achieves a rate of the order $O(1/\sqrt{T})$ for general convex regularization functions, and the rate $O(1/T)$ for strongly convex regularization functions, where $T$ is the number of iterations. In both cases, the impact of asynchrony on the convergence rate of our algorithm is asymptotically negligible, and a near-linear speedup in the number of workers can be expected. Theoretical results are confirmed in real implementations on a distributed computing infrastructure.

I. INTRODUCTION

The paper proposes asynchronous mini-batch optimization for smooth-loss regularized stochastic problems, avoiding global synchronization while allowing workers to compute independently. It extends prior asynchronous results to general regularization functions and establishes convergence guarantees under several conditions.

  • Dekel et al.’s parallel mini-batch method synchronizes every round, so a failed or slower processor can set the pace for the entire algorithm.Source: §I · p. 2
  • The asynchronous mini-batch algorithm removes global synchronization overhead and lets processors compute independently at different rates, updating shared variables with out-of-date gradients.Source: §I · p. 2
  • The analysis extends Agarwal and Duchi’s asynchronous results, which considered only indicator regularizers for compact convex sets, to general regularization functions such as l1.Source: §I · p. 2
  • With constant step sizes and general convex regularization on a closed convex constraint set, the running average converges at O(1/T) to a ball around the optimum.The residual error and convergence depend on loss properties, step size, batch size, and maximum delay.Source: §I · p. 2
  • For general convex regularization on compact constraint sets, a time-varying step size makes the running average converge to the true optimum, with near-linear speedup for O(T^1/4) processors.Source: §I · pp. 2–3
  • For strongly convex regularization on closed convex constraint sets, the iterates achieve O(1/T) when the processor count is O(T^1/4), matching the best known serial rate.Source: §I · p. 3

II. NOTATION AND PRELIMINARIES

The section introduces notation and mirror-descent preliminaries, then sets up stochastic convex optimization with an unknown data distribution and stochastic-oracle access.

A. Notation

  • The notation defines natural-number conventions and vector inner-product and norm notation, including the corresponding dual norm.The preliminaries also define subgradients and subdifferentials for convex functions.Source: A. Notation · p. 3, B. Preliminaries · p. 4

B. Preliminaries

  • Distance-generating functions are strongly convex and induce Bregman distances, which can adapt optimization geometry to the feasible set.The paper motivates generalized distance functions as an alternative to ordinary Euclidean distance.Source: B. Preliminaries · pp. 3–4

III. PROBLEM SETUP

  • The objective is a stochastic composite convex problem with a simple convex regularizer, and the distribution is accessed through an oracle returning sampled gradients.The setup assumes an attained minimum, Lipschitz-continuous sample gradients, bounded gradient variance, and a closed effective domain for the regularizer.Source: §III · pp. 4–5
  • A serial mini-batch mirror-descent method provides a reference approach, but large datasets motivate execution across multiple processors.The serial method samples a batch, averages stochastic gradients, and applies a composite mirror-descent update.Source: §III · p. 6

IV. AN ASYNCHRONOUS MINI-BATCH ALGORITHM

The paper presents an asynchronous mini-batch algorithm for the stochastic optimization problem and analyzes its iteration complexity and convergence rate.

IV. AN ASYNCHRONOUS MINI-BATCH ALGORITHM

  • The proposed asynchronous mini-batch algorithm uses multiple processors to solve the stochastic optimization problem, with iteration complexity and convergence rate compared favorably to the state of the art.The section introduces the algorithm and characterizes its convergence properties.Source: §IV · p. 6

A. Description of Algorithm

Algorithm 1 lets processors run independently, compute mini-batch gradients from locally read iterates, and update the shared decision variable without synchronization.

A. Description of Algorithm

  • Each process reads x, samples a batch, computes an averaged stochastic gradient, and updates the current x in shared memory.The algorithm repeats these steps until its termination test is satisfied.Source: A. Description of Algorithm · pp. 6, 8
  • The algorithm supports shared-memory and master-worker implementations, with the master-worker arrangement assigning the minimization step to the master.In shared memory, processors read and write global x; in master-worker, workers return averaged gradients to the master.Source: A. Description of Algorithm · p. 7
  • Processors need not wait for one another’s gradient computations and may apply gradients evaluated at stale iterates to the current decision variable.Their work rates may differ, and the gradient’s read-time iterate can differ from the iterate receiving the update.Source: A. Description of Algorithm · pp. 7–8
  • The delay between reading an iterate and using its gradient is bounded, and cyclic-delay mini-batch updates are a special case of Algorithm 1.The paper defines delay as a measure of gradient staleness and identifies the cyclic case by a fixed delay of p − 1.Source: A. Description of Algorithm · p. 8

B. Convergence Rate for General Convex Regularization

For general convex regularization, the analysis gives convergence guarantees for constant and time-varying step sizes and bounds how delays affect iteration complexity.

B. Convergence Rate for General Convex Regularization

  • O(1/T) convergence in expectation to a ball around the optimum holds for the running average under a constant step size satisfying the stated bound.Theorem 1 establishes the constant-step-size result under Assumptions 1–4.Source: B. Convergence Rate for General Convex… · pp. 8–9
  • When τmax is of order 1/√ε, the delay term is asymptotically negligible and iteration complexity is O(cσ²/bε²).The paper identifies this as the serial mini-batch algorithm’s iteration complexity.Source: B. Convergence Rate for General Convex… · p. 9
  • With p processors, updates occur roughly p times as quickly, so near-linear speedup can be expected when p is of order O(1/√ε).The stated condition is that parallelization does not appreciably degrade asymptotic convergence.Source: B. Convergence Rate for General Convex… · pp. 9–10
  • For compact dom Ψ, the time-varying step-size includes a delay-dependent term, and τmax = O(T^1/4) makes delay increasingly harmless as the algorithm progresses.The reported delay penalty is O(τmax²/T), which the text says is much smaller for large T.Source: B. Convergence Rate for General Convex… · pp. 10–11
  • The time-varying-step-size result extends delayed mirror descent to general regularization functions and gives a sharper guaranteed convergence rate than the cited prior result.The comparison is to Agarwal and Duchi.Source: B. Convergence Rate for General Convex… · p. 11

C. Convergence Rate for Strongly Convex Regularization

For strongly convex regularization, the paper analyzes Algorithm 1 with a time-varying step size under Assumptions 2–5. Its iterates converge at O(1/T), and delays as large as O(T^1/4) do not affect the asymptotic rate.

C. Convergence Rate for Strongly Convex Regularization

V. EXPERIMENTAL RESULTS

The distributed implementation shows near-linear relative speedup as worker count increases. The conclusions also report convergence guarantees for convex and strongly convex regularization, with asymptotically negligible asynchrony penalty.

V. EXPERIMENTAL RESULTS

  • The implementation evaluated Algorithm 1 on sports-document classification using the RCV1 dataset and l1-regularized logistic regression.The dataset contains approximately 800,000 documents and 50,000 unique stemmed tokens; the batch size was 1,000 documents.Source: §V · p. 12
  • Near-linear relative speedup was observed as the number of workers increased, consistent with the theoretical results.Timings were averaged over 10 Monte Carlo runs.Source: §V · p. 12, Figure 2 · p. 13

VI. CONCLUSIONS

  • For compact constraint sets, the running average with a time-varying step size converges to the optimum at O(1/√T).Source: §VI · p. 13
  • With strongly convex regularization, the algorithm achieves O(1/T), while the convergence-rate penalty from asynchrony is asymptotically negligible.The paper states that near-linear speedup in processor count can be expected.Source: §VI · p. 13

APPENDIX

The appendix develops an iterate recursion and bounds its accumulated error using convexity, smoothness, and delay assumptions. These bounds feed into the convergence lemmas for Algorithm 1.

APPENDIX

  • Lemma 1 establishes a recursion satisfied by the iterates generated by Algorithm 1 under Assumptions 1–4.Source: APPENDIX · p. 13
  • The proof bounds objective error using convexity and the L-Lipschitz continuity of ∇f, then rewrites the bound in terms of gradient-estimation error.The argument also bounds delay-related terms using τ(k) ≤ τmax.Source: APPENDIX · pp. 15–16
  • Lemma 2 sums the iterate relations across T steps to produce an aggregate bound for positive step sizes.Source: APPENDIX · pp. 16–17
  • Lemma 3 bounds the norm of a sum of independent, identically distributed mean-zero random vectors under a strongly convex distance-generating function.Source: APPENDIX · p. 18

A. Proof of Theorem 1

The proof of Theorem 1 applies the iterate bound with a selected step-size parameter, then takes expectations using independence and Assumption 3. Substituting η = γ^−1 − L(τmax + 1)^2 completes the argument.

A. Proof of Theorem 1

  • The proof applies Lemma 2 with fixed γ and η, then substitutes η = γ^−1 − L(τmax + 1)^2 to prove the theorem.Source: A. Proof of Theorem 1 · pp. 18–19
  • Each iterate depends on past stochastic samples but not on the current samples, enabling expectation-based use of the stochastic gradient relation.Source: A. Proof of Theorem 1 · p. 18
  • The proof uses independence across workers’ samples and Assumption 3 when taking expectations.Source: A. Proof of Theorem 1 · p. 19

B. Proof of Theorem 2

The proof of Theorem 2 chooses a step size using the delay bound and a sequence α(k). It combines a lemma-based expectation argument with an integral estimate to obtain the claimed bound.

B. Proof of Theorem 2

  • The step size is chosen so that γ(k)^−1 = L(τmax + 1)^2 + α(k).The proof also uses that γ(k) is non-increasing and Dω(x, y) ≤ R^2 for x, y in dom Ψ.Source: B. Proof of Theorem 2 · p. 19
  • Applying Lemma 2 with μΨ = 0 and η(k) = α(k), then taking expectation and using Lemma 3, follows the proof of Theorem 1.Source: B. Proof of Theorem 2 · p. 19
  • The proof lower-estimates an integral using y(t) = 1/√t + 1 and substitutes the resulting inequality into bound (16).The text states that this yields the claimed guaranteed bound.Source: B. Proof of Theorem 2 · p. 19

C. Proof of Theorem 3

The proof of Theorem 3 uses a step size involving the delay bound and β(k), then combines inequalities, expectations, and a bound on β(T) to conclude.

C. Proof of Theorem 3

  • The step size is set so that γ(k)^−1 = 2L(τmax + 1)^2 + β(k).Source: C. Proof of Theorem 3 · p. 20
  • The proof notes that γ(k) is non-increasing, applies Lemma 1 under Assumption 5, and later multiplies both sides of a relation by 1/γ(k) before using (19).Source: C. Proof of Theorem 3 · pp. 20–21
  • Summing the inequality over k = 0 to T − 1 and bounding the third term on the right-hand side of (21) leads to an expectation bound.The proof substitutes the bound into (21) before taking expectations.Source: C. Proof of Theorem 3 · p. 21
  • 3Q ≤ β(T) ≤ 1/γ(T) is combined with bound (22) to conclude the proof.Source: C. Proof of Theorem 3 · p. 22

Related papers

Loading 1505.04824v1…