SLowcalSGD : Slow Query Points Improve Local-SGD for Stochastic Convex Optimization

Authors: tehila  dahan
kfir y levy
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 13:54:31

Abstract: We consider  distributed learning scenarios where $M$ machines interact with a parameter server along several communication rounds in order to minimize a joint objective function. 
Focusing on the heterogeneous case, where different machines may draw samples from different data-distributions, we design the first local update method that provably benefits over the two most prominent distributed baselines: namely Minibatch-SGD and Local-SGD. 
Key to our approach is a slow querying technique  that we customize to the distributed setting, which in turn enables a better mitigation of the bias caused by local updates.

Main paper: 
 introduction: 
 Federated Learning (FL) is a framework that enables huge scale collaborative learning among a large number of heterogeneous1 clients (or machines). FL may potentially promote fairness among participants, by allowing clients with small scale datasets to participate in the learning process and affect the resulting model. Additionally, participants are not required to directly share data, which may improve privacy. Due to these reasons, FL has gained popularity in the past years, and found use in applications like voice recognition [1, 4] , fraud detection [2] , drug discovery [3] , and more [33] .The two most prominent algorithmic approaches towards federated learning are Minibatch-SGD [10] and Local-SGD (a.k.a. Federated-Averaging) [26, 27, 32] . In Minibatch-SGD all machines (or clients) always compute unbiased gradient estimates of the same query points, while using large batch sizes; and it is well known that this approach is not degraded due to data heterogeneity [36] . On the downside, the number of model updates made by Minibatch-SGD may be considerably smaller compared to the number of gradient queries made by each machine; which is due to the use of minibatches. This suggests that there may be room to improve over this approach by employing local update methods like Local-SGD, where the number of model updates and the number of gradient queries are the same. And indeed, in the past years, local update methods have been extensively investigated, see e.g. [18] and references therein.We can roughly divide the research on FL into two scenarios: the homogeneous case, where it is assumed that the data on each machine is drawn from the same distribution; and to the more realistic heterogeneous case where it is assumed that data distributions may vary between machines.For the homogeneous case it was shown in [35, 13] that the standard Local-SGD method is not superior to Minibatch-SGD. Nevertheless, [38] have designed an accelerated variant of Local-SGD that provably benefits over the Minibatch baseline. These results are established for the fundamental Stochastic Convex Optimization (SCO) setting, which assumes that the learning objective is convex.Table 1 : We compare the best known guarantees for parallel learning, to our SLowcal-SGD approach for the heterogeneous SCO case. The bolded term in the Rate column is the one that compares least favourably against Minibatch SGD. Where G and G * relate to the dissimilarity measures that are defined in Equations ( 1) and (3) . The R min column presents the minimal number of communication rounds that are required to obtain a linear speedup (we fixed values of K, M and take σ = 1). Note that we omit methods that do not enable a wall-clock linear speedup with M , e.g. [28, 29] .Rate R min (σ = 1) MiniBatch SGD [10] 1R + σ √ M KR M KAccelerated MiniBatch SGD [10, 24] 1R 2 + σ √ M KR (M K) 1/3Local SGD [36] G 2/3R 2/3 + σ 2/3 ( √ KR) 2/3 + 1 KR + σ √ M KR G 4 • (M K) 3 + M 3 K SCAFFOLD [20] 1 R + σ √ M KR M K(This paper)σ 1/2 +G 1/2 * K 1/4 R + 1 KR + 1 K 1/3 R 4/3 + 1 R 2 + σ √ M KR G * • M K 1/2 + M K 1/2Lower Bound: Local-SGD [38] G2/3 * R 2/3 + σ 2/3 * ( √ KR) 2/3 + 1 KR + σ √ M KR G 4 * • (M K) 3 + M 3 KSimilarly to the homogeneous case, it was shown in [36, 13] that Local-SGD is not superior to Minibatch-SGD in heterogeneous scenarios. Nevertheless, several local approaches that compare with the Minibatch baseline were designed in [20, 14] . Unfortunately, we have so far been missing a local method that provably benefits over the Minibatch baseline in the heterogeneous SCO setting.Our work focuses on the latter heterogeneous SCO setting, and provide a new Local-SGD-style algorithm that provably benefits over the minibatch baseline. Our algorithm named SLowcal-SGD, builds on customizing a recent technique for incorporating a slowly-changing sequence of query points [9, 21] , which in turn enables to better mitigate the bias induced by the local updates. Curiously, we also found importance weighting to be crucial in order to surpass the minibatch baseline.In Table 1 we compare our results to the state-of-the-art methods for the heterogeneous SCO setting.We denote M to be the number of machines, K is the number of local updates per round, and R is the number of communications rounds. Additionally, G (or G * ) measures the dissimilarity between machines. Our table shows that Local-SGD requires much more communication rounds compared to Minibatch-SGD, and that the dissimilarity G (or G * ) substantially degrades its performance. Conversely, one can see that even if the dissimilarity measure is G * = O(1), our approach SLowcal-SGD still requires less communication rounds compared to Minibatch-SGD.Similarly to the homogeneous case, accelerated-Minibatch-SGD [10, 24] , obtains the best performance among all current methods, and it is still open to understand whether one can outperform this accelerated minibatch baseline. In App. A we elaborate on the computations of R min in Table 1 . Related Work. We focus here on centralized learning problems, where we aim to employ M machines in order to minimize a joint learning objective. We allow the machines to synchronize during R communication rounds through a central machine called the Parameter Server (PS); and allow each machine to draw K samples and perform K local gradient computations in every such communication round. We assume that each machine i may draw i.i.d. samples from a distribution D i , which may vary between machines.The most natural approach in this context is Minibatch-SGD, and its accelerate variant [10] , which have been widely adopted both in academy and in industry, see e.g. [16, 31, 37] . Local update methods like Local-SGD [27] , have recently gained much popularity due to the rise of FL, and have been extensively explored in the past years.Focusing on the SCO setting, it is well known that the standard Local-SGD is not superior (actually in most regimes it is inferior) to Minibatch-SGD [35, 36, 13] . Nevertheless, [38] devised a novel accelerated local approach that provably surpasses the Minibatch baseline in the homogeneous case.The heterogeneous SCO case has also been extensively investigated, with several original and elegant approaches [23, 22, 20, 36, 29, 14, 28, 30] . Nevertheless, so far we have been missing a local approach that provably benefits over Minibatch-SGD. Note that [29, 28] improve the communication complexity with respect to the condition number of the objective; However their performance does not improve as we increase the number of machines M2 , which is inferior to the minibatch baseline.The heterogeneous non-convex setting was also extensively explored [20, 19, 14] ; and the recent work of [30] has developed a novel algorithm that provably benefits over the minibatch baseline in this case. The latter work also provides a lower bound which demonstrates that their upper bound is almost tight. Finally, for the special case of quadratic loss functions, it was shown in [35] and in [20] that it is possible to surpass the minibatch baseline.It is important to note that excluding the special case of quadratic losses, there does not exist a local update algorithm that provably benefits over accelerated-Minibatch-SGD [10] . And the latter applies to both homogeneous and heterogeneous SCO problems.Our local update algorithm utilizes a recent technique of employing slowly changing query points in SCO problems [9] . The latter has shown to be useful in designing universal accelerated methods [21, 12, 5] , as well as in improving asynchronous training methods [6] . 
setting: parallel stochastic optimization: 
 We consider Parallel stochastic optimization problems where the objective f : R d → R is convex and is of the following form,f (x) := 1 M i∈[M ] f i (x) := 1 M i∈[M ] E z i ∼Di f i (x; z i ) .Thus, the objective is an average of M functions {f i : R d → R} i∈[M ] , and each such f i (•) can be written as an expectation over losses f i (•, z i ) where the z i are drawn from some distribution D i which is unknown to the learner. For ease of notation, in what follows we will not explicitly denote E z i ∼Di but rather use E to denote the expectation w.r.t. all randomization.We assume that there exist M machines (computation units), and that each machine may independently draw samples from the distribution D i , and can therefore compute unbiased gradient estimates to the gradients of f i (•). Most commonly, we allow the machines to synchronize during R communication rounds through a central machine called the Parameter Server (PS); and allow each machine to perform K local computations in every such communication round.We consider first order optimization methods that iteratively employ samples and generate a sequence of query points and eventually output a solution x output . Our performance measure is the expected excess loss,ExcessLoss := E[f (x output )]-f (w * ), where the expectation is w.r.t. the randomization of the samples, andw * is a global minimum of f (•) in R d , i.e., w * ∈ arg min x∈R d f (x).More concretely, at every computation step, each machine i ∈ [M ] may draw a fresh sample z i ∼ D i , and compute a gradient estimate g at a given point x ∈ R d as follows, g := ∇f i (x, z i ) . and note that E[g|x] = ∇f i (x), i.e. g is an ubiased estimate of ∇f i (x).General Parallelization Scheme. A general scheme for parallel stochastic optimization is described in Alg. 1. It can be seen that the PS communicates with the machines along R communication rounds. In every round r ∈ [R] the PS distributes an anchor point Θ r which is a starting point for the local computations in that round. Based on Θ r each machine performs K local gradient computations based on K i.i.d. draws from D i , and yields a message Φ i r . At the end of round r the PS aggregates the messages from all machines and updates the anchor point Θ r+1 . Finally, after the last round, the PS outputs x output , which is computed based on the anchor points {Θ r } R r=1 . Ideally, one would hope that using M machines in parallel will enable to accelerate the learning process by a factor of M . And there exists a rich line of works that have shown that this is indeed possible to some extent, depending on K, R, and on the parallelization algorithm.Next, we describe the two most prominent approaches to first-order Parallel Optimization, (i) Minibatch SGD: In terms of Alg. 1, one can describe Minibatch-SGD as an algorithm in which the PS sends a weight vector x r ∈ R d in every round as the anchor point Θ r . Based on that anchor Θ r := x r , each machine i computes an unbiased gradient estimate based on K independent samples from D i , i.e. g i r := 1K K k=1 ∇f i (x r , z i Kr+k ), and communicates g i r as the message Φ i r to the PS. The latter aggregates the messages {Φ i r := g i r } i∈[M ] and compute the next anchor point x r+1 ,x r+1 = x r -η • 1 M i∈[M ] g i r ,where η > 0 is the learning rate of the algorithm. The benefit in this approach is that all machines always compute gradient estimates at the same anchor points {x r } r , which highly simplifies its analysis. On the downside, in this approach the number of gradient updates R is smaller compared to the number of stochastic gradient computations made by each machine which is KR. This gives the hope that there is room to improve upon Minibatch SGD, by mending this issue.(ii) Local SGD: In terms of Alg. 1, one can describe Local-SGD as an algorithm in which the PS sends a weight vector x rK ∈ R d in every round r ∈ [R] as the anchor information Θ r . Based on the anchor Θ r := x rK , each machine performs a sequence of local gradient updates based on K independent samples from D i as follows, ∀k ∈ [K],x i rK+k+1 = x i rK+k -η • ∇f i (x i rK+k , z i rK+k ) ,where for all machines i ∈ [M ] we initialize x i rK = x rK := Θ r , and η > 0 is the learning rate of the algorithm. At the end of round r each machine communicates x i (r+1)K as the message Φ i r to the PS and the latter computes the next anchor as follows,Θ r+1 := x (r+1)K = 1 M i∈[M ]x i (r+1)K .In local SGD the number of gradient steps is equal to the number of stochastic gradient computations made by each machine which is KR. The latter suggests that such an approach may potentially surpass Minibatch SGD. Nevertheless, this potential benefit is hindered by the bias that is introduced between different machines during the local updates. And indeed, as we show in Table 1 , this approach is inferior to Minibatch SGD in the prevalent case where σ = O(1).Assumptions. We assume that f (•) is convex, and that the f i (•) are smooth i.e. ∃L > 0 such,∥∇f i (x) -∇f i (y)∥ ≤ L∥x -y∥ , ∀i ∈ [M ] , ∀x, y ∈ R dWe also assume that variance of the gradient estimates is bounded, i.e. that there exists σ > 0 such,E∥∇f i (x; z) -∇f i (x)∥ 2 ≤ σ 2 , ∀x ∈ R d , ∀i ∈ [M ] .Letting w * be a global minimum of f (•), we assume there exist G * ≥ 0 such that,EQUATIONThe above assumption together with the smoothness and convexity imply (see App. B) ,EQUATIONA stronger dissimilarity assumption that is often used in the literature is the following,EQUATIONNotation: For {y t } t we denote y t1:t2 := t2 τ =t1 y τ . For N ∈ Z + we denote [N ] := {0, . . . , N -1}. 
our approach: 
 Section 3.1 describes a basic (single machine) algorithmic template called Anytime-GD. Section 3.2 describes our SLowcal-SGD algorithm, which is a Local-SGD style algorithm in the spirit of Anytime GD. We describe our method in Alg. 2, and state its guarantees in Thm. 2.The standard GD algorithm computes a sequence of iterates {w t } t∈[T ] and queries the gradients at theses iterates. It was recently shown that one can design a GD-style scheme that computes a sequence of iterates {w t } t∈[T ] yet queries the gradients at a different sequence {x t } t∈[T ] which may be slowly-changing, in the sense that ∥x t+1 -x t ∥ may be considerably smaller than ∥w t+1 -w t ∥.Concretely, the Anytime-GD algorithm [9, 21] that we describe in Equations ( 4) and ( 5), employs a learning rate η > 0 and a sequence of non-negative weights {α t } t . The algorithm maintains two sequences {w t } t , {x t } t that are updated as follows ∀t,EQUATIONand then,EQUATIONIt can be shown that the above implies that x t+1 = 1 α0:t+1 t+1 τ =0 α τ w τ , i.e. the x t 's are weighted averages of the w t 's. Thus, at every iterate the gradient g t is queried at x t which is a weighted average of past iterates, and then w t+1 is updated similarly to GD with a weight α t on the gradient g t . Moreover, at initialization x 0 = w 0 .Curiously, it was shown in [9] that Anytime-GD obtains the same convergence rates as GD for convex loss functions (both smooth and non-smooth). It was further shown and that one can employ a stochastic version (Anytime-SGD) where we query noisy gradients at x t instead of the exact ones, and that approach performs similarly to SGD. Slowly changing query points. A recent work [6] , demonstrates that if we use projected Anytime-SGD, i.e. project the w t sequence to a given bounded convex domain; then one can immediately show that for both α t = 1 and α t = t + 1 we obtain ∥x t+1 -x t ∥ ≤ 2D/t, where D is the diameter of the convex domain. Conversely, for standard SGD we have ∥w t+1 -w t ∥ ≤ η∥g t ∥, where g t here is a (possibly noisy) unbiased estimate of ∇f (w t ). Thus, while the change between consecutive SGD queries is controlled by η which is usually ∝ 1/ √ t, and by magnitude of stochastic gradients; for Anytime-SGD the change decays with time, irrespective of the learning rate η. In [6] , this is used to design better and more robust asynchronous training methods. Relation to Momentum. In the appendix we show that Anytime-SGD can be explicitly written as a momentum method, and therefore is quite different from standard SGD. Concretely, for α t = 1 we show that x t+1 ≈ x t -η t τ =1 (τ /t 2 )•g τ , and for α t ∝ t we show thatx t+1 ≈ x t -η t τ =1 (τ /t) 3 •g τ .Where g τ here is a (possibly noisy) unbiased estimate of ∇f (x τ ). This momentum interpretation provides a complementary intuition regarding the benefit of Anytime-SGD in the context of local update methods. Momentum brings more stability to the optimization process which in turn reduces the bias between different machines.For the sake of this paper we will require a specific theorem that does not necessarily regard Anytime-GD, but is rather more general. We will require the following definition, Algorithm 2 SLowcal-SGD Input: M machines, Parameter Server PS, #Communication rounds R, #Local computations K, initial point x 0 , learning rate η > 0, weights {α t } t Initialize: set w 0 = x 0 , initialize anchor point Θ 0 := (w 0 , x 0 ), and set t = 0 for r = 0, . . . , R -1 do Distributing anchor: PS distributes anchor Θ r := (w t , x t ) to all machines, each machine i ∈ [M ] initializes (w i t , x i t ) = Θ r := (w t , x t ) for k = 0, . . α τ ∇f (x τ ) • (w τ -w * ) .Our approach is to employ an Anytime version of Local-SGD, which we name by SLowcal-SGD. Notation: Prior to describing our algorithm we will define t to be the total of per-machine local updates up to step k of round r, resulting t := rK + k. In what follows, we will often find it useful to denote the iterates and samples using t, rather than explicitly denoting t = rK + k. Additionally we use {α t } t to denote a pre-defined sequence of non-negative weights. Finally, we denote T := RK.In the spirit of Anytime-SGD our approach is to maintain two sequences per machine i ∈ [M ]:{w i t ∈ R d } t and {x i t ∈ R d } t .Our approach is depicted explicitly in Alg. 2. Next we describe our algorithm in terms of the scheme depicted in Alg. 1: (i) Distributing anchor. At the beginning of round r the PS distributes Θ r = (w t , x t ) = (w rK , x rK ) ∈ R d × R d to all machines. (ii) Local Computations. For t = rK, every machine initializes (w i t , x i t ) = Θ r , and for the next K rounds, i.e. for any rK ≤ t ≤ (r + 1)K -1, every machine performs a sequence of local Anytime-SGD steps as follows,EQUATIONwhere similarly to Anytime-SGD we query the gradients at the averages x i t , meaning g i t = ∇f i (x i t , z i t ) . And query points are updated as weighted averages of past iterates {w t } t , ,EQUATIONAt the end round r, i.e. t = (r + 1)K, each machine communicates (w i t , x i t ) as a message to the PS. (iii) Aggregation. The PS aggregates the messages and computes the next anchor pointΘ r+1 = (w t , x t ) = 1 M i∈[M ] Φ i r := 1 M i∈[M ] w i t , 1 M i∈[M ] x i t, where t = (r + 1)K.Remark: Note that for t = rK our notation for (w i t , x i t ) is inconsistent: at the end of round r -1 these values may vary between different machines, while at the beginning of round r these values are all equal to Θ r := (w t , x t ). Nevertheless, for simplicity we will abuse notation, and explicitly state the right definition when needed. Importantly, in most of our analysis we will mainly need to refer to the averages1 M i∈[M ] w i t , 1 M i∈[M ]x i t , and note the latter are consistent at the end and beginning of consecutive rounds due to the definition of Θ r , and Φ i r-1 .Below we state our main result for SLowcal-SGD (Alg. 2), Theorem 2. Let f (•) be a convex and L-smooth function. Then under the assumption that we make in Sec. 2, invoking Alg. 2 with weights {α t = t + 1} t∈[T ] , and an appropriate learning rate η ensures,E∆ T ≤ O LB 2 0 1 KR + 1 R 2 + 1 K 1/3 R 4/3 + σB 0 √ M KR + L 1/2 (σ 1/2 + G 1/2 * ) • B 3/2 0 K 1/4 R ,where ∆ T := f (x T ) -f (x * ), B 0 := ∥w 0 -w * ∥, and we choose the learning rate as follows,EQUATIONAs Table 1 shows, Thm. 2 implies that SLowcal-SGD improves over all existing upper bounds for Minibatch and Local SGD, by allowing less communication rounds to obtain a linear speedup of M .Intuition. The degradation in local SGD schemes (both standard and Anytime) is due to the bias that it introduces between different machines during each round, which leads to a bias in their gradients.Intuitively, this bias is small if the machines query the gradients at a sequence of slowly changing query points. This is exactly the benefit of SLowcal-SGD which queries the gradients at averaged iterates x i t 's. Intuitively these averages are slowly changing compared to the iterates themselves w i t ; and recall that the latter are the query points used by standard Local-SGD. A complementary intuition to the benefit of our approach, is the interpretation of Anytime-SGD as a momentum method (see Sec. 3.1 and the appendix) which leads to decreased bias between machines.To further simplify the more technical discussion here, we will assume the homogeneous case, i.e., that for any i ∈ [M ] we haveD i = D and f i (•) = f (•).So a bit more formally, let us discuss the bias between query points in a given round r ∈ [R], and let us denote t 0 = rK. The following holds for standard Local SGD,EQUATIONwhere g i τ is the noisy gradients that Machine i computes in w i τ , and we can write g i τ := ∇f (w i τ ) + ξ i τ , where ξ i τ is the noisy component of the gradient. Thus, for two machines i ̸ = j we can write,E∥w i t -w j t ∥ 2 = η 2 E t-1 τ =t0 g i τ -g j τ 2 ≈ η 2 E t-1 τ =t0 ∇f (w i τ ) -∇f (w j τ ) 2 + η 2 E t-1 τ =t0 ξ i τ -ξ j τ 2And it was shown in [35] , that the noisy term is dominant and therefore we can bound,EQUATIONSimilarly, for SLowcal-SGD we would like to bound E∥x i t -x j t ∥ 2 for two machines i ̸ = j; and in order to simplify the discussion we will assume uniform weights i.e., α t = 1 , ∀t ∈ [T ]. Now the update rule for the iterates w i t , is of the same form as in Eq. ( 9), only now g i τ := ∇f (x i τ ) + ξ i τ , where ξ i τ is the noisy component of the gradient. Consequently,t τ =t0 (w i τ -w j τ ) ≈ -η t-1 τ =t0 (t -τ )(g i τ -g j τ ) ≈ -ηK t-1 τ =t0 (g i τ -g j τ ) ,where we took a crude approximation of t -τ ≈ K. Now, by definition of x i t and α t = 1,x i t = t0 t • x t0 + 1 t t τ =t0 w i τ , ∀i ∈ [M ], t ∈ [t 0 , t 0 + K] .Thus, for two machines i ̸ = j we have,1 η 2 E∥x i t -x j t ∥ 2 = 1 η 2 E 1 t t τ =t0 w i τ -w j τ 2 ≈ 1 η 2 • η 2 K 2 t 2 E t-1 τ =t0 g i τ -g j τ 2 ≈ K 2 t 2 E t-1 τ =t0 ∇f (x i τ ) -∇f (x j τ ) 2 + K 2 t 2 E t-1 τ =t0 ξ i τ -ξ j τ 2 .As we show in our analysis, the noisy term is dominant, so we can therefore bound,EQUATION)Taking t ≈ T = RK above yields a bound of O(K/R 2 ). Thus Equations ( 10), (11) , illustrate that the bias of SLowcal-SGD is smaller by a factor of R 2 compared to the bias of standard Local-SGD.In the appendix we demonstrate the same benefit of Anytime-SGD over SGD when both use α t ∝ t.Finally, note that the biases introduced by the local updates come into play in a slightly different manner in Local-SGD compared to SLowcal-SGD3 . Consequently, the above discussion does not enable to demonstrate the exact rates that we derive. Nevertheless, it provides some intuition regarding the benefit of our approach. The full and exact derivations appear in the appendix. Importance Weights. One may wonder whether it is necessary to employ increasing weights α t = t + 1, rather than employing standard uniform weights α t = 1 , ∀t. Surprisingly, in our analysis we have found that increasing weights are crucial in order to obtain a benefit over Minibatch-SGD, and that upon using uniform weights SLowcal-SGD performs worse compared to Minibatch SGD! We elaborate on this in Appendix L. Below we provide an intuitive explanation.Intuitive Explanation. The intuition behind the importance of using increasing weights is the following: Increasing weights are a technical tool to put more emphasis on the last rounds. Now, in the context of Local update methods, the iterates of the last rounds are more attractive since the bias between different machines shrinks as we progress. Intuitively, this happens since as we progress with the optimization process, the expected value of the gradients that we compute goes to zero (since we converge); and consequently the bias between different machines shrinks as we progress.Proof Sketch for Theorem 2. As a starting point for the analysis, for every iteration t ∈ [T ] we will define the averages of (w i t , x i t , g i t ) across all machines as follows,w t := 1 M i∈[M ] w i t , & x t := 1 M i∈[M ] x i t & g t := 1 M i∈[M ] g i t .Note that Alg. 2 explicitly computes (w t , x t ) only once every K local updates, and that theses are identical to the local copies of every machine at the beginning of every round. Combining the above definitions with Eq. ( 6) yields,EQUATIONFurther combining these definitions with Eq. ( 7) yields,EQUATIONThe above implies that the{x t } t∈[T ] sequence is an {α t } t∈[T ] weighted average of {w t } t∈[T ]. This enables to employ Thm. 1 which yields,α 0:t ∆ t ≤ t τ =0 α τ ∇f (x τ ) • (w τ -w * ), where we denote ∆ t := f (x t ) -f (w * ). This bound highlights the challenge in the analysis: our algorithm does not directly compute unbiased estimates of x t , except for the first iterate of each round. Concretely, Eq. ( 12) implies that our algorithm effectively updates using g t which is a biased estimate of ∇f (x t ).It is therefore natural to decompose ∇f (x τ ) = g τ + (∇f (x τ ) -g τ ) in the above bound, yielding,EQUATIONThus, we intend to bound the weighted error α 0:t ∆ t by bounding two terms: (A) which is related to the update rule of the algorithm, and (B) which accounts for the bias between g t and ∇f (x t ).In what follows we will find the following notation useful, ḡt := 1 M i∈[M ] ∇f i (x i t ), and note that ḡt = E g t |{x i t } i∈[M ]. We will also employ the following notations:V t := t τ =0 α 2 τ ∥ḡ τ - ∇f (x τ )∥ 2 , and D t := ∥w t -w * ∥ 2, where w * is a global minimum of f (•). We will also denoteD 0:t := t τ =0 ∥w τ -w * ∥ 2 .Bounding (A): Due to the update rule of Eq. ( 12), one can show by standard regret analysis that:(A) := t τ =0 α τ g τ • (w τ -w * ) ≤ ∥w0-w * ∥ 2 2η + η 2 t τ =0 α 2 τ ∥g τ ∥ 2 ,Bounding (B): We can bound (B) in expectation using V t and D 0:t as follows for any ρ > 0:E [(B)] ≤ 1 2ρ EV t + ρ 2 ED 0:t ,Combining (A) and (B): Combining the above boounds on (A) and (B) into Eq. ( 14) we obtain the following bound which holds for any ρ > 0 and t ∈ [T ],EQUATIONNow, to simplify the proof sketch we shall assume that D t ≤ D 0 ∀t, implying that D 0:T ≤ T D 0 . Plugging this into the above equation and taking ρ = 1 4ηT gives,EQUATIONNext we will bound ( * ) and EV T , and plug them back into Eq. (16) .Bounding ( * ): To bound ( * ) it is natural to decompose g τ = (g τ -ḡτ )+(ḡ τ -∇f (x τ ))+∇f (x τ ).Using this decomposition we show that, ( * )⪅ 3 σ 2 M T t=0 α 2 t + 3EV T + 12LE T t=0 α 0:t ∆ t .Bounding EV T The definition of V t shows that it is encompasses the bias that is introduced due to the local updates, which in turn relates to the distances∥x i t -x j t ∥ , ∀i, j ∈ [M ].Thus, EV T is therefore directly related to the dissimilarity between the machines. Our analysis shows the following:EV T ≤ 400L 2 η 2 K 3 T τ =0 α 0:τ •(G 2 * +4L∆ τ )+90L 2 η 2 K 6 R 3 σ 2 .Plugging the above into Eq. ( 16), and using our choice for η, gives an almost explicit bound,α 0:t E∆ t ⪅ ∥w 0 -w * ∥ 2 η + η σ 2 M T t=0 α 2 t + L 2 η 3 T K 6 R 3 σ 2 + L 2 η 3 T K 3 T τ =0 α 0:τ G 2 * + 1 2(T + 1) E T t=0 α 0:t ∆ t .The theorem follows by plugging above the choices of η, α t , and using a technical lemma.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments: 
 To evaluate the effectiveness of our proposed approach, we conducted experiments on the MNIST [25] dataset-a widely used benchmark in image classification comprising 70,000 grayscale images of handwritten digits (0-9), divided into 60,000 training images and 10,000 test images. The dataset was accessed through torchvision (version 0.16.2). We implemented a logistic regression model [7] using the PyTorch framework and performed all computations on an NVIDIA RTX 3090 GPU.To ensure the reliability of our results, we averaged the outcomes over three different random seeds.The code used for these experiments is available in our GitHub repository. 4We compared our approach, utilizing parameters suggested by our theoretical framework (α t = t), against Local-SGD and Minibatch-SGD across various configurations. Specifically, we experimented with 16, 32, and 64 workers and varied the number of local updates K (or minibatch sizes for Minibatch-SGD) among 4, 8, 16, 32, and 64. In SLowcal-SGD and Local-SGD, each local update was computed using a single sample. We optimized the learning rate through grid search, setting it to 0.01. All experiments involved a single pass over the MNIST dataset. Our results on the MNIST dataset, illustrated in Figures 1 and 2 , highlight the effectiveness of using local steps over equivalently sized batches in this setting. As shown in Figures 1a and 2a , both SLowcal-SGD and Local-SGD demonstrate substantial improvements in test accuracy and loss over Minibatch-SGD, where these become more significant as the number of local steps grows.At a closer look, Figures 1b and 2b indicate that with an increasing number of local iterations, the performance gap between SLowcal-SGD and Local-SGD generally becomes more pronounced. This gap suggests that SLowcal-SGD's approach, which maintains closer alignment of weights both within local updates and across workers, enhances convergence, resulting in superior performance over Local-SGD. 
conclusion: 
 We have presented the first local approach for the heterogeneous distributed Stochastic Convex Optimization (SCO) setting that provably benefits over the two most prominent baselines, namely Minibatch-SGD, and Local-SGD. There are several interesting avenues for future exploration: (a) developing an adaptive variant that does not require the knowledge of the problem parameters like σ and L; (b) Allowing a per dimension step-size that could benefit in (the prevalent) scenarios where the scale of the gradients considerably changes between different dimensions; in the spirit of the well known AdaGrad method [11] . Finally, (c) it will be interesting to understand whether we can find an algorithm that provably dominates over the Accelerated Minibach-SGD baseline, which is an open question also in the homogeneous SCO setting.A Explanations Regarding the Linear Speedup and Table 1 Here we elaborate on the computations done in Table 1 . First we will explain why the dominance of the term 1 √ M KR implies a linear speedup by a factor of M .Explanation. Recall that using SGD with a single machine M = 1, yields a convergnece rate of 1 √ KR (as a dominant term). Thus, in order to obtain an excess loss smaller than some ε > 0, SGD requires RK ≥ Ω 1 ε 2 . Where RK is the wall-clock time required to compute the solution. Now, when we use parallel optimization with R communication rounds, K local computations, and M machines, the wall-clock time to compute a solution is still RK. Now, if the dominant term in the convergence rate of this algorithm is 1 √ M KR then the wall clock time to obtain an ε-optimal solution should be RK ≥ Ω 1 M ε 2 . And the latter is smaller by a factor of M compared to a single machine.Computation of R min in Table 1 . The term1 √M KR appears in the bounds of all of the parallel optimization methods that we describe. Nevertheless, it is dominant up as long as the number of communication rounds R is larger than some treshold value R min , that depends on the specific convergence rate. Clearly, smaller values of R min imply less communication. Thus, in the R min column of the table we compute R min for each method based on the term in the bound that compares least favourably against := B parallel (M, K, R, G * ) 5 , then R min is the lowest R which satisfies, B parallel ≤ 1 √ M KR . 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: we do not foresee any special societal impact that arise due to our work Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification:Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Let us assume that the following holds at the optimum w * ,1 M i∈[M ] ∥∇f i (w * )∥ 2 ≤ G 2 * /2Then we can show the following relation for anyw ∈ R d , 1 M i∈[M ] ∥∇f i (w)∥ 2 = 1 M i∈[M ] ∥∇f i (w) -∇f i (w * ) + ∇f i (w * )∥ 2 ≤ 2 M i∈[M ] ∥∇f i (w) -∇f i (w * )∥ 2 + 2 M i∈[M ] ∥∇f i (w * )∥ 2 ≤ 4L(f (w) -f (w * )) + G 2 * .where we used ∥a + b∥ 2 ≤ 2∥a∥ 2 + 2∥b∥ 2 which holds for any a, b ∈ R d , and the last line follows by the lemma below that we borrow from [17, 8] .Lemma 1. Let L(x) = 1 M i∈[M ] ℓ i (x)be a convex function with global minimum w * , and assume that every f i : R d → R is L-smooth. Then the following holds,1 M i∈[M ] ∥∇ℓ i (w) -∇ℓ i (w * )∥ 2 ≤ 2L(L(w) -L(w * )) .Proof of Lemma 1. The lemma follows immediately from lemma 27.1 in [8] , by taking v = w * therein.Here we show how to interpret the Anytime-SGD algorithm that we present in Equations ( 4), (5) , as a momentum method. For completeness we rewrite the update equations below,EQUATIONand then,EQUATION)where g t is an unbiased gradient estimate at x t , and {α t } t is a sequence of non-negative scalars. And at initialization x 0 = w 0 .First note that Eq. ( 18) directly implies that,x t+1 = 1 α 0:t+1 t+1 τ =0 α τ w τ .Next, note that we can directly write,w τ = w 0 -η τ -1 n=0 α n g nPlugging the above into the formula for x t+1 yields,x t+1 = w 0 -η 1 α 0:t+1 t+1 τ =0 τ -1 n=0 α τ α n g n = w 0 -η 1 α 0:t+1 t n=0 t+1 τ =n+1 α τ α n g n = w 0 -η 1 α 0:t+1 t n=0 α n+1:t+1 α n g n .Thus,EQUATIONwhere we used the equality below,α n+1:t+1 - α 0:t+1 α 0:t α n+1:t = α t+1 -α n+1:t α t+1 α 0:t = α t+1 (1 - α n+1:t α 0:t ) = α t+1 α 0:n α 0:t .Thus we can write,x t+1 ≈ x t -η 1 α 0:t+1 t n=0 α t+1 α n α 0:n α 0:t g n ,Uniform Weights. Thus, taking uniform weights α t = 1 yields,x t+1 ≈ x t -η t n=0 n t 2 g n .Linear Weights. Similarly, taking linear weights α t = t + 1 yields,x t+1 ≈ x t -η t n=0 n 3 t 3 g n .Proof of Theorem 1. We rehearse the proof of Theorem 1 from [9] .First, since w * is a global minimum and α 0:t are non-negative than clearly,α 0:t (f (x t ) -f (w * )) ≥ 0 .Now, notice that the following holds,α t (x t -w t ) = α 0:t-1 (x t-1 -x t )Using the gradient inequality for f gives,t τ =0 α τ (f (x τ ) -f (w * )) ≤ t τ =0 α τ ∇f (x τ ) • (x τ -w * ) = t τ =0 α τ ∇f (x τ ) • (w τ -w * ) + t τ =0 α τ ∇f (x τ ) • (x τ -w τ ) = t τ =0 α τ ∇f (x τ ) • (w τ -w * ) + t τ =0 α 0:τ -1 ∇f (x τ ) • (x τ -1 -x τ ) ≤ t τ =0 α τ ∇f (x τ ) • (w τ -w * ) + t τ =0 α 0:τ -1 (f (x τ -1 ) -f (x τ )) ,where we have used the gradient inequality again which implies ∇f(x τ ) • (x τ -1 -x τ ) ≤ f (x τ -1 ) - f (x τ ).Now Re-ordering we obtain,t τ =0 (α 0:τ f (x τ ) -α 0:τ -1 f (x τ -1 )) -α 0:t f (w * ) ≤ t τ =0 α τ ∇f (x τ ) • (w τ -w * ) .Telescoping the sum in the LHS we conclude the proof,α 0:t (f (x τ ) -f (w * )) ≤ t τ =0 α τ ∇f (x τ ) • (w τ -w * ) .More Elaborate Intuitive Explanation. The intuition is the following: We have two extreme baselines: (1) Minibatch-SGD where queries do not change at all during updates-implying that there is no bias between different machines. However, Minibatch-SGD is "lazy" since among KR queries it only performs R gradient updates. Conversely (2) Local-SGD is not "lazy" since each machine performs KR gradient updates. Nevertheless, the queries of different machines change substantially during each round, which translates to bias between machines, which in turn degrades the convergence.Ideally, we would like to have a "non-lazy" method where each machine performs KR gradient updates (like Local-SGD), but where the queries of each machine do not change at all during rounds (like Minibatch-SGD) and therefore no bias is introduced between machines. Of course, this is too good to exist, but our method is a step in this direction: it is "non-lazy" and the query points of different machines change slowly, and therefore introduce less bias between machines. This translates to a better convergence rate.Additional Technical Intuition for α t ∝ t. Here we extend the technical explanation that we provide in Sec. 3.2.1 to the case where α t ∝ t, and show again that SLowcal-SGD yields smaller bias between different machines compared to Local-SGD.As in the intuition for the case of uniform weights, to simplify the more technical discussion, we will assume the homogeneous case, i.e., that for any i ∈ [M ] we haveD i = D and f i (•) = f (•).Note that upon employing linear weights, the normalization factor α 0:T that plays a major role in the convergence guarantees of Anytime-SGD (see Thm. 1) also grows as α 0:T ∝ T 2 . Thus, in order to make an proper comparison, we should compare the bias of weighted Anytime-SGD, to the appropriate weighted version of SGD; where the normalization factor α 0:T also plays a similar role in the guarantees (see e.g. [34] ). This weighted SGD is as follows [34] , ∀t ≥ 0EQUATION)and after t iterations it outputs w T = 1 α 0:T T t=0 α t w t . And for α t = t + 1 this version enjoys the same guarantees as standard SGD.Next, we compare the Local-SGD version of the above weighted SGD (Eq. ( 20)) to our SLowcal-SGDwhen both employ α t = t + 1. So a bit more formally, let us discuss the bias between query points in a given round r ∈ [R], and let us denote t 0 = rK. The following holds for weighted Local SGD,EQUATIONwhere g i τ is the noisy gradients that Machine i computes in w i τ , and we can write g i τ := ∇f (w i τ ) + ξ i τ , where ξ i τ is the noisy component of the gradient. Thus, for two machines i ̸ = j we can write,EQUATIONNow, we can be generous with respect to weighted SGD and only take the second noisy term into account and neglect the first term 6 . Thus we obtain,EQUATION)where we used α t ≤ α t0+K , ∀t ≤ t 0 + K, as well as α 2 t0+K = (r(K + 1) + 1) 2 ≈ (rK) 2 . We also used t -t 0 ⪅ K.Similarly, for SLowcal-SGD we would like to bound E∥x i t -x j t ∥ 2 for two machines i ̸ = j; while assuming linear weights i.e., α t = t + 1 , ∀t ∈ [T ]. Now the update rule for the iterates w i t , is of the same form as in Eq. (21) , only now g i τ := ∇f (x i τ ) + ξ i τ , where ξ i τ is the noisy component of the gradient. Consequently, we can show the following,t τ =t0 α τ (w i τ -w j τ ) ≈ -η t τ =t0 α τ τ -1 n=t0 α n (g i n -g j n ) ≈ -η t-1 n=t0 α n+1:t α n (g i n -g j n ) ≈ -ηr 2 K 3 t-1 τ =t0 (g i τ -g j τ ) ,where we took a crude approximation of α n+1:t α n ≈ α t0:t+K α t0 ⪅ rK 2 • rK = r 2 K 3 . In the last "≈" we also change the notation of summation variable from n to τ . Now, by definition,x i t ≈ α0:t 0 α0:t • x t0 + 1 α0:t t τ =t0 α τ w i τ , ∀i ∈ [M ], t ∈ [t 0 , t 0 + K] .Thus, for two machines i ̸ = j we have,1 η 2 E∥x i t -x j t ∥ 2 = 1 η 2 E 1 α 0:t t τ =t0 α τ (w i τ -w j τ ) 2 ≈ 1 η 2 • η 2 r 4 K 6 (α 0:t ) 2 E t-1 τ =t0 g i τ -g j τ 2 ≈ 1 η 2 • η 2 r 4 K 6 r 4 K 4 E t-1 τ =t0 g i τ -g j τ 2 ≈ K 2 E t-1 τ =t0 ∇f (x i τ ) -∇f (x j τ ) 2 + K 2 E t-1 τ =t0 ξ i τ -ξ j τ 2 .where we have used α 0:t ≈ α 0:t0 ∝ t 2 0 ≈ r 2 K 2 . As we show in our analysis, the noisy term is dominant, so we can therefore bound,EQUATION)Thus Equations ( 22), ( 23), illustrate that for α t ∝ t, then the bias of SLowcal-SGD is smaller by a factor of r 2 compared to the bias of weighted Local-SGD. Since r 2 can be as big as R 2 this coincides with the benefit of SLowcal-SGD over standard SGD in the case where α t = 1, which we demonstrate in the main text.Finally, note that upon dividing by the normalization factor α 0:T ,we have, that for SLowcal-SGD with either α t = 1 or α t ∝ t then,EQUATIONComparably, upon dividing by the normalization factor α 0:T ,we have, that for Local-SGD with either α t = 1 or α t ∝ t that,EQUATIONThus, with respect to the approximate and intuitive analysis that we make here SLowcal-SGD maintains similar benefit over Local-SGD for both α t = 1 and α t = t + 1.As we explain in Appendix L, taking α t = 1 in SLowcal-SGD does not actually enable to provide a benefit over Local-SGD. The reason is that for α t = 1, the condition for which the dominant term in the bias (between different machines) is the noisy term (this enables the approximate analysis that we make here and in the body of the paper), leads to limitation on the learning rate which in turn degrades the performance for SLowcal-SGD with α t = 1. Conversely, for α t ∝ t there is no such degradation due to the limitation of the learning rate. For more details and intuition please see Appendix L.F Proof of Thm. 2Proof of Thm. 2. As a starting point for the analysis, for every iteration t ∈ [T ] we will define the averages of (w i t , x i t , g i t ) across all machines as follows,w t := 1 M i∈[M ] w i t , & x t := 1 M i∈[M ] x i t & g t := 1 M i∈[M ] g i t .Note that Alg. 2 explicitly computes (w t , x t ) only once every K local updates, and that theses are identical to the local copies of every machine at the beginning of every round. Combining the above definitions with Eq. ( 6) yields,EQUATIONFurther combining these definitions with Eq. ( 7) yields,EQUATIONAnd the above implies that the {x t } t∈[T ] sequence is an {α t } t∈[T ] weighted average of {w t } t∈[T ] . This enables to employ Thm. 1 which yields,α 0:t ∆ t := α 0:t (f (x t ) -f (w * )) ≤ t τ =0 α τ ∇f (x τ ) • (w τ -w * ) ,where we denote ∆ t := f (x t ) -f (w * ). The above bound highlights the challenge in the analysis: our algorithm does not directly computes unbiased estimates of x t , except for the first iterate of each round. Concretely, Eq. ( 26) demonstrates that our algorithm effectively updates using g t which might be a biased estimate of ∇f (x t ).It is therefore natural to decompose ∇f (x τ ) = g τ + (∇f (x τ ) -g τ ) in the above bound, leading to,EQUATIONThus, we intend to bound the weighted error α 0:t ∆ t by bounding two terms: (A) which is directly related to the update rule of the algorithm (Eq. ( 26)), and (B) which accounts for the bias between g t and ∇f (x t ).In what follows we will find the following notation useful,EQUATIONand the above definition implies that ḡt = E g t |{z i 0 } i∈[M ] , . . . ,{z i t-1 } i∈[M ] = E g t |{x i t } i∈[M ]. We will also employ the following notations,V t := t τ =0 α 2 τ ∥ḡ τ -∇f (x τ )∥ 2 , & D t := ∥w t -w * ∥ 2where w * is a global minimum of f (•). Moreover, we will also use the notation D 0:t :=t τ =0 ∥w τ - w * ∥ 2 .Bounding (A): Due to the update rule of Eq. ( 26), one can show by standard regret analysis (see Lemma 2 below) that,EQUATIONLemma 2. (OGD Regret Lemma -See e.g. [15] ) Let w 0 ∈ R d and η > 0. Also assume a sequence of T non-negative weights {α t ≥ 0} t∈[T ] and T vectors {g t ∈ R d } t∈[T ] , and assume an update rule of the following form:w t+1 = w t -ηα t g t , ∀t ∈ [T ] .Then the following bound holds for any u ∈ R d , and t ∈ [T ],t τ =0 α τ g τ • (w τ -u) ≤ ∥w 0 -u∥ 2 2η + η 2 t τ =0 α 2 τ ∥g τ ∥ 2 .for completeness we provide a proof in Appendix G.Bounding (B): Since our goal is to bound the expected excess loss, we will bound the expected value of (B), thus,EQUATIONwhere the second line follows by the definition of ḡτ (see Eq. ( 29)) and due to the fact that w τ is measurable with respect to 30) and (31) into Eq. ( 28) we obtain the following bound which holds for any ρ > 0 and t ∈ [T ],{z i 0 } i∈[M ] , . . . , {z i τ -1 } i∈[M ] while ḡτ = E g τ |{z i 0 } i∈[M ] , . . . , {z i τ -1 } i∈[M ] implying that E[g τ • (w τ -w * )] = E[ḡ τ • (w τ -w * )]; the third line uses Young's inequality a • b ≤ inf ρ>0 { ρ 2 ∥a∥ 2 + 1 2ρ ∥b∥ 2 }EQUATIONwhere we have used V t ≤ V T which holds for any t ∈ [T ], as well asE t τ =0 α 2 τ ∥g τ ∥ 2 ≤ E T τ =0 α 2τ ∥g τ ∥ 2 , which holds since t ≤ T . Next, we shall bound each of the above terms. The following lemma bounds ED 0:t , Lemma 3. The following bound holds for any t ∈ [T ],ED 0:t = E t τ =0 ∥w τ -w * ∥ 2 ≤ 2T ∥w 0 -w * ∥ 2 + 2T η 2 E T t=0 α 2 t ∥g t ∥ 2 + 16η 2 T 2 • EV TCombining the above lemma into Eq. ( 33) gives,α 0:t E∆ t ≤ ∥w 0 -w * ∥ 2 2η + η 2 + ρT η 2 E T τ =0 α 2 τ ∥g τ ∥ 2 + 1 2ρ + 8ρη 2 T 2 EV T + ρT ∥w 0 -w * ∥ 2Since the above holds for any ρ > 0 let us pick a specific value of ρ = 1 4ηT ; by doing so we obtain,EQUATIONNext, we would like to bound (C); to do so it is natural to decompose g τ = (g τ -ḡτ ) + (ḡ τ -∇f (x τ )) + ∇f (x τ ). The next lemma provides a bound, and its proof goes directly through this decomposition, Lemma 4. The following holds,(C) ≤ 3 σ 2 M T t=0 α 2 t + 3EV T + 12LE T t=0 α 0:t ∆ t .Combining the above Lemma into Eq. ( 33) yields,EQUATIONwhere we have uses 3 ≤ 4T which holds since T ≥ 1. The next lemma provides a bound for EV t , Lemma 5. For any t ≤ T := KR, Alg. 2 with the learning choice in Eq. ( 8) ensures the following bound,EV t ≤ 400L 2 η 2 K 3 T τ =0 α 0:τ • (G 2 * + 4L∆ τ ) + 90L 2 η 2 K 6 R 3 σ 2 .Plugging the above bound back into Eq. ( 34) gives an almost explicit bound,EQUATIONand we used 12ηL ≤ 1/4(T + 1) which follows since η ≤ 1 48L(T +1) (see Eq. ( 8)), as well as 16 • 10 3 L 3 η 3 T K 3 ≤ 1/4(T + 1), which follows since η ≤ 1 40LK(T +1) 2/3 (see Eq. ( 8)). Next we use the above bound and invoke the following lemma, Lemma 6. Let {A t } t∈[T ] be a sequence of non-negative elements and B ∈ R, and assume that for any t ≤ T ,A t ≤ B + 1 2(T + 1) T t=0 A t ,A T ≤ 2B .Taking A t ← α 0:t E∆ t and B ← ∥w0-w * ∥ 2 η + 3η σ 2 M T t=0 α 2 t + 720L 2 η 3 T K 6 R 3 σ 2 + 2 • 10 3 L 2 η 3 T K 3 T τ =0 α 0:τ G 2* provides the following explicit bound,EQUATIONwhere we have usedT τ =0 α 0:τ ≤ T t=0 α 2 t ≤ R-1 r=0 K-1 k=0 (r + 1) 2 K 2 ≤ K 3 R 3 ,Recalling that T = KR and that,η = min 1 48L(T + 1) , 1 10LK 2 , 1 40LK(T + 1) 2/3 , ∥w 0 -w * ∥ √ M σT 3/2 , ∥w 0 -w * ∥ 1/2 L 1/2 K 7/4 R(σ 1/2 + G 1/2 * )The above bound translates into,EQUATIONNoting that α 0:T ≥ Ω(T 2 ) and using T = KR gives the final bound,E∆ T ≤ O L∥w 0 -w * ∥ 2 KR + L∥w 0 -w * ∥ 2 K 1/3 R 4/3 + L∥w 0 -w * ∥ 2 R 2 + σ∥w 0 -w * ∥ √ M KR + L 1/2 (σ 1/2 + G 1/2 * ) • ∥w 0 -w * ∥ 3/2 K 1/4 R .which establishes the Theorem.Proof of Lemma 2. The update rule implies for all τ ∈ [T ]∥w τ +1 -u∥ 2 = ∥(w τ -u) -ηα τ g τ ∥ 2 = ∥w τ -u∥ 2 -2ηα τ g τ • (w τ -u) + η 2 α 2 τ ∥g τ ∥ 2Re-ordering and gives,2ηα τ g τ • (w τ -u) = ∥w τ -u∥ 2 -∥w τ +1 -u∥ 2 + η 2 α 2 τ ∥g τ ∥ 2 .Summing over τ and telescoping we obtain,2η t τ =0 α τ g τ • (w τ -u) = ∥w 1 -u∥ 2 -∥w t+1 -u∥ 2 + η 2 t τ =0 α 2 τ ∥g τ ∥ 2 ≤ ∥w 1 -u∥ 2 + η 2 t τ =0 α 2 τ ∥g τ ∥ 2Dividing the above by 2η establishes the lemma.Proof of Lemma 3. Recalling the notations D τ := ∥w τ -w * ∥ 2 , our goal is to bound ED 0:t . To do so, we will derive a recursive formula for D 0:t . Indeed, the update rule of Alg. 2 implies Eq. ( 26), which in turn leads to the following for any t ∈ [T ],∥w t+1 -w * ∥ 2 = ∥(w t -w * ) -ηα t g t ∥ 2 = ∥w t -w * ∥ 2 -2ηα t g t • (w t -w * ) + η 2 α 2 t ∥g t ∥ 2Unrolling the above equation and taking expectation gives,E∥w t+1 -w * ∥ 2 = ∥w 0 -w * ∥ 2 -2ηE t τ =0 α τ g τ • (w τ -w * ) ( * ) + η 2 E t τ =0 α 2 τ ∥g τ ∥ 2 (39)The next lemma provides a bound on ( * ), V T := T t=0 α 2 t ∥ḡ t -∇f (x t )∥ 2 .Plugging the bound of Lemma 7 into Eq. (39), and using the notation of D t we conclude that for any t ∈ [T ],ED t ≤ D 0 + 2η EV T • ED 0:T + η 2 E t τ =0 α 2 τ ∥g τ ∥ 2 ≤ D 0 + 2η EV T • ED 0:T + η 2 E T t=0 α 2 t ∥g t ∥ 2 ,where we used t ≤ T . Summing the above equation over t gives,EQUATIONWe shall now require the following lemma, Lemma 8. Let A, B, C ≥ 0, and assume that A ≤ B + C √ A, then the following holds,A ≤ 2B + 4C 2Now, using the above Lemma with Eq. ( 40) implies,EQUATIONwhere we have takenA ← D 2 0:T , B ← T ∥w 0 -w * ∥ 2 +T η 2 E T t=0 α 2 t ∥g t ∥ 2, and C ← 2ηT • √ EV T . Thus, Eq. ( 41) establishes the lemma.Proof of Lemma 7. Recall that ( * ) = -2ηE t τ =0 α τ g τ •(w τ -w * ), we shall now focus on bounding ( * )/2η,EQUATIONwhere the first line is due to the definitions of g τ and ḡτ appearing in Eq. ( 29) (this is formalized in Lemma 9 below and in its proof); the third line follows by observing that the {x t } t sequence is and {α t } t weighted average of {w t } t and thus Theorem 1 implies that E t τ =0 α τ ∇f (x τ ) • (w τ -w * ) ≥ 0 for any t, as well as from Cauchy-Schwarz; the fourth line follows from the Cauchy-Schwarz inequality for random variables, which asserts that for every random variables X, Y , then E[XY ] ≤ √ EX 2 √ EY 2 ; the fifth line is an application of the following inequalityt τ =0 a τ b τ ≤ t τ =0 a 2 τ t τ =0 b 2 τwhich holds for any two sequences {a τ ∈ R} τ , {b τ ∈ R} τ , and the above also follows from the standard Cauchy-Schwarz inequality. Thus, Eq. ( 42) establishes the lemma.We are left to show thatE [g τ • (w τ -w * )] = E [ḡ τ • (w τ -w * )] which is established in the lemma below, Lemma 9.The following holds for any τ ∈ [T ],E [g τ • (w τ -w * )] = E [ḡ τ • (w τ -w * )] .Proof of Lemma 9. Let {F τ } τ ∈[T ] be the natural filtration induces by the history of samples up to every time step τ . Then according to the definitions of g t and ḡt we have,E [g τ • (w τ -w * )] = E [E [g τ • (w τ -w * )|F τ -1 ]] = E [E [g τ |F τ -1 ] • (w τ -w * )] = E [E [ḡ τ |F τ -1 ] • (w τ -w * )] = E [ḡ τ • (w τ -w * )] ,where the first line follows by the law of total expectations; the second line follows since w τ is measurable w.r.t. F τ -1 ; the third line follows by definition of g τ and ḡτ ; and the last line uses the law of total expectations.Proof of Lemma 8. We will divide the proof into two case. Case 1: B ≥ C √ A. In this case,A ≤ B + C √ A ≤ 2B ≤ 2B + 4C 2 . Case 2: B ≤ C √ A. In this case, A ≤ B + C √ A ≤ 2C √ A ,dividing by √ A and taking the square implies,A ≤ 4C 2 ≤ 2B + 4C 2 .And therefore the lemma holds.Proof of Lemma 4. Recalling that (C) := E T τ =0 α 2 τ ∥g τ ∥ 2 , we will decompose g τ = (g τ -ḡτ ) + (ḡ τ -∇f (x τ )) + ∇f (x τ ) which gives,EQUATIONwhere the second line uses ∥a + b + c∥ 2 ≤ 3(∥a∥ 2 + ∥b∥ 2 + ∥c∥ 2 ) which holds for any a, b, c ∈ R d ; the third line uses the definition of V T as well as the smoothness of f (•) implying that ∥∇f (x τ )∥ 2 ≤ 2L(f (x τ ) -f (w * )) := 2L∆ τ (see Lemma 10 below); the fourth line invokes Lemma 11; the fifth line uses α 2 τ = (τ + 1) 2 ≤ 2α 0:τ .Lemma 10. Let F : R d → R be an L-smooth function with a global minimum x * , then for anyx ∈ R d we have, ∥∇F (x)∥ 2 ≤ 2L(F (x) -F (w * )) .Lemma 11. The following bound holds for any t ∈ [T ],E∥g τ -ḡτ ∥ 2 ≤ σ 2 M .Proof of Lemma 10. The L smoothness of f means the following to hold ∀w, u ∈ R d ,F (x + u) ≤ F (x) + ∇F (x) ⊤ u + L 2 ∥u∥ 2 .Taking u = -1 L ∇F (x) we get,F (x + u) ≤ F (x) - 1 L ∥∇F (x)∥ 2 + 1 2L ∥∇F (x)∥ 2 = F (x) - 1 2L ∥∇F (x)∥ 2 .Thus:∥∇F (x)∥ 2 ≤ 2L F (x) -F (x + u) ≤ 2L F (x) -F (x * ) ,where in the last inequality we used F (x * ) ≤ F (x + u) which holds since x * is the global minimum.Proof of Lemma 11. Recall that we can write,g τ -ḡτ := 1 M i∈[M ] (g i τ -ḡi τ )where ḡi τ := ∇f i (x i τ ), and g i τ := ∇f i (x i τ , z i τ ), and that z 1 t , . . . , z M t are independent of each other. Thus, conditioning over {x i t } M i=1 then {g i τ -ḡi τ } M i=1 are independent and zero mean i.e.E[g i τ -ḡi τ |{x i t } M i=1 ] = 0. Consequently, E ∥g τ -ḡτ ∥ 2 |{x i t } M i=1 = 1 M 2 E    i∈[M ] (g i τ -ḡi τ ) 2 |{x i t } i∈[M ]    = 1 M 2 i∈[M ] E ∥g i τ -ḡi τ ∥ 2 |{x i t } M i=1 ≤ 1 M 2 i∈[M ] σ 2 ≤ σ 2 M .Using the law of total expectation implies that E∥g τ -ḡτ ∥ 2 ≤ σ 2 M .Proof of Lemma 5. To bound EV t we will first employ the definition of x t together with the smoothness of f (•),EQUATIONwhere the first line uses the definition of ḡt , the second line uses Jensen's inequality, and the third line uses the smoothness of f i (•)'s. The last line follows from Jensen's inequality.We use the following notation for any τ ∈ [T ]EQUATIONand notice that j∈[M ] q i,j τ = q i τ , and that i,j∈[M ] q i,j τ = M 2 Q τ . Moreover q i,j τ = q j,i τ , ∀i, j ∈ [M ].Thus, according to Eq. (44) it is enough to bound EV t as follows,EQUATIONNext we will bound the above term.Bounding (⋆): Let t ∈ [T ], if t = rK for some r ∈ [R],then according to Alg. 2 x i t = x t for any machine i ∈ [M ], thus x i t -x j t = 0 for any two machines i, j ∈ [M ]. More generally, if t = rK + k for some r ∈ [R], and k ∈ [K], then by denoting t 0 := rK we can write t = t 0 + k. Using this notation, the update rule for x i τ implies the following for any i ∈ [M ],x i t = α 0:t0 α 0:t x i t0 + 1 α 0:t t τ =t0+1 α τ w i τ = α 0:t0 α 0:t x t0 + 1 α 0:t t τ =t0+1 α τ w i τ ,where we used x i t0 = x t0 , ∀i ∈ [M ]. Thus, for any i ̸ = j we can write,EQUATION)So our next goal is to derive an expression for t τ =t0+1 α τ (w i τ -w j τ ). The update rule of Eq. ( 6) implies that for any τ ∈ [t 0 , t 0 + K],EQUATION)where the second equality is due to the initialization of each round implying thatw i t0 = w t0 , ∀i ∈ [M ].Next, we will require the following notation ḡi t := ∇f i (x i t ), and ξ i t := g i t -ḡi t . We can therefore write, g i t = ḡi t + ξ i t and it is immediate to show that E[ξ i t |x i t ] = 0. Using this notation together with Eq. ( 48), implies that for any τ ∈ [t 0 , t 0 + K] and i ̸ = j we have,EQUATIONand in the last line we use the following notationξ n := ξ i n -ξ j n 7 .Summing Eq. (49) over τ ∈ [t 0 + 1, t] we obtain,EQUATIONwhere in the last equation we replace the notation of the summation index from n to τ (only done to ease notation). 7 A more appropriate notation would be ξ (i,j) n := ξ i n -ξ j n , but to ease notation we absorb the (i, j) notation into ξ.Plugging the above equation back into Eq. ( 47) we obtain for any t ∈ [t 0 , t 0EQUATIONwhere the first inequality uses ∥a + b∥ 2 ≤ 2∥a∥ 2 + 2∥b∥ 2 which holds ∀a, b ∈ R d , the second inequality uses∥ N2 n=N1+1 a n ∥ 2 ≤ (N 2 -N 1 )N2 n=N1+1 ∥a n ∥ 2 which holds for any {a n ∈ R d } N2 n=N1+1 ; the third inequality uses the definition of ḡi τ , it also uses t -t 0 ≤ K as well as (α τ :t ) 2 ≤ (Kα t ) 2 which holds since τ ≤ t and since both α τ ≤ α t ; and the last inequality uses the fact that α t = t + 1 implying that the following holds,α 4 t (α 0:t ) 2 ≤ 4 , & α 2 t (α 0:t ) 2 ≤ 4 α 2 tLemma 12. The following holds for any i, j ∈ [M ],∥∇f i (x i τ ) -∇f j (x j τ )∥ 2 ≤ 3L 2 M α 2 τ (q i τ + q j τ ) + 6 ∥∇f i (x τ )∥ 2 + ∥∇f j (x τ )∥ 2 ,Using the above lemma inside Eq. (51) yields,EQUATIONwhere we have denoted 8θ := 48η 2 K 3 L 2 , & B i,j t := 8η 2 α 2 t t τ =t0+1 α τ :t α τ α 2 t ξ τ 2 .Summing Eq. ( 52) over i, j ∈ [M ] and using the definition of Q t gives,EQUATIONwhere we used,i,j∈[M ] q i τ = j∈[M ] i∈[M ] q i τ = j∈[M ] M 2 Q τ = M 3 Q τ .Now dividing Eq. ( 53) by M 2 gives ∀t ∈ [t 0 , t 0 + K],EQUATIONwhere the second line follows from the dissimilarity assumption Eq. ( 2), and the last line is due to the definition of ∆ τ .Thus, we can re-write the above equation as follows forall t ∈ [t 0 , t 0 + K],EQUATIONwhereH t = 2θ L 2 t τ =t0+1 α 2 τ • (G 2 * + 4L∆ τ )) + 1 M 2 i,j∈[M ] B i,jt , and recall that θ := 48η 2 K 3 L 2 . Now, notice that Q t , H t ≥ 0, and that θ satisfies θK = 48η 2 K 4 L 2 ≤ 1/2 since we assume that η 2 ≤ 1 100L 2 K 4 (see Eq. ( 8)). This enables to make use of Lemma 13 below to conclude, . We absorb this notation into ξτ to simplify the notation.Q t0+1:t0+K ≤ 2H t0+1:t0+K = 4θ L 2 t0+K τ =t0+1 α 2 τ • (G 2 * + 4L∆ τ )) + 2 M 2 i,j∈[M ] B i,j t0+1:t0+K = 200η 2 K 3 t0+K τ =t0+1 α 2 τ • (G 2 * + 4L∆ τ )) + 2 M 2 i,j∈[M ] B i,Recalling that we like to bound the expectation of the LHS of Eq. ( 56), we will next boundt τ =t0+1 α τ :t ατ α 2 t ξ τ 2, which is done in the following Lemma9 , Lemma 14. The following bound holds for any t ∈ [t 0 , t 0 + K],E t τ =t0+1 α τ :t α τ α 2 t ξ τ 2 ≤ 4K 3 σ 2 .Since the above lemma for any i, j and t ∈ [t 0 , t 0 + K] we can now bound EB i,j t0+1:t0+K as follows,EB i,j t0+1:t0+K = 8η 2 α 2 t t0+K t=t0+1 E t τ =t0+1 α τ :t α τ α 2 t ξ τ 2 ≤ 8η 2 α 2 t t0+K t=t0+1 4K 3 σ 2 = 32η 2 α 2 t K 4 σ 2 = 32η 2 (r + 1) 2 K 6 σ 2 ,(57) where the last lines α t ≤ (r + 1)K for any iteration t that belongs to round r.Since the above holds for any i, j it follows that,2 M 2 i,j∈[M ] B i,j t0+1:t0+K ≤ 2 • 32η 2 (r + 1) 2 K 6 σ 2 = 64η 2 (r + 1) 2 K 6 σ 2 .Plugging the above back into Eq. ( 56) gives,EQUATION)Final Bound on EV t . Finally, using the above bound together with the Eq. ( 46) enables to bound EV t as follows,1 L 2 EV t ≤ t τ =0 Q τ ≤ T τ =0 Q τ ≤ 200η 2 K 3 T τ =0 α 2 τ • (G 2 * + 4L∆ τ )) + R-1 r=0 rK+K t=rK+1 α 2 t E∥x i t -x j t ∥ 2 ≤ 200η 2 K 3 T τ =0 α 2 τ • (G 2 * + 4L∆ τ )) + R-1 r=0 64η 2 (r + 1) 2 K 6 σ 2 ≤ 200η 2 K 3 T τ =0 α 2 τ • (G 2 * + 4L∆ τ )) + 64η 2 K 6 σ 2 • 8 6 R 3 ≤ 400η 2 K 3 T τ =0 α 0:τ • (G 2 * + 4L∆ τ )) + 90η 2 K 6 R 3 σ 2 ,where we have used R-1 r=0 (r + 1) 2 ≤ 8 6 R 3 , and the last line uses α 2 τ = (τ + 1) 2 ≤ 2α 0:τ Consequently, we can boundEV t ≤ 400L 2 η 2 K 3 T τ =0 α 0:τ • (G 2 * + 4L∆ τ )) + 90L 2 η 2 K 6 R 3 σ 2 ,which established the lemma.Proof of Lemma 12. First note that by definition of x τ we have for any i ∈ [M ],EQUATION)where we have used Jensen's inequality, and the definition of q i τ . Using the above inequality, we obtain,∥∇f i (x i τ ) -∇f j (x j τ )∥ 2 = ∥(∇f i (x i τ ) -∇f i (x τ )) + (∇f i (x τ ) -∇f j (x τ )) -(∇f j (x j τ ) -∇f j (x τ ))∥ 2 ≤ 3∥∇f i (x i τ ) -∇f i (x τ )∥ 2 + 3∥∇f i (x τ ) -∇f j (x τ )∥ 2 + 3∥∇f j (x j τ ) -∇f j (x τ )∥ 2 ≤ 3L 2 ∥x τ -x i τ ∥ 2 + ∥x τ -x j τ ∥ 2 + 6 ∥∇f i (x τ )∥ 2 + ∥∇f j (x τ )∥ 2 ≤ 3L 2 M α 2 τ (q i τ + q j τ ) + 6 ∥∇f i (x τ )∥ 2 + ∥∇f j (x τ )∥ 2 ,where the second and third lines use∥ N n=1 a n ∥ 2 ≤ N N n=1 ∥a n ∥ 2 which holds for any {a n ∈ R d } Nn=1 ; we also used the smoothness of the f i (•)'s; and the last line uses Eq. (59).Proof of Lemma 13. Since the Q t 's and θ are non-negative, we can further bound Q t for all t ∈ [t 0 , t 0 + K] as follows,Q t ≤ θQ t0+1:t + H t ≤ θQ t0+1:t0+K + H t .Summing the above over t gives,Q t0+1:t0+K := t0+K t=t0+1 Q t ≤ θK • Q t0+1:t0+K + H t0+1:t0+K ≤ 1 2 • Q t0+1:t0+K + H t0+1:t0+Kwhere we used θK ≤ 1/2. Re-ordering the above equation immediately establishes the lemma.Proof of Lemma 14. Letting {F t } t be the natural filtration that is induces by the random draws up to time t, i.e., by{{z i 1 } i∈[M ] , . . . , {z i t } i∈[M ] }.By the definition of ξ t it is clear that ξ t is measurable with respect to F t , and that,E[ξ t |F t-1 ] = 0 .Implying that {ξ t } t is martingale difference sequence with respect to the {F t } t . The following implies that,E t τ =t0+1 α τ :t α τ α 2 t ξ τ 2 ≤ t τ =t0+1 α τ :t α τ α 2 t 2 E ∥ξ τ ∥ 2 ≤ t τ =t0+1 Kα t • α t α 2 t 2 E ∥ξ τ ∥ 2 = K 2 t τ =t0+1 E ∥ξ τ ∥ 2 ≤ K 2 t τ =t0+1 E ξ i τ -ξ j τ 2 ≤ 2K 2 t τ =t0+1 (E∥ξ i τ ∥ 2 + E∥ξ i τ ∥ 2 ) ≤ 2K 2 t τ =t0+1 2σ 2 ≤ 4K 2 σ 2 • (t -t 0 ) ≤ 4K 3 σ 2 ,where the first line follows by Lemma 15 below, the second line holds since α τ ≤ α t , and α τ :t ≤ Kα t (recall α τ ≤ α t since τ ≤ t); the fourth line follows due to ξ τ := ξ i τ -ξ j τ ; the fifth line uses ∥a + b∥ 2 ≤ 2∥a∥ 2 + 2∥b∥ 2 for any a, b ∈ R ; the sixth line follows since E∥ξ i τ ∥ 2 := E∥g i τ -ḡi τ ∥ 2 := E∥∇f (x i τ , z i τ ) -∇f (x i τ )∥ 2 ≤ σ 2 ; and the last line uses (t -t 0 ) ≤ K.Lemma 15. Let {ξ t } t be a martingale difference sequence with respect to a filtration {F t } t , then the following holds for all time indexes t 1 , t 2 ≥ 0E t2 τ =t1 ξ τ 2 = t2 τ =t1 E ∥ξ τ ∥ 2 .Proof of Lemma 15. We shall prove the lemma by induction over t 2 . The base case where t 2 = t 1 clearly holds since it boils down to the following identity,E t1 τ =t1 ξ τ 2 = E ∥ξ t1 ∥ 2 = t1 τ =t1 E ∥ξ τ ∥ 2 .Now for induction step let us assume that the holds for t 2 ≥ t 1 and lets prove it holds for t 2 + 1. Indeed,E t2+1 τ =t1 ξ τ 2 = E ξ t2+1 + t2 τ =t1 ξ τ 2 = E t2 τ =t1 ξ τ 2 + E∥ξ t2+1 ∥ 2 + 2E t2 τ =t1 ξ τ • ξ t2+1 = t2+1 τ =t1 E ∥ξ τ ∥ 2 + 2E E t2 τ =t1 ξ τ • ξ t2+1 |F t2 = t2+1 τ =t1 E ∥ξ τ ∥ 2 + 2E t2 τ =t1 ξ τ • E [ξ t2+1 |F t2 ] = t2+1 τ =t1 E ∥ξ τ ∥ 2 + 0 = t2+1 τ =t1 E ∥ξ τ ∥ 2 ,where the third line follows from the induction hypothesis, as well as from the law of total expectations; the fourth lines follows since {ξ τ } t2 τ =0 are measurable w.r.t F t2 , and the fifth line follows since E[ξ t2+1 |F t2 ] = 0. Thus, we have established the induction step and therefore the lemma holds.Proof of Lemma 6. Summing the inequality A t ≤ B + 1 Plugging this back to the original inequality and taking t = T gives,A T ≤ B + 1 2(T + 1)A 0:T ≤ 2B .which concludes the proof.One may wonder, why should we employ increasing weights α t ∝ t rather than using standard uniform weights α t = 1 , ∀t. Here we explain why uniform weights are insufficient and why increasing weights e.g. α t ∝ t are crucial to obtain our result.Intuitive Explanation. Prior to providing an elaborate technical explanation we will provides some intuition. The intuition behind the importance of using increasing weights is the following: Increasing weights are a technical tool to put more emphasis on the last rounds. Now, in the context of Local update methods, the iterates of the last rounds are more attractive since the bias between different machines shrinks as we progress. Intuitively, this happens since as we progress with the optimization process, the bias in the stochastic gradients that we compute goes to zero (in expectation), and consequently the bias between different machines shrinks as we progress.Technical Explanation. Assume general weights {α t } t , and let us go back to the proof of Lemma 5 (see Section J). Recall that in this proof we derive a bound of the following form (see Eq. ( 55))EQUATIONwhereEQUATION, and importantly 10 ,θ := η 2 2α 4 t (α 0:t ) 2 • K 3 L 2 .Now, a crucial part of the proof is the fact that θK ≤ 1/2, which in turn enables to employ Lemma 13 in order to bound EV t .Not let us inspect the constraint θK ≤ 1/2 for polynomial weights of the form α t ∝ t p where p ≥ 0. condition boils down to,η 2 2α 4 t (α 0:t ) 2 • K 3 L 2 • K ≤ 1/2 ,Implying the following bound should apply to η for any t ∈ [T ],η ≤ 1 2LK 2 • α 0:t α 2 t ≈ 1 2LK 2 • t p+1 t 2p = 1 2LK 2 • t 1-pNow since the bound should hold for any t ∈ [T ] we could divide into two cases: Case 1: p ≤ 1. In this case t 1-p is monotonically increasing with t so the above condition should be satisfied for the smallest t, namely t = 1, implying,η ≤ 1 2LK 2 • α 0:t α 2 t ≈ 1 2LK 2 .The effect of this term on the overall error stems from the first term in the error analysis (see e.g. Eq. ( 36)), namely,1 α 0:T • ∥w 0 -w * ∥ 2 η = 2LK 2 • ∥w 0 -w * ∥ 2 T p+1Now, for the extreme values p = 0(uniform weights) and p = 1 (linear weights), the above expression results an error term of the following form,EQUATIONThus, for p = 0, the error term is considerably worse even compared to Minibatch-SGD, and p = 1 is clearly an improvement. Case 2: p > 1. In this case t 1-p is decreasing increasing with t so the above condition should be satisfied for the largest t, namely t = T , implying,η ≤ 1 2LK 2 • α 0:t α 2 t ≈ 1 2LK 2 • 1 T p-1 .Now, the effect of this term on the overall error stems from the first term in the error analysis (see e.g. Eq. ( 36)), namely,1 α 0:T • ∥w 0 -w * ∥ 2 η = 2LK 2 • ∥w 0 -w * ∥ 2 • T p-1 T p+1 = 2LK 2 • ∥w 0 -w * ∥ 2 • T 2Thus, for any p ≥ 1 we obtain,EQUATIONConclusion: As can be seen from Equations (61) (62), using uniform weights or even polynomial weights α t ∝ t p with p < 1 yields strictly worse guarantees compared to taking p ≥ 1.NeurIPS paper checklist Justification: In the intro and conclusion sections, we discuss that our approach does not aqpply to non-convex scenarios, and state it as future direction Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Justification: we ensured that our paper conforms with the NeurIPS Code of Ethics Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Heterogeneous here refers to the data of each client, and we assume that its statistical properties may vary between different clients.This implies that such methods do not obtain a wall-clock speedup as we increase the number of machines M .A major challenge in our analysis is that for a given i ∈ [M ] the {x i t }t sequence is not necessarily an {αt}t weighted average of the {w i t }t.https://github.com/dahan198/slowcal-sgdB parallel may also depend on σ, L, ∥w0 -w * ∥ but for simplicity of exposition we hide these dependencies in Table1.It was shown in[35], that the noisy term is dominant for standard SGDrecall that for simplicity of notation we denote ξτ rather than ξ i,j τ .Indeed, in the case where αt := t + 1 we can take θ := 8η 2 K 3 L 2 , and this is used in the proof ofLemma 5 


Decision: This paper gives a convergence guarantee for a distributed learning algorithm that improves upon both baselines of mini-batch SGD and local SGD. It does so by leveraging a slowly-changing sequence of query points (see Anytime-SGD), which in turn enables to better mitigate the client drift induced by the local updates. The paper provides novel insights, is well executed and interesting, as acknowledged by the reviews.

For the camera-ready version, we urge the authors to incorporate the mentioned feedback by the reviewers.

Reviews: review: paper_summary: paper_summary: This paper proposes SLowcal-SGD, which is a distributed learning algorithm that builds on customizing a recent technique for incorporating a slowly-changing sequence of query points, which in turn enables to better mitigate the bias induced by the local updates. Theoretical proof is given on the proposed algorithms.
strength_weakness: strength_weakness: * While the paper is heavy on theory, it has no validation on any synthetic or real-world data. It should not be hard to verify this since this is convex problems and there are multiple ways and open sourced code to produce heterogeneous data.
* The rates shown in table 1 is a little confusing. Comparing to accelerated mini-batch SGD, what is the advantage of proposed slowcal-SGD?
* The assumptions of equation (1) - (3) are somewhat strong if we discuss the data heterogeneity. What is the main difference between proposed slowcal-SGD and general variance reduction SGD? (which doesn't need equation 1-3).
questions: questions: Please refer to the previous section.
limitations: limitations: The paper is theory-driven and does not have negative societal impact.
paper_summary: paper_summary: This paper introduces a new federated learning algorithm called Slowcal-SGD, which basically introduces anytime-SGD into federated learning setting. The authors provide solid convergence analysis and fruitful insights on the new algorithm. They show the algorithm can provably beat both mini-batch SGD and local SGD in the heterogeneous data setting. No experiments are provided, though.
strength_weakness: strength_weakness: - It'd be better to define "query". It could be controversial. For example, why is computing the gradients wrt a mini-batch a single query instead of B (batch size) queries?
- No experimental results are provided. So it's hard to tell whether the proposed algorithm works in practice.
questions: questions: See above comments
limitations: limitations: NA
paper_summary: paper_summary: This work studies distributed model training with a parameter server; contributions are theoretical:
* **Assumptions**: $L$-smooth convex objectives, stochastic gradient estimates, heterogeneous worker distributions, bounded difference in expected gradients of local workers' objectives at a global minima, denoted $G^\star$.
* **Main result**: Given a fixed set of communication rounds $R$ with the parameter server, $M$ worker machines, and a budget of $K$ local gradient queries per worker in each communication round, this work presents a simple method for improving local SGD. Given $L$-smooth convex objectives with stochastic gradients and heterogeneous worker distributions, the local-SGD variant proposed in this work achieves more favorable convergence than mini-batch SGD (where the $K$ stochastic gradient queries are used to compute a larger mini-batch gradient at each worker). The proposed method converges in $\mathcal{O}(MK^{-1/2})$ rounds, whereas mini-batch SGD converges in $\mathcal{O}(MK)$ rounds.
* **Method**: The proposed method extends anytime GD (Cutkosky, ICML'19) to the distributed local-sgd parameter-server setting. In short, regular local-sgd with $K$ local steps, but where stochastic gradients are computed at an exponential moving average (ema) of the model parameters. The parameter server averages both the primal and ema parameters, and sends back the exact average to each worker at the end of each round.
strength_weakness: strength_weakness: **Significance**
* No numerical experiments conducted to explore the convergence of the proposed method or generalization capabilities. To increase impact and adoption, researchers may be interested in the generalization performance of the method; i.e., going beyond the number of communication rounds required to decrease training error. Would design considerations (e.g., choice of $\alpha_t$ schedule) change in such a setting?
* Not a major issue for a theoretical paper, but current hyper-parameter choices requires knowledge of problem parameters ($\sigma$ and L-smoothness constant).

**Clarity**
* Minor complaint is that the proof sketches do not always correspond to a similar logic used in the actual proofs themselves. For instance, (16) in the proof sketch in the main paper was obtained by assuming a somewhat monotonic iterate sequence, but such a result is never explicitly proven in the appendix. Instead, Lemma 3 in Appendix H (which bounds the sum of the iterate sequence using the T times the starting error, plus additional terms depending on the gradient magnitude and variance; which should indeed converge) is used to arrive at (33) in the proof of Theorem 2 in the appendix, which corresponds to (16) in the main paper.
questions: questions: * Please consider including simple numerical experiments in the convex setting (e.g., multinomial logistic regression or least squares) to empirically evaluate the performance of the proposed method.
* Would appreciate a discussion on the main challenges to demonstrating improved convergence relative to accelerated mini-batch SGD (not just vanilla mini-batch SGD), especially since the proposed EMA update can be given a momentum-like interpretation as stated in Appendix C.
limitations: limitations: N.A.