Delayed Algorithms for Distributed Stochastic Weakly Convex Optimization
Authors: Wenzhi Gao
Qi Deng
Venue: NeurIPS 2023 poster (2023)
Keywords: Stochastic optimization
Distributed optimization
Prox-linear method
Stochastic gradient method
TL;DR: Delay independent rates for distributed stochastic weakly convex optimization

Abstract: This paper studies delayed stochastic algorithms for weakly convex optimization in a distributed network with workers connected to a master node.  Recently, Xu~et~al.~2022  showed that an inertial stochastic subgradient method   converges at a rate of $\mathcal{O}(\tau_{\text{max}}/\sqrt{K})$ which depends on the maximum information delay $\tau_{\text{max}}$. 
In this work, we show that the delayed stochastic subgradient method ($\texttt{DSGD}$) obtains a tighter convergence rate which depends on the expected delay $\bar{\tau}$. Furthermore, for an important class of composition weakly convex problems, we develop a new delayed stochastic prox-linear ($\texttt{DSPL}$) method in which the delays only affect the high-order term in the rate and hence,  are negligible after a certain number of $\texttt{DSPL}$  iterations.  In addition, we demonstrate the robustness of our proposed algorithms against arbitrary delays.  By incorporating a simple safeguarding step in both methods, we achieve convergence rates that depend solely on the number of workers, eliminating the effect of delays. Our numerical experiments further confirm the empirical superiority of our proposed methods.

Delayed Algorithms for Distributed Stochastic Weakly Convex Optimization
Wenzhi Gao" Stanford University gwzestanf ord. edu
Qi Deng'
Shanghai University of Finance and Economics qidengosufe. edu.
Abstract
This paper studies delayed stochastic algorithms for weakly convex optimization in distributed network with workers connected to master node. Recently, Xu et al. 2022 showed that an inertial stochastic subgradient method converges at a rate of (Tmaa/ /VK) which depends on maximum information delay Tmax- In this work, we show that the delayed stochastic subgradient method (DSGD) ob- tains a tighter convergence rate which depends on the expected delay F. Further- more, for important class of composition weakly convex problems, develop a new delayed stochastic prox-linear (DSPL) method in which the delays only af- fect the high-order term in the complexity rate and hence, negligible after certain number of DSPL iterations. In addition, we demonstrate the robustness of our proposed algorithms against arbitrary delays. By incorporating simple safe- guarding step in both methods, we achieve convergence rates that depend solely the number of workers, eliminating the effect of the delay. Our numerical experiments further confirm the empirical superiority of our proposed methods.
Introduction
In this paper, we consider the following stochastic optimization problem
min =ER"
dh (2) Eq-=lf(x;, E)] + w(x),
where f(x, {) is a nonconvex continuous function over and is a random variable sampled from swwrrssemicontinuuus and proximal-friendy: We assume that both fæz, E) and w(x) belong to general class of nonsmooth nonconvex functions that exhibit weak convexity. Here, we say that function g(x)) is k-weakly convex if g(x) + ||a=|]2 is convex for some 2 O. Weakly convex optimization has attracted growing interest in machine learning in recent years, and we are particularly interested in a general type of weakly convex problems with the following composition structure [12]
some distribution E; w(x)
f(x, = h(c(I,E)),
(2)
where / a convex Lipschitz function and c(x; 5) is smooth. Optimization in the above composition form is pervasive in applications arising from machine learning and data science, including robust phase retrieval [14], blind deconvolution [8], robust PCA and matrix completion [5], among others.
Stochastic (sub)gradient method and its proximal variants [39, 10, 30, 28, 31] (all referred as SGD in our paper) are arguably the most popular approaches for solving problem (I). Typically, SGD
iteratively solves xx arg min, (x* )² I²) + w(x) + 24 || 11,) where &l is
Work done while at SHUFE.
The corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

a random sample and f'(="{"* denotes subgradient of f(x", However, despite its wide popularity in machine learning, the sequential and synchronous nature of SGD is not suitable for modern applications that require parallel processing in multi-cores or over multiple machines.
To further improve SGD in parallel and distributed environments, recent work considers a more prac- tical asynchronous setting where the parameter updates allow outdated gradient information. See [1, 32, 38, 29, 21J. In the asynchronous setting, it is crucial to know how the stale updates based on delayed information affects convergence. For smooth convex optimization, Agarwal and Duchi [1] show that delayed stochastic gradient method (DSGD) obtains rate of O(a/VV where Tza bounds of the second moment of random delays. DSGD with adaptive stepsize has also been studied by [25, 32, 38] to achieve better empirical performance and the latest work [2, 33] further improves the rate to O(a/Vi + Tmax/KK. K)) For general smooth (nonconvex) problems, the work [33] shows that DSGD converges to stationarity at rate of O / + TTmxx (K). In follow- up study [7], the authors propose more robust DSGD whose rate depends on the average delay Tavg. rather than the maximum delay. Recently, Koloskova et al. [18] develop sharp analysis for asyn- chronous SGD and then simple delay-adaptive stepsize to achieve the best rate O /VKV/+// +ww////// K). Based on novel delay-adaptive stepsizes and virtual iterate-based analysis, a concurrent work [26] has established new convergence rates that depend on the number of workers rather than the delay of the gradient.
Despite much progress in distributed smooth optimization, it remains unclear how to develop ef- ficient asynchronous algorithms for nonsmooth and even nonconvex problems. For general non- smooth convex problems, the pioneering work [27] has shown that the asynchronous incremental subgradient method obtains an O O(VTmax/ K) convergence rate. The aforementioned work [26] indeeedndeeen rate of O(ym/K) K/K), where m is the number of work-
shows that DSGD achieves ers. However, it is still unknown whether their key technique by telescoping the virtual iterates can be extended to composite nonconvex optimization.
For distributed weakly convex optimization, Xu et al. [34] shows that Delayed Stochastic Extrap- olated Subgradient (DSEGD), inertial version of DSGD, exhibits a convergence rate of O((1 + Tmax)/ /VVV + / (K), which has undesired dependence the maximum delay mmax- This issue is further exacerbated in real heterogencous environments where the maximum delay is dictated by the slowest, or the "straggler" nodes. It remains unclear
1) whether such delay dependence in DSGD is still improvable or not for weakly convex problems?
Nevertheless, even if the rate is improvable in terms of т, there yet remains a fundamental chal- lenge, as the delay significantly influences the leading term (11/ of the convergence rate. This contrasts with smooth distributed optimization, where the delay only affects higher order term O(1/K) and hence is negligible in the long run. Such a performance gap highlights a substan- tial limitation of the prior study when nonsmoothness is present. Hence, natural to ask: For distributed weakly convex optimization,
2) can we design algorithms with negligible penalty caused by delays?
3) Moreover, can we make convergence rates delay independent?
The goal of this paper to address the above three questions.
Contributions In this paper, we answer the above questions positively (Table 1). Our contribu- tions are as follows.
1) For distributed weakly convex optimization, we provide a sharp convergence analysis of DSGD under statistical assumptions on the delays and obtain a rate of O(F/VK + T / K), where F, Taa are respectively first and second moments of stochastic delays. Our result significantly improves upon the previous O(Tmxx/ / VK + / K) rate for DSGD [34].
2) For weakly convex problems with composition structure (2), we propose new delayed stochastic prox-linear method (DSPL) which can exploit the structure (2) more effectively. Unlike SGD, the stochastic prox-lineat algorithm (19, 11I) partially linearizes the inner function c(:,g while retaining the outer function h(-). Then it iteratively solves; I x++1
arg min, [h(e(a . +

---

(ooe=a.)).x-00000 _x)xx==))) +w(x)+ 2x 11>->"11² To the best of our knowledge, this is the first study of SPL in the asynchronous distributed setting. We show that the new DSPL method achieves a rate of O(1/V To2 /K), which consistently better than that of DSGD in terms of the dependence on delay. Interestingly, our result implies that the delay is negligible when K' is sufficiently large.
(Ve(a",
3) We propose a simple yet effective safeguarding step that skips the iteration when the delay is sig- nificantly large. This enhancement ensures that the rate depends only the number of workers rather than on the delay explicitly. Specifically, in an environment of m workers, we obtain an Olym/v VK + mm/K) K) rate for DSGD and O(/vV + m²/ K) for DSPL, making both methods robust to arbitrary delays. As per our knowledge, these distributed nonsmooth nonconvex optimization. Prior to our work, delay-independeer rates were only known for smooth or convex optimization [26], which were derived through distinctly different delay-adaptive stepsize strategy.
the first delay-independent rates for
Table 1:
Rates of delayed algorithms for nonconvex optimization. m: the agent number; Tmax the maximum delay; 7 = 18 [T(x Ta² E[[T]; Tavg average arbitrary delays.
Delay
Work
Setting
Problems / algorithms
Convergence rate
22
[34]
f w / DSGD
O
VK
Non-robust
weakly convex
f + w DSGD
Ours
VK
a e w DSPL
VK
[26, 18, 7]
smooth nonconvex
f DSGD
0
VR
K or 0
Tex
Robust
f w DSGD
0
Ours
weakly convex
VK
h c + w DSPL
0
Structure of the paper Section 2 introduces the notations and problem setup. Section 3 an- alyzes the delayed stochastic (proximal) subgradient method (DSGD). Section 4 develops the de- layed stochastic prox-linear method (DSPL). Section 5 proposes a simple strategy to make the asyn- chronous algorithms robust to arbitrary delays. Section 6 conducts experiments to verify our theo- retical results. We draw conclusions in Section 7 and leave all the proofs and further discussions in the appendix.
Preliminaries
Notations We use - and (.-)) to denote the Euclidean norm and inner product. The sub- differential of function f is defined by 0f(x) == {u: f(y) Z f(x)+ (w, z) -=<l<==>>l] + r} and fa(x) (z) denotes subgradient. 1f0 E (x), then is called stationary point of f- The domain of f is defined by dom f == (x f(x < 00). At iteration k. we use ExI-] to denote the expectation conditioned on past iterations {ar ... x
x-1). I(-} denotes the 0-1 indicator function
of an event. Given a delay sequence {Tx). we write A := K Ek= and A = ΣK 1
Our analysis will adopt the Moreau envelope the potential function, a technique initially identified in the work [8]. Let if be a k-weakly convex function. Given p > K, the Moreau envelope and the associated proximal mapping of are respectively defined by
f1/p(z) = min (f(v) + f1(= 2 and prox (z) = arg min {f()) + -11 v113.
By the optimality condition and convexity of f(y) + 611 yl2 E af(prox,/p(=))) + p(prox (z)()) .). The Moreau envelope can be nicely interpreted a smooth approximation of the original function. Specifically, can be shown that f1/p(a)) differentiable and its gradi- ent (z) = p(r - prooxx;;ppe (See [8]. Combining the above two relations, we obtain (x) E (prox, (x)). Therefore, the Moreau envelope can be used as a measure of approx- imate stationarity: if [|)()( s E, then x is in the proximity (i.e. ||æ - proxx S ps of near stationary point prox s/p (x) (i.e. dist( (pro 0) E).
3

---

2.1 Assumptions
Throughout the paper, we make the following assumptions.
Al: (i.i.d. sample) We draw ii.d. samples {5*} from E.
A2: (Lipschitz continuity) w(x) is -Lipschhi continuous over its domain.
A3: (Weak convexity) x-weakly convex.
A4: (Bounded moments) The distribution of the independent stochastic delays {Tk} has bounded first and second moments. i.c., E[Tu] S < 00, B[T]] S T < J0, Vk.
Remark 1. Assumptions A1 A3 typical in stochastic weakly convex optimization [8], while A4 common in distributed optimization [3, 32). Moreover, throughout our analysis, we regard [Te} as pre-defined random sequence independent of data sampling and the algorithm [32, 34].
3 Delayed proximal subgradient method
In this section, we analyze the convergence rate of the delayed stochastic proximal subgradient method (DSGD) for weakly convex optimization. DSGD the workhorse of most applications and is frequently analyzed in the literature on centralized distributed optimization.
Algorithm 1: Delayed stochastic proximal subgradient method
Input: x²:
for k = 1, 1,.,... do
Let oet""~r 0f(x t , gh-rk) be computed by worker with delay Tw:
In the master node update
x k+1 arg min ((g (( , xn) w(x) 22 || x= 112)
#ER*
end
We restrict f to have a bounded subgradient and make the following extra assumption.
B1: (xx {) is A-weakly convex, Eelllg]|3] L3,99 0f(x, <) for all E domw int(dom and all { =.
Now we are ready to present the convergence analysis of DSGD. Our analysis relics on Moreau envelope, denoted as / (x*), which serves the potential function. After assessing the descent of the potential function with delays separated as an error term, we derive the convergence result by
bounding the stochastic delays. The following lemma provides the descent property.
Lemma 1. Let a == prox p/p (zp()>)) Suppose A1, A2, A3 and B1 hold. If >
2A + Ki Th 2 p. then
(A-)) 2(th 1174-2A-4 22 18t 22 < (x=) (2/2//// k+1]]]]] p(xx-p) E3 k+1 x² [12]
2(Tu 2λ-x)
E1 Ea k+1 k-n |
_
20h,
Remark Lemma shows that aside from the noise and delay-related terms, unless we are close to approximate stationarity characterized by | - x>1 there is always sufficient decrease in the potential function. Intuitively, if we take sufficiently large regularization y and bound the delays using A4, convergence is almost immediate. Now we show convergence of DSGD in Theorem 1.
Theorem 1. Under the same conditions as Lemma well as A4, taking " = p 4A + 16 VK/a for some > 0, letting k. be chosen between I and K uniformly at random, then
E B[IIVei/o )13 < p-2
(p+2A)D
D VKa
4pLy(Li+hule VK
+ + K
where D = (1)p((²)) inf ((x) and recall our notation A -2
# T
Remark Note that a controls the trade-off between noise, delay and optimization. practice we can set a hyper- parameterrt and tune it improve performance.

---

The bound for DSGD states that
A V ) 0 V + VK + R2) or Elll V ) - +
if we take [[A]] = F and || = Tza. Here A is the average delay and is considered "robust" in the distributed setting. However, there exists a second term XD2 arising from X-weak convexity. As we will show later, this term, in the worst case, can be trivially bounded. Therefore, we now resort to our statistical assumption A4 and use the first and second moments to give bound.
4 Delayed stochastic prox-linear method
In this section, we present a delayed stochastic prox-linear method (DSPL) for the composition op- timization problem with [x, {) h(c(2, E)), where h(-) R + R is convex nonsmooth func- tion and c( : IR" + is a smooth, potentially nonconvex function. For brevity, we denote (=( = h(c(z, + (Ve(z, {). z)). partial linearization of the objective, and we use these two notations interchangeably to describe DSPL. We will show that this lincarization scheme im- proves the accuracy of approximating the objective, thus giving improved convergence rates in the presence of delay. It should be noted that while we assume c(-) to be a smooth function, our analysis can seamlessly extend to the case where is smooth mapping with bounded Jacobi matrix.
Algorithm 2: Delayed stochastic prox-linear method
Input: x;;
for k 1, 2,..... do
Let (*-T)))))))))))) and T be computed by worker with delay Thi the master node update
x+1 arg min (x, Tk) + +w(x) + 11 x* |1
(4)
#ER"
end
We describe DSPL Algorithm 2. DSPL can be deployed in multi-agent network where all the workers are connected to master server. We assume the workers access random samples & and compute the function value c(x, {) and gradient Ve(z, E). At the k-th iteration, the master node receives delayed value c(z**>h,, -*- and gradient Vo(a* <h of an earlier point ===Te, Next, it performs proximal update (4) obtain the next iterate x*+1 Figure 1 illustrates the operational dynamics of DSPL and contrast it with DSGD. Throughout the rest of this paper, we assume that the proximal update is easy to compute. To derive the convergence results of DSPL, now formally state the assumptions on / and c.
C1: h(x) is convex and LA LnpLiscchitz continuous over its domain; c(x, {) has C($)-Lipschitz con- tinuous gradient and is L.(g ( Lipsschit continuous over dom w. Moreover, we assume that E<(C(E)*) C22 (E) < I.2
Remark 4. The assumption of Lipschitz continuity for is quite prevalent in the literature of weakly convex optimization [8, 12, 13]. However, it may not hold if dom w is unbounded and c nonlinear, such in the case of quadratic functions. To circumvent this problem, we introduce the relative Lipschitzian property and extend the method to the Bregman proximal iteration. This involves replacing the Euclidean regularization term =|| 27 1| in (4) with the divergence Va(x, 2*), which is generated by strongly convex function d(.). The Bregman DSPL encompasses Algorithm 2 as special case; the details are provided the appendix for thorough examination.
Under the above assumptions, fa( satisfies the following desirable properties. Proposition 1 (Properties of fz(
PI: fa(x, E) is convex for all x, z E dom w, and every & ~ E.
P2: (5=(x,{) - f(x,() < (a((E) || - z||2 for all x, z E domw and & E.
2
P3: fs(x,)) (v. < (x) ly - xll for all x, y, z dom and all & &~
5

---

From Propasition 1, we see f(z, 5) is -,e(())-eakly convex since the error between f(x, {) and a convex function is bounded by quadratic function. Furthermore, we know that f(z) is L Le Lipschitz-contimuuus and T- C-weally convex after taking expectation. For a unified analysis, we take f, = Le, = C and use these constants to present the results. The following lemma characterizes the descent property for our potential function in DSPL.
Lemma 2. Suppose A1, A2, A3 and C1 hold, if p > 2Λ + K; 2 p. then
plo-22-N) 2(th - 22-x) |8 12 2 S V11p(aak)
/ (x
7 22 m) Ex Bxlll
1|1l=++++11 x² x01
20h3 11-1)(1--2A- 3(T 2イ-
3nd
En || ||
let Tu [12].
Similar to the analysis of DSGD, we bound the delays to give the convergence result.
Theorem 2. Under the same conditions as Lemma 2 as well as A4, taking "tk = = p + 6Λ +
V tor oo for some 0, letting ke be uniformly chosen between 1 and K, then
E E1IVe1/p 6" )| p-2d-R
20
(p+ANDD
D- VKaa
+
20L3a
+
6pd(T, +h. Po8
42
VK
K
where = =11/p(a*) inf, (x))).
If we take [[Ag] T22, then Theorem 2 implics that
V || - + 2 E[I B[I (000)))0(001111)01 0 VK R
Compared to DSCD, the delays for DSPL appear only in a higher-order term with respect to K. Different from DSGD where À only characterizes weak convexity, À for DSPL also represents the quadratic upper-bound on fxx E) in P2, which is not O even if the problem is convex.
DSGD
DSPL
Mate::
(1H i More CII
Mirker S,y.A
Ve
VV
Figure 1: DSGD and DSPL in a master-worker architecture.
DSPL vs. DSGD We give some further insights on the behavior of DSPL and DSGD for the com- position function (2). Intuitively, as the algorithm converges, we have lim - x = 0 a.s. When o² se - DSPL enjoys an increasingly stable estimation of the proximal mapping (4), as the influence of delay diminishing and the eιror is mainly driven by stochastic sampling. The same conclusion holds on smooth DSCD due to the Lipschitz continuity of f.. On the other hand, when DSGD is applied for nonsmooth problem, the master node receives an out-of-date subgradient f from the worker and solves (3). Since fax E) is nonsmooth, the subgradient f' (=x {) may differ significantly from f'(x* E) even when the sequence {x*} converges. Hence, DSGD will constantly suffer from delay during all the updates (3).
DSPL with momentum We also remark that the momentum technique from DSGD can be extended to DSPL, which gives us the same O(Tmux/ /K K + r K) convergence rate as in [34]. We refer the interested readers to the Appendix F.
When f is smooth, the analysis of DSPL can be adapted yield a comparable convergence rate for the proximal stochastic gradient method for minimizing v²(-).
Theorem 3. Suppose all the assumptions in Lemma 1 and A4 hold, and that f is X-smooth. Let
7h 7 = + 6Λ + K VK f for some a > then E[//V {[ = 0 V AA2).
So far we have spent two sections analyzing the two algorithms so that enough intuition can be established. All these serve for our ultimate goal: making DSGD and DSPL robust to arbitrary delays.

---

Weakly convex optimization robust to arbitrary delays
This section proposes robust variants of DSGD and DSPL, for which the explicit delays are eliminated from the convergence rate. What we will do is reduce the impact of delay to the number of agents in the network. Moving forward, we substitute A4 with D1.
DI: The distributed environment has m workers.
The previously established results have provided sufficient intuition how delays impact our algo- rithms. In view of Theorem and Theorem 2, we have isolated delay-dependent O(A1/ ////) and O(22/K) in the proof. Although A1/Vi seems larger, it turns out that 22 stands in our way. The following lemma shows A = K Ex=t Tk is bounded by m.
Lemma 3. In a distributed environment of m workers 4 = + E Z m m.
Given Lemma 3, we know A1/VK O(m/ /K) and we can replace dependency on A by m. Now consider 22 E Th Even if we have a larger denominator K neutralizing the effect of 22, the following example shows that in the worst case, A2 can be of O(K) and result in (1)) error.
Example (Why A₂ hurts performance). Given sequence of delays {Tk} such that Tk 0, S K 1, TK = K. Then 22 = and 2 =
The example tells that delays of O(K) ruin our convergence. In other words, to recover an overall O(I/VK) convergence rate, we need 2 K O(IV/)) = Σk Ek tf O(K3/2). The next
lemma provides hint for our algorithm design.
Lemma 4. If sequence of nonnegative integers {Tx} satisfy Ek= Th S mK, then given T 2
1. Th S ST for all k. then E o S mKT;
2. Σx k= 1 S 27) K -
Lemma 4 tells us two facts about nonnegative integer sequence of length K with sum bounded
by O(K): 1). if we restrict the elements to less than O(T), then Σ 7i I OKTT). 2). there will be 2(K (KK mKT-1) elements bounded by T. Back to our context, this implies 1). To reduce
2 K to O(I/VK), we can discard the iterations of delays greater than = (VVK). ). 2). We skip no more than O(vK) iterations and optimization works with O(K - /K) OKK) iterations left.
Having established the foundational under- standing, we outline the main steps in Algo- rithm 3. It is based on the aforementioned in- tuition and incorporates a "safeguarding" step to discard inaccurate information which could potentially hurt the convergence performance. As the above argument the accumulated de- lay is independent of any specific algorithm, the safeguarding strategy can be applied both DSGD and DSPL. To make our parameter setting more general, in our analysis con- sider T = mK3 > 0,3 0.
Algorithm 3: Safeguarded DSGD/DSPL.
Input: x '''=>''K'' mmK3
for 1, 2,... do if < then Update with
(3) for DSGD or (4) for DSPL
else
x x++ z
end
end
Intuitively, under worst-case scenarios, Algorithm 3 will perform after K iterations in a manner similar to its non-safeguarded counterpart. However, the maximum delay will be capped at m,, and the iteration count will be (11-rK-F)
Theorem (Safeguarded DSGD). Under the same conditions as Lemma 1 as well as D1, taking 1) 3 >>0 0, > 4/8 or 2) B = 0,r r < 1, then letting 7kk 7 /K
av + 4X 7 = x== for
7

---

some a > O and k- be uniformly chosen between iterations where =T=r" pr=>rr1mm mK
V )1
2p
a(tt2ADD
vDD
1n pL, + mamma 8ij² pALL +L )
p- 2--
VRa
/K
rk
where D - /111p(1))) - inf vxx)..
Theorem (Safeguarded DSPL). Under the same conditions as Lemma 2 as well as DI, taking 1) vK > 0, K ,1/0 2) B 0,r < 1, then letting **k = ov'9 p 6λ, 1 k for
some > 0 and k* be uniformly chosen between iterations where T S = mrrmm
VIIVvi// )| P-2A-K K
M(++4A
ARD
2umpLya
6n/2 + mm²a?
VKa
VK
where D = (1/p(x²) inf (xx).
Remark 5. Theorem and 5 show that by employing a safeguarding step, both DSGD and DSPL can achieve delay-independent rates. also interesting see how the choice of | and r affects performance. To recover convergence rate of O(K ( it is sufficient to have B S 1/2. If we set 0, then we skip rk~ 9 of all the iterations and incur penalty of up to 3/2 in DSGD and r/ in DSPL. However, this loss becomes negligible for large K, as 1 + k 1. Alternatively,
set 0, DSGD achieves Ovym/v / m/K) rate with a 1/ / while DSPL yields a rate of O(L/VK + m²/K) with a = 1. This setting aligns with [7. 18] and achieves optimal rate on However, the penalty from 1 > 1 is non-negligible and adversely affects the overall convergence rate by a constant factor. Therefore, we can strike a balance practice by choosing / in (0, 1/2]
and allow delays of up O(K)).
Experiments
This section performs numerical experiments on the robust phase retrieval problem to demonstrate the efficiency of our methods. Given a measuring matrix A E Rmxa and set of observations b, AJ (a,, a) 12, < S m (m in this section represents the number of samples), robust phase retrieval aims to recover the true signal è from
Σ (a:, x)2 bul + dx::|=]|MM
min WER
77A
where ōs denotes the set indicator function and the & loss function improves robustness. Our periment contains three parts. The first part profiles algorithms in an asynchronous environment simulated via MPI; second experiment runs sequentially with simulated delays from common distributions; our last experiment also runs in the simulated environment and demonstrates the ef- fectiveness of safeguarding step under adversarially chosen delays.
6.1 Experiment setup
Synthetic data. For the synthetic data, take 300, 100 in the experiments of simulated delay and m = 1500, n 500 in the asynchronous environment. Data generation follows the setup of [11], where, given some 2 1, compute A QD, Q mm Ii A/(,, 1) and D = diag(d) (d), d E IR, RR,d, d, E [1/k, 1] for all Then we generate true signal f ~ NO I) and obtain the measurements using formula b, (a,, 2 Last we randomly choose Prai ffactratiion of the measurements and add (0, 25) to them to simulate data corruption.
Real-life data. The real-life data is generated from zipcode dataset, where we vectorize 16x 16 hand-written digit from [16] and use it as the signal. The measuring matrix comes from normalized Hadamard matrix Il E 25622666
generate three diagonal matrices S, diag( s; J.j 1,2, 3; each element of sj E 2556 is taken from {-1, 1} randomly and we let Finally Pla-fraction of the observations are set
= H S S2, S5) E R 768x256
1) Dataset. the asynchronous environment, we keep up with [34] setting a: 1, 1, = and in the simulated environment, follow [11] setting {1, and Pial E {0.2, 0.3).
8

---

2) Initial point and radius. Synthetic data: we generate x' ~ (0, ,,) and start from x' ||a'|
zipcode data: we generate x' ~ (i, In) and take x² = 10x'.
1000||>*1|
3) Stopping criterion. We run algorithms for 400 epochs (K = 400m). the asynchronous en- until reaching the maximum iteration. In the simulated environment,
vironment, algorithms algorithms stop if f & (.). When f contains corrupted measurements, fā) > 0.
Stepsize. We set > //aa, where a {0.1, 0.5, 1.0] in the asynchronous environment, E [10-2, 10"] for synthetic data and a E [10*, 10 for the zipcode dataset.
Simulated delay. In the simulated environment, we generate тą from two common distributions from literature, which are geometric (p) and Poisson P(A) [37]. After the delay is generated, truncated by twice the mean of the distribution.
A Adversarial delay. We let delay happen at the last iteration of each epoch and use the informa- tion of x to update. Safeguarding parameter set to T 0.1
7) Trade-off between computation and communication. the asynchronous environment, the numerical linear algebra on the worker uses raw implementation (not importing package) to balance the cost gradient computation and communication.
6.2 Asynchronous environment
Our first experiment runs an asynchronous environment implemented by MPI Python interface and is profiled on an Intel (R) Xeon (R) CPU E5-2640 v4 @ 204OH machine with 10 cores and 20 threads. This experiment runs on a single machine to verify our theoretical finding rather than to test the algorithm's 's real performance on a specific distributed architecture.
400
SGD
8PL
Distnnc to optimal
Funstion value pap
DSGO workers
DEPL Wariers
to
0550
CSPL warters
DEPs Jwakers
200
COPL Fasrioe
10n DEPL waakers
CAPL Aariove
DEPL verkers
DEPL veriine
104
16
20
35
50
Number of workers
Number opochs
Number spacha
Figure 2: First: speedup in time and the number of workers. Second: progress of ||æ a|| in the first 40 epochs given a = 0.1. Third: f(**) f(Ø) in the first 40 epochs given a 0.5. For more details about the two figures on the right, please refer to Figure 12 the appendix.
The first figure plots the wall-clock time (in seconds) for DSGD and DSPL complete 400 epochs when the number of workers increases. It is observed that both algorithms exhibit speed-up with more workers and note that DSPL takes more time than DSGD due the need to pass the function value to the master and slightly more expensive updates. But as the second and the third figure sug- gest, this extra cost is justified by the superior convergence: in the first several epochs DSPL reaches a high accuracy of 10-6 in both function value and distance to the optimal solution, while DSGD stagnates at a relatively low-accuracy solution of 10-2 These observations suggest that DSPL offers better convergence behavior than the methods only based on subgradient. Finally, our experiments suggest both DSGD and DSPL are sensitive to the increase in the number of workers when there are relatively few workers.
6.3 Simulated environment
The second part of our experiment compares the performance between DSGD and DSPL and is based on the simulated delay, where the algorithm runs sequentially but the gradient information is com- puted from the previous iterates.
Figure 3 plots the number of iterations for each algorithm to converge under different datasets and delay parameters. We see that spite of delays, DSPL admits a wider range of stepsize parameters ensuring convergence than DSGD, and the performance slightly deteriorates delay increases.

---

228"
8360
Figure 3: Left two: Geometric delay (R.) (1,0.3). 2p- (28, 47]; right two: Poisson delay (6, Prai) (10, 0.2), 2λ e {28, (7). x-axis: parameter o: y-axis: number of iterations. Definition of delay is given in experiment setup 5).
6.4 Adversarial delay
The final experiment verifies the efficacy of our safeguarding step when delays are introduced in an adversarial setting. We evaluate the performance of DSGD, DSPL, both with and without the safeguarding step, under the delay patterns we have generated.
0.52
04
07
0.55
saleosso
08
08
DSM
0.6
NN
Function
Selx0000
0.35
Feb-O5c0 Rab-OOFL
0.9
0.43
044
0.42
3.59
37
2.59
2.45
28
2.5
x11
X38
110
Figure 4: From left to right: zipcode data, Prail 0.2, a E {10, 100), Paat = 0.3, a E {10, 100). x-axis: iteration count; y-axis: f(**).
Figure clearly illustrates the superior performance our method incorporating the safeguarding step. As suggested by theory, DSGD is notably sensitive to delays of O(K). However, upon discarding outdated information, DSGD exhibits much greater robustness. Interestingly, even under adversarial setup, the performance of DSPL remains acceptable, albeit slightly inferior to its safeguarded version, which aligns well with our thcoretical findings.
7 Conclusions
We offer a sharp analysis of delayed stochastic algorithms for weakly convex optimization, dis- cussing the widely utilized DSGD method and introducing the novel DSPL method for problems with composition structure. Through careful examination of delay factors, propose straightforward safeguarding approach to eliminate the effect delays, and instead derive bounds depending on the number of agents in the distributed environment. This makes algorithms resilient to arbitrary delays. A promising future direction is the application of these prox-linear methods in more diverse distributed settings, such decentralized networks.
8
Acknowledgement
The authors thank the anonymous reviewers for their constructive suggestions. This research is par- tially supported by National Natural Science Foundation of China (NSFC-72150001, 11831002).
References
[1] Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In J. Shawe- Taylor, Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
10

---

[2] Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Algoritimic Learning Theory, pages 111-132. PMLR, 2020.
[3] Karl Bäckström, Marina Papatriantafilou, and Philippas Tsigas. Mindthestep-ssynepsae Adap- tive asynchronous parallel stochastic gradient descent. 2019 IEEE International Conference Big Data (Big Dala), pages 16-25. IEEE, 2019.
[4] Dimitri Bertsekas and John Tsitsiklis. Parallel and distributed computation: numerical methods. Athena Scientific, 2015.
[5] Vasileios Charisopoulos, Yudong Chen, Damek Davis, Mateo Díaz, Lijun Ding, and Dmitriy Drusvyatskiy. Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence. Foundations of Computational Mathematics, 21(6):105--193, 2021.
[6] Shixiang Chen, Alfredo Garcia, and Shahin Shahrampour. On distributed non-convex optimiza- tion: Projected subgradient method for weakly convex problems in networks. IEEE Transac- tions on Automatic Control, 2021.
[7] Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances in Neural Information Processing Systems, 34, 2021.
[8] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly con- vex functions. STAM Journal on Optimization, 29(1):207-239, 2019.
[9] Damek Davis, Dmitriy Drusvyatskiy, and Kellie J MacPhee. Stochastic model-based minimiza- tion under high-order growth. arXiv preprint arXiv: /807 2018.
[10] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, aureloo Ranzato, Andrew Senior, Paul Tucker, Ke Yang. et al. Large scale distributed deep networks. Advances in neural information processing systems, 25, 2012.
[11] Qi Deng and Wenzhi Gao. Minibatch and momentum model-based methods for stochastic weakly convex optimization. Advances in Neural Information Processing Systems, 34, 2021.
[12] Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of con- vex functions and smooth maps. Mathematical Programming, pages 1-56, 2018.
[13] John Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimiza- tion problems. SIAM Journal on Optimization, (14::3222-3253 2018
[14] John C Duchi and Feng Ruan. Solving (most) of set of quadratic equalities: Composite opti- mization for robust phase retrieval. Information and Inference: A Journal of the IMA, 8(3):471- 529, 2019.
[15] R Fletcher. A model algorithm for composite nondifferentiable optimization problems. In Nondifferential and Variational Techniques in Optimization, pages 67-76. Springer, 1982.
[16] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
[17] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR, 2019.
[18] Anastasiia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous sgd for distributed and federated learning. Advances in Neural Information Processing Systems, 35:17202 2022.
[19] Adrian S Lewis and Stephen J Wright. A proximal method for composite minimization. Math- ematical Programming. 158(1):00-554,, 2016.
[20] Xiao Li, Zhihui Zhu, Anthony Man-Cho So, and Jason D Lee. Incremental methods for weakly convex optimization. arXiv preprint arXiv: arXiv: 1907. 1687, 2019.

---

[21] Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gra- dient for nonconvex optimization. Advances in Neural Information Processing Systems, 28, 2015.
[22] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decen- tralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
[23] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochas- tic gradient descent. In International Conference on Machine Learning, pages PMLR, 2018.
[24] Vien Mai and Mikael Johansson. Convergence of a stochastic gradient method with momentum for non-smooth non-convex optimization. In International Conference on Machine Learning, pages 6630-6639. PMLR, 2020.
[25] Brendan McMahan and Matthew Streeter. Delay-tolerant algorithms for asynchronous dis- tributed online learning. Advances in Neural Information Processing Systems, 27, 2014.
[26] Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[27] Angelia Nedié, Dimitri P Bertsekas, and Vivek S Borkar. Distributed asynchronous incremen- tal subgradient methods. Studies in Computational Mathematics, 8(C):38 1077, 2001.
[28] A. Nemirovski, A. Juditsky, G. Lan, and Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-1609, 2009.
2009.
[29] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. volume 24, 2011.
[30] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Math- ematical Statistics, pages 400-407, 1951.
[31] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, volume 2, page 5, 2009.
[32] Suvrit Sra, Adams Wei Yu, Mu Li, and Alex Smola. Adadelay: Delay adaptive distributed stochastic optimization. In Artificial Intelligence and Statistics, pages 957-965. PMLR, 2016.
[33] Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates. Journal of Muchine Learning Research, 21:1-36, 2020.
[34] Yangyang Xu, Yibo Xu, Yonggui Yan, and Jie Chen. Distributed stochastic inertial- methods with delayed derivatives for nonconvex problems. SIAM Journal on Imaging Sciences, 15(2):550-590, 2022.
[35] Jinshan Zeng and Wotao Yin. On nonconvex decentralized gradient descent. IEEE Transac- tions on signal processing, 66(11):2834-2848, 2018
[36] Junyu Zhang and Lin Xiao. Stochastic variance-reduced prox- algorithms for nonconvex composite optimization. Mathematical Programming, pages 1-43, 2021.
[37] Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-aware async-sgd for distributed deep learning. arXiv preprint 1rXiv:1511.05990 2015.
[38] Shuxin Zheng, Qi Meng. Taifeng Wang. Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Tie-Yan Yan Liu. Asynchronous stochastic gradient descent with delay compensation. In International Con- ference on Machine Learning, pages 4120-4129. PMLR, 2017.
[39] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradi- ent descent. Advances in neural information processing systems, 23, 2010.
12

---

Appendix
Table of Contents
A More on the related works
14
B Bregman context and auxiliary results
15
B.I Context setup
15
B.2 Auxiliary lemmas
15
Convergence Analysis DSGD
Proof Lemma
C.2 Proof of Thcorem
D Convergence analysis of DSPL
19
D.1 Preliminaries and analysis of Bregman DSPL
................................
19
D.2 Proof of Lemma 2 and Theorem 2
24
D.3 Proof of Theorem
24
E
Delay-independent analysis
24
E.1 Proof of Lemma
24
E.2 Proof of Lemma
25
E,3 Proof of Theorem 4
25
E,4 Proof of Theorem
26
F
DSPL with momentum
26
F1
Preliminaries DSEPL.
26
F2
Convergence analysis DSEPL
28
Kernel and subproblems
33
G.1 Choosing the divergence kernel
................................
33
G.2 Bregman proximal subproblem
................................
34
G.3 Euclidean subproblem with nonsmooth regularizer
................................
35
H Additional experiments
36
H.1 Robust phase retrieval
36
H.2 Blind deconvolution problem
37
H.3 Proximal sub-problems
39
H.4 Separate figures of Section
40
Structure of the appendix In this paper, strive to provide comprehensive treatment of de- layed stochastic algorithms for stochastic weakly convex optimization in both theoretical and prac- tical aspects.
1) Theoretically, we choose to employ a more general Bregman divergence context in our proof. This broader context covers the primary results for the Fuclidean setting discussed in the main section. Specifically, this context will be invoked in our analysis for DSPL method to accommodate real-life applications of prox-lineat method and by relaxing the Lipschitz condition C1.
13

---

2) Practically, provide detailed discussion on how to implement the DSPL algorithm, both in Euclidean and Bregman context. We specifically address the selection of the Bregman divergence kernel and propose efficient subroutines to solve proximal subproblems. Additionally, in view of the wide usage of momentum techniques stochastic optimization, we analyze DSEPL, the momentum variant of DSPL. While this is not the central contribution of our paper, we believe it represents an important step for making DSPL applicable to real-workd problems.
Main results
Section A Other related works
Section C Convergance of DSGD (Euclidean)
Section E Delay-independent Analysis for DSGD DSPL
K
Section B setup 2. Auxiliary results Bregmen a Euclidean
Section
Convergence DSPL
(Bregman)
Practical extensions (Optional)
Section Subproblem solving
Section F Convergence DSEPL (Euclidean)
Section H Additional Experiments
Figure 5: Structure of the appendix
The appendix is organized as follows.
The first five sections address the theoretical aspects of delayed stochastic algorithms.
In Section A, we first conduct extended review of other related works. Section introduce the Bregman context with some auxiliary results. In Section C, we perform convergence analysis for the DSGD method, and Section presents a more general Bregman DSPL that relaxes the Lips- chitzness assumption. Section E presents the safeguarded variant of our algorithms that are robust arbitrary delays.
(Optional) The last three sections are devoted to more practical aspects.
In Section F, we present the convergence analysis of DSEPL, namely, the momentum variant of DSPL using variable extrapolation. Section discusses how to construct the kernel and solve the Bregman proximal subproblems. Finally, Section H displays additional experiment results.
A More on the related works
First, we review the literature on stochastic weakly-convex optimization. The Prox-Linear (PL) method [19, 12, 15] has received more attention lately. The seminal work [8] conducts novel complexity analysis using the Moreau envelope as the potential function. They show that SGD (and many other stochastic algorithms) achieves an ((++) complexity in terms of convergence to proximity of approximate stationary points. [20] analyzes an incremental subgradient method for finite-sum problems. [36] extends the prox-linear algorithm to the finite-sum setting and provides analysis based variance-reduction. SGD with momentum is studied in [24] and [1]] reveals that SPL can be accelerated by minibatching even for nonsmooth objective functions. [11] also employs heavy-ball momentum to further improve the model-based optimization.
There is substantial literature on distributed and asynchronous optimization. We refer the seminal work [4]. In addition to the aforementioned asynchronous issues, another important research di- rection concerns reducing the network communication cost by gradient compression. For example, see [17]. Besides the centralized setting, there is also growing interest in decentralized algorithms. Recently, [6] presents decentralized SGD the network where nodes exchange parameters and sub- gradients locally. However, their method requires all the nodes to update synchronously and only
14

---

proves asymptotic convergence of SGD. An extensive study of decentralized optimization is beyond our work. Therefore, we refer interested readers [22, 23, 35] for more recent advances.
B Bregman context and auxiliary results
We initiate the theoretical discussion by introducing the Bregman context, which includes the con- cepts of Bregman divergence, relative Lipschitzian property, and Bregman Moreau envelope. Fol- lowing the provision of requisite definitions, we present some auxiliary results that will be used frequently in our analysis.
B.1
Context setup
Bregman divergence and relative Lipschitzness Given Legendre function d(-) [7] that is proper, closed, strictly convex and essentially smooth, it induces the Bregman divergence defined by
Va(x, = d(x) d(v) (Vd(y).
and d is called the kernel of Va_ Since d is strictly convex, we know Va(æ, y) 2 0 and the equality holds and only if x y. The notion of Bregman divergence greatly enhances the coverage of the algorithms and has recently been adopted in the context of weakly convex optimization [8, 3] tackle a broader class of nonsmooth nonconvex optimization problems. In this paper, we mainly leverage the concept of relative Lipschitzian property to extend the analysis of delayed stochastic algorithms. First, we give its formal definition.
Definition 1 (Relative Lipschitzian property). [3] function f satisfies L-relative Lipschitzian property to kernel d if for all E dom d,
f(z)
f(y) S 2V2V2(g.2)
(5)
Bregman proximal mapping and Bregman envelope
As in conventional weakly convex optimization, we need an approximate measure of stationarity in the oon-uucideann setting. A naturally choice is the Bregman envelope [3]. Assume that d is I-strongly convex, then for any p > the Bregman envelope of ʃ with respect to kernel d
(x) = (f)) pVa(u,
and the Bregman proximal mapping is represented using prox (z) == arg min(f + pV)(y,z)}
We sometimes refer to prox v/p (x) as è and proximal distance [V(V x²))] has been proven proper measure of the convergence of stochastic algorithms [3] under specific choice of d and p.
Connection with Euclidean geometry One advantage of using Bregman context is that it sub- sumes the Euclidean case. we take d(x:) |a|| then Va(z,, y) 2 || - yll and relative Lipschitzian property becomes standard Lipschitz condition. Particularly have the following relation between Va(i, x) and Moreau envelope.
Va(ah x²) = l1at 111
2p
When the context is clear, we will use vi = vi directly if d(x) | ||/ In the next section, we present several useful auxiliary results that appear frequently in the proof.
B.2 Auxiliary lemmas
In this section, we present all the auxiliary lemmas that will be used in the proof of our main results. While some of these lemmas are widely recognized in the field, we reproduce them here to ensure that our work remains self-contained. To begin, introduce the well-known three-point lemma.
15

---

and Lemma (Three point lemma). Let f be closed convex finction and define
arg mrg + /Va(2,));
for some y E dom d. Then we have
f(z) VVlz & f(x) vVa(a, - VV( 2), Ve dom d.
The following lemma bounds, for a deterministic function, the proximal step by the regularization term and relative Lipschitzian property.
Lemma 6 (Bounding the proximal step). Given the divergence Va generated by some 1-strongly convex function d. Let the function f() satisfy the relative Lipschitzian property (5). For any such that f + nd is strongly convex, if we define
xt = arg min ((i) + Valy,
then
Valat,, x)) S V2
(6)
| 2|| 2- L.
Proof. By the optimality of x and relative Lipschizian property, we have
f(x + +Valx 5 f(x)
and
VVll (()xtt,)== S f(x) f(x+)((+))))==)){()))) S TV 2VV((tttt)) s
(8)
Dividing both sides of (8) by / VVlxt, x) gives (9); (10) uses Vala+ x) 2 1 x1/
Lemma (Bounding the proximal step expectation). Given the divergence Va generated by some I-strongly convex functiio d. Let convex stochastic functionn f(x, E) satisfy the relative Lipschitzian property (5) with L(E) for & ~ For any 7 > 0, if we define
+ arg ary
then
1 -e-==ll>*** - x|1| s Be-= Va(xt, S V2. (Eg-=IL(E)) V2
(9)
and
2 (BE=E(L(E)?) Eewellx* - xx13] - 47
(10)
Proof. We can apply Lemma 6. Then have, for each E, that
Valx x) s -2y-1 and Va(a+ .x) -
Taking expectation with respect to &, the fact that Va(a+ ,.) 2 } -|--~ = completes the proof
C Convergence Analysis of DSGD
In this section, present the convergence analysis of DSGD. The proof follows standard inexact potential reduction scheme and done the Fuclidean setup, where Lemma 5 and Lemma 7 hold for d = 1 11
16

---

C.1 Proof of Lemma
Since p > X + and Nhe 2 p. by three-point lemma get the following two relations
- + w(x
7k || - x²11
+
2
(g Tg 2 + w(+h)
2
11 x²111
7k
1C
11
x
11
(11)
2
2
1(6*) + w(th) Glla* - 2²112 S f(ahtl) + ( + + -llckt1-
=2111
(12)
Summing up (11) and (12) and taking expectation, we have
7hk EE
(| h+t x²11 - 7k - |1t x x11
7h
Exll x x+1 ||2]
2
2
- Ben-n TT T - x [2 - f f(a²) + [x
E& 1i0 k =1)-))))
Eqa- 1g9 8- 3, # [x]]
}] + f fa ) 1 f((ht)
+ E& [5 [1]] [s Th) - Ex (gg" " -,, - x rm)
$ | TT
To 1|2 2T, f 1 k 7m
(13)
where (13) follows from X-weak convexity of (x, E) and B1 (using (I]). Re-arranging the terms, have
Yk
E& |I|
xx 2
2
7k
P
11st - *²111² 112 + =/2 11
2
+ 2 Bx Exll2= 11 - _ -x ||]
7/- PEn EE [11 -
2
7/- P 11a" - =01 + 11
- - 112 + AE 2
2
+ 2T,,, [1 kk
7k
P EA ||| 1011
(14)
2
where (14) follows by Cauchy's inequality ||l+ < 2||a||2 Now we re-arrange the terms and divide both sides by 7 2X k to derive
E& 11
x 1121
7k - P
11 11
2
E1 (1|1 b-re rk 1|2]
7k- 2) x
21
+ 7k 2)
41,,
E
Tk |1]
7/6 P
F2 11x x² [12]
K
7k 22
P 2) Ki
2,
=
|1.a - x11
|
x* 112
+
E2 [[]
7 2X
7k 2A - k
+ 7k 2A
4T,
E Exll| ++1l
Th
7/ p
E4.
[1a - x 1111
(15)
K
7
22
17

---

Finally, we measure the reduction in potential function /1 and successively deduce that
Exlv1//(xtt11) Ba(J(Eh+1) + w(th+t) ) [111at1] [13)
S <Bulf(af + w(th) + 11s 11²
Bxlf((t) + w(*t) + p |, -²1
plp 22 k))
11 =2/113
2(7x 22 13)
pA
2pLs
Ex 8+1 +1 x² || + Yk 22
E2
1 - x² Tx
(16)
Tk 1 22
p(76 -p)
-Blll= h+1 - 211
2(Th- - 22 k)
v1/ p(p 22 k)
Pd
11:it 11 7/k 2A n
BxIl1a k+1 ~0 []
2(71k - 22 - 1)
2 / E&l [| lx xk- TM 11]
p( p)
E4
x 112].
7k
2X
2(7h: - 22 K)
where relation (16) plugs (15) in. A simple re-arrangement completes the proof.
C.2 Proof of Theorem
By the descent property revealed in Lemma 1, we multiply both sides of the inequality by n/- 2A K, telescope over k I,..., K and deduce that
p(p
2\
K)
El| x² 1131
2
p(p
2X-
12)
B Blllat 1$11
2K
k=1
(1/1/ - -E(121 p(7 p) K
7
2A
B lo - 24113
K
2K
K
E[|||a - Tp + 2T. 21,, x -
K
k=1
(7
2X RDD
p( p)
E[ll 111
K
2K
P K
E
7 P
2212 + Allzkt1 =0 112 + 2L 1latt1 - []]
(17)
K
2
k=1
where (17) is due to (x=*) < E& (x K+ ]. Now it remains to bound the error from the stochas- tie delays. Let's first consider applying ||a + blI2 < 2||a|| + 2| to get
K
K
x* 72
< 2
E x
2
E
k+1
111
(18)
18

---

and we can bound the first term using
K
K
1
x
k + 1
24-11
111
1=1
7k
7h
++1-1
2
(19)
4(L f + Lan )
K
(20)
72
where (19) uses the fact | a:ll - k: Σ || 1,, (20) invokes Lemma since (g. x) + w is
(llgil + Iw) Lipsehitz continuous with Egg g 21
I 1.y. and we let = x² if k 2 j. On the other
hand, we bound the first-order terms by
K
TM
B B[[1
E B[[1
1+1 x x
k= 1=0
K
27 -1 (L. + (T +
(21)
k=1
K
2y (L + L K
Σ Tk),
where (21) again invokes Lemma 7. Plugging the bound back, we deduce that
p 2X
x)
Bllla*
- kk |23
2
(7 2X R)D
+ K
E
7-P P II 2/122+ + Al 10 + 2L 11///1//1)
x
K
2
k=1
(7 2X - xD)D
4pL, (Ly + Lw)
K
Spi(Ly + L
+
(Th +1
(22)
72K
k=1
(p 2A)D
K +
D
+
ApL,(L, + Law
Σ
1T++10
K
+1)
8pA(Tsp
+ Iow 2
K Σ
VKa
VK
K
K
K
where (22) is by 7 VK/a+ p 4A + K and cancel the first summation term in (18) with
-IK 3 | I²1 since 7 2 p + 4A. The proof is complete after dividing both sides by
p(p- - 2A- k) and using the fact that 1 211 20 (+)1/()))
D Convergence analysis of DSPL
In this section, we introduce a more general DSPL associated with Bregman divergence and establish its convergence analysis. After proving the result our Bregman context, the Euclidean results in Section 4 follows immediately as a special case.
Why Bregman divergence? Recall that in C1 assume Lipschitz continuity of both and Vc, which does not hold without assuming bounded set. The main issue here is to expect Lipschitz smooth function also be Lipschitz continuous. Using the Bregman context, we can relax such Lipschitz continuity to relative Lipschitzian property, so that we do not necessarily need the bounded set assumption.
D.1 Preliminaries and analysis of Bregman DSPL
In this section, we present the convergence results of DSPL. we mentioned in Remark 4, we replace 1ll regularization by divergence Va and summarize the update in Algorithm 4.
19

---

Algorithm 4: A delayed stochastic prox-linear method with Bregman proximal updates
Input: x²;
for k == 2,..... do and Ve(a g be computed by worker with delay Thi the master node update
Let
x+1 arg min { (e(x g + (Ve(x , (u- x²1) + w(x) + Ya Va(x, mb)}
(23)
end
Now we overload the assumptions used in Section 4.
A1':
(i.i.d. sample) It is possible to draw i.i.d. samples {5*) from E. A2': (Relative Lipschitzian property) w(x) satisties relatively Lipschitzian property (5)
w(x) w(v) S L 2V
A3': (Weak convexity) w(x) is k-weakly convex.
A4': (Strongly-convex kernel) Kernel function d 1-strongly convex.
AS': (Bounded moment) The distribution of the independent stochastic delays {Tr} has bounded first and second moments. i.e., E[Tx] < oo, E[T Ta < co, for all k.
C1': Mx) is convex and Lipssipctitz continuous; c(x, {) has C(f)-Lipschitz continuous gradient, for all & ~ E. Moreover, during the algorithm the stochastic function fe(x, f), E dom is (E)relatte Lipschitzian to d for all E. Moreover, assume [C(E)) S L?
C² (2,Eç|La(5))]
Remark 6. It can be that added extra assumptions the kernel and relaxed the Lipschitz continuity of e C1' and w in A2'. Specially if c is Lipsssiipschitz continuous, we have fz E)
continuous since
(x (v(
M(((2,)) (Ve(2,)),
(Vo(),)))(Vo(,,))))).))) x x 2)) Mc((2,)) + (Ve(2,)).) 2))
< Inl(Ve(2,E),== y)1
s LnIe(E)ll==1)
With the above assumptions, we can further derive a more general version of Proposition 1. Proposition 2 (Proposition 1 in the Bregman setting). Let {f((:E)} be the sequence of stochastic functions queried during the DSPL algorithm, then
Pl:: (Convexity) [2(x, {) is convex, for all E dom and & =
P2': (Two-sided approximation) {xx f(x {]] La Ln E~E.
2112 a1l2.5o for all dom d and all
P3': (Relative Lipschitzian property) (z. f2( (2VVlv)))) for all x, y e dom and all & &~ =.
As we did in Section 4, we take À = L, and use these constants to present the results. Our analysis adopts the conventional potential reduction framework but more careful treatment of stochastic noise is needed improve the convergence result. The next lemma bounds the stochastic noise of the algorithm and is key our analysis of DSPL.
Lemma 8 (Stability of the stochastic iteration). Assume that the assumptions A1' to A4' hold. If fz(: {) is convex and satisfies Proposition 2. then the proximal iteration
x
k+1
arg min ffa va (x, ge..g + w(x) + 7t x
12
20

---

satisfies
21 Ek [E [fae-r (2tt1 [2) - ff (ottt ) (
7 n¹
for any The > K.
Now we can get the lemmas that match our main results in Bregman context.
Lemma 9 (Lemma in the Bregman setting). Suppose A1', A4' and C1' hold, if p > 2A + K, 7k P. then
p(p 2A m)
p(7 p)
- 2A Va(*", ((((",=") S w1/p(=²))
E& E (x
Ex Exlll - 11
2(7h - 22 -n)
3pd
2p123
Ex Sx111 sk- 11²] (7k 16)(Tk 2x 12)
2(7h
2X - k)
Theorem (Theorem in the Bregman setting). Under the same conditions as Lemma 9, as well as A5', taking 7k = = p + 6λ + A + VK/o /a for some a > 0, letting ks be uniformly chosen between I and K, then
1
(x+4X)D
D 2 6pX(Ls + )a² + VKa
[[Va(á x 1
D2
p(p - 2X - H))
K
vK
K
where (x²) i (1x).
Proof Proposition?
(x, inherits convexity from h. The other properties hold by
[f(x, - (x)
[h(c(x, {)) (V v))l
I Ln(c(z,E) -cly.)) - (Vc(y. -yyl
LgC.
s ||. 1e-99 -11²
and P3' is by C1'.
Proof of Lemma
Without loss of generality, we consider the following proximal mapping
A(z, <) == arg min (w, {) + w(w) + + 7Va(w,
where A denotes the proximal mapping from two past iterates 2, x and given sample & &~ E. Then we invoke the three-point lemma to get, for any и E dom d that
(A(,, x, ((A( $
+Va(A))))
(24)
Similarly, given some g' ~ E, domd, we have
x, + (1) +Va zz)
$
(25)
Letting u = A(2,2, 5') in (24) and A(2, in (25), we sum the two relations up and get
< 31ff:::.633-11MM4444444444433343
< BA
(26)
(27)
21

---

where (26) is by Lipschitzness from A2', P3' and (27) uses the relation va+vb= v2va+b. Then this implies
max ( (a(AA2,,, v (. 21.g
- 7-h K
(28)
Last we successively deduce that
f: (2 (dddddd d
// (1 (
E)dedde J Je Ja (A( {²), d'ueue
I (1 Edd SemE (e E), Eddus)
(2, x. E) ( ddueddue Je (A( () (A(22
$ Jer Se- n. () (A(2, x, E) dueduu
(29)
< fews Jev5 Ly max {V Va {), (.)),
(30)
Va(AA x. 8¹), A(z, ()) aadpapp
(31)
242 S -e Je- gーk dugdue 7-K¹
227
(32)
where the third equality holds since & and g' are from the same distribution; (29) follows from
Jensen's inequality and (32) uses (28). Plugging in = = zk- x = zt =k = g and 7 7 into (32) completes the proof.
Proof of Lemma
First, we have, by the three-point lemma and optimality of &*, that
fat-re (, ) + w(1x+1) ++1 78 Va(x**1 k+1 ,x*)
$ fae-re (it, TK- + w(* + 7/ Va 2²) - (7k Va x
and that
f(a*) + w(+ + pVa(á x²)) S f(ahtl) + w(xht)) + pVa(attt1 20h)
Summing the above two relations and taking expectations, we have
(7h E) (V x²0]] (7x - p) Va(a x²) + (TH K)LE VV ..+111
< Egt- Tu 1fat nx (# 5th ck-T)}] - f(**)= + E& (1 -xIfst-re (20 , ,kh-Th)
Eet . 12t 22 (a+ 5 )k- - f(**) + Es [f (t)) - Ex (a (a*+1,,))
+ E& Belf k11 [ - E& 1f,t (2+ (k=1,
S | Th f* 12 + x
2L
By A|l k- Th 122 +
(33)
2
7lk- 16.
where (33) uses P2 and Lemma Next we lower-bound the left-hand side using the 1-strong convexity of kernel d
2 P "Ealllatt x² 20112 (7k - V& x²)) + (7h - -x)= V x+11]]
2
< (m - -))xx 11 .x+²] - (7x Vat x²*) + (1 +x x x+1]]]
(34)
22

---

Re-arranging the terms,
(7k Bx ( xx+1]]++ 7k - -P Bx11ett1 - =011
"xx
(35)
2
213
< (7x- V)Va ,Ith)
EBelllatt1 - =6 + o - 13 + 1
2
7k ni
31
21
$ (*k D)Va((*, ,xx)
+
E&
11
24 ||-] + AE ||| 1/11 + 7h n
(36)
2
31
2
(7x D)Va( ,x²)
E&
||1
xx [1
2XT Va( , rht1)]
7k n
+ +ABal1bbtt - --112 -Va
31
2L
S (7x - VoVa x0"))"""""))))) +
x Th 11 + Ex ||
+ 2 Vo(a", v
(37)
2
7k K
where the (36) uses ||a b11 v 2||a||++||6b| and (37) again follows by Va 11+11 2 111
1*1 Now we re-arrange the terms and divide both sides by Yhe 2A - to get
Ex (a(**, , 1
- 7k- 22 Va(at
7kk
E& Ex[l k+1 - +11 []]]
2(7hk-
22 16)
2L7
31
Ex ||| 1|1. - k 112]
(7h- (7k - 22 k)
2(716 - 22 - 1))
Va(a* .ath) p 22
Va Va(8 x²))
7kk - p
Ex [11100t112 - 11
7k 2\
2(7/K 2x - 15)
213
31
Ex 1| - Tu
(38)
(7h- k7( - 2X k)
2(7k
21
1²)
Now are ready to evaluate the decrease in the potential function.
Ex ExIVi (x+t1)) =Ea1S(akt1) + w(att)) + (Va(t , []]
(E*) + w(at)) + -VV x
S f(tt) + ww(t)) + +VValtt, ,2,) p(p- 22 n))
Va xx
(39)
7x-- - -2A n
3pp
2pL3
R2 11
x² TM 11] + (yx- k:)(Tk -2A x)
2(th - 22 k)
p(7k- - p)
E& 11 - -1a12?
2(1u - 22 k)
p(p 2X - 13)
p(7n - p)
(x*)
Val x²
Ex 111 - 11
7k 2)
2(7h= 2A - x))
3pp Ex 20 k+1
2pT.7
[| (7x - k)(7'k - 22 x)
2(Th - 2 k)
where (39) plugs in the relation from (38). Another re-arrangement completes the proof.
Proof of Theorem
23

---

Summing the relation from Lemma' 9 from k = 1..... K and multiplying both sides by y y 22 ni
p(p - 2 - x)
(V) xx""]]
K
p(p 2A
x)
(40)
K
1=1
7 22
2pL
(1/:p(x0t
Elul//p (x {
K
- n
3pX
p( p)
K
Billx
x
18 [||| x01
2K
2K
k=1
k=1
( 22 K)D
2pL2
+
P
K
E
| k+1
x²1
+
-
37 - 1p] (41)
2 |z
K
7
K
2
where (41) uses the relation vid and recall that we have
(x
K+1)
2 inf (x).
Now it remains to bound the error of delays
1/p
Σ
x k+ x --
112 S
| l 44 + L
(42)
and plugging the bounds back, we have
p(p 2A k.)R( s**')]
(7 22 K)D
2pL2
6pt(Ls L2 K
Σ
TK
K
--H k
72K
h=1
(0 + 4A)D 4A)D
2pL3 D
Gpd(T.g + Tww)
+
A2.
(43)
K
VKa
VK
K
where in (43) we cancel the first summation from (42) since p- VK/a-61- 11a+66++0 + 6A. Finally divide both sides by p(p 2) k) to complete the proof.
D.2 Proof of Lemma and Theorem 2
First d(xx) = 1 ||= 12 satisfies A4'. Since A1, A2, A3, and C1 are equivalent to A1', A2', A3', A5' and C1', noticing that Lemma 2 special case of Lemma and Theorem is special case of Theorem 6, we complete the proof.
D.3 Proof of Theorem
Recall that in the proof of DSPL, actually used A4 and the properties from Proposition 1 that are deduced from A1, A2, A3 and C1. Indeed, it is straightforward to verify that (x( = f2 (). 2) satisfies Proposition 1 given A1, A2, A3 and X-smoothness of f.
E Delay-independent analysis
In this section, we further improve our analysis and show that by adopting simple safeguarding strategy during the iterations.
E.1 Proof of Lemma 3
We show - Tk < mK by noticing the following facts: 1). each iteration there are at most m - agents accumulating I unit of delay; 2). тk must come from a machine's previous delay
accumulation. 3). once the gradient is used, delay on machine starts count from 0. Assuming
that there are no previously accumulated delays on each agent, then we have Σk Th S (m 1)K mK. We use a loose bound mK to simplify notation.
24

---

E.2
Proof of Lemma 4
We know that T
E 1TT 2 T) -
Σ k
k= Th S mK and recall that T = rrrmmmmmm m
K
K
mk
Σ
[T) K - Σ
M 2 TT
K rk
T
k=1
Also we have Σ
Th S T T k= Th S MKT.
k
E.3 Proof of Theorem 4
First we rewrite Lemma by associating potential reduction with 15 [1(T:: S ST).
Ex 10 S w/1/((ah) - p(p 2\ - Ik
p( - 0)1x
|1at
x²112-
Eie (lllllatt1 - x 1/1
2(7h- - 2x x²)
2(T 22 - 16)
pdTx
2plcpTx
E& 11 x² 16 +
1xa 11 x k- 7w
Yk
2x - x
7k 2x - k
where we have x++ = x², thus Eg h////ppp ///11/1(/////// (x=+1)) = = 111/(1=)) if 11 = 0.
From Lemma 4, we know that Σ Ck=1 In 2 K -- = K(1 rk = 17 'K. Then similar telescopic sum over the un-skipped iterations will give
plp - 2A k)
Elllak
x* $191
2
plp 2A k)
Blla* -x011111 111 k=1
2 >
7 2X-
p(7 p)
K
(V1/olx")
{Vi
(x K+11 11
Elei
Ellla h+1 - 1
(44)
Σ Is
x= >
K
Ik k=1
pd
2pLs
K
E -1 x0 +
E
BlIa k+1 - -m
-u [1)T
Σ 1= I k=1
k== k=1
pD
VKD
(45)
Σ k=
K
Ik
0/11 Σボ= Ix
K
E
7
| k+ x²112 12 + AlI - 10 + +T
1| ++1
xx To
Tk.
Σk 1k k=1
2
where (44) uses the fact that 2k y is the same for all the iterations; (45) uses the relation = T
p+ + K + 4A
max / P + K 4A3. Then we bound the above terms, respectively, by
K
pD
pD
MD
(46)
Σ Tt
K
K
VKD
VKD VTD
a²" ΣK k= 1/- S an 1/2K
(47)
VKa'
where we used the fact that Ek= 1t S K. Meanwhile,
2pL.
2pL. K |laht1 - -T lT
llakt1 kT
Σk I k=1
=k=1 In k=l
4 / MpL , (L, Lw
K
E(TH
(Tx + 1)
VKn-
k=1
2/23/2 pL p/2//pL,(0
وLا + Lm)ma
(48)
VK
25

---

where (48) uses tighter bound Σ k= The S (m - 1)K.
Finally, we bound the delays using
K
K
K
2pA
Ellla*
24 1 I
Σ
T
80
Th
SK
Iu
K²
k=1
R=
and that nique as in (18) to cancel the error 2|||=*+1 we can re-arrange the terms to complete the proof.
3 R²
E RE I mKT m² K²
Putting the above bounds back, using the same tech-
rk
2²122 with >i= 27 =fllatt1 x 111,, 7 P 2 41,
E,4 Proof of Theorem 5
We prove Theorem by showing its Bregman version.
Theorem 7 (Safeguarded DSPL in Bregman setting). Under the same conditions as Lemma 9 as well as D1, taking 1) 0, K > /18 2) 3 0, r < 1, then letting " = 7
/K av + K 6Λ, 11=
1 _ some a > 0 and k- be uniformly chosen between iterations where To S VK, then
E[Va(a* xx 1| S 2P--2
1(p+ K
-DD
+
2vJpLia + 6rP2 t. PmPa
VKa
VK
K178
where = (xt) - inf 2 (x).
Proof of Theorem 7
Similar to the proof of Theorem 4, we write the modified potential reduction by
p(p - 2A - T
p(7k =P)
E& (1 (x (1 I w (9/p(a*)
Va x²*)
E& 1x 101
2(7% 22 k)
2(T1k -2 x)
3p2Ik
2 Ik
Bx 11 - k- |2] (7x k>)(Tk - 22 k)
2x 1
Then telescoping gives
p(p 2A- x)
ElVa(ak xx*
p(p
2X k)
EiVa 2
2 2
K
In
k=1
p(7 - p) K
7 2A K
(11/p(01) - Bl13200 (1]
Ell|a h+l
1/
Σx
2 2
Lx k=1
3pd
K
2pI.f
E El[aa*t1
T 112 +
In k=1
7 - K
k=
(0 + D
VKD + 2pLs
(49)
k= IN
a
E In.
K
E
Y-P 11aht1 - x1111 +
7
31
-
| 2² 11
1x
Σ
In
2
kml
(p
4X)D
VTD
2 6nf + I 2 VK
K
KK
-K1-8 3
where (49) reuses (46), (47) and (48). A re-arrangement completes the proof of Theorem 7. Taking
d(x) | completes the proof of Theorem 5.
F
DSPL with momentum
F.1 Preliminaries of DSEPL
Momentum has been an important ingredient for a stochastic algorithm to be implemented in prac- tice. In this section, we incorporate the extrapolation technique into the delayed prox- mox-linear algo-
26

---

rithm. Before the master performs a proximal update, it uses two recent iterates to compute an extrapolated iterate y². Then a proximal update done centered around y with delayed informa- tion. We summarize the procedure in Algorithm 5. Throughout this section we take * = 7-
Algorithm 5: Extrapolated DSPL
Input: _ x! 8;
for k = 1,2, do
Let c(2 Th _ g) and Th g be computed by a worker with delay Thi
In the master node update
y² x² + B(x - 1)-1),
x arg min (Jar-re (2r, (x- w(x) + 1 v 1²
end
To analyze DSEPL, we extend the framework from [5] to the delayed case and the analysis is based on virtual iterate
==
30 300 (x x²" x
where the extrapolation parameter, also known momentum. is fixed at some constant 3 [0,1] and 0 = 1 - B. Using the virtual iterate, DSEPL uses more complicated potential function.
01/a(=²) - (7 - x)02 ((**) + p(7 + 2p330- 2)
pB
||
112
(50)
2(7 - X)0
As extrapolation increases the instability of the iterations, analysis of DSEPL furthers requires bound- edness of the delays.
E1: (Bounded delay) Independent delays are bounded by
The following lemma presents a similar descent property for the potential function.
Lemma 10. Suppose A1, A2, A3 and C1 hold. Given 0 S 3 1, > 3λ + 2xB + n. and y 2 p.
(0 (p-K0) k0)
\v/1/o(=>>11
2p(7 k)0
p3
S V1/1(=²) - E& Ex(V1/0(e (=tt)) + (7 (17-Kpp k))² (v(1** - E& (x
+ p(2p820- + 7:30)
11105 - 11/ -Exlllaht 1/1
2(7 x)02
2pL?
p(702 - -20(p + kB) -2p38-11
pExlEx]
[x[lla x 11
+ (7 2)2
2(7 - x)
(7 x)02²
where En = (AO + -
zk- + A1100 || - 112 characterizes the error of delay.
We next bound the stochastic delay using E1 and eliminate the delays.
Lemma 11. Under the same conditions as Lemma 10 as well as E1, given γ
>
max {pr 2(p x:3)0-1 2p.32-33.
K ElI El x x11
V1/1/000 )12
2pd
(--R+p80-210
+ 1--2
2pL
+
PA(37" +29)
p-m0
K
20"K
where D = max (11///11/002)) - (,xx") -
Remark Lemma reveals the effect of extrapolation. After simplification 1 3 appears in the denominator of the error from delay and will enlarge such an error if 3 - 1. This is intu- itive since when extrapolating using two iterations generated from delayed information, the error magnified.
27

---

By taking less aggressive steps, we bound the term Σx= B11 +1 - -11 and arrive at the final convergence result for DSEPL.
Theorem 8. Under the same conditions as Lemma 11. if we further choose y 2 28 20-1(p + kB) +
220 2B + 3A0 T², then
E / K >l <
2p0
1(372 +
+1)
( (7-K 15=K+p50-0
2013VK
(p KO) VK
VK
(7 - k302
where g'g == -02 -20(p + x33 22p
3X7 - 2A33
Remark 8. I 00==OvVp (). then (3-R+030~110
2pt.
0 /K
0
and
(7-x)62
VR
E V ||
1 K
1
+
K
VK
VK
which implies that the delay is negligible if ol (K111).
Remark 9. Although our convergence result is based on the extrapolated sequence, we can leverage
Lemma 10 to show that E|||=* +1 x² []²] and subsequently ||| x-' x² ||3] xx)). Using
smoothness of the Moreau envelope, we finally have Vill/ k" 21 is 0 VKK
F.2
Convergence analysis of DSEPL
In this section we present the convergence analysis for DSEPL.
F.2.1
Auxiliary results
To show the convergence of DSEPL, we need to define an auxiliary sequence
x 1- 3 (x
x*-1)
Given o², define ā = =3x + +(1- - 3)x for x E dlom(w) and = 1 1-3. The following identities hold
r² 0(x x²)
f 3²t = 0(x )²
x - x k+1 = 0(x - 2111).
and will be used frequently in the analysis. Proof of Lemma 10
First by the (y k))-srongg convexity of the proximal sub- sub-problem, we have
fat va (x+ Tk= + w(x +
| ++1 - 2 21112
2
far-re (5, 5 T*) + (i) + 7
||
112 - 16 -="1 ||ahtt1 -x112
702
(7 (7- x?²
= fa (3, x 7x) + wi) +
x >*
||
(51)
2
2
Also, since fak-re (1 + w(:) + / ||| -x* 2 is convex, we plug in and apply convexity to get that
fa (I, - Th) + ( + # || - x² 112
$ (1 0) [S ( g - + w(x+t) + 0 [ (x,, (K- + w(x)) + K
2 =11= [x1
< (1 0) f. (1" u... + w(x0)) + + f[f(z) + w(z) + = -=122112 1o1 x [2]
28

---

where the second inequality leverages two-sided approximation since faa- (2, - -f(x)) s || x xx
7x
1 Then simple re-arrangement gives
f (7, 5 + w(x)
1 (1 0) [f - =2 ( )) + w(x*))
2 2 21110 x -0
KB2
ff( + w(x) + 2 |oe 2²11²
[1]
1 x²11?
2
Now combining the above inequality with (51), we get that
fa (x 1ogtt1,5hmg rz) + w( + 2 || - 112
S (1 1) (x", 5t gh ) + w(xx)) ) + 0l((x) + w(x) + R2 111 121
- =2
||
x
Tk |?]
kBR
2 || - -0=1111 2²112+ + 70²
2 || - z 1| (7 - x))
2 || 1
(52)
From now on let x zh in (52) and successively deduce that
Sah-r (x k+1 :5 sh- + ( + 1 ||, 12/12
S (1 - 8) [fak-r (x" gh- ) + w(z")] + +0 ff(((2)) + w((1)
+ K 2
-
112 + 2 11 - x xm 112
2
kB²
112h x²112++ + 782 1 - 2/ (7 - ==)02
11 111-
2
+ kl x02
10
(1 - 0) [f ve (a* (5 5 + [[*) + ( + w(sh)]
1k x² 112 + 2 112# 22 1|2
2
+ 2 11sh - x11 - ( k2)2
702
1/ -
2
$ (1 - 0) [aat-r ghhrr + w(a0)] + *1(( + +w(+t)] + 20
11 - 102 112
2
+ 2 11 - =21/2 (7 - xx> 2 22 + 0mp3 110 2²12 + -1 1|2)
70
(53)
2
<(1 0) [fax re ( 5k-oe) ) + w(20)]] + +f(f(**)
+ w02 (2*))] + (1:B + A)Il - 2122
702
- || - 111 (*=x)6-
+ 1011z - - 1|a +
|| 1* - 2 ++ 1|2 + 01 - 11,
2
2
(54)
where the second inequality (53) applies || - x²112 < 21||=*+1 - 12 + 11
x² 11 and the
last inequality applies ||2* - T 1 < 21(2* - x 2 + 2||2*+1 x 1|2.
By definition of Ek, for p > A A K. we have (0 (0-2- x - w)-strong convexity of (/xx) + fll --] and
f(at) + w(*h) + G1 - 2112
< {((+t)) + w(thtt)) + fllahtt =011 p-
x
| 1a 1/122.
(55)
2
Multiplying (55) by and adding it to (54), we have
2
2 1112/11 y²1 12
< (1 0) [Saa -r (x**, , ck- + w(xx)) + +0((a*+)) - fae-m (a ( )h- - (1 ()
+ 00
|+1 - =11 0(p 31 2x3 x))
||aht11 - 22122 + 2011u x 112
702 p0
1|2 211 (7 - kx)22
2 - 2 + 01:5ll ++ - 1!1
(56)
2
2
29

---

Then we bound the first line of the right hand side in (56) by
(1 11-61 0) [Sa (e -5 -h ) + w(**)] }] + (x - f2 (xt =m) - (1 - ()w(x
S 5 (1-00) 5 m) + w(-") - f (( - w(x +1 +1 + f(x - 1E. [fat in (cttt) [0]
(1 - 0)1
+ EE |5at (2 [E]l - far- (2tt11 1 r)) +
2 |, - =x====1² 112
+ 21.
s -00 (00 ()) + w((x)) - [(ahtl) - w(ahht))
+ A - 11 - + (1 - -0)1l(* 1111 2
(57)
where the inequalities invoke two-sided approximation |sat-ra (ath gd- Matt, ) S 311 E11e** - 12 and bound Eg [far- (a**t, - sa--1x (2tht) , Tk- with Lemma 8. Now plugging (57) back into (56) gives
-112A11- - -12
2
$ - (1-0) (xt ekh + w(x - [(aht1) - w(tht1]] +
7
+ 00 |1 k+1 - -/11 0(p- 31 2x8 -x) 11a - =112
+ 002- - -p 11sh - -2/12 (7- - k2
11 - - +
- 1/1
2
2
+ (A0 + 2)
A(1 - f)
2 -
- x 1| +
2 | - x 112
(58)
Isolating the delayed error by EN (A0 + 2) ||akt1 x 12 + -(1 have, by algebraic manipulations of the momentum terms, that
2 1| x 1|2 and we
|
1²112=
|| x² x² y 1|2
2 k+1 - 2²112 + 8 x - x z²-1 112 -511 k+1 -
-x²13 111 2 - 3112** 11
0|| z²1l - 301 - x 112
(59)
and that
p0 || - 1 < 101 - 112 +
112
(60)
2
Combining (59), (60) with (58) and taking expectation, we have
70
7:30
2 Ex [|a - 2²1 [1]]
|| -
x
2
2T,
< (1 0)(bb(*)) BN (2x
+111
7- k
+ (p + +3)00x([100 k+1 - 10 + -,320-111 '1,0** - 1 0(p - 3A 2x,3 - x)
Bx
Bx[11 11 - -391
2
+ 0 - p0 1 212 (x x2)
ER || - - + Ex Ex[ex].
2
After re-arrangement, we arrive at
(7- x)0
Exll 2* 2111
2
702 p0
< (1 (1b((())
E& (1
+
11 2112
2
+ (0130011 + 2:50
0(p- 3A
2nrB 13)
2
12
E&
(1
x* 1111]
En [||a k+1 - =$113]
2
213
702 20(p + xxB)
2p
ER.
[1
x² [11] + Bx(ex]-
(61)
7 K
30

---

Dividing both sides of (61) by (r=x)0²
2 we obtain that
E& |1 = [12]
2(1 0)
70 - p
(7 k:)02 (xb(2r²)
[x(
+
(7 x/) 11 =111
2p 0- + 7,30
P -3 2x.3
111 ---- 112 Es 1x xx11313
18x [1 =X]]]]
(7- k))2
(7 =x)0
413
702 20(p p + k:3) 2pp3001
2E [Ex]
+ (7 x)202
1x11 111 11 + (7 xx)0²
- (x=x)
= 11 - 112 p-k8 k0
11 - + (x- - k0)= (0b(2²) - -E& [E((bba
233
(7- - k)0
2p 0- + 7/30
{11 - - Ex 55 k+1 - 2111/13 P p- 21:8
+
E& Ex - -2 101
(7 x)02
(7 =n)
112
702- (p + kB}) -21
2B [=x]
- 101 E+ll=*+1-
(62)
(7 22)
(7 22)2
(7 k))
Next, we consider the Moreau envelope and
=Ea (((ttt)) +
L plistt - - 1
2
SEn [s(st) w
- 12]
+
s f(2*) w(+t)
2 11aa 111 + (7 1:) 02)
P
P3
(1(a*))
Bx (=(
p k0)
2112 + p(2p320 + 730)
1|
E11:0h -11=0~ -0--112 Ex -1
- 113
2(7 - k))0
2(7 K2
2p13
p(702 20(p + k:3) 20320-11
Ex |11| M+ - x* [|3] + pE (=x]
+ (7 x)202
(63)
2(7 -x)02
( x)
P8
= -;1 +
(7- k2)2 (vb(a²) - Ex (zx
p(p - k8)
11 112 + p(2p320 0 81 + 7180)
{1120 - -x 22-1 Ex ||| k+1 ,² 11
2(7 - k)0
2(7 x)0
20L3
p(702
20(p + k. 2p.32-11
E& Bx - x 1| + [
+ (7 x22
(64)
2(7 K)
(y x)02
where (63) uses the relation from (62). Last we re-arrangement the terms in (64) to get
plp k0)
2(7 x)0 1 x
pB
$ <///o=>>>- - -E (all11//(200 (o
+ (7- x=0= (W(at) - Es [x((
822p + 730)
[11a* 1111 - 1113
2(7 - x)02
2pL3
ph102 - -20(p + kB) - 221320-11
a [1] + p
(r 22
2(r k2)
(7 x)02
Recalling that || VV11 1²11 - =* 212 we complete the proof.
Proof of Lemma 11
31

---

By Lemma 10 we have that
p k0
2p(7 k)0 11 - 111
P3
S ))/0(=²)) 1 (2(+1))
+ (x x)]0 (V-k)02 (1(aa)) - E& (x((b(
0(2p + +7,30)
(112 - -Bulllttt - 1/1
(65)
2(7 - k:)02
2pL?
ply - 20(p + kBB) 2p BA 11 xx1]
pl [Ex]
(7 - K)202
2(7 - k))02
(7 x))0
Summing up the inequality (65) from k == 1 to K, multiplying both sides by y + K > 0 and taking expectation, we have
P K0
BIL VIIVvi//
)121
2p0
5 7 (V1/p(z))
1 -Eulvr/0(2 K+1 }|}
+
02K (v(x²)
p3
- En (x
p22p800 1 + +7,0)
2p137K K
K
+
|| =2012- 12+ +
+
BlEn]
202K
(7 x))
02
p(702 - =20pp + kB) -
R Blllattt1
x
2
(7 + --88-222 2)D
2pI.3
K
P
E[Es]
K
(7 - xx)02
02K
k=
p(702 20(p + k,3) 2p
K
B||laht-- k+1 - 111
(66)
202K
k=1
where the last incquality uses x x and D= = max max(v - =//1/(=))), - divide both sides of the inequality by
- (xx))} Now
p-n6 to get 220
E Vebiole 1 (11
2p0
(7- k + 030-2)D
20L
p
Σ E
+ (9 - k)82 +
K
0²K
k=1
Last we bound Ek E[Ex]. First, we have the following relations
k
|| h+1 k- TA S 2
100
k
112
1a ktl xx x11
A=1
where the first inequality is by E1 and the second inequality uses the fact that x00 xr. Similarly
K
K
a h+1
x r2 12 =
2
* - 122 + I|a 101
1=1
K
2(( + 1)
1 +++ - 2²1
k=1
where the first inequality uses ||a + b12 < 2||a|22 + 2| and the second inequality re-uses the bound of the first term. Plugging the above bounds back into Σk1 [[ss], we successively deduce
32

---

that
K
K
1(1 -
8)
[[s
Σ 1=1
11
x
8880 1? +
00 + 1/2) R+1
[1]]
2
km
1((1 0)( +1) (0 1/2) x
B Blll - - 1111
R=1
K
1(372/2 + 3)
B1|l2 k+ - -1
which implies
Elll ViVi1ppp=" )1
2p8
(7 - p:00
+
2pT.3
+
pA(3r2 + 223
Σ
El|l EllI - x 2$1
(67)
p- k0
K
(7 02)
202 K
1mm
and this completes the proof.
Proof Theorem
By Lemma 11, remains bound the quantity Σx the relation in (66), where we have
To this end we consider E E[ 111].]
p(102 20(p + k3) -2p320-1
3xT² 2 -219)
Σ
[|[|a x 1
202 K
(7 - p30 2) 2pL?
(4 k))6²
Since we choose B, such that 702 - -20(p + +x²3)= - -2p320-1-23 -3 - 22,3 > 0, then
1(3 + 233) {
[T 2)D
2pl.
pA(3>2 + 23) 202K
K
Bllaa k+1 - < 702 20 + k3))
K
+ ( ko-k)00
22p
3A-² 22,3
Plugging the bound back, we have
Vibl//// [1
2p0
(7-6 K + D33-22D
2pL7
A(372 + +33
( x 2,12
K
+ (--xx00
2pL
<
+
p k0
K
( k)02 702 -20 x3)
2p - 3A- - 2X3
This completes our proof.
G Kernel and subproblems
In this section, we delve into the practical considerations related to Bregman proximal methods. In particular, we discuss how to construct suitable divergence kernels for DSPL so that commodate non-Lipschizzness of the objective function. We also propose efficient subroutines for solving Bregman proximal subproblems, which applicable to wide range of loss functions typically encountered in machine learning tasks.
G.1 Choosing the divergence kernel
The selection of the kernel function is a critical aspect of the Bregman proximal method. The choice of kernel has been widely discussed the literature [3, 6). and we incorporate these findings to construct suitable kernels for the DSPL method. Given the assumptions we have made throughout the paper, suffices to consider kernels d(x)) ([][])) Σ | which are degree-n polynomials in ||æ||. We recall the following lemma and refer the readers to [3] for its proof.
33

---

Lemma 12. Given f(z) such that [())-((y) I PR(IE=])) + PR(lelI) Ei=oPa Pa(l| + 1---1l
Iyvl"), p 2 O, Vo E dom ht then f satisfies 1-relative Lipschitzian property with kernel d(x) 3k47 R+2 Pk ||//////
Ex=o
The above lemma implies that once we establish polynomial upper bound on the Lipschitzness of {x, + w(x), kernel d is immediately available.
We note that the above kernel covers most of the applications [2] of the prox-linear method, in- cluding phase retrieval, blind deconvolution, matrix completion, covariance estimation, robust PCA, and on. In many machine learning applications, has Lipschitz continuous gradient, meaning that Vc is bounded by first-order growth. For example, in the phase retrieval problem, we have |x), c(x, { (a, x) b. Hence, get
0, h(x)
fx( - f2(U.E) < |||a||/|=||
V|Vc(z, O)l = a,, 2) ||a|| s 2) |||||| and
10- yl1
Now assume that 2 = 2, then for any Po 2 and P1 = 2a 2a²,a = supa~z |a|l we know that
||||||/||>||| S Po + Pi | Hence, we can take d(x:) 1| + 100² || as our kernel. Recall that in DSPL = , x x² as long there exist some M, N such that |||' s M for all k, our assumptions are satisfied.
M| || N
Now that we have specified ways to construct kernels for DSPL, we discuss how solve the Breg- man proximal subproblems in the next section. The subproblems solution determines the practical applicability of our methods, and we show that these subproblems can be efficiently solved for wide range of problems.
G.2 Bregman proximal subproblem
In this section, we discuss the solution of the proximal subproblems for DSPL when w = 0, where the Bregman proximal subproblem can then be expressed
min h((a,z) + 6) + Va(æ,, v).
(68)
Consider a piece-wise linear h(x) = max(aj + 31, a2 + 82). This formulation characterizes common nonsmooth loss functions including loss |æ|| max(x, -x} and hinge loss max x). Substituting h in and removing terms irrelevant to æ, we arrive at the following DSPL subproblem.
min max{ (a1, x) b1, (a2, 2) b2) + d(x)
(69)
The next proposition provides a solution to the above subproblem.
Proposition 3 (Solving the proximal subproblem). The proximal subproblem can be solved by eval- uating solutions to the following three problems
min (a1, d(z),
min (a2, d(z),
and
min 2
(01, + d(z)
subject (ar - 0z 2) + bi b2 O,
where the solution to the third problem satisfies x = u + av, where u (a) (bp
V
aa 02
[[a,]] -//0]]1]]) (01 az) 91-02 and is a positive root of the following equation
2|[a: 22ll
Σ Prallu u + avll*
0.
Proof. Recall that are solving the following convex optimization problem max((a1, æ) + by, (a2, x) + b2) d(xx,,
min
2
34

---

where d is strongly convex and thus the problem admits a unique minimizer z". Then we do case analysis.
Case 1. (=), bi (az, x²) + b2 In this case solving min .r) + d(x:) produces x². Case 2. (a1, ²") + 61 < (az, x²) + b2. In this case solving ming ma2g z) + d(x) produces x".
The above two cases degenerate into the subproblems from stochastic mirror descent and its solution has been discussed in [6]. The last case is bit more tricky.
Case 3. (a1, x²) )- + b1 = (a2, + b2.
In this case, the proximal subproblem becomes an equality constrained problem.
min (a1, + d(x)
subject
(a--as) -2,-2, .) + bi b2
Letting be the multiplier of the equality constraint and appealing to the optimality condition, we have
01 + Vd(x)) A(a1 - 02) + Vd(x)) A(a) 02) 0 (al - 02, 2) +b b
(70)
(71)
(72)
Summing (70) (71) and dividing both sides by 2, we have a Vd(x) X(a1 02) O.
(73)
Multiplying both sides of (73) by 01 - a2, we arrive at
|| ||2l| + (a1 02 Vd( + a|Ia 02ll = 0.
(74)
2
Since d(x) is a polynomial in ||>||| Vd(x) (x. and using (72), we have
X =
| Te--a-
bط C
2 a2
-
(75)
Then substituting À into (74),
0 tat Vd(x) + X(11 a2)
tat + (x (0)- 22) ba)
|| -|all1
(a. a2)
2 -02 1
= ( x + (a= [0) (b)=b2)
|0
||02
(01 a2) +
01 +22
||a| -22
a2 2|
12
we get
2 5
[Ile: || |a2||
(a1 02)
ag tag
(a: a2 (br b2)
2 01 02-o2 021
2
||o] [ai-a2] 1
for some >>0 O. Without loss of generality, we express x ov for
(a) - -ag) (bn and
1ai-as 12
v
[laa
2 2 (a1 - (2) - = and a > 0. Substituting back gives ( Et= Ph ||=||| and
3 |all
[[<( - u) w| = |lar - w|| loς - 1| |||||| = 0.
o Therefore, we only need to verify the positive roots of Σ Paa u| + awill* - = 0, which can be done efficiently if n is not large. This completes the proof.
G.3 Euclidean subproblem with nonsmooth regularizer
In this section, we discuss the solution of the proximal subproblems for DSPL when d(x) = 1 |
and w takes on one of two forms: 1). Indicator function of ball 8 [[ 2). & regularizer | We still assume h(z) max maxfajæ
x aazæ 31, az2 + }2), which covers all the popular applications of SPL from [2, 4J. Following the same argument as in the previous section, each DSPL iteration is reduced to
min max{(a1, 2) + by, (az, x) + be) + w(x) + -11 y/1
x
35

---

and after doing case analysis on (a1, + b1 and (a2, x²) + by as in Proposition 3, it suffices to solve
min subject to
w(x) 2112 yll2
(a,x) b 0
efficiently.
Case 1. w(x) ([)])R)) In this case, we need to solve
min subject to
|| - yl
(a, =
||m||
R2
whose KKT condition is given by
(a, x) = X
M(|[= - r)
y + va + 2λx = 0
After simplification, we arrive at
y
(a, 1) (1 + 2A)ba
+ 2A
+ 2
Then either À 0 or the solution can be obtained using bisection.
Case 2. w(x) = ||z||1. In this case, we need to solve
min subject to
| + -/1 - y112
(a, - -b=0 0
Given the Lagrangian multiplier v associated with the equality constraint, we have that a(v) Syy va), which is given by the soft-thresholding operator. The residual of the equality constraint given by:
f(v) (a, = (a, x(v)) b.
This function is univariate in v and is semi-smooth. Therefore, semi-smooth Newton method can efficiently find its root. This makes the computation tractable.
H Additional experiments
In this section, we present additional experiments incorporating momentum. Our experiments focus on both robust phase retrieval and blind deconvolution problems.
H.1 Robust phase retrieval
We refer readers to Section 6 for the detailed formulation of phase retrieval. Most of the experiment settings in this section are consistent with Section
H.1.1 Experiment setup
1) Initial point and radius. For the synthetic data, generate o' NN( and start from
o xl | and for zipcode data, we generate x' N I,)) and take の x x'
M 1000||>"||.
36

---

2) Stepsize. We tune the stepsize parameter setting = VK/a, where {0.1, 0.5, 1.0) in the asynchronous environment, a E [10-2, 100) for synthetic data in the simulated environment and a [10", 100] for the zipcode dataset.
3) Momentum parameter. In the asynchronous environment, we allow E {0, 0.1, 0.6] and in the simulated environment, test B {0.6, 0.9) for the synthetic and zipcode data respectively.
4) Others. Other settings are consistent with Section 6.
H.1.2 Asynchronous environment
10
107
DIED 2-3
DSEPL mookers
DSEGD p-31
DSETL morkers
10
DSEGO p-3
12
DSEPL
DIEGD d-
00111 werken
10
20
20
Figure 6: First: speedup in time and the number of workers. Second: progress of || first 40 epochs given 16 workers and a = 0.5. Third: progress of f(**) - (z) in the first 40 epochs given 3 0.3 and different number of workers.
2|| in the
The first figure plots the effect of different momentum parameters in the distributed environment. It can be seen that both DSEGD and DSEPL perform better with momentum. Moreover, the performance of DSEPL dominate DSEGD observed in the previous experiments.
H.1.3 Simulated Environment
DSGD CSPL
10
OSGD
DSCO DSERL
DSPL
DSPL
XX-X-
327
107
38
30?
167
10
Figure 7: Left to right: (Ns, Pta)) = (10, 0.3) = 5.0, Geometric and Poisson delays; zipcode
data of Pfail 0.2,o 6.0, Geometric and Poisson delays. x-axis represents Tmax and y-axis shows average iteration number to reach the stopping criterion over 20 tests.
Figure plots the impact of staleness on the number of iterations each algorithm takes to reach the desired accuracy. It can be seen that with other parameters fixed, DSPL tends to be more robust against delays than the pure subgradient-basse based methods, which consistent with the theoretical results. Moreover, we observe that when extrapolation is used, the algorithm converges faster at the cost of less robustness delay increases.
Our last experiment investigates the robustness of DSPL compared to DSGD and justifies the use of extrapolation in presence of delay. Figure 8 plots the number of iterations for each algorithm to converge with different datasets, extrapolation parameters, and delays. spite of delays, DSPL and DSEPL still admit a wider range of stepsize parameters ensuring convergence than DSGD, Also, when the stepsize not large, the use of extrapolation can effectively accelerate the convergence.
H.2 Blind deconvolution problem
In this section, we present the additional experiments on blind deconvolution problem to further illustrate the efficiency of DSPL. The blind deconvolution problem, unlike robust phase retrieval,
37

---

DEGD
D5G0
DOGD DSEGO
O
DDEGO
DEEGO
DEEGO DIGPL
1.S.
DSEGD
DSEGO
D6EG0
0.5
0.:
38a 10 32.
10
10'
10'
Figure 8: First row rww (Geometric) left: (x, Pma)) = (1, 0.3), 8 0.6, E {28, 47). right: zipcode
Prail 0.3, 8 0.9, (28, 600). Second roo(son)n))) left: (K., Psat) (10, 0.6,
(28, 47). right: zipcode Plat = 0.3, 3 0.9, r E {28, 600).
aims recover two signals from their convolution and its mathematical formulation is given by
min ZEERR M
(u,, - b.l + I|| Illll = A}.
where } are the measurements, {(u,, v:)) are the measuring data and are the optimization variables corresponding the signals. Similar phase retrieval, first present the detailed setup and then inspect the performance of DSPL in both real and simulated asynchronous environments.
H.2.1 Experiment setup
Data generation. We use synthetic data for blind deconvolution problems.
Synthetic data. We take 1500, n = 150 in the asynchronous environment. The data is generated similar to phase retrieval, where, given some conditioning parameter 2 1, compute U Q2 V Q2 Q Rmx" 9ú ~ NN 1) and generated like è in phase retrieval and we random corruption is applied.
300, 100 in the experiments of simulated delay and
diag(d), d E IR", d, E [1/K, k. 1), Vi. Then two true signals are
1) Dataset. In the asynchronous environment, we set K 1, Phai 0 and in the simulated environ- ment, we set and Prail 0.3..
2) Initial point and radius. We generate z',y' ~ NO0 In) and start from x. x² 11 8d
y y ||'l| A (0000](=0,,')1)
3) Stepsize. We tune the stepsize parameter setting y /K/a, where {0.1, 0.5, 1.0) in the asynchronous environment, a E [10-2, 10'] for synthetic data in the simulated environment.
The rest of the experiment setup are consistent with in phase retrieval.
H.2.2 Asynchronous environment
The experiments for blind deconvolution again justifies the effect of DSPL in its convergence behav- ior and robustness to the stochastic delays. By retaining the smooth structure of the inner composite function, DSPL gives a more accurate approximation of the original objective function only at cost of transmitting one more scaler (i.e., the inner objective value). Hence DSPL serves as competitive alternative to DSGD when the problem enjoys composite structure (2) in the distributed setting.
38

---

10
107
SPI
300
DGGPL
0000L
00CPL
66560
DGEPL
100
DCEPL
ECEG0 1o wortera
10"
Figure 9: First: speedup in time and the number of workers. Second: progress of [1 ,8) (t. 01 in the first 40 epochs given 16 workers and a = 0.5. Third: progress of f(=t,2"" first 40 epochs given / = 0.1 and different number of workers.
224) ) - f(, 2) in the
DSGB
DISPL
03:0
D5GD
DEEGO
DSPL
DSPL
DSPL
Figure 10: From left to right: Pna)) (1,0.2), 4.6, Geometric and Poisson delays; (K, Pran) = (1, 0.3),a = 2.1, Geometric and Poisson delays. The x-axis represents delay t and the y-axis gives the number of iterations reach the stopping criterion.
H.2.3 Simulated environment
In the simulated experiments for blind deconvolution, we can see similar robustness of DSPL against delay and stepsize selection, which confirms our previous observations.
H.3 Proximal sub-problems
This subsection shows how the sub-problems from DSPL and DSPL are solved for completeness. The results are direct adaptation from [1] and interested readers check [1] for the detailed derivations.
Phase retrieval problem In phase retrieval problem, denote to be the point where the stochastic model function constructed and y to be the center of the proximal term. Then the DSPL proximal subproblem given by
min xa,
x)² + 2/a, 2) 2) - bl 61+ 2 yll
and it admits dosed--orm solution when away from the boundary
x+ = + Projj- Tड| )s:
where 5 = > 2)² + 2(a, 2) <) x - 2) b) and Ç = 2 (a, z)aa and Proj denotes projection onto the box [-1, 1].
Blind deconvolution problem In the blind deconvolution problem, use (zz: 2y) to de- note the point of model construction and w (We, wyy to denote the proximal center. Then the subproblem given by
min |
(u,, = (v, =y) (v, zy) (u, x- 2n) (u, 2x) (v. zny) b|+ 2 ||| w. 12 ||y wy [13]-
First we assume that the constraints are inactive, then the solution is available in closed form at w Proj (11) - )
39

---

DEGB DSSIL
D6G0 EREGO DSEPL
8660 SSPL 0GEPL
D6G0 DOPS OGEPL
Figure 11: From left to right: (k.,Pra) (1, 0.2). Geometric and Poisson delays with 7 10;
(6,, Prat)
(1, 0.3), Geometric and Poisson delays with 216.
where
8 = 7- Ku, (2, (1,, zn) + (v, (y, (u, wz - 2x) + {u, 2x) wy =zy) -
< = <=> uy (u, 22)
H.4 Separate figures of Section 6
BSOD MERE ESGO sostee
DEPL bunken DSPt nars
06CB Sorree
550 nertor
BASIIE to opteal
dSc0 mar
banction vakan
2001 10 varten
Dibarce
10'
Nambor of Epoochs
Mamber of opacks
Wamber spechs
Rhmmber of opopeh
Figure 12: Figure after splitting DSGD and DSPL. Two plots on the left: || all in the first 40 epochs given 0.1; two the right: f(**) f() in the first 40 epochs given 0.5.
References in the appendix
[1] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-233 2019.
[2] Damek Davis and Dmitriy Drusvyatskiy. Graphical convergence of subgradients in nonconvex optimization and learning. Mathematics of Operations Research, 47(1):209-25 231, 2022.
[3] Damek Davis, Dmitriy Drusvyatskiy, and Kellie J MacPhee. Stochastic model-based mini- mization under high-order growth. arXiv preprint arXiv:1807.0022 2018.
[4] Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal on Optimization, 29(3):1908-1955 2019.
[5] Qi Deng and Wenzhi Gao. Minibatch and momentum model-based methods for stochastic weakly convex optimization. Advances in Neural Information Processing Systems, 34, 2021.
[6] Haihao Lu. "relative continuity" for non-lipschitz nonsmooth convex optimization using stochastic (or deterministic) mirror descent. INFORMS Journal on Optimization, 1(4):288- 303, 2019.
[7] Tyrrell Rockafellar, Convex analysis princeton university press. Princeton, NJ, 1970.
[8] Siqi Zhang and Niao He. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXiv preprint arXiv: 1806:0880007788 2018.
40


Reviews:
[{"review_id": "QAUvc0Kxtm", "reviewer": "Reviewer_bGwb", "summary": "The authors study a class of weakly convex optimization over a distributed network under the presence of delayed derivatives. They first analyze an existing algorithm and show that they can improve its complexity bound in terms of the dependence on the properties of the delay. They further provide another algorithms and show even a more relaxed bound dependent on the delay. ", "questions": "It seems that one of the reasons to get a better dependency of the delay, is to have direct assumption on the stochastic functions and not the expectation ones. The authors need to clarify this.", "limitations": ".", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors can improve the complexity bounds in terms of their dependence on the values of delay.", "weaknesses": "Assumptions B1 and C1 seems to be much stronger than the ones in the existing works as they have been made on the stochastic functions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to reviewer bGwb**\n\nWe thank the reviewer for the time spent reviewing our paper. \n\n**Question**. Assumptions B1 and C1 are much stronger than the ones in the existing works; The reasons to get a better dependency of the delay is to have direct assumption on the stochastic functions and not the expectation ones.\n\nWe understand the concern of the reviewer on the assumptions, and our original intention was to put emphasis on the delay itself in a clean and reader-friendly manner, so that enough intuition can be established. In a word we can make standard assumptions (as in [1]) by a few lines' modification of the proof, giving a slightly worse constant in the final results. And we kindly refer the reviewer to our global reply for more details.\n\n**References**\n\n[1] Xu, Yangyang, et al. \"Distributed stochastic inertial-accelerated methods with delayed derivatives for nonconvex problems.\" *SIAM Journal on Imaging Sciences* 15.2 (2022): 550-590."}, {"review_id": "NzTVA3faLf", "reviewer": "Reviewer_Ld2g", "summary": "This paper studies delayed stochastic algorithms for weakly convex optimization. For a general weakly convex problem, the authors provide a sharper bound that improves the max delay in the previous bounds to \"average\" delays. For a weakly convex problem with a composition structure, they propose a variant, DSPL, of the delayed SGD (DSGD) by only linearizing the inner function and provide a convergence analysis. Moreover, they propose variants of DSGD and DSPL that are robust to arbitrary delays by checking if the delay is too outdated. Finally, they provide some empirical results to support their theoretical findings.", "questions": "1. Could you add labels to the axes in your figures?\n2. The right two figures in Figure 1 are impossible to parse given that many curves are very close to each other. I suggest you split each of them into subplots. For example, you could have a subplot showing DSGD 1 worker v.s. DSPL 1 worker, one showing DSGD with different workers, and one showing DSPL with different workers.\n3. The two types of delays in Figure 2 are not defined.\n4. In Section 6.4 it is claimed that \"upon discarding outdated information, DSGD exhibits much greater robustness\". How to see that from the plots?\n5. The bound of DSPL also has the $\\Delta_2$ term. Why is it robust to your adversarial delay? Does that mean your bound could be improved?", "limitations": "Yes", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. I'm not an expert in this literature but the work seems to be technically solid and make a significant contribution.\n2. The paper is very well written with enough intuition and discussions given after each main results. I enjoyed reading it.\n3. The theoretical results are strong and supported with empirical evidence", "weaknesses": "The experiment section seems to be rushed. I left a few questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer Ld2g**\n\nWe appreciate the efforts the reviewer puts into the review process and thank the reviewer for acknowledging the novelty of our work.\n\n**Questions**.\n\n1. Add labels to the axes of figures and split the figures.\n\n   We thank the reviewer for the suggestion and we are glad to add the axes to the figures.\n\n   As with splitting Figure 1, we would put this in the appendix due to page limit. \n\n2. The two types of delays in Figure 2 are not defined\n\n   We kindly refer the reviewer to our experiment setup 5) (Line 284), where we briefly discussed the two types of delays. But we'll add more details on how these delays are generated.\n\n3. \"upon discarding outdated information, DSGD exhibits much greater robustness\"\n\n   Sorry for the confusion, we intended to mean \"SAFE-DSGD\" exhibits greater robustness, as we can see from the convergence plot\n\n4. The bound of DSPL also has the $\\Delta_2$ term. \n\n   We interpret the reviewer's question as \"DSPL, even without safe-guarding step, still performs well in practice\". Indeed, in our experiments we observed that DSPL is only slightly inferior to SAFE-DSPL. One explanation is that our starting point is initialized within a ball, which itself is not that far from the optimal solution. Therefore updating with information of $x^0$ will not badly hurt convergence of DSPL. \n\n   In other words, while the delays are generated according to the worst case, the problem we optimize is not.\n\nWe again thank the reviewer for the efforts in reviewing our paper."}, {"review_id": "Z5qz6Tz7H0", "reviewer": "Reviewer_SDCr", "summary": "This paper presents DSPL, which is an optimization for a certain structured weakly convex problems. This algorithm can work with arbitrarily delayed updates, and outperforms existing algorithms in both theoretical rates and numerical experiments.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The algorithm is robust to arbitrary delays. The robust rate doesn't rely on $\\tau$.\n2. The safeguard is a simple procedure, which makes it more practical.\n3. The authors conduct numerical experiments which showcase the effectiveness of proposed algorithms.", "weaknesses": "1. The authors compare the proposed algorithm with some non-convex algorithms. Is this paper's setting inherently simpler than nonconvex optimization?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer SDCr**\n\nWe thank the reviewer for the efforts put into the review process.\n\n**Question**. Is this paper's setting inherently simpler than nonconvex optimization.\n\nThis is a good question, and we would like to answer the question for SGD and SPL respectively. \n\nFor SGD, it is known that general weakly convex problems are a subset of locally Lipschitz continuous nonsmooth nonconvex optimization, and it is more diffIcult than the convex or smooth case, since smooth nonconvex optimization with Lipschitz continuous gradient is a subset of weakly convex functions.\n\nFor SPL, it deals with weakly convex problems with composition structure. This setting is a subset of weakly convex optimization with broad applications from machine learning. And it's still harder than smooth nonconvex optimization with Lipschitz continuous gradient.\n\nWe would like summarize the difficulty of the settings as follows.\n\nSmooth nonconvex (DSGD) < Structured Weakly convex (DSPL, ours) <  Weakly convex (DSGD, ours)  < Locally Lipschitz Nonsmooth Nonconvex (no result to our knowledge)\n\n\n"}, {"review_id": "3I4NZb8kCA", "reviewer": "Reviewer_6vL5", "summary": "This paper studies distributed nonsmooth optimization with delayed updates. The authors study two kinds of objective functions, the first class is the sum of a weakly-convex nonsmooth function and a computation-friendly nonsmooth regularizer, while the second class is the sum of a composite function with a regularization, where the inner function of the composite function is smooth. For the first class of functions, the paper improves the results in Reference[1] by replacing the maximum delay with the expected delay and the second momentum of the delays. For the second class, they propose a prox-linear algorithm that can further get rid of the delay in the dominant term of the convergence rate. Convincing numerical experiments also demonstrate the effectiveness of the proposed algorithms.", "questions": "* Is it possible to generalize the inner function of the composite function to a mapping while the convergence rate remains invariant. \n\n* I would like to know about the maximum magnitude of numerical errors in the solutions to the subproblem in Algorithm 2 so as to keep the convergence rate invariant.", "limitations": "I am not aware of any potential negative social impact of this paper.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* the delay in the dominant term is removed for the composite functions where the inner function is smooth. This is the first result to remove the dependence on the delay in the dominant term for nonsmooth and nonconvex functions.\n\n* for weakly-convex nonsmooth functions, the maximum delay in the convergence rate is improved to the expected delay. \n\n* the presentation and structure of the paper are quite clear.", "weaknesses": "* for prox-linear methods, the inner function is usually vector-valued. I would like to know whether it is possible to extend Algorithm 2 to the cases when the inner function is a mapping while the convergence rate remains invariant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer 6vL5**\n\nWe appreciate the efforts of the reviewer in reviewing our paper.\n\n**Questions**.\n\n1. Is it possible to generalize the inner function of the composite function to a mapping\n\n   Yes. Our analysis actually can be directly extended to the case, where function $c$ is replaced by $C$, almost without any modification. The only difference is that we have to replace the properties (e.g., Lipschitzness) of $c$  by the counterparts in mappings. We adopt function $c$ to make our notations consistent with DSGD.\n\n2. The maximum magnitude of numerical errors in the solutions to the subproblem in Algorithm 2.\n\n   This is indeed a very good question concerning the inexact analysis of prox-linear method. To our knowledge  one close work [1] discusses the impact of inexactness on prox-linear method, where the result therein (See [1], **Theorem 5.2**) is summarized as follows\n\n   **Letting $\\delta_k$ be the error (sub-optimality) of the $k$-th prox-linear update, then the impact of error will not hurt convergence if $\\sum_k \\delta_k$ is summable.**\n\n   Following [2], the above analysis can be further extended to the stochastic setting, where we need  $\\frac{1}{\\sqrt{K}}\\sum_k\\sqrt{\\delta_k}$ to be summable. We have a formal proof of this inexact analysis and are willing to provide it using an anonymous link on reviewer's request. \n    We also remark that for the structures we are interested in, the subproblems 1) often have closed form solution, and 2) can commonly be solved to high accuracy using efficient subroutines. We kindly refer the reviewer to our appendix **Section G.3**, where we show how to efficiently solve the proximal subproblems.\n\n\n**References**\n\n[1] Drusvyatskiy, Dmitriy, and Courtney Paquette. \"Efficiency of minimizing compositions of convex functions and smooth maps.\" *Mathematical Programming* 178 (2019): 503-558.\n\n[2] Wang, Jialei, Weiran Wang, and Nathan Srebro. \"Memory and communication efficient distributed stochastic optimization with minibatch prox.\" *Conference on Learning Theory*. PMLR, 2017."}, {"review_id": "skVNiHhPGz", "reviewer": "Reviewer_93YJ", "summary": "This paper investigates delayed stochastic optimization problems with composite objective functions. The authors demonstrate that, under weakly convex conditions, the convergence rate of the delayed stochastic subgradient method can be improved from $\\mathcal{O}(\\tau_{\\max}/\\sqrt{K})$ to $\\mathcal{O}(\\bar{\\tau}/\\sqrt{K})$. Additionally, when the stochastic part $f$ in the objective function follows the structure $f = h\\circ c$, the authors propose a delayed stochastic prox-linear method to address the impact of delayed information. Lastly, by utilizing a hard-thresholding technique, the authors effectively manage the magnitude of delay, mitigating the issue of excessive delay compromising the robustness of the original algorithm.", "questions": "Most of the questions are raised in the Weaknesses section. Another question worth considering is whether an experiment can be conducted to demonstrate that the convergence of DSPL is unaffected by the magnitude of delay.", "limitations": "The main limitations of the paper center around its limited scope, incremental contributions, and insufficient exploration of key theoretical aspects, undermining its broader impact and significance in the field.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is written in a clear and easily understandable manner. The language and organization make it accessible to readers.\n\n2. The majority of the proofs presented in the paper are accurate and sound. This demonstrates the authors' proficiency in the mathematical aspects of their work.\n\n3. The authors provide valuable numerical experiments that effectively showcase the strengths and weaknesses of the DSGD and DSPL methods, specifically in terms of their step size selection. This empirical evidence enhances the practical relevance of the research.", "weaknesses": "Weaknesses:\n\n1. The research direction pursued in the paper appears to be relatively narrow, as the authors focus solely on improving the convergence rate under a specific setting. Moreover, the paper lacks substantial evidence to demonstrate the significance of these improvements. It would benefit from a more comprehensive exploration of the broader implications and potential applications of the proposed methods.\n\n2. The paper lacks in-depth explanations of the theoretical results. For instance, the authors fail to clarify why DSGD improves the maximum delay $\\tau_{\\max}$ to $\\bar{\\tau}$ compared to the reference [1]. Similarly, there is a lack of explanation regarding why DSPL can eliminate the impact of delay in objective functions that do not possess the $h\\circ c$ structure. And if there is a minimax lower bound for the latter? It would be helpful to provide further insights and discussions to enhance the readers' understanding.\n\n3. The assumptions made about the objective function predominantly revolve around the uniformity of the randomness $\\xi$. For example, requiring $f(x,\\xi)$ to be weakly convex for any $\\xi$, compared to the less restrictive assumption of $ E_{\\xi} f(x,\\xi) $\nbeing weakly convex in the reference [1]. This raises concerns about whether the improvements in convergence rate are solely attributed to the introduction of stronger assumptions. Additionally, the assumption $\\sup_{g\\in \\partial f(x,\\xi)}\\|g\\| \\le L_f, \\forall \\xi$ may not hold for the robust phase retrieving problem considered in the authors' experiments, where the measuring matrix is sampled by a Gaussian ensemble. These limitations should be acknowledged and discussed to provide a more comprehensive analysis.\n\n[1] Distributed stochastic inertial-accelerated methods with delayed derivatives for nonconvex problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer 93YJ**\n\nWe thank the reviewer for the time spent on our paper and the constructive suggestions.\n\n**Weaknesses**\n\n1. The research direction is narrow, only focusing on a specific setting\n\n   We politely disagree with the reviewer on \"narrow, only focusing on a specific setting\". \n\n   First of all, we believe that our target setting, weakly convex problem, is a quite a general class of problems covering many applications. Since [1] introduced the notion of model-based weakly convex optimization, a number of researches have been conducted to understand the theory of weakly convex problems in different fields. We believe that our contribution establishes a fundamental understanding of weakly convex optimization in the distributed setting. Besides, due to two recent work [6, 8], we believe that the understanding of DSGD in convex and smooth nonconvex setting has been rather mature, while there is still a gap between theory and practice in the weakly convex setting.\n\n2. Lack of substantial evidence to demonstrate the significance of these improvements\n\n   We also beg to disagree with the reviewer on this point. Our major contribution is the improvement of dependency of our algorithms on delay, which is a very significant topic in distributed stochastic optimization. One clear evidence is that since [2], a lot of researches have been done on delayed stochastic optimization, and related works have been consistently published at decent venues and journals (see [5, 6, 7, 8, 9, 10, 11], where recent work [5, 8, 9] improve delays and are all published at ICML/NeurIPS). Given the vast amount literature on distributed delayed stochastic optimization, the significance of weakly convex optimization, together with our comprehensive empirical studies, we believe that our improvements are indeed significant. \n\n3. Lack of in-depth explanation of DSGD/DSPL\n\n   We totally agree with the reviewer on the importance of intuition, and we have been trying to give the mathematical intuition of our improvements, especially on the delay-independent analysis. However, due to space limit we have to move some of the contents to the appendix. We kindly refer the reviewer to **Section D.4. DSPL vs DSGD** on the intuition why DSPL improves beyond DSGD. \n\n   As with why we manage to improve over the result of [3], it is indeed a good question. In our understanding, [3] puts emphasis on the momentum variant of DSGD, which we believe somehow complicates the analysis and makes it hard to improve on the dependency of delays. The intuition is that: if you extrapolate with inaccurate information, it would unlikely do you much favor. \n\n4. Existence of min-max bound\n\n   To our knowledge there's not a min-max bound for our setting. The most relevant paper we can find [4] analyzes a lower-bound of DSGD, but their setting is different from ours, and does not take into account the real distributed environment.\n\n5. Assumptions are strong\n\n   We understand the concern of the reviewer on our assumptions. In a word our analysis needs a few lines of modification to support non-uniform assumptions. For more details we refer the reviewer to our global reply.\n\n**Questions**\n\n1. Experiment showing the convergence of DSPL is unaffected by the magnitude of delay\n\n   We kindly refer the reviewer to the third part of experiment (**Section 6.4**), which compares DSGD, DSPL and their robust variants under adversarial delays. We also have additional experiments in the appendix **Section H** that study the performance of DSGD/DSPL on blind deconvolution problem.\n\nWe believe that our replies adequately address the concerns of the reviewer, and we again thank the reviewer for the efforts in reviewing our paper.\n\n**References**\n\n[1] Davis, Damek, and Dmitriy Drusvyatskiy. \"Stochastic model-based minimization of weakly convex functions.\" *SIAM Journal on Optimization*\n\n[2] Agarwal, Alekh, and John C. Duchi. \"Distributed delayed stochastic optimization.\" *Advances in neural information processing systems*\n\n[3] Xu, Yangyang, et al. \"Distributed stochastic inertial-accelerated methods with delayed derivatives for nonconvex problems.\" *SIAM Journal on Imaging Sciences*\n\n[4] Arjevani, Yossi, Ohad Shamir, and Nathan Srebro. \"A tight convergence analysis for stochastic gradient descent with delayed updates.\" *Algorithmic Learning Theory*. PMLR\n\n[5] Mishchenko, Konstantin, et al. \"Asynchronous sgd beats minibatch sgd under arbitrary delays.\" *Advances in Neural Information Processing Systems*\n\n[6] Zheng, Shuxin, et al. \"Asynchronous stochastic gradient descent with delay compensation.\" *International Conference on Machine Learning*\n\n[7] Stich, Sebastian U., and Sai Praneeth Karimireddy. \"The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates.\" *The Journal of Machine Learning Research*\n\n[8] Cohen, Alon, et al. \"Asynchronous stochastic optimization robust to arbitrary delays.\" *Advances in Neural Information Processing Systems*\n\n[9] Koloskova, Anastasiia, Sebastian U. Stich, and Martin Jaggi. \"Sharper convergence guarantees for asynchronous sgd for distributed and federated learning.\" *Advances in Neural Information Processing Systems*\n\n[10] Karimireddy, Sai Praneeth, et al. \"Error feedback fixes signsgd and other gradient compression schemes.\" *International Conference on Machine Learning*\n\n[11] Lian, Xiangru, et al. \"Asynchronous parallel stochastic gradient for nonconvex optimization.\" *Advances in neural information processing systems*"}]

Author rebuttal:
**Clarification of the assumptions**

First, we thank all the reviewers for their efforts in the review process, and for acknowledging the novelty of our work. 

Both reviewer bGwb and 93YJ share the concern that the assumptions are made on stochastic functions and not the expectation ones, which could be a limitation and make it hard to tell the source of improvement.

We appreciate the insightful feedback from the reviewers. We concur that assumptions on the expected function, $\mathbb{E}[f(x,\xi)]$, are indeed more standard and weaker compared to those on the stochastic functions $f(x,\xi)$. However, transitioning to assumptions on $\mathbb{E}[f(x,\xi)]$ can be achieved in a standard manner. **While this change might lead to small adjustments to some constants in the rate, we assure that the dependency on both $K$ and $\tau$ are unaffected.** 

To convince the reviewers, we highlighted the key difference in the updated analysis for DSGD/DSPL and are glad to provide a link of pdf with more details on reviewer's request. We will also attach the proofs directly on official comments (when it becomes visible). We believe this suffices to convince the reviewers that these adjustments are primarily related to the constants in a few inequalities, leaving the core conclusions of our work intact. Furthermore, we promise that the revisions will detail the adjustments made in our proof to incorporate these changes.  

Our revised assumptions will be

**Rlx B1**. $f(x)$ is $\lambda$-weakly convex and $\mathbb{E}[\|\| f' (x,\xi)
\|\|^2]\leq L_f^2$. ($f'(x,\xi)=g\in \partial f(x,\xi)$) for all $x \in \text{dom} ~\omega$

**Rlx C1**. $c(x,\xi)$ is $C(\xi)$-smooth and $\mathbb{E}[\|\| \nabla c(x,\xi)\|\|^2]\leq L_c^2$,   $\mathbb{E}[\|\| C(\xi)\|\|^2]\leq C^2$
for all $x \in \text{dom} ~\omega$.

These assumptions are standard in stochastic optimization literature, and now we highlight the modifications of the proof, taking DSGD as an example (similar analysis is applicable to DSPL). Now we get down to technical details.

**Step 1.** Bounding $\|\|x^{k+1}-x^k\|\|$ on expectation.
The first consequence of **Rlx B1** is that our original bound 
$$\|\|x^{k+1}-x^k\|\|\leq \frac{2(L_f+L_\omega)}{\gamma} \tag{1}$$
no longer holds uniformly. Now we instead show it on expectation. Recall that 
$$\begin{align}
  x^{k+1} ={} & \arg \min\_x  \\{ \langle g^{k-\tau_k},x-x^k\rangle +
  \omega (x)+\frac{\gamma}{2}\|\|x-x^k\|\|^2 \\} 
\end{align}$$
in our proximal update. And by three-point lemma,
$$\langle g^{k-\tau_k},x^{k+1}-x^k\rangle+\omega (x^{k+1}) +
   \frac{\gamma}{2}\|\|x^{k+1}-x^k\|\|^2\leq \omega (x^k)- \frac{\gamma}{2}\|\|x^{k+1}-x^k\|\|^2$$
Re-arranging the terms and applying Cauchy-Schwartz,
$$\gamma\|\|x^{k+1}-x^k\|\|^2\leq (L_{\omega} +\|\|g^{k-\tau_k}\|\|)
  \|\|x^{k+1}-x^k\|\|$$
Dividing both sides by $\|\|x^{k+1}-x^k\|\|$,
$$\|\|x^{k+1}-x^k\|\|\leq \frac{1}{\gamma} (L_{\omega}+g^{k-\tau_k})$$
Conditioned on the history, taking expectations on both sides,
$$\mathbb{E}\_k[\|\|x^{k+1}-x^k\|\|]\leq \frac{1}{\gamma} \mathbb{E}\_{\xi^{k-\tau_k}}[L_{\omega}+\|\|g^{k-\tau_k}\|\|]\leq \frac{L_f+L_\omega}{\gamma},$$
where the last relation is by Jensen's inequality. Now we get a counterpart of $(1)$. A more tricky part is about $\mathbb{E}\_k[\|\|x^{k+1}-x^k\|\|^2]$, and we note that 
$$\begin{align}
  \gamma \mathbb{E}\_k[\|\|x^{k+1}-x^k\|\|^2] \leq{} & \mathbb{E}\_k
 [(L_{\omega}+\|\|g^{k-\tau_k}\|\|)\|\|x^{k+1}-x^k\|\|]\\\\
  ={} & \mathbb{E}\_k
 [\|\|g^{k-\tau_k}\|\|\cdot\|\|x^{k+1}-x^k\|\|]+\mathbb{E}\_k
 [L_{\omega}\|\|x^{k+1}-x^k\|\|]\\\\
  \leq{} & \mathbb{E}\_k[(2\gamma)^{- 1}\|\|g^{k-\tau_k}\|\|^2]+\frac{\gamma}{2} \mathbb{E}\_k[\|\|x^{k+1}-x^k\|\|^2]+\frac{2 L_{\omega} (L_{\omega}+L_f)}{\gamma}\\\\
  \leq{} & \frac{L_f^2+4L_{\omega}(L_f+L_{\omega})}{2\gamma}+\frac{\gamma}{2}\mathbb{E}\_k[\|\|x^{k+1}-x^k\|\|^2]
\end{align}$$
The last relation uses $2x y\leq a x^2+\frac{y^2}{a}$ to decouple correlated $\|\|g^{k-\tau_k}\|\|$ and $x^{k+1}$; $\mathbb{E}\_k
 [L_{\omega}\|\|x^{k+1}-x^k\|\|]$ is bounded using $(1)$. Finally, we re-arrange the terms to cancel $\frac{\gamma}{2} \mathbb{E}\_k[\|\|x^{k+1}-x^k\|\|^2]$ on both sides, giving 
$$\mathbb{E}\_k[\|\|x^{k+1}-x^k\|\|^2]\leq \frac{L_f^2+4L_{\omega}(L_f+L_{\omega})}{\gamma^2}$$
Compared to our original result, the bound on $\mathbb{E}\_k[\|\|x^{k+1}-x^k\|\|^2]$ becomes slightly worse in the enumerator.

**Step 2. Relaxing uniform assumption on the stochastic function**

Our assumption on uniform weak convexity appears on Line 561 in the appendix, where we have
$$\mathbb{E}\_{\xi^{k-\tau_k}}[\langle g^{k-\tau_k}, \hat{x}^k - x^{k -
   \tau_k} \rangle]+f (x^{k-\tau_k}) - f (\hat{x}^k) \leq
   \frac{\lambda}{2}\|\| \hat{x}^k - x^{k-\tau_k}\|\|^2$$
using $\lambda$-weak convexity. However, since $\mathbb{E}\_{\xi^{k-\tau_k}}[g^{k-\tau_k}] \in \partial f (x^{k -
\tau_k})$, we only need $\lambda$-weak convexity of $f$.


**Step 3. Putting things together**

After the two steps above, we can smoothly go through, where our last piece of proof (Line 572) needs a modification of constant in bounding $\sum_{k=1}^K \mathbb{E}[\|\| x^k - x^{k-\tau_k}\|\|^2]$. 
$$\begin{align}
 \sum_{k=1}^K\mathbb{E}[\|\|x^k-x^{k-\tau_k}\|\|^2]={}&\sum_{k=1}^K
\mathbb{E}[\|\|\sum_{l=1}^{\tau_k}x^{k+1-l}-x^{k-l}
\|\|^2]\\\\
 \leq{}&\sum_{k=1}^K\tau_k\sum_{l=1}^{\tau_k}\mathbb{E}[\|\|x^{k+1-
l}-x^{k-l}\|\|^2]\\\\
\leq{}&\frac{L_f^2+4L_{\omega}(L_{\omega}+L_f)}{\gamma^2}\sum_{k=
1}^K\tau_k^2,
\end{align}$$
where the first inequality uses the relation $\|\|\sum_{i=1}^ka_i\|\|^2\leq k \sum_{i=1}^k\|\|a_i\|\|^2$ and the second inequality applies our modified bound on $\mathbb{E}\_k[\|\|x^{k+1}-x^k\|\|^2]$. The bound on $\sum_{k=1}^K \mathbb{E}[\|\| x^k - x^{k-\tau_k}\|\|]$ remains unchanged.

At this stage, **our analysis is fully compatible with the standard assumptions**, at the cost of a slightly worse constant in the bound. Our convergence rate and main results are unaffected.

Meta-review: The authors develop new theoretical guarantees for the delayed stochastic subgradient method for nonsmooth weakly convex optimization problems. Their work improves on previous bounds for nonsmooth distributed optimization by replacing the maximum delay by the first and second moments of the delay. They also present delay-independent rates for nonsmooth weakly convex optimization problems.
Decision: Accept (poster)