Asymptotic Behaviors of Projected Stochastic Approximation: A Jump Diffusion Perspective
Authors: Jiadong Liang
Yuze Han
Xiang Li
Zhihua Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Diffusion Approximation
Federated Learning
Loopless Algorithm
Jump Diffusion
Bias-variance Tradeoff
Asymptotic Normal
Asymptotic Biased

Abstract: In this paper, we consider linearly constrained stochastic approximation problems with federated learning (FL) as a special case. We propose a stochastic approximation algorithm named by LPSA with probabilistic projections to ensure feasibility so that projections are performed with probability $p_n$ at the $n$-th iteration. Considering a specific family of the probability $p_n$ and step size $\eta_n$, we analyze our algorithm from an asymptotic and continuous perspective. Using a novel jump diffusion approximation, we show that the trajectories consisting of properly rescaled last iterates weakly converge to the solution of specific SDEs. By analyzing the SDEs, we identify the asymptotic behaviors of LPSA for different choices of $(p_n, \eta_n)$. We find the algorithm presents an intriguing asymptotic bias-variance trade-off according to the relative magnitude of $p_n$ w.r.t. $\eta_n$. It provides insights on how to choose appropriate $\{(p_n, \eta_n)\}_{n \geq 1}$ to minimize the projection complexity.

Asymptotic Behaviors of Projected Stochastic Approximation: A Jump Diffusion Perspective
Jiadong Liang
Yuze Han School of Mathematical Sciences Peking University hanyuze edu. cn
School of Mathematical Sciences Peking University
jdl iang@pku edu.
Xiang Li School Mathematical Sciences Peking University 1x100770pku edu. cn
Zhihua Zhang
School of Mathematical Sciences
Peking University zhzhangemath, edu. wwu.
Abstract
In this paper we consider linearly constrained stochastic approximation prob- lems with federated learning as special case. We propose loopless projection stochastic approximation algorithm (LPSA) ensure fcasibility by performing the projection with probability Ps, at the n-th iteration. Considering specific family of the probability Pa and step size The we analyze our algorithm from an asymptotic and continuous perspective. Using novel jump diffusion approximation, we show that the trajectories connecting those properly rescaled last iterates weakly converge to the solution of specific stochastic differential equations (SDEs). By an- alyzing SDEs, we identify the asymptotic behaviors of LPSA for different choices of (Pn: Mh.). We find the algorithm presents intriguing asymptotic bias- variane trade-off according to the relative magnitude of pn. w.r.t. 7h- It brings insights on how choose appropriate {(Pn, Th hn21 minimize the projection complexity.
Introduction
Recently, novel distributed computing paradigm that called Federated Learning (FL) has been proposed for collaboratively training a global model from data that remote clients hold [31]] standard optimization algorithm in FI., Local SGD alternates between running stochastic gradient descent (SGD) independently parallel on different clients and averaging the sequences only once in while. Put simply, it learns a shared global model via infrequent communication. Empirical investigation finds its superior performance in communication efficiency (30) and theoretical analysis toward it has already provided complete picture (26 15] 42
Among them, Li et al. [27] establishes a functional CLT that Local SGD with Dolyak-Rupper averaging simultaneously achieves the optimal asymptotic variance and diminishing average communication frequency. However, they are all derived from a discrete perspective.
The use of continuous-time stochastic process to characterize the entire trajectory of discrete stochastic algorithm has been witnessed progresses recent years, and we call it diffusion ap- proximation. The continuous approach has advantages in its rich toolbox and can provide intuitive explanation for uncanny phenomena that are intractable to analyze discrete cases. can also motivate new optimization algorithms and statistical inference methods. Current works applying diffusion approximation to stochastic optimization algorithms can roughly divided into two classes. The first one is to interest the optimization algorithm numerical discretization of specific stochastic differential equation (SDE) 14 in a finite time interval [0, TP. When the step size is
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

sufficiently small and the length T(= r17) of the interval is fixed (n is the total iterations), such approximation of high accuracy, and is easy to analyze the geometric properties of our target However, this avenue is difficult to capture the convergence behaviors around the optimal point due to the fixed T The second class comes up to solve the issue. It instead considers the iterates divided by proper power function of step sizes. Under certain conditions, as n goes to infinity, the rescaled iterates would weakly converge to the stationary solution of corresponding SDEs [21 35 6 2 [0] In FL, to the best of our knowledge, no work considers analyzing Local SGD via the aspect, which is our focus here.
algorithms 41 23 13
38
34 g
However, it is not easy to serialize Local SGD iterates due to its double-loop nature. Recent researchers developed a new technique named as 'loopless' to simplify the two-loop structure for SVRG and Katyusha [[6]. The key is to replace the hard loop with probabilistic loop. Specifically, we will independently toss a (possibly biased) coin win with head probability Pa, at iteration n. When getting the head w/ 1, we start new loop and update the outer-loop intermediate variables; when getting the tail Wn, 0, we stay in the same loop and keep the intermediate variables. this way, we obtain a loopless counterpart algorithm and do not need to distinguish inner and outer loops anymore. facilitates theoretical analysis and typically does not deteriorate the convergence rate [12 29 28 [.]
It is worth mentioning that Hanzely and Richtárik [12 first introduced the loopless technique to FL and obtained many efficient FL algorithms. Li (28) used a dynamic pv. (which varies with n) to generalize the scope of original methods. We are then motivated to analyze a loopless version of Local SGD with decreasing Pa. but from an asymptotic and continuous perspective.
1.1 Contribution
Our work is motivated by Local SGD but beyond it. In particular, for general optimization problems with linear constrains (of which FL is special case), develop a loopless projection stochastic approximation method (LPSA) as a generalization of Local SGD (see Appendix [A for more details). Such generality renders the possibility to transfer techniques and results to other linearly constrained problems. I.SSA is affected by two important hyperparameters, namely the step size }m1 and the projection probability {Pr)- For the choices of 1m x n n and pr. min (y, 1).
derive a non-asymptotic convergence rate for different a E (0. 1] and 3 E (0, 1) in Theorem 3.1 We observe a phase transition for the convergence rate O(n -a momminn. (1. (1.2 2.)) when / crosses 0.5.
To derive asymptotic results, we obtain two sequences (un) and {u.,} by orthogonal decomposition for the optimized sequence of LPSA. We then construct two sequences of processes which pass through the appropriately rescaled un and u, respectively. We show rigorously, when the iteration goes to infinity, these two sequences of stochastic processes weakly converge to the solutions of specific SDEs that are driven by either Brownian motion or a Poisson process. As corollary, the rescaled last iterate of u. (which we mainly care about) has a known asymptotic distribution (either Gaussian distribution in Theorem 3.3 or Dirac in Corollary []. And the phase transition mentioned above evolves into a trade-off between the bias caused by the low frequency projection and the fluctuation resulting from the gradient noise (see Section 3.2.3).
Moreover, according to different convergence rate for every {fm, Pn)} pair, we consider selection scheme at the end of Section 3.2.3 which makes the algorithm have the same nonasymptotic convergence order as the conventional stochastic approximation and spend as little as possible on the projection operation which is usually expensive in practice. At the end, we conduct numerical experiments to confirm the theoretical results.
From a technical level, we propose novel proof technique to analyze the discontinuity brought by probabilistic projection. In particular, we borrow tools from jump diffusion and verify necessary conditions (e.g., stochastic tightness) to apply it. See the paragraph after Theorem 3.4 for main idea. We believe our technique can extend to and help analyze other stochastic approximation algorithms which can be approximated by jump diffusion.
A finite I' implies not only the algorithm but also its corresponding SDE do converge to the optimum.

---

2 Problem Formulation
2.1 Loopless Projected Stochastic Approximation
Notice that distributed optimization such FL can be formulated global consensus problem which is linearly constrained problem [5]. For the sake of simplicity and generality, we aim to solve the following problem
min Eq-D subject to A
(1)
via a randomly (and infrequently) projected stochastic approximation algorithm. particular, at iteration we first perform one step of SGD via
Th Vf(xxn) + mn.n:
F+
where (z) = EZ () and En = Vf(..) (z G.). Here {En a martingale difference sequence (m.d.s.) under the natural filtration Fn+1 (Ce, wii k S n++1. We then use the loopless trick introduced in the introduction, i.e., we independently cast coin with the head probability and obtain the result wn Bernoulli(pa). If Wn, 1, we perform
step of projection ensure
Ln+1 fall into the feasible region: En+1 = PA (#++ ) where PA= denotes the projection onto the null space of AT. If wi, 0, we assign 2x+1 as the same value of F i.e., In+1 2 a It is clear this algorithm 2 mimies the behavior of Local SGD in Fl. settings (see Appendix A the
equivalence).
2.2 Assumptions
For the linearly constrained convex optimization problem (T). we make the following assumptions which are quite common in the literature. Without special clarification, || denotes the Fuclidean norm for vectors and the spectral norm for matrices.
Assumption (Smoothness). We assume that f: Rd R is L-smooth, that is,
[Vf(x) - f((iil < x yll. Vx,y E Rd.
Assumption 2 (Strong convexity). We assume that f: Rdd - R is p-strongly convex, that is,
f(z) - f(v) 2 (Vf(y). y)
uli. YE E Rd.
Assumption 3 (Continuous Hessian matrix). We assume that f: RRd + R is Hessian Lipschitz, that is, there is a constant L such that
|| f(x) v2 f())) s D|| yll. V Rd.
Assumption 4 (Continuous covariance matrix). Given m.d.s. {Er}, we denote the conditional covariance as E[G, [F,] = Exx,) and assume it is L-Lipschitz continuous in the sense that
|E(x) E(y)l12 S L| - yll. Va, y E
Assumption 5. For the m.d.s. {En}, we assume there exists p >> 2 such that the p-th moment of every element in {En} } is uniformly bounded, that is,
sup E| II < 00. n20
The first three assumptions imply we consider the strongly convex case. The last two assumptions help us identify the asymptotic variance. Especially, the assumption of uniformly bounded p (p > 2) moments is typically required to establish central limit theorems 9 10 27 Finally, we want to emphasize that the stationary condition for the problem ① is different from unconstrained ones; ff(x*) is not necessarily zero. however, its projection into the null space of A must be zero.
Proposition (25), Corollary 2.1). Let PA be the projection onto the column space of A and P the projection onto the null space of T Under Assumption 2 the solution of is unique (denoted x Moreover, have PA- ( (x 0.

---

2.3 Jump Diffusion
Jump diffusion a stochastic Lévy process that involves jumps and diffusion. Typically, the former is modeled by a Poisson process, while the latter is modeled as a Brownian motion. It has wide and important applications physics, finance and computer vision.
We say a function f defined on R is cădläg when f is right- right-continuous and has left limits everywhere. For cådlàg process (Va) <220000. we denote Vc- as the left limit of V. at time t. Let (t)()) denote the Poisson process with the intensity, which quantifies the number of jumps up to the time t and is clearly cådlág. We use (dt) (t) (t-) {0, 1) to indicate whether N., jumps at time and J'' function g(-). We will consider special class of jump diffusion in the following form
E
((t-) to denote the integral that drives for measurable
dx, att X3) dt (t. X, JdW, + c(t,, (d,
(3)
When the coefficient functions att, X²) and (tt Xx) satisfy conditions like linear growth and Lipschitz continuity, there exists a solution for the jump diffusion (3) (c.g., Theorem 1.19 in (3))
3
Main Results
In the section, we are going capture the convergence behaviors of our projected stochastic approxi- mation method (2) from both non-asymplotic and asymptotic perspectives. We consider a specific family of step size The and projection probability pn, namely, th- 1oon and pn. min 1) indexed by 0 < a < and < B < respectively. The choice of step sizes 7/s has been used to establish CLTs [3 (7). while the choice of p, is quite novel. To provide complete picture of convergence, we will consider almost all combinations of a and 3.
3.1 Non-asymptotic Analysis
To provide the convergence rate, it natural to focus on the projection of æ, into the column space of A (since it is the easiest feasible solution one can obtain from xx.). Hence, we decompose the iterated nnn into two orthogonal components Fn == U. U, where un PA - (Ix) and e,, = PA (x,.) We specify the the convergence rate of E l|u, 1=2 in terms of a, 3 and n in the following theorem.
Theorem 3.1. Suppose that Assumptions 1 and hold. Let T, = non and p.. = min ( 1} with 0 < < Then for (i) a < or (ii) a with no 2/μ (μ is the strong convexity parameter of the objective function f). we have
E Un x On -a (i2
From Theorem 3.1 as 33 decreases, that is, the projection happens more frequently, E |u,, x x= converges faster. The rate is (nn-a) when 3 < 0.5, while the rate is O(n -2c(1-9)) when 8 > 0.5. Thus there exists a phase transition when goes across 0.5, which implies we should analyze asymptotic performances for these two phases respectively. As an extreme, when B 1, the algorithm is possible to disconverge in an artifact quadratic loss with a specific A (see Theorem 3.2) Though for specific A, it could apply to FL (see Corollary in Appendix A.2. for the detail).
Theorem 3.2. If 166n a and Pn min(pora. 1 with 0 < < for specific A, there exists quadratic function f(x) so that V2 > Ia and T.. ||u,, -x= ||,,,==** 112 does not converge to O. Here
Ig E dxd is the identity matrix, and 2 f(x) > La means 2 f(x) -Ia is positive semidefinite.
3.2 Asymptotic Behavior of the Rescaled Trajectory
In this section, we want to derive an asymptotic convergence for 22) Recall that there exists a phase transition for the convergence rate of E || x when 3 crosses 0.5, when the projection probability is set as Pa = Th In the following, we will analyze the asymptotic behaviors of ISPA for the cases [0, 1 1/2) and 3 1).
One check Proposition 4 in Appendix B to see why u. orthogonal

---

3.2.1 Case 1: Frequent Projection where 3 E 1/2)
From an asymptotic perspective, the typical central limit theorem (CLT) claims Un == U. would weakly converge to rescaled standard distribution [21. It helps capture the large-sample convergence behaviors and provide ways for future statistical inference. However, we can provide stronger result that captures the asymptotic behavior of the whole trajectory. In particular, serialize the sequence ( by constructing continuous random function (denoted (x(") such that it starts from 140 (()) ihn and as increases it will pass through #,,+1, uh++2 and so We will show that such random function ut") will weakly converge to the solution of specific SDE. From SDE, we can derive asymptotic variance of úh, and the whole trajectory evolution.
Since a!"h should pass all {ue}knn functions. To that end, we first derive the one-step relation between ú, and ūn+1- particular,
connect these discrete points by piecewise linear
un+1 th -nnnn
(4)
bn PA (v"s(x")
1 1 1 (a=1) ün + - R.y
(5)
2/10
TJn
where RS stands for high-order residual error, and <h denotes the component of noise &n on the
null space of A. One can find the derivation of (4) in Appendix C.1 Roughly speaking, (4) can be viewed as a one-step Euler Maruyama discretization with timescale 7/, for an SDE, which starts at ün with local drift coefficient b, and local diffusion coefficient var((!!)
Definition (Time interpolation). Let a positive sequence = {7m)2 100 decrease to zero. For N. 2 define
N m
min mEN
2 n
7k > t [n( .
Σ Tks and (n(r) (N((e)))) In-
We introduce time interpolation for the formal description of the continuous function and fur- ther analysis. Intuitively, (nn,t, 7,) is the number of iterations m at which the sum step sizes m1+1 Lkea+1 The is just larger than and L. (x) is the approximation of when we only use step sizes (TR) Since Yn - 0, (7)
t as goes to infinity. A property of Definition D is that ( I' - 7)) = m for any m 2 n. By now, we are ready to construct u."" (n) For a given N, let Ug
(m) ūn and define for 2 0.
N N(n.t.)- Σ
u,
(n) Un
nabs (t (n)
(6)
N(nttt)-1
Vmneh + Vt (7)
(1)
From the construction, that ū (n)
(.( üntk.
Theorem 3.3 (Diffusion Approximation). Let Assumptions 5 hold. The following family of
continuous stochastic processes {u,.7) 0 weakly converges the stationary weak solution of the following SDE:
dx. = -PA (v'S(0")
1 (a=1))1a) X,di + PA Elx)
(7)
21J0
Further, the rescaled sequence { converges weakly to the invariant distribution of the dynam- ics i.e., (0, E). Here the variance E. satisfies the Lyapunov equation
PA- F2f(xx) - 2noo (a=1)1a| E I+ E ( f2=((=)
1
11a=114d PA==PAL\(Zz'))
2no0
5

---

Remark 1. By using the contimuous time version of the Lyapunov theorem (Lemma 1 in (40]), the Lyapunov equation has a unique positive semidefinite solution (denoted E). From Theorem 3.3 and Theorem 4. 1.1 1.11 in [,] we can tell that when [0, 5) our algorithm LPSA achieves the same asymptotic variance as SGD that also uses the same step size. The typical projected SGD corresponds to the case 3 = O, while LPSA allows 3 to vary [0. 2) One can reduce the projection frequency by increasing 3 (equivalently decreasing the probability Pu.). Hence, when projection is expensive, LPSA more efficient in performing projections due to its flexible and moderate projection frequency.
Proof Idea of Theorem 3.3
We shed light on the proof idea of Theorem 3.3 From high level, we
leverage the general theory for operator semigroups, which are developed by Trotter and Kurtz [39 17- [9] and are used to analyze stochastic optimization algorithms in (9]. Our diffusion approximation results are built on it, but generalize
the sense that we use the celebrated Prokhorov's theorem to
extend to the whole trajectory. One difficulty is to prove the stochastic tightness of {u, J. To that end, we make use classic result (e.g. Theorem 7.3 of
3.2.2 Case 2: Occasional Projection where B E (1/2,1)
When step into the low-frequeney regime where E 12 the situation totally changes. Intuitively, when LPSA performs much less frequent projection, we will frequently use infeasible æt update parameters, which accumulates residual errors. These errors would not only dominate and slow down the non-asymptotic convergence rate (see Theorem 3. but also change the asymptotic behavior. In this case, we should not only find the right timescale, but also need figure out how these errors are accumulated. To solve the issue, we develop new analysis routine. In the following. we consider Pa >y with > O.
Our solution is to monitor another random process that related with {v,}. which serves as bridge to derive the asymptotic behavior of (. The right scale should make the scaled sequence have non-vanishing expected Le norm. From Theorem 3.1 it should be Ü, 8-1 un- In addition, given 6n the candidate value of ún+1 before tossing the coin whs can be derived from LPSA's Algorithm in Appendix A and we denote this candidate ([n+1)-
((++1)- 1)- == Ün T/. d, + n
(8)
where d,, V fxx) + nn SS, with S, residual error which satisfies n, SS, o1(1) (see Appendix C.2 for more details) and c!!²) stands for the component of noise &n on the orthogonal complementary space A Due to the probabilistic projection, ön+1 takes value ((x+1)- with probability 7mh and takes value zero with probability 7ng. Similar to the previous section, we then construct a cådlàg random process o(() which starts from o and will pass through {((z)- Jazn. We can connect these discrete points with step function. results in the following construction
vl(") (n) (,("))) (1-))(1)) (dN(,,tnp)) - -M(mA))) if EE (L.(7r)), L. ) ..))
V (m) 2, ()) UN(n,e.p))
From we can claim that o/ (-) = (N(ntt))))) for any 1. 2 0. With probability PN(nat)f)
( takes value zero, which causes the process (!!)) to change abruptly the time L, (n7)).
These discontinuities about (.(") prevent the diffusion process from working (!(1) as the result of
Theorem 3.3] Even so, the following theorem shows that we can still find a suitable process in the
broader jump diffusson class to approximate (!!))
Theorem 3,4 (Jump Approximation). Let Assumptions
1 and 5 hold. The following family of càdlåg stochastic processes (o( : 0 weakly converges the stationary weak solution of the following SDE
dY, = =V.==Vf(""dd" Y,- - (dd).
(10)
- Further, the rescaled sequence 100 [ weakly converges to the invariant distribution of the dynamics (T0)
Here (!) represents Poisson process with intensity 7, and
ie.,
f((m)
[[V((=')
Here {() represents the exponential distribution with intensity 4

---

Theorem 3.4
shows that the sequence {0 constructed by shifting initial points will finally approximate a jump process with a constant drift as n goes to infinity. The SDE (10) sheds light on how a!") (equivalently a rescaled version of U, move as t increases. As the enror incurred by infrequent projections, "!!") will move towards the direction of f=(")) (due to the drift term - - )dt) and be periodically forced to set as zero vector ( due to the correcting term - -Y,- N, (dt)). From a qualitative perspective, the SDE (T0) captures the periodical behavior of un. hence it shows without projection the residual error will accumulate along the direction of V v(()). As argued in
Proposition 1 V ((=) is unlikely to be zero in our constrained problems.
The remaining issue is how to link {5 (") } to our target { {un} Similarly, we should consider a rescaled thp that is, ih == (un, x²) )/n
1-8 The following corollary, which is based on Theorem 3.4 shows
when 3 E 1), ün converges to a non-zero vector. Recall that un "y V 7n 0.5
Unn The
Eú,|l + co. As result, the bias in Corollary | instead of the Gaussian fluctuation in Theorem 3.3 becomes the leading term hindering the convergence.
equation together with Corollary implies ||Eū,,] 7/- 0.3-8
Corollary 1. Let Assumptions 7- 3
hold. Then in L (un xx)) converges to a non-zero
vector 7 {PAL (v²
-- (a=1; PAL) (PAi (a*)) in the L2 as n + co.
To
Where G denotes the pseudoinverse of the symmetric matrix G.
Proof Idea of Theorem 3.4 The main proof idea is similar to that of Theorem 3.4 exceett that we need to handle the jump diffusion which introduces additional discontinuity. As a result, for each n 2 0. (5. he2n is càdlág rather than continuous. We then use the approximation result for jump diffusions developed by Kushner [20 instead of Trotter and Kurtz's theories. Furthermore, the tool for proving tightness also needs to change. We replace the classic tool in [4] with a generalized determination method, the latter used to establish the stochastic tightness for càdlåg processes (e.g.. Theorem 4.1 in 19).. The remaining issue is to figure out properties (e.g., the mixing nature) of (TO). To that end, we establish the geometric ergodicity of Eq. (TO) by combining the coupling method with the Itô's formula for jump diffusions, and show that its invariant distribution exists uniquely.
3.2.3 Summary and Discussion
From Sections 1.2.1 and 3.2.2. for the choice pr. nh when 33 varies, our algorithm has an interesting
bias-variance tradeoff. In fact, Theorems 3.3 and 3.4 reveal that the fluctuation of u, is of order
O(nā) and the bias of order - When 3 [0, 1/2) the fluctuation caused by the randomness of gradient queries in every iteration dominates the optimization accuracy. And when 8 E (1/2, 1), this indicator is manipulated by the biases formed by the accumulation of skewed updates in the unconstrained state within each 'inner loop'.
In practice, projection is expensive to perform. Hence, it is important tune and 3 so that the projection complexity is minimized as much as possible. We use the average projection complexity (APC) quantify the projection efficiency. For target accuracy >> 0, APC is defined as the number of projections required to obtain an 6-accuracy feasible solution. We summarize the derived results and the corresponding APC in Table T. We can that APC is minimized when - 1 and 3 0.5. In this case, APC is approaching V
We find an interesting parallelism between LPSA and Local SGD. In the case of FI., projection complexity corresponds to communication complexity, because a synchronization in FL is essentially a projection in linearly constrained problems (see Appendix [ for the equivalence). In (27). the authors analyzed the averaged communication complexity for Local SGD with -uppert averaging B They considered general case where the length of the m-th inner loop could be up to Em = m" with y E [0, 1). After Em steps of inner loop, communication would perform to synchronize local models. Hence, E, plays role similar to Pr. in our paper. Li et al. [27] found that when v [0, 1), the averaged Local SGD iterates enjoy an optimal asymptotic normality up
FFor target accuracy e > 0, ACC is defined as the number of communication required to obtain a e-accuracy global parameter.
7

---

Table I: (Sym-)Asymitotii results and projection complexity under different choice of 7h and pn- The first two columns list the non-ssymptotic and asymptotic results respectively. and the last column characterizes projection complexity.
(a, 5)
E|
U
xx 1
Asymptotic behavior
APC
(o, 1] x [0, 1/2)
3.1
Normal 3.3
0
(
(0, 1J x (1/2, 1)
3.1
Biased
6 2o(1-a]
(e 23
1 similar Y to our case where APC converges to vi when a - and | + 0.5. Actually, the ve average
to known constant scale and its ACC is (2) When v + 1, ACC is approaching
communication complexity is actually optimal for any first-order oracle distributed algorithms, as shown [ Hence, implies our I.SPA is efficient and near optimal projection, because we can
always reduce FL special of
Experiments
In this section, we validate our theoretical results through comprehensive experiments. Due to space limitations, only show some representative results on synthetic datasets under FL settings. For the results on general linearly constrained problems, please refer to Appendix D
Experimental Setup We focus classification problems with cross entropy loss, and Eg regular- ization is imposed to ensure the strong convexity of the objective function. The synthetic datasets are generated by following (24). There are K clients and the sample (æ 2x:) on the k-th client is modeled as 2 ~ M(k,, A) and = argmax(softmax((W))
+ b,)) where A E RRdxd is diagonal with the entry (j,j) equal to j-22, W₂ E pxxd and by E R We consider two specific datasets. The first one is denoted by IDD, where all the clients share the same Wà and by. and v ~ (N, Ia). For this one, we set K = 100, d = 60 and C = 10. The second one is denoted by Synthet ic (a, b), where a and control the heterogeneity across clients. Specifically, each entry of W. and b is modeled as N (Mu, 1) with f4 ~ N(0, a) and 1/2 ~ N I) with SA ~ (O, 6la). For this dataset, we set K 20, d 10 and C 5.
We find that the results on IDD are intuitive enough to demonstrate the convergence rates of the mean and the asymptotic behavior of ú, for 3 E [0, 1/2). The results
squared error (MSE) IE [|u,, - 1 on Synthetic ic (a, b). dataset with fewer parameters and more heterogeneity, are more appropriate to illustrate the asymptotic biased of it, for / E (1/2, The full results on both the datasets are deferred to Appendix D
We plot the log-log scale graphs of averaged MSEs over 5 repetitions IID vs iterations in Figure [ The value of a is set as 0.8, 0.6} and the value of / is from {0, 0.2, 0.4, 0.6, 0.83. For each repetition, the line in the log-log scale graph should be -a a min(1.2 2 2.3.. This in accordance with Figure ] when the iteration is larger than 100. For 3 E [0, 1/2), the value of B3 does not affect the slope, while for 3 E (1/2, 1), larger /3 and smaller a both lead to smoother lines.
Convergence Rate
run 2000 steps of LPSA. By Theorem 3.1] the slope of
2-00
Zane
107
2-
20
3- 02
25F
2-03
1-
2-31
2-06
10
Figure 1: The log-log scale graphs of averaged MSE on IID over 5 repetition vs iterations.
8

---

-- 1-12
Desccon
Diaccion
230
632
033
-0.
012
2000
2000
Figure 2: The heatmaps ú across two orthog- Figure 3: Trajectories of ú. along random di- onal directions over 100 repetitions IID. rections over 5 repetitions on Synthetic (1, 1).
Frequent Projection For a 1 and 8 E {0, 0.2), we run 2000 steps of LPSA over 100 repetitions on IID and pick up the last 200 iterates. For these iterates, we compute the rescaled vectors ū, and project them into two-dimensional random subspace. Then we plot the heatmaps across the two dimensions in Figure 2 We observe that the cells near the origin have the lightest colors, and move away from the origin the cell color becomes darker. Since the cells with lighter colors imply more frequencies, these phenomenons agree with Theorem 3.3 where the limiting distribution of ün
Gaussian. The results with other values of and 3 are deferred to Appendix D.4
Occasional Projection For a = 0.8 and = 0.6, we run 50000 steps of LPSA over 5 repetition Synthetic (1, 1). Then compute the rescaled sequence ú, and project them along two random directions é and E2. The trajectories depicted in F that the limits of (ūn, ei) and n E2) nonzero and verify the asymptotic biased of un mentioned in Corollary The results with other values of a and / are deferred to Appendix D.6
Concluding Remarks
In this paper study the linearly constrained optimization problem. We propose the LPSA algorithm that is inspired by Local SGD. The probabilistic projection in LPSA follows the spirit of loopless methods [16, 12 28 and simplifies the double-loop structure of original Local SGD, facilitating theoretical analysis. We thoroughly analyze the (non-)asy masy)Jasymptotic properties
properly scaled trajectories obtained from {u,} and discover interesting phase transition where {u, changes from asymptotically normal to asymptotically biased as the projection frequency decreases. From a technical level, generalize jump diffusion approximations accommodate the particularity and discontinuity of LPSA.
There also some open problems. It is unclear about the asymptotic behavior of u, when 3 = 0.5. ie., Pn. ( (, The jump diffusion approach fails because we can't analyze {un} via the length of { anymore. It accounts for failure that {ū,,} and (Ø,.) are incompatible in the sense that they use different time scales and the time interpolation. However,
speculate ün would finally converge weakly to a non-centred Gaussian distribution. In addition, it is also interesting to analyze the performance of projection complexity of LPSA. From Corollary achieve better convergence rate at lower projection frequencies, we must overcome the asymptotically biased nature of u,, One feasible approach is to build 'de-biasing' algorithm which attenuates the effect of U,, during the update of u, We leave them as future work.
Acknowledgments and Disclosure of Funding
This work has been supported by the National Natural Science Foundation of China (No. 12271011).

---

References
[1] Ahmed Khaled Ragab Bayoumi, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 2519-4522 2020.
[2] Pascal Bianchi, Gersende Fort, and Walid Hachem. Performance of a distributed stochastic approximation algorithm. IEEE Transactions Information Theory,
2013.
[3] Patrick Billingsley. Probability and measure. John Wiley & Sons, 2008
[4] Patrick Billingsley. Convergence of probability measures. John Wiley & Sons, 2013.
[5] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122) 2011.
[6] Jianqing Fan, Wenyan Gong, Chris Junchi Li, and Qiang Sun. Statistical sparse online regression: A diffusion approximation perspective. In International Conference on Artificial Intelligence and Statistics, pages 1017-1026. PMLR, 2018.
[7] Yuanyuan Feng, Tingran Gao, Lei Li, Jian-Guo Liu, and Yulong Lu. Uniform-in-time weak error analysis for stochastic gradient descent algorithms via diffusion approximation. Communications in Mathematical Sciences, 18(1):163-188, 2020.
[8] Xavier Fontaine, Valentin De Bortoli, and Alain Durmus. Convergence rates and approximation results for SGD and its continuous time counterpart. In Conference Learning Theory, pages 1958. PMLR, 2021.
[9] S. Gadat. Stochastic Optimization algorithms. 2012.
[10] Sébastien Gadat, Fabien Panloup, and Sofiane Saadane. Stochastic heavy ball. Electronic Journal of Statistics, 12(1):461-529, 2018.
[11] Matilde Gargiani, Andrea Zanelli, Andrea Martinelli, Tyler Summers, and John Lygeros. PAGE- PG: A simple and loopless variance-reduced policy gradient method with probabilistic gradient estimation. arXiv preprint arXiv:2202.00308 2022.
[12] Filip Hanzely and Peter Richtárik. Federated learning of mixture of global and local models. arXiv preprint a5X1v:2002.05516 2020.
[13] Li He. Qi Meng, Wei Chen, Zhi-Ming Ma, and Tie- Yan Liu. Differential equations for modeling asynchronous algorithms. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 2220-2226. 2018
[14] Peter Kloeden and Eckhard Platen. Numerical solution of stochastic differential equations. IEEE transactions on neural networks a publication of the IEEE Neural Networks Council, 19:1991, 12 2008.
[15] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In International Conference Machine Learning, pages 5381-5393. PMLR, 2020.
[16] Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Algorithmic Learning Theory, pages 451 4577 PMLR, 2020.
[17] Thomas Kurtz. Extensions of Trotter's operator semigroup approximation theorems. Journal of Functional Analysis, 3(3):354-375, 1969.
[18] Thomas G Kurtz. A general theorem on the convergence of operator semigroups. Transactions of the American Mathematical Society, 148(1): 1:23-32, 1970.
[19] Thomas G Kurtz. Semigroups of conditioned shifts and approximation of Markov processes.
The Annals of Probability, pages 618-642, 1975.
10

---

[20] Harold J Kushner. A martingale method for the convergence of a sequence of processes to jump- jump-diffusion process. Zeitschrift für Vahnscheinnichkeeisthoooe und Verwandte Gebiete, 53 (2):207-219, 1980.
[21] Harold J Kushner and Hai Huang. Asymptotic properties of stochastic approximations with constant coefficients. SIAM Journal on Control and Optimization, 19(1):87-105, 1981.
[22] Harold Kushner and G Yin. Asymptotic properties of distributed and communicating stochastic approximation algorithms. SIAM Journal on Control and Optimization, 25(5):1266 1290, 1987.
[23] Qianxiao Li, Cheng Tai, and E Weinan. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning, pages 2101-21 10. PMLR, 2017.
[24] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint 2018.
[25] Xiang Li and Zhihua Zhang. Delayed projection techniques for linearly constrained problems: Convergence rates, acceleration, and applications. arXiv preprint arXiv:2101.01505, 2021.
[26] Xiang Li, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Communication efficient decentral- ized training with multiple local updates. arXiv preprint arXiv:1910.09122 2019.
[27] Xiang Li, Jiadong Liang, Xiangyu Chang, and Zhihua Zhang. Statistical estimation and inference via local sgd federated learning. arXiv preprint arXiv:2109.01326, 2021.
[28] Zhize Li. ANITA: An optimal loopless accelerated variance-reduced gradient method. arXiv preprint urXiv:2103.1133. 2021.
[29] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference Machine Learning, pages 6286-6295 PMLR, 2021.
[30] Tao Lin, Sebastian U Stich, and Martin Jaggi. Don't use large mini- batches, use local sgd. arxiv preprint 1eXXvv1:88... 072177 2018
[31] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficee learning of deep networks from decentralized data. In Artificial Intelligence and Statistics (AISTATS), 2017.
[32] Yurii Nesterov. Lectures on Convex Optimization. 2018.
[33] Bernt Øksendal and Agnes Sulem. Stochastic Control of jump diffusions. Springer, 2005.
[34] Antonio Orvieto and Aurelien Lucchi. Continuous-time models for stochastic optimization algorithms. Advances in Neural Information Processing Systems, 32, 2019.
[35] Mariane Pelletier. Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Annals of Applied Probability, pages 10-44, 1998.
[36] Eckhard Platen and Nicola Bruti-Liberati. Numerical solution of stochastic differential equations with jumps in finance, volume 64. Springer Science Business Media, 2010.
[37] Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki Matematicheskoi Fiziki, 3(4):643-653, 1963.
[38] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pages 1674-1703. PMLR, 2017.
[39] Hale F Trotter. Approximation of semi-groups of operators. Pacific Journal Mathematics, (4):887-919, 1958.

---

[40] CZ Wei. Multivariate adaptive stochastic approximation. The annals of statistics, pages 1115- 1130, 1987.
[41] Andre Wibisono, Ashia Wilson, and Michael Jordan. A variational perspective on accelerated methods in optimization. proceedings of the National Academy of Sciences, 113(4))E87351- E7358, 2016.
[42] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In International Conference on Machine Learning, pages 10334-10343. PMLR, 2020.
[43] Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local SGD for heterogeneous distributed learning. In Advances in Neural Information Processing Systems, volume 33, pages 2281-6292, 2020.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See the Introduction part and the comparison with
previous works in Appendix A
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts your work? [N/A] Our work is purely theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] They are all deferred in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] We describe the experimental details in Appendix D
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix [
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] Our experiments use synthetic datasets validate the theoretical results. It is easy to reproduce the experiments on an average computer using only CPUs.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "jTFx-mfW_NB", "reviewer": "Reviewer_RZGN", "summary": "The paper considers the problem of stochastic convex optimization with linear constraints. They proposed the so-called loopless projected stochastic approximation (LPSA) that randomly performs or skip the project step at each iteration. The authors provide the non-asymptotic convergence rate of the resulting algorithms. They also study the asymptotic behaviors of the algorithms under different conditions and parameters of the algorithm. Moreover, their asymptotic analysis provides insights of the effect of projection frequency on the convergence rates.\n", "questions": "The paper proposed a loopless stochastic approximation algorithm. The main results are obtained for stochastic convex optimization. For general stochastic approximation, the mean field is not necessary a gradient function. I wonder would the proofs of Theorem 3.3 and Theorem 3.4 be easily adapted to this case?\n", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and technically strong. Analyzing asymptotic convergence rate of stochastic approximation algorithms with projection is generally difficult because of the discontinuous dynamics (which people usually resort to stochastic inclusion for establishing convergence). I did not check the proofs in the appendix, but outlines of proofs seems plausible. \nThe results they obtained reveal the relationship between convergence rate and the tuning parameter that controls projection frequency, which is useful in practice.\n\n\nWeakness:\nCurrently, the experiment focuses on validating convergence rate of the proposed algorithm. Since the paper consider stochastic optimization with projection. It could help readers understand the effect of loopless projection better by providing plots of number of projections or computational complexity for each parameter setting, along with the MSE figure.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fGlKX1hxPx", "reviewer": "Reviewer_ikRt", "summary": "This paper analyzes the performance of projected SGD in solving constrained optimization problems. It shows that a bias-variance tradeoff appears in the choice of the frequency of the projection. This bias-variance tradeoff is shown is two ways:\n- a non-asymptotic analysis\n- an asymptotic description with continuous-time stochastic processes. \nUnderstanding this bias-variance tradeoff enables to use the optimal communication rate in federated learning. ", "questions": "Minor comments:\n(*) l.782: Can you explain \"entry-wise linear interpolation\"?\n(*) L.780, 4th equality: why is there no more projection on the last term?\n(*) eq. (16): should it be $v_{n+1}$ on the r.h.s.?\n(*) l.58: did you mean $p_n$ instead of $\\beta_n$?\n(*) Could you explain (or give a ref) for the sentence l.185-186?\n(*) l.232: should it be $-Y_{t-}$ instead of $-Y_{t}$?", "limitations": "I have none.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The continuous-time perspective provides an elegant perspective on the choice of the projection frequency: either we have convergence to a diffusion process (variance dominates) or to a process with Poisson jumps (bias dominates). \nIn general, this paper is well-written, elegant and rigorous. \nI do not master all the stochastic approximation results used in this paper. However, the authors introduce well the necessary tools, and provide all necessary references. \nIt seems that the techniques used in this paper could be used to understand other stochastic approximation algorithms. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "aVZYCqXd08C", "reviewer": "Reviewer_L3VQ", "summary": "This paper proposes a jump diffusion perspective for a loopless variant of stochastic approximation schemes, essentially replacing the loop-length ratios by flipping a coin at each time step and performing projections accordingly. The main result is that there is a phase transition depending on the parameter , which controls the projection rate. The authors prove that in the frequent projection regime (), the asymptotic behavior of the algorithm is close to a diffusion, while in the occasional projection regime the asymptotic behavior goes to a discontinuous jump diffusion.\n", "questions": "Since I'm not an expert in the field, I find the constant drift outcome to be counterintuitive. Usually in stochastic approximation, the algorithms converge to either the gradient flow or, in the stochastic case, Langevin diffusion. Is there any intuition why we should expect a constant drift for both the frequent and occasionally projection regimes?\n", "limitations": "In my opinion, the most significant limitation of the work is the assumption of strong convexity; in the non-federated setting, we know that strong convexity is not necessary; see [Kushner-Yin]. It would therefore be great if the authors can point out potential avenues to improving/relaxing these restrictive assumptions.\n\n[Kushner-Yin] Stochastic Approximation and Recursive Algorithms and Applications\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrength: The analysis technique is fairly straightforward: The proof goes by decomposing the target sequences into a first-order term and then high-order terms that vanish in the long run. This technique is standard in stochastic approximation but seems adequate for the authors' purposes.\n\nWeakness: The analysis relies heavily on strong convexity and does not seem to easily generalize to the non-strongly convex case; the latter, however, is of higher interest.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept