PaperlayerView exact revision on arXiv

Source-linked AI summary

High-Performance Distributed ML at Scale through Parameter Server Consistency Models

Wei Dai, Abhimanu Kumar, Jinliang Wei, Qirong Ho, Garth Gibson, Eric P. Xing

arXiv:1410.8043v1cs.LGstat.ML

TL;DR

Distributed ML's parameter-server setting must balance theoretical behavior against communication feasibility: VAP offers value-bounded asynchronous behavior but can demand communication comparable to strong consistency. The paper analyzes VAP and ESSP and proposes ESSP; experiments report higher throughput than SSP and improved convergence speed and quality for two ML algorithms.

Abstract

from arXiv · show

As Machine Learning (ML) applications increase in data size and model complexity, practitioners turn to distributed clusters to satisfy the increased computational and memory demands. Unfortunately, effective use of clusters for ML requires considerable expertise in writing distributed code, while highly-abstracted frameworks like Hadoop have not, in practice, approached the performance seen in specialized ML implementations. The recent Parameter Server (PS) paradigm is a middle ground between these extremes, allowing easy conversion of single-machine parallel ML applications into distributed ones, while maintaining high throughput through relaxed "consistency models" that allow inconsistent parameter reads. However, due to insufficient theoretical study, it is not clear which of these consistency models can really ensure correct ML algorithm output; at the same time, there remain many theoretically-motivated but undiscovered opportunities to maximize computational throughput. Motivated by this challenge, we study both the theoretical guarantees and empirical behavior of iterative-convergent ML algorithms in existing PS consistency models. We then use the gleaned insights to improve a consistency model using an "eager" PS communication mechanism, and implement it as a new PS system that enables ML algorithms to reach their solution more quickly.

Introduction

Distributed ML addresses data and model demands that exceed a single machine, while parameter servers offer a simpler way to share models across workers. The paper studies how relaxed consistency affects convergence and uses those insights to design a faster consistency model and system.

Introduction

  • Parameter servers let workers train a shared model on partitioned data to address ML workloads that exceed a single machine’s computation and memory.The distributed shared-memory interface can simplify programming by letting workers access model parameters through a cluster-wide memory pool.Source: Introduction · p. 1
  • Relaxed consistency trades parameter-read accuracy for throughput, relying on ML algorithms’ error tolerance and iterative convergence.The paper notes that parameter dependencies can also make parallelization difficult.Source: Introduction · p. 2
  • The paper targets limited understanding of how relaxed consistency affects convergence and stability, and of how to improve algorithm progress and system throughput.It contrasts its ML-theoretic analysis with prior work focused on system heuristics.Source: Introduction · p. 2
  • VAP provides a theoretical target, while ESSP matches its guarantees and is implemented to reduce average staleness and improve convergence over SSP.The paper develops variance bounds for VAP and ESSP and reports ESSP gains in real time and per iteration.Source: Introduction · p. 2

Consistency Models for Parameter Servers

Relaxed parameter consistency can reduce synchronization for iterative-convergent ML, but its inconsistency must be controlled. VAP bounds value deviation but is difficult to implement efficiently; ESSP uses eager communication within SSP to reduce observed staleness and improve convergence.

Consistency Models for Parameter Servers

  • Consistency models trade read accuracy for throughput; controlling inconsistent reads can preserve convergence to local optima while reducing synchronization.The passage frames inconsistent reads as errors in the algorithmic procedure, whose effects can be tolerated when inconsistency is controlled.Source: Consistency Models for Parameter Servers · p. 2

The ideal but inefficient Value-bounded Asynchronous Parallel (VAP) model

  • VAP bounds the magnitude of the difference between strongly consistent values and worker views, requiring aggregated in-transit updates to stay below a specified threshold.The condition is checked whenever a worker computes using model variables.Source: The ideal but inefficient… · p. 3
  • VAP is difficult to implement efficiently because checking its value bound generally requires communication comparable to strong consistency.The bound must hold before computation, and a worker needs information about other workers’ in-transit updates.Source: The ideal but inefficient… · p. 3

Eager Stale Synchronous Parallel (ESSP)

  • ESSP eagerly propagates updates to reduce empirical staleness beyond what SSP requires, without adding guarantees beyond SSP.In matrix factorization, ESSP’s eager cache updates reduce the negative tail of clock differentials compared with SSP; Figure 1’s left panel shows the observed staleness distributions.Source: Eager Stale Synchronous Parallel (ESSP) · pp. 3–4, Figure 1 · p. 4
  • ESSP combines theoretical properties comparable to VAP with efficient implementation, and reports higher throughput than SSP through aggressive scheduling.Its performance is evaluated on matrix completion using SGD and topic modeling using sampling.Source: Eager Stale Synchronous Parallel (ESSP) · p. 4

Theoretical Analysis

The analysis establishes SGD convergence guarantees under VAP and SSP, then compares their variance behavior and sensitivity to staleness. It finds that (E)SSP depends more weakly on its staleness threshold than VAP does on its value bound.

SGD for Low Rank Matrix Factorization

  • Under VAP, the worker’s noisy view converges to the global optimum in expectation at O(T^-1/2).The guarantee uses a real-time update sequence as its reference and assumes suitable conditions, including Lipschitz components and bounded diameter.Source: SGD for Low Rank Matrix Factorization · p. 5
  • Under VAP, variance decreases over successive iterations when δt is sufficiently small, controlled by the VAP threshold.The authors note that enforcing VAP requires synchronization comparable to strong consistency, limiting its practical benefit.Source: SGD for Low Rank Matrix Factorization · p. 6
  • Under SSP, SGD has an O(T^-1/2) convergence bound in probability with an exponential tail bound.The result assumes convex components, Lipschitz conditions, bounded divergence, and fixed staleness s.Source: SGD for Low Rank Matrix Factorization · p. 7
  • Near an optimum, SSP’s SGD variance decreases monotonically when the stated staleness assumptions hold.The analysis uses a nonnegative covariance term and assumes bounded staleness-related quantities.Source: SGD for Low Rank Matrix Factorization · pp. 7–8

Comparison of VAP and ESSP

  • Both VAP and (E)SSP achieve decreasing variance, but VAP is more sensitive to its value-bound threshold than (E)SSP is to staleness.For (E)SSP, staleness appears in high-order variance terms; the analysis attributes its weaker dependency to SGD’s decreasing step size.Source: Comparison of VAP and ESSP · p. 8
  • VAP’s reliability requires lowering its value threshold, while (E)SSP’s bounded staleness generally avoids gradual threshold reduction.The paper notes that lowering VAP’s threshold increases communication, whereas ESSP proactively pushes fresh values and usually produces near-zero-staleness reads.Source: Comparison of VAP and ESSP · p. 8

ESSPTable: An efficient ESSP System

ESSPTable implements ESSP through a key-value interface, local parameter caches, and server-pushed updates. Its callback and batching mechanisms reduce read-request traffic and empirical staleness.

ESSPTable: An efficient ESSP System

  • Computation threads use GET and INC through a key-value interface, and CLOCK advances each worker’s clock.A read at clock c is guaranteed to include updates generated in clocks [0, c − s − 1].Source: ESSPTable: An efficient ESSP System · p. 9
  • The client library caches accessed parameters and returns a cached value only when its clock satisfies the SSP staleness condition.Cold parameters may be evicted using an approximate LRU policy.Source: ESSPTable: An efficient ESSP System · p. 9
  • ESSPTable uses server callbacks to push updated table rows to registered clients, instead of waiting for each client read request.A client registers a callback on its first row request; later server clock advances trigger pushes to registered clients.Source: ESSPTable: An efficient ESSP System · p. 9
  • Communication for coalesced updates usually takes less time than computation, so observed staleness is usually 1 regardless of the configured threshold.Batched server pushes also reduce latency compared with sending each parameter separately in response to client requests.Source: ESSPTable: An efficient ESSP System · p. 9

Experiments

The experiments compare ESSP with SSP on topic modeling and matrix factorization, finding faster or comparable convergence alongside greater robustness to staleness. ESSP also offers communication-pipelining opportunities that contribute to convergence per second.

Speed of Convergence

  • ESSP improves convergence speed and quality over SSP for LDA collapsed Gibbs sampling and matrix-factorization SGD, converging faster or comparably per iteration and per second.LDA uses 50% minibatches and log-likelihood; MF uses 1% and 10% minibatches and squared loss.Source: Experiments · pp. 9–10

Experimental Setup

  • The benchmarks use LDA on the New York Times dataset and MF on Netflix, with experiments run on separate clusters for the two tasks.LDA uses 8 nodes; MF uses 64 nodes.Source: Experiments · pp. 9–10

Robustness to Staleness

  • Across investigated staleness settings, ESSP produces lower variance and remains robust, while high staleness makes SSP diverge on MF.This reduces the need to tune SSP’s staleness parameter.Source: Experiments · p. 10

System Opportunity

  • Preemptively sending updates reduces staleness and client blocking, creating communication-pipelining opportunities that contribute to ESSP’s larger convergence-per-second gain.The comparison of convergence per second is reported alongside convergence per iteration.Source: Experiments · p. 10

Related Work and Discussion

The discussion distinguishes programmable general-purpose ML frameworks from application-specific solvers and explains the paper’s focus on consistency and systems code. It also notes limits of prior PS implementations and the consistency–portability trade-off in general-purpose big-data frameworks.

Related Work

  • General-purpose frameworks such as GraphLab and Parameter Servers are programmable, unlike special-purpose solvers such as CCD++ [18] and Yahoo LDA.General-purpose systems focus on communication and synchronization, while special-purpose systems can combine systems and algorithmic improvements.Source: Related Work and Discussion · p. 10

Discussion

  • Figure 2 covers convergence speed per iteration and per second for LDA and matrix factorization.Source: Figure 2 · p. 11
  • The paper uses relatively simple benchmark algorithms to match other frameworks’ update equations and avoid relying on application-specific techniques.The authors note these benchmarks are unlikely to beat special-purpose solvers in running time, though their algorithmic techniques may also apply to PS programs.Source: Related Work and Discussion · p. 11

Related Work

  • The cited model in has VAP-like theoretical guarantees, but its implementation assumes zero network latency and may read highly inconsistent parameters during congestion.Its reads do not wait for delayed updates.Source: Related Work and Discussion · p. 11
  • Hadoop and Spark provide portability, reliability, and fault tolerance, but support strict rather than flexible consistency; the authors know of no recent evidence that they outperform ML-focused frameworks.Source: Related Work and Discussion · p. 11

Appendix

The appendix states convergence results for SGD under VAP and SSP, including expectation, probability, and variance claims. Its local analysis assumes suitable regularity conditions and, for the decreasing-variance result, a bounded invertible Hessian near the optimum.

VAP Results

  • Under suitable conditions, Theorem 1 states convergence in expectation for SGD under VAP.The setup assumes convex component functions, Lipschitz components, bounded divergence, and a decreasing VAP bound.Source: Appendix · p. 13

SSP Results

  • Under suitable conditions, Theorem 5 states convergence in probability for SGD under SSP with staleness s and P workers.Its setup assumes convex component functions, Lipschitz components, and bounded divergence.Source: Appendix · p. 15
  • Theorem 6 gives a decreasing-variance result for SGD under SSP near the optimum, assuming a bounded invertible Hessian and bounded γ_t.The local analysis uses the Hessian at the optimum and treats higher-order terms separately.Source: Appendix · pp. 16–17

VAP Results

  • Theorem 2 gives a bounded-variance result for SGD under VAP, assuming a bounded, invertible Hessian at the optimum.The appendix identifies the VAP variance quantity and gradient at the noisy iterate.Source: Appendix · p. 19
Loading 1410.8043v1…