Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations
Authors: Alexander Tyurin
Kaja Gruntkowska
Peter Richtárik
Venue: NeurIPS 2024 poster (2024)
Keywords: Nonconvex Optimization
Asynchronous Methods
Distributed Optimization
Lower Bounds
Variance Reduction
Primary area: optimization

Abstract: In practical distributed systems, workers are typically not homogeneous, and due to differences in hardware configurations and network conditions, can have highly varying processing times. We consider smooth nonconvex finite-sum (empirical risk minimization) problems in this setup and introduce a new parallel method, Freya PAGE, designed to handle arbitrarily heterogeneous and asynchronous computations. By being robust to "stragglers" and adaptively ignoring slow computations, Freya PAGE offers significantly improved time complexity guarantees compared to all previous methods, including Asynchronous SGD, Rennala SGD, SPIDER, and PAGE, while requiring weaker assumptions. The algorithm relies on novel generic stochastic gradient collection strategies with theoretical guarantees that can be of interest on their own, and may be used in the design of future optimization methods. Furthermore, we establish a lower bound for smooth nonconvex finite-sum problems in the asynchronous setup, providing a fundamental time complexity limit. This lower bound is tight and demonstrates the optimality of Freya PAGE in the large-scale regime, i.e., when $\sqrt{m} \geq n,$ where $n$ is \# of workers, and $m$ is \# of data samples.

Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations
Alexander Tyurin KAUST, AIRI; Skoltech
Kaja Gruntkowska KAUST
Peter Richtárik KAUST
Abstract
In practical distributed systems, workers typically not homogeneous, and due to differences hardware configurations and network conditions, can have highly varying processing times. We consider smooth nonconvex finite-sum (empirical risk minimization) problems in this setup and introduce new parallel method, Freya PAGE, designed to handle arbitrarily heterogeneous and asynchronous compu- tations. By being robust to "stragglers" and adaptively ignoring slow computations, Freya PAGE offers significantly improved time complexity guarantees compared all previous methods, including Asynchronous SGD, Rennala SGD, SPIDER, and PAGE, while requiring weaker assumptions. The algorithm relies on novel generic stochastic gradient collection strategies with theoretical guarantees that can be of interest on their own, and may be used in the design of future optimization meth- ods. Furthermore, problems the asynchronous setup, providing a fundamental time complcxity limit. This lower bound is tight and demonstrates the optimality of Freya PAGE in the large-scale regime, i.c., when / /m 2 n,, where n # of workers, and m is data samples.
establish lower bound for smooth nonconvex finite-sum
Introduction
In real-world distributed systems used for large-scale machine learning tasks, it is common to encounter device heterogeneity and variations in processing times among different computational units. These can stem from GPU computation delays, disparities in hardware configurations, network conditions, and other factors, resulting in different computational capabilities and speeds across devices [Chen et al., 2016, Tyurin and Richtárik, 2023]. As a result, some clients may execute computations faster, while others experience delays or even fail to participate the training altogether.
Due to the above reasons, we aim to address the challenges posed by device heterogeneity in the context of solving finite-sum nonconvex optimization problems of the form
min ZER
f(x) = Σ f((x)
where f. IRd + R can be viewed as the loss of machine learning model æ on the 7th example in a training dataset with samples. Our goal is to find an e-stationary point, i.c., (possibly random) point & such that f())(( < e. We focus on the homogeneous distributed setup:
there are n workersfclienttsdeevice able to work in parallel,
KKin Abdullah University Science Technology, Thuwal, Saudi Arabia
AIRI, Moscow, Russia
$ Skolkovo Institute of Science and Technology, Moscow, Russia
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

each worker has access to stochastic gradients ff..j j E [m],
worker calculates V (-) in less or equal to E [0, oo] seconds for all i E [n]. E [mm].
Without loss of generality, we assume that тi S ... < Tn. One can think of T; E [0, oo] as an upper bound on the computation time rather than a fixed deterministic time. Looking ahead, iteration complexity can be established even if T; = oo for all E [x] (Theorem 4). We also provide results where the bounds (T/} } are dynamic and change with every iteration & (Section 4.4). For simplicity of presentation, however, we assume that T T; for E [n], k 2 unless explicitly stated otherwise.
1.1 Assumptions
We adopt two weak assumptions, which are standard for the problem (1) [Fang et al., 2018). Assumption 1. The function f is L-ssoooth and lower-bounded by f E R.
Assumption 2. 1L+ 2 such that 1 m
[Vf(()) < L2 || yll Va, y e Rd.
We also consider Assumption 3. Note that this assumption does not restrict the class of considered functions {fi]. Indeed, if Assumption 2 holds with L4, then Assumption 3 holds with some L I L+. If one only wants to rely Assumptions and 2, it is sufficient to take L = L+. However Assumption 3 enables us to derive sharper rates, since L can be small or even 0, even if L_. and L,, large [Szlendak et al., 2021, Tyurin al., 2023, Kovalev et al., 2022].
Assumption 3 (Hessian variance [Szlendak al., 2021]). There exists L 2 0 such that
V - - V/ S L1 || yl1
Vx,y E Rd.
1.2 Gradient oracle complexities
Iterative algorithms are traditionally evaluated based on their gradient complexity. Let us present a brief overview of existing theory. The classical result of Gradient Descent (GD) says that in the smooth
nonconvex regime, the number of oracle calls needed to solve problem (1) is O(ms 1) because GD converges in O(=-1) iterations, and calculates the full gradient Vf = 1/m Di=1 ff, in each iteration. This was improved to O(m m by several variance-reduced methods, including SVRG and SCSG [Allen- Zhu and Hazan, 2016, Reddi et al., 2016, Lei et al., 2017, Horváth and Richtárik, 2019]. Since then, various other algorithms, such as SNVRG, SARAH, SPIDER, SpiderBoost, PAGE and their variants, have been developed [Fang et al., 2018, Wang et al., 2019, Nguyen et al., 2017, Li et al., 2021, Zhou et al., 2020, Horváth al., 2022]. These methods achieve a gradient complexity of O(m + /m= ") matching the lower bounds [Fang et al., 2018, Li et al., 2021].
That said, in practical scenarios, what often truly matters is the time complexity rather than the gradient complexity [Tyurin and Richtárik, 2023]. Although the latter metric serves as a natural benchmark for sequential methods, seems ill-suited in the context of parallel methods.
1.3 Some previous time complexities
Let us consider some examples to provide intuition about time complexities for problem (1).
GD with 1 worker (Hero GD). In principle, each worker can solve the problem their own. Hence, one approach would be to select the fastest client (assuming it is known) and delegate the task to them exclusively, A well-known result says that for L- objective function f (Assumption 1), GD converges in 8 L_e -1 iterations, where 8 ;= f(x²) f", and x. is the starting point. Since at each iteration the method computes gradients Vf(()) i E [m]] the time required to find an E-stationary point is 80 __ x mti seconds.
GD with n workers and equal data allocation (Soviet GD). The above strategy leaves the remaining n workers idle, and thus potentially useful computing resources are wasted. A common approach is to instead divide the data into equal parts and assign one such part to each worker, so that each has to compute m//n gradients (assuming for simplicity that m is divisible by n). Since at each iteration the strategy needs to wait for the slowest worker, the total time is 8 P__E-t x m7./n. Depending

---

Table 1: Comparison of the worst-case time complexity guarantees of methods that work with asynchronous computations in the setup from Section (up to smoothness constants). We assume that Ti E [0, oc| is the bound on the times required to calculate one stochastic gradient V.s by worker i, T1 S S Tu, and m 2 n log n. Abbr: 8 = f(x") f",
# of data samples, n = of workers, error tolerance.
Method
Worst-Case Time Complexity
Comment
Hero GD (Soviet GD)
00
Suboptinal
Haro RAGE (Soviat PAGE) [L al. 2021]
m.
(Th
m
Vm
Suboptimal
Limitatinn:
SYNTHESIS
bounded gradient assumption, calculates the full pradienss suboptimal. (b)
[Li er al. 2022]
Asynchronous SGD [Kolokkva et 2023]
Limitations:
_ +
bounded vuriance assumption. suboptimal when is small.
[Mishchenko et 2022)
73
Ronnala SGD [Tyurin Richtinkk, 2023
min |E(m]
+ to
1
x2
-1)
hounded variance aesumption, suboptimaa when is small.
Limitation:
2- 7:
min sE(m)
(m +)
Proya PASE
Optimal in the large scale regime. ie. ymm 2 (sce Section
(Theorems
50 sc
min
(wii +
min
1
(m + 5)
bound (Theorem 10)
?5
g0
min jE(m)
(m++
Fraya PAGE has universoily better guarantees than all previous methods: the dependence on C (1/e) (unlike Remall SGD and Asynchronous SOD), the dependence on [rr] harmonic-like like and robust slow workers (robust the assumptions are weak, and the time complexity Freya PAGE optinall when /m 2 n.
oo) (unlike Soviel PAGE and SYNTHESIS).
In Line 3 of their Algorithm 3. they calculate the full gradient, assuming that it can be done for free and not explaining how. (i Their convergence rates Theorems and depend on bound the delays A, which tum depends on the performance of the slowest worker. Our method does not depend on the slowest worker if it is too slow (see Section 4.3), which is required for optimality. We prove better time complexity in Theorem 6, but this result requires the knowledge of {T,} in advance, unlike Theorems 7 and 8.
on the relationship between Ti and Tw/n., this could be more efficient or less efficient compared to Hero GD. This shows that the presence of stragglers can eliminate the potential speedup expected from parallelizing the training [Dutta et al., 2018].
SPIDER/PAGE with worker or n workers and equal data allocation (Hero PAGE and Soviet PAGE). As mentioned in Section 1.2, SPIDER/PAGE can have better gradient complexity guarantees than GD. Using the result of Li et al. [2021], the equal data allocation strategy with n workers leads to the time complexity of
Tooiiet PAGE := + Tn max { 13 + Tn
8 max L- max
(2)
seconds. We refer to this method as Soviet PAGE. In practical regimes, when E is small and L. xe L1. this complexity can be /m better than that of GD. Running PAGE the fastest worker (which will call Hero PAGE), we instead get the time complexity THero PAGE == θ (Tim + 71 (1%/c//)
Given these examples, the following question remains unanswered: what is the best possible time complexity in our setting? This paper aims to answer this question.
2 Contributions
We consider the finite-sum optimization problem (1) under weak assumptions and develop new method, Freya PAGE. The method works with arbitrarily heterogeneous and asynchronous computa- tions on the clients without making any assumptions about the bounds on the processing times We show that the time complexity of Freya PAGE is provably better than that of all previously proposed synchrooousaasymccrooooss methods (Table 1). Moreover, we prove a lower bound that guarantees optimality of Freya PAGE in the large-scale regime (ym 2 n). The algorithm leverages new compu- tation strategies, ComputeGradient (Alg. 2) and ComputeBatchDitfeeencc (Alg. 3), which are generic
3

---

Algorithm Freya PAGE
1: Parameters: starting point 20 Rd, learning rate 0, minibatch size S E N, probability
E (0, 1]. initialization g" = (xx²) using ComputeGradient(e)) (Alg. 2)
2: for k= ....,
do
3: 1h+1 x²"h 7g
4: Sample c Bernouli(pp)
5:
if ch then
(with probability p) (Alg. 2)
6:
V [l(x+t1) ++) ComputeGraddee(((A()))
7:
++ (f(x*t1)
8:
else
(with probability 1 p)
9:
Σ (Vi((*tt)) -V(((t))-V(((()) CompuueeaacchDiferrcce((( x+1 ,x²)) (Alg. 3)
EES
++1 g
Σ (Vf((*t11) V(f((z+))
iES*
end if
12: end for
(note): S* is a set of ii.d. indices that sampled from [m]] uniformly with replacement,
|*
and can be used in any other asynchronous method, These strategies enable the development of our new SGD method (Freya SGD); see Sections 6 and Experiments from Section on synthetic optimization problems and practical logistic regression tasks support our theoretical results.
3 The Design of the New Algorithm
It is clear that to address the challenges arising in the setup under consideration and achieve optimality, a distributed algorithm has to adapt to and effectively utilize the heterogeneous nature the underly- ing computational infrastructure. With this in mind, now present new algorithm, Freya PAGE, that can efficiently coordinate and synchronize computations across the n devices, accommodating arbitrarily varying processing speeds, while mitigating the impact of slow devices or processing delays on the overall performance of the system.
Freya PAGE is formalized in Algorithm 1. The update rule is just the regular PAGE [Li et al., 2021] ] update: at each iteration, with some (typically small) probability p. the algorithm computes the full gradient V /f(zx ")(**+1,, and otherwise, samples a minibatch S of size S and reuses the gradient estimator ge from the previous iteration, updated by the cheaper-to-compute adjustment $ E.es (V -
Within Algorithm 1, at each iteration we call one of two subroutines: ComputeGradient (Alg. 2, performing the low-probon wwwobababiyitty step), and ComputeBatchDifeerenaa (Alg. 3, performing the high- probability step). Let us focus on ComputeGradient, designed to collect the full gradient: it takes point input and returns V f(()
my Di=1 (xr).. There exist many strategies for implementing this calculation, some of which were outlined in Section 1.3. The most naive one is to assign the task of caleulating the whole gradient V f single worker i, resulting in worst-case running time of mt, seconds for ComputeGradient. Another possible strategy is to distribute the functions {frt evenly among the workers; in this case, calculating f takes tn max(""/n 1} seconds in the worst case.
Clearly, we could do better if we knew {T; } in advance. Indeed, let us allocate to each worker j a number of functions {fi} inversely proportional to Ty. This strategy is reasonable the faster the worker, the more gradients can compute. We can show that such a strategy finds V in
+
min jEin
(m + j)
seconds in the worst case (see the proof of Theorem 2). This complexity is better than mT) and Tn mm/x(m/n)) 1} (Theorem 31). However, this approach comes with two major limitations: requires knowledge of the upper bounds {T:}. ii) even if we have access to (Tr). the computation environment can adversarial: theoretically and practically, it is possible that at the beginning the
first worker is the fastest and the last worker is the slowest, but after some time, their performances

---

Algorithm 2 ComputeGradien((2)
Algorithm 3 CompuuuBaacchDiiirenaaa..
1: Input: point E Rd
1: Input: batch size 5 E N. points z, R2
2: Init g E Rd set =
2: Init g = 0 E IR
3: Broadcast
all workers
3: Broadcast y to all workers
4: For each worker i E [n], sample j from [m]]
4: For each worker, sample j from [m] uniformly
uniformly and ask it to calculate (z)(
and ask it to calculate V[z(x) vl(w)
5: while M o [m] do
5: for i 1. ........, do
6: Wait for V (x)()) from worker
6:
Wait for V5((z) f from worker
7:
if p E [m]] M then
7:
g g + (Vf(()) ff((y)
8:
g - 9 + (z)
8: Sample from [m] uniformly and ask
9:
Update M + MU {p)
this worker calculate
end if
9:
end for Return g
11: Sample j from [m]] M uniformly and ask 10:
this worker to calculate (z)
12: end while
can aggregatte fy locally, algorithm call AlReeduce once to collect all calculated gradients. ii) By splitting
Notes:
13:
Return m Σ f((x))
[mm] into blocks, instead V we can workers to calculate the sum of one block in Alg, 2 (and use similar idea in Alg. 3).
swap. Consequently, the first worker might end up being assigned the largest batch, despite now having the lowest performance. Thus, this strategy is not robust to time-varying speeds.
New gradient computation strategy. The key innovation of this work lies in the introduction of new computation strategies: Algorithms 2 and 3. We start by examining Algorithm 2. first broadcasts the input x E Ra to all workers. Then, for each worker, it samples uniformly from [m] and asks it to calculate (z) (with a non-zero probability, two workers can be assigned the same computation). Then, the algorithm enters the loop and waits for any worker to finish their calculations. Once this happens, it asks this worker to compute a stochastic gradient with new index sampled uniformly from the set [m]] of indices that have not yet been processed (again, is possible to resample an index previously assigned to another worker). This continues until all indices i E [m]] have been processed and the full gradient 7n, Ei= ffs has been collected. Unlike the previous strategies, our Algorithm does not use {T,}. thus being robust and adaptive to the changing compute times. Furthermore, we can prove that its time complexity (almost) equals (3):
Theorem 1. The expected time needed by Algorithm 2 to calculate
1 m
Σ i=1
Vi is at most
i Σ -.
12 min jEin]
(m + min(m, n) log (min (m, n)) + 5)
seconds.
The result (4) (the proof of which can be found in Section C) is slightly worse than (3) due to the extra min(m, n log (minfm, n)}) term. This term arises because worker may be assigned gradient (x) that was previously assigned to another worker (in Line 11 of Algorithm 2). Hence, with small (but non-zero) probability, two workers can perform the same calculations. However, typically the number of samples m much larger than the number of workers n. If we assume that m log n, which is satisfied in many practical scenarios, then the time complexity (4) equals
+ min jEIn
(m +2)
and the term min(m, n] log (min (m, n)) never dominates. Since this complexity is not worse than (3), our strategy behaves as if it knew (Ti) in advance! To simplify formulas and avoid the logarithmic term, we use the following assumption throughout the main part of this paper: Assumption 4. m log n, where is the # of data samples and is the # of workers.
We now proceed to discuss ComputeBatchDifferenee (Algorithm 3), designed to compute a minibatch of stochastic gradient differences. Both Algorithms 2 and 3 calculate sums. However the latter only
5

---

waits until there are S samples in the sum, where some indices in the batch may not be unique. On the other hand, Algorithm 2 must ensure the collection full batch of m unique stochastic gradients. As result, Algorithm 3 offers better complexity results and, unlike ComputeGradient, does not suffer from suboptimal guarantees and logarithmic terms, as demonstrated in the theorem below.
Theorem 2. The time needed by Algorithm 3 to calculate is at most
Σ -1
4 min jE(n]
(S (5+1)
(5)
seconds.
Algorithm uses uniform sampling with replacement, implemented Algorithm 3. However, one can modify the two algorithms slightly support virtually any unbiased sampling (see Section E).
is clear that to eliminate the need of waiting for very slow machines, some level of asynchronicity has be injected into algorithm for it to be efficient. Asynchronous SGD [Recht et al., 2011, Nguyen et al., 2018, Koloskova et al., 2022, Mishchenko et al., 2022] takes this concept to the extreme by never synchronizing and continually overwriting the updates. Consequently, the algorithm's 's time complexity is suboptimal. Conversely, imposing limitations on asynchronicity leads optimal methods, both in our context (in the large-scale regime) and in the scenario examined by Tyurin and Richtárik [2023]. Freya PAGE seamlessly combines synchrony and asynchrony, getting the best out the two worlds.
Note on asynchronicity.
4 Time Complexities and Convergence Rates
Formulas (3) and (4) will be used frequently throughout the paper. To lighten up the heavy notation, let us define the following mapping.
Definition (Equilibrium time). A mapping
IR20 x 120 7 R20 defined by
(S. [T. 1 = min
Σ 72
(S (8+1) oc]
(6)
JEIn]
called the equilibrium time. We let (S) t" (S, [Talitn) when considering {Fe} from Section 1.
Returning the algorithm, we guarantee the following iteration complexity.
Theorem 4 (Iteration complexity). Let Assumptions 1, 2 and 3 hold. Consider any minibatch size
N .1, any probability (0, 1), and let the stepsize be ? [T__ Iu v Then, after
1-p
ps
K 2 KPAGE == 28t (I- L+ V 173
iterations of Algorithmm we have [|V S where aK is sampled uniformly random
from the iterates {x=) ,..,,.... x K-1).
Theorem states that the iteration complexity is the same as in the optimal PAGE method [Li et al., 2021]. Note that (as long as there exists some worker that can complete computations within a finite time).
guarantee convergence even if the upper bounds {T,) are unknown infinite
We now derive time complexity guarantees. With probability the workers need to supply to the algorithm m stochastic gradients each of the m data samples, which by Theorem can be done in at most t" (m) seconds (up log factor). Otherwise, they compute S differences of stochastic gradients, which by Theorem 2 takes at most E (S)) seconds (up to a constant factor). The resulting time complexity is given in the theorem below.
Theorem 5 (Time complexity with free parameters p and S). Consider the assumptions and the parameters from Theorem 4, plus Assumption 4. The expected time complexity of Algorithm I is at most
T(p, S. (T]]/_] = 12- (m, [T,]]_]
(8)
4860
[__ + L+ /
1-p 15
[T]) x tp 17 (m, + (1- - p) ('' (8.

---

The first term comes from the preprocessing step, where the full gradient is calculated to obtain g" (x²)). Here, we use Assumption 4 that m 2 n logn. n. The result (8) is valid even without this assumption, but at the cost of extra logarithmic factors.
4.1 Optimal parameters S and
The time complexity (8) depends on two free parameters, S E N and p E (0. 1]. The result below (following from Theorems 13 and 14) determines their optimal choice.
Theorem 6 (Main result), Consider the assumptions and parameters from Theorem 4, plus Assump- tion 4. Up constant factor, the time complexity (8) is at least (( == 1" (m,, (Ti]E=)
00 min L- 1 (m, (TIK
min SEN
(S.
L1 (m, (S.
(9)
V3
F(S)=
and this lower bound is achieved with S arg min F(S) and p- = p" (S*), where
SEN
V (m..177 1 (8.mm
1.
L_ (-l== S
L (S, [T.]E=) + L+
(S)
v9
otherwise.
Result (9) is the best possible time complexity that can be achieved with the Freya PAGE method. Unfortunately, the final time complexity has non-trivial structure, and the optimal parameters depend on {T.} in the general case. If we have access to all parameters and times {T.). then (9), S and p" can be computed efficiently. Indeed, the main problem is to find minsen F(S), which can be solved, for instance, by using the bisection method, because L_t" (S, [Ta]] is non-decreasing and La / (m, (S //////5 non-increasing in S.
4.2 Optimal parameters and p in the large-scale regime
Surprisingly, we can significantly simplify the choice of the optimal parameters S and p in the large-scale regime, when /m n. This is a weak assumption, since typically the number of data samples is much larger than the number of workers.
Theorem (Main result in the large-scale regime). Consider the assumptions and parameters from Theorem 4. plus Assumption 4. Up to constant factor and smoothness constants, if /mm 2 then the optimal choice of parameters in (8) is S* = [/m] and p* = 1/vm For this choice, the expected time complexity of Algorithm I is most
T(/vm, mm, (To) 12t (m, (T)) 1928 max .I+ to (Vm, (T]iit)
(10)
seconds. The iteration complexity with S [m and p = 1/mm is KPAGE S 48 mox(L
We cannot guarantee that S [ and p 1/ym is the optimal pair when /m n, but it is valid choice for all m 2 1. Note that (10) is true if m 2 n log n, and it is true up to a log factor n log n. In light of Theorem 15, can further refine Theorem 7 if the ratio L1/L is known:
Theorem 8 (Main result in the large-scale regime using the ratio L-/1.). Consider the assumptions and parameters from Theorem 4, plus Assumption 4. The expected time complexity of Algorithm I is at most (t (m, [Tr 1 + 8 x t' (min max [++ /////L 1), m,, [Ti) seconds, where = min max{ v L- 13, m) and 5/m.
For brevity reasons, we will continue working with the result from Theorem 7 in the main part of this paper. Note that the optimal parameters do not depend on {Ti), ). and can be easily calculated since the number of functions m is known in advance. Hence, our method is fully adaptive changing and heterogeneous compute times of the workers.
Even if the bounds are unknown and t; 4 max maax(T__,)) [I_, 3/e iterations, and calculates the optimal number of stochastic gradients equal to Om vm8 max{L_ L_, L+) /EE)
for all i E [n]. our method converges after
7

---

4.3 Discussion of the time complexity
Let us use Definition 3 and unpack the second term the complexity (10), namely,
max L L+}
min jeIn]
(vm 5)
somewhat similar expression involving minje[n] and harmonic means was obtained by Tyurin and Richtárik [2023], Tyurin et al. [2024] for minimizing expectation under the bounded vari- is standard in optimization [Nesterov, 2018, Lan,
ance assumption. The term 8 2020] and describes the difficulty of the problem (1). The term miin)em)((( 1/7.)- j))
represents the average time of one iteration and has some nice properties. For instance, the last worker is slow and In & oo, then minje[m]
the com- plexity effectively ignores it. Moreover, if j is an index that minimizes min then minje/ni (( ( 1/x))=((+++))) = (EE) (Vm + j*)). The last formula, again, does not depend on the slowest workers (j" +1.... na. which are automatically excluded from the time complexity expression. The same reasoning applies to the term t" (m, [Ti]E=1] ). Let us now consider some extreme examples which are meant to shed some light on our time complexity result (10);
mimje(a-nj(---)
Example 1. [Equally Fast Workers] Suppose that the upper bounds on the processing times are equal, i.e., Tj for all j E [n]. Then
T(//m, Vm, (r [=)) = θ (T mamxx { n (rmax
8th max LL. max
ym 1))
The complexity in Example matches that (2), which makes sense since Soviet PAGE is reasonable method when (7:} are equal. Note that the reduction happens without prior knowledge of (Ti).
Example 2. /Infinitely Fast Worker| If = 0, then T(4 Vm, [Ti] = O.
Example 3. [Infinitely Slow Workers] If = do E [n], then T(I /m. [Ty] = co.
Example 4. /Extremely Slow Workers] Suppose that the times T < oc are fixed Vj S jB and
Tj 2 B > jB for some B large enough. Then T(//mm, vm, [rilem) = T(1 mm, [T k=)))
Example says that the workers whose processing time is too large are ignored, which supports the discussion preceding the examples.
4.4 Dynamic bounds
turns out that the guarantees from Theorem 7 can be generalized the situation where the compute times } are allowed to dynamically change throughout the iterations. Consider the 4t iteration of Algorithm 1 and assume that worker calculates one Vf, in at most Tf E [0, oo] seconds Vi E [n], J e [m]. Clearly, max T < T Vi E [n] (where {r;-1} are upper bounds from the preprocessing step), but T.e can be arbitrarily smaller than т; (possibly Th = 0 and T; =0)).
Theorem Consider the assumptions and parameters from Theorem plus Assumption Up to constant factor, the expected time complexity of Algorithm I with S = /m] and 1//m is at most
[480 max [L,
(m, [T--1 1111
Σ
8s (Vmm, ( 1
(11)
where kk, is a permutation such that x Theorem 22 with the chosen parameters).
S mh.. for all 2 -1. (This theorem follows from
Hence, algorithm is adaptive the dynamic compute times {T.² Let consider an example with 2 workers. Assume that the first worker is stable: Tf = for all k: 2 0, and the second worker unstable: 7 = - is small the first iteration, and T a oo in the second iteration. For explanation purposes, we ignore the preprocessing term t" ("m,)) -), which is not factor if & is small. Then,
(11) t" (Vm, tt)==t(mm,,
[To.. 2) + t' (Vmm, I ( 2n + =t (' IT. 7)) t" (Vm, [7]) +...
8

---

because t" (ym, I ==22)) = (V [r]) when T2 ~ co. The time complexity in the second iteration depends on the first (stable) worker only, which is reasonable since oo, and this happens automatically. At the same time, the first term ("[ym, [T, depends on both workers, and this iteration will be faster because 1* (mm, [T, 7]) S 1" (*(m, [T]).
4.5 Comparison with previous strategies from Section 1.3
Our time complexities (9) and (10) are better than all known previous guarantees if m 2 n log n. In particular, T(//m,, vm, [Ti]i=1) I Troiict PAGE (from (2)), because t" ("m,, [Ti]i=1) X vmnra/n (Theorem 31). In fact, since lim,,-oo 1" (Vm,, (Ta]i=]) (" [Ti)l=1) co and lim,, -hn0 Vmr./n oc, Soviet PAGE can be arbitrarily larger. We also improve on Hero PAGE (see Remark 32).
4.6 Comparison with existing asynchronous variance reduced methods
Several studies have explored asynchronous variance reduced algorithms. Essentially all of them variants of the existing synchronous methods discussed in Section 1.2 and depend on the slowest worker in every iteration. There have been several attempts to combine variance reduction techniques with asynchronous computations, Perhaps the most relevant baseline is SYNTHESIS, an asynchronous variant of SPIDER [Fang et al., 2018] introduced by Liu et al. [2022]. The obtained gradient complexity matches that of SPIDER in terms of dependence on m, but scales linearly with the bound on the time performance of the slowest worker, making it non-adaptive to slow computations. Moreover, in Line 3 of their Algorithm 3, the full gradient is calculated, assuming that it can be done for free. Lastly, the analysis assumes the gradients to bounded.
Lower Bound
In previous sections, showed that Freya PAGE converges in most (9) (10) seconds, providing better time complexity guarantees compared to all previous methods. The natural question is: how good are these time complexities, and can they be improved? Section we formalize our setup and prove Theorems 29 and 30, which collectively yield the following lower bound.
Theorem 10 (Less formal version of Theorems 29 and 30). Assume that O < S... Tn and take any L4,80, 0 and m N such that < e1 L L80. Then, for any ggeooresppecting algorithm. there exists function f that satisfies f(0) - f < 8 and Assumption 2, such that it is impossible to find e-stationary point faster than in
Ω (m,, (m)
5 1" (m, (ri](==)) Vmme
(12)
seconds using uniform sampling with replacement.
Comparing (10) and (12), we see that Freya PAGE optimal under Assumptions and in the large-scale regime (y/m n). Indeed, without Assumption 3, have max(I__. I=] max L_, L+ = L.. Up to constant factor, (10) is less or equal to (12) since
L4.
((
-1
(vm+ (m++)))=
(
f 1 Tt
) (m + vmm)
t' (Vm, [Tilk_)) = min
1
=
1 min
JElm]
vm JEIN]
min jEbn
(m (m++
2 t (m, [Ts] ym
This is the first optimal method for the problem we consider, and Theorem 10 gives the first lower bound.
6 Using the Developed Strategies in Other Methods
ComputeBatchDifference (Algorithm 3) is generic subroutine and can be used in other meth-
ods. In Section H, we introduce Freya SGD, a simple algorithm with update rule xt11 x* 7 x ComputeBatch(S, x**, where S is batch size and ComputeBatch (Algorithm 4) is

---

minor modification of ComputeBatchDifference Theorem 25 establishes that Freya SGD converges in O (4/e> (4/e, [r:][=1) seconds (where we only keep the dependence on E and {ri}) ). For small E. this complexity is worse than (10), but it can be better, for instance, in the interpolation regime [Schmidt and Roux, 2013, Ma al., 2018]. Freya SGD resembles Rennala SGD [Tyurin and Richtárik, 2023], but unlike the latter, it is specialized to work with finite-sum problems (1) and does not require the bounded variance assumption on stochastic gradients (which is not satisfied our setting).
Acknowledgments and Disclosure of Funding
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Artificial Intelligence and Data Science. The work of A.T. was partially supported by the Analytical center under the RF Government (subsidy agreement 00000007:3021 Grant No. 70-2021-00145 02.1 02.11.2.
References
Z. Allen-Zhu and E. Hazan. Variance reduction for faster non-convex optimization. In International Conference on Machine Learning, pages 699-707. PMLR, 2016.
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pages 1-50, 2022.
Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points I. Mathematical Programming. 184(1):71-12)) 1000:111100,, 2020.
J. Chen, X. Pan, R. Monga, S. Bengio, and R. Jozefowicz. Revisiting distributed synchronous SGD. arXiv preprini arXiv: 006400997, 2016.
S. Dutta, G. Joshi, S. Ghosh, Dube, and P. Nagpurkar. Slow and stale gradients can win the race: Error-runtime trade-offss in distributed SGD. In International Conference on Artificial Intelligence and Statistics, pages 803-812. PMLR, 2018.
C. Fang, J. Li, Z. Lin, and T. Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Advances Neural Information Processing Systems, 31, 2018.
Horváth and P. Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. In International Conference on Machine Learning, pages 2781-2789. PMLR, 2019.
S. Horváth, L. Lei, P. Richtárik, and M. I. Jordan. Adaptivity of stochastic gradient methods for nonconvex optimization. SIAM Journal on Mathematics of Data Science, 4(2):634-648, 2022.
A. Khaled and P. Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2022.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference Learning Representations, 2015.
A. Koloskova, S. U. Stich, and M. Jaggi. Sharper convergence guarantees for asynchronous. SGD for distributed and federated learning. Advances Neural Information Processing Systems, 2022.
D. Kovalev, A. Beznosikov, F. Borodich, A. Gasnikov, and G. Scutari. Optimal gradient sliding and its application optimal distributed optimization under similarity, Advances in Neural Information Processing Systems, 35:33494-33507, 2022.
G. Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020.
Y. LeCun, C. Cortes, and C. Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://www..ccu.o.o/eeeeeeeeeeee 2, 2010.
10

---

L. Lei, C. Ju, J. Chen, and M. I. Jordan. Non-convex sinite-sum optimization via SCSG methods. Advances in Neural Information Processing Systems, 30, 2017.
Z. Li, H. Bao, X. Zhang, and Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pages 6286-6295. PMLR, 2021.
Z. Liu, X. Zhang, and J. Liu. Synthesis: A semi-asynchronous path-integrated stochastic gradient method for distributed learning in computing clusters. In Proceedings of the Twenty-Third Interna- tional Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 151-160, 2022.
S. Ma, R. Bassily, and M. Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern wer-paaametrized learning. In International Conference on Machine Learning, pages 3325 3334-3334. PMLR, 2018.
K. Mishchenko, Bach, M. Even, and B. Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances in Neural Information Processing Systems, 2022.
A. S. Nemirovskij and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley-Intersciene 1983.
Y. Nesterov. Lectures on conver optimization, volume 137. Springer, 2018.
L. Nguyen, P. H. Nguyen, M. Dijk, P. Richtárik, K. Scheinberg, and M. Takác. SGD and hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning, pages 3750-3758. PMLR, 2018.
I. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2613-2621. PMLR, 2017.
B. Recht, C. Re, S. Wright, and F. Niu. Hogwild!: A lock-frec approach to parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24, 2011.
J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola. Stochastic variance reduction for nonconvex optimization. In International Conference Machine Learning, pages 314-323. PMLR, 2016.
M. Schmidt and N. L. Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint 3rXiv:1308.63770 2013.
R. Szlendak, A. Tyurin, and P. Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. In International Conference on Learning Representations, 2021.
A. Tyurin and Richtárik. Optimal time complexities of parallel stochastic optimization methods under fixed computation model. Advances in Neural Information Processing Systems, 2023.
A. Tyurin, I.. Sun, K. Burlachenko, and P. Richtárik. Sharper rates and flexible framework for nonconvex sgd with client and data sampling. Transactions on Machine Learning Research, 2023.
A. Tyurin, M. Pozzi, I. Ilin, and P. Richtárik. Shadowheart SGD: Distributed asynchronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity. arXiv preprint 4rXiv:2402.04777
2024.
Z. Wang, K. Ji, Y. Zhou, Y. Liang, and V. Tarokh. SpiderBoost and momentum: Faster variance reduction algorithms. Advances in Neural Information Processing Systems, 32, 2019.
D. Zhou, P. Xu, and Q Gu. Stochastic nested variance reduction for nonconvex optimization. Journal of Machine Learning Research, 21(103):1-66 2020.
11

---

APPENDIX
Contents
1
Introduction
1.1 Assumptions
1.2 Gradient oracle complexities
1.3 Some previous time complexities
Contributions
3
The Design of the New Algorithm
Time Complexities and Convergence Rates
4.1
Optimal parameters S and p
4.2
Optimal parameters S and p in the large-scale regime
4.3
Discussion of the time complexity
4.4
Dynamic bounds
8
4.5
Comparison with previous strategies from Section 1.3
4.6
Comparison with existing asynchronous variance reduced methods
5
Lower Bound
Using the Developed Strategies in Other Methods
A Experiments
14
A.I Experiments with nonconvex quadratic optimization
14
A.2 Experiments with logistic regression
14
The Time Complexity Guarantees of Algorithms and
16
C The Time Complexity Guarantees of Algorithms 2 and 5
17
Proofs for Algorithm (Freya PAGE)
20
E Freya PAGE with Other Samplings
25
E.1 Nice sampling
26
E.2 Importance sampling
27
F Dynamic Bounds
27
G Examples
29
New Stochastic Gradient Method: Freya SGD
Setup of the Experiments from Section A.1
33
12

---

J Lower bound
34
J.1 Time multiple oracles protocol
34
J.2 The "worst case" function in the nonconvex world
................................
35
J.3 The first lower bound
36
J.4 The second lower bound
39
Useful Identities and Inequalities
42
13

---

A
Experiments
We compare Freya PAGE with Rennala SGD, Asynchronous SGD, and Soviet PAGE nonconvex quadratic optimization tasks and practical machine learning problems. The experiments were con- ducted in Python 3.8 with Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz. We developed library that emulates the working behavior of thousands of nodes.
A.1 Experiments with nonconvex quadratic optimization
10-1
10-
Rox't "xx"
5G20 SHip 8038125
Remrul 5CD 60 0.820125
Remmaa Sazt 120 Stip sinu EIS00S
Remadl Secx ds 120 Stip Mlsi 0.015925
Praye Skpp ane
maye
100000 200000 300000 400000 times (seconds)
500000
100000 200000 300000 400000 times (seconds)
500000
(a) 1000
10000
Figure 1: Experiments with nonconvex quadratic optimization tasks. We plot function suboptimality against elapsed time.
In the first set of experiments, compare the algorithms synthetic quadratic optimization task generated using the procedure from Section I. To ensure robust and fair comparison, we fix the performance of each worker and emulate our setup by assuming that the zM worker requires vi seconds calculate stochastic gradient. For each algorithm, we fine-tune the step size from the {2' E [-20, 20) }. Uniform sampling with replacement is used across all methods. In Freya PAGE, we set I / according to Theorem 7. We consider {1000, 10000} and in each case plot the best run of each method.
The results presented in Figure 1. It is evident that best convergence performance among all algorithms considered. The convergence behavior of Rennala SGD and Asynchronous SGD is very noisy, and both achieve lower accuracy than Freya PAGE. Furthermore, the gap between Freya PAGE and Soviet PAGE widens with increasing n because Soviet PAGE robust the presence of slow workers.
method, Freya PAGE, has the
A.2 Experiments with logistic regression
Table 2:
Mean and variance of algorithm accuracies the MNIST test set during the final 100K seconds of the experiments from Figure 2b.
Method
Accuracy
Variance of Accuracy
Asynchronous SGD
KKoloskova al., 2022]
92.60
5.85e-07
Mishhhhenko et al., 2022]
Soviet PAGE [Li al., 2021]
92.31
1.62e-07
Rennala SGD
92.37
3.12e-06
[Tyurin and Richtárik, 2023]
Freya PAGE
92.66
1.01e-07
14

---

Appddhonnu Sao dee 0,0083011
3x10
ALSCWERAA GOD AND EXMEROILE
baxt mowe Nis son 6-
28
famne 56B 22 323 Sop xon
28x
Al Aeradistar: da 120 stee 1iw
hays MAGE
226010
124
2
22x10-
22x10--
0.5
022
54
0.5
10:000 Z0P00 S0D0O abveds sunoed BOODO0 times (seconds)
times (seconds)
1e6
(a) 100
(b) 10000
Figure 2: Experiments with the logistic regression problem on the MNIST dataset.
We now consider the logistic regression problem on the MNIST dataset [LeCun al., 2010], where each algorithm samples one data point at a time. The results of the experiments are presented Figure 2. The difference between Freya PAGE and Rennala SGD/Asynchronous SGD is not as pronounced as in Section A.I: the methods have almost the same performance for this particular problem. However, our method still outperforms its competitors significantly better than Soviet PAGE.
low accuracy regime, and
critical disadvantage of Rennala SGD and Asynchronous SGD their noisy behavior, evident in both the plots and reflected in higher variance of the accuracy (see Table 2). In contrast, the iterations of Freya PAGE Figure 2 are smooth, and its accuracy exhibits the lowest variance, as shown in Table 2. This stability can be attributed to the ceriance-reduction nature of Freya PAGE.
15

---

B The Time Complexity Guarantees of Algorithms and 4
In addition to CompureBatchDifferenne (Algorithm 3) introduced in the main part, also analyze ComputeBatch (Algorithm 4) that is similar to ComputtBatchDifferencc,, but calculates a minibatch of stochastic gradients V (z) instead of stochastic gradient differences (z) Vf(().
Algorithm 4 ComputeBatch(S, 2)
1: Input: batch size S N, point R
2: Init g = 0 Rd
3: Broadcast
all workers
4: For each worker, sample j from [m] (uniformly) and ask to calculate (z)
5: for i-ri=1 =1 1, ..., do
6: Wait for fpp(z) from a worker
7:
+ 9 + S fp(z))
8: Sample j from [m] (uniformly) and ask this worker to calculate [z)())
9:
end for
10:
Return 0
Theorem 2. The time needed by Algorithm 3 to calculate g is at most
Σ 1=1 7
4 min JC(n)
(S 15+)))
(5)
seconds.
Proof. Let
(S +
min jE(n
As soon as some worker finishes calculating the stochastic gradient difference, it immediately starts computing the difference of the next pair. Hence, by the time t, all workers will have processed at least
t
2ti
pairs. Assume that
1
5 arg min jE(N]
(S (S+
Using Lemma 4, have / > 4rg for all j
Thus, we get L 27
2 for all j and
2T
2T
4T
im
-1
1
Σ
(S+
=S
4
We conclude that by the time (5), the algorithm will have calculated S pairs of stochastic gradients and exited the loop.
Theorem 11. The time needed by Algorithm calculate g is at most
2 min
(S + +
(13)
JE(n)
T
seconds.
16

---

Proof. The proof of this theorem is essentially the same as the proof of Theorem 2. The only difference that Algorithm 4 calculates (x)) instead of Vfi()) Vf(
C
The Time Complexity Guarantees of Algorithms 2 and 5
Instead of Algorithm 2, we analyze a more general Algorithm 5 that reduces Algorithm when
S = [m].
Algorithm 5 ComputteBachhAyySamiiigggg.... x))
1: Input: multiset S, point x E Rd
2: Init g
Rd multiset M
3: Broadcast æ to all workers
4: For each worker, sample j from S (uniformly) and ask it to calculate (z)())
5: while M & S do
6: Wait for (x)()) from worker
7: if E S M then
8:
g - g [ f
9:
Update M < (
end if
11: Sample j from S (uniformly) and ask this worker to calculate V (z)
end while
13:
Return [8
Σ (x(r)
RES
Theorem 12. The expected time needed by Algorithm calculate g
Σ
V is at most
[3|
iES
12 min
Σ T3
(IS) min[[S] n2 log (min{[S) . + +
(14)
JE(n]
seconds.
Proof Sketch: While the following proof is technical, the intuition and idea behind it and the algorithm are relatively simple. For simplicity, assume that 2 |S] The set M includes all indices that have not yet been calculated. Each worker is assigned the calculation of the gradient. At the beginning of the algorithm, when the set S is large, the probability that two workers are assigned the same index is very small. Hence, using the same idea as in the proof of Theorem 2, the workers will calculate zo |S] n stochastic gradients after
random index from S and starts
-1
R min JE(n]
(1S) - n +)
seconds. However, once the size of SYM becomes roughly equal to the probability that two workers sample the same index increases. In the final steps of the algorithm, we encounter the same issue as in the famous coupon collector's problem, resulting in additional factor of log because some stochastic gradients will calculated multiple times.
Proof. Let us define $ | and take any & E [nx]. We refer to the workers with the upper bounds т; such that 7; Tk "fast", and the others will be termed "slow".
Consider the moment when the algorithm samples j from the set S to allocate it to one of the "fast" workers (Line 4 or 11). The probability of sampling such that (z)(z) is currently being calculated by another "fast" worker is
Kindices from S'M taken by "fast" workers)
(indices from S taken by "fast" workers]| + (indices from S not taken by "fast" workers]
17

---

[, min S) + (indices from S S'M not taken by "fast" workers)]
because there are at most "fast" workers and at most distinct stochastic gradients. Let us define the set
U == (indices from S not taken by "fast" workers).
"fast" worker can be "unlucky" and start calculating stochastic gradient that is being computed by another "fast" worker. However, with probability at least
[in S} [4
it will take new index j that was not previously taken by another "fast" worker.
Thus, the while loop of the algorithm defines Markov process that begins with some U S S. The size uf decreases by one with probability at least min ( in iterations where the algorithm samples j from U4 and asks "fast" worker to calculate the stochastic gradient. Additionally, the size uf can decrease by one when a "slow" worker finishes calculating stochastic gradient from U.
Let be the time required for the Markov process to reach the state U = 0. Then, the while loop in Algorithm 2 will finish after most
T Th
(15)
seconds because once = 6, all non- non- con-processed indices from S S are assigned the "fast" workers, so calculating the remaining stochastic gradients will take at most seconds.
It remains to estimate T. Let V/p be the number of iterations of the while loop where the algorithm samples j from S and asks a "fast" worker to calculate the stochastic gradient when [21] = By
the definition of the Markov chain, we have
= =1+ min(k,
E [mpl S min min S)
(16)
because with probability at least min(k,,)+pp' one of the ("lucky") "fast" workers receives j from U and decreases the size of U by 1 (7p has geometric-like distribution).
Since 44] < S at the beginning of the while loop, it is sufficient for the "fast" workers to calculate at most
Σ hp 1)
stochastic gradients to ensure that 2 0 (it is possible that some stochastic gradients will be
calculated many times). Indeed, if [2| = p for the first moment, then after Vlp + calculations of stochastic gradients by the "fast" workers, the size of set will be at most p 1. The last "plus one" calculation can only happen when [ = 1.
The time required for the "fast" workers to process this number of stochastic gradients is at most
S
2
Up 1)
+ Tk.
T3
because for this choice of i', we have
1'
Up + 1),
T
where the number of stochastic gradients that worker can calculate in t' seconds. Taking expectation gives
E E = 2 Ts
E [mp + 11 + Tk
18

---

1
1
min
28
-h
P
min (n, 5}
2
2S +
+ 5k
8
mn, S}
min(n.5)
2
28 +
Σ
min S}
Σ
7h
P
p)
1=1
pmmmin
p=1
min(n.9)
2
Σ
35 + (n
Σ
+
Th
p
1=1
2
(3S + (n, + log (min (}))) + Tk
1=1
-1
10
(S + min S} log (min(n, S})) + Tk-
where we use the standard bound on the harmonic series. Thus, the expectation the total time (15) can be bounded by
-1
1
E
[T]
S
10
(S + mi, log (min(n,,{)) + -
i=1
-1
1
<
10
(S + min S} log (min(n, St) + k) + 2Tk.
where in the last line we add k 2 0. Recall that & is parameter we can choose. Let us take
-1
k: = arg min jEjD]
(S + min(n, log (min(n,,)) + j)
Using Lemma 4, we have
-1
The S min
(S + min(n, 8} log (min(n, 5}) + j)
/E(n
and hence
& 12 min jE[n]
Σ
(S + minfn, S} log (min(n, (n,n)))))))))) 5}) + +5)
19

---

D Proofs for Algorithm (Freya PAGE)
The proofs use the simplified notation t*(S) := (", (T|(1]) from Definition
Since the update rule of PAGE coincides with that of Freya PAGE, one can directly apply the iteration complexity results established in Tyurin et al. [2023].
Theorem (Iteration complexity). Let Assumptions 1, 2 and 3 hold. Consider any minibatch size
S N (1.2.... .,. any probability E (0, 1], and let the stepsize be LL- + L 1-p
Then, after
K 2 KPAGE: == 28
(T. + Tu
1-p
ps
iterations of Algorithm we have E [|V S where & is sampled uniformly random from the iterates {x=; p...,
Proof. The result follows from Theorem 6 of Tyurin et al. [2023], using the parameters from the "Uniform With Replacement" line Table of the same work.
Theorem 5 (Time complexity with free parameters p and S). Consider the assumptions and the parameters from Theorem 4, plus Assumption 4. The expected time complexity of Algorithm is at most
Tp, S.
(T.) 12 (m, (Tili=))
(8)
488
T._ TT- + L1
t (T))))))) (1 p) ( (m))))
x
(S
ps
Proof. The result established in Theorem says that the iteration complexity of the algorithm is
28 [
11
11-
KPAGE := E
L+V
pS
At each iteration, with probability p. workers compute differences of stochastic gradients, which by Theorem 2 takes
4 min jE(n]
(S +))
Tr
seconds. Otherwise, they collect the full gradient, which can be done (Theorem 1) in
12 min JEmn
(m min(m, n3 log (min(m,n)) + j)
< 24 min jE(n]
(m +
seconds, where the inequality uses Assumption 4. Hence, recalling the notation
Σ
(')) min _E(m)
(S (S+1))
the (expected) time complexity of the method is
T(p, S, [m]]])) 24t" (m) + 24KPAGE x (pt + (1 (S))
where the term (m) corresponds to the preprocessing step, when the algorithm needs to calculate 9d vf(x)) 1/m Σm fxx").
D
20

---

Theorem 13. Up to a constant factor. the time complexity T(p, S, [Ti from (8) is at least
80
{ _ (m)
(S))(((S)
El (m)
min
(17)
5
and attains this value with
1,
(_t(() s ( L
(S)
(*(
(18)
(())
otherwise.
[mm]
Proof. Up to a constant factor, by Theorem the time complexity of Freya PAGE is
80 (I- +
T(p,S, (Tllin)) == t" (m) +
p (pt (m) + - p)))
&
ps
Let us denote the second term in the above equation as Tp.s. Then for all p
1
we have
2'
80 -_ 1i2
8
Tp.s x
p PS
(pl (m) + (1 (1-p) (1-p)(((5)) 2 1" (m),
(19)
28
and for all 2
80 L sp 2 Otherwise, when p < 1/2 and S < 2. we have
pt (m) + +11 (1- p) min
Σ
j
-1
m
+ :))
80
(m).
E
jE[n]
2
2E
8
Tp.s 2
L- + L+
(m) +t)(s))
28
PS
8
(S) +
L+
(pt + (S))
23
2:
ps
8
80
L- (8)
(m)
28
pS
8
5"
t (m)
(S)
L+
28
S
Hence, up constant factor,
80
(m) vs
T(p, (. = (m) Tp.s 2 (m)
min L (m)( L+
can be easily verified that this bound can be attained (up to a constant factor) using the parameter as defined (18).
Theorem 14. Up to a constant factor, the minimum of the time complexities (8) and (17) is
8 min L_ (m), min SE(m)
/ (m)t*(S) (S)
(mm)
L_t + L+
VS
and is achieved for
/ [ (m))(()))
S* arg min min T_ I. SElm)
V8
and p² = (S*),, where p (S) defined in (18).
Proof. This is simple corollary of Theorem 13: take S that minimizes (17).
21

---

In certain scenarios, we can derive the optimal parameter values explicitly. Theorem 15.
L+ 1. I S L+ym S m, then (up to constants) S L parameters and
and p³
b+
are optimal
L-
L- /m
T(p', (mll = (m) + L t" [ILVI
2. 1f
L-ym 1.
< 1, then (up to constants) S = 1 and p¹ = 1/m are optimal parameters and
T(p", 5" (m)lie)) = (m) + 8 L
(1).
3. 1f La m
then (up to constants) p 1 is optimal parameter and
8 (m)
Twp", ,, [Ti]?=1)=
for any S E [m]]
Proof. We fist consider the case when n S
LAVi T_
& m. Since j S n S
LLvm
we have
1-
LtVm L_
L
L +
+
2
(20)
I. mm
L
and from the assumption that L- 2
Ltt. it follows that vm
Lt T.
L4V m T._
L
+
+
j
(21)
T.
for all j [n]. Thus,
-1
L7 [ ('(m) min
1
L+V
L
(20) 1
(Lemm
T. m JE(n]
T.
+
T. v
2
2"
1"
I
i=
and
-1
L 1- (m) min
(
[LLVm
I _mmmm))
L1
21) r-
(LeVm
L-vm jE(m)
L_
I.
It follows that
L+Vm b_
L+ - (m) 5t
(LVV
t"
(
(22)
I_ mm
Since L-
Livm < m, we have
(M()((())
(m))(())
min SElm]
(L(()) by
L min Se(m)
(S) + mm
VSS
v5
2L (m),
(23)
and thus, according to the result from Theorem 14, sufficient to minimize
(m)tt())
(-))) L+
VS
22

---

First, let us note that
c' Li L
m
1-1²
Livm T.-
+ L
L-
(m))t
L+V
1-
T vm
To_
(22)
L
I._
I.- V-v to
(" tt ( [Lav
1_
+ L
L--
L=vm L1
--
L+Vm
= 2
If S 2 Ltym then L-
(((m)(())
(LaVm
-(S)=I + L1
2 t_
S
L
Otherwise, S < L_
b- then
-1 (1 j
((S) = L-))) L1 (m)
min jE(n)
5)
(1 (1+
2 11 (m)
min iE(m]
L min
-1
L v m -_
+1))
L+ (mm)
L+ m jEln
To
T- 1' L
[LLV
-La (m)
L_
(22)
1
LLVM L
L-vm L.
(L+V Is
2 Tes
122""
1o
L LIVm"
L- (L+Vm)
-2""
Therefore, the optimal choice is S chosen to be
Lavi L_
and by Theorem 13 and inequality (23), p should
L LiVm m
t (m)
Using (22), we can conclude that p* L_ vm
1+
is optimal, proving the first part of the Theorem.
Next, consider the case when L m
< 1. By the reasoning above, it is sufficient to minimize
('(S) (())= L+ (M)
VS
First, let us note that
(m))((1)
(1)==--()) La Lavr(M) S [_
< (T),
m
where the last inequality follows from the fact that for any S E [m], (8)\s < ts (1). On the other hand, if S > 1, then
(s())((S)
= L2
2 L ( 2 (1).
VS
23

---

Therefore, the optimal choice is S = 1. Then
(f(m) + (1 (1- e())
[b_ + 17 D+Vm-1)
28
L
-- +
v m -1 1 (1)
Vm
48 L
(1),
while for any p
80
1-P p
L1
L
(pl + +1-
p
L
(pt + (1 - p))
8
8
8 (1))
8
Hence p" p== 1/m.
remains to prove the third result. Suppose that I_ follows from the fact that
Lx Vm
Then, the last part of the theorem
(((m)((() min L L2 SE(m)
(M(M)(()))
L min SE(m)
VS
VS
(t((m))
L+
vm
2 (m).
In practice, the values of smoothness constants are often unknown. However, the algorithm can still be run with close to optimal parameters.
Theorem 7 (Main result in the large-scale regime). Consider the assumptions and parameters from Theorem 4. plus Assumption 4. Up to a constant factor and smoothness constants, if /mm 2 then the optimal choice of parameters in (8) is S* /m and p* 1/vm. For this choice, the expected time complexity of Algorithm 1 is at most
T(//m, m. (Ta)it)) = 12/"(m, (T: ) + 1925" max ( (T
(10)
seconds. The iteration complexity with S [m and p 1/vm is KPACE 48 max(L__,L_)) 1/e.
Proof. The proof is the same as in Theorem 15. Indeed, up to a constant factor, the time complexity (8) can be bounded as
= (m)) + 8" I.- + Ta
(pl + (1 -1-1p) p))((s())))
ps
S 5 (m) + 280 max mL_
P ps
1
(pt" (m) + (1-p)t((S))
Therefore, by setting L = L_ in Theorem 15, one can easily derive the parameters p and S that are optimal up to the smoothness constants. The time complexity (10) can be obtained by applying S 5= [mm] and p 1/ym to (8).
24

---

E
Freya PAGE with Other Samplings
Algorithm be adapted to accommodate other sampling methods. This brings us the intro- duction of Algorithm 6, which supports virtually any sampling strategy, formalized by the following mapping:
Definition 16 (Sampling). A sampling is random mapping Ss. which takes as an input set of indices = {a,,..., Jm and returns a (multi)set {a....... 0ig ), where di E for all j E [S].
Algorithm 6 Freya PAGE (with virtually any sampling)
Parameters: starting point xº Rd learning rate y > 0, minibatch size S, sampling Ss. probability (0, 1], initialization g" = v fz using ComputeGradient((m) x²) (Alg. 2)
2: for 0, 1.......: K do
3: x++1 x² 7
4: Sample ck Bernoullipp)
5:
if c then
6:
V Vf(x*t)
ComputeGradient(2*1
(Alg. 2)
7:
g ++1
()(**t1)
8:
else
9:
Sample indices S = Ss([m])
10:
Σ [Vi((=++1) - vf((z*))
1ES
Compuuelacchiiieerrccyyyymaggggg (St x6+1 .zk)
(Alg. 7)
11:
g++ 9 Σ (vf(())))) Vf((x*))
iES
end if
13: end for
Algorithm 7 CompuuesSttiDfffrrrraa////nninn x,
1: Input: multiset S, points z, E Rd
2: Init g 0 Rd. multiset M /
3: Broadcast æ to all workers
4: For each worker, sample j from S (uniformly) and ask it to calculate (zf(2)) Vz)(
5: while M * S do
6: Wait for (x) fy((y) from worker
7: if E M then
8:
g+ IST (Vf((z) v)((w)
9: Update M < MUMMU {p)
10: end if
11: Sample j from S (uniformly) and ask this worker to calculate Vzz(2) V
12:
end while
13:
Return
TST
E (Vf((x) v((())) RES
The only difference is instead of ComputeBatchhifferenne (Algorithm 5), Algorithm uses a new subroutine, called ComputteattoDDiifeeennAAAASSaaaa
(Algorithm 3).
For this algorithm, we can prove the following time complexity guarantees. Theorem 17. The expected time needed by Algorithm 7 to calculate g is at most
(VS(()) - vA(())
EE
-1
24 min JEin]
Σ
(IS) + min([S] nn log (minf]S), n2) +
(24)
seconds.
25

---

Proof. The proof of this theorem is the same as the proof of Theorem 12. We only have to multi- ply (14) by because Algorithm 3 calculates (z) f(yy) instead of f(()).
While changing the sampling strategy might affect the iteration complexity of the method, for fixed minibatch size S, the time complexity of a single iteration remains unchanged. Thus, having established the expected time needed by the algorithm to perform a single iteration (i.e., collect minibatch of stochastic gradients of the required size), one can simply multiply it by the iteration complexity of the method determined for any supported sampling technique to obtain the resulting time complexity.
With this in mind, techniques: nice sampling and importance sampling. However, it can be analyzed with virtually any other unbiased sampling [Tyurin al., 2023].
analyse the time complexity of Algorithm 6 with different sampling
E.1
Nice sampling
Nice sampling returns a random subset of fixed cardinality S chosen uniformly from [m]. Unlike uniform sampling with replacement used in Algorithm which returns random multiset (that can include repetitions), the samples obtained by nice sampling are distinct. The iteration complexity of Algorithm with nice sampling is given by the following theorem.
Theorem 18 (Tyurin et al. [2023], Section 3). Let Assumptions 1, 2 and 3 hold. Choose minibatch size S E [m]) probability E (0, 1] and the stepsize
L_ L /
(1-p)(m-S) p(m-1)5
Then, the number of iteration needed by Algorithm 6 with nice sampling to reach an e-stationary point is
28
(1 -1- pm 5)
K
--
L+\
(25)
p(m 1)5
Proof.
The result follows from Theorem and Table from [Tyurin et al., 2023].
Theorem 19. Consider the assumptions and parameters from Theorem 18 and Assumption 4. Up to a constant factor, the time complexity of Algorithm 6 is
(I-
80
(1 - (1-p)(m p)(m S)
T(p, S. (Ti) (mm, [Ta]
T._ + T
x
p(m - 1)5
x (m, + 1' + mings, log (min( nz) (T]]_)) (26)
where to defined from Definition 3.
Remark 20. Compared Theorem 5, which uses uniform sampling with replacement, the guarantees
for nice sampling are slightly worse: the term (S, [T)) Theorem here is replaced with (S + min(5 (S, n) log (min(S,n)). [T Ignoring the logarithmic term log (min (8, n3) (5 log (min m, n,)),, the result from Theorem 19 is equivalent to that in Theorem 5. Thus, Theorems 6 and 7 hold also for the nice sampling (up logarithmic factors).
Proof. We the reasoning in the proof of Theorem 5. With probability p, the algorithm calculates the full gradients, which by Theorem requires
(m + minfm, n) log (minfm, n2)) + (1 =0))
min jE(n|
Σ
-1
Σ 1
- min jE(n]
(m + i)
Tz
26

---

seconds, where we use Assumption 4. With probability - p, the algorithm calls CatputeBatchDii- ferenceAnySampling which by Theorem 17 requires
-1 (S + min nJ log (min{S, n3) + j)
min jE[n]
seconds. One can obtain the result by multiplying the iteration complexity (25) by the expected time needed to collect the required number of stochastic gradients per iteration and adding the preprocessing time.
E.2
Importance sampling
Here additionally assume L--smoothness of the local objective functions fi- Assumption 5. The functions fq are L,-smooth. We denote L Eド= را and Luuax max4e(1] Li.
Importance sampling is sampling technique that returns a multiset of indices with repetitions. Index j is included in the multiset with probability E Toj
L;
Theorem 21 (Tyurin et al. [2023], Section 3). Let Assumptions I and 5 hold. Choose a minibatch size S E [m]. probability p E (0. 1] and the stepsize
1
L
ps
Then, the number of iteration needed by Algorithm with importance sampling to reach an e- stationary point is
28 E T +
P PS
(27)
The complexity (27) is nearly identical (7) and (25), with the only difference being the dependence on rather than L+. Thus, all the results up to constant and logarithmic factors can be derived using the same methodology as that outlined in Section 4, with the simple substitution of L with L.
Dynamic Bounds
As noted in Section 4.4, the results from Section D can be easily generalized iteration-dependent processing times.
Theorem 22. Consider the assumptions and the parameters from Theorem and Assumption Up to a constant factor, the time complexity of Freya PAGE (Algorithm 1) with iteration-ependde processing times {T+) which are defined Section 4. is at most
1
min JE(n]
(m +
TK-1.1
[KPace]
p min
Σ
(m+ + +11 min jefm)
Σ THe
(8+11)
JEin]
T+k
k=
(28)
to find an e-stationary point, where p E (0, and S N are free parameters, and Wa. permutation such that T S... Th. for all k 2 -1.
Remark 23. The theorem can be trivially extended to other samplings by changing KPACE to the iteration complexities from Theorems 18 and 21.
27

---

The reasoning behind this result is exactly the same as in the proof of Theorem 5. The only difference is that in this more general setting, the expected time per iteration varies across iterations. Therefore, instead of simply multiplying, one needs to sum over the iterations to obtain the total time complexity.
Proof.
We introduce the permutations to ensure that { H==1 are sorted. When 7, there is no need to introduce them because, throughout the paper, it is assumed 71 ... S Ta (see Section I))
28

---

G
Examples
Here we provide the proofs for the examples from Section 4.3. We will use the notation
t(S,j)
(S+
for fixed S [m]] and all j E [n].
Example 1. [Equally Fast Workers] Suppose that the upper bounds on the processing times are
equal, i.e., T3 T for all j [m]. Then
T(//m, mm, [T:]]=)) @ (7 max { m 1] + 8" max LL- L+]
(r
11)
max
Proof. First, when Ty for all [nx], then for any S [m], t(S,5) is minimized by taking
j = n:
Σ
(((s)
min ((S,j)
min jE(n]
(S
(8+1)
jE[n]
To
()) e mmxxx
{
S
11)
min
JE(M]
It remains to substitute this equality in (10).
Example 2. [Infinitely Fast Worker] Tf 0, then T(/vm, vm, [Ti][=]] 0.
Proof. The statement follows easily from the fact that for any S E [m]] we have
(*(S) min JE(n]
Σ
(S
s
1 Ti
-1
(S + j) 0.
Example 3. [Infinielly Slow Workers] !fT, = 0o Vjj E [n]. then T(//m, vm, [ri]i=]) oc.
Proof. This follows from the fact that for any S E [m]] and any j E [n]] we have
((S.))==
(S oc.
To
Example 4. (Extremely Slow Workers] Suppose that the times T < 00 are fixed Vj S jB and
Tj 2 B > jB for some B large enough. Then T(/ vm, [T)) = T(//m, v m. (2)))1))
Proof. Suppose that B >
miis E/8
and fix any k jB. Then, since Tj 2 B for all js, we have
k jB
k jB
m + jB
S + jB = =((Sjis)
B
>
E
jB
-
for any S E [m]. Rearranging and adding (S + jB) Σ 1= obtain
to both sides of the inequality, we
ju
k Σ
ja
ju
(S +jn)
Σ
+ + + jn)
< (S (S jB)
Σ
+ (k - j8)
Σ
jj
i=1
29

---

meaning that
5 jB Σ 7
S+
(())
t(S,k)
Σ 2i=1
for any k > jB and any S E [m]. Therefore,
-1
1 T3
min jeIn]
Σ
(S +)
min jelil
Σ i=
(S
(S+1)
for any S E [m], which proves the claim.
30

---

H A New Stochastic Gradient Method: Freya SGD
In this section, introduce non-variance reduced SGD method that call Freya SGD. Freya SGD is closely aligned with Rennala SGD [Tyurin and Richtárik, 2023], but Freya SGD does not require the bo-uddd variance assumption on stochastic gradients.
Algorithm 8 Freya SGD
1: Parameters: starting point x² E R learning rate 7 >> O, minibatch size
2: for k O.......K K
do
3:
5 Σ Vii(a")
ComputeBatch(S,
(Alg. 4)
EES
4: xk+1 x² 7
Σ Vf((**)
SES*
5: end for
(note): S* a set size | = S of i.i.d. indices sampled from [m] uniformly with replacement
Assumption 6. For all E [n], there exists f such that f((x) 2 St for all Rdd
We define
A
EF-
Theorem 24. Let Assumptions 1, 5 and hold. Choose minibatch size [m]] and stepsize
VS
1 Se
7 min
[L K SGD
L ))
4L.max A
where
126
1
4Lmax 12
KSGD
S'
Se
Se
Then, the number of iterations needed by Algorithm reach an e-stationary point [KsGD]-
Proof. The iteration complexity can be proved using Corollary 1 and Proposition 3 (i) of Khaled and Richtárik [2022] (with 4 = 1/n).
Theorem 25. Consider the assumptions and the parameters from Theorem 24. Up constant factor, the time complexity of Freya SGD (Algorithm 8) is at most
(S (T.
8
(1
1
Liax 5S
(8" + +1a)
min jEin]
(S +
5
T
i=
and is minimized by choosing
Lmax (8 A*)
S*
Up to a constant factor, we gel
-1
8 min Je(n)
Lmax (50 (0+ ((+)))+))}
TS [Til
Proof. At each iteration, the algorithm needs collect minibatch of stochastic gradients of size S. Multiplying the iteration complexity of Theorem 24 by the time needed to gather such a minibatch (Theorem I1), the resulting time complexity is
(11 [
TSGD (T]](t] =
1
+
Lmax (80 + (60
+2-))
min jE(n]
(S (s+1)
E
31

---

We now find the optimal S. Assume first that fmax (6 + + 2. Assumption 5 ensures that the
function ʃ is -mmx-hh Thus, we have || < 2Lmaxod S e, and x is an e-solution.
Therefore, we can take any 5 2 1.
Now, suppose that Lemase (50 + A*) 2.
Then we have
L_
1
1
Linxx (60 (++))) +3) ))
TsoD(Lmox/e (6 + +1") [Ta]
2
min
E
5
jEin]
E
-1
28 レー
Lmax (d + A*) + )
min jE(n)
8
T3
For all S > max { [max (50 + a0), .1],
we get S 2 2 and hence
=
1 -1 (S+
TsaD (S (0.(((].)1111 (r)l==)==
80L_
1
Lmax
(8 + )))
min jE(n]
Σ c-1 T3
E
s
ES
-1
8
1
min
(S (5)
28
jE(n
T
i=1
-1
8 min
1
Imma (50 + +1' :))
2=
jE(n]
To
Let us now consider the case <<< S S max { Lmmxs (80 )-) 13 We can additionally assume
that Lrnax (60 + A-) > and S < Linxx (8u. + A (otherwise, the set S that satisfies the condition
1 < S < max Luuax (0" + A+) 1) is empty). We get
1 -1 T3
TSGD (5, [T=]
8 Lー (1
1
+
Lmax (5 + +A²))
(6'+
min jE(n)
Σ
(8 (8+
8
5
ES
801 T__
Tmmax
(50 + +a')
min jEin]
j Σ Ts
(S + 1)
8
ES
8 L
1
Liaxx
Limax (6 + )7
min
(60 + A*) + j
8
%E(n]
Ti
8
5S
L
1
Limxx
(50 (00 +
+
min
jE[n]
Ti
E
Finally, for S = 1, we have
-1
L Lmax
Σ #
TsGD (5, [T]]
(80 + A
min
(1 (1+1))
6²
jE(m)
7.
min
Σ i=1 Ts
Tamax
+ (5+ + Trmax
(50 (8+
jE
E
-1 Limax (80 +++)++)
L
min
2s
jE(n]
because we assume
Lrmax (80 + +*) >
1
Therefore, an optimal choice is S* Lmaa (60 + +A').
2.
32

---

I Setup of the Experiments from Section A.1
We consider the optimization problem (1) with nonconvex quadratic functions. The matrices and vectors defining the objective functions fi are generated using Algorithm 9 with m 10000, 1000, 1c-6, and 10. The output is used construct
1 T A, - b/ E Rd Vi E [m). [(x)) N"
Algorithm 9 Quadratic optimization task generation
1: Parameters: number of functions m, dimension d, regularizer X, noise scale
2: for = 1,...,,7.. do
3: Generate random noises o = 1 + sC} and Up = sEP, i.i.d. 62 ~ (0)
4: Let (-1 v 0, ......... 0) E Rd
5: Take the initial tridiagonal matrix
2
o A;
-1
Raxd
4
-1
0
-1
2
6:
end for
7: Take the mean of matrices A
ii=1 A;
8: Find the minimum eigenvalue Amnin (A)
9: for i 1, ................................ do
10: Update matrix A; = A; + (A Amin (A))I
end for
12: Take starting point _. = (vd.0.....
Output: matrices A 1.. Am vectors b,, bys starting point σ0
33

---

Lower bound
J.1 Time multiple oracles protocol
The classical lower bound frameworks [Nemirovskij and Yudin, 1983, Carmon et al., 2020, Arjevani al., 2022, Nesterov, 2018] are not convenient in the analysis of parallel algorithms since they designed to estimate lower bounds on iteration complexities. In order to obtain time complexity lower bounds, we use the framework by Tyurin and Richtárik [2023]. Let us briefly explain the main idea. A more detailed explanation can be found in [Tyurin and Richtárik, 2023][Sections 3-6].
We start by introducing an appropriate oracle for our setup:
O
R R200
Rd
(R>0 x R {0,1)) +
R2 x R x {0, 11) xR"
time
point
input state
output state
(tt,,,
0).
Sq = 0,
such that
Or(1, (8,, 8z, 8q))
(2, 1).
0). 8q = 1, < 8t +
(29)
(0,,0,0,
(s*))))),
Sq = L, 8t +
where j ~ Uniform ([ml), m,mn),,, i.e., j is a random index sampled uniformly from the set [m]. We assume that all draws from Uniform([rne (Im]) are i.i.d.
Next, we define the time multiple oracles protocol, first introduced in [Tyurin and Richtárik, 2023].
Protocol 10 Time Multiple Oracles Protocol
1: Input: function f = 1 >m Si, oracles and distributions (O,,..., On. E O(), algorithm
A E A
2: sf = f all i E [n]
3: for ==
D0 do
4: (th+1 juti ) = (g)
.'), Set
D + > th
5: (s/tt), gh+l = Oct (th+1 x (b+1)
D 5 k+1
= s Vj + th+
6: end for
Let us explain the behavior of the protocol. At each iteration, the algorithm A returns three outputs, based on the available information/gradients: time ph-1, the index of a worker g++1, and a new point 2 Depending the current time t*+1 and the state of the worker, three options are possible (see (29)). 8g = O, then the worker is idle. It then starts calculations at the point x², changes the state s, from 0 to 1, stores the point x² in Sar (at which a new stochastic gradient should be calculated), and returns a zero vector. sg = O and + < 8t + т, then the worker is still calculating stochastic gradient. It does not change the state and returns zero vector because the computation has not finished yet. If sy = 0 and +++1 2 8 + т, the worker can finally return a stochastic gradient 8, because sufficient time has passed since the worker was idle (s, = 0). Note that with this oracle, the algorithm will never receive the first stochastic gradient before time r (assuming that all oracles have the same processing time t; in general, we will assume that the processing times different).
In the setting considered in this work, there are n oracles that can do calculations in parallel, and an algorithm orchestrates their work. Let the processing times of the oracles be equal to Ti...., Tn. A reasonable strategy would be to call each oracle with & = 0, then to call the fastest worker with possible, then to call this worker again
th minig[m] 7; get the first stochastic gradients with ** min,g (n] 7; to request calculation of the next stochastic gradient, and so on. One unusual thing about this protocol is that the algorithm controls the time. The oracle is designed to force the algorithm to increase the time; otherwise, the algorithm would not receive new information about the function.
Our goal will be bound the complexity measure Miime (A, defined
maime (A, = inf sup sup inf t 2 0
inf |f
seJ.
AEA SEF (O,)E(())
RES.
(30)
S E Nolt* st),
34

---

where the sequences th and x are generated by Protocol 10. Hence, unlike the classical approach, where the lower bounds are obtained for the minimum number of iterations required find an e-stationary point, we seek to find the minimum time needed to get an e-stationary point.
We consider standard for setup class of functions [Fang et al., 2018]:
Definition 26 (Function Class F $0.4+ ). We say that E F 80, L inlzeR" (a) S 8 and
if it is bo-uoddde,, i.e., ʃ(0)
[(x) -x)== - f(())
where the functions f Rd IR are differentiable and satisfy
V/(x)) v - 1 I| y/l²
Vx, E Rd.
Next, we define the class of algorithms we will analyze. Definition 27 (Algorithm Class Ar). Let us consider Protocol 10. We say that sequence of K== is zero-respecting algorithm, if
mappings A = {
1. A Rd ... R
R20 N Rd for all k 2 1 and A" E Xx
times
2. For all and gt ..... g E BR gk+1 > 1t where p411 and th defined as (Ikt1....) ( ge) and ((.....)=
3. supp (x*) UJ supp (I') for ls E No, where supp(x) = {i E [d] M # 0).
We denote the of all algorithms with these properties as Az.
In the above definition, property defines the domain of the mappings A and property 2 ensures that our algorithm does not "cheat" and does not "travel into the past": the time can only go forward (see (TTyurin and Richtárik, 2023][Section 4, Definition 4.1 Property is standard assumption for zero-respecting algorithms [Arjevani et al., 2022] that satisfied by virtually all algorithms, including Adam [Kingma and Ba, 2015], SGD, PAGE [Li et al., 2021] and Asynchronous SGD.
remains to define an oracle class for our problem that employs oracles from (29). We design oracles that emulate the real behavior of the workers.
Definition 28 (Computation Oracle Class O. For any f F ,4, the oracle class Og..... returns oracles O = Oz,, i [n], where the mappings O,, are defined in (29).
).
J.2 The "worst case" function in the nonconvex world
The analysis uses standard function, commonly employed to derive lower bounds in the nonconvex regime. First, let us define
prog(z) max i 2 0 24 0}
(xo 1).
Our choice of the underlying function F follows the construction introduced in Carmon et al. [2020). Arjevani al. [2022]: for any T E N, define
Fr(x) == : -1)) + Σ 10 ((z)-1)(<z))),
(31)
where
0,
x S 1/2,
and ((x) Ve J 3 di
v(x) exp (1 ---)-11
x 2 1/2,
Throughout the proof, only rely on the following properties of the function:
35

---

The sequences x and th are defined in Lemma (Carmon et al. [2020], Arjevani et al. [2022]). The function Fr satisfies:
Pr( zeR Pr(x) S A where A 12.
2. The function Fr is 4msmooth, where 4 = 152.
3. For all x E R², / S Yoo: where "Yoo = 23.
4. For all x E R", prog (x)())) S prog(2) (z) + 1.
5. For all x ERR if prog(()) x) < T, then V (x)ll)) > 1.
J.3 The first lower bound
We are ready to present the main results of this section.
Theorem 29, Let us consider Protocol 10. Without loss of generality, assume that 0 < T1 S ... S Tn and take any L4.8
and m N such that C10+60 and LL o2ym. Then, for any algorithm E Ar, there exists a function f E F ,4, and computation oracles (O1,..., ,,) E
O ORLmnTTa (f) such that E infnee, [++{
E, where St ={k No th S { and
-1
L min JEIn]
(m +i++j)
c3 x
Vine
The quantities C1,02, and 03 are universal constants. Protocol 10.
Proof. (Step 1: Construction of a hard problem) We start our proof by constructing an appropriate function f E F L. Let fix any T 2 and define f+ IR. R such that
VmLL422 12
h:=
Fr
for all RT. and fe(x) 0 for all i (2,...,ml m) and E R.. Essentially, all information about the function f = Ee fa is in the first function. Note that
1
( V((0))
(f(()) - (1)l1
1
1 VmL
VFT
Fr 5
m
11
4
1
VFT
(
V (2) l|
Then, using Lemma 1, we have
-
< 22
T
-
L3 - =11²
(32)
Taking
1
T
1.
we ensure that
1 [VmL+X² X2
v VmL_X X2
f(0) - inf f(x)
FT (0)
inf ZERT
Fr(())
xER?
m
1
11
36

---

L4
L4 S 8000
Pr (0)
inf Pr (x)) aERz
(33)
mmh
v mml
where in the inequalities we Lemma and the choice of T. Now, inequalities (32) and (33) imply
that f = Li Si E F ,, and hence, using Lemma again, we get
1
VmL+
inf RES!
inf
FFT
KESt
m
41
L 12
L
inf REST
FF
inf 1 [prog(=*) < <T] kest
ml}
ml
Let us take
211 MIVE
1.+
Then
inf [/<>>>>||
4s inf 1 [prog(=*)< <T] kEst
(34)
BESt
and
8 L+
T
A mm
The last inequality means that while prog(x** T for all k E St. all gradients are large. The function Fr a zero-chain: due to Lemma we know that prog(VPr(z)) S prog - for E RR. This implies that we can discover at most one new non-zero coordinate by calculating the gradient of the function V f1. Since the algorithm A E Az is zero-respecting, by definition it cannot return point z² with progress greater than that of the vectors returned by the oracles. In view of this, it is necessary to calculate the gradient of fi at least times to get prog(x") 2 T.
The gradient of f1 can be calculated if and only if j = 1, where j ~ Uniform((m) [m]) (see (29)). Consider worker i and define n!! be the number of draws from Uniform(mm]] until the index j = sampled. Clearly, nf! is Geometric random variable with parameter P (j 1) 1. Recall that the workers can do the computations in parallel, and by the design of the oracles, worker needs least ram! seconds calculate n stochastic gradients. Hence, it is impossible calculate V. before the time
min T.
Once the algorithm calculates fi for the first time, needs to do at least T times more to achieve prog(=*) 2 T. Thus, one should wait at least
min T.l.
seconds, where of iid. Geometric(/mm).
We can conclude that
PP
inf 1 [prog (x*) < =0) KESt
SP TP
Σ
min गHk
(35)
EE|m
(Step 2: The Chernoff Method) The theorem's proof is now reduced to the analysis of the concentration of El= mingej) T. Using the Chernoff method, for all O. we have
IP Σ
min Ten St) El(l
min
tein
Er min T. 2 E ES)
e
37

---

T
S
E
exp
8
min iE|m
Independence gives
T
T
T. ]
P
min
T.
* St
S es
II E
exp
min se(n]
<E(n)
h=1
iid.
(E
[exp
(-s
-sii
min Tan!
))
(36)
kE(n)
Let us consider the term in the last bracket separately. For fixed t' 0, we have
min Tmm! ]
E
exp
(37)
VE(x)
max exp (-s7mn!) se(n]
E
E
max (1 [गeा)] V =1] exp (-STAnt) + (1- - [r(r s (T] exp (-sTat)) xE(n]
E
max (1
[ran]] $ =t] (1
[Tan] S {t) exp (- ssst)))
[E(m]]
exp (-s(') + (1 exp (-
max (1 (E(x)
[Tank S (1)
(38)
We now consider the last term. Due to the independence, we have
E max LE(n]
(1 [ran] s ('])
II
(Ten) ()) =1 (1 (1-
i=1
where we use the cumulative distribution function of geometric random variable and temporarily define p = L. Using Lemma 3, we get
E max (1 [Tan mE
StT)
Sp
(39)
Let us take
6'
min jE(n)
Σ
j
min g())
p
jE(n)
where I())= = EE 1 that minje(m) r(o) = "(""). Then, Lemma 4 gives
+
for all j E [n] and assume that j is the largest index such
7.
p
Ty. 5 min s(i) +1 jE
(40)
where we let Ta+1 = cc. Therefore, l' < Tz and (39) gives
S -
L T S <ti)
E max
(E(m)
Using (40), we get obtain
87:
2 8
1 for all $ j Since |
S 2x
1 for
all x
2
1
8, we
5'
E
max (1
[Tant S st])
<p
Σ
21'
= 2pt'
pj
(e(n)
T 4
4
i=1
38

---

1'
= 2p x
Σ
+
x
Σ
1
pj
p
T3
4
1=1
(1 + +5
pj
1
4 P
4
4'
Substituting the last inequality to (38) gives
)]
1
E
exp
min
T.mb
S exp st') 41( 11 exp(-st)).
We now take 1/1 to obtain
] se++ (1 () se
E
exp
- min Tm
xe(n]
Substituting this inequality in (35) and (36) gives
inf 1 |prog(x*) KEst
< T| =0) S
min Tank st S se - icinl
k=
Therefore,
inf 1 [prog(=*) <T] =0) sp p
IP
kESt
for all
T
t min jE(m
log p
8
2
and p 0. Using the bound on the probability with p and (34), finally conclude
inf RES
4sP
inf 1 parog(=*) < = 1 2 2: KESt
for all
(1 +
T
t x min
Σ T3
2
+ log
8 jE(n)
D
1 min
Σ To
1
L
1
(m 5)
+ log
8 jE[n
2
4 A Vms
It remains to use the conditions proof.
L8 and d²
cavm from the theorem finish the
J.4 The second lower bound
Theorem 30. Let us consider Protocol 10. Without loss of generality. assume that 0 < S ... S Tn and take any 14,80 > O, and m E N such that E < L4 Then, for any algorithm A E Aa, On)) E O...... (f) such that
there exists function E Fm 80, and computation oracles
infkes,
> E, where St = {k E No 1 <t} and
1 = C2 X min
(m + j).
JE(n]
The quantities e₁ and 0g universal constants. The sequences x² and th are defined in Protocol 10.
39

---

Proof.
We use the same construction as in the proof of Theorem of Li et al. [2021]. Let us consider
f((x) = c (0;, x)
|
(41)
2
for x E IRT where E R and in E TR. E [n] are parameters that we define later. Then
[V)((a)
v fi(())l - L3 1
yl1
m
for all y E Rd and
2
1 m
L
c²
m
f(0) inf f(x) =
#ERr
inf SERR
m
U/ 20
+
| ?
2L 2
Σ
U/
=
8
1=1
where we take
2 m2
E vzll
Thus, we have f == 1 E1 Ji E FM
Now, let
1,0, 0)T E ERT
02 (0,
0, 1, ......0) 0) E R
03 (0, 0. 0,
0 .......) E R.
On (0, ...,,
ERT
and choose any T E {sm 8 E N) (one can always take T = m). Then
22
c=V
T
Let fix some time / > 0 to be determined later and recall that the workers can calculate the stochastic gradients V fz) = cu, + L+ in parallel. Suppose that up to time t, fewer than m stochastic gradients have been computed, Then, since the algorithm is zero-respecting algorithm, cannot have discovered more than in to and
2
2 x T
2 coordinates. Thus, at least o coordinates are equal
[1
Σ
Lack
T
U1
m
2
for all k E f No | | <t. Therefore, substituting our choice of c and using the assumptions from the theorem, we get
L4800 2E.
(42)
It remains to find the time t 0. The workers work in parallel, in seconds they caleulate most
40

---

stochastic gradients, Now, let
-1 (m + j),
min 8 jEjN
Σ
(43)
and define g(i) = (E/=) 1/2
(m + j) for all j E [n]. Assume that j" is the largest index such
that minje(M) ((i) = g(j"). Using Lemma 4, we have
Since 1 2 for all i S and [x] 7i
s 2x 1 for all x 2 g we obtain
f
2t
5 Ti
4"
Ti
Therefore, it is possible calculate most 4 stochastic gradient in time (43) and we can finally conclude that inequality (42) holds for any time that is less than or equal (43).
41

---

K Useful Identities and Inequalities
Lemma 2 ([Szlendak et al., 2021J). It holds that L- S Lt, L- S 1 [ < 12_ S - Lz
m E Le and L33 12 S
Lemma 3. Consider sequence 4 Qn 10, 11. Then
II (1 qm) m=l
qm
PP
Proof. We prove the result by induction. It is clearly for 1: Em Qm
Im== (1 qm). Now, assume that that it holds for n - 1, meaning that
Qm
(1 Qm)
m=1
m=1
Multiplying both sides of the inequality by 1 - On E [0, 1] gives
II (1 4m) 2 (1 (n) (1
n-1
pm
= Σ
4m
In + In
Σ
4m
2
Im
m=1
m=1
m=1
m=1
m=l
since 9m E [0, 1] for all m E [n].
Theorem 31. Let us consider the equilibrium time mapping from Definition 3. Then
1. (S, (m) < 2n max 1
2. (S, (T))))) S 2n max {S, 1]
for all S 2 0, Ts [0, oo) for all E [m], and S ... S Tu
Remark 32. Assume that T1 = Tn-1 = T and Tn + 00, then
S
S n-
lim (S, (T)))) (S, (+ = 11
+ 1
S max
1
To 700
n
S
lim 2nn max Tu +00
1 -00
and
lim 2T max {8 27 max {S,
Thus, (T))))) can be arbitrarily smaller than 2T, max { S 1} and 2T max {S, 1}. This im- plies that our new complexities (9) and (10) can be arbitrarily better than Tsovict PAGE and T Heso PAGE-
Lemma 4, Consider sequence 0 ... Tn and fix some S > 0. For all [n], define
(S 5).
1. Let Jinnx be the largest index such that min g(i) = g(imaxx) For Imax n, we have
5E(m]
min
9(i) < T(jama +1)-
jE(m]
2. Let j be any index such that min g(i) = g(r"), ). For j < n, we have
JE(m
min g(i) S -(--
jE(n]
42

---

3. Let min be the smallest index such that min ( = mima) Then
jEIn]
min g(i).
7
jEin
4. Let be any index such that min g(i) g(j"). Then
je(n
T
S min g(i).
jE(m
Proof. We first prove the first inequality. Suppose that Jmax n. Then g(mma) < Dimax + 1), meaning that
+1
1
Σ
(S + Jmax)
(S + Jmax + 1).
This implies the following series of inequalities:
Imax
Juns
Σ
(S + Imax) <
Σ
(S + Fmax + 1)
Imnx
1
(S Finax)
T(inax +1)
Ti
Juma
(S + fmax) = Fm(x)))) min g(i).
T(jmax +1)
jC(n]
The proof of the second inequality the same, but with non-strict inequalities. To prove the third inequality, first suppose that Jumn 1. Then g(iii)) Tjmm (S 1) Tyan needed. On the other hand, Juin implies
g(imiu) < Aiiii 1)
-1
Jmin
Jmin
(S + Jmin)
(S jmin
Ti
Ti
Juin 1
Juni
1
(S + Jmin)
Σ
(8 + Jiin 1)
Ti
i=1
Jmin
(S + Fminn
Timm
-1
Jimi
Tja
Σ
(S jimm) min g(j).
mm
Ts
jEin]
The proof of the fourth inequality is the same, but with non-strict inequalities.
43

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sections 4 and 5, Table 1
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Sections 3, 4.1, and 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
44

---

Justification:
Sections 1.1, 4, and the appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section A
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
45

---

Answer:
[Yes]
Justification:
In the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/nips. wwtppcccccc/ccccccccccccccccclct httpa//guuiee//eeSuuiiiieeeeee /Coo///oomissssseeeee momiisssoooolyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Section A
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide two plots for each algorithm to ensure the soundness of experiments. We also calculate the variance accuracies in Table 2.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
46

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section A
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https htt////nuripppp wwwpurip..ccpppllllpe http//ullic/thhcsssiiiieeceeeeee
Answer: [Yes]
Justification: We have thoroughly reviewed the code of ethics and we can confidently state that our paper is fully compliant with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Our paper considers a mathematical topic.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
47

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Section A
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
48

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
In the supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "2QP9f91915", "reviewer": "Reviewer_MLsi", "summary": "This paper considers the problem of minimizing a finite sum of non-convex objective terms with multiple computational units that calculate gradient oracles. It introduces two efficient computational subroutines for the main steps of the PAGE algorithm, and provides novel bounds on the real time of computation assuming a heterogeneous computational scenario. For this, the paper gives bounds on the execution time of these subroutines and combines them with the previously known iteration complexity of PAGE. Next, the paper considers multiple variations: it optimizes the hyperparameters of the PAGE algorithm in different regimes, and also extends the results to a dynamic scenario. Finally, it provides a lower bound on the overall execution time and in this way establishes that their strategy is optimal in large-scale regimes.", "questions": "Compared to the results in the appendix, the stated theorems are generally simplified for better comprehension, but some confusion is also introduced. In particular, I am not sure which results are deterministic and which results are in terms of statistical expectation or high-probability. Could you clarify? \n\nIn the statement of Theorem 4, you assume two bounds on m, where one of them seem to be stronger than the other. Why do you keep both?", "limitations": "No limitations or potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and has an excellent presentation of the subject. It provides an extensive theoretical study of a novel gradient management strategy in the PAGE algorithms, and achieves tight bounds on the convergence rate.", "weaknesses": "I do not have any major concern about this work. The only limitation for me is that from a practical standpoint, this algorithm might not be optimal as it may introduce a significantly higher communication overhead. This is because each gradient is now required to be sent in an individual message.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and appreciating the strengths of our work. We would like to address your comments and provide additional explanations.\n\n__Weaknesses__\n\n> The only limitation for me is that from a practical standpoint, this algorithm might not be optimal as it may introduce a significantly higher communication overhead. This is because each gradient is now required to be sent in an individual message.\n\nNotice that it is possible to avoid sending an individual message for each computed gradient. As noted under Algorithms 1 and 2, _the workers can aggregate $\\nabla f_p$ locally, and the algorithm can call AllReduce once to collect all calculated gradients_. While, indeed, the current listings of Algorithms 1 and 2 require the workers to send individual gradients, this strategy can be slightly improved. We can ask the workers to aggregate the gradients locally and send these aggregated vectors at the end of Algorithms 1 and 2. This simple modification can significantly reduce the communication overhead.\n\nIt is possible to improve the communication complexity of the algorithm even further, e.g., through compression techniques. It is a research direction that deserves a separate study. We therefore leave this topic for future work.\n\n__Questions__\n\n> Compared to the results in the appendix, the stated theorems are generally simplified for better comprehension, but some confusion is also introduced. In particular, I am not sure which results are deterministic and which results are in terms of statistical expectation or high-probability.\n\nThe algorithms presented in Algorithms 1, 2, and 3 are all stochastic in nature, which means that the complexity results are not deterministic. The iteration complexities (Theorem 4) are derived in terms of the expected number of iterations needed to find an $\\varepsilon$-stationary point. Similarly, Theorems 1 and 2 describe the expected time required to compute the relevant quantities (hence the term 'expected' in Theorem 1; this word is indeed omitted in some other results - we will correct this oversight in the revised version of the paper). The time complexities outlined in Theorems 5, 6, 7, and 8 are based on expected iteration complexities, and thus are also non-deterministic. Thank you for pointing this out, we will make the adjustments in the paper.\n\n> In the statement of Theorem 4, you assume two bounds on m, where one of them seem to be stronger than the other. Why do you keep both?\n\nWe believe that the reviewer is referring to Theorem 7 (as there are no bounds on $m$ in Theorem 4; please correct us if a different result was meant). The result in Theorem 7 states that $S^* = \\lceil\\sqrt{m}\\rceil$ and $p^* = 1/\\sqrt{m}$ are the optimal parameters when $\\sqrt{m}\\geq n$. The inequality $m \\geq n\\log n$ comes from Assumption 4, and does not need to be included. Thank you for pointing this out.\n\n---\n\nWe are grateful for the valuable feedback and trust that our responses have satisfactorily addressed the reviewer's concerns. Please let us know if more details or clarifications are needed.", "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": "ZkluuS9fdW", "reviewer": "Reviewer_QBDK", "summary": "The paper introduces Freya PAGE, a new parallel method for large-scale nonconvex finite-sum optimization in heterogeneous and asynchronous computational environments. Freya PAGE, specifically addresses the variability in processing times across different workers due to hardware and network differences. By being robust to \"stragglers\" and adaptively ignoring slow computations, Freya PAGE  improves time complexity guarantees compared to existing methods. Additionally, the paper proves a lower bound for smooth nonconvex finite-sum problems in asynchronous setups.", "questions": "If you have tested Freya PAGE in real-world scenarios, can you share the results and insights?\nHow does Freya PAGE specifically determine which computations to ignore or adaptively manage in the presence of stragglers? Can this mechanism be fine-tuned for different distributed system configurations?", "limitations": "The performance of Freya PAGE might vary significantly with different configurations of worker speeds and hardware setups. This variance could be problematic in environments with highly variable computational resources.\nThe impact of communication overhead in distributed systems with significant network latency, is not extensively discussed.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Freya PAGE is a novel parallel optimization method specifically designed to handle heterogeneous and asynchronous computations. This appears to be a significant advancement and addresses real-world challenges in distributed systems. By addressing the variability in processing times across different workers due to hardware and network differences, the method is highly relevant to practical distributed systems used in large-scale machine learning tasks. This method shows improved time complexity guarantees compared to existing methods. The paper also provides a strong theoretical framework in general. Specifically, proving lower bound for smooth nonconvex finite-sum problems in asynchronous setups shows the optimality of Freya PAGE in large-scale regimes. The stochastic gradient collection strategies ComputeGradient and ComputeBatchDifference introduced in this paper is innovative. Overall, this is a very well written paper and easy to follow and understand.", "weaknesses": "The empirical results of this paper are primarily focused on synthetic quadratic optimization tasks and logistic regression problems. More diverse and extensive experimentation on a wider range of real-world datasets and applications would strengthen the practical validation. \n\nThe algorithm's performance might vary significantly for different configurations of worker speeds and hardware setups. The variance in performance could be an issue in highly dynamic environments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and for recognizing the strengths of our work. We would like to address each of your comments and provide clarifications.\n\n__Weaknesses__\n\n> The empirical results of this paper are primarily focused on synthetic quadratic optimization tasks and logistic regression problems. More diverse and extensive experimentation on a wider range of real-world datasets and applications would strengthen the practical validation.\n\nWe thank the reviewer for the suggestion. Given the theoretical nature of our work, our primary focus was not on extensive experimental validation. The empirical results included were meant to demonstrate that our theoretical findings align closely with practical observations, underscoring the robustness of our theoretical framework. Nevertheless, we are open to incorporating additional experimental results.\n\n> The algorithm's performance might vary significantly for different configurations of worker speeds and hardware setups. The variance in performance could be an issue in highly dynamic environments.\n\nIt is certainly true that the more challenging the problem and the less favorable the environment, the worse the performance of any algorithm. However, it is important to note that our method matches the lower bound established in Theorem 10, demonstrating that Freya PAGE is optimal for the problem we consider, and suggesting that it is infeasible to develop a method with a better performance.\n\n__Questions__\n\n> How does Freya PAGE specifically determine which computations to ignore or adaptively manage in the presence of stragglers? Can this mechanism be fine-tuned for different distributed system configurations?\n\nThe greatest strength of the algorithm is its ability to adapt to the behavior of clients automatically, without requiring manual fine-tuning of this mechanism. Specifically, consider Algorithms 2 and 3 (the asynchronous subroutines of Freya-PAGE). In step 6, the algorithm waits for any worker to send any update. As soon as an update is received, the gradient estimator is updated, and the worker is immediately assigned a new job. This mechanism operates automatically and independently of the order in which messages arrive - whichever worker completes their task first has its update used and is given new data to process. If some workers are too slow to participate in the training, their computations can potentially never be completed, and hence they may effectively be ignored. However, the algorithm itself does not ignore any messages it receives. This is the reason why Freya PAGE is capable of fully utilizing the available computing resources, and why it achieves its superior performance.\n\n__Limitations__\n\n> The performance of Freya PAGE might vary significantly with different configurations of worker speeds and hardware setups. This variance could be problematic in environments with highly variable computational resources.\n\nPlease refer to our responses to the weaknesses above.\n\n> The impact of communication overhead in distributed systems with significant network latency, is not extensively discussed.\n\nIn this paper, we do not directly focus on the communication overhead. However, our method is communication-friendly. As noted just after Algorithms 1 and 2, _the workers can aggregate $\\nabla f_p$ locally, and the algorithm can call AllReduce once to collect all calculated gradients_. It means that Freya PAGE requires each worker participating in the training to send one vector per iteration/round. \n\nIt is possible to improve the communication overhead further using, for instance, compression techniques. It is a research direction that warrants a separate study. We therefore leave this topic for future work.\n\n---\n\nWe are grateful for your feedback and believe that we have addressed the questions. If further information or clarifications are required, please do not hesitate to ask.", "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": "PIacP1TNp2", "reviewer": "Reviewer_6ZMd", "summary": "The paper introduces Freya PAGE, a novel parallel optimization method designed for distributed systems where computational resources vary in capability and speed. This method addresses the challenge of stragglers in asynchronous environments by adopting a strategy that adaptively ignores slower computations, thereby significantly improving the time complexity over previous methods like Asynchronous SGD and PAGE. The paper claims that Freya PAGE achieves optimal time complexity under weaker assumptions and also presents a theoretical analysis that establishes a lower bound for the time complexity in such settings. The approach is particularly effective in large-scale scenarios where the number of data samples is greater than the square root of the number of workers, thus demonstrating the algorithm's suitability for practical large-scale machine learning tasks.", "questions": "How do the workers operate asynchronously? And why do the authors assert that Freya PAGE combines synchrony and asynchrony?", "limitations": "The authors have partially addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The problem tackled is relevant to current large-scale machine learning applications, making the findings applicable and valuable to both academics and practitioners working with distributed computing environments.\n2. Freya PAGE introduces a novel approach to handling heterogeneous and asynchronous computational environments in distributed systems. Its ability to adaptively ignore slower computations is a significant advancement over traditional methods.\n3. The paper demonstrates that Freya PAGE achieves an optimal time complexity, which is a significant improvement compared to existing methods like asynchronous SGD.", "weaknesses": "1. Determining the optimal parameters $S$ and $p$ as outlined in Theorem 7 requires knowledge of unknown $\\tau_i$ and solving an optimization problem, which can be challenging or even impractical.\n2. The paper lacks sufficient experimental results on more complex machine learning tasks, including comparision with cutting-edge distributed learning algorithms.\n3. The algorithm does not address the non-iid data senarios, workers may access data from varying distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and appreciating the strengths of our work. We would like to address your concerns and provide additional explanations.\n\n__Weaknesses__\n\n> Determining the optimal parameters $S$ and $p$ as outlined in Theorem 7 requires knowledge of unknown $\\tau_i$ and solving an optimization problem, which can be challenging or even impractical.\n\nIt is true that in general finding the optimal parameters requires access to $\\{\\tau_i\\}$ (Theorem 6). However, in the large-scale regime (which is the main focus of the paper), the optimal $S$ and $p$ can in fact be determined very easily! The result in Theorem 7 states that the optimal parameters are $S^* = \\lceil\\sqrt{m}\\rceil$ and $p^* = 1/\\sqrt{m}$, where $m$ is the number of data points. Hence, no unknown parameters are involved. Importantly, the assumption that $\\sqrt{m} \\geq n$ in Theorem 7 is relatively weak, since the number of data points is typically much larger than the number of workers. Consequently, in practical scenarios, the optimal parameters can be found easily.\n\n> The paper lacks sufficient experimental results on more complex machine learning tasks, including comparison with cutting-edge distributed learning algorithms.\n\nWe thank the reviewer for the suggestion. Given the theoretical nature of our work, our primary focus was not on extensive experimental validation. The empirical results included were intended to demonstrate that our theoretical findings align closely with practical observations, highlighting the robustness of our theoretical framework. Nonetheless, we are open to incorporating additional experimental results in the revised version of the paper.\n\n> The algorithm does not address the non-iid data scenarios, workers may access data from varying distributions.\n\nThis is indeed an important scenario where appropriate asynchronous algorithms should be developed. However, establishing the time complexity even for the iid (homogeneous) data scenario was an open mathematical problem, which our paper resolves. Even in this scenario, we encountered non-trivial difficulties. Addressing these difficulties takes significant space and is enough to warrant a full research paper. We are currently considering the heterogeneous scenario, and we believe that this topic merits separate, dedicated work.\n\n__Questions__\n\n> How do the workers operate asynchronously? And why do the authors assert that Freya PAGE combines synchrony and asynchrony?\n\nUnlike fully asynchronous methods, Freya PAGE does not update the model based on gradients evaluated at stale parameters — this is the synchronous aspect of the update process, presented in Algorithm 1. However, at each iteration, Freya PAGE invokes the asynchronous subroutines ComputeGradient or ComputeBatchDifference. These subroutines handle the heterogeneity of processing times by waiting for the fastest worker to complete their computations and immediately assigning them a new job until a minibatch is computed. As a result, all workers are kept busy, and whenever they finish their computations, they asynchronously transmit the updates to the server.\n\n---\n\nWe believe that we have addressed all the issues raised by the reviewer and would appreciate if the reviewer could reconsidered the score. Please, let us know if any further clarifications are needed.", "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": "CUpVvlnRAU", "reviewer": "Reviewer_wr2A", "summary": "In this study, the authors developed a new distributed optimization algorithm, Freya Page method, for the non-convex finite-sum optimization problem. The authors provided the corresponding iteration and time complexity bounds. In addition, a lower bound on the time complexity is also provided.", "questions": "- I wonder if the results can be extended to the case when the computation time for each gradient $\\nabla f_j$ is different for different $j$. In other words, can we replace $\\tau_{i}$ in Line 31 with $\\tau_{i, j}$, which may be different for different $j$?\n\n- Line 118: It would be better if the authors can provide more details on the choice of inverse proportion to $\\tau_i$. I feel that this choice can guarantee that the worst-case running time is the same for all workers?\n\n- In Section 1, the authors claimed that Theorem 4 allows $\\tau_i = \\infty$ for all $i$. But I feel that the authors are referring to Theorem 5? Also, I think Theorem 5 (as well as Theorems 1-2) requires $\\tau_i$ to be finite for some $i$ so that $t^*$ is finite? It seems that this is supported by Example 3, where the current analysis is not able to provide an upper bound on the time complexity.\n\n- For the time complexity in Theorem 4, I think the authors are computing the *expected* time complexity. This information is not mentioned in the paper and I feel it might be better to add a formal definition of the expected time complexity in the paper.\n\n- It seems that the authors defined the notion of $t^*(S)$ in Definition 3 but did not used it in the following theorems.\n\n- Line 200: I am not sure why the monotony of the two terms enable the application of the bi-section method.\n\n- Line 294: I am a little confused when the authors mentioned that (10) is less than or equal to (12). It seems that (12) should be a lower bound on the complexity (up to a constant) and the achieved time complexity (10) should not be smaller than it?", "limitations": "See my comments in the Questions section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and easy to follow. The developed Algorithms 2-3 are novel and lead to useful time complexity bounds. The results should be interesting to audiences in distributed optimization and machine learning fields. Due to the time limit, I did not check the proofs in the appendix. But I feel that the proofs should be correct, except that of Theorem 10, which I have a concern about.", "weaknesses": "I did not see major weaknesses. But I am a little confused by the lower bound in Theorem 10 and the claims after the theorem. I have also included a few comments for the authors' consideration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your comments and are grateful for highlighting the positive aspects of our work. We will now proceed to address the questions raised and provide clarifications.\n\n> I wonder if the results can be extended to the case when the computation time for each gradient $\\nabla f_j$ is different for different $j$. In other words, can we replace $\\tau_i$ in Line 31 with $\\tau_{i,j}$, which may be different for different $j$?\n\nIf the processing times varied across different data points, one could always set $\\tau_i = \\max_j \\tau_{i,j}$, and our theory would still be applicable without requiring any adjustments. However, there are probably better strategies than this, which we plan to investigate in future work.\n\n> Line 118: It would be better if the authors can provide more details on the choice of inverse proportion to $\\tau_i$. I feel that this choice can guarantee that the worst-case running time is the same for all workers?\n\nThe idea is the same as that in the proof of Theorem 2 in the appendix, which shows that a batch of $m$ data points can be processed in time (3). We agree that this should be stated more clearly in the main part of the paper and will make the necessary adjustments in the revised version.\n\n> In Section 1, the authors claimed that Theorem 4 allows $\\tau_i=\\infty$ for all $i$. But I feel that the authors are referring to Theorem 5? Also, I think Theorem 5 (as well as Theorems 1-2) requires $\\tau_i$ to be finite for some $i$ so that $t^*$ is finite?\n\nTheorem 4 establishes the iteration complexity, and the total number of iterations to find an $\\varepsilon$-stationary point is independent of the processing times. Therefore, the upper bounds can indeed be infinite, and the result still holds. \n\nIf we assumed that the processing times of workers are *exactly* equal to $[\\tau_i],$ then indeed we would have to assume $\\tau_i$ to be finite for some $i.$ However, throughout the paper, we only assume that $\\tau_i$ provides an upper bound on the processing times.\n\nFor instance, consider an example where all workers have processing times equal to $1$ in the first iteration. Then, in the second iteration, the first worker turns off, meaning its processing time is $\\infty.$ All other workers continue to have processing times equal to $1.$ In the third iteration, the first worker turns on with a processing time equals $1,$ but the second worker turns off, and so on. In this mathematical example, all workers turn off and turn on in a cyclic manner. Clearly, $\\tau_i = \\infty$ for all $i \\in [n]$ because there is at least one iteration in which worker $i$ is turned off. However, in every iteration, there are at least $n - 1$ workers with processing times of $1.$\nThis example is closely related to Section 4.4, where we allow the upper bound $\\tau_i$ on processing times to be _dynamic_.\n\n> For the time complexity in Theorem 4, I think the authors are computing the expected time complexity. This information is not mentioned in the paper and I feel it might be better to add a formal definition of the expected time complexity in the paper.\n\nTheorem 4 states the iteration complexity, so we believe the reviewer is referring to the next result. Thank you for the suggestion. Indeed, this is an oversight on our part, and we will include a formal definition in the revised version.\n\n> It seems that the authors defined the notion of $t^*(S)$ in Definition 3 but did not used it in the following theorems.\n\nThis shorthand notation is used in the text (see e.g. lines 183, 184) and in the proofs in the appendix.\n\n> Line 200: I am not sure why the monotony of the two terms enable the application of the bi-section method.\n\t\nLet us consider the problem $\\min_{S \\in N} h(S) + g(S),$ where $h(S) \\geq 0$ is non-decreasing, $g(S) \\geq 0$ is non-increasing, and $S^*$ is a solution. In order to solve it up to a constant factor (in the paper, we forgot to stress that the solution will be up to a constant factor), we can instead solve the equation $h(\\bar{S}) - g(\\bar{S}) = 0$ (a solution exists because $g(1) \\geq h(1)$ and $h(S) \\to \\infty $ when $S \\to \\infty $ in our setting). Since $h(S) - g(S)$ is non-decreasing, $\\bar{S}$ can be found using the bisection method.\n\nIf $\\bar{S} > S^*,$ then $h(S^*) + g(S^*) \\geq g(\\bar{S})$ because $g$ is non-increasing and $h(S^*) \\geq 0.$ Then\n$h(S^*) + g(S^*) \\geq \\frac{1}{2} \\left(h(\\bar{S}) + g(\\bar{S})\\right)$ because $\\bar{S}$ is a solution of $h(\\bar{S}) = g(\\bar{S}).$\n\nIf $\\bar{S} < S^*,$ then $h(S^*) + g(S^*) \\geq h(\\bar{S}) = \\frac{1}{2} \\left(h(\\bar{S}) + g(\\bar{S})\\right).$ \n\nHence, $\\bar{S}$ is a minimizer of $h(S) + g(S)$ up to the constant factor of $2.$ It remains to round $\\bar{S}$ to the nearest integer. The rounding operation will increase $h(S) + g(S)$ by no more than a multiplicative factor.\n\n> Line 294: I am a little confused when the authors mentioned that (10) is less than or equal to (12). It seems that (12) should be a lower bound on the complexity (up to a constant) and the achieved time complexity (10) should not be smaller than it?\n\n(10) should be greater or equal to (12), and this is indeed the case. Note that we also have\n$$\\frac{1}{\\sqrt{m}} t^*(m) = \\min_{j\\in[n]} \\left(\\left(\\sum_{i=1}^j \\frac{1}{\\tau_i}\\right)^{-1} \\left(\\sqrt{m} + \\frac{1}{\\sqrt{m}} j\\right)\\right) \\leq \\min_{j\\in[n]} \\left(\\left(\\sum_{i=1}^j \\frac{1}{\\tau_i}\\right)^{-1} \\left(\\sqrt{m} + j\\right)\\right) = t^*\\left(\\sqrt{m}\\right).$$\nTogether with the inequality in line 294, this demonstrates that Freya PAGE achieves the lower bound **up to a constant factor**. In other words, it holds that \n$$c_1 \\times (12) \\leq (10) \\leq c_2 \\times (12),$$\nwhere $c_1 \\leq c_2$ are some universal constants.\n\n---\n\nWe trust that our responses have satisfactorily addressed the reviewer's questions. Should any additional clarifications be required, we are happy to provide them.", "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:

Meta-review: This paper proposes a distributed stochastic optimization algorithm called Freya Page that is suitable for heterogeneous asynchronous computations. It is shown that for general nonconvex problems, the gradient converges to zero in expectation at a rate that approaches the lowerbound in the large scale regime. The reviewers all appreciate the theoretical contributions of this work. Some minor concerns include limited experimental results and potential difficulty in parameter tuning in practice.
Decision: Accept (poster)