PaperlayerView exact revision on arXiv

Source-linked AI summary

Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms

Christopher De Sa, Ce Zhang, Kunle Olukotun, Christopher Ré

arXiv:1506.06438v2cs.LGmath.OCstat.ML

TL;DR

비동기 실행과 reduced precision은 stale update와 추가 noise를 통해 SGD 수렴 분석을 복잡하게 만든다. 이 논문은 통합 martingale 기반 framework를 개발하고 이를 convex, non-convex, low-precision 설정 전반에 적용한다. BUCKWILD!는 logistic regression에서 HOGWILD! 기반 알고리즘보다 최대 2.3× 빠른 속도 향상을 달성한다.

  • 문제

    비동기 SGD의 수렴 분석은 stale update가 race condition을 유발하기 때문에 어렵고, 특히 non-convex 문제에서 더 복잡하다.

  • 방법

    이 논문은 sampling, initialization, asynchronous delay를 통합된 noise로 모델링하는 martingale 기반 framework를 개발하고, 순차 수렴 증명을 비동기 알고리즘에 맞게 조정한다.

  • 결과

    이 framework는 완화된 sparsity 가정을 둔 convex HOGWILD!, 비동기 non-convex matrix completion, quantization error에 대한 수렴률을 도출하며, BUCKWILD!는 HOGWILD! 기반 logistic-regression 알고리즘보다 최대 2.3× 빠른 속도 향상을 달성한다.

  • 시사점 및 한계

    이 결과는 비동기 및 low-precision SGD 변형을 위한 공통 수렴 framework를 제공하며, BUCKWILD!는 순차 알고리즘 대비 near-linear parallel speedup을 달성한다.

  • 시사점 및 한계

    이 분석은 asynchronous delay가 서로 독립이라고 가정하는 대신, random variable에 의해 위에서 bounded 된다고 가정한다.

Abstract

from arXiv · show

Stochastic gradient descent (SGD) is a ubiquitous algorithm for a variety of machine learning problems. Researchers and industry have developed several techniques to optimize SGD's runtime performance, including asynchronous execution and reduced precision. Our main result is a martingale-based analysis that enables us to capture the rich noise models that may arise from such techniques. Specifically, we use our new analysis in three ways: (1) we derive convergence rates for the convex case (Hogwild!) with relaxed assumptions on the sparsity of the problem; (2) we analyze asynchronous SGD algorithms for non-convex matrix problems including matrix completion; and (3) we design and analyze an asynchronous SGD algorithm, called Buckwild!, that uses lower-precision arithmetic. We show experimentally that our algorithms run efficiently for a variety of problems on modern hardware.

1 서론

이 논문은 비동기 실행과 저정밀도를 SGD의 통합 분석에서 noise로 모델링하는 martingale 기반 framework를 제시한다. 이 framework를 완화된 sparsity를 가정하는 HOGWILD!, 비동기 non-convex matrix completion, 그리고 HOGWILD! 기반 logistic-regression 알고리즘보다 최대 2.3× 속도 향상을 달성하는 양자화 BUCKWILD!에 적용한다.

  • 동기: SGD는 널리 사용되는 machine-learning 알고리즘 으로, neural-network backpropagation, recommendation systems, optimization [20]을 비롯한 다양한 응용에 사용된다.특히 deep learning을 포함한 non-convex 문제에서 이론적으로 성공한 이유는 여전히 충분히 이해되지 않았다.
  • 동기: HOGWILD! [17]을 포함한 비동기 lock-free 실행은 여러 thread가 lock 없이 병렬로 update할 수 있게 해 SGD를 가속한다.관련 방법은 PageRank 근사 [16], deep learning, recommender systems 에도 적용되었다.
  • 통합 framework: martingale 기반 결과는 비동기성과 precision 변화를 서로 다른 noise 형태로 취급함으로써 다양한 확장을 하나로 통합한다.이에 따라 비동기성이나 precision의 각 유형마다 완전히 새로운 분석 모델을 요구하지 않아도 된다.
  • 응용: convex HOGWILD!의 경우, 이 분석은 엄격한 sparsity 가정을 완화하면서 convergence rate를 도출하고 HOGWILD!의 더 엄격한 가정하에서는 기존 rate를 회복한다.이 결과는 원래 조건에서 확립된 보장을 유지하면서 convex case를 다룬다.
  • 응용: 이 framework는 non-convex matrix completion에서 asynchronous SGD의 rate를 도출하고, De Sa et al. [4]의 synchronous 연구에 이어 이러한 rate를 처음 제시하며, fixed-point arithmetic에서 quantization error를 분석한다.실험에서 BUCKWILD!는 logistic regression용 HOGWILD! 기반 알고리즘보다 최대 2.3× 속도 향상을 달성한다.

2 주요 결과

이 논문은 일부 non-convex 문제를 포함해 asynchronous update에서 convergence rate를 bound하기 위한 martingale 기반 기법을 제시한다. stochastic update와 delay를 함께 모델링해, 최악의 expected delay에 의해 rate가 제어되도록 한다.

  • 문제 정식화: core가 iterate의 별도 cached copy를 유지하기 때문에 asynchronous execution은 stale read와 race condition을 유발한다.알고리즘은 update sample, success region, 그리고 time T까지 어떤 iterate도 해당 영역에 도달하지 못했음을 나타내는 failure event를 통해 formalize된다.
  • Martingale framework: martingale method는 stochastic sampling, random initialization, asynchronous delay를 하나의 model로 결합해 asynchronous SGD와 관련 알고리즘을 분석한다.이 기법은 sequential setting을 넘어 convergence analysis를 확장하며, convex 문제와 일부 non-convex algorithm에 적용된다.
  • Asynchronous hardware model: hardware model은 central store에서 write를 serialize하고, atomic single-coordinate read-add-write update를 사용하며, asynchronous effect를 coordinate-wise delay로 나타낸다.update sample은 i.i.d.라고 가정하는 반면, delay는 상관될 수 있지만 expected value가 τ인 random variable로 bound된다.
  • Asynchronous convergence theorem: Theorem 1은 bounded rate supermartingale을 갖는 asynchronous stochastic algorithm이 HRξτ < 1일 때 converge함을 보인다.필요한 boundedness condition은 supermartingale의 iterate sensitivity, expected update sensitivity, expected update magnitude를 제어한다.
  • Asynchronous convergence theorem: asynchronous failure probability는 worst-case expected delay τ에만 의존하며, sequential bound보다 1 − HRξτ의 factor만큼 증가한다.논문은 HRξτ ≪ 1인 practical case에서 이 증가가 negligible하다고 말한다. 증명에서는 W_t로부터 corrected supermartingale V_t를 구성한다.

3 응용

이 논문은 martingale 기반 분석을 convex asynchronous SGD, low-precision BUCKWILD!, non-convex HOGWILD! Alecton에 적용해, 완화된 가정하에서 failure-rate bound를 도출하고 기법의 일반성을 입증한다.

  • Convex HOGWILD!: convex HOGWILD! 분석은 gradient sparsity를 가정하지 않고 failure-rate bound를 도출하며, 대신 gradient-sample second moment와 expected delay에 의존한다. 더 엄격한 가정하에서는 Niu et al.의 rate [17]를 복원한다.이 결과는 rate supermartingale을 구성하고 Theorem 1을 적용해 얻어진다.
  • Low-Precision BUCKWILD!: BUCKWILD!는 low-precision arithmetic을 unbiased하고 bounded한 round-off noise로 모델링하고, 동일한 supermartingale 접근법을 적용해 convex convergence bound를 얻는다.κ ≪ 1일 때 추가 error는 무시할 수 있으므로, BUCKWILD!는 HOGWILD!보다 적은 wall-clock time에 comparable한 output quality에 도달한다.
  • Non-Convex Alecton: non-convex 문제에서는 rank-1 low-rank least-squares matrix completion에 분석을 특화해, eigengap, incoherence, bounded-space 조건 [4]하에서 asynchronous HOGWILD! Alecton을 분석한다.이 방법은 dominant eigenvector의 eigenvalue가 아니라 direction의 recovery를 추적하며, entrywise matrix sampling을 사용한다.
  • Non-Convex Alecton: 결과적으로 얻은 supermartingale은 HOGWILD! Alecton의 failure-probability bound를 제공하며, 이 framework가 convex SGD를 넘어 확장됨을 보인다.분석에서 parameter γ는 허용 가능한 runtime horizon과 supermartingale의 initial value 사이의 trade-off를 조절한다.

4 실험

실험은 비동기 non-convex matrix completion과 BUCKWILD!에 대한 이론적 결과를 검증하며, low-precision arithmetic이 training을 크게 가속할 수 있고 비동기 matrix completion이 sequential training과 비슷하게 수렴함을 보인다.

  • BUCKWILD! 구현: BUCKWILD!는 HOGWILD!의 32-bit floating point representation 대신 입력 데이터를 8-bit 또는 16-bit integers로 반올림한다.낮은 precision은 memory usage를 줄이고 single-instruction-multiple-data (SIMD) instructions를 사용할 수 있게 하며, thread들은 locking 없이 병렬로 update한다.
  • Precision 실험: Table 1은 네 개의 DimmWitted-favored datasets [25]에서 arithmetic precision에 따라 logistic-regression training loss가 어떻게 변하는지 평가한다.실험에서는 step size α = 0.0001을 사용하며, 다양한 step size 범위에서도 비슷한 결과가 보고된다. datasets에는 Reuters, RCV1, Forest가 포함된다.
  • BUCKWILD! 가속: BUCKWILD!는 dense RCV1에서 sequential full-precision SGD와 best-case HOGWILD! 모두에 비해 significant speedups를 달성한다.Figure 1(a)는 각각 six hyperthreaded cores를 갖춘 두 개의 Xeon X650 CPUs와 24GB의 RAM이 장착된 machine에서 두 baseline을 비교한다.
  • 비동기 matrix completion: 비동기 및 sequential Alecton matrix completion은 synthetic matrix에서 질적으로 유사한 convergence를 보이며 same noise floor에 도달한다.각 plotted series는 서로 다른 randomized run이므로 trajectory는 어느 정도 달라진다.

5 결론

이 논문은 BUCKWILD!라는 하드웨어 지향 SGD 전략을 포함해, asynchronous 및 low-precision random algorithm의 수렴률을 다루는 통합 martingale 기반 프레임워크를 제시한다.

  • 이 논문은 SGD와 같은 asynchronous 및 low-precision random algorithm의 수렴률을 위한 통합 이론적 프레임워크를 개발한다.
  • sequential full-precision algorithm에 대한 martingale 기반 수렴률을 활용하면 asynchronous low-precision 버전의 수렴률을 얻을 수 있다.
  • 이 논문은 작업 및 데이터...를 위해 최신 하드웨어 자원을 활용하도록 설계된 SGD 전략 BUCKWILD!를 소개한다.

정리 1의 증명

증명은 보정된 process V_t를 구성하고, asynchronous update에서 그 기댓값이 증가하지 않음을 보인다. 이 supermartingale 성질을 초기 조건 및 total expectation과 재귀적으로 결합하면 성공 확률의 bound를 얻는다.

  • 정리 1의 증명: 증명은 delay-dependent term으로 W_t를 보정해 V_t를 정의한 다음, update x_t+1 = x_t + ˜G(˜v_t) 이후의 evolution을 분석한다.보정에는 H_R, ξ, 그리고 stopping-time quantity τ_t가 사용된다.
  • 정리 1의 증명: Lipschitz continuity, W의 rate supermartingale 성질, 그리고 update-distance bound를 통해 V_t에 대한 one-step inequality를 확립한다.각 step에서 x의 단일 entry만 update되므로 1-norm과 2-norm이 같다는 사실을 사용한다.
  • 정리 1의 증명: 모든 T < B에 대해 재귀적으로 적용하면 E[V_T] ≤ E[V_0]이고, hardware initialization은 E[V_0] = E[W_0(x_0)]을 함의한다.algorithm이 성공한 뒤에는 V_t가 변하지 않으므로 성공 이후에도 inequality는 유효하다.
  • 정리 1의 증명: total expectation의 법칙은 성공한 execution과 성공하지 못한 execution을 분리하며, 이후 rate-supermartingale bound를 사용해 P(F_T)에 대해 푼다.success event는 W_T의 conditional value와 correction term H_Rξτ_T를 통해 lower-bound된다.

B 볼록 경우의 증명

이 절에서는 조각별 로그 논증을 강한 볼록성, 반올림 오차 경계, 명시적 유계성 검증과 결합해 저정밀도 볼록 SGD rate-supermartingale lemma를 증명한다. 이어 Theorem 1을 적용해 대응하는 corollary를 도출한다.

  • B 볼록 경우의 증명: 이 lemma는 저정밀도 볼록 SGD rate supermartingale에 대한 유계성 매개변수 R = αL 및 ξ2 = α2(1 + κ2)M 2를 확립한다.증명에서는 로그 도함수, 평균값 정리, 희소성 구조, 반올림 오차 경계, unbiased quantization을 이용해 필요한 연속성 경계를 검증한다.
  • B 볼록 경우의 증명: 조각별 로그는 미분 가능하고 오목하므로, rate-supermartingale 증명에 사용하는 Jensen 기반 부등식을 얻을 수 있다.그 지지 부등식은 오목 함수의 일차 과대근사에서 도출된다.
  • B 볼록 경우의 증명: 증명에서는 W_t를 구성해 성공 이전에는 rate-supermartingale 성질을 만족하고, iterate가 success set에 들어간 뒤에는 remains constant하도록 한다.로그의 비음수성이 필요한 post-horizon bound를 확립한다.
  • B 볼록 경우의 증명: 볼록 경우의 corollary는 lemma의 결과에 Theorem 1을 직접 적용해 따른다.rate-supermartingale 조건과 매개변수 경계를 증명한 뒤 수렴 결과를 완성한다.

C 비볼록 경우의 증명

비볼록 경우의 증명은 De Sa et al. [4]의 lemma를 rank-1 entrywise sampling에 맞게 특수화하고, rate supermartingale를 통해 asynchronous Alecton의 수렴을 확립한다. 이어서 supermartingale parameter를 bound하고 이에 대응하는 failure-probability guarantee를 도출한다.

  • τ-bound: 증명은 entrywise sampling, incoherence, 그리고 Section 3.3의 step-size 조건하에서 Alecton에 대한 특수화된 τ-bound를 사용한다.이 bound는 De Sa et al. [4]의 결과를 rank-1, entrywise-sampling에 맞게 특수화한 것이다.
  • Rate supermartingale: asynchronous Alecton에 대한 rate supermartingale W_t를 구성하고, iterate가 S ∪ Z에 들어가면 이를 freeze한다.증명은 필요한 horizon bound를 포함해 stopping 전후의 supermartingale 성질을 검증한다.
  • Parameter bounds: 증명은 boundedness parameter H, R, ξ를 확립하며, R = ηµ ∥A∥F이고 ξ = ηµ ∥A∥F C이다.H bound는 τ(x)를 미분해 얻고, R bound에는 incoherence를 사용하며, ξ bound는 update magnitude를 제어한다.
  • Failure probability: Theorem 1을 B = T 및 확립된 상수와 함께 적용하면 asynchronous Alecton에 대한 명시된 failure-probability bound를 얻는다.corollary는 선택한 horizon과 parameter 값을 Lemma 2에 대입해 원하는 결과를 얻는다.

D 단순화된 볼록 결과

이 절에서는 Section 3.1의 조건에서 constant step size를 사용해 주요 결과와 유사한 볼록 경우 결과의 초등적 증명을 제시한다. 이 증명은 최적해까지의 제곱 거리를 기대값으로 bound하지만 non-convex 경우로는 확장되지 않는다.

  • 단순화된 볼록 증명은 martingale 결과를 사용하지 않으므로 앞선 증명보다 더 초등적이지만 볼록 경우로 제한된다.
  • Theorem 2: Theorem 2는 임의의 ǫ > 0 및 ϑ ∈ (0, 1)에 대해 선택한 constant step size를 사용해 Section 3.1의 조건에서 볼록 경우 결과를 확립한다.
  • Proof: 증명은 각 timestep에서 최적해까지의 제곱 거리가 일반적으로 감소함을 보여 최적해까지의 제곱 거리를 제어한다.
  • Proof: one-step bound는 conditional expectation과 full expectation을 취하기 전에 현재 거리, first-order 변화, delayed-update noise, random-sampling noise를 분리한다.
Loading 1506.06438v2…