Source-linked AI summary
Revisiting Distributed Sign-Based Variance Reduction
Wei Jiang, Zechao Li, Lijun Zhang
TL;DR
Heterogeneous worker objectives can make majority voting local signs biased relative to the gradient of the average objective. The paper tracks the global gradient at the server using compressed recursive increments, and reports improved stochastic convergence rates and finite-sum oracle orders matching corresponding centralized bounds.
Problem
With heterogeneous local objectives, majority voting local signs may not align with the gradient of the average objective, limiting distributed extensions of variance reduction.
Source: §1 · pp. 1–2Method
The server tracks a global gradient by accumulating unbiased-compressed recursive increments, with periodic exact gradient refreshes and compressed component-gradient differences for finite-sum problems.
Source: §1 · p. 2Results
The stochastic methods improve the ℓ2 horizon dependence of previous methods and remove the previous error floor for the ℓ1 criterion; finite-sum bounds have the same oracle orders as corresponding centralized methods.
Source: §1 · p. 2Takeaways & Limitations
The proposed approach obtains stochastic and finite-sum convergence guarantees for distributed sign-based variance reduction under the stated settings.
Source: §1 · p. 2The majority-vote counterexample establishes a gradient floor for SSVR-MV Option 1 in a three-worker setting, including when local estimates are exact.
Source: §3.1 · p. 4
Abstract
from arXiv · showhide
Sign-based methods reduce communication costs in distributed environments, but aggregating local signs can introduce bias when data are heterogeneous. As a result, existing sign-based variance reduction methods fail to obtain the optimal convergence rates. In this paper, we solve this problem and obtain optimal rates for both nonconvex stochastic and finite-sum optimization. We first give a counterexample showing that majority voting can fail to approach stationary points even with exact local gradients. Motivated by this limitation, we propose tracking the global gradient at the server through unbiased compression of recursive gradient increments. As a result, we can obtain the convergence rates of $O(\sqrt{d/K}+\sqrt d (a/(nK))^{1/3})$ for the $\ell_1$-norm and $O(\sqrt{a/K}+\sqrt a/(nK)^{1/3})$ for the $\ell_2$-norm. Here, $K$ is the iteration number, $n$ is the number of workers, $d$ is the dimension, and $a=1+\omega$, with $\omega$ denoting the compressor's relative variance. For finite-sum problems with $M$ components, we combine periodic exact gradient refreshes with compressed component-gradient differences. The resulting total sample complexities are $O(M+d\sqrt{aM}\epsilon^{-2})$ and $O(M+a\sqrt M\ epsilon^{-2})$ for $\ell_1$ and $\ell_2$ gradient norms at most $\epsilon$, matching the corresponding bounds in centralized settings.
1 Introduction
The introduction frames heterogeneous local objectives as a challenge for sign-based variance reduction: majority voting can misalign with the gradient of the average objective. The paper instead tracks a server-side global gradient and reports improved stochastic rates and finite-sum complexities.
1 Introduction
- A majority vote of local signs may not align with the gradient of the average objective when workers have different local objectives.The paper identifies this nonlinear aggregation as a barrier to automatically extending centralized variance reduction to distributed settings.Source: §1 · p. 2
- The stochastic methods track a server-side global gradient by accumulating unbiased-compressed recursive increments rather than aggregating local signs.The server retains a global estimate; the ℓ1 variant uses deterministic signs, while the ℓ2 variant uses unbiased compression for its update.Source: §1 · p. 2
- A three-worker counterexample has a nonzero average-gradient floor despite exact local gradients, isolating bias in the final vote.The example motivates tracking the global gradient before taking signs.Source: §1 · p. 2
- The ℓ2 stochastic rate improves the horizon dependence of previous methods.For the ℓ1 criterion, the paper reports removing the previous error floor.Source: §1 · p. 2
- For finite-sum problems, periodic exact gradient refreshes and compressed component-gradient differences yield bounds with the same oracle orders as corresponding centralized methods.The finite-sum method also removes the need for a bounded-gradient assumption.Source: §1 · p. 2
2 Assumptions
The assumptions specify lower-bounded objectives and smoothness conditions for the stochastic and finite-sum settings, alongside a relative-variance compression model. The finite-sum results require no bounds on gradients, oracle variance, or gradient heterogeneity.
2 Assumptions
- The stochastic setting assumes the objective is lower bounded and imposes smoothness conditions on the worker objectives.The stated alternative uses bounded oracle variance and a true-gradient bound to imply the relevant inequality.Source: §2 · p. 3
- The compressor is assumed to be unbiased with noise controlled relative to the input magnitude.The paper notes that this model includes the usual scaled stochastic sign, for which 1 + ω = d.Source: §2 · p. 3
- The finite-sum results use Assumptions 2 and 3 without requiring bounds on gradients, oracle variance, or gradient heterogeneity.The finite-sum objective is assumed lower bounded and its components satisfy the stated smoothness condition.Source: §2 · p. 3
3 The proposed method
The proposed method replaces majority voting with server-side tracking of the global gradient through compressed increments. Its updates are tailored to the ℓ1 and ℓ2 criteria, while a counterexample identifies the bias in the earlier majority-vote approach.
3.1 SSVR-MV and the limitation of its majority voting
- With worker sign means (u, u, −2u), the average sign mean is zero but the expected majority vote is u^3 > 0.The example exposes bias from nonlinear voting even when worker messages are unbiased; the paper also gives a gradient-floor counterexample with exact local estimates.Source: §3.1 · p. 4
3.2 Tracking the global gradient through compressed increments
- The server retains its global gradient estimate and corrects it with numerical increments before choosing an update direction, rather than taking a majority vote of randomized local signs.Workers send compressed recursive increments; the decomposition uses a fresh-gradient term and a same-sample gradient difference.Source: §3.2 · p. 5
3.3 The compressed update for the server
- For the ℓ1 criterion, the deterministic sign update turns a bound on server tracking error into an ℓ1 stationarity guarantee.The paper names this method DVR-Sign.Source: §3.3 · p. 5
- For the ℓ2 criterion, the server uses an unbiased compressed update whose descent analysis accounts for additional tracking error from random step length.The negative squared-norm term absorbs that additional tracking error.Source: §3.3 · p. 6
4 Stochastic guarantees
DVR-Sign and DVR-Q share a server-side gradient tracker but use different update directions and descent analyses for their respective stationarity criteria. Their stochastic guarantees bound tracking error and use parameter choices to obtain convergence guarantees.
4 Stochastic guarantees
- Both variants analyze a server estimate zt against the global gradient, with c = a/n and a = 1 + ω.The section distinguishes their model movements and descent arguments: deterministic signs for the ℓ1 criterion and compressed updates for the ℓ2 criterion.Source: §4 · p. 6
4.1 The ℓ1 guarantee for DVR-Sign
- For the DVR-Sign variant, E1 ≤ cH^2/B0 and, for t ≥ 2, Et ≤ (1 − β)Et−1 + 2c(β^2H^2 + L^2η^2d).Source: §4.1 · p. 6
4.2 The ℓ2 guarantee for DVR-Q
- DVR-Q instead uses unbiased compressed updates; under Laη ≤ 1/2 and β ≥ 4caL^2η^2, its tracker-norm term is nonnegative and can be dropped.The conditional second moment of Q(zt) is bounded by (1 + ω)∥zt∥2^2, supporting descent in the squared Euclidean norm.Source: §4.2 · p. 7
5 The proposed methods for finite-sum problems
For finite-sum optimization, the methods periodically refresh the exact global gradient and use compressed component-gradient differences between refreshes. They pair deterministic sign updates with an ℓ1 guarantee and unbiased compressed updates with an ℓ2 guarantee.
5 The proposed methods for finite-sum problems
- At refresh times, workers compute local full gradients and the server resets its estimate to the exact global gradient; intervening steps use compressed component-gradient differences.The same component is evaluated at successive iterates, so component smoothness controls update noise without requiring bounded gradients or bounded heterogeneity.Source: §5 · pp. 7–8
5.1 Deterministic sign updates for the ℓ1 guarantee
- With q = m, DVR-Sign-FS uses deterministic sign updates and ensures E∥∇f(xτ)∥1 ≤ ϵ.A refresh removes estimation error; setting q = m makes the amortized refresh cost M/q = n, the same order as an ordinary update cost of 2n.Source: §5.1 · pp. 8–9, §5 · p. 8
5.2 Unbiased compressed updates for the ℓ2 guarantee
- DVR-Q-FS uses unbiased compressed updates and ensures E∥∇f(xτ)∥2 ≤ ϵ when q = m.Its update uses Q(zt), whose conditional second moment is bounded by aη^2∥zt∥2^2; unbiasedness supports descent in the squared Euclidean norm.Source: §5.2 · p. 9
A Proof of Proposition 1
The proof constructs a three-worker example in which exact local estimates still produce a biased expected majority vote at the global minimizer. It then bounds the average vote to establish a finite-horizon gradient floor.
A Proof of Proposition 1
- In the construction, all three local derivatives have absolute value at most G = 1, the local objectives are 1/2-smooth, and x1 = 0 is a global minimizer.Source: A Proof of Proposition 1 · p. 11
- At the minimizer, h(0) = z = 0, yet M(0) = u^3 > 0; thus M is positive there even though h(0) and z are zero.Source: A Proof of Proposition 1 · p. 11
- The proof controls the average vote even though individual iterates need not converge.It establishes xM(x) ≥ −1 for every x, then combines this control with the finite-horizon argument.Source: A Proof of Proposition 1 · pp. 11–12
- With η = Θ(K−1/2), the proof derives a finite-horizon lower bound on the expected gradient norm at an independently uniform output iterate.The argument uses u^3 = 1/4096 and obtains the limiting lower-bound constant 1/1542.Source: A Proof of Proposition 1 · p. 12
B Proofs for the stochastic results
The stochastic proofs analyze the server tracker using unbiased compression, conditional expectations, and controlled second moments. The resulting recursion retains dependence on model movement and worker initialization samples.
B Proofs for the stochastic results
- The proof retains actual model movement in its tracking estimate rather than replacing it with a gradient-magnitude bound.The stochastic setup defines c = a/n and identifies K as the number of model updates and B0 as the initialization batch per worker.Source: B Proofs for the stochastic results · p. 12
B.1 Moments and server tracking
- The tracking analysis controls the compressed estimator's second moment by a times the squared input norm, where a = 1 + ω.The proof conditions on the history before current samples and compression calls, then uses centered, conditionally independent worker errors in the recursion.Source: §B.1 · pp. 13–14
- The initialization batch is compressed as separate independent sample messages, whose centered second moments are bounded by aH^2.Distinct worker-sample messages use independent samples and compression calls, so their centered cross terms vanish when averaging.Source: §B.1 · p. 13
B.2 The ℓ1 guarantee
The ℓ1 guarantee follows by bounding sign errors through the tracking error, summing objective decreases, and choosing parameters so the resulting error terms meet the target accuracy.
B.2 The ℓ1 guarantee
- A sign mismatch on a nonzero gradient coordinate implies that coordinate’s gradient magnitude is at most the corresponding tracking error.Coordinates with zero gradient contribute nothing to this bound.Source: §B.2 · p. 14
- Smoothness bounds the objective change under the deterministic sign update; summing the decreases and averaging over a uniform output yields the stationarity bound.The proof controls the error sum using Jensen’s inequality and Cauchy–Schwarz.Source: §B.2 · pp. 14–15
- The parameter choice c = (1 + ω)/n is used when translating the bound to the stated setting with fixed L, H, and ∆f.The cited passage identifies this substitution as the step giving (27).Source: §B.2 · p. 15
- The selected horizon makes each of the two terms in the bound at most ϵ/2, so their sum is at most ϵ.The two horizon entries are chosen by solving the first-term inequality and cubing the second-term inequality.Source: §B.2 · p. 15
B.3 The ℓ2 guarantee
The ℓ2 analysis uses an unbiased compressed tracker update and preserves its dependence on the tracker norm in the descent calculation. Parameter choices then make the tracking contribution compatible with the target squared stationarity bound.
B.3 The ℓ2 guarantee
- Unlike a sign update, the movement under the compressed update shrinks with the tracker, so the descent calculation retains its dependence on the tracker norm.The proof uses this dependence rather than replacing the tracker norm with a gradient-magnitude bound.Source: §B.3 · p. 16
- With independent uniform output τ, the first average is E||∇f(xτ)||²; when Laη ≤ 1/2 and β ≥ 4caL²η², both subtracted terms are at most 1/2, making the tracker coefficient nonnegative.This cancellation explains why Zt was not replaced by a gradient-magnitude bound earlier.Source: §B.3 · p. 16
- With r = (K/n²)^(1/3), the parameter choices set β = 1/[n(1 + r)²] and make the tracker coefficient nonnegative.The proof then bounds the remaining terms separately to establish the stated result.Source: §B.3 · pp. 16–17
- The chosen horizon makes the two terms in the squared-norm bound at most ϵ²/2 each, yielding a total at most ϵ².The cited passage states that the resulting update and per-worker sample complexities follow for fixed L, H, and ∆f.Source: §B.3 · p. 17
C Proofs for finite sums
The finite-sum proof counts component-gradient evaluations by separating exact refreshes from ordinary updates. The resulting expressions account for both total and per-worker evaluations.
C Proofs for finite sums
- For K updates with refresh period q, exact refreshes occur at 1, 1 + q, 1 + 2q, and subsequent intervals of q.The count distinguishes r refreshes from K − r ordinary updates.Source: §C.1 · pp. 17–18
- The total component-gradient count is Ngrad = Mr + 2n(K − r).Each refresh evaluates every component once; each ordinary update evaluates one component at two points on each worker.Source: §C.1 · p. 18
- The per-worker count is Ngrad,j = mr + 2(K − r).This count includes the refresh evaluations and the two evaluations per ordinary update.Source: §C.1 · p. 18
C.2 Tracking error between exact refreshes
Between exact refreshes, the estimator’s tracking error is bounded using component-gradient differences and smoothness. The ℓ1 and ℓ2 descent arguments then convert tracking-error bounds into stationarity bounds.
C.2 Tracking error between exact refreshes
- At each refresh the estimator error is zero, and between refreshes the same component is evaluated at successive iterates so component smoothness controls the update noise.For DVR-Sign-FS, the tracking-error bound sums at most q − 1 terms, each equal to η²d.Source: §C.2 · pp. 18–19
C.3 Descent for the ℓ1 criterion
- For the ℓ1 criterion, smoothness and the tracking-error bound yield a stationarity guarantee; setting q = m gives the stated target-accuracy complexity construction.Uniformly choosing τ identifies the average gradient norm with the expected norm at the output iterate.Source: §C.3 · pp. 19–20
C.4 Descent for the ℓ2 criterion
- For the ℓ2 criterion, the descent inequality combines squared gradient norm, tracker norm, and tracking error; applying the tracking bound yields the squared-norm guarantee.An independent uniform output choice converts the averaged bound to an expectation at τ, after which Cauchy–Schwarz gives the norm guarantee.Source: §C.4 · p. 21