arXiv CSopen access

Revisiting Distributed Sign-Based Variance Reduction

Revisiting Distributed Sign-Based Variance Reduction Wei Jiang1,2 1

Lijun Zhang2,3

School of Computer Science and Engineering, Nanjing University of Science and Technology, China 2

National Key Laboratory for Novel Software Technology,Nanjing University, China 3

arXiv:2609.18656v1 [cs.LG] 16 Sep 2026

Zechao Li1

School of Artificial Intelligence, Nanjing University, China

Abstract 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 p a result, we can obtain the convergence rates of O( d/K + d (a/(nK))1/3 ) for the ℓ1 -norm p √ and O( a/K + a/(nK)1/3 ) for the ℓ2 -norm. Here, K is the iteration number, n is the number of workers, d is the dimension, and a = 1 + ω, with ω 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 aM ϵ−2 ) and O(M + a M ϵ−2 ) for ℓ1 and ℓ2 gradient norms at most ϵ, matching the corresponding bounds in centralized settings.

1

Introduction

In this paper, we focus on smooth nonconvex optimization in the distributed setting: min f (x) =

x∈Rd

n 1X fj (x), n j=1

fj (x) = Eξ∼Dj Fj (x; ξ).

(1)

In this setting, each worker j ∈ {1, 2, · · · , n} accesses its own data distribution Dj , and these data distributions may differ for different nodes. Such heterogeneous objectives arise when data are partitioned arbitrarily across machines. We also consider the finite-sum formulation, in which every worker has a fixed dataset of m components, and the problem can be written in the form: min f (x) =

x∈Rd

n 1X fj (x), n j=1

fj (x) =

m 1 X fj,i (x). m i=1

(2)

Here M = nm is the total number of components across the system. Our goal is to find stationary points while reducing the information sent between workers and the parameter server. Sign-based methods are highly attractive for this purpose since a vector of signs only takes one bit per coordinate (Bernstein et al., 2018, 2019). Later studies show that the momentum technique improves the small-batch convergence guarantees (Safaryan and Richtárik, 2021; Jiang et al., 2025), and variance reduction further improves the quality of the gradient estimate. In particular, the previous centralized variance reduction method SSVR attains an ℓ1 convergence rate 1

√ of O( d K −1/3 mean-squared smoothness, and SSVR-FS attains a total gradient complexity √ ) under −2 of O(M + d M ϵ ) for ℓ1 accuracy ϵ on a centralized dataset of M components (Jiang et al., 2024). These results motivate extending the benefits of variance reduction to the distributed problem. Such an extension is not automatic. In a majority-vote method, each worker first converts its local estimate into a sign vector, and the server takes the majority of those signs. For different local objectives, this nonlinear aggregation may not align with the gradient of their average. SSVR-MV (Jiang et al., 2024) provides two options with p different server updates. Option 1 uses deterministic √ majority voting and has an ℓ1 guarantee O( d/K + d/ n) with an error floor. Option 2 uses randomized worker and server signs and obtains an ℓ2 rate O(d1/4 K −1/4 ). SSVR-MV Option 2 also requires projecting each local estimate onto a Euclidean ball before worker-side sign quantization, and its O(K −1/4 ) guarantee leaves a gap to the centralized variance-reduced O(K −1/3 ) rate. In this paper, we obtain improved convergence rates with new algorithms. We assume an unbiased relative-variance compressor that introduces noise proportional to the input magnitude, allowing more general compressors. We then let the server retain a global gradient estimate. Workers send compressed recursive increments, and the server accumulates these messages before choosing a global update direction. Our recursion compresses an increment consisting of a scaled gradient and a same-sample gradient difference, whose second moment is controlled by the parameter choices. Finally, we use deterministic signs for the ℓ1 criterion and unbiased compression for the ℓ2 guarantee. For the finite-sum problem, we periodically compute the exact global gradient and use compressed component-gradient differences for steps between checkpoints. The same component is evaluated at two successive iterates, so component smoothness controls the update noise even when local gradients√are large or heterogeneous. The resulting √ −2 total component-gradient complexities are −2 O(M + d aM ϵ ) for ℓ1 -norm and O(M + a M ϵ ) for ℓ2 -norm, where a = 1 + ω and ω is the compressor’s relative variance. These have the same oracle orders as the centralized SSVR-FS algorithm and Euclidean variance-reduced methods, respectively. Our contributions.

We summarize the results and contributions of this paper below.

• We first analyze the obstruction to local majority voting. We give a three-worker counterexample in Proposition 1, which suffers a nonzero average-gradient floor despite exact local gradients. It isolates the bias of the final vote and motivates tracking the global gradient before taking signs. √ p • For stochastic problems, we attain O( d/K +p d(a/(nK))1/3 ) in the ℓ1 criterion, removing √ the previous error floor. Then, we obtain O( a/K + a/(nK)1/3 ) for the ℓ2 -norm. This improves the horizon dependence of previous methods. • We also obtain the finite-sum bounds for the sign-based distributed setting. Exact refreshes and compressed component differences remove √ the need for a bounded √ gradient assumption. We obtain total oracle complexities O(M + d aM ϵ−2 ) and O(M + a M ϵ−2 ) for the ℓ1 and ℓ2 criteria, matching the corresponding centralized rates.

2

Assumptions

We now specify the assumptions used. Write gj (x; ξ) = ∇Fj (x; ξ) for a stochastic gradient and ∆f = f (x1 ) − f∗ for the initial objective gap, where f∗ is a lower bound of the objective f . We first give the following assumption on the objective function for the stochastic problem (1).

2

Assumption 1. The objective satisfies f ≥ f∗ > −∞. For every worker and all x, y, we have Eξ gj (x; ξ) = ∇fj (x),

(3)

Eξ ∥gj (x; ξ)∥22 ≤ H 2 , Eξ ∥gj (x; ξ) − gj (y; ξ)∥22 ≤ L2 ∥x − y∥22 .

(4) (5)

Remark: Here, Jensen’s inequality implies that fj and f are also L-smooth. Besides, inequality (4) can be replaced with bounded oracle variance σ 2 and a true-gradient bound ∥∇fj (x)∥2 ≤ G2 , which imply inequality (4) with H 2 = σ 2 + G22 . Next, we give the general compression assumption below. Assumption 2 (Relative-variance compressor). For every input v, the output Q(v) satisfies E[Q(v) | v] = v,

(6)

E[∥Q(v) − v∥22 | v] ≤ ω∥v∥22 .

Note that unbiasedness also gives E[∥Q(v)∥22 | v] ≤ (1 + ω)∥v∥22 .

(7)

Remark: The general compression assumption includes the usual scaled stochastic sign. For v ̸= 0, let ρ(v) = ∥v∥∞ and draw independent signs with Pr(Sk = 1 | v) = (1 + vk /ρ(v))/2. Then Q(v) = ρ(v)S,

Q(0) = 0,

(8)

is unbiased and satisfies 1 + ω = d since E[∥Q(v) − v∥22 | v] = d∥v∥2∞ − ∥v∥22 ≤ (d − 1)∥v∥22 . Finally, we list assumptions for the finite-sum problem (2). Assumption 3. The average objective is lower bounded and each component satisfies ∥∇fj,i (x) − ∇fj,i (y)∥2 ≤ L∥x − y∥2

for all x, y, j, i.

(9)

The finite-sum results use Assumptions 2 and 3, requiring no bound on gradients, oracle variance, or gradient heterogeneity.

3

The proposed method

We begin with the earlier SSVR-MV method and explain the bias created by its majority vote. This motivates a global gradient estimate at the server, followed by either a sign update for the ℓ1 criterion or an unbiased compressed update for the ℓ2 criterion.

3.1

SSVR-MV and the limitation of its majority voting

The earlier method. SSVR-MV, introduced by Jiang et al. (2024), combines a local variancereduced estimator with bidirectional sign communication. Specifically, each worker j first initializes v1j = gj (x1 ; ξ1j ) and, for t ≥ 2, computes j vtj = gj (xt ; ξtj ) + (1 − β)[vt−1 − gj (xt−1 ; ξtj )].

(10)

The two stochastic gradients in this update use the same sample. For a fixed radius R > 0 and an input satisfying ∥v∥∞ ≤ R, define the random sign vector SR (v) coordinatewise by Pr(SR (v)k = +1 | v) =

1 + vk /R , 2

Pr(SR (v)k = −1 | v) = 3

1 − vk /R . 2

(11)

Thus the signs estimate the scaled input without any bias. In SSVR-MV (Option 1), worker j sends qtj = SR (vtj ), and the server broadcasts their deterministic majority vote: 

 n X 1 st = Sign qj  ,

n j=1 t

xt+1 = xt − ηst .

(12)

The setting of their Theorem 3 uses ∥gj (x; ξ)∥∞ ≤ G, β = 1/2, η = O((dK)−1/2 ), and R = 4G, keeping the inputs inside the radius. The server forms a new vote at every iteration. Where the bias enters. The worker signs are unbiased for their scaled inputs, but the majority operation is nonlinear. This can be seen exactly with three workers. For any q1 , q2 , q3 ∈ {−1, 1}, Sign(q1 + q2 + q3 ) =

q1 + q 2 + q 3 − q 1 q2 q3 . 2

(13)

Writing mj = Eqj , with all expectations conditional on these inputs, we obtain 

E Sign(q1 + q2 + q3 ) =



3 X

1 Eqj − E[q1 q2 q3 ] 2 j=1

1 = (m1 + m2 + m3 − m1 m2 m3 ). 2

(14)

If (m1 , m2 , m3 ) = (u, u, −2u) with 0 < u ≤ 1/2, the average sign mean is zero, whereas the expected majority vote is u3 > 0. Unbiased worker messages therefore can produce a biased vote. Proposition 1 (A gradient floor with exact local estimates). There exist three lower-bounded smooth one-dimensional local objectives with gradients bounded by G = 1 such that SSVR-MV Option 1, initialized at a global minimizer and using exact gradients, satisfies lim inf E|f ′ (xτ )| ≥ K→∞

1 >0 1542

(15)

for R = 4 and step size η = Θ(K −1/2 ), where τ is independent and uniform on {1, . . . , K}. Construction and intuition. Take f1 (x) = f2 (x) = 12 log cosh x + 14 x,

f3 (x) = 21 log cosh x − 12 x.

Their average is f (x) = 12 log cosh x, minimized at x = 0. At this point the worker sign means are (u, u, −2u) with u = 1/16, so (14) gives a nonzero expected vote despite f ′ (0) = 0. Appendix A proves that this bias produces the stated gradient floor.

3.2

Tracking the global gradient through compressed increments

We retain the variance-reduction idea in (10), but change what workers transmit and what the server remembers. For t ≥ 2, worker j forms the increment hjt = gj (xt ; ξtj ) − (1 − β)gj (xt−1 ; ξtj ) = βgj (xt ; ξtj ) + (1 − β)[gj (xt ; ξtj ) − gj (xt−1 ; ξtj )].

4

(16)

Algorithm 1 DVR-Sign / DVR-Q Require: x1 , K, B0 , η, β, compressor Q. 1: Each worker draws B0 samples at x1 . P j 2: Server initializes z1 = (nB0 )−1 j,b Q(gj (x1 ; ξ1,b )). 3: for t = 1, . . . , K do 4: if t ≥ 2 then 5: Each worker draws a sample ξtj , forms (16), and sends Q(hjt ). 6: Server updates zt by (17). 7: end if 8: if variant is DVR-Sign then 9: Server broadcasts st = Sign(zt ) to all workers. 10: else 11: Server broadcasts st = Q(zt ) to all workers. 12: end if 13: All workers and the server set xt+1 = xt − ηst . 14: end for 15: Draw an independent uniform τ ∈ {1, . . . , K} and return xτ . The worker sends an encoding of Q(hjt ) and the server then accumulates the increments: zt = (1 − β)zt−1 +

n 1X Q(hjt ). n j=1

(17)

The difference from (12) is substantive: the server retains zt−1 and corrects it with numerical increments before choosing its update direction. In particular, it does not take a majority vote of independently randomized local signs. The increment decomposition is central to the analysis. The fresh-gradient term is multiplied by β, while mean-squared smoothness controls the same-sample difference. These two terms give Et ∥hjt ∥22 ≤ 2β 2 H 2 + 2L2 ∥xt − xt−1 ∥22 .

(18)

Here Et conditions on the history before the current worker samples and compression calls. Unlike repeatedly compressing a full local estimate, compressing this increment introduces noise that decreases with smaller β and smaller model movements. The two methods below control this movement differently. At initialization, every worker compresses B0 independent sample gradients separately. The whole algorithm is specified in Algorithm 1.

3.3

The compressed update for the server

For ℓ1 measure For the ℓ1 criterion, the natural direction is st = Sign(zt ). With an exact estimate zt = ∇f (xt ), its inner product with the gradient equals ∥∇f (xt )∥1 . With an approximate estimate, the corresponding inequality is √ −⟨g, Sign(z)⟩ ≤ −∥g∥1 + 2∥z − g∥1 ≤ −∥g∥1 + 2 d∥z − g∥2 . (19) Thus the deterministic sign update converts a bound on the server’s tracking error into an ℓ1 stationarity guarantee. We call this algorithm DVR-Sign: distributed variance reduction with sign updates. 5

For ℓ2 measure An ℓ1 -norm guarantee already implies an ℓ2 -norm guarantee through ∥g∥2 ≤ ∥g∥1 . √ However, this transfer retains the d tracking-error coefficient in (19). We therefore use the unbiased compressor already defined in Assumption 2 for the server broadcast as well: st = Q(zt ),

xt+1 = xt − ηst .

(20)

We call this method DVR-Q. Conditional on the history Gt containing zt and all current worker messages, fresh server randomness gives E[st | Gt ] = zt ,

E[∥st ∥22 | Gt ] ≤ (1 + ω)∥zt ∥22 .

(21)

With an exact estimate, the expected gradient inner product is ∥∇f (xt )∥22 . For an approximate estimate, the elementary identity −2⟨g, z⟩ = −∥g∥22 − ∥z∥22 + ∥z − g∥22

(22)

connects descent to squared Euclidean tracking error. Its negative ∥z∥22 term is essential: it absorbs the additional tracking error caused by the random step length in (21). The two methods thus use different directions for different criteria. Deterministic signs give the √ ℓ1 inner product in (19), while unbiased Q updates give squared ℓ2 descent without its explicit d conversion.

4

Stochastic guarantees

We first analyze DVR-Sign under the ℓ1 stationarity criterion and then analyze DVR-Q directly in the squared Euclidean norm. The two methods share the server recursion, but their model movements and descent arguments differ. Write a = 1 + ω and c = a/n. Denote et = zt − ∇f (xt ), P Et = E∥et ∥22 , and E K = K −1 K t=1 Et .

4.1

The ℓ1 guarantee for DVR-Sign

Theorem 2. Under Assumptions 1 and 2, for any η > 0, β ∈ (0, 1], and integers K, B0 ≥ 1, the DVR-Sign variant of Algorithm 1 satisfies Et ≤ (1 − β)Et−1 + 2c(β 2 H 2 + L2 η 2 d)

E1 ≤ cH 2 /B0 , EK ≤ E∥∇f (xτ )∥1 ≤

cH 2

+ 2c H 2 β +

B0 βK

L2 η 2 d

(t ≥ 2),

(23)

!

(24)

,

β

∆f Lηd + + 2 d EK . ηK 2 q

(25)

Balancing these effects gives the following result. Corollary 3. Under the assumptions of Theorem 2, choose 1 , u1 = √ K + c1/3 K 2/3

β = u1 ,

Hu1 η= √ , L d

1 B0 = 2 . u1 K 



(26)

Then DVR-Sign satisfies   √  L∆f √   c 1/3 L∆f H −1/2 E∥∇f (xτ )∥1 ≤ d + K + + 2 5H H 2 H K "

s

=O

√ 1+ω d + d K nK 

6

1/3

 .

#

(27)

Remark: To achieve E∥∇f (xτ )∥1 ≤ ϵ, the required number of model updates is ad3/2 d K =O 1+ 2 + ϵ nϵ3

4.2

!

.

The ℓ2 guarantee for DVR-Q

The unbiased compressor Q(zt ) has conditional mean zt , and its conditional second moment is at most (1 + ω)∥zt ∥22 . The descent analysis therefore controls the squared gradient norm and retains a negative tracker-norm term. This term absorbs the tracking error caused by moving the model, which is the key difference from the sign analysis. Theorem 4. Under Assumptions 1 and 2, for any η > 0, β ∈ (0, 1], and integers K, B0 ≥ 1, the DVR-Q variant of Algorithm 1 satisfies E∥∇f (xτ )∥22 + ≤

2caL2 η 2 1 − Laη − β

!

K 1 X E∥zt ∥22 K t=1

2∆f cH 2 + + 2cβH 2 . ηK B0 βK

(28)

In particular, if Laη ≤ 1/2 and β ≥ 4caL2 η 2 , the tracker-norm term on the left is nonnegative and can be dropped. Corollary 5. Under the assumptions of Theorem 4, choose r=



K n2

1/3

,

η=

1 , 2La(1 + r)

β=

1 , n(1 + r)2

B0 = ⌈1 + r⌉.

(29)

Then DVR-Q satisfies √ q a a 2 E∥∇f (xτ )∥2 ≤ 4L∆f + 4L∆f + 3H K (nK)1/3 ! r √ 1+ω 1+ω =O + . K (nK)1/3 q

+ H2

r

(30)

Remark: To achieve E∥∇f (xτ )∥2 ≤ ϵ, the required number of model updates is a a3/2 K =O 1+ 2 + 3 ϵ nϵ

5

!

.

(31)

The proposed methods for finite-sum problems

For the finite-sum problem (2), an occasional full pass through the data can replace the stochastic correction used by DVR-Sign and DVR-Q. We compute exact gradients at checkpoints, followed by compressed component-gradient differences. We use a deterministic sign for the ℓ1 criterion and employ the unbiased compressor Q for the ℓ2 criterion. Fix an integer refresh period q = m. At times t = 1 + kq, every worker computes and sends its local full gradient, and the server resets zt = ∇f (xt ). At other times, each worker independently

7

Algorithm 2 DVR-Sign-FS and DVR-Q-FS Require: x1 , K, η, refresh period q, and compressor Q. 1: for t = 1, . . . , K do 2: if t = 1 + kq for an integer k ≥ 0 then P 3: Each worker computes and sends ∇fj (xt ) = m−1 m i=1 ∇fj,i (xt ). P 4: Server sets zt = n−1 nj=1 ∇fj (xt ). 5: else 6: Every worker j draws an independent uniform ijt ∈ {1, . . . , m}. 7: Every worker forms ytj in (32) and sends Q(ytj ). P 8: Server sets zt = zt−1 + n−1 nj=1 Q(ytj ). 9: end if 10: if DVR-Sign-FS then 11: Server broadcasts st = Sign(zt ). 12: else 13: Server broadcasts st = Q(zt ). 14: end if 15: Set xt+1 = xt − ηst . 16: end for 17: Draw an independent uniform τ ∈ {1, . . . , K} and return xτ . draws a uniform component ijt ∈ {1, . . . , m} and sends a compressed paired difference, using the same component at both iterates. The server uses ytj = ∇fj,ij (xt ) − ∇fj,ij (xt−1 ), t

t

zt = zt−1 +

n 1X Q(ytj ). n j=1

(32)

The server retains zt itself for the next estimator update. Component smoothness gives ∥ytj ∥2 ≤ L∥xt − xt−1 ∥2 , which controls the increment without requiring bounded gradients or bounded heterogeneity. The whole method is described in Algorithm 2.

5.1

Deterministic sign updates for the ℓ1 guarantee

The first version uses st = Sign(zt ). A refresh eliminates the estimation error and only the q − 1 intervening updates can contribute to its variance. A refresh costs M component-gradient evaluations, whereas an ordinary update costs 2n. Choosing q = m makes the amortized refresh cost M/q = n, of the same order as the ordinary update cost. Theorem 6. Under Assumptions 2 and 3, let a = 1 + ω. For DVR-Sign-FS, define d J1 = + 2d 2

s

a(q − 1) . n

(33)

For an independent uniform τ ∈ {1, . . . , K}, aL2 η 2 d(q − 1) , n ∆0 E∥∇f (xτ )∥1 ≤ + LηJ1 . ηK

E∥zt − ∇f (xt )∥22 ≤

8

(34) (35)

Corollary 7. Under the assumptions of Theorem 6, set q = m. We ensure E∥∇f (xτ )∥1 ≤ ϵ, with ϵ , η= 2LJ1





L∆0 d  K =O1 + 1+ ϵ2

s



a(m − 1)  . n

(36)

√ L∆0 d Ngrad =O M + [n + aM ] . ϵ2 



(37) √





. Remark: For n ≤ O(am), the total oracle order is Ngrad = O M + d ϵaM 2

5.2

Unbiased compressed updates for the ℓ2 guarantee

The second version keeps the same refreshes and estimator, but uses st = Q(zt ), where Q satisfies Assumption 2 with a = 1 + ω. Unlike a sign step of fixed length, this update has conditional second moment at most aη 2 ∥zt ∥22 . Unbiasedness also makes the expected descent depend on ⟨∇f (xt ), zt ⟩. These two facts allow the tracking error to be absorbed into the descent inequality and yield a squared Euclidean stationarity guarantee. Theorem 8. Under Assumptions 2 and 3, for a = 1 + ω, define JQ = a 1 +

r

q−1 , n !

η=

1 . 2LJQ

(38)

Then an independent uniform τ ∈ {1, . . . , K} satisfies s

4L∆0 JQ E∥∇f (xτ )∥22 ≤ , K

E∥∇f (xτ )∥2 ≤ 2

L∆0 JQ . K

(39)

Corollary 9. Under the assumptions of Theorem 8, set q = m. We ensure E∥∇f (xτ )∥2 ≤ ϵ, with m−1 n  √  aL∆0 Ngrad = O M + M] . [n + ϵ2 "

aL∆0 K =O 1+ 1+ ϵ2

r

#!

,

(40) (41)

 √  √ Remark: For n ≤ O( m), this total oracle order Ngrad = O M + a ϵ2M matches the centralized Euclidean benchmark of SPIDER and PAGE (Fang et al., 2018; Li et al., 2021).

9

References Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Proceedings of the 35th International Conference on Machine Learning, pages 560–569, 2018. Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In International Conference on Learning Representations, 2019. Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, 2018. Wei Jiang, Sifan Yang, Wenhao Yang, and Lijun Zhang. Efficient sign-based optimization: Accelerating convergence via variance reduction. In Advances in Neural Information Processing Systems, 2024. Wei Jiang, Dingzhi Yu, Sifan Yang, Wenhao Yang, and Lijun Zhang. Improved analysis for sign-based methods with momentum updates. arXiv preprint arXiv:2507.12091, 2025. Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtarik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Proceedings of the 38th International Conference on Machine Learning, pages 6286–6295, 2021. Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In Proceedings of the 38th International Conference on Machine Learning, pages 9224–9234, 2021.

10

A

Proof of Proposition 1

We first prove Proposition 1 for the SSVR-MV Option 1. Use the three one-dimensional functions f1 (x) = f2 (x) = 21 log cosh x + 14 x,

f3 (x) = 21 log cosh x − 12 x.

(A.1)

Since cosh x ≥ e|x| /2, we have log cosh x ≥ |x| − log 2. It follows that f1 (x) = f2 (x) ≥ 12 |x| + 14 x − 12 log 2 ≥ − 12 log 2,

f3 (x) ≥ 12 (|x| − x) − 12 log 2 ≥ − 12 log 2.

Thus each local objective is lower bounded. Their derivatives are f1′ (x) = f2′ (x) = 21 tanh x + 14 ,

f3′ (x) = 21 tanh x − 12 .

Because | tanh x| ≤ 1, all three derivatives have absolute value at most G = 1. Moreover, fj′′ (x) = 1/(2 cosh2 x) ∈ (0, 1/2], so local objectives are 1/2-smooth. Their average and its derivative are f (x) = 21 log cosh x,

h(x) := f ′ (x) = 12 tanh x.

In particular, we observe that x1 = 0 is a global minimizer and |h(x)| ≤ 1/2. Take the deterministic oracle gj (x; ξ) = fj′ (x) whose variance is zero. j Exact initialization gives v1j = fj′ (x1 ). If vt−1 = fj′ (xt−1 ), the local recursion gives vtj = fj′ (xt ) + (1 − β)[fj′ (xt−1 ) − fj′ (xt−1 )] = fj′ (xt ). Induction therefore proves exact local estimates at every iteration for every β ∈ (0, 1]. The signs qtj = S4 (fj′ (xt )) are well defined because |fj′ (xt )| ≤ 1 < 4. Next, to keep the following scalar calculation short, write u = 1/16 and z = h(x)/4. The three sign means at xt = x are z + u, z + u, z − 2u. Expanding the product, (z + u)2 (z − 2u) = (z 2 + 2uz + u2 )(z − 2u) = z 3 − 3u2 z − 2u3 . Consequently the expected vote, denoted by M (x), is M (x) := E[st | xt = x] =

3(1 + u2 )z − z 3 + 2u3 3z − (z + u)2 (z − 2u) = . 2 2

(A.2)

At the minimizer, h(0) = z = 0 and M (0) = u3 > 0. The following derivative bound controls how much this bias can change when the true gradient is small: dM 3 = (1 + u2 − z 2 ), dh 8

0<

dM 3 771 ≤ (1 + u2 ) = . dh 8 2048

(A.3)

Indeed |z| = |h|/4 ≤ 1/8, so 1 + u2 − z 2 > 0. The mean value theorem now gives |M (x) − u3 | ≤

771 |h(x)|. 2048

(A.4)

Next, we control the iterate without assuming it is bounded. Since tanh 1 > 1/2, x ≥ 1 implies that z ≥ u, and x ≤ −1 implies z ≤ −u. The polynomial in (A.2) is increasing in z on [−1/8, 1/8]. Its values at u and −u are, respectively, (3u + 4u3 )/2 > 0 and −3u/2 < 0. Thus xM (x) ≥ 0 for |x| ≥ 1. For |x| < 1, the fact that M (x) is the expectation of a sign gives |M (x)| ≤ 1 and hence xM (x) ≥ −1. Combining the two regions yields xM (x) ≥ −1 for every x. 11

The update xt+1 = xt − ηst and s2t = 1 give E[x2t+1 | xt ] = x2t − 2ηxt M (xt ) + η 2 . Take expectations and sum over t = 1, . . . , K. Since x1 = 0, Ex2K+1 =

K X

−2ηE[xt M (xt )] + η 2 ≤ 2ηK + η 2 K.

(A.5)

t=1

All moments are finite, since for a fixed horizon, |xt | ≤ (t − 1)η on every sample path. Taking expectations gives Ext+1 − Ext = −ηEM (xt ). After summing and using x1 = 0, K ExK+1 1 X EM (xt ) = − . K t=1 ηK

Cauchy–Schwarz and (A.5) imply K 1 X

K t=1

q

EM (xt ) ≤

Ex2K+1 ηK

s

≤

2 1 + . ηK K

(A.6)

This argument controls the average vote even though individual iterates need not converge. Finally, the triangle inequality and (A.6) give u3 ≤

K K 1 X 1 X EM (xt ) + u3 − EM (xt ) K t=1 K t=1

s

K 2 1 1 X + + E|u3 − M (xt )| ηK K K t=1

s

K 2 1 771 1 X E|h(xt )|. + + ηK K 2048 K t=1

≤ ≤

By independent uniform output selection, the final average is E|f ′ (xτ )|. Since u3 = 1/4096, rearranging gives the finite-horizon bound 2048 1 E|f ′ (xτ )| ≥ − 771 4096 "

s

2 1 + . ηK K #

(A.7)

For η = Θ(K −1/2 ), we have ηK → ∞, so the square-root term tends to zero. Taking the lower limit and using 2048/(771 · 4096) = 1/1542 proves (15).

B

Proofs for the stochastic results

We first prove a tracking estimate that retains the actual model movement. Throughout, a = 1 + ω, c = a/n, K counts model updates, and B0 is the initialization batch per worker.

12

B.1

Moments and server tracking

For t ≥ 2, let Ft−1 contain all randomness generated before the current worker samples and compression calls. Write Et [·] = E[· | Ft−1 ]. First, unbiased compression controls second moments. Conditional on an input v, expansion of the squared norm gives E[∥Q(v)∥22 | v] = ∥v∥22 + 2⟨v, E[Q(v) − v | v]⟩ + E[∥Q(v) − v∥22 | v] ≤ a∥v∥22 . The middle term is zero by unbiasedness. Applying ∥u + v∥22 ≤ 2∥u∥22 + 2∥v∥22 to the decomposition in (16), we obtain Et ∥hjt ∥22 ≤ 2β 2 Et ∥gj (xt ; ξtj )∥22 + 2(1 − β)2 Et ∥gj (xt ; ξtj ) − gj (xt−1 ; ξtj )∥22 ≤ 2β 2 H 2 + 2L2 ∥xt − xt−1 ∥22 .

(B.1)

The last inequality uses mean-squared smoothness and (1 − β)2 ≤ 1. j Next, we control the initial error. Write Yj,b = Q(gj (x1 ; ξ1,b )) for the message from sample b at worker j. Repeated conditioning gives EYj,b = ∇fj (x1 ),

E∥Yj,b ∥22 ≤ aH 2 .

Its centered second moment therefore satisfies E∥Yj,b − ∇fj (x1 )∥22 = E∥Yj,b ∥22 − ∥∇fj (x1 )∥22 ≤ aH 2 . Distinct initialization messages use independent samples and compression calls. For (j, b) ̸= (k, r), their centered cross term is consequently E⟨Yj,b − ∇fj (x1 ), Yk,r − ∇fk (x1 )⟩ = 0. Expanding the squared norm of the average gives B

E1 =

n X 0 1 X cH 2 nB0 aH 2 2 . = E∥Y − ∇f (x )∥ ≤ j 1 j,b 2 2 2 B0 n2 B0 j=1 b=1 n2 B0

This explains why each initialization sample is compressed separately. We now derive the tracking recursion. For t ≥ 2, define the centered decoded error δtj = Q(hjt ) − [∇fj (xt ) − (1 − β)∇fj (xt−1 )]. Unbiasedness of the oracle and of the compressor implies Et Q(hjt ) = Et hjt = ∇fj (xt ) − (1 − β)∇fj (xt−1 ),

Et δtj = 0.

Subtracting ∇f (xt ) from (17) gives the exact identity et = (1 − β)et−1 +

n 1X δj . n j=1 t

(B.2)

The conditional squared norm expands as Et ∥et ∥22 = (1 − β)2 ∥et−1 ∥22 + +

2(1 − β) X ⟨et−1 , Et δtj ⟩ n j

1 X 2 X j 2 E ∥δ ∥ + Et ⟨δtj , δtk ⟩. t 2 t 2 2 n j n j<k 13

(B.3)

The second term is zero because et−1 is fixed under conditioning. The last term is zero because the current worker errors are conditionally independent and centered. For each remaining variance, centering and (B.1) give Et ∥δtj ∥22 = Et ∥Q(hjt )∥22 − ∥∇fj (xt ) − (1 − β)∇fj (xt−1 )∥22 ≤ aEt ∥hjt ∥22 ≤ 2aβ 2 H 2 + 2aL2 ∥xt − xt−1 ∥22 .

(B.4)

Taking full expectations and using (1 − β)2 ≤ 1 − β yields Et ≤ (1 − β)Et−1 + 2cβ 2 H 2 + 2cL2 E∥xt − xt−1 ∥22 .

(B.5)

For completeness, summing this recursion from t = 2 to K gives β

K X

Et ≤ E1 − (1 − β)EK + 2cβ 2 H 2 (K − 1) + 2cL2

t=1

K−1 X

E∥xt+1 − xt ∥22

t=1

≤ E1 + 2cβ 2 H 2 K + 2cL2

K−1 X

(B.6)

E∥xt+1 − xt ∥22 .

t=1

After division by βK, this proves EK ≤

X cH 2 2cL2 K−1 + 2cβH 2 + E∥xt+1 − xt ∥22 . B0 βK βK t=1

(B.7)

For DVR-Sign, ∥xt+1 − xt ∥22 = η 2 d. Substituting this identity into (B.5) and (B.7) proves (23) and (24). The DVR-Q specialization is given separately in Appendix B.3.

B.2

The ℓ1 guarantee

Let g be a true gradient and z an arbitrary estimate. If Sign(gk ) ̸= Sign(zk ) and gk = ̸ 0, then zk is on the opposite side of zero or is zero, and therefore |gk | ≤ |gk − zk |. Coordinates with gk = 0 contribute zero. It follows that ∥g∥1 − ⟨g, Sign(z)⟩ = 2 ≤2

d X k=1 d X

|gk |1{Sign(gk ) ̸= Sign(zk )} √ |gk − zk | = 2∥g − z∥1 ≤ 2 d∥g − z∥2 .

(B.8)

k=1

Next, we sum the objective decreases. Mean-squared smoothness and Jensen’s inequality give ∥∇fj (x) − ∇fj (y)∥2 = ∥E[gj (x; ξ) − gj (y; ξ)]∥2 ≤ E∥gj (x; ξ) − gj (y; ξ)∥22

1/2

≤ L∥x − y∥2 .

Averaging over workers shows that f is also L-smooth. Applying its smoothness inequality to the deterministic sign update gives Lη 2 ∥Sign(zt )∥22 2 √ Lη 2 d ≤ f (xt ) − η∥∇f (xt )∥1 + 2η d∥et ∥2 + . 2

f (xt+1 ) ≤ f (xt ) − η⟨∇f (xt ), Sign(zt )⟩ +

14

(B.9)

Taking expectations and summing from t = 1 to K, we have η

K X

K √ X KLη 2 d E∥∇f (xt )∥1 ≤ ∆f + 2η d E∥et ∥2 + . 2 t=1 t=1

For the error sum, Jensen’s inequality followed by Cauchy–Schwarz gives K 1 X

K t=1

E∥et ∥2 ≤

v u q K X 1u t Et ≤ K Et = E K .

K p 1 X

K t=1

K

t=1

Dividing the previous descent inequality by ηK proves K ∆f Lηd 1 X + + 2 d EK . E∥∇f (xt )∥1 ≤ K t=1 ηK 2

q

(B.10)

Because τ is uniform on {1, . . . , K} and independent of the run, its expected gradient norm equals the average on the left. This proves Theorem 2. For Corollary 3, choose   1 1 Hu1 u1 = √ , β = u1 , η = √ , B0 = 2 . (B.11) u1 K K + c1/3 K 2/3 L d These are admissible because 0 < u1 ≤ K −1/2 ≤ 1 and B0 ≥ 1. Inserting the parameters into (24) controls each contribution separately: cH 2 ≤ cH 2 u1 , B0 βK

2cL2 η 2 d = 2cH 2 u1 . β

2cH 2 β = 2cH 2 u1 ,

Thus E K ≤ 5cH 2 u1 , and (B.10) becomes √  L∆f √ √  Hu1 E∥∇f (xτ )∥1 ≤ d + + 2 5H cu1 . Hu1 K 2 The definition of u1 gives 1 = K −1/2 + c1/3 K −1/3 , u1 ≤ K −1/2 , u1 ≤ c−1/3 K −2/3 . u1 K √ In particular, the third inequality implies cu1 ≤ c1/3 K −1/3 . Substitution proves the explicit bound E∥∇f (xτ )∥1 ≤

√

"

d

L∆f H + H 2



K

−1/2

+



√ L∆f + 2 5H H



c K

1/3 #

.

(B.12)

Keeping L, H, ∆f fixed and recalling c = (1 + ω)/n gives (27). Finally, we specify initialization and a target accuracy. Squaring the denominator of u1 yields the exact batch size l m B0 = (1 + c1/3 K 1/6 )2 = Θ(1 + c2/3 K 1/3 ). (B.13) To verify the order including the ceiling, use 1 + b2 ≤ (1 + b)2 ≤ 2(1 + b2 ) for b ≥ 0, and y ≤ ⌈y⌉ ≤ y + 1 ≤ 2y for y ≥ 1. For any ϵ > 0, the following explicit integer horizon suffices: ( & ' & ') √ 4d(L∆f /H + H/2)2 8cd3/2 (L∆f /H + 2 5H)3 K = max 1, , . (B.14) ϵ2 ϵ3 The second entry makes the first term of (B.12) at most ϵ/2: square that desired inequality and solve for K. The third entry does the same for the second term by cubing it. Their sum is therefore at most ϵ. With fixed L, H, ∆f , d cd3/2 K =O 1+ 2 + 3 ϵ ϵ 15

!

.

(B.15)

B.3

The ℓ2 guarantee

Let Gt denote the history after the server has formed zt and before drawing that downlink. Thus E[Q(zt ) | Gt ] = zt ,

E[∥Q(zt )∥22 | Gt ] ≤ a∥zt ∥22 .

(B.16)

For clarity, write Zt = E∥zt ∥22 only within this proof. The actual movement satisfies E∥xt+1 − xt ∥22 = η 2 E∥Q(zt )∥22 ≤ aη 2 Zt . Inserting it into the general tracking bounds gives Et ≤ (1 − β)Et−1 + 2cβ 2 H 2 + 2caL2 η 2 Zt−1 EK ≤

(t ≥ 2),

X cH 2 2caL2 η 2 K−1 + 2cβH 2 + Zt . B0 βK βK t=1

(B.17) (B.18)

Unlike the sign update, this movement becomes small when the tracker becomes small. We must retain its dependence on Zt in the descent calculation. By L-smoothness and (B.16), E[f (xt+1 ) | Gt ] ≤ f (xt ) − η⟨∇f (xt ), zt ⟩ +

Laη 2 ∥zt ∥22 . 2

(B.19)

The exact inner-product identity 2⟨∇f (xt ), zt ⟩ = ∥∇f (xt )∥22 + ∥zt ∥22 − ∥et ∥22 then gives, after taking full expectations, η η η Ef (xt+1 ) ≤ Ef (xt ) − E∥∇f (xt )∥22 − (1 − Laη)Zt + Et . 2 2 2

(B.20)

Summing from t = 1 to K, using Ef (xK+1 ) ≥ f∗ , and dividing by ηK/2 yields K K 2∆f 1 − Laη X 1 X E∥∇f (xt )∥22 + Zt ≤ + EK . K t=1 K ηK t=1

Substitute (B.18) and use

PK−1 t=1

Zt ≤

t=1 Zt . Moving this last contribution to the left gives

PK

K 1 X 2caL2 η 2 E∥∇f (xt )∥22 + 1 − Laη − K t=1 β

≤

(B.21)

!

K 1 X Zt K t=1

2∆f cH 2 + + 2cβH 2 . ηK B0 βK

(B.22)

The independent uniform output τ turns the first average into E∥∇f (xτ )∥22 . If Laη ≤ 1/2 and β ≥ 4caL2 η 2 , both subtracted terms in the tracker coefficient are at most 1/2, so the coefficient is nonnegative. This proves Theorem 4. The cancellation explains why we did not replace Zt by a gradient-magnitude bound earlier. We next prove Corollary 5. Recall c = a/n and choose r = (K/n2 )1/3 ,

η=

1 , 2La(1 + r) 16

β=

1 , n(1 + r)2

B0 = ⌈1 + r⌉.

(B.23)

These choices satisfy 0 < β ≤ 1 for every n, K ≥ 1. Direct substitution gives Laη =

1 , 2(1 + r)

4caL2 η 2 =

1 = β. n(1 + r)2

The tracker coefficient in (28) is consequently 1 1 r − = ≥ 0. 2(1 + r) 2 2(1 + r)

1−

We can drop that term and bound the three remaining terms separately: 2∆f 4La∆f (1 + r) = , ηK K cH 2 aH 2 (1 + r)2 aH 2 (1 + r) = ≤ , B0 βK B0 K K 2aH 2 2aH 2 r3 2aH 2 r = ≤ . 2cβH 2 = 2 n (1 + r)2 K(1 + r)2 K

(B.24)

The second bound uses B0 ≥ 1 + r. The last uses r3 = K/n2 and r2 ≤ (1 + r)2 . Adding the bounds and using r/K = (nK)−2/3 proves "

E∥∇f (xτ )∥22 ≤ a Jensen’s inequality and

√

u+v ≤

√

u+

√

4L∆f + H 2 4L∆f + 3H 2 + . K (nK)2/3 #

v for u, v ≥ 0 give

E∥∇f (xτ )∥2 ≤

q

E∥∇f (xτ )∥22

≤

q

+ H2

4L∆f

(B.25)

r

√ q a a 2 + 4L∆f + 3H . K (nK)1/3

(B.26)

This proves (30). To obtain E∥∇f (xτ )∥22 ≤ ϵ2 , and hence E∥∇f (xτ )∥2 ≤ ϵ, it suffices to choose [2a(4L∆f + 3H 2 )]3/2 2a(4L∆f + H 2 ) , K = max 1, ϵ2 nϵ3 (

' &

&

')

.

(B.27)

The second entry makes the first term in (B.25) at most ϵ2 /2. Raising the desired bound on its second term to the power 3/2 gives the third entry. Their sum is at most ϵ2 . For fixed L, H, ∆f , the resulting update and per-worker sample complexities are a a3/2 K =O 1+ 2 + 3 ϵ nϵ

C

Proofs for finite sums

C.1

Exact computation

!

.

For K updates and an integer refresh period q ≥ 1, the times 1, 1 + q, 1 + 2q, . . . give r =1+



K −1 K = . q q 

17





(B.28)

Each refresh evaluates every component once for M = nm evaluations. At each of the K − r ordinary updates, every worker evaluates one component at two points. Therefore Ngrad = M r + 2n(K − r),

Ngrad,j = mr + 2(K − r).

(C.1)

For q = m, the inequality r ≤ 1 + K/m gives K Ngrad ≤ M 1 + m 

C.2



+ 2nK = M + 3nK.

(C.2)

Tracking error between exact refreshes

Lemma C.1. For the estimator (32), the error is zero at each refresh t0 = 1+kq. For t0 ≤ t < t0 +q, we have t aL2 X 2 E∥zt − ∇f (xt )∥2 ≤ E∥xs − xs−1 ∥22 . (C.3) n s=t +1 0

Deterministic sign updates therefore give the bound aL2 η 2 d(q − 1)/n. For updates xt+1 = xt − ηQ(zt ), with a fresh common downlink satisfying the same compressor assumption, K K a2 L2 η 2 (q − 1) 1 X 1 X 2 E∥zt − ∇f (xt )∥2 ≤ E∥zt ∥22 . K t=1 n K t=1

(C.4)

Proof. At an ordinary iteration, condition on the history through xt and before the current component indices and compression calls. Denote this conditional expectation by Et ; the points xt , xt−1 and the previous estimate zt−1 are fixed under this conditioning. Write Xj = Q ∇fj,ij (xt ) − ∇fj,ij (xt−1 ) ,

t

t

µj = Et Xj = ∇fj (xt ) − ∇fj (xt−1 ). Uniform component sampling and unbiased compression give the expression for µj . The same component is evaluated at both points. Thus Et ∥Xj ∥22 ≤

m a X ∥∇fj,i (xt ) − ∇fj,i (xt−1 )∥22 ≤ aL2 ∥xt − xt−1 ∥22 . m i=1

The first inequality uses (7); the second is component smoothness. Since Xj − µj is centered, Et ∥Xj − µj ∥22 = Et ∥Xj ∥22 − ∥µj ∥22 ≤ aL2 ∥xt − xt−1 ∥22 . Note that the component indices and compressor calls are conditionally independent across all n workers. For j ̸= k, this independence and centering imply Et ⟨Xj − µj , Xk − µk ⟩ = ⟨Et (Xj − µj ), Et (Xk − µk )⟩ = 0. Consequently, Et

n 1X (Xj − µj ) n j=1

2

n 1 X aL2 = 2 Et ∥Xj − µj ∥22 ≤ ∥xt − xt−1 ∥22 . n j=1 n

The averaging is over all workers and n−1

j µj = ∇f (xt ) − ∇f (xt−1 ) exactly.

P

18

Next, let et = zt − ∇f (xt ). The estimator recursion gives et = et−1 +

n 1X (Xj − µj ). n j=1

The new sum has zero conditional mean, and et−1 is fixed under Et . Expanding the square yields n n 1X 1X Et (Xj − µj ) + Et (Xj − µj ) Et ∥et ∥22 = ∥et−1 ∥22 + 2 et−1 , n j=1 n j=1

+

*

≤ ∥et−1 ∥22 +

2

aL2 ∥xt − xt−1 ∥22 . n

At a refresh, zt0 = ∇f (xt0 ), so et0 = 0 on every sample path. Taking total expectations and applying the recursion successively at t0 + 1, . . . , t gives E∥et ∥22 ≤ E∥et0 ∥22 +

t aL2 X E∥xs − xs−1 ∥22 . n s=t +1 0

This proves (C.3). For DVR-Sign-FS, each summand is η 2 d, and there are at most q − 1 summands. For DVR-Q-FS, condition on the history Gs after all uplinks in iteration s and before the server’s new compression call. Then E[∥xs+1 − xs ∥22 | Gs ] = η 2 E[∥Q(zs )∥22 | Gs ] ≤ aη 2 ∥zs ∥22 . Substituting its total expectation in (C.3) yields E∥et ∥22 ≤

t−1 a2 L2 η 2 X E∥zs ∥22 . n s=t0

Let t1 = min{t0 + q − 1, K} be the last iteration in this interval between refreshes. Reversing the order of the finite sums gives t1 −1 a2 L2 η 2 X 2 E∥et ∥2 ≤ (t1 − s)E∥zs ∥22 n s=t0 t=t0 t1 X

t

≤

1 a2 L2 η 2 (q − 1) X E∥zs ∥22 . n s=t0

These intervals are disjoint. Summing over them and dividing by K proves (C.4).

C.3

Descent for the ℓ1 criterion

Proof of Theorem 6. The deterministic sign st = Sign(zt ) has squared norm d. Thus the deterministic sign case of Lemma C.1 proves (34). To translate this into stationarity, smoothness gives Lη 2 d f (xt+1 ) ≤ f (xt ) − η⟨∇f (xt ), Sign(zt )⟩ + . 2 By (19), √ ⟨∇f (xt ), Sign(zt )⟩ ≥ ∥∇f (xt )∥1 − 2 d∥zt − ∇f (xt )∥2 . 19

Substituting and rearranging before taking expectations gives √ Lη 2 d ηE∥∇f (xt )∥1 ≤ Ef (xt ) − Ef (xt+1 ) + 2η dE∥zt − ∇f (xt )∥2 + . 2 Sum this inequality over t = 1, . . . , K. The objective terms telescope to f (x1 ) − Ef (xK+1 ) ≤ f (x1 ) − f∗ = ∆f ≤ ∆0 . After division by ηK, we obtain √ K K 1 X ∆0 Lηd 2 d X E∥∇f (xt )∥1 ≤ + + E∥zt − ∇f (xt )∥2 K t=1 ηK 2 K t=1 s

aL2 η 2 d(q − 1) n

s

a(q − 1)  . n

√ ∆0 Lηd ≤ + +2 d ηK 2 

∆0 d = + Lη  + 2d ηK 2



q

In the second line, E∥zt − ∇f (xt )∥2 ≤ E∥zt − ∇f (xt )∥22 and Lemma C.1 bound each summand. Uniformity of τ implies that the average on the left equals E∥∇f (xτ )∥1 . This proves (35). Finally, J1 ≥ d/2 > 0, so the positive stepsize is well defined and LηJ1 = ϵ/2. If ∆0 > 0, the choice of K gives ∆0 2L∆0 J1 ϵ = ≤ . ηK ϵK 2

Complexity

Set q = m. The target-accuracy choice gives, for every ϵ > 0, 

4L∆0 J1 4L∆0 d  1 K ≤1+ =1+ +2 2 ϵ ϵ2 2

s



a(m − 1)  . n

For the total oracle count, multiply the coefficient by n: nJ1 =

q √ dn dn + 2d an(m − 1) ≤ + 2d aM . 2 2

(C.5)

The inequality uses n(m − 1) ≤ nm = M . Substituting the iteration bound into (C.2) now gives 12L∆0 nJ1 ϵ2  √ 12L∆0 d n ≤ 4M + + 2 aM . ϵ2 2

Ngrad ≤ M + 3n +

Here n ≤ M absorbs the extra update arising from the ceiling.

C.4

Descent for the ℓ2 criterion

Proof of Theorem 8. Condition on the post-uplink history Gt , which includes xt and zt and precedes the server’s new call to Q. Unbiasedness and the second-moment bound give E[Q(zt ) | Gt ] = zt ,

E[∥Q(zt )∥22 | Gt ] ≤ a∥zt ∥22 . 20

Since xt+1 = xt − ηQ(zt ), smoothness implies E[f (xt+1 ) | Gt ] ≤ f (xt ) − η⟨∇f (xt ), zt ⟩ +

Laη 2 ∥zt ∥22 . 2

The inner product has the exact decomposition 2⟨∇f (xt ), zt ⟩ = ∥∇f (xt )∥22 + ∥zt ∥22 − ∥zt − ∇f (xt )∥22 . Substitute this identity, take total expectations, and rearrange: η η η E∥∇f (xt )∥22 + (1 − Laη)E∥zt ∥22 ≤ Ef (xt ) − Ef (xt+1 ) + E∥zt − ∇f (xt )∥22 . 2 2 2 Sum the last inequality over t = 1, . . . , K and divide by ηK/2. The objective values telescope, and f (x1 ) − Ef (xK+1 ) ≤ ∆0 . Applying (C.4) to the right side gives K K 1 X a2 L2 η 2 (q − 1) 1 X E∥∇f (xt )∥22 + 1 − Laη − E∥zt ∥22 K t=1 n K t=1

"

≤ Write s =

p

#

2∆0 . ηK

(C.6)

(q − 1)/n ≥ 0. The choice in (38) gives Laη +

a2 L2 η 2 (q − 1) 1 s2 1 1 1 = + = + ≤ . 2 2 n 2(1 + s) 4(1 + s) 4 4(1 + s) 2

Thus the bracket in (C.6) is at least 1/2, and we may discard its nonnegative contribution. Since 2∆0 /(ηK) = 4L∆0 JQ /K, we obtain the squared-norm bound in (39). The independent uniform choice of τ identifies its expectation with the averaged left side. Cauchy–Schwarz then gives s

E∥∇f (xτ )∥2 ≤

Complexity

q

E∥∇f (xτ )∥22 ≤ 2

For q = m, we have JQ = a(1 +

p

L∆0 JQ . K

(m − 1)/n). Hence

4L∆0 JQ 4aL∆0 K ≤1+ =1+ 1+ 2 ϵ ϵ2 "

r

m−1 , n

which proves (40). To count gradients, use 

nJQ = a n +



q

n(m − 1) ≤ a(n +

√ M ).

Then (C.2) yields 12L∆0 nJQ ϵ2 √ 12aL∆0 ≤ 4M + (n + M ). 2 ϵ

Ngrad ≤ M + 3n +

21

#