Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction
Authors: Alexander Tyurin
Venue: ICLR 2026 Poster (2026)
Keywords: nonconvex optimization
lower bounds
distributed optimization
Primary area: optimization

Abstract: We consider centralized distributed optimization in the classical federated learning setup, where $n$ workers jointly find an $\varepsilon$-stationary point of an $L$-smooth, $d$-dimensional nonconvex function $f$, having access only to unbiased stochastic gradients with variance $\sigma^2$. Each worker requires at most $h$ seconds to compute a stochastic gradient, and the communication times from the server to the workers and from the workers to the server are $\tau_{\textnormal{s}}$ and $\tau_{\textnormal{w}}$ seconds per coordinate, respectively. One of the main motivations for distributed optimization is to achieve scalability with respect to $n$. For instance, it is well known that the distributed version of \algname{SGD} has a variance-dependent runtime term $\frac{h \sigma^2 L \Delta}{n \varepsilon^2},$ which improves with the number of workers $n,$ where $\Delta := f(x^0) - f^*,$ and $x^0 \in \mathbb{R}^d$ is the starting point. Similarly, using unbiased sparsification compressors, it is possible to reduce \emph{both} the variance-dependent runtime term and the communication runtime term from $\tau_{\textnormal{w}} d \frac{L \Delta}{\varepsilon}$ to $\frac{\tau_{\textnormal{w}} d L \Delta}{n \varepsilon} + \sqrt{\frac{\tau_{\textnormal{w}} d h \sigma^2}{n \varepsilon}} \cdot \frac{L \Delta}{\varepsilon},$ which also benefits from increasing $n.$ However, once we account for the communication from the server to the workers $\tau_{\textnormal{s}}$, we prove that it becomes infeasible to design a method using unbiased random sparsification compressors that scales both the server-side communication runtime term $\tau_{\textnormal{s}} d \frac{L \Delta}{\varepsilon}$ and the variance-dependent runtime term $\frac{h \sigma^2 L \Delta}{\varepsilon^2},$ better than poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same function or distribution. Indeed, when $\tau_{\textnormal{s}} \simeq \tau_{\textnormal{w}},$ our lower bound is $\tilde{\Omega}(\min[h (\frac{\sigma^2}{n \varepsilon} + 1) \frac{L \Delta}{\varepsilon} + {\tau_{\textnormal{s}} d \frac{L \Delta}{\varepsilon}},\; h \frac{L \Delta}{\varepsilon} + {h \frac{\sigma^2 L \Delta}{\varepsilon^2}}]).$ To establish this result, we construct a new ``worst-case'' function and develop a new lower bound framework that reduces the analysis to the concentration of a random sum, for which we prove a concentration bound. These results reveal fundamental limitations in scaling distributed optimization, even under the homogeneous (i.i.d.) assumption.

Published as a conference paper at ICLR 2026
PROVING THE LIMITED SCALABILITY OF CENTRALIZED DISTRIBUTED OPTIMIZATION VIA A NEW LOWER BOUND CONSTRUCTION
Alexander Tyurin
AXXX, Moscow, Russia
Applied Al Institute, Moscow, Russia alexandert wuriiiiinnn narinngnn gma i com
ABSTRACT
We consider centralized distributed optimization in the classical federated learn- ing setup, where workers jointly find e-stationary point of T-smooth, d-dimennional nonconvex function f. having access only to unbiased stochastic gradients with variance o², Each worker requires most seconds compute a stochastic gradient, and the communication times from the server to the workers and from the workers the server are т and Tw seconds per coordinate, respectively. One of the main motivations for distributed optimization is to achieve scalability with respect to n. For instance, it is well known that the distributed version of SGD has variance-dependent runtime term ho Lo which improves with the number of workers n, where A := {(=") Similarly, using unbiased sparsification compressors, it is possible reduce both the variance-dependent runtime term and the communication runtime term from TudLA/s to 7. + /r,dhoo /ns LA/E, which also benefits from increasing n. However, once we account for the communication from the server the workers we prove that it becomes infeasible to design method using unbiased random sparsification compressors that scales both the server-side communication runtime term T.di.A/c and the variance- variance-dependent runtime term ooy hoRL//?" better than poly- logarithmically
f", and x E IRd is the starting point.
n, even in the homogeneous (i.i.d.) case, where all workers access the same function distribution. Indeed, when = Tw, our lower bound is á min h (²" ne +1) tTdL,, hLd + ho }) To establish this result, "worst-case" function and develop work that reduces the analysis to the concentration of random sum, for which we prove concentration bound. These results reveal fundamental limitations scaling distributed optimization, even under the homogencous (i.id.) assumption.
construct
lower bound frame-
INTRODUCTION
We focus on the classical federated learning setup, where n workers, such as CPUs, GPUs, servers, mobile devices, connected to a central server via a communication channel (Konečný et al., 2016; McMahan al., 2017). All workers collaboratively solve common optimization problem in a distributed fashion by computing stochastic gradients and sharing this information with the server, which then propagates it to other workers. Together, they aim to minimize smooth nonconvex objective function defined as
Server
min f(x). EERI
where f Rd + R and d is the dimension of f. We assume that d is huge, which is indeed the in modern machine learning and large language model training (Brown et al., 2020; Touvron et al., 2023).

---

Published as a conference paper at ICLR 2026
We consider the homogeneous (i.i..) setting, where all workers have access to stochastic gradients of the same underlying function f. As the reader will see, the homogeneous setting assumption is challenge, not limitation of our work: all results extend, potentially with even stronger implications, to the more general heterogeneous (non-i.i.d.) case, when each worker works with fi # f. We consider the standard assumptions:
Assumption 1.1. f is differentiable & L-smooth, i... [[f ff(ii)l = L || all. Vx,y E R*. Assumption 1.2. There exist f E IR such that f(x f for all E R We define A :=
f(a)) f",
f", where x is a starting point methods.
For all i E [nt, worker i calculates unbiased stochastic gradients V {) with o² -e-varince-bbuudee variances, where is a random variable with some distribution Dę-
Assumption 1.3 (Homogeneous setting). For all i E [u], worker can only calculate V.((;; {) and [e[V.f(x;E)] fz) and Eg [ellVV(( f(x) o² for all æ E Fd where o² 0.
The goal in the nonconvex world is to find an s-stationary point, (random) point T R such that f[][ < & (Nemirovskij & Yudin, 1983; Murty & Kabadi, 1985). We also consider a realistic computation and communication scenario:
Assumption 1.4. Each of the n workers requires at most seconds to compute a stochastic gradient, and communication from the server to any worker (s2w communication) takes at most seconds per coordinate, and communication from any worker to the server (w2s communication) takes at most Tw seconds per coordinate.
For instance, under Assumption 1.4, it takes d т, and d x Tw seconds to send a vector e E Rd from the server to any worker and from any worker to the server, respectively. We consider settings with bidirectional communication costs, where communication in both directions requires time. Typically, especially in the early stages of federated learning algorithm development, most works assume that communication from the server to the workers is free, i.e., Ts = O, which is arguably not true in practice: communication over the Internet 4G/5G networks can be costly in both directions (Huang et al., 2012; Narayanan et al., 2021).
1.1 RELATED WORK
1. Communication is free. Let temporarily assume that communication does not take time, i.e.,
T, = and Tu = 0. Then, in this scenario, the theoretically fastest strategy is to run the Synchronized SGD method, i.e., x++ =* - E (= {)',, where 7 O(min (mmin(//z, sntoa)) { are i.i.d., and (V+(<> are computed parallel by the workers, which send to the server that aggregates and calculates 2+1 One can show that the time complexity of this method is (h(( LA + afLA)) )). because requires O LA + eLLA) iterations (Lan, 2020), and each itcration takes at most h seconds due to Assumption 1.4. Moreover, this result is optimal and can not be improved (Arjevani et al., 2022; Tyurin & Richtárik, 2023b).
x
ng"
One obvious but important observation is that the second "statistical term" in the complexity bound scales with n. The larger the number workers n, the smaller the overall time complexity of Synchronized SGD, with a linear improvement in This is a theoretical justification for the importance of distributed optimization and the use of many workers.
Observation 1:
2. Worker-to-server communication
not be ignored. For now, consider the setup where communication from workers to the server takes Tw > 0 seconds, while communication from the server to the workers free, i.e., T3 0. In this scenario, the described version of Synchronized SGD has a suboptimal (h(( LA + "'I + Twd(( LA + =²LA) time complexity, because takes seconds to calculate a stochastic gradient and Twd seconds to send the stochastic gradients of size d
= ne"
to the server, which calculates =++1 However, if we slightly modify this method and consider Batch Synchronized SGD:
ktl
(Batch Synchronized SGD)
with b = ((0"/en) and 0(/L), then the time complexity becomes
O
(h
LA
IAA ns²
+ Twd L.
(2)
2

---

Published as a conference paper at ICLR 2026
because the number of iterations reduces to O (IA//). In other words, each worker, instead of immedi- ately sending a gradient, locally aggregates a batch of size b to reduce the number of communications. It turns that the last complexity can be improved further with the help of unbiased compressors.
Definition 1.5. A mapping C R4 x S IR with distribution D. is an unbiased compressor if there exists 2 0 such that I,, [C;; v)] and ExIlI((z;)) v) ==I²] S w || for all IR We U(w) denote the family of such compressors. The community uses the shorthand C(2; v) = C(x), which we also follow.
A standard example of an unbiased compressor is RandK E U('K 1), which selects K random coordinates of the input vector æ, scales them by d/K, and sets the remaining coordinates to zero (see Def. C.I). Numerous other examples of unbiased compressors have been explored in the literature (Beznosikov et al., 2020; Xu et al., 2021; Horváth et al., 2022; Szlendak et al., 2021). Using the construct modified version of QSGD (Alistarh et al., 2017)
seminal ideas (Seide et al., 2014), (special case of Shadowheart SGD from (Tyurin et al., 2024)), which we call Batch QSGD:
N+1
Σ 1=1
Cik
Σ Vf(a": (
(Batch QSGD)
vbbm
where worker sends m compressed vectors calculates = With RandK and proper parameters' (Tyurin et al., 2024), we can improve (2) to
to the server, which aggregates and
( (n(1+ LA + (2 1) LA
dr 2 LA
Observation 2: of workers n, which once again justifies the use of many workers in the optimization of (I). The "statistical term" ho² LA/n"" and the "communication term" rudLA/ne improve linearly with n, while the "coupling term" / /dr,ho"/ne of d and d for reasonably large n.
As in Observation I, unlike (2), the time complexity (3) scales with the number
improves with the square root of which reduce the effect
A high-level explanation for why the dependence on d improves with is that all workers use i.i.d. and unbiased compressors {Cac), which allow them to collaboratively explore more coordinates. This ff(x)]]]] o
effect is similar to Synchronized SGD. where the variance Eg | Ei= fz also improves with n. There are many other compressed methods that also improve with n, including DIANA (Mishchenko al., 2019), Accelerated DIANA (Li et al., 2020), MARINA (Gorbunov al., 2021), DASHA (Tyurin & Richtárik, 2023a), and FRECON (Zhao et al., 2021).
3. Both communications point of interest, where the communication time from the server to the workers is T. >> 0. In this case, Batch QSGD requires
not be ignored. Consider more practical scenario, and our main
(1
(1+
LA Tw
d
+
LA
LA
Ti LA
TE
n2
seconds because the server has to send x² E Rdd of size d to the workers in every iteration.
Observation 3: If T3 ~ Tw. then (4) asymptotically equals O (h (LA/++ o' + 7TdLA/e) reducing to (2), as in the method that does not compress at all! The "communication term" T/dLA/c does not improve with n.
We now arrive at our main research question:
In the first case (1. Communication is free) and the second case (2. Worker-to- server communication can not be ignored), possible design a method that scales the complexity with the number of workers n, while improving the dependencies on d and o² o²/e.
Can we design a similarly efficient method for the third case (3. Both communica- tions not be ignored) using unbiased compressors, where the communication
1b = ==)()) ) ) @ max { h, Tw:
ho2
dowhhr har
1) , e(2), ,x=(()) K = Rand/
3

---

Published as a conference paper at ICLR 2026
time from the server to the workers cannot be ignored, and where the dependence on both and o²/c improves with n, either linearly or with the square root of n? At least, can this be achieved in the simplest homogeneous setting, where all workers have access the same function, a scenario that arguably represents the simplest form of distributed optimization?
We know for certain that the answer is "No" in the heterogeneous case, due to the result of Grun- tkowska et al. (2024), who proved that the iteration complexity does not improve with the number of workers n under Assumptions 1.1 and 1.2. However, the homogeneous setting is "easier," " giving us hope that the workers can exploit the fact that they all have access the same distribution.
1.2 CONTRIBUTIONS
Lower bound. Surprisingly, the answer is "No" to our main research question, even in the homogeneous case. We prove the following theorem.
Theorem 1.6 (Informal Formulation of Theorems 4.2 and F.I). Let Assumptions 1.1, 1.2, 1.3, and 1.4 hold. It is infeasible to find an 8 8-stationary point faster than
LA + M }) (5)
② min
LA Tw Tw
+
LA
Ted
nC
seconds (up logarithmic factorrs, using unbiased compressors (Def. 1.5) based on random sparsifi- cation, for all L, E,,,,, Tw, Ts, h such that LA O(s) and dimension d 2 θ (LA/s).
Because of the min, the bound shows that it is possible to improve either the dependence on or the dependence on o²/s as the number of workers n increases, but not both simultane- ously. The lower bound is matched either by Batch QSGD or by the non-distributed SGD method (without any communication or cooperation). Moreover, if т₃ ~ Tw. the lower bound becomes which
á (min { {n
nt +1)+4 فA rTddA, * }).
be matched by Batch Synchro- nized SGD with the complexity (2) (without compression) by the non-distributed SGD method. In other words, T, = Tw, then using methods with random sparsification compression the distributed centralized setting offers no advantage. However, if Ts S Tw, the compression techniques can help on the workers side in the regimes when sud/n o ddr /nc is larger than rıd due the former scaling with n.
New "worst-case" function. To prove the lower bound, as we explain in Section 2.3, needed new "worst-case" function construction (see Section 3). We designed a new function Fr, in (9), which extends the ideas by Carmon et al. (2020). Proving its properties in Lemmas 3.1 and 3.2, as well as designing the function itself, can be an important contribution on its own.
Proof technique. Using the new function, develop new proof technique and explain how the problem of establishing the lower bound reduces to statistical problem (see Section 4), where we need to prove concentration bound for a special sum (13), which represents the minimal possible random time required to find an E stattionary point. Combining this result with the proven properties, we obtain our main result (11).
Improved analysis when >> 0. To obtain the complete lower bound, we extended and improved the result by Tyurin et al. (2024), which was limited for our scenario and required additional modifications to finally obtain (5) (see Sections F and 5 for details).
2 PRELIMINARIES
For better comprehension of our new idea, we now present arguably one of the most important worst-case functions by Carmon et al. (2020), which widely used to prove lower bounds in nonconvex optimization. It has been used by Arjevani et al. (2022; 2020a) to derive lower bounds in the stochastic setting, by Lu & De Sa (2021) in the decentralized setting, by Tyurin & Richtárik (2023b; 2024); Tyurin et al. (2024) in the asynchronous setting, by Huang et al. (2022) to show the lower iteration bound for unidirectional compressed methods, and by Li et al. (2021) in problems with emnconve-strrongyyccome structure.
4

---

Published as a conference paper at ICLR 2026
For any T N, Carmon et al. (2020) define Fr
RRT
R such that
T (r) = Σ 8; (1(--;1))((-3p)))
v (zii1))(xzi]]
(6)
where up 1, di is the 7th coordinate of x IRT""
00 v(x)) -(x)= exp (1 (1-1-1)))
x $ 1/2,
and ((x) ve / c- dt.
x 2 1/2,
12
Notice that this function has "chain-like" structure. If method starts from x = 0 and computes the gradient of Fr, then the gradient will have a non-zero value only in the first coordinate (use that (0) (0) 0). Thus, by computing single gradient, any "reasonable" method can "discover" at most one coordinate. At the same time, if the method wants to find an e-stationary point, it should eventually discover the 7 coordinate. These two facts imply that every "reason- able" method should compute the gradient of Fr at least T times. In the construction, Carmon al. (2020) take T θ (مA)) This construction a "more technical" version of the celebrated quadratic optimization construction from (Nesterov, 2018), which has similar properties. Let us define prog(z) == max i 2 0 24 # 0} (zo = 1), then the following lemma is formalization of the described properties.
Lemma 2.1 (Carmon et al. (2020)). The function Fo satisfies:
1. For all æ E R², Prog((Vr((t)) S prog (x) + 1.
2. For all x E RRT if (x: < T, then | (r(2))) > 1.
Actually, in most proofs, the structure of (6) is not needed, and it is sufficient to work with Lemmas 2.1 and Lemma 2.2 from below, where the latter allows us to show that a scaled version of Fr satisfies Assumptions 1.1 and 1.2.
Lemma 2.2 (Carmon et al. (2020)). The function Fr satisfies:
1. Fr(0) - infZeRT Pr(x)= < A where A := 12.
2. The function Fr is l l-smooth, where & = 152.
3. For all x E RR., (V)T(()) Too: where Yoo 23.
Hence, one of the main results by Carmon et al. (2020) to show that is infeasible to find an e-stationary point without calculating O LA gradients of a function satisfying Assumptions 1.1 and 1.2. In turn, the classical gradient descent (GD) method matches this lower bound.
2.1 FAMILY OF DISTRIBUTED METHODS
In our lower bound, we focus on the family of methods described by Protocol 1. This protocol takes an algorithm as input and runs the standard functions of the workers and the server: the workers compute stochastic gradients locally, send compressed information, the server aggregates them asynchronously and in parallel, and sends compressed information back based on the local information. For now, we ignore the communication times from the workers to the server Protocol
For all i E [n]. the algorithm can choose any point, based on the local information T;, at which worker will start computing a stochastic gradient. It can also choose any point s based on the server's local information I, along with the corresponding compressor Ch. which will be sent to worker i. This protocol captures the behavior of virtually any asynchronous optimization process with workers connected to a server. We work with respeeenpn algorithms, as defined below.
Definition 2.3. We say that an algorithm A that follows Protocol zero-respecting if it does not explore or assign non-zero values to any coordinate unless at least one of the available local vectors contains a non-zero value that coordinate. The family of such algorithms we denote A.r.
similarly Fr(x) (1)0((z)) + E. 1 (V(-I111)(( m1 T (x:)) because ((-1)
5

---

Published as a conference paper at ICLR 2026
Protocol
Input: Algorithm A E Ar
2: Init I = @ (all available information) on the server
3: Init
0 (all available information) on worker for all E [n]
4: Run the following three loops in parallel. The first two on the workers. The third on the server.
5: for -....., (in parallel on the workers) do
6: for == 0, .... do
Algorithm calculates a new point ir based on local information 4; (takes seconds) any vector Rd such that supp(z) supp,)) (supp(v) := i [d] v, # 0 Calculate one stochastic gradient f()(z)), E~ Dg (E are ii.d.) (takes h seconds) 9: Add Va E) to 4
7:
8:
(takes seconds)
10: end for
11: end for
12: for
= ,,.., n (in parallel on the workers) do for k = 0. 1, 1,... do
13:
14:
Algorithm A calculates any vector g/ IRd such that supp(s ( (yee,,upp(()
point क based local information T5:
(takes 0 seconds)
15:
Send C (5.) to the server
(takes Tw X Pk seconds, where P is the number of coordinates retained by C (stt)
16:
Add to C/ to
(takes 0 seconds)
end for
18:
end for for
= I,...,,, n (in parallel on the server) do for k = 0, 1... ... do
20:
21:
Algorithm A calculates a new point s based on local information
(takes seconds)
any vector s E [Rd such that supp(s{) E U>ersupp(y))
22:
Algorithm A compresses the point: Cf (sf+ Vi v
(takes seconds)
Send C (s.) (takes Ts X pk seconds, where PK is the number of coordinates retained by (+f)) Add to C, (s{) to Is
the worker i
24:
(takes 0 seconds)
25:
end for
26: end for
(a vector may be added to I or 13 at the same time as the algorithm calculates a new point; in this case, the protocol adds the vector first (with delay since the operation takes 0 seconds))
This is the standard assumption (Carmon et al., 2020) that generalizes the family methods working with the span of vectors (Nesterov, 2018) and holds for the majority of methods, including GD, Adam (Kingma & Ba, 2015), DORE (Liu et al., 2020), EF21-P (Gruntkowska et al., 2023), MARINA-P, and M3 (Gruntkowska et al., 2024).
2.2 PREVIOUS LOWER BOUND IN THE HETEROGENEOUS SETTING
Let us return back to our main question. order to show that it impossible to scale with n in the heterogeneous setting, Gruntkowska al. (2024) have proposed to use scaled versions of
(x(2) = ISiST and mod n=j-1
Σ
1 (21-1))
for all j E [no]. worker i has access only scaled version of G; for all i e [n]. The idea is that the first block from (6) belongs to the first worker, the second block to the second worker, ..., and the (n + 1hth block to the first worker again, and so on. Notice that Fr)x) En (.).).

---

Published as a conference paper at ICLR 2026
Notice one important property of this construction: only worker time discover the next coordinate. In other words, if the server sends a new iterate to all workers, only one worker, after computing the gradient, can make progress to the next coordinate.
The next step in (Gruntkowska et al., 2024), in the proof of the lower bound theorem, was to analyze Protocol 1. They consider' RandK with K = 1. Then, since the compressor sends only one coordinate with probability = 1/d, the probability that the server sends the last non-zero coordinate the worker responsible for the current block of (6) that can progress also p. Thus, the number of consecutive coordinates that the server has to send to the workers is at least Zj=1 Tij. where fi is a geometric-like random variable with P (1) = m m/ /71 S Using classical tools from statistical analysis, one can show that
the new coordinate is
p(1 p) m) for all m Σj di 2 T/p = dLA/e with high probability. Thus, under Assumption 1.4, the communication time complexity cannot be better than Ω (T,dLA/e), which does not improve with 72
2.3 FAILURE OF THE PREVIOUS CONSTRUCTION IN THE HOMMOGENEOUS SETTING
However, the homogeneous setting, we want to reuse the idea, arguably the only option we have is to assign (scaled) Fr to all workers to ensure that they all have the same function. But in this case, the arguments from Section 2.2 no longer apply, because all workers can simultaneously progress to the next coordinate, since they have access all blocks of (6).
Indeed, if the server sends i..dd RandK compressors with K = 1, then the number of consecutive coordinates that the server has to send before the workers receive the last non-zero coordinate is Σj=1 min Vij. where P (1}= = ml mng hees) S p(1 p)m for all m.j 2 1, E [n]. The min vE[n)
|E[m] operation appears because it is sufficient to wait for the first "luckiest" worker. Analyzing this sum, we can only show that
TB Σ min ThE j=1
2 Ts LA
(8)
E
with high probability, which scales with due to min.
There are two options: either 52(r, ((rr/)..//=)) is tight and it is possible to find method that matches it, or we need to find another way to improve the lower bound. To prove the latter, we arguably need a different fundamental construction from (6), which we propose in the next section.
A NEW "WORST-CASE" FUNCTION
In this section, give less technical description of our lower bound construction and the main theorem from Section D. Instead of (6), we propose to use another "worst-case" function. For any T, K E N, and 2 a 1, we define the function Fr,K,a K,a RT R such that
T (r. Σ
v Va(x; (a(z;kk) v
+ Σ r(x)):
(9)
(0,
* < 1/2,
((x)) = ve 1 2 dt,
Va (x) = exp (loga (1-12-117)
(10)
x >> 1/2,
x < 0 x 1 0,
[(x)
0,
'1) Multiple queries with the same random variable do not change the lower bound; see Remark E. in Section E; ii) In the heterogeneous setup (Section 2.2), worker computes Vfi(z; E), where fi is its local function.
'In general, they presented more general setting where the server can zero out coordinates with any probability, capturing not only Rand with K = 1 and p 1/4, but also Rand with K > and other compressors.
7

---

Published as a conference paper at ICLR 2026
11.5
1100
0.75
1.00
1.25
1.50
1.15
2.00
-20
-15
-10
-05
0.0
0.5
1.0
4/
F
W
</
Vi.00
1.00
3.25
0.5
Figure 1: The functions (x) and [(r), along with their derivatives V. (2) and (z).. The plots of (xx) and &' (x) are shown in (Carmon al., 2020).
and = _... - -- 1-
The main modification is that instead of the block - (xx (axx), 1 2
(ignore a now). the previous approach, was sufficient for worker to have 2,-1 0 to discover the next 7th coordinate. However, in our new construction, the worker needs z4-1 * O, 21-2 *
we use - V. (x( ... V (a(
* for that. With this sufficient for the "luckiest" worker get the non-zero 1 coordinate to
modification, it discover the next coordinate: to progress to the in coordinate, the worker should also have non-zero K + coordinates.
2th
Next, we remove the positive blocks (( which we believe was introduced to prevent the methods from ascending, exploring negative values of vi, and finding nearby stationary point "above." Instead, we introduce I(xx,), which serves the same purpose: a method starts exploring negative values, this term prevents from reaching a stationary point there. Let us define
prog K (z) := max 2 0| x; + 0, I #0}.
Instead of Lemma 2.1, prove the following lemma:
Lemma 3.1 (Lemmas D.4 and D.5). The function FT, K.a satisfies;
1. For all æ E RT, supp V (a(k)())) S ((.....,pro'" (x) + U supp(x),
where supp(e) = (i E [d] : #0).
2. For all x E RRT, if prog (a) < T, then (x))
The function Fr,K,a remains smooth. However, by multiplying with additional T terms, alter its geometry and make it more chaotic: the difference Fr.K.a infzer" Fr, (x), the smoothness constant, and the maximum -oom may increase. To mitigate this, introduce the parameter in (10) that allows us to control these properties. Notice that if a = e, then V Va(x) (xx)) for all R where V is defined in (7). Instead of Lemma 2.2, we prove
Lemma 3.2 (Lemmas D.6, D.7, and D.8). The function Fr,Ka satisfies:
1. Fr,k. znr (r, S AK, T, where A (K, 2 o
2. The function Fr,K.O is E1 (K, a) -mmoohhh where (i(K, a) = 2/1 K²
log
3. For all x E R.. (VFT 5o0 Too(K, a), where 7o0 (K, 2//e3/
Ka
Vlog a
Taking K = 1 and e, up constant factors, Lemmas 3.1 and 3.2 reduce to Lemmas 2.1 and 2.2. The larger the value of K, the larger the bounds in Lemma 3.2, and this growth can be exponential However, with proper choice of 1 < e, we can mitigate the increase caused by K.
8

---

Published as a conference paper at ICLR 2026
4 LOWER BOUND WITH SERVER-TO- WOROOR (S2W) COMMUNICATION
We now present informal and formal versions of our main result:
Theorem 4.1 (Informal Formulation of Theorem 4.2). Let Assumptions 1.1, 1.2, 1.3, and 1.4 hold. It infeasible to find an E-stationary point faster than
i (min
{
(Td
h LA
LA })
(11)
seconds (up to logarithmic factorr)) using unbiased compressors (Def. 1.5) based on random sparsifi- cation, for all L, A, E, n. 0² Ts,
such that LA z ①(E) and dimension d Z (TTA/)).
Theorem 4.2. Let I,, A. e, n, nn o² d, Tsy Tw, h > O be any numbers such that ei log" (n+1) < LA and dimension d 2 C3 (n+1e= Consider Protocol 1. For all i [n]] and k 0, compressor C selects and transmits P. uniformly random coordinates without replacement, scaled by any constants where Ph E {o,...,d} may vary across each compressor Then, for any algorithm A E Ar (Def. 2.3), there exists a function f IRd + R such that f is L-smooth, i.e., [V V < L || - yll for all v.y y RR. and [(0) infzeRs [xx) S A, exists stochastic gradient oracles that satisfies Assumption 1.3, and E yes. [ > E for all
LA
t 0
LA min
log[n+I) Tzd, max {ir (n
ha }]
(12)
(n+g(
where St is the set of all possible points that can be constructed by A up to time t based on I and (1a). The quantities C1, 022 and 03 are universal constants.
The formulation of Theorem 4.2 standard in the literature. However, following Tyurin & Richtárik (2023b). we present the lower bound in terms of time complexities rather than iteration complexities. Then, following Huang al. (2022): He et al. (2023): Tyurin et al. (2024), we consider a subfamily of unbiased compressors based from Definition 1.5 on random sparsification to prove the lower bound; this is standard practice for taking the "worst-case" compressors from the family (similarly to taking the "worst-case" functions (Carmon al., 2020; Nesterov, 2018)). Moreover, due to the uncertainty principle (Safaryan et al., 2022), all unbiased compressors exhibit variance and communication cost comparable those of the RandK sparsifier in the worst case (up constant factors).
The main observation in Theorems 4.1 and 4.2 is that it is not possible to scale both and ''/2 / by more than log 1 (n + 1) and log (n + 1), respectively. Asymptotically, this scaling is significantly worse than the linear and square-root / scalings discussed in Section 1.1. For instance, if n 10,000 and d is increased by factor of 10, we have to increase n by a factor of 10 (two factors more) to ensure that rad/log' (m+1) does not change.
In Section A, we present the intuition and the proof sketch of the result.
LOWER BOUND WITH BOTH W2S AND S2W COMMUNICATION
In the previous section, we provide the lower bound without taking into account the commu- nication cost Tw. Combining Theorem 4.2 with our new Theorem F.I, which extends the re- sult by Tyurin et al. (2024) for our setup, we can obtain the complete lower bound (5) from Theorem 1.6 with > 0 and > 0. Notice that if т, = Tw. then the lower bound is Up to logarithmic factors, under Assump- tions 1.1, 1.2, 1.3, and 1.4, is infeasible to improve both and 0²/2 as n increases.
á min { h g² + 11 LA + L h + =" })
5.1 ALGORITHMS ALMOST MATCHING THE LOWER BOUND
Due to the min, there are two regimes in which the lower bound (5) operates. If the second term is smaller in (5), then the lower bound is Ω KLA + ho? LA which is matched by the vanilla
"To potentially preserve unbiasedness. For instance. RandK scales by 4/K. 6 For instance, the compressors can be RandK (see Def. C.I) with any K E [d]. PermK (Szlendak et al., 2021), )), Identity compressor when p. d.

---

Published as a conference paper at ICLR 2026
SGD method run locally (without any communication cooperation). Otherwise, if the first term smaller, then the lower bound is matched by Batch QSGD, which has the matching complexity (4) (up logarithmic factors). Moreover, in the latter case, if T3 Tw. the lower bound becomes LA + = }}. which can be matched by Batch Synchronized SGD with the Ω min h o² + E
complexity (2); thus, T, , = Tw, then unbiased sparsified compression is not needed at all, as cannot help due to the lower bound.
CONCLUSION
We prove nearly tight lower bounds for centralized distributed optimization under the computation and communication Assumption 1.4. We show that even in the homogeneous scenario, it is not possible to scale both d and o by more than poly-logarithmic factors in n. Notice that the family of unbiased compressors contains the family of biased compressors (Beznosikov et al., 2020). Therefore, our lower bounds also apply to methods that use biased compressors, the sense that there exists a "worst-case" compressor for which these methods cannot achieve a convergence rate faster than the lower bound Theorem 1.6.
The lower bounds tight only up to logarithmic factors. Thus, possible challenging direction is to improve the powers of the logarithms, or even climinate the logarithms entirely. The latter (if at all possible) may be very challenging and would likely require entirely different constructions and techniques. Another limitation is that the lower bounds are constructed using random sparsifiers. Due to the uncertainty principle (Safaryan al., 2022), conjecture that the bounds also hold for the entire family of unbiased compressors, but proving this would require more sophisticated constructions.
In practice, however, biased and unbiased compressors. including TopK and Rank (Alistarh et al., 2018; Vogels et al., 2019), exhibit significantly better compression properties than those predicted by worst-case analysis (Beznosikov et al., 2020). When used on the server side in combination with EF or EF21-P (Gruntkowska et al., 2023; Tyurin al., 2024), they may help mitigate the pessimistic term T,dLAye. Moreover, our pessimistic lower bound may potentially be broken under additional assumptions such as convexity or second-order smoothness.
ACKNOWLEDGEMENTS
The work was supported by the grant for research centers in the field of Al provided by the Ministry of Economic Development the Russian Federation in accordance with the agreement 000000C11325PPFFOM and the agreement Nr139-00-2025-033.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances in Neural Information Process- ing Systems (NIPS). pp. 7709-1720 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems, 31, 2018.
Yossi Arjevani, Yair Carmon, John Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pp. 242-299. PMLR, 2020a.
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, 2020b.
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.
10

---

Published as a conference paper at ICLR 2026
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint 20Xv:2200..12410, 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Vosse Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Ben- jamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot leamers. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901, Curran Associates, Inc., 2020. URL https: http:s::pppcceedeeeeeee new.eeddinnn....ii............. 9 6 1174488fb8acc122550 Papaaa-appp..... pdf.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):11-100, 2020.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex SGD. arXiv preprint arXiv:9005 111199055001., 2019.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex op-
timization via stochastic path integrated differential estimator. In NeurlPS Information Processing Systems, 2018.
Margalit R. Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (Local SGD) and continuous perspective. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera The (cds.), Proceedings The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 90500909099 PMLR, 28-30 Mar html..
2022. URL https::t///o htt.tttsst/////oeeeeeeeeeeeeeeee http:///oocceddeeeeee
mlr, pre.s
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. In 38th International Conference on Machine Learning, 2021.
Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. EF21-P and friends: Improved theoret- ical communication complexity for distributed optimization with bidirectional compression. In International Conference on Machine Learning, pp. 11761-11807 PMLR, 2023.
Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. Improving the worst-case bidirectional communication complexity for nonconvex distributed optimization under function similarity. In Advances in Neural Information Processing Systems, 2024.
Yutong He. Xinmeng Huang, and Kun Yuan. Unbiased compression saves communication in distributed optimization: When and how much? Advances in Neural Information Processing Systems, 36:47991 --0020, 2023.
Samuel Horváth, Chen-Ye Yu Ho, Ludovít Horváth. Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, pp. 129-141. PMLR, 2022.
Junxian Huang, Feng Qian, Alexandre Gerber, Z Morley Mao, Subhabrata Sen, and Oliver Spatscheck. A close examination of performance and power characteristics of 4g Ite networks. In Proceedings of the 10th international conference on Mobile systems, applications. and services, pp. 225-238, 2012.
Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algo- rithms in distributed learning with communication compression. Advances in Neural Information Processing Systems, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Jakub Koneč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: arXiv:1610.05492 2016.
11

---

Published as a conference paper at ICLR 2026
Guanghui Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020.
Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex- strongly-concave min-max optimization. Advances in Neural Information Processing Systems, 34: 1792-1804, 2021.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, 2020.
Xiaorui Liu, Yao Li. Jiliang Tang, and Ming Yan. A double residual compression algorithm for efficient distributed learning. In International Conference on Artificial Intelligence and Statistics, pp. 133-143. PMLR, 2020.
Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In International Conference on Machine Learning, pp. 7111-7123. PMLR, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efficceen learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint 1rX.9:190,.09269, 2019.
Katta G Murty and Santosh N Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Technical report, 1985.
Arvind Narayanan, Xumiao Zhang, Ruiyang Zhu, Ahmad Hassan, Shuowei Jin, Xiao Zhu, Xiaoxuan Zhang, Denis Rybkin, Zhengxuan Yang, Zhuoqing Morley Mao, et al. A variegated look at 5g in the wild: performance, power, and qoe implications. Proceedings of the 2021 ACM SIGCOMM 2021 Conference, pp. 610 605, 2021.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. A method of solving a convex programming problem with convergence rate o (1/k**
2). Doklady Akademii Nauk SSSR, 269(3):543, 1983.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Kumar Kshitij Patel, Lingxiao Wang, Blake Woodworth, Brian Bullins, and Nati Srebro. Towards optimal communication complexity in distributed non-convex optimization. Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022. ISBN 9781713871088
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compres- sion in distributed and federated learning and the search for an optimal compressor. Information and Inference: Journal of the IMA, 11(2):55-588, 2022.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Rafat Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. In International Conference on Learning Representations, 2021.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 2023.
Alexander Tyurin and Peter Richtárik. DASHA:
Distributed nonconvex optimization with communi- cation compression, optimal oracle complexity, and no client synchronization. 11th International Conference Learning Representations (ICLR), 2023a.
12

---

Published as a conference paper at ICLR 2026
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, 2023b.
Alexander Tyurin and Peter Richtárik. On the optimal time complexities in decentralized stochastic asynchronous optimization. Advances in Neural Information Processing Systems, 37, 2024.
Alexander Tyurin, Marta Pozzi, Ivan Ilin, and Peter Richtárik. Shadowheart SGD: Distributed asynchronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity. Advances in Neural Information Processing Systems, 37, 2024.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGI: Practical low-rank gradient compression for distributed optimization. In Neural Information Processing Systems, 2019.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. local SGD better than minibatch SGD? In International Conference on Machine Learning, 10334-10343. PMLR, 2020.
Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. Advances in neural information processing systems, 29, 2016.
Blake 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.
Blake E Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Conference on Learning Theory, pp. 4386-4433 PMLR, 2021.
Hang Xu, Chen- Ho. Ahmed M Abdelmoniem. Aritra Dutta, El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, and Panos Kalnis. Grace: A compressed communication framework for distributed machine learning. In 2021 IEEE 41st International Conference Distributed Computing Systems (ICDCS), pp. 561-572. IEEE, 2021.
Haoyu Zhao, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. Faster rates for compressed federated learning with client-variance reduction, arXiv preprint 1rXiv:2112.13097, 2021.
13

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
1.1
Related work
1.2 Contributions
2
Preliminaries
2.1
Family of distributed methods
2.2 Previous Lower Bound in the Heterogeneous Setting
2.3 Failure of the previous construction in the homogeneous setting
New "Worst-Case" Function
4
Lower Bound with Server-to-Worker (S2W) Communication
5
Lower Bound with Both W2S and S2W Communication
5.1 Algorithms almost matching the lower bound
6
Conclusion
10
A Proof Sketch
15
Additional Related Work
16
C Auxiliary Facts and Notations
16
C.1 Notations
16
Lower Bound
16
D.I New Construction
16
D.2 Auxiliary Lemmas
17
D.3 Proof of lemmas
18
Proof of Theorem 4.2
21
E.1 Main Concentration Lemma
27
Main Theorem with Worker-to-Server Communication
31
F.I Main Concentration Lemma
34
14

---

Published as a conference paper at ICLR 2026
A PROOF SKETCH
We illustrate the main idea behind the proof and how the new "worst-case" function helps to almost eliminate the scaling with n. Consider the first K coordinates of Fr,K,a (which is scaled in the proof to satisfy Assumptions 1.1 and 1.2). Recall that, due to Lemma 3.1, the only way to discover the K + 1th coordinate in any worker is to ensure that all of the first K coordinates are non-zero.
Reduction to a statistical problem. There are only two options by which a worker may discover a new non-zero coordinate: through local stochastic computations or through communication from the server. In the first option, a worker computes a stochastic gradient, which takes h seconds. However, due the construction of stochastic gradients (Arjevani et al., 2022), even if the computation is completed, the worker will not make progress or discover a new non-zero coordinate, as it will be zeroed out with probability Po = @ (E-aa (K,)))))) In the second option, due to the condition of Theorem 4.2, a worker receives a stream of uniformly sampled coordinates VI, M2.... (workers get different streams), and the worker can discover a new non-zero coordinate only random variable 1/2 E [K], which satisfies P (v, E [K] 1/-1) S K/r-i+1 S Рк == =2K/r for all i S 7/2.
Next, we define two sets of random variables: (i) let 17.,s,k denote the number of stochastic gradient computations until the first moment when a coordinate is not zeroed out in the stochastic gradient oracle (see (26)), after the moment when the (A: 1 coordinate is no longer zeroed out in worker i; (ii) let M1,ik be the number of received coordinates until the moment when the last received coordinate belongs to [K], after the (k= - 1)th time this has happened. In other words, ,1,,,1 is the number stochastic gradient computations until the moment when the algorithm receives "lucky" stochastic gradient where the last coordinate is not zeroed out. The random variable M1,12 is the number of computations until it happens for the second time, and so on. Similarly, f1,111 is the position of the first coordinate from the stream sent by the server to worker i that belongs to [K]. The random variable 11,i,2 refers to the second time this occurs, and so on. By definition, the sequences ( and { follow approximately geometric-like distributions with parameters pa and pk, respectively.
To discover all of the first K coordinates, either the first the second process must uncover least K/2 coordinates. If worker i has discovered fewer than K/2 coordinates through stochastic gradient computations, and fewer than K/2 coordinates through receiving them from the server, then it will not be able to cover all K coordinates. Thus, the algorithm should wait at least mingg]s] min h E > M,,AA T. (11,1 seconds until the moment when it can potentially discover the K + 1hhh coordinate, where the outer minimum minte[n] appears because it is sufficient for the algorithm to wait for the first "luckiest" worker. Repeating the same arguments B == LT/K times, the algorithms requires at least
B
K/2 h
K/2
tB = Σ min
min
Σ 7o
Σ
pb.sk
(13)
seconds to discover the T coordinate and potentially find an e-stationary point, where the sequences ( and (Mo,..} follow approximately geometric-like distributions with Pa and pk, respectively.
Analysis of the concentration. Hence, we have reduced the lower bound to the analysis of the
sum f.. Recall (8), where the lower bound improves with n due minke]n]- . In (13), we also get min However, and this is the main reason for the new construction, there are two sums ExE, which allows us to mitigate the influence of the min.e In particular, we can show that tB 2 w7/k instead of n due to the sums; thus, the larger K, the smaller the influence of n.
BK min (2/no; 3/px) with high probability. Notice that the first fraction improves with n *
Putting it all together. However, we cannot take K too large due to Lemma 3.2. Substituting the choice of T, T,po, and Pk (defined in the proof of Theorem 4.2 to ensure that Assumptions 1.1, 1.2, and 1.3 are satisfied and the scaled version of Fr, K,a has the squared norm larger than while the 7 is not discovered), we can show that
LA LB Z R A Ka)) min max (h. (K,))
ho?
Id
with high probability, where A A a), e, (K, a). and You (K, a) are defined in Lemma 3.2. The final step is to choose K e (log n) and a = 1 + 1/x obtain the result of Theorem 4.2.
15

---

Published as a conference paper at ICLR 2026
B ADDITIONAL RELATED WORK
While we focus on lower bounds in the context of stochastic optimization and compressed vectors in nonconvex settings, there is much related work in other domains and setups. The seminal works on lower bounds were done by Nemirovskij & Yudin (1983); Nesterov (2018), where Nesteroy (2018) showed that the accelerated gradient descent (Nesterov, 1983) is optimal in the convex setting using a quadratic "worst-case" function. In the nonconvex setting, Carmon et al. (2020) provided an alternative function, described in the main part of the paper. For convex problems, Woodworth et al. (2018) introduced the graph oracle, generalization of the classical gradient oracle (Nemirovskij & Yudin, 1983; Nesterov, 2018), and established lower bounds for broad class of parallel optimization methods. Arjevani et al. (2020b) further analyzed the delayed gradient descent method, which corresponds to Asynchronous SGD with constant iteration delays. Tyurin & Richtárik (2023b; 2024); Tyurin al. (2024) proved lower bounds for methods in asynchronous settings. Fang et al. (2018); Patel et al. (2022) studied a different setting from Assumption 1.3, where they assumed the mean- mean--sqaared smoothness property to enable the analysis of methods with variance reduction techniques (Fang et al., 2018; Cutkosky & Orabona, 2019). Woodworth & Srebro (2016) considered the finite-sum setting in the convex setting. Woodworth et al. (2020; 2021) proved that the min- max optimal algorithm for optimizing smooth convex objectives in the intermittent communication setting is the best of accelerated local and minibatch SGD, which leads to a similar conclusion to ours; however, their results are related to, but not directly comparable with ours, since we analyze the limited scalability of improving both stochastic noise and communication complexity through compressors. Glasgow et al. (2022) provided sharp lower bounds for local SGD approaches in terms of iteration complexity. Huang et al. (2022); He et al. (2023); Gruntkowska et al. (2024) provided lower bounds for compression techniques, but in the heterogeneous setting.
C AUXILIARY FACTS AND NOTATIONS
Definition C.1 (RandK). Assume that S is random subset of [d] such that |S] = K for some K [d]. A stochastic mapping C : Id x S + Rd is called Rand if
C(x; S) = K
Σ Ejej
jES
where {= denotes the standard unit basis. The set S can be produced with uniform sampling of [d] without replacement.
C.I NOTATIONS
N = (1, }; ||^|| the output of the standard Euclidean norm for all x E Rd: (x, y)
Σd - IiHi is the standard dot product; ||A]| is the standard spectral/operator norm for all A E
Rdxd, g = =O() exiist C > O such that g(z) < C x f22 for all = E 2; = 2(ʃ) exist
C > 0 such that g(2) 2 C x f(z) for all z 2: = 0(f) : :g O(f) and g A(f))
g = Ō().g ()f) = Ō(f) : the same as g =
0(f), respectively, but up to logarithmic factors; g ~ h g and h are equal up universal positive constants; g h g greater or equal to up to universal positive constants; C is an unbiased compressor (Definition 1.5); supp(u)
[d] v + 0); h maximum time (in seconds) for any worker to compute one stochastic gradient; 7. : communication time per coordinate from the server to any worker; Tw : communication time per coordinate from any worker to the server;
D LOWER BOUND
D.1 NEW CONSTRUCTION
For any T, K E N, and e 2 a > we define the function Fr,Ka T - R such that
T
T
Fr,K,ax)) =
Σ
L Va (x;
1 W.. (x.)) + Σ r(x.)
(14)
16

---

Published as a conference paper at ICLR 2026
where n, is the hth coordinate of vector z E R² and
0,
x 1/12
((x) vt I cr dt
(x())
exp (loga: (1- (2=-11²))
x > 1/2.
and
-ree /m+1 < 0, x 2
[2x)
00
We assume that assume that e 2 a > 1, even if this assumption is not explicitly stated in all theorems.
--K++ = Importantly, throughout the lower bound analysis, we
We additionally define
C,,,,,,,.KK... prog (x) = max 2 0| x; + 0, 0, #0, ...... T--K+1 # 0}
(zo I-K+1 = 1),
which extends prog(r) = prog't (x) == max 2 0 24 # 0} (zo 1).
D.2 AUXILIARY LEMMAS
In this section, we list useful properties of the functions 4 r, Va and Fr,K.a. We prove them in Section D.3.
Lemma D.1 (Carmon et al. (2020)). Function & is twice differentiable and satisfies
0 < (xx) & V2ee, 0 (x) S Ve. and [0"(x) < 27
for all x E R. Moreover, ('(x) for all -1 <r<l.
Lemma D.2. Function I' is twice differentiable and satisfies
0 S [(x), for all x E R. Moreover, ('))) S 2 for all x S -1.
[' s 0, and 0 S (x) s 27c
Lemma D.3. Function V is twice differentiable and satisfies
2e
56e
0 (x(
0 0 (x))) <
and [=(x)]
Vloga
log a
for all x E R and < S e. Moreover, (a(x)= 2 for all x 2 and < a S e.
Lemma D.4. For all RT. (upp(VVFr,,,a(t)) (1,...,,prop (x) 1} U supp(ar), where supp(u) = (i [d] # 0).
Lemma D.5. For all x E RTT prog (a) < T, then || [V >1
Lemma D.6. Function Fr,K.o satisfies
Fr. inf Fz) (K) .T FeRr
where AK a) == V2TE Kk
Lemma D.7. For all a E RT, [VFr S 7oo(K, a), where (K, = 3/2 KoK
Vloga'
Lemma D.8. The function Fr,K,a (K(K, a) smoothhh ie,, ([ S (((K,a) for all
RTT where E (i(K a) 22 k²,
log
17

---

Published as a conference paper at ICLR 2026
D.3 PROOF OF LEMMAS
Lemma D.2. Function I' is twice differentiable and satisfies
[e< - 0, and 0 (x) s 27e 0 T(x),
for all x E R. Moreover, (x) - all x - -1.
Proof. The first fact is due to lim r(A) 0, (0) = 0, and lim A-0
[(A) A
0. is clearly non-
A-+
negative, Next, for all æ S 0,
el/z+1
('(x) ee//011 +
and
e2/0+1
(+) =
x,3
Thus, IY is strongly increasing for all x S 0, and lim 2-0000
[' = - (x) < O. Next, (²xx) 2
(xx))
for all x S 0, and max T (x:) 27e for all 0.
z50
Lemma D.3. Function Va is twice differentiable and satisfies
2e
56e
5 (x(x)
0 < V' - Vloga
and (V <
log a
for all x E R and
< a v e. Moreover, (x( 2 1 for all 2 and < S c.
Ma(++A) for all >> 1. For all x S 2 A
Proof. The differentiability at æ = follows from lim V (x) 0. For all
A-40
3. we get
0 S V V'(())
4 llg
exp loga
(1- (2x - 1)2
(2r - 1)3
4a
log"/2
3/2
log
exp
Vloga
(2x 1)3
(2x 1)
Taking t 1/3 (2a-1)
> 0 and using
ete
2/2 we get
4a
2e Vlog a
v.(x)
v
log a
since I C.
Clearly, 4 (x) 2 0 for all x E R, and v is non-decreasing. Moreover is strongly monotonic for 2. Thus (x( < lim V (x) = a for all x E RR.
all x 1
200
The twice differentiability at \ follows from lim +((++A) 0 for all a > 1. For all æ S 2 (x)) = 0. For all
1,1 taking the second derivative and using simple algebra, we get
8 log a x (3(2x 1)² 2 loga)
exp loga (1- (2x -
(x)
(2x 1)6
(112 1)2
Sa log a x (3(2x- 1)2 2 2loga)
log a
(2r -166
exp
(2x -1)2
24a log
exp (- log
16a log²
2
log
(2x 1)a
(-
(2xx - 1)3
+
(2r
1)6
exp
(2x - 1)2
24a
x log² a
log a
16a
log a
log a (2x 1)
exp
+
x
exp
log
(2x 1)4
(2x
1)²
log a
(2x - 1)6
18

---

Published as a conference paper at ICLR 2026
Taking
log (2x 1)2
and using the Σ 1 and t =
24a
16a
56c
[V(()) S
x 2 v
log a
log a
log a
since S
Lemma D.4. For all x E R², supp V VFT,K,(()) S
(x) + 1} U supp(æ), where
supp(u) = { E [d] : n #0}.
Proof. Let j prog K (x) and p prog' (z), then
3+1
Fr,) =
v (x) ... V Σ
Σ
L Va(x:- (
i=
T
+
T(x.)
+
Σ r(æ.). i=p+1
i=1
Since = prog (z), for all 2 2, least one of the values Zt-K 24-2, is zero. Noting that vr (0) = V (0) 0. the gradient of the second sum is zero. The first sum depends only on the first j coordinates; thus, the gradient of the first sum non-zero in at most the (j + 1)th coordinate.
Since p prog (ar), the gradient of the last sum is zero because (* 0. Moreover, x; 0, then 1'(x;) = 0; thus, V (2 I(xx)) E supp(x).
Lemma D.5. For all RT, if prog (a) T, then [VFT, (x)) 1.
Proof. For all j E [T], the partial derivative of Fr, with respect to zj is
OFr,K.a (x) = Va (a(zz-k) (a(x)-1)0((x))
dx,
(z (+1)
(15)
(2,) (mx)) (1)+1) ... Va (1
+ (xrg))
We now take the smallest j E [T] for which zy and rj-1 2 1, ..... 35-K 2
If such does not exists, then 2 due to = ... z-K+1 = 1. Then 22 2 1, and so on. Meaning that Ty 1 for all j E [T]. which contradicts the assumption of the theorem that prog (x) <
Fixing such j. consider (15). There are two cases.
Case 1: x, > Note that V, T, V कO z 0 are non-negative and I" is non-positive. Thus
OFr.K. (x) S va(x)-K) ... V
dr,
Since 2ÿ-1 2 1,...,; and
xj -1 (see Lemmas D.1 and D.3), we get
öF (x) -1.
Ox,
Case 2: I, Note that V Tb, V T > 0 non-negaeive. Thus
OFr K.a (x) < (x,)) dx;
19

---

Published as a conference paper at ICLR 2026
Since 2y - -1 (see Lemma D.2), get
i Fr. Fzz
K.a
(x) < -1.
Finally, we can conclude that
aFr.K.a (x)) Oiy
[V), 2
> 1.
Lemma D.6. Function Fr,K., satisfies
(r),
inf FI, (r),,( (K) WERT
where (K, == v 2Tm k
0,000.000000 Proof. Since r(0) = 0 and Va, + 2 O, we get Fr,K,a < 0. Next, due to [(x) 2,00 2 ((x) s
V2Te and 0 - (x S a for all x E Rd.
T
(x) 2
Σ
- ( -TV2Te a
for all x E IR
Lemma D.7. For all x E RT, [VFr I %oo(K, a), where (s0(K, = 6v 2
K
Vloga'
Proof. Using (15),
Faa (x)
$ Va(0)-k). Va(()))))
dx,
+ Va (()z))K11)-- ... ........ (d)
+...
+
T. (2(2min(j-K (. ) (2 (Imin(j- + (zz))
(16)
Thus,
TF..Ka (x) On, due to Lemmas D.1, D.2, and D.3.
& a Ve Ka K-1 V2T 2e
Kat
+ 6v 2m3
(17)
Vlog
Vlog a
Lemma D.8. The function Fr,K,, is l (i -mmooohhh i.e., |[ S (i(K,a) a) for all E RT, where L (i(K, a) 2 K²a
log
Proof.
Taking the second partial derivative in (15),
82 FT... (2:) = [[ Va(az [-VValir- k)... V.(xz-1))
On7
(a(zy-K+1). ... V.l
(18)
(" MI (1
(2min + (xz))
Due to Lemmas D.I, D.2, and D.3,
8 Fr,Ka
56 56 3/2
Ka
(x) < k + K x
+ 27e -2 1688 3
(19)
0x3
log
log
20

---

Published as a conference paper at ICLR 2026
Clearly, for all min + <isT, 0 Fr,r,
(x)
(20)
Ōr,ōr;
due to the construction of Kr.K.a Next, for all j < S min + K,T),
0º PT. (z) = - (e 0r,0z;
2. (a (2;)
.. (a ( ((
and
8 FT K. (1)) S Vloga a
2
4
Kak
+ (K- 1) x
S 2/2
(21)
dx. 0x,0n;
log a
log a
for all + j E [T] due Lemmas D.1 and D.3 and 2 2>>
Notice that Fr. is (2K + -iadogal Hessian. Repeating a textbook analysis for completeness and denoting temporary H = V2 F2 we will show that
0 FT. (x) Ür,0zz
V Fr. s (2K +1)
max WJE(T]
(22)
for all x E RR. Indeed, for all x E R such that ||>|| 1
T
(it K,T)
min min (,+K
T H
=
Σ
x
Hig
Σ
T2
Σ
Iz H.H
S max Hayl (JE(
Σ
|008
j=max K11
=maxxfi-K.1
where the second equality due H is (2K diagonnl. Using the Cauchy-Schwarde inequality.
T
T
min K.T)
miufi+
1x T Ha & max Hol
Σ
bayl
S
max H JJEM
Σ
|0yg
t=1
ji
K.I)
j=max K.I}
since || < 1. Next, using Jensen's 's inequality and |0|||
< 1,
T min(i+K,T)
T (2K + 1)3
x H
max [.j
Hiyl
(2K
+ 1)
Σ
R3 max [JE!
Hyl
max
K.1)
1=1
< (2K + 1) max
HHl-
(JE(T]
We have proved (22). It is left to combine (22), (21), and (19).
E PROOF OF THROREM 4.2
Theorem 4.2. Let A, E, 0² Ts, 0 be any numbers such that E₁E log((n+1) < LA and dimension d > C3 log"(=+ Consider Protocol 1. For all i [n] and O, compressor C%² selects and transmits Ph uniformly random coordinates without replacement, scaled by any constants?, where may vary across each compressor Then, for any algorithm A E An (Def. 2.3).
I.A
plc E [.....,d) dd
"To potentially preserve unbiasedness. For instance, RandK scales by 4/K.
$ Forr instance, the compressors can be RandK (see Def. C.I) with any K E [d]. Permy (Szlendak et al., 2021), )) Identity compressor when p. d.
21

---

Published as a conference paper at ICLR 2026
there exists a function f I + R such that f is L-smooth, i.e., [V(()
= yl
for all z, E IR and f(0) in f(z)= I A, exists a stochastic gradient oracles that satisfies
Assumption 1.3, and infyes, [[V]())])@] E for all
x
LA min
log[n+1) Tydd max {1i, log" (n)
(12)
(n+1()+
where St is the set of all possible points that can be constructed by A up to time t based on I and {Ia). The quantities é1, C22 and 03 universal constants.
Proof. (Step 1: Construction). Using the construction from Section D.I, we define a scaled version of it. Let us take any À 0, d, T N, T, and take the function f TR R such that
LA²
f(x) :- ((K, PT, K,a
(
where E (K, a) is defined in Lemma D.8 and 2|r E IR" is the vector with the first I' coordinates of E Rd. Notice that the last d - T coordinates are artificial.
First, we have show that / s-ssooth and f(0) znRZ ((x) S A, Using Lemma D.8,
VV(() - vf(wi) = (i(K,a) a)
LA
VFT,Ka
VTT.K.
- LA
LA |
Mr
L |
B(T)]
$ L -| yll
Vz. E Rd.
Let us take
A- (,,) LX2 A a
T
Due to Lemma D.6,
LX² f(0) inf f(z) (K,,a) a) zER
LX2 SA.
(Fr,K,a (0)
inf Fr,K,o(z)) #ER"
(i(K,a)
where A"(K a) is defined in Lemma D.6. We also choose
(K,
(23)
L
ensure that
x,2x2 VFr,K,o
(=)))===
l²
[Vf(=)] = (?(K,a)
25
VFr,K.a
2e |prog K (IIT) T
X
(24)
where the last inequality due Lemma D.5. Note that
LA
T=
(25)
(Step 2: Stochastic Oracle).
We take the stochastic oracle construction form (Arjevani et al., 2022). For all j E [d].
1 + [j prog K (z) + 1| ( $ -1)
f O) == fzf())
Vr E Rd.
(26)
and De = Bernouilli(p)), where Po E (0, 1]. We denote [xl, as the 7th index of vector x E Rd. left to show this mapping is unbiased and x² vvrriaacce-bounded Indeed,
1 + prog K ((x) +
E [El
-1)) v.f(x)
E [ (ar ON = (.)(x)
Po
for all E [d], and
E (
- v(()))]
< max jeld
2
-11
Pr
22

---

Published as a conference paper at ICLR 2026
because the difference is non-zero only in coordinate. Thus
L2X² Fr,K.o ( (<x1)l(> (1 Po)
- V 1 [V[(x)] (1 -pa)
E
Po
((K,a))
I 1 700 (K, (1 Po)
((K,a))
where we use Lemma D.7 in the last inequality. Taking
(2) min
128 (K,a)
Pr = min
(27)
ensure that E ( vf(=))] 0
(Step 3: Reduction to the Analysis of Concentration). At the beginning, due to Definition 2.3, of for all E [n]. Thus, if k 0, all workers can receive zero vectors from the server. Thus, the beginning, all workers can only calculate stochastic gradients at the point zero.
Let (1 denote the earliest time which all of the first K coordinates become non-zero in the local information available to worker i. In other words, t is the first time when worker has discovered all of the first K coordinates. Consequently, prior time
t min 11,
(28)
iE(n)
neither the server any worker is able discover (filled with non-zero values) the (K + 1)th and subsequent coordinates due to Lemma D.4.
There two options by which a worker may discover non-zero coordinate: through local stochastic computations or through communication from the server.
Option 1: In the first option, a worker computes a stochastic gradient, which takes h sec- onds. However, due to the construction stochastic gradients, even if the computation is completed, the worker will not make progress or discover new non-zero coordinate, as it will be zeroed out with probability Pa- Due to Lemma D.4, each worker can discover at most one coordinate at position prog* (z) + before time i in the first K coordinates, where x is query point.
Remark E.I. For this reason, making multiple queries with the same random variable instead of single query does not help the algorithm progress: if the coordinates are zeroed out, then they are zeroed out in vectors.
Let 7 be the number of stochastic gradients computations" until the first moment when a co- ordinate is not zeroed out in (26) in worker Assume that Ei, f2,..... a stream of i.i.d. random Bernuuli variables from (26) in worker i (all workers have different streams), then
[e|
PP (m S1) S
Σ P 1, 0, 4 k=1
po (al1-pa)- pa) S tpo. Epo(1
for all 2 0. Similarly, let 71,.. denote the number of stochastic gradient computations until the first moment when coordinate is not zeroed out in (26), after the moment when the (k- (6-1] 1)th coordinate is no longer zeroed out in worker i. other words, worker should calculate V),,, stochastic gradients discover the first coordinate, calculate M1,, stochastic gradients to discover the second coordinate, and so on. Since the draws of & in (26) are i..dd, we can conclude that
IP (M... S tlm.ak-1...... M.,..1 S tp.
for all & 2 1 and O.
Option 2: In the second option, worker receives P {O....,d) d} random coordinates with the set of indices (V1,1.-.., V1,p} without replacement, where it takes т, seconds to receive one
It is possible that P (m...1 = oc) > 0 if, for instance, the algorithm decides to stop calculating stochastic gradients. And even P (M..11 oc) = 1 does not calculate at all.
23

---

Published as a conference paper at ICLR 2026
coordinate. Then, the worker receives P E {O...., d) random coordinates with the set of indices (12.1.....,44 P2 without replacement, and so on (all workers get different sets; we drop the indices of the workers in the notations).
Consequently, the worker receives a stream of coordinate indices (V1, V/2,...) where we concatenated the sets of indices, preserving the exact order in which the server sampled them. Note that all workers have different streams, and we now focus on one worker.
Notice that
K
IP ( E [K])
d
since ii is uniformly random coordinate from the set [d]. Next,
K
PP (u2 [K]
d
K because either i1 E [K]. in which case the probability is d-
or vn & [K], in which case the
probability 2-1
K Using the same reasoning.
K
P (Mv E [K] [
11-1) S d d-i+1
for all d.
Hence, the worker receives a stream of coordinates v1, U2,... such that IP (Mt E [K]]u)....;..11) S d-r+1 for all S d. Let fı,,i11 be the number of received coordinates until the moment when the last received coordinate belongs to [K] in worker i. Similarly, let fI,úA be the number of received coordinates until the moment when the last received coordinate belongs to [K], after the (A: 1 time this has happened in worker i. In other words, worker should receive 11,,11 coordinates to obtain a coordinate that belongs to [K]. To get the next coordinate that belongs to [K], the worker should receive 21, coordinates, and so on. Then,
P (M11111 j) P (Mg [K], P/-1 & [K] V1 [K])
K
P (yg E [K] & [K]. & [K] P (P)-1 & [K].... 11 $ K]) S
d d +1
for 1 isiS S d, and
1d
Kt
P ( St) Σ
P (M1.11 = = d-
(29)
for 0 S 1 S Similarly,
IP (1I,i, 11.
(uuts E [K] Mutj-1 @ [K].... , & [R]|,, E [K], E [K])
K
max(d u, 0) - 1
where u -i=1 Mini, for all j maxfd u, 0}. Thus,
Kt.
P (pLLA S S1/
max - Ex= 01
for all 0 StS max(d
Σド= (1. 0}.
Recall that the workers can discover new non-zero coordinates only through the stochastic processes discussed above. To discover all of the first K coordinates, either the first or the second process must uncover least 2 c0ordinates If worker é has discovered fewer than K coordinates through 2
At the end of the proof, we take K mod 2 0.
24

---

Published as a conference paper at ICLR 2026
stochastic gradient computations and fewer than K the server, then it will not be able to cover all K coordinates. Hence,
2 coordinates through receiving coordinates from
t min
min
M1,5.
(30)
where & is defined in (28). This is because
>> Miik is the time required to obtain "lucky" 2
stochastic gradients, those for which the coordinates are not zeroed out, and Σ Mi,i is the time required to receive K "lucky" coordinates that belong [K] 2
Remark E.2. The previous derivations hold for all Tw 0. If we start taking the communication time Tw into account, then the bound on ti in (30) may only increase. For all Tw > O, worker still has to discover non-zero coordinates either through stochastic gradient computations by receiving coordinates from the server and it will take at least
min se(n
min
n Ts
M1,i,
A=1
Am
seconds to discover all of the first K coordinates.
Once the workers have discovered the first K coordinates, the discovery process repeats for the set {K + (4...,2K,, which similarly requires least
min ve(n
min
h
T2
Ts
M2,i,
Rim
seconds, where ( and (m are random variables such that
PP (Mb.,, S tlmb,i.--1. Th.1,1 96- I tp
(31)
for all b 2 1, 2 1, [n], 0, and
Kt
PP (pb,LK S tl 1b.1.1, Go-1)
(32)
max Σ/= Mb.i,f 0} t +
for all b 2 1,k 1, [n], and & max(d - Mb.i., 0}, where G6-1 is the sigma-algebra generated by (Tb (e) cb and (u (e and u E}= Mb,i.
More formally, 72,i, be defined the number of stochastic gradient computations until the first
moment when coordinate is not zeroed out in (26), after the moment when the (I: 1) coordinate no longer zeroed out, when prog* of the input points to the stochastic gradients is 2 K, and P2.i. be the number of received coordinates until the moment when the last received coordinate belongs to {K + 1,..., 2K) J. after the (k thth time this has happened, when prog* of the input points to the compressor is > K 1, and on.
We define
2K
PK d
(33)
Finally, to discover the th coordinates it takes at least
B
Σ
min
min
7. Ts
Pb.sk
A=1
seconds, where B = [ it left to use the following lemma.
25

---

Published as a conference paper at ICLR 2026
Lemma E.3. Let (Mo.is 1,5000 and (1o,s, H.5.b20 be random variables such that
TP (Mb,i, I 11 1b,,,, 96-1) 7b,1,199-111
S tpo
(34)
for all b 2 1 2 1, i [n],t 0, and ( S t/pb,.k-1...... Mb,1,1 90-1)
Kt
(35)
max -E Mb,i.j. 0} +1
for all bulbbie 1,1,,,, [n]. 0 0 max(d EE= Mb,a, 0}, and S K & d, where -0- is the Then
sigma-algebra generated by {nv kel 11 and {pv i,
P
min REin]
min
h
ts Ts
Mb,i.
si 5 {]
hml
Joml
with
BK + log d
h Ts PK
1:
min
(36)
(2n)22/K(4 1og(2n))
Pa
where
2K
PK d
(Step 4: Endgame). Thus, with probability at least 1 - 5, any zero-respecting algorithm requires at least & seconds discover the 7hh coordinate. Since prog K (x) s prog (x) for all IR"" and due to (24),
inf [V 25 inf [prog' (wrzn) < T], yES.
WES.
where S; is the set of all possible candidate points to be an s-stationary point up to time which can be computed by A. Taking 8 = 2
E
inf DES.
[((()) 2=E
inf 1 [prog' (ym)) T] EE yes.
for 1 because prog* (ym) T for all y E St with probability least 3-
is left choose K and a, and substitute all quantities to f. Using B
F K log
h
==
min
(2n) 2/K (4 + K log(2n))
Po
PK
T K log 8
h Ts
e (2m) 2/k (4 x (2n)
min
-
Po
PK
Due to (25), (27), and (33),
LA (KK ((22)2/K (oog(2n)
K -og 8
ho?
T,d
min max
h, 2072 (K,a)
'22
Using the definitions of 1 A9 Yo0(K,,) a), and e aK)
e (2n))2/K
[+ K log(2n)
LA LA
K log min max h
ho² log a
Tyd
48Te'3 K2a2k
144me3 K K2
2K
We can take any a from the interval (1, c]. We choose a = 1 + * then loga = log (1 + R
> 2K
for all K 2 2k < e² for all K 2 1, and
2 72 (2(2)))/K (4+ K 1og(2n)))
(L
LA
ho²
Ted
K --log min max h
96meb
288 K3g
''2
26

---

Published as a conference paper at ICLR 2026
Taking K = (2 (2n)] (2m)2/K
Se, K & 16 + 1) and
LA
32 log(n + 11) min max { h, 288. 8 log (n + 1)
ha²
Ted
i
5e
96 m log (n + 1)e
32 log (2 +1)
LA
ho?
T,d
36log(n + +1) min max h, 288 me log" (n + 1)e
5e
96 84 meb log (n + 1)
32 log 1)
We assume
LA 2 é log' (n + 1) for universal constant č1. Taking é large enough, one can see
that
LA
ho²
T,d 32 log
min max h. 288 8* log (n + 1)E f
5e
2 96 8 log (n + 1)E
1)
For small enough universal C22 we get the inequality
LA
ha?
Tsd
2 02 x
min
max
h, log (n + 1)
log 1)
log(n +
which finishes the proof. Notice that we can take
LA loga
LA log (n + 1)E
d d2T=
48Te K²a2k
E.I MAIN CONCENTRATION LEMMA
Lemma E.3. Let (T and (Pons be random variables such that
IP (No, I t Tb.i,,, 1b. 90-1) S tpo
(34)
for all b 2 k, 2 1, i [n],t 2 0, and
Kt
P (ub,ii S tlpb,ik-11- 1,.............................. 18, Go-1)
(35)
max (d Σ}= j=1 Mb,s, 0}
for all b2 1, 1,iE [n], 0 < S max Σラ=1 Mh.i.g. 0}, and 1 < K S d, where G6-1 is the Then
sigma-algebra generated by {nw 3, (eee) $1.0<b and (.W,i,k
PP
min RE mn)
min
7o Ts
Mobii 1]
SE 5
with
BK + log 8
Ts PK
[ 1==
min
(36)
+ log(2n))
Po
where
pk = 2K
Proof. Let us temporarily define Bo = min nn Σ x method, we get
== Abiik
Using Chernoff's
B
B
IP
min /Eim
So, <t
=P P
exp
A min S0,t iE(n]
2 exp (-
1=1
1=1
exp (At)
E
exp
Σ
X min Bort iE
(37)
b=1
B-1
cAxp E
E
cxp
- min sE[n]
SB,b
GB-1
cxp
-
Σ
min Bo,s
ie|n|
b=1
27

---

Published as a conference paper at ICLR 2026
for all À >> 0 since ".ss...,,,,.11. 100-1-measurable Consider the inner expectation separately:
E
exp
min BB.i) (e(m)
Gn = IR
max exp (-XB,)) 9 E exp (-ABB,)) 9B-1): ielm
1=1
where we bound max by E.
Using the temporal definitions of {3B,t):
exp
-A min BB,i
9B-1
(E(m)
n
E
exp
-min
h
BBBkk
Ts
9B-1
1=1
k=1
k=1
E
max
exp
Ah
eep
AT
MBibk
9B-1
(38)
k=
n
E
exp
- Ahh
B
9B-1
+
E
cxp
-
ATz
BB
9B-1
i=1
Kim
7
Using the tower property,
E
E
exp
(-XMm
1B., -1.... 00,11 Gn
exp
-Ah
mn,ik
GT-1
J1==
(39)
Next,
( -Ahm )
J1 : E exp
9B-1
I exp (-\t)
+ P [17B,1 S 1 4- -1..... 17B,1,1, 9B-1)
= =exp (- + (1 - exp (-Xht)) [INB,, S &111B, -1,-.., 1,,,,, Gn-1
exxp (-Xt) + F
(1TB,1 # S St -11.... 1...1....BB...1195.... 1B,1119B-11
t
= exp (-Xt) + P
1B,i. S h
MB,, 1.B............3.... AB..1.
for all 2 0. Due to (34),
J1 S exp (-Xt) + tpo
Substituting to (39),
lpo h
Σ exp (-Xt)
E
exp
Ah
AB,i,
GB-1
Using the same arguments
K 2
1 times, we obtain
1po $
h (exp(-Xx
+
(40)
28

---

Published as a conference paper at ICLR 2026
for all 1 2 0. The analysis of 12" K222
little bit more evolved. For all 1 S S 2
12
exp
-XTs
MBB.,k
9B-1
n
4-1
E
E eexp
-XT, k=1
PBi.kk
9B-1
Kai
and 12 = n. Let us define u Exm BBB. If 2 1 then
(- Ardd 2
K₂ = Eexp (-XTT) -. 1.t.-.................... exp s exx
Otherwise, if u < 2 then, for all t 0,
E [eepp (-AAABBB,.))) (BB.J--......MB..1......
$ expp (-xt) +
PBB.. S -BB,i,-1,..... 1,,,6,,,,,,,,,,111 9B-1
K
S exp (-Xt) + 2Kt
S cxp (-x + - u
c +1
Tyd 2t
due to (35) and
2. Combining both cases,
{ (xx
2Kt T,d 2t
ATzd
K2 S max
exp
-ATs k=1
BBiik
eep
for all 1 < Id and u 2 0, and
13 < exp (-xt) + 2Kt
AT,dd
E
exp
-XT,
MB
GB-1
+ +nexp
(-2
Tsd 21
i=1
2Kt
XTed
exp (-X6)
12-1
exx
(41)
T&d
where we use the inequality max {a, b) S a b for all b 2 0. Substituting (40) to (38),
K
(- min SB,i
tpo
E
exp
1B-1 S eep +
+ 1
ie(n)
h
where I, A 2 are free parameters. Taking! / = 4+ loR(2n)
$
-> min (B,) ) GB-1 S iE|n]
c-1
(4 +
log log(2n))re
K
exp
(2n)2/K +
+
Ah
Choosing (2m)
2 (4 2 log(2n))
max
PK
h
Te
exp
-X min (B.)) G3 1Eim
S n
(2n)2/k)
-
+
1
2
1
# (2c 12
+1
With this choice of and in (41), get
-1
T1 <
-111 - exe
(ee ( + 2 log((2))
(2n)2/K
30 -
30
1 + 40 <n
+ 2e 4
<
(2n)2/K
(2n))/K
29

---

Published as a conference paper at ICLR 2026
for j 2 because /
T.d (2 K.
4+ & log(2n) 2 22 (4 + 1 loog(2n) n.a In the
3
third inequality, unrolled the recursion with 13 n and use Σラ=
(2x)aTx
3e
2.
Finally, 12 1 1/2 (3c-1) $ + 22ee_eek
S = and
E
exp
-> min In.s)
)
9B-1
- 2
1 $ + 1 1 2 _0- + e =
4)
se-
(E(m]
Substituting the last inequality to (37) and repeating the steps more times, we get
B
min Bo, =( S eexp(X - BK). xE(ni
left take 7
BK 6
30

---

Published as a conference paper at ICLR 2026
F MAIN THEOREM WITH WORKER-TO-SERVE COMMUNICATION
In this section, we extend the result of Theorem 4.2 by taking into account the communication time Tw. However, in this section, ignore the communication times from the server the workers in the analysis, which will be sufficient to obtain an almost tight lower bound combined with Theorem 4.2.
Tyurin et al. (2024) consider similar setup with 7, = O. However, their protocol does not allow the workers modify the iterate computed by the server and operates in the primal space. For instance, the workers are not allowed to run local steps. Moreover, P. are fixed in their version of Protocol 1. We improve upon this in the following theorem:
Theorem F.1 Let L, A, a², d, Tw: Tsp h > 0 be any numbers such that < ca L. and d 2 AL ozg Consider Protocol For all E [m] and k 2 compressor C selects and transmits P uniformly random coordinates without replacement, scaled by any constants, where P {O..... d] may vary across each compressor. For any algorithm A E Aa, there exists function f R R such that f is L-smooth, f(0) inf f(x)= S A, exists a stochastic gradient oracle that satisfies Assumption 1.3, and yns [[)(()) > E for all
LA
ho?
Twd
Two
ho? 1 E .11]
t C3 log(n 1)
min max
h, Tw
max
ns
n
where St is the set of all possible points that can be constructed by up to time t based on and {Tz). The quantities cı, c22 and eg universal constants.
Proof. The proof closely follows the analysis from (Tyurin et al., 2024; Tyurin & Richtárik, 2024)
and the proof of Theorem 4.2, but with some important modifications. In this proof, sufficient to work with (6) and Lemmas 2.1 and 2.2.
Let us fix and define the function f Rd R such that
LX² ((x) = 41
FT
where the function Fr is given in (6) and T[T] E RR is the vector with the first 7 coordinates of Rdd Notice that the last d coordinates are artificial.
First, we have to show that f is L-soohhh and f(0) infzer f(x) < A.
Using Lemma 2.2,
[V(()) vf(()) L
[
U[T]
T[T
M[T]
V Fr
V Fr
LA
X
X
= L | yıl!
< L
||
yll
Vz, y E IRd
Taking
A
T=
LA
LA2
LA
f(0) inf f(x) zERd
(Fr (0)
inf Pr(x)) ZERT
<A.
due to Lemma 2.2.
Next, we construct a stochastic gradient mapping. For our lower bound, we define
Po -5-1) Vr E IRd.
[v((2 == v,f((>) 1 1 prog(z))
(42)
and let Dj- = (Bernouli(p,)) for all j E [n], where Po E (0, 1]. We denote [xl, as the jth coordinate of vector I E IRd. We choose
Pa = min 22X232 2
2
31

---

Published as a conference paper at ICLR 2026
Then this mapping is unbiased and --variaace-boundde. Indeed,
(1 (1+1 1 prog(z))
[5]
-1) 1)) V.f(x)
[[V =
Po
for all E [d]. and
(
(5-11)
E
[V)(zt v
max [ jcld
Po
because the difference is non-zero only in one coordinate. Thus
[V)((>) (1 po)
L2X2 Fr
(+) (1- -p))
E [V V
G.
Po
I. 2/ Po)
5
i.p
where we use Lemma 2.2. Taking
V25h
L
we ensure that
[+(())]
L2X²
Fr
[[T]]
2
2=1 (prog(Zrr) < T]
(43)
l9
for all x E Rd, where we use Lemma 2.1. Thus
AT
T
(44)
2cl A
and
2 r²
Pr min
Using the same reasoning in Tyurin al. (2024) and our Theorem 4.2, we define two of random variables. Let 7/. be the first computed stochastic gradient when the oracle draws a "successful" Bernoulli trial in (42) at worker Then,
P (mn, 51) S
_ Po) Do) ) Po S Po Lt
1=1
fort 2 0, and
P (m, 5) < min(ps [t],
For all E [n], the server receives stream of coordinates from worker i. Let fı,á be the number of received coordinates by the server from worker until the moment when the index of the last received coordinate is 1. Let us define
2
Pa =
Similarly to the proof of Theorem 4.2 with K (see (29)),
11
PP (J4, S 5/m)))
Σ
(M1,5,1 =s) d-
1=1
for < d. Thus,
18
t d
[t] pd:
t t
P (pr. 5 t/ma)) <
7-411
<
< min [8] pa. 1}
1
t>
1,
32

---

Published as a conference paper at ICLR 2026
for all 2 O.
There are two ways in which worker can discover the first coordinate. Either the worker is "lucky" and draws successful Bernoulli random variable locally, or it gets to discover the first coordinate through the server. Thus, worker requires at least
M1 min hom min (mm + Tw/liat min (km + 1 f]TwHln) jE(n)
jE(mlivti
seconds because fim1 is the minimal time discover the first coordinate locally, and miniii [hm,, + Tw/11.j } is the minimal time to discover the first coordinate from other workers via the server, which can transmit
worker i.
Remark F.2. The previous derivations hold for all > 0. If we start taking the communication time Ts into account, then y1, may only increase. For all Ts > O, worker still requires at least yı,; seconds for the same reason that fmm, is the minimal time discover the first coordinate locally, and jil.jj { + Tw/lij) workers. If we start taking into account the communication time from T,, the lower bound
the minimal time to discover the first coordinate from other
min
lmm,s min (Jms + Tw/l je(n]ays
still holds.
Using the same reasoning, worker requires least
Uk.i min {lonks + 1[ + j Tw/ik + yk 15) jEin]
seconds discover the hthh coordinate for all 2, where
P (mn.a S t(9x-1) & min([t] po: 1}
(45)
for all k 2 1, i E [n]] and t 2 0, and
P (Mu.s S t/mk,i GR-1) min [t] pa.
(46)
for all k 1, [n]. and 2 0, where GR-1 the sigma-algebra generated by {me, aeer) and {ur (eei,, Thus, the first possible time when the workers and the server can discover the thh coordinate is
yr min yr,
vE(n]
For this random variable, we prove the lemma below (see Section F.l).
Lemma F3. Let (ma.) J4,200 and (un,i)i be random variables such thut
P ((K.s $ 11 S min(L!) Po; 1}
(47)
for all l 2 1, [n), and 2 0, and
TP (JuKs S t/me,,, 9k-1) S min 1), for all k 2 1, 1, [n], and 2 0, where Gk-1 is the sigma-algebra generated by (ne ahee Mejm) and (uw,)sselll ck. Then
(48)
P 5
with
T logn + log i
min max h Tw Vhew h, Tw }. h
(49)
32 looo(8n) (8n)
Pon pan' VPopan"
Po
where
vr min ST. sE(n]
Uk.i == min {lon. + 1 + jl TwWki + Nk-15} jEin]
for all k 1, [n] and you for all [n].
33

---

Published as a conference paper at ICLR 2026
Thus, with probability at least 1 6, any zero-respecting algorithm requires at least f seconds to discover the last coordinate. Due to (43),
inf yES,
[V > 2s inf 1 prrg((r))) < <T),
yES.
where St the set of possible candidate points to be an e-staionnayy point up to time 1, which can be computed by A. Taking 0
2
E
inf
[V
2=E inf [prog(urr)) < [T] 2 E,
yES.
L
for = f because prog(u (UT)) < T for all E St with probability at least 2.2 is left to substitute all quantities:
AL log n + log
A0
o² 11 Tud VhdTw o²
o² 225
64 (8g(
min
max max n
2 [
2n
V2n V
2
h, Tw hmax
Since l, A You
Yoc are universal constants, assuming e < ci LA for some small universal e₁ > 0, we
get
LA min
ha² T1
Twd
ha 718
hao
22
max
h, Tw
max
12
log(n + 1)
n
for some small universal Cs > 0. Notice that we can take any dimension d such that
LA
d d 0
F.1 MAIN CONCENTRATION LEMMA
Lemma F.3. Let F1,20 and (PRA)skko be random variables such that
P (TK.a S t s min((t] pa: 1}
(47)
for all k 2 1, [n]. and t 2 0, and
(uu,s S t/m Gk-1) S min [t] pa. 1,,
(48)
for all 1, E [m], and 2 O, where 9k-1 the sigma-algebra generated by {Tk Aoleeo) and (pw (eee))) Then
P(T S S
with
[ 1:= T- log log
h
Tw
hhw PPoPan
min max
Ji Tw
(49)
32 (gg(8))
Pon Pan'
Pc
where
vr = min yr,
sE(n]
Uk. == min (lonk.j + 1 + jl Twitkis M)-15) jEim]
for all k 1, E [n]] and yo, for all [n].
Proof. Using the Chernoff method for any > 0 and A 2 1, we get
P (yk < 1) PP (-sys- 2 - st) = sye 2 e ed)
< = of
-
34

---

Published as a conference paper at ICLR 2026
(-s min yk.s))
)
E exp
- e
maxexp (-SyRR))
jE(n)
JE(m)
Bounding the maximum by the sum,
(un 5 S
E (exp (-syk.)) ne" max E [exp (-SyKk.)] je(n)
(50)
We focus on the last exponent separately. For all i [n],
E [exp (-8yR,))
=
E
exp
-8 min (1m + 1 o j) Tw/Ak. + yk-1-)) jE(n]
E
max exp (-s (fomee + L[i + j] Twfkkis yo- ]E(nn
E (exp (-s (fom + 1 # fTTtt 9k-1)))]
(51)
/=1
E
E [exp (-8 (hmps 1 j)TWAk Gk (xppp 15)
11=m
Considering the inner expectation separately:
I = E exp (-s (hm + 1 * 51 9k-1l
I exp (-st) (hma. + 1 + jwTWk S 9
for all 2 0. Using the properties of condition expectations,
Ti S exp (-s() + IP (hma. S 6, 1 + j]_mees S 1(gk-1)
exp (-st) + E [hm..j < [1 + j|Tw/u.. S t]] 9k-1]
exp (-st) + E E
[ j]Tw/Kk.j I fl] nk.j. 94-1 [hm S 9k-1
(-sl + E
P [1 i * j] S 1/ Gx-1) [hm S 1] 9k-1]
If =. then we bound the probability by 1 and get
41 S exp (-st) + E [hmss S 9x-1
exp st) + P (hmm.s t(gk-1)
t
exp (-st) +
h
Po:
for / 2 0, where we use (47). Otherwise, if + j, using (48) and (47),
t
11 exp (-st) + EE min 1,2
Pd
[hn]a S
Gk-1
Tw
t
exp (-st) + min 1,2
Pa
P (hamee
st(9r-1)
Tw
t
t
exp (-st) + min
1,2
Pa
min
1,
Po
Tw
h
for 2 0. Substituting the inequalities to (51),
E (exp (-syk.:)]
Σ
exp (-st) min 1,2
t
Pd
min
1,
t
Po }
lexp (-syk-1,))
Tw
h
jti
exp (-st) + min {1] 1,
+
Pa
lexp
(-8yk-
h
for all e [n] and 2 0. Thus,
max E. |exp (-sy).:)] sE[n]
35

---

Published as a conference paper at ICLR 2026
Pa })
Po Do
})
(n - 1) exp (-st) + min 1,2
pd
min
1,
ht]
exp (-st) + min
1.
max E (exp ( (-yyk-1,(t)
po }) + min {1
exx (-st) + (n 1) min
1,2
Pa
min
1,
Po
max kE(x)
IE [exp (-8yk- -y,k-,,,))
Tw
Taking 8 = log(8n) we get
max jexp (-syk,,) ie|n
+ (n 1) min 1, 2
Pd
min
po }
+
min
Po
max [EIn]
(exp (-89k-
8
T2:m
Ig
(52)
Next, we take min(41, /2), where
h
Tw
/TT
h
Tw
= max
32p
32p 32 /2/PoPa'
32
32
and
h
t2 =
32po
to ensure that
13 S min (1, t2po
1
h
16
There are five possible values of tj.
If f1 32pm then
(1,
lia
1
12 I (n - 1) 1)min
h
16'
If f1- 32pan then
12 S (n 1) min {1,
5
Tw
16
Vhr PP
then
212
I S (n - -1)
<
Tn
16
f =
h 32
then
t1
12 S (n - 1) min
1,
Po
h
Finally, if
32 then
t1
1 - (n - 1) min
1,2
Pd
0.
Tw
Thus, using (52), we obtain
max E (exp (-st.)) < VE(N)
max E /exp (- (-stk- -- (E(N]
max E (exp (-syk-1.)) sEIn]
16
16
for our choice of Unrolling the recursion and using yo.; = for all E [n].
max E [exp (-88k.))) 5 *E[n]
We substitute it to (50), get
P 5 < coltlognkk
It is left choose i = k-llg Hog
36


Reviews:
[{"review_id": "dy4ZjvZbhM", "reviewer": "Reviewer_2Z8R", "summary": "In the paper the authors discuss the influence of both worker to server (w2s) and server to worker (s2w) communications on the overall complexity of solving the distributed optimization problem. The authors propose a new worst-case function, that is required to prove the lower bounds for this setup.", "questions": "1)Theorem 4.2 contains only $\\tau_s$, but no $\\tau_w$. Theorem E.1, on the contrary, contains $\\tau_w$, but no $\\tau_s$. Could the authors clarify, how they correctly combine lower bound, that involve both s2w and w2s communications?\n\n2)Could authors specify more, how does the heterogeneous setup fail under the consideration of s2w communications?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1)Addressing not only w2s, but also s2w communications is important and not usually done in optimization.\n\n2)Modifying the worst-case function and using novel techniques to prove the lower bounds.", "weaknesses": "1)The class of zero-respecting protocols is quite restricting, as it does not contain sketchings, dithered quantizations, and so on. \n\n2)Theorems 4.2 and E.1 seems to be proven only for RandK compressors, rather than for any unbiased zero-respecting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "csRZy6aE9z", "reviewer": "Reviewer_9bv8", "summary": "This paper presents lower bounds for centralized federated learning under $L$-smoothness, where communication time is important. It contains a new construction of lower bounds with theoretical guarantees.\n\n I think this paper may be accepted.", "questions": "I checked all the theorems, except for key Lemma D.1. Therefore, I don't have any major or minor comments, and for this reason, I marked a low level of confidence.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) This paper is well written, and all the results are clarified.\n\n2) This paper provides a new construction for lower bounds.\n\n3) The result of this paper provides theoretical evidence and a quality comparison with previous works.", "weaknesses": "**Typos:** \n\n1). p. 5 line 228. It seems “quartic” $\\to$ “quadratic”\n\n2). P. 7 line 377. I think, $F_T \\to F_{T, K, a}$\n\n3). P. 22 line 1146. $j \\to k$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jNdaFkObxx", "reviewer": "Reviewer_vzMo", "summary": "This paper presents new lower bounds for centralized distributed non-convex optimization of smooth functions. This is an active area, where convergence guarantees for finding approximate stationary points using first-order stochastic oracles have been studied extensively in the past several years. The key difference in this paper's setting is that, instead of examining oracle, communication, or iteration complexity, the paper focuses on time complexity in a model where each machine has the same computation speed and potentially different up (to the server) and down (from the server) communication times. The paper considers the homogeneous setting, for which it is more challenging to establish lower bounds, as one can not benefit from the usual round complexity constructions, which force machines to depend on each other for growing the coordinate span of their model. \n\nThe most remarkable, and perhaps astonishing, result that the paper shows is that when the up and down communication times are comparable, the optimal time complexity is attained by the best of (uncompressed) mini-batch SGD and single-machine SGD. Given the attention this research area has received, a plethora of algorithms have been devised and analyzed, including compression algorithms. However, the fact that one of the two simplest algorithms is min-max optimal provides a firm foundation for the optimization theory in this area. Notably, this result is comparable to the seminal work of [Woodworth et al.](https://arxiv.org/abs/2102.01583), which also reveals the same dichotomy for homogeneous smooth convex optimization, but without considering computation and communication times. \n\nAdditionally, the paper presents a lower bound in the case where up and down communication require different times. In that setting, the bound is still matched by either one of the most natural compression algorithms, mini-batch QSGD or single machine SGD. The hard instance for the lower bound follows the serial hard instance due to Carmon et al., which in turn follows the chain function of Nesterov. The authors make the original hard instance more complex by altering the process of discovering the next coordinate. \n\nOverall, besides minor writing issues, I don't have any significant concerns with the paper and recommend accepting it. Once the authors address the writing issues, I am happy to increase my score.", "questions": "1. Because section 2.1 is not super clear, does the class of algorithms considered here allow simultaneous queries (multiple queries at the same random seed) or not? What about local update algorithms? Can the queries be adaptive to the information on each machine locally or not? I would like the authors to comment on the results of [Patel et al.](https://openreview.net/pdf?id=SNElc7QmMDe), which may provide better upper bounds when simultaneous queries are permitted. \n2. In the vein of the previous question, can the authors use their hard instance to give better lower bounds in the setting when computation and communication times are not critical, and we are looking at oracle complexity? Specifically, I want to understand whether the new technique can actually demonstrate that the convergence rate of SCAFFOLD and MB-SGD is tight in the oracle complexity sense. For more context, see [Table 1](https://openreview.net/pdf?id=SNElc7QmMDe) of Patel et al. and note that there is no lower bound for the single query model (their Theorem 3.2 can not demarcate between single and multiple queries).   \n3. How is the result in this paper morally different from [Woodworth et al.](https://arxiv.org/abs/2102.01583)? Should I view the consequence of the result as just the time-complexity version of their result? If so, can the authors comment on whether they believe non-convexity is actually critical to their construction? If not, is it possible to get a similar dichotomy between mini-batch and single-machine SGD in the convex setting as well? That would complete the picture in the homogeneous setting.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is well-written; it provides a comprehensive survey of the current landscape of results and algorithms, ultimately highlighting the gap in existing rates when it comes to time complexity, thereby motivating the central question of the paper. The paper also does a good job of summarizing the technical preliminaries and clearly expresses the novel technical idea. As mentioned above, the dichotomy between mini-batch and single machine SGD is a somewhat surprising result in the non-convex setting. It provides clarity on existing gaps and guides future research.", "weaknesses": "1. I believe the paper can do a more thorough job of reviewing the relevant literature. For instance, the morally most similar paper due to [Woodworth et al.](https://arxiv.org/abs/2102.01583) is not discussed. Similarly, several other interesting related threads are not discussed, such as multi-point oracles and variance reduction, which present natural improvements in the non-convex setting and where, in the oracle complexity model, (almost) min-max rates [are known](https://openreview.net/forum?id=SNElc7QmMDe). \n2. While the lower bound of the paper is surprising, I believe it is essential to highlight that the lower bound itself does not indicate or explain the \"limited scalability of centralized distributed optimization\". Firstly, the lower bound considers a specific setting of homogeneous non-convex optimization. It is very well possible that under additional assumptions, such as higher-order smoothness and/or some notion of quasi-convexity, we might expect different results and optimal algorithms. I would encourage the authors to read the future directions presented by [Woodworth et al.](https://arxiv.org/abs/2102.01583), which indeed motivated many exciting follow-up results. I recommend that the authors temper the conclusions to be drawn from the results, and instead use these to either motivate why other settings might be interesting to study or show empirical evidence that centralized distributed optimization has indeed plateaued (the latter is very unlikely to be the case).\n3. It is essential to underline that while in optimization theory the variance reduction due to averaging across the clients is usually the only justification for collaboration, that is a very narrow view. In a sense, the model under which such rates are provided is actually too restrictive to demonstrate the other benefits of collaboration. For instance, in the same vein as the hard instance of this paper, collaboration can help clients discover parts of the loss landscape that are inaccessible to individual clients. This effect does not appear in the stochastic optimization setup where fresh samples are used, and there is no distribution shift between the training and test distributions. Both of these effects are unavoidable in practice. Similarly, there is ample evidence that collaboration can have a regularization effect. This has been studied in the context of local update algorithms ([1](https://openreview.net/forum?id=dOoPSZFDiRB), [Section 4.3](https://arxiv.org/pdf/2507.00195)), but it may also be true in general for other forms of collaboration. \n\nOverall, in the last two points, I aim to emphasize that it is crucial to note that the paper examines a specific theoretical model, which does provide some evidence for what we might observe in real experiments. However, ultimately, that is a particular model, which can not capture all aspects of empirical training. \n\n4. I believe the presentation and definition of distributed zero respecting algorithms (whole of section 2.1) can be made much more crisp by introducing an oracle model. I recommend that the authors check the definitions in [Patel et al.](https://openreview.net/forum?id=SNElc7QmMDe) and other similar papers. Protocol 1 is quite confusing, and I especially don't like how the authors present two parallel for loops sequentially. I believe it is ambiguous to say what it means to calculate the next point, based on some information. This can be made more rigorous by considering a coordinate span, like the papers in this area do.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y8u8oGVQm5", "reviewer": "Reviewer_Neht", "summary": "This paper investigates the fundamental limitations of centralized distributed optimization within the federated learning framework. It establishes a new lower bound on the time complexity for finding an ε-stationary point of smooth non-convex functions. A key aspect of the work is the explicit inclusion of bidirectional communication costs, particularly the server-to-worker  communication time. The paper reveals fundamental limitations in scaling distributed optimization.", "questions": "1.Given the pessimistic results for unbiased compressors when τs > 0, does this imply that biased compressors (e.g., TopK) are a fundamentally better choice in practical scenarios with communication bottlenecks?\n2.Can the current analysis framework be extended to provide lower bounds for biased compressors? What are the main challenges in doing so, or would a completely new approach be required?\n3.How should a practitioner interpret these results when designing a distributed system? For instance, in a network with symmetric communication costs (τs ≈ τw), does your lower bound suggest that investing in the studied forms of compression is futile and methods like Batch Synchronized SGD are preferable?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The explicit consideration of bidirectional communication costs (τs and τw) is a powerful and novel contribution, reflecting a more realistic model of distributed systems.\n2.The paper makes a significant theoretical contribution by constructing a new lower bound that clarifies the scalability limits of a specific class of optimization algorithms.\n3.The construction of a novel \"worst-case\" function and the associated proof framework is a strong technical achievement.", "weaknesses": "1.The paper's discussion on the practical implications of its pessimistic results for unbiased compressors is too brief. It would be significantly strengthened by a more detailed exploration of how this points to the potential superiority of biased compressors in real-world scenarios.\n2.The practical takeaways for system designers and practitioners are not stated explicitly enough. The paper should offer clearer guidance on how these theoretical results should inform practical decisions (e.g., algorithm selection based on network characteristics).\n3.The scope is limited to unbiased compressors, while many state-of-the-art methods use biased ones. The paper should better position itself regarding this gap between its theoretical setting and common practice.\n4.The notation is dense. A table of key symbols and their definitions in the appendix would improve the paper's readability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)