Conceptio › Archive › arXiv CS

arXiv CSopen access

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

B RIDGING THE G AP B ETWEEN H OMOGENEOUS AND H ETEROGENEOUS A SYNCHRONOUS O PTIMIZATION I S S URPRISINGLY D IFFICULT

arXiv:2609.17483v1 [math.OC] 15 Sep 2026

Alexander Tyurin AXXX, Moscow, Russia Applied AI Institute, Moscow, Russia

A BSTRACT Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Łojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.

I NTRODUCTION

We consider optimization problems described by n o n P min f (x) := n1 Eξi ∼Di [fi (x; ξi )] , x∈Rd

(1)

i=1

where fi : Rd × Sξi → R and ξi is a random variable with distribution Di on Sξi for all i ∈ [n]. Let us denote fi (x) := Eξi ∼Di [fi (x; ξi )] . In our setup, we have n workers/clients/CPUs/GPUs working in parallel and asynchronously, and each worker i has access only to the stochastic gradient ∇fi (x; ξi ) of the function fi for all x ∈ Rd . We concentrate on the standard convergence metric and 2 want to find a (possibly random) point x̄ such that E[∥x̄ − x∗ ∥ ] ≤ ε, where x∗ is a solution of (1). Such a problem arises in many machine learning (ML), deep learning, federated learning (FL), and data science problems (Konečný et al., 2016; McMahan et al., 2017; Goodfellow et al., 2016). In general, we use the following standard assumptions from convex stochastic optimization, but each result states which assumptions it requires. Assumption 1.1 (Global smoothness). The function f is differentiable and L–smooth, i.e., ∥∇f (x) − ∇f (y)∥ ≤ L ∥x − y∥ for all x, y ∈ Rd . Assumption 1.2 (Local smoothness). The functions fi are differentiable and Li –smooth. We also define Lmax := maxi∈[n] Li . Note that L ≤ Lmax (This is why we distinguish Assum. 1.1 and 1.2). Assumption 1.3 (Convexity). The functions fi are convex for all i ∈ [n]. The function f attains a minimum at a (non-unique) point x∗ ∈ Rd . Assumption 1.4 (Unbiased and σ 2 -variance-bounded noise). For all x ∈ Rd , stochastic gradients ∇fi (x; ξ) are unbiased and σ 2 -variance-bounded, i.e., Eξi [∇fi (x; ξi )] = ∇fi (x) and Eξi [∥∇fi (x; ξi ) − ∇fi (x)∥2 ] ≤ σ 2 for all i ∈ [n], where σ 2 ≥ 0. 1

We also consider the case where f satisfies the PŁ-condition, which is a much weaker assumption than µ–strong convexity (Karimi et al., 2016): 2

Assumption 1.5 (Global Polyak-Łojasiewicz condition). There exists µ > 0 such that ∥∇f (x)∥ ≥ 2µ (f (x) − f ∗ ) for all x ∈ Rd , where f ∗ is the finite optimal function value of f. We focus on the modern setup where many workers work together in a distributed environment, where the workers can have arbitrarily computation behaviors due to hardware delays or network connectivity problems. Most previous works typically assume that the workers have the same performance that does not change over time. In contrast, our focus is on the setting where the computation times are heterogeneous and non-constant. In the literature, the optimization problem (1) in the asynchronous environment is considered in two regimes: i) heterogeneous setting, where the functions fi can be arbitrarily different; in the context of ML and FL, it means the workers have access to different datasets. ii) homogeneous setting, where the functions fi are equal; in the context of ML and FL, it means the workers have access to the same dataset (Koloskova et al., 2022; Mishchenko et al., 2022; Feyzmahdavian & Johansson, 2023). Notations. [n] := {1, . . . , n}; N0 := {0, 1, 2, . . . }; ∥·∥ is the standard Euclidean norm; ⟨·, ·⟩ is the standard dot product; g = O(f ) : exist C > 0 such that g(z) ≤ C × f (z) for all z ∈ Z; g = Ω(f ) : exist C > 0 such that g(z) ≥ C × f (z) for all z ∈ Z; g = Θ(f ) : g = O(f ) and g = Ω(f ); e ) : the same as g = Θ(f ) but up to logarithmic factors. g = Θ(f 1.1

P REVIOUS WORK

Oracle complexity. In the classical optimization theory (Nemirovskij & Yudin, 1983), algorithms are compared in terms of oracle calls. Assume that the number of workers is one and we work with nonconvex functions and Assumptions 1.1 and 1.4. It is well known (Arjevani et al., 2022; 2 Carmon et al., 2020) that the optimal oracle complexity is O L∆/ε + σ L∆/ε2 to find x̄ ∈ Rd 2 such that E[∥∇f (x̄)∥ ] ≤ ε. It is attained by the vanilla SGD method: xk+1 = xk − γ∇f (xk ; ξ k ), k where ξ are i.i.d. random samples, ∆ := f (x0 ) − f ∗ , x0 ∈ Rd is a starting point, and γ = Θ (min{1/L, ε/Lσ2√}) is a step size. In the convex setting (Assumption 1.3), the optimal oracle 2 2 √ complexity is Θ LR/ ε + σ R /ε2 (Lan, 2020; Nemirovskij & Yudin, 1983) to find x̄ ∈ Rd such that E[f (x̄)] − f (x∗ ) ≤ ε, where R := x0 − x∗ . In the µ–strongly convex setting, the optimal √ e L/√µ + σ2/µ2 ε is to find x̄ ∈ Rd such that E[∥x̄ − x∗ ∥2 ] ≤ ε (up to logarithmic complexity Θ factors). Oracle complexity with many workers. Many works discovered oracle complexities with multiple workers. Arjevani & Shamir (2015); Scaman et al. (2017) analyze the heterogeneous convex setting and provide lower bounds when the workers are synchronized. Lu & De Sa (2021) consider the similar setup but in the nonconvex setting. Arjevani et al. (2020) analyze settings where methods receive delayed stochastic gradients. Woodworth et al. (2018) provide lower bounds for parallel setups with intermittent communications and delayed updates. The primary limitation of these results is the assumption that all workers have consistent computational performance, without accounting for individual delays, random lags, or variations in performance over time. Time complexity. To address the problem of analyzing methods with workers having different computation capabilities and performances, Mishchenko et al. (2022) proposed to consider the fixed computation model. In this model, it is assumed that worker i requires at most τi seconds to calculate one stochastic gradient. Without loss of generality, we assume that the times are sorted: τ1 ≤ · · · ≤ τn . One of the most popular methods is Asynchronous SGD (Lian et al., 2015; Zhang et al., 2015; Feyzmahdavian et al., 2016; Sra et al., 2016; Dutta et al., 2018; Stich & Karimireddy, 2020; Wu et al., 2022; Islamov et al., 2024; Maranjyan et al., 2025; Maranjyan & Richtárik, 2026). In the homogeneous setting, Mishchenko et al. (2022); Koloskova et al. (2022); Cohen et al. (2021) showed that Asynchronous SGD and Picky SGD can provably improve Pn the performance of the synchronized Minibatch SGD method that does the steps xk+1 = xk − γ/n i=1 ∇f (xk ; ξik ), where γ is a stepsize, ξik are i.i.d. samples, and 2 ∇f (xk ; ξik ) are calculated in parallel in n workers. Minibatch SGD requires O L∆/ε + σ L∆/nε2 iterations (Cotter et al., 2011; Goyal et al., 2017; Gower et al., 2019) in the nonconvex setting. 2

Algorithm 1 Malenia SGD or Rennala SGD when wik = 1/Bik or wik = n/

k i=1 Bi

, respectively

Input: point x , stepsize γ, parameter S, weights {wik }

1: 2: for k = 0, 1, . . . , K − 1 do 3: Ask all workers to calculate stochastic gradients at xk ; init gik = 0 and Bik = 0 ∀i ∈ [n] 4: 5: 6: 7:

−1 Pn while n1 i=1 (wik )2 Bik ≤ Sn do Wait for the next worker j Update Bjk = Bjk + 1 k k k k k Receive stochastic gradient ∇fj (xk ; ξj,B k ) and update gj = gj + ∇fj (x ; ξj,B k ) j

Ask this worker to calculate a stochastic gradient at xk end while PBik Pn Pn k k ) ∇fi (xk ; ξij gw := n1 i=1 wik gik = n1 i=1 wik j=1 k+1 k k 11: x = x − γgw 12: Stop all the workers’ calculations (or ignore the unfinished calculations in the next iterations) 13: end for 8: 9: 10:

2 Moreover, Minibatch SGD converges after O maxi∈[n] τi × L∆/ε + σ L∆/nε2 seconds because it waits for the slowest worker with maxi∈[n] τi in every iteration. Asynchronous SGD, methods with Pn k the step xk+1 = xk − γ /n i=1 ∇f (xk−δk ; ξik−δk ) and δk –delayed stochastic gradients, improve Pn −1 L∆/ε + σ 2 L∆/nε2 ). this time complexity to O((1/n i=1 1/τi ) Optimal time complexities in the heterogeneous and homogeneous settings. Surprisingly, the time complexity can be further improved. In the nonconvex setup (under Assumptions 1.1, and 1.4), Tyurin & Richtárik (2023) formalized the notion of time complexities and showed that the optimal time complexity is " #! −1 m P 1 σ 2 L∆ 1 L∆ Thomog := Θ min (2) m τi ε + mε2 m∈[n]

i=1

seconds in the homogeneous setup to find an ε–stationary point, achieved by the Rennala SGD method, where, without loss of generality, the times are sorted: τ1 ≤ · · · ≤ τn . In the heterogeneous setup, the optimal time complexity is n P 1 σ 2 L∆ Theter := Θ τn L∆ + τ , (3) i ε n nε2 i=1

achieved by the Malenia SGD method. A unifying perspective on Rennala SGD and Malenia SGD. Let us look closer to the Rennala SGD and Malenia SGD methods (see Algorithm 1) that achieve the optimal time complexities (2) and (3) in the homogeneous and heterogeneous setting, accordingly. We now recall how they work. In every iteration, Rennala SGD and Malenia SGD ask all workers to calculate stochastic gradients asynchronously at the same iterate xk . Assume that worker i has calculated Bik stochastic gradients for all i ∈ [n] at the iteration k. Then the methods do the steps k

k+1

= x − γgR ,

:= Pn 1

k i=1 Bi

n B P Pi

and xk+1 = xk − γgMk ,

gMk := n1

n P i=1

k ∇fi (xk ; ξij )

(Rennala SGD)

k ∇fi (xk ; ξij ),

(Malenia SGD)

i=1 j=1

1 Bik

k B Pi

j=1

accordingly. Rennala SGD and Malenia SGD ask all workers calculating stochastic gradients until −1 Pn Pn 1 1 k S 1 k > S/n correspondingly, where S is a parameter. Hence, i=1 Bi > /n and n i=1 /Bi n both methods asynchronously collect and aggregate stochastic gradients to compute gRk and gMk , and then perform a descent step. However, the way the methods aggregate is both different and important. It turns out the variance of the Rennala SGD’s update is smaller. Indeed, one can easily show that n −1 −1 h h k 2 i σ2 1 P k 2 i σ2 n k k k P E gR − E gR ≤ n n Bi and E gM − E gM ≤ n . n 1 i=1 B k i

i=1

Thus, the variance of Rennala SGD improves with the arithmetic mean of Bik , while the variance of Malenia SGD improves with the harmonic mean of Bik , which can be much smaller. Why wouldn’t k we use Rennala SGD in all scenarios if it is better? Because gR isbiased if {fi } are non-homogeneous. In general, E gRk ̸= ∇f (xk ), while it is always true that E gMk = ∇f (xk ). Both methods can PBik Pn k k k ∇fi (xk ; ξij ), where the weights be generalized into xk+1 = xk − γgw , gw := n1 i=1 wik j=1 Pn k k k n {wi } are free parameters. If we take wi = / i=1 Bi for all i ∈ [n], we get Rennala SGD with small variance. If we take wik = 1/Bik , we get Malenia SGD with high variance but with an unbiased estimator. The weights enable interpolation between the methods. Difference between the two settings. Using the inequality of arithmetic and harmonic means, one can easily show that Thomog ≤ Theter (ignoring constant factors). At the same time, the gap between the complexities can be arbitrarily huge. Indeed, when the performance τ1 of fastest 2 worker tends Pthe n to 0, one can easily show that Thomog → 0 and Theter → Θ τn L∆/ε + n1 i=2 τi σ L∆/nε2 , and Pn Pn Theter improves by at most i=1 τi / i=2 τi ≤ 2. While the improvement in the homogeneous setup is ∞. Consider another example when the performance τn of the slowest worker (straggler) tends Pm −1 L∆/ε + σ 2 L∆/mε2 ]), so to ∞. Then Theter → ∞ and Thomog → Θ(minm∈[n−1] [(1/m i=1 1/τi ) the complexity Thomog is robust to stragglers unlike Theter . Arbitrarily computation dynamics. The previous discussion explain that a significant gap appears between homogeneous and heterogeneous problems under the fixed computation model. This “arithmetic mean vs harmonic mean gap” was also observed in (Tyurin, 2025), where the author generalizes the fixed computation model to the universal computation model, accounting for potential disruptions caused by hardware or network delays, and any variations in computation speeds. For simplicity, in this work, we will continue working with the fixed computation model, but we also show how our final results translate to the universal computation model in Section A. Convex world. When we want to find a point x̄ such that E [f (x̄)] − f ∗ ≤ ε in the convex setup, the gap is similar. The optimal time complexity in the homogeneous setup is " Θ

min m∈[n]

1 m

m P 1 i=1

−1 √

2 2 LR √ + σmεR2 ε

τi

#! (4)

seconds (Tyurin & Richtárik, 2023). While the optimal time complexity in the heterogeneous setup is √ n P 1 σ 2 R2 Θ τn √LR + τ i n nε2 ε

(5)

i=1

seconds under Assumptions 1.1, 1.3, and 1.4 (our new contribution, Theorem E.4; the final puzzle piece needed to reveal the systematic gap between the two settings). Both complexities are achieved by the accelerated versions of Rennala SGD and Malenia SGD accordingly. Strongly convex world. Assume additionally that the function f is µ–strongly convex. Using reduction (Woodworth & Srebro, 2016), up to logarithmic factors, we can obtain the optimal time complexity " e Θ

min m∈[n]

m P 1 1 m

i=1

−1 q

τi

L σ µ + mεµ

#! (6)

in the homogeneous setting and the optimal time complexity q n P σ2 L 1 e Θ τn µ + n τi nεµ

(7)

i=1

in the heterogeneous setting when we want to find a point x̄ such that E [f (x̄)] − f ∗ ≤ ε. Here we also observe a large gap between the settings. Note that the complexities (3), (5), and (7) can only be improved under additional assumptions because they are optimal. 4

Main question: Having the systematic gap between the homogeneous and heterogeneous setups, the goal of this work is to identify theoretical assumptions that are as weak as possible to improve the results of asynchronous methods in heterogeneous scenarios. Under which assumptions can we improve the dependence on the arithmetic mean of {τi } (see (3), (5), and (7)) to the dependence on the harmonic mean of {τi } (see (2), (4), and (6))? Right now, the only possible way is to assume that the functions {fi } are equal—an assumption we clearly want to avoid in the heterogeneous setting. Is there any chance to relax this assumption? 1.2

C ONTRIBUTIONS

To the best of our knowledge, this is the first work to address the main question in any setting; our analysis considers the convex setting under standard Assumptions 1.1, 1.2, 1.3, 1.4, and 1.5. Analysis of first- and second-order similarity. First, we consider the celebrated first- and secondorder similarity and, surprisingly, prove that even under these assumptions—no matter how close the P 2 n σ τi nµ functions {fi } are—any randomized algorithm cannot converge before Ω n1 seconds 2ε i=1

for small ε (Theorem 2.3). Thus, it is infeasible to break the dependence on the arithmetic mean of {τi } under these assumptions. Investigation of the interpolation assumption. Inspired by Theorem 2.3, which provides a construction with local functions having different minimizers, we decided to go in another direction and consider the interpolation assumption. Thus, we introduce two additional assumptions, strong interpolation and the local Polyak-Łojasiewicz condition, and prove that it is impossible to drop either of these assumptions for improvement (Theorems 3.6 and 3.7). Bridging the gap. By identifying this minimal set of assumptions, we derive a new time complexity result that matches the dependence on worker computation times in the best-known bound in the homogeneous setting (Theorem 3.8), but without requiring the functions fi to be identical. Our theoretical results are validated numerically in Section H. To bridge the gap in Section 3.2, we need to introduce Assumptions 3.3 and 3.4. However, our primary goal was to illustrate and prove that these assumptions are indeed necessary. Merely stating the assumptions might not be convincing; this is why the central part of our paper investigates different assumptions and shows that most of them do not allow us to bridge the gap. While previous work noted the existence of the gap, our contribution goes further by systematically investigating which assumptions are sufficient and which are insufficient to eliminate it.

F IRST-O RDER AND S ECOND -O RDER S IMILARITY D ON ’ T H ELP

The main problem with the arithmetic mean dependence in the heterogeneous setting is that this setting considers a worst-case scenario with arbitrarily heterogeneous functions. Due to the fact that Malenia SGD is optimal, we have to introduce assumptions to obtain faster convergence. One of the most popular assumptions in the literature is first-order and second-order similarity of the functions (Arjevani & Shamir, 2015; Szlendak et al., 2021; Mishchenko et al., 2022): Assumption 2.1 (First-Order Similarity). The functions fi satisfy 2 maxi,j∈[n] ∥∇fi (x) − ∇fj (x)∥ ≤ δ1 for all x ∈ Rd for some δ1 ≥ 0. It implies Pn 2 1 d i=1 ∥∇fi (x) − ∇f (x)∥ ≤ δ1 for all x ∈ R . n Assumption 2.2 (Second-Order Similarity). The functions fi satisfy 2 2 2 d maxi,j∈[n] ∇ fi (x) − ∇ fj (x) ≤ δ2 for all x ∈ R for some δ2 ≥ 0. It implies Pn 2 1 2 2 d ∇ f (x) − ∇ f (x) ≤ δ i 2 for all x ∈ R . i=1 n One might expect that when both δ1 and δ2 are small, it would be possible to exploit the similarity and design a method with smaller variance and better dependence on {τi }. Surprisingly, this is not the case: for any δ1 > 0 and δ2 ≥ 0, one can construct a problem for which the convergence speed of Malenia SGD (Theorem F.2) cannot be improved, up to logarithmic factors, in small-ε regimes: 5

Theorem 2.3 (Lower Bound). Consider stochastic gradients ∇fi (x; ξi ) = ∇fi (x) + ξi ei with ξi ∼ N (0, σ 2 ) for all i ∈ [n], and x ∈ Rn . Consider any randomized algorithm that has access only to the stochastic gradients (randomized method), which starts at x0 = 0, under the fixed computation 2 β2 2 model and any R, µ, β, σ, ε > 0 such that 0 < ε ≤ µcβ 2 n2 and R ≥ µ2 n , where c > 0 is a universal n P σ2 constant. For any time budget t ≤ c0 n1 τi nµ 2 ε , where c0 is a universal constant, there exist i=1 2

fi (x) : Rn → R such that fi (x) = µ2 ∥x∥ − βφi ⟨x, ei ⟩ and φi ∈ [−1, 1]. Assumptions 1.1, 1.2, 1.3, 1.4, and 1.5 hold. Moreover, Assumption 2.1 (the first-order similarity) is satisfied with δ1 = 2β 2 , 0 ∗ 2 and Assumption 2.2 (the second-order similarity) ≤ R2 , and h is satisfiedi with δ2 = 0, x − x 2

the method cannot produce a point x̄ such that E ∥x̄ − x∗ ∥ minimizer of f.

≤ ε within t seconds, where x∗ is the

Hence, for any small δ1 > 0 and δ2 ≥ 0, the convergence speed cannot be improved over that of Malenia SGD up to logarithmic factors in small-ε regimes (compare to Theorem F.2). Due to the construction in Theorem 2.3, we can choose any β > 0, and hence any δ1 > 0. No matter how close the functions are to each other, the lower bound does not allow us to break the pessimistic time complexity. In view of this, additional assumptions about the first- and second-order similarity will not help to improve the time complexity of Malenia SGD. 2 2 Remark 2.4. For the construction in Theorem 2.3, we can also show that ∥∇fi (x)∥ ≤ 2 ∥∇f (x)∥ + 2 2β d for all i ∈ [n], which corresponds to the ρ–strong growth condition when β = 0 and ρ = 2 (Schmidt & Roux, 2013). Since Theorem 2.3 holds for all β > 0, we have proved the result for a “slightly” broader class of problems and have “almost” established that, even under the strong growth condition, the convergence speed of Malenia SGD cannot be improved up to logarithmic 2 factors. Whether a similar result holds for the class of problems satisfying maxi∈[n] ∥∇fi (x)∥ ≤ 2 2 ∥∇f (x)∥ for all x ∈ Rd remains an important open research question. Takeaway 1: Even with first-order and second-order similarity, for any randomized algorithm, there is still no hope of improving upon the convergence speed of Malenia SGD, up to logarithmic factors, in small-ε regimes.

U NDERSTANDING THE G AP VIA I NTERPOLATION A SSUMPTIONS

Looking at Takeaway 1, we see that a different similarity assumption is required to close the gap between the heterogeneous and homogeneous results. Recall Theorem 2.3. The local minima of the functions fi are not the same. This motivates us to explore an alternative assumption known as the interpolation assumption (Vaswani et al., 2019). This assumption provides another way to capture the similarity among the functions fi by requiring that they share the same set of minimizers as the function f . Assumption 3.1 (Weak Interpolation). If x∗ is a minimizer of f , that is, ∇f (x∗ ) = 0, then x∗ is also a minimizer of each fi for all i ∈ [n]. Interpolation is a property of the solutions of fi , whereas the heterogeneity assumptions, Assumptions 2.1 and 2.2, concern the gradients and Hessians. These are different characteristics of fi (see Remark 3.5). Assumption 3.1 is considered practical in modern optimization literature, as there is evidence that it holds for large deep learning models (Zou & Gu, 2019; Zhang et al., 2021). However, as we show next, this assumption alone is not sufficient to achieve improved time complexity, leading to yet another pessimistic result: Theorem 3.2 (Lower Bound). Consider any randomized method under the fixed computation model 2 and assume that n ≥ 2. Let us fix any ε, L max ,nR, µ, σ > 0 such that µ < Lmax /(2n), ε < 0.01, P σ2 and R > 10. For any time budget t ≤ c0 n1 τi εnµ 2 , where c0 is a universal constant, there i=1

Table 1: The summary of our results and the time complexities (up to logarithmic factors) to get a 2 point x̄ such that E[∥x̄ − x∗ ∥ ] ≤ ε under the fixed computation model (worker i requires at most τi seconds to calculate one stochastic gradient; τ1 ≤ · · · ≤ τn ) and Assumptions 1.1, 1.2, 1.3, 1.4, and 1.5, where x̄∗ is the closest solution to x̄. The table compares methods in the fully heterogeneous setting and lists the extra assumptions the methods require to work. Method Minibatch SGD Asynchronous SGD

(Mishchenko et al., 2022)

Time Complexity Guarantees σ2 τn L µ + nεµ2 n −1 P 1 L 1 σ2 n τi µ + nεµ2

— {fi } are equal µ–strong convexity

i=1

Malenia SGD

τn L µ +

(Tyurin & Richtárik, 2023) (Theorem F.2)

Rennala SGD

(Tyurin & Richtárik, 2023) (Theorem F.1)

Additional Assumptions

min m∈[n]

1 m

1 n

m P 1 i=1

n P

τi

i=1

−1

τi

σ2 nεµ2

L σ2 µ + mεµ2

—

# {fi } are equal

Lower Bounds (new results) Under the first-order and second-order similarity, the following results state that it is infeasible to improve Malenia SGD in small-ε regimes: n P Assumptions 2.1 and 2.2 Any randomized method σ2 τi nεµ ≥ n1 2 (Theorem 2.3) (first-order and second-order similarity don’t help) i=1 Under weak interpolation, the following result states that it is infeasible to improve Malenia SGD in small-ε regimes: n P σ2 Assumption 3.1 τi nεµ ≥ n1 2

Any randomized method (Theorem 3.2)

i=1

The following results state that any randomized method can not improve Malenia SGD for small ε if we discard Assumption 3.3 or 3.4: n P Assumptions 3.1 and 3.4 Any randomized method σ2 τi nεµ ≥ n1 2 (weak interpolation is not enough) (Theorem 3.6) i=1 n P Any randomized method σ2 Assumption 3.3 ≥ n1 τi nεµ 2 (Theorem 3.7) i=1 Upper Bound (new result) The following results state that under Assumption 3.3 and 3.4 it is possible to improve Malenia SGD: " # −1 m P Assumptions 3.3 and 3.4 Rennala SGD Lmax 1 1 σ2 min + m τi µ mεµ2 (Theorem 3.8) (weaker than the equality of functions {fi }) m∈[n] i=1

Thus, even under Assumption 3.1, we can not improve the arithmetic mean dependence on {τi }. Takeaway 2: Using the weak interpolation assumption, which captures the similarity of the functions in a different way compared to first-order and second-order similarity, it is still infeasible to improve the pessimistic dependence on {τi } achieved by Malenia SGD using any randomized algorithm. 3.1

S TRONG INTERPOLATION AND LOCAL PŁ CONDITION ARE BOTH REQUIRED

Once again, we need to go deeper and introduce additional assumptions to break the lower bound from Theorem 3.2. To further investigate the problem, we now turn to two related assumptions. Assumption 3.3 (Strong Interpolation). For all i ∈ [n], a point x∗ is a minimizer of f , that is, ∇f (x∗ ) = 0, if and only if it is also a minimizer of fi . This assumption is clearly stronger than the weak interpolation assumption since it requires all the functions to share the set of minimizers (see Remark 3.9). 2

Assumption 3.4 (Local Polyak-Łojasiewicz condition). There exists µ such that ∥∇fi (x)∥ ≥ 2µ (fi (x) − fi∗ ) for all x ∈ Rd and for all i ∈ [n], where fi∗ is the finite optimal function value of fi . This assumption, unlike Assumption 1.5, requires each function to satisfy PŁ condition. Remark 3.5. The similarity and interpolation assumptions are neither disjoint nor does one imply the other. For example, consider fi (x) = 12 x2 + ci (1 − cos x), 0 ≤ ci < 1. These functions have the same unique minimizer x⋆ = 0 and are strongly convex and smooth, and thus satisfy strong interpolation and the local PŁ condition. At the same time, |fi′ (x) − fj′ (x)| = |ci − cj || sin x|, 7

|fi′′ (x) − fj′′ (x)| = |ci − cj || cos x|, so the first- and second-order similarity assumptions also hold. Conversely, the construction in Theorem 2.3 satisfies the similarity assumptions while interpolation fails. In the other direction, the functions fi (x) = ai x2 /2,ai > 0, have the same minimizer and satisfy the local PŁ condition, whereas for ai ̸= aj their gradient difference |(ai − aj )x| is unbounded. Thus, interpolation-type and similarity assumptions describe different, overlapping forms of heterogeneity. It turns out again that if we do not assume both Assumption 3.3 and Assumption 3.4, then it is infeasible for any randomized method to get a time complexity faster than in Malenia SGD (Theorem F.2) for ε small enough. This statement is formalized in the following two theorems. Theorem 3.6 (Lower Bound). Consider any randomized method under the fixed computation model 2 and assume that n ≥ 2. Let us fix any ε, L max ,nR, µ, σ > 0 such that µ < Lmax /(2n), ε < 0.01, P σ2 and R > 10. For any time budget t ≤ c0 n1 τi εnµ 2 , where c0 is a universal constant, there i=1

exist functions {fi } and stochastic gradients {∇fi (·; ·)} such that {fi } satisfy Assumptions 1.2, 1.3, 3.1, and 3.4 (Assumption 3.3 is not imposed and may or may not hold), f satisfies Assumptions 1.1 and 1.5 with L = Lmax , {∇fi (·; ·)} satisfy Assumption 1.4 such that the method cannot find ε– solution in terms of distances to the solution set after t seconds, when the method starts at a point in a distance less or equal to R to the closest solution. Theorem 3.7 (Lower Bound). Consider any randomized method under the fixed computation model 2 and assume that n ≥ 2. Let us fix any ε, L max ,nR, µ, σ > 0 such that µ < Lmax /(2n), ε < 0.01, P σ2 and R > 10. For any time budget t ≤ c0 n1 τi εnµ 2 , where c0 is a universal constant, there i=1

exist functions {fi } and stochastic gradients {∇fi (·; ·)} such that {fi } satisfy Assumptions 1.2, 1.3, 3.1, and 3.3 (Assumption 3.4 is not imposed and may or may not hold with parameter µ), f satisfy Assumptions 1.1 and 1.5 with L = Lmax , {∇fi (·; ·)} satisfy Assumption 1.4, such that the method cannot find ε–solution in terms of distances to the solution set after t seconds, when the method starts at a point in a distance less or equal to R to the closest solution. Takeaway 3: Even when the weak interpolation assumption is combined with only one of Assumptions 3.3 and 3.4, we still obtain only the arithmetic mean dependence on {τi }. Once we drop either Assumption 3.3 or Assumption 3.4, it becomes possible to construct a “bad” function (see the proof of theorems) that provides no room for any randomized method to improve. 3.2

F INALLY BRIDGING THE GAP

However, if assume that both Assumption 3.3 and Assumption 3.4 hold, then, finally, we can proof the convergence with harmonic-like dependence on {τi } : Theorem 3.8 (Upper Bound). Let Assumptions 1.2, 1.3, 1.4, 3.3, 3.4 hold1 . We choose wik = n/Pn B k for all k ≥ 0, i ∈ [n] in Algorithm 1 (reduces to Rennala SGD). We take γ = 1/Lmax , S = i i=1 h i 2 2 4σ 2/µLmax ε, and run Rennala SGD for k ≥ Ω Lmax log R iterations, then E xk+1 − xk+1 ≤ ∗ µ ε ε, where xk+1 is the closest xk+1 . Moreover, under fixed computation model, the ∗ "solution to # the ! −1 m P 2 2 Lmax 1 1 σ method requires O min log Rε seconds. m τi µ + mεµ2 m∈[n]

i=1

Under weaker assumptions, without requiring the equality of the functions {fi }, this theorem yields time complexity guarantees with a “harmonic”-like dependence on the times {τi } for the Rennala SGD method, improving upon the previous theoretical results in Theorem F.1 and (Tyurin 2023). Notice ithat the method in Theorem 3.8 is still biased because hP &PRichtárik, Pn Bik n k E ∇f (x; ξij )/ i=1 Bik ̸= ∇f (x) in general. That said, we can successfully prove i j=1 i=1 the theorem under this constraint. One of the primary reasons for this is the right choice of convergence metric. Initially, we aimed to analyze the biased gradient estimator in terms of function values 1 It is well-know that Assumption 1.2 implies Assumption 1.1. In Section G, we prove that Assumptions 1.3, 3.3 and Assumption 3.4 with constant µ imply Assumption 1.5 with constant µ/4.

and gradient norms, trying to prove that the method returns a point x̄ such that E[f (x̄)] − f ∗ ≤ ε or 2 2 E[∥∇f (x̄)∥ ] ≤ ε. However, the more appropriate approach is to show E[∥x̄ − x∗ ∥ ] ≤ ε. Using this convergence metric allows us to analyze the biased gradient estimator. This observation can be important on its own. Note that we can get convergence in terms of E[f (x̄)] − f ∗ ≤ ε using L–smoothness, but the result would be loose. One interesting observation is that we do not observe a regime where any other method or strategy improves upon both Malenia SGD and Rennala SGD. Takeaway 4: Improving the pessimistic dependence in Malenia SGD is possible with Rennala SGD and the additional assumptions, Assumption 3.3 and Assumption 3.4, in convex optimization. Remark 3.9. Theorem 3.8 is proved under the strong interpolation assumption. This assumption is essential for our result: even relaxing strong interpolation to weak interpolation is insufficient to improve the pessimistic time complexity achieved by Malenia SGD. At the same time, strong interpolation does not require the local functions fi to be identical. For example, consider the least-squares problems fi (x) = 21 ∥Ai (x − x⋆ )∥2 , where the matrices Ai can be different but have a common kernel N . Then argmin fi = x⋆ + N for every worker i, so the strong interpolation assumption holds. Thus, this setting provides a concrete machine-learning example with heterogeneous, non-identical local functions covered by Theorem 3.8. 3.3

E XTENSION TO NONCONVEX AND GENERAL CONVEX OPTIMIZATION

Although in this paper we focus on the convergence metric E[∥xk − x∗ ∥2 ] under Assumptions 1.1, 1.2, 1.3, 1.4, and 1.5, we briefly sketch how the constructions behind Theorems 2.3, 3.2, 3.6, and 3.7 may extend to general convex optimization in terms of function values and to nonconvex optimization in terms of gradient norms. Indeed, in the general convex optimization setting, we typically consider Assumptions 1.1, 1.3, and 1.4. The same constructions can be considered with 2 f (x) − f ∗ = µ2 ∥x − x∗ ∥ , where µ = L. For sufficiently small ε, applying the construction in the proof of Theorem 3.7 with squared-distance accuracy 2ε/µ suggests a lower bound of order σ2 Pn Ω n1 i=1 τi εnL seconds for finding x̄ such that E [f (x̄)] − f ∗ ≤ ε. Similarly, applying the con 2 Pn struction with squared-distance accuracy ε/L2 suggests a lower bound of order Ω n1 i=1 τi σεn 2 seconds for finding x̄ such that E[∥∇f (x̄)∥ ] ≤ ε. In nonconvex optimization, we consider Assumptions 1.1 and 1.4, and may use the same (convex) construction to prove the lower bounds. These observations suggest that the importance of Assumptions 3.3 and 3.4 for improving the arithmeticmean dependence may extend to other optimization settings. However, obtaining tight dependence on other parameters such as L and ε would require a different construction and is left for future work.

C ONCLUSIONS

In this work, we investigated various assumptions and setups in an effort to break the pessimistic dependence on {τi } achieved by Malenia SGD. We considered the first- and second-order similarity, strong growth, and interpolation assumptions. We proved that under the first- and second-order similarity assumptions, it is infeasible to improve the dependence on the arithmetic mean of {τi } with any randomized algorithm. We also showed that under weak interpolation (Assumption 3.1), it is likewise not possible for any randomized algorithm to improve upon the result of Malenia SGD. Subsequently, we presented new theoretical results that provide improved time complexity guarantees in the heterogeneous setting, without assuming that the functions fi are identical (Theorem 3.8). These results are obtained under the standard assumptions of convex optimization, together with Assumptions 3.3 and 3.4. Importantly, we have not merely introduced these assumptions to close the gap, but have shown that neither Assumption 3.3 nor Assumption 3.4 can be dropped in general within our setting, highlighting the fundamental limits of heterogeneous stochastic optimization. At the same time, we acknowledge that strong interpolation is a restrictive assumption in heterogeneous settings, as it requires the local functions to share the same set of minimizers. Identifying this fundamental difficulty is one of the main goals of our work. There are many unexplored directions that can build on our initial results and observations. While we focused on the most common assumptions in federated and distributed learning, our findings may inspire the development of new assumptions and settings where it is possible to improve upon Malenia 9

SGD. Moreover, our upper bounds and lower bounds were investigated in terms of E[∥xk − x∗ ∥2 ]

convergence, and the lower bounds are only tight up to logarithmic factors and in small-ε regimes. It would be interesting to see whether tight lower bounds can be obtained in terms of E[∥∇f (xk )∥2 ] in the non-convex setting, and in terms of E[f (xk )] − f ∗ for convex functions.

R EFERENCES Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances in Neural Information Processing Systems, 28, 2015. Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Algorithmic Learning Theory, pp. 111–132. PMLR, 2020. Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1–50, 2022. Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71–120, 2020. Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances in Neural Information Processing Systems, 34: 9024–9035, 2021. Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. Advances in Neural Information Processing Systems, 24, 2011. Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and stale gradients can win the race: Error-runtime trade-offs in distributed SGD. In International Conference on Artificial Intelligence and Statistics, pp. 803–812. PMLR, 2018. Hamid Reza Feyzmahdavian and Mikael Johansson. Asynchronous iterations in optimization: New sequence results and sharper algorithmic guarantees. Journal of Machine Learning Research, 24 (158):1–75, 2023. Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61 (12):3740–3754, 2016. Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016. Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In International Conference on Machine Learning, pp. 5200–5209. PMLR, 2019. Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training imagenet in 1 hour. arXiv preprint arXiv:1706.02677, 2017. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770–778, 2016. Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems (NeurIPS), 2022. Rustem Islamov, Mher Safaryan, and Dan Alistarh. AsGrad: A sharp unified analysis of asynchronousSGD algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 649–657. PMLR, 2024. 10

Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximalgradient methods under the polyak-łojasiewicz condition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pp. 795–811. Springer, 2016. Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. Advances in Neural Information Processing Systems (NeurIPS), 2022. Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492, 2016. Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, 2009. Guanghui Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020. Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. Advances in Neural Information Processing Systems, 28, 2015. Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In International Conference on Machine Learning, pp. 7111–7123. PMLR, 2021. Artavazd Maranjyan and Peter Richtárik. Ringleader asgd: The first asynchronous sgd with optimal time complexity under data heterogeneity. In International Conference on Learning Representations, volume 2026, pp. 4738–4768, 2026. Artavazd Maranjyan, Alexander Tyurin, and Peter Richtárik. Ringmaster ASGD: The first asynchronous SGD with optimal time complexity. In International Conference on Machine Learning, 2025. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pp. 1273–1282. PMLR, 2017. Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances in Neural Information Processing Systems (NeurIPS), 2022. Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983. Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018. Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference on Machine Learning, pp. 3027–3036. PMLR, 2017. Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv:1308.6370, 2013. Suvrit Sra, Adams Wei Yu, Mu Li, and Alex Smola. Adadelay: Delay adaptive distributed stochastic optimization. In Artificial Intelligence and Statistics, pp. 957–965. PMLR, 2016. Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: SGD with delayed gradients. Journal of Machine Learning Research, 21(237):1–36, 2020. Rafał Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. In International Conference on Learning Representations, 2021. Alexander Tyurin. Tight time complexities in parallel stochastic optimization with arbitrary computation dynamics. In International Conference on Learning Representations (ICLR), 2025. 11

Alexander Tyurin and Peter Richtárik. Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. Advances in Neural Information Processing Systems (NeurIPS), 2023. Alexander Tyurin, Kaja Gruntkowska, and Peter Richtárik. Freya PAGE: First optimal time complexity for large-scale nonconvex finite-sum optimization with heterogeneous asynchronous computations. Advances in Neural Information Processing Systems (NeurIPS), 2024. Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon LacosteJulien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Advances in neural information processing systems, 32, 2019. Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019. Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. Advances in Neural Information Processing Systems, 29, 2016. Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Advances in Neural Information Processing Systems, 31, 2018. Xuyang Wu, Sindri Magnusson, Hamid Reza Feyzmahdavian, and Mikael Johansson. Delay-adaptive step-sizes for asynchronous learning. arXiv preprint arXiv:2202.08550, 2022. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107–115, 2021. Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-aware async-sgd for distributed deep learning. arXiv preprint arXiv:1511.05950, 2015. Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.

C ONTENTS 1

Introduction

1.1

Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

First-Order and Second-Order Similarity Don’t Help

Understanding the Gap via Interpolation Assumptions

3.1

Strong interpolation and local PŁ condition are both required . . . . . . . . . . . .

3.2

Finally bridging the gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3

Extension to nonconvex and general convex optimization . . . . . . . . . . . . . .

Conclusions

A Arbitrarily computation dynamics

B Proof of the Main Results

C Proof of Lower Bounds

D Auxiliary Results

E Lower Bound in the Heterogeneous Convex Setting

F Proof of Theorems F.1 and F.2

G Assumptions 1.3, 3.3 and 3.4 imply Assumption 1.5

H Experiments

H.1 Without interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

H.2 With interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

H.3 ResNet-18 and CIFAR-10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Experiments Details

I.1

Quadratic optimization task generation procedure . . . . . . . . . . . . . . . . . .

I.2

Experiments with ResNet and CIFAR-10 . . . . . . . . . . . . . . . . . . . . . . .

A RBITRARILY COMPUTATION DYNAMICS

Our new result can be readily extended to the universal computation model. To encompass virtually all computation scenarios, assume that each worker i performs computations based on a computation power function vi : R+ → R+ . Then the number of stochastic gradients that worker i can calculate from a time t0 to a time t1 is an integral of the computation power vi followed by the floor operation: Z t1 “# of stoch. grad. in [t0 , t1 ]” = vi (τ )dτ . (8) t0

For instance, if worker i is inactive for the first t seconds and then active again, it would mean vi (τ ) = 0 for all τ ≤ t and vi (τ ) > 0 for all τ > t. Using the universal computation model, we can prove the theorem: Theorem A.1. Consider the assumptions, algorithm, and parameters from Theorem 3.8. Then, m seconds, where the sequence {t̄ } is defined Rennala SGD converges after at most t̄l Lmax 2 k log R c× µ

recursively as t̄k := ( min t ≥ 0 :

n P i=1

$Z t

% vi (τ )dτ

) ≥ max {⌈2S⌉ , 1}

(9)

t̄k−1

for all k ≥ 1 (t̄0 ≡ 0), and c is a universal constant. A similar result was obtained in (Tyurin, 2025). However, Tyurin (2025) requires the equality of the functions {fi }.

P ROOF OF THE M AIN R ESULTS

Theorem 3.8 (Upper Bound). Let Assumptions 1.2, 1.3, 1.4, 3.3, 3.4 hold2 . We choose wik = n/Pn B k for all k ≥ 0, i ∈ [n] in Algorithm 1 (reduces to Rennala SGD). We take γ = 1/Lmax , S = i i=1 h i Lmax R2 µ log ε k+1

4σ 2/µLmax ε, and run Rennala SGD for k ≥ Ω

xk+1 − xk+1 ∗

iterations, then E

≤

ε, where xk+1 is the closest x . Moreover, under fixed computation model, the ∗ # the ! "solution to −1 m P 2 2 Lmax σ 1 1 log Rε seconds. method requires O min m τi µ + mεµ2 m∈[n] i=1 Proof. Let us define xk∗ as an euclidean projection of the point xk+1 on to the solution set of the main problem (1), and take the condition expectation Ek [·] w.r.t. the randomness from the iteration k only. Then we have h i h i 2 k+1 k 2 Ek xk+1 − xk+1 ≤ E x − x k ∗ ∗ due to the projection’s properties. Then h i 2 Ek xk+1 − xk+1 ∗   2 Bik n 1 X kX   k w ∇fi (xk ; ξij ) − xk∗  ≤ Ek  xk − γ n i=1 i j=1 *

Bi X

+



Bi n 2  1 X kX k k = xk − xk∗ − 2γEk  xk − xk∗ , wik ∇fi (xk ; ξij )  + γ 2 Ek  wi ∇fi (xk ; ξij ) n i=1 n j=1 i=1 j=1 n 1X

Using unbiasedness (Assumption 1.4) and the variance decomposition equality, we get h i 2 Ek xk+1 − xk+1 ∗ 2 It is well-know that Assumption 1.2 implies Assumption 1.1. In Section G, we prove that Assumptions 1.3, 3.3 and Assumption 3.4 with constant µ imply Assumption 1.5 with constant µ/4.

  .

≤ x

2 − xk∗ − 2γ

+ γ2

* x

1 − xk∗ ,

n i=1

n 1X

wik Bik ∇fi (xk )

n i=1

n X

+ wik Bik ∇fi (xk ) 

Bi n  1 X kX k + γ 2 Ek  wi ∇fi (xk ; ξij ) − ∇fi (xk ) n i=1 j=1

  .

Consider the last term, due to the independence of stochastic gradients and Assumption 1.4, we ensure that   2 Bik n X X   1 k wik Ek  ∇fi (xk ; ξij ) − ∇fi (xk )  n i=1 j=1 k

Bi n n h i 1 X k 2X 1 X k 2 k 2 2 k = 2 (wi ) (w ) Bi σ . Ek ∇fi (xk ; ξij ≤ 2 ) − ∇fi (xk ) n i=1 n i=1 i j=1

Thus h i 2 Ek xk+1 − xk+1 ∗ ≤ x

(10)

n 2γ X k k 2 w B − xk∗ − n i=1 i i

− xk∗ , ∇fi (xk )

+γ

1X k k w B ∇fi (xk ) n i=1 i i

γ2 X k 2 k 2 (w ) Bi σ . n2 i=1 i

Pn We now consider the second and the third term. Since n1 i=1 wik Bik = 1, using Jensen’s inequality, we get * + 2 n n X X k k 1 k k k 2 1 k k k − 2γ x − x∗ , w B ∇fi (x ) + γ w B ∇fi (x ) n i=1 i i n i=1 i i * + n n X 1X k k 2 k k k k k 1 wi Bi ∇fi (x ) + γ 2 w B ∇fi (xk ) . ≤ −2γ x − x∗ , n i=1 n i=1 i i Due to Assumption 3.3, we get n n 1X k k 1X k k 2 k 2 w B ∇fi (x ) = w B ∇fi (xk ) − ∇fi (xk∗ ) n i=1 i i n i=1 i i n

≤

1X k k w B Li xk − xk∗ , ∇fi (xk ) − ∇fi (xk∗ ) n i=1 i i n

≤ Lmax

1X k k k w B x − xk∗ , ∇fi (xk ) − ∇fi (xk∗ ) n i=1 i i

= Lmax

1X k k k w B x − xk∗ , ∇fi (xk ) . n i=1 i i

In the first inequality, we use Lemma D.1 under Assumption 1.2 and convexity (Assumption 1.3). In the second inequality, we use the bound Li ≤ Lmax for all i ∈ [n]. Taking γ ≤ 1/Lmax and substituting the last inequality to (10), we obtain h i 2 Ek xk+1 − xk+1 ∗ ≤ xk − xk∗

≤ xk − xk∗

− (2γ − Lmax γ 2 ) −γ

1X k k k γ2 X k 2 k 2 wi Bi x − xk∗ , ∇fi (xk ) + 2 (w ) Bi σ n i=1 n i=1 i

n n 1X k k k γ2 X k 2 k 2 wi Bi x − xk∗ , ∇fi (xk ) + 2 (w ) Bi σ . n i=1 n i=1 i

Using the convexity, Assumption 3.4, and Lemma D.2, we get i h 2 Ek xk+1 − xk+1 ∗ ≤ xk − xk∗ We take wik = n/

k i=1 Bi

−

n n γµ 1 X k k k γ2 X k 2 k 2 2 wi Bi x − xk∗ + 2 (w ) Bi σ . 2 n i=1 n i=1 i

in the theorem for all i ∈ [n]. Thus

γ 2 σ2 γµ k 2 x − xk∗ + Pn . ≤ 1− k 2 i=1 Bi Pn In Algorithm 1, with the chosen weights {wik }, we wait for the moment when i=1 Bik > S. Thus h

h Ek

xk+1 − xk+1 ∗

γµ k γ 2 σ2 2 ≤ 1− x − xk∗ + . 2 S

Unrolling the recursion and taking the full expectation, we obtain h E

xk+1 − xk+1 ∗

k X γµ k+1 0 γµ j γ 2 σ 2 2 ≤ 1− x − x0∗ + 1− 2 2 S j=0

γµ k+1 0 2γσ 2 2 ≤ 1− x − x0∗ + . 2 µS h i 2 Due the choice of γ, S, and the condition on k, we have E xk+1 − xk+1 ≤ ε. ∗ It is sufficient to run the method for Lmax R2 O log µ ε Pn iterations. In each iteration, the method has to ensure that i=1 Bik > S. A sufficient time for that is   !−1 m 2 X 1 4σ 1 . 1+ 2 min  m i=1 τi mLmax εµ m∈[n]

under the fixed computation model (see Theorem 11 in (Tyurin et al., 2024)). Theorem A.1. Consider the assumptions, algorithm, and parameters from Theorem 3.8. Then, m seconds, where the sequence {t̄ } is defined Rennala SGD converges after at most t̄l Lmax 2 k c× log R µ

recursively as t̄k := ( min t ≥ 0 :

n P i=1

$Z t

% vi (τ )dτ

) ≥ max {⌈2S⌉ , 1}

(9)

t̄k−1

for all k ≥ 1 (t̄0 ≡ 0), and c is a universal constant. Proof. From the proof of Theorem 3.8, we know that it is sufficient to run the method for c×

R2 Lmax log µ ε

iterations, where c is a universal constant. The method waits the moment when each iteration. The workers work in parallel, and for all i ∈ [n], will calculate Z t vi (τ )dτ 0

k i=1 Bi > S in

k Pn jR t stochastic gradients after t seconds. In total, all workers will calculate i=1 0 vi (τ )dτ stochastic gradients. Hence, the first iteration will end by ( ) n Z t X t̄1 := min t ≥ 0 : vi (τ )dτ ≥ max {⌈2S⌉ , 1} , i=1

seconds. After that, the second iteration starts before time t̄1 and ends no later than time ( ) n Z t X t̄2 := min t ≥ 0 : vi (τ )dτ ≥ max {⌈2S⌉ , 1} , i=1

t̄1

because worker i can calculate at least Z t

vi (τ )dτ

t̄1

stochastic gradients between the end of the first iteration and a time t. Using the same reasoning, we can recursively define t̄3 , . . . , t̄lc× Lmax log R2 m . µ

The algorithm will converge by t̄l

c× Lmax log Rε µ

m seconds due to the discussion at the beginning of

the theorem.

P ROOF OF L OWER B OUNDS

the method cannot produce a point x̄ such that E ∥x̄ − x∗ ∥ minimizer of f.

≤ ε within t seconds, where x∗ is the

Proof. We assume that φi ∈ [−1, 1] for all i ∈ [n] and define them later. The first-order similarity of these functions is 2

max max ∥∇fi (x) − ∇fj (x)∥ ≤ 2β 2 .

x∈Rn i,j∈[n]

Thus, the parameter β from the construction controls this similarity. Taking β small, we increase similarity between the functions. Notice that the second-order similarity between the functions i is zero since ∇2 fi (x) = µI for all i ∈ [n]. The optimal point is x∗ such that x∗i = βφ µn and 2

≤ µβ2 n ≤ R2 . j k Let Ni (t) := τti denote an upper bound on the number of stochastic gradients returned by worker i by time t. For every stochastic gradient returned by worker i, the method gets ξ ∇fi (x̄; ξ) = µx̄ − βφi ei + ξei = µx̄ − β φi − ei (11) β x0 − x ∗

where x̄ is a query point and ξ ∼ N (0, σ 2 ). Therefore, all the information obtained from worker i 2 about φi consists of at most Ni (t) independent observations from N (φi , βσ2 ). 17

Let x̄t be the point returned by the algorithm at time t for the objective parametrized by φ. Then, 2 2 n n X β 2 X µn βφi 2 ∥x̄t − x∗ ∥ = = 2 2 (x̄t )i − (x̄t )i − φi . µn µ n i=1 β i=1 2

Thus, we reduced the problem to estimating φi using the observations N (φi , βσ2 ). Using the classical statistical result (e.g., Example 15.4 from (Wainwright, 2019)), for a universal constant c2 > 0, n h i β2 X σ2 ∗ 2 sup E ∥x̄t − x ∥ ≥ c2 2 2 min 1, 2 , µ n i=1 β Ni (t) φ∈[−1,1]n where x̄t depends on φ. Thus, n h i β2 X σ 2 τi 2 E ∥x̄t − x∗ ∥ ≥ c2 2 2 min 1, 2 . µ n i=1 β t φ∈[−1,1]n sup

We take n σ2 X τi , µ2 n2 ε i=1

T = c1 where c1 is a universal constant. Then,

n h i σ 2 τi β2 X 2 min 1, 2 E ∥x̄t − x∗ ∥ ≥ c2 2 2 µ n i=1 β T φ∈[−1,1]n sup

due to the bound on t. The condition on ε ensures that σβ 2τTi ≤ 1 for all i ∈ [n]. Therefore, h i 2 sup E ∥x̄t − x∗ ∥ ≥ 2ε.

(12)

φ∈[−1,1]n

h i 2 Finally, E ∥x̄t − x∗ ∥ > ε after t seconds for some φ due to (12). The adversary can choose this φ. Theorem 3.6 (Lower Bound). Consider any randomized method under the fixed computation model 2 and assume that n ≥ 2. Let us fix any ε, L max ,nR, µ, σ > 0 such that µ < Lmax /(2n), ε < 0.01, P σ2 and R > 10. For any time budget t ≤ c0 n1 τi εnµ 2 , where c0 is a universal constant, there i=1

exist functions {fi } and stochastic gradients {∇fi (·; ·)} such that {fi } satisfy Assumptions 1.2, 1.3, 3.1, and 3.4 (Assumption 3.3 is not imposed and may or may not hold), f satisfies Assumptions 1.1 and 1.5 with L = Lmax , {∇fi (·; ·)} satisfy Assumption 1.4 such that the method cannot find ε– solution in terms of distances to the solution set after t seconds, when the method starts at a point in a distance less or equal to R to the closest solution. Proof. p Without loss of generality, assume that the method starts at 0. Let Sτ = ai = R τi /Sτ . For all i ∈ [n], φi ∈ [−ai , ai ] is defined later, and fi (x) =

nµ 2 ⟨x − φ, ei ⟩ , 2

∇fi (x; ξi ) = nµ ⟨x − φ, ei ⟩ ei + ξi ei ,

where ξi ∼ N (0, σ 2 ). The average function is f (x) =

µ 2 ∥x − φ∥ , 2

and its unique minimizer is x∗ = φ. Moreover, ∥φ∥ ≤ R. Each fi is convex and smooth with parameter nµ ≤ Lmax , and 2

∥∇fi (x)∥ = 2nµfi (x) ≥ 2µfi (x). 18

i=1 τi and

Hence Assumptions 1.3, 1.2, and 3.4 hold. The function f is smooth with parameter µ ≤ Lmax and satisfies the global PŁ condition with constant µ. Assumption 3.1 holds because φ minimizes every fi , while Assumption 3.3 does not hold in general because arg min fi = {x ∈ Rn : xi = φi } ̸= {φ} = arg min f. Finally, the stochastic gradients are unbiased and have variance σ 2 . The rest of the proof is the same as the proof of Theorem 2.3. Every stochastic gradient returned by worker i gives an observation from N (φi , σ 2 /(n2 µ2 )). Let Ni (t) := ⌊t/τi ⌋ be an upper bound on the number of stochastic gradients calculated by worker i by time t. The same Gaussian mean-estimation lower bound gives n h i X σ2 2 2 sup E ∥x̄t − φ∥ ≥ c1 min ai , 2 2 n µ Ni (t) φi ∈[−ai ,ai ] i=1 i∈[n]

σ 2 Sτ ≥ c1 min R , 2 2 n µ t

≥ 2ε

for a universal constant c1 > 0, where x̄t any possible query point by time t for the objective with φ. The second inequality follows from Ni (t) ≤ t/τi and a2i = R2 τi /Sτ , which imply σ2 τi σ 2 Sτ min a2i , 2 2 ≥ min R2 , 2 2 , n µ Ni (t) Sτ n µ t Pn where remains to sum over i and use i=1 τi /Sτ = 1. The third inequality follows from ε < 0.01, R > 10, and the condition on t. Finally, h i 2 E ∥x̄t − φ∥ > ε for some φi ∈ [−ai , ai ], which the adversary can choose. Theorem 3.2 (Lower Bound). Consider any randomized method under the fixed computation model 2 and assume that n ≥ 2. Let us fix any ε, L max ,nR, µ, σ > 0 such that µ < Lmax /(2n), ε < 0.01, P σ2 and R > 10. For any time budget t ≤ c0 n1 τi εnµ 2 , where c0 is a universal constant, there i=1

exist functions {fi } and stochastic gradients {∇fi (·; ·)} such that {fi } satisfy Assumptions 1.2, 1.3, and 3.1, f satisfies Assumptions 1.1 and 1.5 with L = Lmax , {∇fi (·; ·)} satisfy Assumption 1.4 such that the method cannot find ε–solution in terms of distances to the solution set after t seconds, when the method starts at a point in a distance less or equal to R to the closest solution. Proof. The theorem is a simple corollary of Theorem 3.6 because Theorem 3.6 is stated under more strict assumptions on the class of the functions and stochastic gradients. The result of Theorem 3.6 holds even under additional Assumption 3.4. Theorem 3.7 (Lower Bound). Consider any randomized method under the fixed computation model 2 and assume that n ≥ 2. Let us fix any ε, L max ,nR, µ, σ > 0 such that µ < Lmax /(2n), ε < 0.01, P σ2 and R > 10. For any time budget t ≤ c0 n1 τi εnµ 2 , where c0 is a universal constant, there i=1

nµτi , Sτ

fi (x) =

ai (x − φ)2 , 2 19

∇fi (x; ξi ) = ai (x − φ) + ξi ,

i=1 τi , take

where ξi ∼ N (0, σ 2 ) and φ ∈ [−R, R] is defined later. Since n1

i=1 ai = µ,

µ (x − φ)2 . 2

f (x) =

Thus, f satisfies the global PŁ condition with constant µ, and every fi is convex and ai –smooth with ai ≤ nµ ≤ Lmax . Moreover, all the functions have the same unique minimizer φ, so Assumptions 3.1 2 and 3.3 hold. Notice that ∥∇fi (x)∥ = 2ai (fi (x)−fi∗ ). Finally, the stochastic gradients are unbiased 2 and have variance σ . Every stochastic gradient returned by worker i gives an observation from N (φ, σ 2 /a2i ). Let Ni (t) := ⌊t/τi ⌋ be an upper bound on the number of stochastic gradients computed by worker i by time t. Let Pφt be the joint distribution of these observations by time t. For Gaussians with the same variance, the KL divergence DKL (N (m1 , v) ∥ N (m0 , v)) = (m1 − m0 )2 /(2v). By the chain rule for KL divergence, DKL Pφt

t P−φ

≤

n X 2φ2 a2 i

σ2

i=1 1 because Ni (t) ≤ τti . Since t ≤ 100

1 n

i=1 τi

t 2tφ2 n2 µ2 = τi σ 2 Sτ

σ2 εnµ2 , we get

φ2 t DKL Pφt P−φ ≤ . 32ε Choosing any √ √ φ ∈ {−4 ε, 4 ε}, 1 t we ensure that −φ, φ ∈ [−R, R] (since ε < 0.01 and R > 10) and DKL Pφt P−φ ≤ 2 . Pinsker’s t t inequality gives Pφ − P−φ TV ≤ 1/2. Hence, the two-point Le Cam bound (Wainwright, 2019) gives h i 2 max E |x̄ − φ| ≥ 4ε, t √ √ φ∈{−4 ε,4 ε}

where x̄t is the random variable that the random algorithm can produce based on all available information up to time thfor the objective with i h parameter i φ. Thus, the adversary can take φ = 2 2 √ √ arg maxφ∈{−4 ε,4 ε} E |x̄t − φ| to get E |x̄t − φ| > ε.

AUXILIARY R ESULTS

In this section, we present well-known results from optimization. Lemma D.1 (Nesterov (2018)). Let f : Rd → R be a function, which L–smooth and convex. Then for all x, y ∈ Rd we have: 2

∥∇f (x) − ∇f (y)∥ ≤ L ⟨∇f (x) − ∇f (y), x − y⟩ .

(13)

Lemma D.2 (Karimi et al. (2016)). Let f : Rd → R be a convex function, which satisfies PŁ condition with a parameter µ (Assumption 1.5). Then, for all x ∈ Rd , we have µ 2 ⟨∇f (x), x − x̄∗ ⟩ ≥ ∥x̄∗ − x∥ (14) 2 where x̄∗ is the projection of x onto the solution set of min f (x). x∈Rd

L OWER B OUND IN THE H ETEROGENEOUS C ONVEX S ETTING

This section complements the results from (Tyurin & Richtárik, 2023), where the authors only prove the optimal time complexities in the homogeneous nonconvex, heterogeneous nonconvex, and homogeneous convex settings. Here, we resolve the last piece, the heterogeneous convex setting. 20

Protocol 2 Time Multiple Oracles Protocol 1: Input: function(s) f ∈ F , oracles and distributions ((O1 , ..., On ), (D1 , ..., Dn )) ∈ O(f ),

algorithm A ∈ A 2: s0i = 0 for all i ∈ [n] 3: for k = 0, . . . , ∞ do 4: (tk+1 , ik+1 , xk ) = Ak (g 1 , . . . , g k ), 5: (sk+1 , g k+1 ) = Oik+1 (tk+1 , xk , skik+1 , ξ k+1 ), ik+1 6: end for

▷ tk+1 ≥ tk ∀j ̸= ik+1

▷ sk+1 = skj j

ξ k+1 ∼ Dik+1

Following Tyurin & Richtárik (2023), we have to formalize and introduce the following protocol and classes. We investigate the optimization problem (1) when the function f is convex. For the convex case, using Protocol 2, we use the complexity measure ( ) h i k(t) mtime (A, F) := inf inf t ≥ 0 sup sup E f (x ) − inf f (x) ≤ ε , (15) A∈A

x∈Q

f ∈F (O,D)∈O(f )

where xk is generated by Protocol 2, k(t) is the largest index such that tk(t) ≤ t, and Q is a convex set. Let us take any set Q, and consider the following class of convex functions. conv Definition E.1 (Function Class FQ,L ). d We assume that a function f : R → R is convex, differentiable, L-smooth on the set Q, i.e., ∥∇f (x) − ∇f (y)∥ ≤ L ∥x − y∥

∀x, y ∈ Q.

conv A set of all functions with such properties we define as FQ,L .

Definition E.2 (Algorithm Class Azr ). An algorithm A = {Ak }∞ k=0 is a sequence such that Ak : Rd × · · · × Rd → R≥0 × Rd {z } |

∀k ≥ 1, A0 ∈ R≥0 × Rd ,

k times

and, for all k ≥ 1 and g , . . . , g k ∈ Rd , tk+1 ≥ tk , where tk+1 and tk are defined as (tk+1 , ·) = Ak (g 1 , . . . , g k ) and (tk , ·) = Ak−1 (g 1 , . . . , g k−1 ). Moreover, xk ∈ Q for all k ≥ 0. The following oracle helps to formalize the fixed computation model. Rd × (R≥0 × Rd × {0, 1}) ×Sξ → (R≥0 × Rd × {0, 1}) ×Rd Oτ∇f : R≥0 × |{z} {z } | {z } |{z} | time

point

output state

input state

 0), ((t, x, 1), 0), such that Oτ∇f (t, x, (st , sx , sq ), ξ) = ((st , sx , 1),  ((0, 0, 0), ∇f (sx ; ξ)),

sq = 0, sq = 1 and t < st + τ, sq = 1 and t ≥ st + τ, (16)

and ∇f (·; ·) is a stochastic mapping. 2

Definition E.3 (Oracle Class Oτconv,σ ). 1 ,...,τn conv Let us consider an oracle class such that, for any f ∈ FQ,L , it returns oracles Oi = Oτ∇ifi and distributions Di for all i ∈ [n], where ∇fi (·; ·) is an unbiased σ 2 -variance-bounded mapping on the set Q of the gradient of the local function in worker i. The oracles Oτ∇ifi are defined in (16). We 2 define such oracle class as Oτconv,σ . Without loss of generality, we assume that 0 < τ1 ≤ · · · ≤ τn . 1 ,...,τn Notice that this oracle class differs from the oracle class for convex functions in (Tyurin & Richtárik, 2023) because we consider the heterogeneous setting where the oracles return unbiased stochastic gradients of the local functions fi , which can be different. We refer the reader to (Tyurin & Richtárik, 2023) for additional details about the time complexities formalization. We are now ready to state the theorem. 21

Theorem E.4 (Informal theorem (see the formal Theorem E.5)). Let Assumptions 1.3, 1.1, and 1.4 hold. It is impossible to converge faster than ! ! n X √ 2 2 √ Θ τn LR/ ε + 1/n τi σ R /nε2 i=1

seconds under the fixed computation model. 2

Theorem E.5. Let us consider the oracle class Oτconv,σ for some σ 2 > 0 and 0 < τ1 ≤ · · · ≤ τn . 1 ,...,τn √ √ We fix any R, L, ε > 0 such that LR > c1 ε > 0. For any " √ # ! n LR 1X σ 2 R2 t ≤ c × τn √ + , τi n i=1 nε2 ε conv in the view Protocol 2, for any algorithm A ∈ Azr , there exists a set Q, a function f ∈ FQ,L and 2

oracles and distributions ((O1 , . . . , On ), (D1 , . . . , Dn )) ∈ Oτconv,σ (f ) such that 1 ,...,τn h i E f (xk(t) ) − inf f (x) > ε, x∈Q

where k(t) is the largest index such that tk(t) ≤ t, and R is the euclidean distance between 0 (starting point) and the closest solution x∗ ∈ Q. The quantities c1 , and c are universal constants. √

using the same idea Proof. First term. It is easy to prove the dependence on the first term τn √LR ε as in (Lu & De Sa, 2021; Tyurin & Richtárik, 2023; Huang et al., 2022). It is sufficient to put a “hard” convex function (Nesterov, 2018; Woodworth et al., 2018) to the slowest worker corresponding with the time τn = maxi∈[n] τi . In particular, we can consider the “hard” quadratic function f¯ from (Nesterov, 2018)[Section 2.1.2] and take the functions n × f¯(x), i = n fi (x) = 0, i < n. Pn conv for all x ∈ Rd . The function f = n1 i=1 fi = f¯ belongs to the class FQ,L . We take the stochastic gradients without noise, i.e., ∇fi (x; ξi ) = ∇fi (x) deterministically for all x ∈ Rd , ξi ∈ Sξi , and i ∈ [n]. It is clear that the only worker that can solve the problem is worker n, and it takes τn seconds √ to find one gradient by the oracle construction. Thus, the required time complexity is Θ τn √LR ε √ (Nesterov, 2018). since the required oracle complexity is Θ √LR ε Second term. The proof of the second term is slightly trickier and uses the construction from (Woodworth et al., 2018). Let us fix any algorithm. We use the proof of Lemma 10 from (Woodworth et al., 2018) that has the following result. For any σ 2 , B > 0 and any algorithm, it is possible to construct a one dimensional linear function g : R → R on the domain {x ∈ R : |x| ≤ B}, a stochastic gradient mapping ∇g : R × Sξ → R, and a distribution D such that σB E g(xN ) − min g(x) ≥ √ |x|≤B 8 N

(17)

after N queries of the oracle, where ∇g is unbiased and σ 2 -variance-bounded. The idea is to put a function gi to each worker but with different domain sizes. In particular, for all i ∈ [n], we take the function fi : Rn → R such that fi (x) = gi (xi ),

(18)

where gi is the function from Lemma 10 of (Woodworth et al., 2018) applied independently with B = Ri and N = Ni (t̄), and xi is the ith coordinate of a vector x. For all i ∈ [n], we consider the √ τ function fi on the domain {xi ∈ R | |xi | ≤ Ri }, where Ri := R × √Pn i . One can see that f i=1 τi

is convex, 0–smooth (because gi is linear). The distance between 0 and the optimal point is less or equal to R because n X

Ri2 =

i=1

n X

τi R2 Pn

= R2

i=1 τi

i=1

and the optimal point for the problem gi (xi ) → min|xi |≤Ri is either Ri or −Ri . We take Q = {x ∈ Rn : |xi | ≤ Ri

∀i ∈ [n]}.

Let us define the time n

σ 2 R2 t̄ := 256nε2

1X τi n i=1

! .

(19)

By the time t̄, worker i can calculate at most Ni (t̄) :=

t̄ τi

(20)

stochastic gradients. Therefore, n n (17) 1 X 1X σR p i E [f (x̄)] − min f (x) = E [gi (x̄i )] − min gi (xi ) ≥ x∈Q n i=1 n i=1 8 Ni (t̄) |xi |≤Ri √ n n (19),(20) X σR τi 1X 2ετ Pn i = 2ε. pPn p = ≥ n i=1 8 Ni (t̄) τ i=1 τi i=1 i i=1 where x̄ is any possible output of the algorithm before the time t̄.

P ROOF OF T HEOREMS F.1 AND F.2

Theorem F.1. Let Assumptions 1.1, 1.3, 1.4, and 1.5 hold, and the functions {fi } are equal. Let us k k+1 k 4σ 2 n Pn take γ = 1/L h and S = /µLεi, then Rennala SGD (Algorithm 1 with wi = / i=1 Bi ) finds x such that E

xk+1 − xk+1 ∗ O

≤ ε after " # ! −1 m P 1 σ2 R2 1 L min log ε m τi µ + mεµ2

m∈[n]

(21)

i=1

seconds, where xk+1 is the closest solution to xk+1 . ∗ Proof. Since the functions are equal, Rennala SGD is equivalent to xk+1 = xk − γgRk , k

:= Pn 1

k i=1 Bi

n B P Pi i=1 j=1

k ∇f (xk ; ξij ).

Clearly, gRk is unbiased and h Ek

gR − ∇f (x )

n X

Bik

i=1

!−2 n B k i XX

∇f (x

k ; ξij ) − ∇f (xk )

i=1 j=1

Rennala SGD waits for the moment when

h Ek

≤σ

n X

!−1 Bik

i=1

k k k n Pn i=1 Bi > S (see Alg. 1 with wi = / i=1 Bi ). Thus

gRk − ∇f (xk )

≤

σ2 µLε ≤ S 4

We can use Theorem F.3 to get i h γµ k+1 0 γLε 2 2 ≤ 1 − E xk+1 − xk+1 x − xk∗ + . ∗ 2 2 Since γ = L1 , we obtain i h µ k+1 0 ε 2 2 ≤ 1 − x − xk∗ + . E xk+1 − xk+1 ∗ 2L 2 The last inequality ensure that the method finds an ε–solution after R2 L log O µ ε Pn iterations. In each iteration, the method has to ensure that i=1 Bik > S. A sufficient time for that is   !−1 m X 1 1 2 min  (1 + S) . m i=1 τi m∈[n] under the fixed model (see Theorem 11 in (Tyurin et al., 2024)). It is left to multiply this computation L R2 time by O µ log ε . 2

Theorem F.2. Let Assumptions 1.1, 1.3, 1.4, and 1.5 hold. Let us take γ h= 1/L and S = 4σi/µLε, then Malenia SGD (Algorithm 1 with wik = 1/Bik ) finds xk+1 such that E after n P 1 R2 σ2 O τn L + log τ i µ n nεµ2 ε

xk+1 − xk+1 ∗

≤ε

(22)

i=1

seconds, where xk+1 is the closest solution to xk+1 . ∗ Proof. The proof of this theorem almost repeats the proof of Theorem F.1. The variance of Malenia SGD is     2 Bik n n h i 2 X X X 1 1  2  1  σ 1 k Ek gMk − ∇f (xk ) = Ek  ∇fi (xk ; ξij ) − ∇f (xk )  ≤ . n i=1 Bik j=1 n n j=1 Bik −1 Pn The method waits for the moment when n1 i=1 1/Bik > Sn . Therefore h i σ2 2 Ek gMk − ∇f (xk ) ≤ . S Using the same reasoning, the method finds an ε–solution after L R2 O log µ ε −1 Pn > Sn . A sufficient time iterations. In each iteration, the method has to ensure that n1 i=1 1/Bik for that is ! ! n 1X S t̄ = 2 τn + τi n i=1 n j k under the fixed computation model because the number of computed stochastic gradients Bik ≥ τt̄i , and n n n 1X 1 1X 1 1 X 2τi n j k ≤ ≤ < , k n i=1 Bi n i=1 t̄ n i=1 t̄ S τi

where we use ⌊x⌋ ≥ x2 for all x ≥ 1. Multiplying t̄ by O 24

L R2 µ log ε

, we get the result.

Theorem F.3. Consider the method (23) xk+1 = xk − γ∇f (xk ; ξ k ), h i 2 where Ek ∇f (xk ; ξ k ) = ∇f (xk ), Ek ∇f (xk ; ξ k ) − ∇f (xk ) ≤ σ 2 , and σ 2 > 0. Let As2

sumptions 1.3, 1.5, and 1.1 hold. Let us take γ = 1/L and S = 2σ /µLε, then the method finds xk+1 such that h i 2γσ 2 γµ k+1 0 2 2 x − xk∗ + , E xk+1 − xk+1 ≤ 1− ∗ 2 µ where xk+1 is the closest solution of min f (x) to xk+1 . ∗ x∈Rd

Proof. Using the properties of the projection and (23), we have i h i h 2 2 Ek xk+1 − xk+1 ≤ Ek xk+1 − xk∗ ∗ h i 2 = Ek xk − γ∇f (xk ; ξ k ) − xk∗ h i h i 2 2 = Ek xk − xk∗ − 2γEk ∇f (xk ; ξ k ), xk − xk∗ + γ 2 Ek ∇f (xk ; ξ k ) h i h i 2 2 = Ek xk − xk∗ − 2γ ∇f (xk ), xk − xk∗ + γ 2 Ek ∇f (xk ; ξ k ) .

In the last equality, we use the unbiasedness. Due the variance decomposition equality, we get h i i h i h 2 k k 2 2 k k k 2 k k k 2 k 2 Ek xk+1 − xk+1 ≤ E x − x + γ E ∇f (x ; ξ ) − ∇f (x ) − 2γ ∇f (x ), x − x + γ ∇f (x ) k k ∗ ∗ ∗ (24) Since the function f is L–smooth and ∇f (xk∗ ) = 0, we obtain − 2γ ∇f (xk ), xk − xk∗ + γ 2 ∇f (xk )

= −2γ ∇f (xk ) − ∇f (x∗ ), xk − xk∗ + γ 2 ∇f (xk ) − ∇f (x∗ )

≤ −2γ ∇f (xk ) − ∇f (x∗ ), xk − xk∗ + Lγ 2 ∇f (xk ) − ∇f (x∗ ), xk − xk∗ = γ (Lγ − 2) ∇f (xk ) − ∇f (x∗ ), xk − xk∗ . Taking γ ≤ L1 and substituting the inequality to (24), we get i h i i h h 2 2 2 . ≤ Ek xk − xk∗ − γ ∇f (xk ), xk − xk∗ + γ 2 Ek ∇f (xk ; ξ k ) − ∇f (xk ) Ek xk+1 − xk+1 ∗ The σ 2 –variance bounded ensures that h i h i 2 2 Ek xk+1 − xk+1 ≤ Ek xk − xk∗ − γ ∇f (xk ), xk − xk∗ + γ 2 σ 2 . ∗ Due to convexity and Assumption 1.5, we can use Lemma D.2, which yields h i h i γµ 2 k k 2 Ek xk+1 − xk+1 ≤ E x − x − xk − xk∗ + γ 2 σ 2 k ∗ ∗ 2 i γµ h k 2 Ek x − xk∗ + γ 2 σ2 . = 1− 2 Unrolling the recursion and taking the full expectation, we obtain h E

xk+1 − xk+1 ∗

γµ k+1 0 2γσ 2 2 ≤ 1− x − x0∗ + 2 µ

A SSUMPTIONS 1.3, 3.3 AND 3.4 IMPLY A SSUMPTION 1.5

Theorem G.1. Let {fi } satisfy Assumption 1.3, 3.3, and Assumption 3.4 with constant µ, then f satisfies Assumption 1.5 with constant µ4 . Proof. We fix x ∈ Rd . Since Assumption 3.3 hold, then the functions share the closest solution x∗ to x. Assumption 3.4 ensures that µ 2 fi (x) − fi (x∗ ) ≥ ∥x − x∗ ∥ . 2 for all i ∈ [n] (Karimi et al., 2016). Thus f (x) − f (x∗ ) ≥

µ 2 ∥x − x∗ ∥ . 2

Due to convexity, we get f (x∗ ) ≥ f (x) + ⟨∇f (x), x∗ − x⟩ . Therefore r f (x) − f (x∗ ) ≤ ⟨∇f (x), x − x∗ ⟩ ≤ ∥∇f (x)∥ ∥x − x∗ ∥ ≤ ∥∇f (x)∥ and µ 1 2 (f (x) − f (x∗ )) ≤ ∥∇f (x)∥ , 4 2 which is Assumption 1.5 with constant µ4 .

2p f (x) − f (x∗ ) µ

E XPERIMENTS

We conduct a comparison between Rennala SGD and Malenia SGD on both stochastic quadratic optimization tasks and real-world machine learning problems. These are standard quadratic optimization and computer vision problems, the design of which we explain in Section I. We developed a library that simulates the behavior of n = 100 workers. Both methods have two hyperparameters: step size γ and parameter S. We do a grid search for both methods and find the best pairs in all setups. We start with synthetic quadratic optimization problems, which are generated without and with the interpolation regime. The procedure is described in Section I.1. H.1

W ITHOUT INTERPOLATION

Malenia SGD: Step size: 1.0 Rennala SGD: Step size: 0.0625

f(xt) f(x * )

101 100

10 1 10 2 0

times (seconds)

1e6

Figure 1: Comparison of the methods on a quadratic optimization problem without interpolation. We take the computation time τi = i2 for all i ∈ [n].

In Figure 1, we present results without interpolation. The plots concur with the theory from Section 3, where we explain that it is essential to have interpolation to break the time complexity of Malenia SGD. Rennala SGD has biased gradient estimators and does not converge to a minimum of the quadratic optimization problem in Figure 1. H.2

W ITH INTERPOLATION

Malenia SGD: Step size: 2.0 Rennala SGD: Step size: 2.0

100

100 10 1

10 1

10 2

10 3

10 3 10 4

Malenia SGD: Step size: 2.0 Rennala SGD: Step size: 1.0

101

f(xt) f(x * )

101

10 4 0

10000

20000

30000

times (seconds)

10 5

40000

500

1000

1500

2000

2500

times (seconds)

3000

3500

4000

Figure 2: Comparison of the methods √ on quadratic optimization problems with interpolation. Times {τi } less diverse: Left plot: τi = i for all i ∈ [n]. Right plot: τ1 = 0.01, τ2 = 1, . . . , τn = 1.

In Figures 2 and 3, we consider the methods in the interpolation regime. As expected, according to Section 3.2, Rennala SGD outperforms Malenia SGD in all experiments. We compare the methods with different {τi }. In Figures 2, the times {τi } are less diverse, so the difference between the methods is less profound. In Figures 3, {τi } are more different; thus, we can see that Rennala SGD converges much faster to low function values because it has much less variance in the corresponding gradient estimator. 27

Malenia SGD: Step size: 1.0 Rennala SGD: Step size: 2.0

100

101 100 10 1 10 2 10 3 10 4 10 5 10 6

Malenia SGD: Step size: 1.0 Rennala SGD: Step size: 1.0

f(xt) f(x * )

101

10 1 10 2 10 3 0

times (seconds)

1e6

1000

2000

3000

4000

5000

times (seconds)

6000

7000

Figure 3: Comparison of the methods on quadratic optimization problems with interpolation. Times {τi } more diverse: Left plot: τi = i2 for all i ∈ [n]. Right plot: τ1 = 0.001, τ2 = 1, . . . , τn = 1. H.3

R ES N ET-18 AND CIFAR-10

We also verify how Rennala SGD and Malenia SGD work with ResNet-18 and the CIFAR-10 classification problem (Krizhevsky et al., 2009) (License: MIT). Both algorithms take step size γ = 0.25, sample a batch of size 128, and the smallest S such that all workers calculate at least one batch. The dataset CIFAR-10 is split between the workers, so we consider the heterogeneous setting; all workers access different samples. The results of the experiments are presented in Figure 4. One can see that Rennala SGD converges faster in terms of accuracy, which might be explained by the fact that neural networks work in the interpolation regime. Note that this is an empirical observation in the nonconvex setup, and explaining it from the theoretical point of view is an important future work. 0.95

Accuracy (Test)

0.90 0.85 0.80 0.75 0.700

5000

10000

15000

Malenia SGD: Step size: 0.25 Rennala SGD: Step size: 0.25

20000

times (seconds)

25000

30000

Figure 4: Comparison of the methods on the CIFAR-10 classification problem with ResNet-18. We take the computation time τi = i2 .

E XPERIMENTS D ETAILS

The experiments were run in Python 3 using an Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz. I.1

Q UADRATIC OPTIMIZATION TASK GENERATION PROCEDURE

In Section H, we perform experiments using synthetic quadratic optimization problems n 1X 1 ⊤ ⊤ min x Ai x − x bi . 2 x∈Rd n i=1 Below, we present the algorithm, based on (Szlendak et al., 2021), that generates these problems. In all experiments, we take s = 3 to ensure that the generated matrices are diverse. We take n = 100, d = 100, and λ = 0.001. The stochastic gradients are equal to the true gradients plus standard Gaussian noise added to the coordinates to emulate stochasticity. With these parameters and procedures, we run the experiments from Section H.1. To conduct the experiments from Section H.2 in the interpolation regime, we take the matrices A1 , · · · , An , vectors b1 ,P · · · , bn returned P by Algorithm 3. Let x̄∗ be the solution of the quadratic optimization problem n n 1 1 A x̄ = i ∗ i=1 i=1 bi . Then, we redefine the vectors {bi } as bi = Ai x̄∗ to ensure that we n n are working in the interpolation regime. With this strategy, the matrices are still different, and the functions {fi } are not equal. Algorithm 3 Generate quadratic optimization tasks 1: Parameters: number nodes n, dimension d, regularizer λ, and noise scale s. 2: for i = 1, . . . , n do 3: Generate random noises ηis = 1 + sζis and ηib = sζib , i.i.d. ζis , ζib ∼ N (0, 1) 4: 5:

ηs

Take vector bi = 4i (−1 + ηib , 0, · · · , 0) ∈ Rd Take the initial tridiagonal matrix  2 −1 Ai =

ηis   −1  4 

0  ..  .   ∈ Rd×d .. . −1  −1 2

6: end for Pn 7: Take the mean of matrices A = n1 i=1 Ai 8: Find the minimum eigenvalue λmin (A) 9: for i = 1, . . . , n do 10: Update matrix Ai = Ai + (λ − λmin (A))I 11: end for √ 12: Take starting point x0 = ( d, 0, · · · , 0) 13: Output: matrices A1 , · · · , An , vectors b1 , · · · , bn , starting point x0

I.2

E XPERIMENTS WITH R ES N ET AND CIFAR-10

In Section H.3, we consider the standard computer vision classification problem with ResNet-18 (He et al., 2016) and CIFAR-10 (Krizhevsky et al., 2009). We conduct the experiments using PyTorch and implement both Rennala SGD and Malenia SGD optimizers. For reproducibility, we use the default ResNet-18 architecture provided in PyTorch and split randomly and evenly the CIFAR-10 dataset across multiple workers to create a heterogeneous data distribution scenario. We use standard preprocessing techniques for CIFAR-10, including normalization and random cropping, and train the network for a fixed number of epochs. The performance metrics include top-1 accuracy. In total, we solve the optimization problem Pn 1 Pm min n1 i=1 m j=1 loss(ResNet(aij ; x), yij ) , x∈Rd

where “loss” is the standard cross-entropy loss, {aij , yij } are samples from CIFAR-10 splitted between the workers. 29

Record · ID 919377 · SHA-256 d276f8f223514081
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.