Faster federated optimization under second-order similarity
Authors: Ahmed Khaled
Chi Jin
Venue: ICLR 2023 poster (2023)
Keywords: federated learning
distributed optimization
hessian similarity
client sampling
stochastic proximal point
proximal point method
distributed learning

Abstract: Federated learning (FL) is a subfield of machine learning where multiple clients try to collaboratively learn a model over a network under communication constraints. We consider finite-sum federated optimization under a second-order function similarity condition and strong convexity, and propose two new algorithms: SVRP and Catalyzed SVRP. This second-order similarity condition has grown popular recently, and is satisfied in many applications including distributed statistical learning and differentially private empirical risk minimization. The first algorithm, SVRP, combines approximate stochastic proximal point evaluations, client sampling, and variance reduction. We show that SVRP is communication efficient and achieves superior performance to many existing algorithms when function similarity is high enough. Our second algorithm, Catalyzed SVRP, is a Catalyst-accelerated variant of SVRP that achieves even better performance and uniformly improves upon existing algorithms for federated optimization under second-order similarity and strong convexity. In the course of analyzing these algorithms, we provide a new analysis of the Stochastic Proximal Point Method (SPPM) that might be of independent interest. Our analysis of SPPM is simple, allows for approximate proximal point evaluations, does not require any smoothness assumptions, and shows a clear benefit in communication complexity over ordinary distributed stochastic gradient descent.

Published as a conference paper at ICLR 2023
FASTER FEDERATED OPTIMIZATION UNDER SECOND- ORDER SIMILARITY
Ahmed Khaled
Chi Jin
Princeton University
Princeton University
ABSTRACT
Federated learning (FL. is subfield of machine learning where multiple clients try to collaboratively learn model over a network under communication constraints. We consider finite-sum federated optimization under a second-order function sim- ilarity condition and strong convexity, and propose two new algorithms: SVRP and Catalyzed SVRP. This second-order similarity condition has grown popular cently, and is satisfied in many applications including distributed statistical learning and differentially private empirical risk minimization. The first algorithm, SVRP, combines approximate stochastic proximal point evaluations, client sampling, and variance reduction. We show that SVRP is communication efficient and achieves superior performance to many existing algorithms when function similarity is high enough. Our second algorithm, Catalyzed SVRP, is Catalyst-accelerated variant of SVRP that achieves even better performance and uniformly improves upon existing algorithms for federated optimization under second-order similarity and strong convexity. In the course of analyzing these algorithms, we provide a new analysis of the Stochastic Proximal Point Method (SPPM) that might be of inde- pendent interest. Our analysis of SPPM is simple, allows for approximate proximal point evaluations, does not require any smoothness assumptions, and shows a clear benefit in communication complexity over ordinary distributed stochastic gradient descent.
INTRODUCTION
Federated Learning (FL) is a subfield of machine learning where many clients (e.g. mobile phones or hospitals) collaboratively try to solve learning task over a network without sharing their data. Federated Learning finds applications in many areas including healthcare, Internet of Things (IoT) devices, manufacturing, and natural language processing tasks (Kairouz al., 2019; Nguyen et al., 2021; Liu et al., 2021). One of the central problems of FI. is federated or distributed optimization. Federated optimization has been the subject of intensive ongoing research effort over the past few years (Wang et al., 2021). The standard formulation of federated optimization is to solve minimization problem:
min [f(x) EM
(I) where each function fm represents the empirical risk of model x calculated using the data on the m-th client, out of a total of M clients. Each client is connected to central server tasked with coordinating the learning process. We shall assume that the loss on each client is ju-stroglyy convex.
Because the model dimensionality d is often large in practice, the most popular methods for solving Problem (1) are first-order methods that only access gradients and do not require higher-order derivative information. Such methods include distributed (stochastic) gradient descent, FedAvg (also known as Local SGD) (Konečný al., 2016), FedProx (also known as the Stochastie Proximal Point Method) (Li al., 2020b), SCAFFOLD (Karimireddy et al., 2020b), and others. These algorithms typically follow the the optimization process is divided into several communication rounds. In each of these rounds, the server sends a model to the clients, they do some local work, and then send back updated models. The server aggregates these models and starts another round.
framework (Woodworth et al., 202 I):
Problem (1) is an example of the well-studied finite-sum minimization problem, for which we have tightly matching lower and upper bounds (Woodworth & Srebro, 2016). The chief quality that

---

Published as a conference paper at ICLR 2023
differentiates federated optimization from the finite-sum minimization problem is that we mainly care about communication complexity rather than the number of gradient accesses. That is, we care about the number of times that each node communicates with the central server rather than the number of local gradients accessed on each machine. This is because the cost of communication is often much higher than the cost of local computation, as Kairouz et al. (2019) state: "It is now well-understood that communication can be a primary bottleneck for federated learning."
One of the main sources of this bottleneck is that when all clients participate in the learning process. the cost of communication can be very high (Shahid et al., 2021). This can be alleviated in part by using client sampling (also known as partial participation): by sampling only a small number of clients for each round of communication, we can reduce the communication burden while retaining or even accelerating the training process (Chen et al., 2022).
Our main focus in this paper is to develop methods for solving Problem (1) using client sampling and under the following assumption:
Assumption 1. (Second-order similarity). We assume that for all x, y E2 we have
1 M ΣM ( - V - 8 || - yl?
Assumption is a slight generalization of the ő-relatedness assumption used by Arjevani & Shamir (2015) in the context of quadratic optimization and by Sun et al. (2022) for strongly-convex opti- mization. It is also known as function similarity (Kovalev et al., 2022). Assumption 1 holds (with relatively small 8) in many practical settings, including statistical learning for quadratics (Shamir et al., 2014), generalized linear models (Hendrikx et al., 2020), and semi supervieee learning (Chayti & Karimireddy, 2022). We provide more details on the applications of second-order similarity in Appendix B. Under full participation communication model where all clients participate each iteration, several methods can solve Problem (1) under Assumption 1, including ones that tightly match existing lower bounds (Kovalev et al., 2022). In contrast, for the setting consider (partial participation or client sampling), no lower bounds are known. The main question of our work is:
Can we design faster methods for federated optimization (Problem (1)) under second-order similarity (Assumption 1) using client sampling?
1.1 CONTRIBUTIONS
We answer the above question in the affirmative and show the utility of using client sampling in optimization under second-order similarity for strongly convex objectives. Our main contributions are follows:
A new algorithm for federated optimization (SVRP, Algorithm 2). We develop new algorithm, SVRP (Stochastic Muriance-Reducee Proximal Point), that utilizes client sampling to improve upon the existing algorithms for solving Problem I under second-order similarity. SVRP has better dependence on the number of clients M in its communication complexity than all existing algorithms (see Table 1), and achieves superior performance when the dissimilarity constant 5 is small enough. SVRP trades off a higher computational complexity for less communication. Catalyst-accelerated SVRP. By using Catalyst (Lin et al., 2015), we accelerate SVRP and obtain a new algorithm (Catalyzed SVRP) that improves the dependence on the effective conditioning
from 82 n to /². Catalyzed SVRP also has a better convergence rate (in number of communication steps, ignoring constants and logarithmic factors) than all existing accelerated algorithms for this problem under Assumption 1, reducing the dependence on the number clients multiplied by the
effective conditioning V from V /I.M to V 1//3/ (see Table 1).
While both SVRP and Catalyzed SVRP achieve a communication complexity that is better than algorithms designed for the standard finite-sum setting (like SVRG or SAGA), the computational complexity is lot worse. This is because we tradeoff local computation complexity for reduced communication complexity. Additionally, both SVRP and Catalyzed SVRP are based upon a novel combination of variance-reduction techniques and the stochastic proximal point method (SPPM). SPPM is our starting point, and we provide a new analysis for it that might be of independent interest. Our analysis of SPPM is simple, allows for approximate evaluations of the proximal operator, and
2

---

Published as a conference paper at ICLR 2023
Method
Communication Complexity
Non-quadratie?
Reference
DANE
M
X
(Shamir et al., 2014)
DiSCO
0
X
(Zhang & Lin, 2015)
SCAFFOLD
A+L
M
X
(Karimireddy et al., 2020b)
SONATA
0
M
(Sun et al., 2022)
Accelerated SONATA
0
EM
(Tian et al., 2022)
Accelerated Extragradient
0
(Kovalev al., 2022)
Lower Bound (no sampling)
6
(Arjevani & Shamir, 2015)
SVRP
0
M)
Theorem 2 (NEW)
Catalyzed SVRP
Ma/4 + M)
Theorem (NEW)
Table I: Communication complexity of different methods for solving Problem 1 under f--strong convexity, L-smoothness, and Assumption 1. Ó(- ignore polylogarithmic factors and constants. We use the client sampling model, which counts exchanging vector between the server and one of the clients as a single communication step.
extends to include variance reduction. In Appendix H we also consider the more general constrained optimization problem and provide similar convergence rates in that setting.
2 RELATED WORK
Distributed optimization under Assumption There is long line of work analyzing distributed optimization under Assumption and strong convexity: Shamir et al. (2014) first gave DANE and analyzed for quadratics, and showed the benefits of using second-order similarity the setting of statistical learning for quadratic objectives. Zhang & Lin (2015) developed the DiSCO algorithm that improved upon DANE for quadratics, and also analyzed for self-concordant objectives. Arjevani Shamir (2015) gave lower bound that matched the rate given by DANE, though without allowing for client sampling. The theory of DANE was later improved in (Yuan & Li, 2019), allowing for local convergence for non-quadratic objectives. Another algorithm SCAFFOLD (Karimireddy et al., 2020b) can be seen as a variant of DANE and is also analyzed for quadratics. the context of decentralized optimization, Sun al. (2022) gave SONATA and showed similar rate to DANE but for general strongly convex objectives, then Tian et al. (2022) improved the convergence rate of SONATA by acceleration. Finally, Kovalev al. (2022) improved the convergence rate of accelerated SONATA even further by removing extra logarithmic factors. We give an overview of all related results in Table and provide more thorough comparisons in the theory and algorithms section.
A parallel line of work considers Assumption as special case of relative strong convexity and smoothness and utilizes methods based on mirror descent. Hendrikx et al. (2020) take this view and consider an accelerated variant of mirror descent in the distributed setting, while Dragomir et al. (2021) also consider sampling and ceriancerrdductio Because this setting much more general, is more challenging to prove tight convergence rates, and in the worst-case the convergence rates are no better than the minimax rate under only smoothness and strong convexity.
Another line of work considers federated optimization for Problem under Assumption but without convexity, as well as optimization under the scenario where the number of clients is very large or infinite. Examples of this include MIME (Karimireddy et al., 2020a), FedShufflcMVR (Horváth et al., 2022), as well as AuxMom and AuxMVR (Chayti & Karimireddy, 2022). Our focus this work is on the convex setting.
Stochastic Proximal Point Method. The stochastic proximal point method (SPPM) is our starting point in developing SVRP and its Catalyzed variant. SPPM is well-studied, and only briefly review some results on its convergence: Bertsekas (2011) terms the incremental proximal point method, and provides analysis showing nonasymptotic convergence around solution under the assumptions
3

---

Published as a conference paper at ICLR 2023
that each fm is Lipschitz. Ryu & Boyd (2014) provide convergence rates for the algorithm, and observe that it is stable to learning rate misspecification unlike stochastic gradient descent (SGD). Pätraşcu & Necoara (2017) analyze SPPM for constrained optimization with random projections. Asi & Duchi (2019) study a more general method (AProx) that includes SPPM as special case, giving stability and convergence rates under convexity. Asi et al. (2020); Chadha et al. (2022) further consider minibatching and convergence under interpolation for AProx.
In the context of federated learning for non-convex optimization, SPPM is also known as FedProx (Li et al., 2020b) and has been analyzed in several settings, see e.g. (Yuan & Li, 2022). Unfortunately, in the non-convex setting the convergence rates achieved by FedProx/SPPM are no better than SGD. SPPM can be applied to more than just federated learning and has found applications in matrix and tensor completion (Bumin & Huang, 2021) and reinforcement learning (Asadi et al., 2021). It can also be implemented efficiently for various optimization problems (Shtoff, 2022).
Compression for communication efficiency. Client sampling is one way of achieving commu- nication efficiency, but there are other ways to do that in federated learning, such compressing the vectors exchanged between the server and the clients. Szlendak et al. (2022); Beznosikov Gasnikov (2022) consider federated optimization with compression under Assumption 1 and obtain better convergence rates using specially-crafee compression operators. Because these techniques are orthogonal, exploring combinations of client sampling and compression may be promising avenue for future work.
3 PRELIMINARIES
We say that a differentiable function f is justtronly convex (for μ 0) if for all æ, E Id we have f() 2 (V) + [VI(y)x=-1) + - - yl1². We assume:
Assumption 2. All the functions f1. J2..... J's in problem (1) are j-stroogly convex. We also assume Problem (1) has a solution z, E Rd.
The assumption that every fm is strongly convex is common in the analysis of federated learning algorithms (Karimireddy et al., 2020b; Mishchenko et al., 2022h) and is often realized when each fm represents convex empirical loss with fz-regularization. We assume that f has minimizer 2.. and by strong convexity this minimizer is unique. The proximal mapping associated with a function and stepsize 1 0 defined
prox (x) arg mingeRs (nh(y) + l1y ==1²]
When convex, the minimization problem has a unique solution and hence the proximal operator is well-defined. We say that point E IR is b-approximation of the proximal operator evaluated if || prox,, [x)]] b. When h fm for some m [M], computing the proximal operator is equivalent to solving a local optimization problem on node m.
4 ALGORITHMM AND THEORY
In this section we develop the main algorithms of our work for solving Problem 1 under Assumption 1, smoothness, and strong convexity. In the first subsection, we analyze the stochastic proximal point method and explore some of its desirable properties. Next, augment the stochastic proximal point method with variance-reduee reduccion and develop SVRP, a novel algorithm that improves upon existing the Catalyst acceleration framework (Lin et al.,
algorithms using client sampling. Finally, 2015) to improve the convergence rate of SVRP. We give more details on how the algorithms are applied in client-server setting in Appendix I.
4.1 BASICS: STOCHASTIC PROXIMAL POINT METHOD
The starting point of our investigation is the stochastic proximal point method (SPPM) (Algorithm 1), because the stochastic proximal point algorithm can achieve rates of convergence that are smoothness- independent and which rely only on the strong convexity of the minimization objectives (Asi &
4

---

Published as a conference paper at ICLR 2023
Algorithm 1: Stochastic Proximal Point Method (SPPM)
Data: Stepsize 77, initialization zo, number of steps K, proximal solution accuracy b.
for k = 0, 2,,..... K - 1 do
Sample & ~ DD
Update with b-approximation of the stochastic proximal point operator:
Th+1 = proSnfeu (Ix).
Duchi, 2019). This makes SPPM a much better starting point for developing new algorithms if our goal to obtain convergence rates that depend on the dissimilarity constant å instead of the (typically larger) smoothness constant L. The stochastic proximal point can be applied to the general stochastic expectation problem, which has the following form:
min [f(z) = E [f)(l
(2)
where each fe is ju-strongly convex and differentiable. Observe that Problem (1) is special case of (2) where DD has finite support. We assume that f has a (necessarily unique) minimizer T.. In this formulation, sampling new D corresponds sampling node/client in federated optimization, and then a proximal iteration corresponds to a local optimization problem to be solved on node g. The next theorem characterizes the convergence of SPPM in this setting:
Theorem 1. Suppose that Se is almost surely p-strongly convex, let x. be the minimizer of S, and define of BęnD fe Suppose that for each k we have that Ik+1 is b-approximation
(nu))²
||e 2.11]] S after K iterations:
of the proximal. Set 17 207 and s [I+nu]z Then E
K =
20 p
log 41120-2,1
The full proofs of all the theorems relegated to the supplementary material. Theorem for SPPM essentially gives the same rate as (Asi & Duchi, 2019, Proposition 5.3) but with different proof technique. Our analysis relies on a straightforward application of the contractivity of the proximal, making it easier to extend to the variance-reduced case compared to the more involved analysis of (Asi & Duchi, 2019).
Comparison with SGD. The iteration complexity of SGD in the same setting is:
22 + KSGD =(2
20 4
log (211===211²)
See (Needell et al., 2014; Gower et al., 2019) for derivation of this iteration complexity and (Nguyen al., 2019) for matching lower bound (up to log factors and constants). Observe that while the dependence on the stochastic noise term is the same in both (3) and (4), the iteration complexity of SGD also has an additional dependence on the condition number к 1L2 while the iteration complexity of the stochastic proximal point method is entirely independent of the magnitude of the smoothness constant L. Thus, we obtain faster convergence rate than SGD we have access to stochastic proximal operator evaluations. federated optimization, a stochastic proximal operator evaluation can be done entirely with local work and with no communication, and thus is relatively cheap. Indeed, the iteration complexity of SPPM can even beat accelerated SGD because acceleration only reduces the dependence on the condition number from T./ to / T./j,, whereas SPPM has no dependence on the condition number to begin with.
Communication vs computation complexities. Every iteration of SPPM involves two communica- tion steps: the server sends the current iterate 2i to node ç. and then node & sends Th+4 back the server. Thus the communication complexity of SPPM is the same as eq. (3) multiplied by two. Each node needs to solve the optimization problem
mingERd
[e(()) + 27 | xx
up to the accuracy b given in Theorem If each fs is L-smooth and j--ttrongly convex, this is I + -mooohh and y + 27 -stroonglyy convex minimization problem, and thus be solved to the
5

---

Published as a conference paper at ICLR 2023
Algorithm 2: Stochastic Variance-Reducca Proximal Point (SVRP) Method
Data: Stepsize 7), initialization zo, number of steps K, communication probability p, local
solution accuracy b.
Initialize Wg _p.
for k = 0, 2,.,...... K do
Sample my uniformly at random from [M].
Set
Jk = vf(w)) V Fmm (wx).
Compute a b-approximation of the stochastic proximal point operator associated with fm;:
1 prox nfmg (xx (9k)
Sample c ~ Bernoullipp) and update wk+1 = Fk+1 if C₁ 1,
if C₁ O.
desired precision b in O (Nesterov, 2018). When 7j
(v
xL+1 m-+1
log b) local gradient accesses using accelerated gradient descent this corresponds to a per-iteration computational complexity of 2
uue
O pLe+402 p²c+40? log +t) Note that if fe itself represents the loss on a local dataset (as is common in federated learning). may methods tailored for stochastic finite-sum problems such as Random Reshuffling (Mishchenko et al., 2020), Katyusha (Allen-Zhu, 2017), or (accelerated) SVRG. Thus we see that, compared SGD, SPPM trades off a higher computational complexity for lower communication complexity.
Related work. We compare against related convergence results for SPPM in Appendix E.
4.2 THE SVRP ALGORITHM
The rate of SPPM, while independent of the condition number k L, is sublinear. While sublinear rate optimal for the stochastic oracle (Foster et al., 2019; Woodworth Srebro, 2021), it is suboptimal in the setting of smooth finite-sum minimization (Woodworth & Srebro, 2016). In this section, we develop a novel variance-reducct method, SVRP (Stochastic Seriance-Reducee Proximal Method, Algorithm 2), that converges linearly and relies only on second-order similarity.
Variance-reduuce methods such as SVRG (Johnson & Zhang, 2013), SAGA (Defazio et al., 2014) SARAH (Nguyen et al., 2017) improve the convergence rate of SGD for finite-sum problems by constructing gradient estimators whose variance vanishes over time. While SGD is used as the building block in most existing variance-reduced methods, in the preceding section we that the stochastic proximal point method is more communication-erie -effiiciennff It stands to reason that variance- reduced variants of SPPM could also be more communication-efficee efficient under second-order similarity. We apply variance-reduction to SPPM and develop our algorithm in the next two steps.
Step (a): Adapting SVRG-style variance reduction SPPM. We use SVRG-style variance- reduction coupled with the stochastic proximal point method as base. To see how, we start with SGD iterations: at each step we sample node my uniformly random from [M] and update as
Tk+1 = 24 fm (xx)-
The main problem with SGD is that the stochastic gradient estimator has non-vanishing variance that slows down convergence. SVRG (Johnson Zhang, 2013) modifies SGD by adding a correction term at each iteration:
gh (w(w - V fm (wx). Ik+1 = Tt 17 [m (xx) + gxl
where wa is an anchor point that is periodically reset to the current iterate. Thus we added the correction term gk in order reduce the variance in the gradient estimator and allow the algorithm to

---

Published as a conference paper at ICLR 2023
converge. We propose to do the same for the stochastic proximal point method, where instead change the argument to the proximal operator:
9k: Vf(w)) - V. (wx);
1k+1
praxnfmx (æt 179h)
We expect the correction term Ok to function similarly and allow SPPM converge faster.
Step (b); Removing the loop. Rather than reset the anchor point wi to the current iterate at fixed intervals, SVRP instead loopless: it uses random coin flip to determine when to communicate and re-compute full gradients. Loopless variants of variance-reduced algorithms such as L-SVRG (Ko- valev et al., 2020) and Loopless SARAH (Li et al., 2020a) enjoy the same convergence guarantees as their ordinary counterparts, but with superior empirical performance and simpler analysis.
Combining the previous two steps gives SVRP (Algorithm 2), and we give the convergence result next.
Theorem 2. (Convergence of SVRP). Suppose that Assumptions I and 2 hold, and that each Tk+1 is
a b-approximation of the proximal (5). Let = min [I=2mu {/ {. Set the parameters of Algorithm
as 1j 262 2(1+ma)33 and 1 M Then the final iterate IK satisfies E
f b <m(m))²
|| x.11? S
provided that the total number of iterations K is larger than Tster:
T Fter ÓŌ ((M + 6² log
Communication complexity. We consider one communication to represent the server exchanging one vector with one client. At each step of SVRP, server samples client my and sends them current iterate the client then computes ÿı: and Jx++ locally, and sends #6+1 back to the server. Then, with probability p. the server changes the anchor point Wk+1 to #K+1, sends WK+1 to the new clients, each client then computes V fm fmm(k+)) (Wk+1) and sends it back to the server, which averages
the received gradients to get ff( The server then proceeds to send V ((W*+1) back to all the clients. Thus the expected communication complexity is
E [eomm (2 + 3pM) Tit 5Teer =6 ((M++ (²) log :).
Compared the SVRG communication complexity ô ((M+ 1.) log
(Sebbouh al., 2019), this replaces the L/μ dependence with a 6²/ /p² dependence. This better when 8 S VLu.
Comparison with existing results. The lower bound related the most to our setting is given by (Arjevani & Shamir, 2015), only considers the setting of full participation (i.e. no client sampling) and corresponds to communication complexity of Ô (v /TMM Our result improves upon this when
M > (6/p)3/2 Note that while our result attains superior dependence M, the dependence on the effective conditioning 6/μu is worse. In the next section, we shall improve this via acceleration. Note that the best existing results for optimization under second-order similarity, such as DiSCO (Zhang & Lin, 2015), Accelerated SONATA (Tian et al., 2022), and Extragradient sliding (Kovalev et al., 2022), match this lower bound (Kovalev al., 2022, Table 1). Therefore, our result shows that significantly better convergence can be obtained under second-order similarity when using client sampling.
Computational complexity. Similar to the discussion of the computational complexity of SPPM in the previous section, here too we essentially need to solve on each sampled device an optimization problem involving an -)-mmooth and (1) convex function up the accuracy b. This
can be done using accelerated gradient descent in Ô (v
Lt
log :) Ō ptn
282 log !
gradient
accesses. Compared to SGD or SVRG, we can see that we trade off a higher local Computational complexity for a lower number of communications steps to convergence.
Similar methods. Point-SAGA (Defazio, 2016) uses the stochastic proximal point method coupled with SAGA-style variance reduction. Point-SAGA achieves optimal performance under smoothness
7

---

Published as a conference paper at ICLR 2023
and strong convexity, but it inherits the heavy memory requirements of SAGA and its performance under Assumption is unknown. Another similar algorithm is SCAFFOLD (Karimireddy et al., 2020b): SCAFFOLD uses a similar SVRG-style correction sequence, and their method can be viewed as approximately solving a local unregularized minimization problem at each step. Unfortunately, their analysis under Assumption only holds for quadratic objectives and without client sampling.
4.3 ACCELERATING SVRP VIA CATALYST
In this section we improve SVRP by augmenting with acceleration. Acceleration is an effective way to improve the convergence rate of first-order gradient methods, capable of achieving better convergence rates in deterministic (Nesterov, 2018), finite-sum (Allen-Zhu, 2017), and stochastic (Jain al., 2018) settings. Catalyst (Lin al., 2015) is generic framework for accelerated first-order methods that we utilize to accelerate SVRP. Catalyst (Algorithm 3) is essentially an accelerated proximal point method that relies on solver A to solve the proximal point iterations. We use SVRP (Algorithm 2) as the solver A. and term the resulting algorithm Catalyzed SVRP.
Catalyst gives us fast linear convergence provided that we solve certain regularized subproblems to a high accuracy. To do that, we run SVRP (as the method A) with an appropriate set of parameters and for a fixed number of iterations. The details of our application of Catalyst are given in the supplementary material (Appendix G). The complexity of Catalyzed SVRP is given next.
Theorem 3. (Catalyzed SVRP convergence rate). For Catalyst (Algorithm 3) with SVRP (Algorithm 2) as the inner solver A, suppose Assumptions and hold, and that I'is L-smooth. Then for a specific choice of the algorithum parameters. the expected communication complexity E [T [Tcomm) to reach an accuracy e, up to polylogarithmic factors and absolute constants, is
E [T comm] = ((M +
(MM+VEMM (EMSIA 4)
(6)
Improvement over SVRP. Compared to ordinary SVRP, observe that since v /M33 S M+
Theorem gives a communication complexity that always better than what Theorem 2 provides up to logarithmic factors. In particular, the rate of Catalyzed SVRP given by (6) is strictly better than the rate of vanilla SVRP when á < /M. Note that unlike the communication complexity given by Theorem 2, the rate given by Theorem 3 requires smoothness, but the smoothness constant L only shows up inside logarithmic factor, and hence does not show up in eq. (6) (as Ô notation hides polylogarithiic factors).
Comparison with the smooth setting. When each function is L-smooth and p-strongly convex, Accelerated variants of SVRG reach an c-accurate solution in Ô (M MV/2 communication steps and (1) local work per node (Lin et al., 2015). The communication complexity Catalyzed SVRP achieves is better when 8 < L.
VM* at the cost of more local computation.
Improvement over prior work. The best existing algorithms for solving Problem (1) under Assump- tion I are Accelerated SONATA (Tian et al., 2022) and Extragradient sliding (Kovalev et al., 2022), both of which achieve communication complexity of Ô V.MM). The rate given by eq. (6) is better than this rate, achieving smaller dependence on the number of nodes M. Arjevani & Shamir (2015) give a lower bound matching the rate δ (v (LM) ignoring polylogarithmic factors, our result improves upon their lower bound through the usage of client sampling. This improvement is possible because Arjevani & Shamir (2015) use an oracle model that does not allow for client sampling. Thus, Catalyzed SVRP improves upon all existing methods for optimization under Assumption 1, smoothness, and strong convexity when ó is sufficiently small.
Computational complexity. Catalyzed SVRP uses SVRP as an inner solver, and hence inherits its computational requirements: at each iteration k. we have to sample node my and evaluate the proximal operator associated with its local objective fmg- However, we set the solution accuracy to b = 0 when applying Catalyst SVRP, i.e. we require exact stochastic proximal operator evaluation; This is only done for convenience of analysis, and we believe the analysis can be extended to the case of nonzero but small b. In practice, the proximal operation can be computed exactly in many cases,
8

---

Published as a conference paper at ICLR 2023
JILL
Aeaee Eocageadert
Acae
SCAPTOLD
SCAPTLL
ACORMMAL Dispues
33-
33"
$0.00
2032
2855
2051
1956
14-
374
SANG
SCATTOL
19-
SCATFOLD
SCATFOLD
13-
38:77
33
Top experiments synthetic data. Left figure has M = 1000 clients, middle has M = 2000, and right has M = 3000. Bottom row: experiments on real data. Left has M = 20 clients, middle has M 40 clients, and right has M 60 clients. We plot the squared distance from the optimum point for all methods on logarithmic scale versus the number of communication steps, where one exchange of vectors between the server and single client counts as a communication step.
Figure 1:
and otherwise we can compute the proximal operator to machine accuracy using accelerated gradient descent.
EXPERIMENTS
We run linear regression with & regularization, where each client has loss function of the form f(x) = > [f(())
= Ei Bmm,)2 - 2 |
where 2m. E Rdd and Y/m,i R. represent the feature and label vectors respectively, for m E [M] and i E [n]. We do two sets of experiments: in the first set, generate the data vectors 2m, synthetically and force the second-order similarity assumption to hold with ō small relative to L. with L R 3330 and 8 x 10, and regularization constant X = 1. We vary the number of clients M as M E {1000, 2000, 3000}. In the second set, we use the "a9a" dataset from LIBSVM (Chang & Lin, 2011), each client's data is constructed by sampling from the original training dataset with 2000 samples per client. We vary the number of clients M as M E (20, 40, 60). and measure L Rs 6.33, 5 ~ 0.22, and the regularization parameter as 0.1. We simulate our results machine, running each method for 10000 communication steps. Our results are given in Figure 1. We compare SVRP against SVRG, SCAFFOLD, and the Accelcrated Extragradient algorithms, using the optimal theoretical stepsize for each algorithm. In all cases, SVRP achieves superior performance to existing algorithms for both the real and synthetic data experiments. This is more pronounced in the synthetic data experiments as 5 is much smaller than L and the number of agents M is very large.
single
6 CONCLUSION
In this paper, we develop two algorithms that utilize client sampling in order to reduce the amount of communication necessary for federated optimization under the second-order similarity assump- tion, with the faster of the two algorithms reducing the best-known communication complexity from δ (VEM) (Kovalev et al., 2022) to Ô ( M3/4 + M). Both algorithms utilize variance- reduction top of the stochastic proximal point algorithm, for which also provide simple and smoothness freeeseeeeeeeeeeeee analysis.
In all cases, the algorithms tradeoff more local work for reduced communication complexity. An important direction in future research is to investigate whether this tradeoff is necessary. and to derive lower bounds under the partial participation communication model and second-order similarity.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
All the theoretical results we derive are accompanied by full proof' in the appendices, and all the definitions and assumptions we make are clearly stated in the main text. We attach the code used to run the experiments as supplementary material to the paper.
REFERENCES
Zeyuan Allen-Zhu. Katyusha: the first direct acceleration of stochastic gradient methods. In Hamed Hatami, Pierre McKenzie, and Valerie King (eds.), Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing. STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pp. 1200-1205. ACM, 2017. doi: 10. 0144///53399.35555555 //doi. worg 10 11411145542 111111155555999 3055448. (Cited pages 6 and
URL https:
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (eds.), Advances Neural Information Processing Systems 28: Annual Conference on Neu- ral Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 1766-1764, 2015. URL https:ttpt.... //tp:pp:://pooeee/ http:///ccccecccccccccoccc neurips CC/ / 201 015 / html. (Cited pages 2, 2, and
Kavosh Asadi, Rasool Fakoor, Omer Gottesman, Taesup Kim, Michael Littman, and Alexander J. Smola. Proximal iteration for deep reinforcement learning. arXiv preprint arXiv:21 12.122200 05848, abs/2112.05848, 2021. URL
wttp:ii/..rr////////////bs aaw//asllli 05848. (Cited on page 4)
Hilal Asi and John C. Duchi. Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity. SIAM Journal on Optimization,, 29()):257-22290, 2019. doi: 10.1137/ 18m1230323. URL and 22)
www.:/doo.orggoo..ooooo.oo 1137 100.111111111223322222 (Cited on pages 4, 5,
Hilal Asi, Karan N. Chadha, Gary Cheng, and John C. Duchi. Minibatch stochastic approximate proximal point methods. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florrin Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL https: http:////cccccceeeeeeeeeeee wwwp:r/owwwww...e.e.eeeeoeeeeeep neurips cc / hwtpppppr////// 20200/ hash/fa2244 htt.:///2442aaffoae32222e22222..
Abstractt....................... html. (Cited on page 4)
Amir Beck. First-order methods in optimization. MOS-SIAM series on optimization. Society for Industrial and Applied Mathematics: Mathematical Optimization Society, 2017. ISBN 9781611974997. (Cited on pages 29, 30, and 31)
Dimitri P. Bertsekas. Incremental proximal methods for large scale convex optimization. Math- ematical Programming, 129(2):163-195 2011. doi: 10.1000//10107-011-001
URL
https:/ /ttp:///do...o wrgg 10. 1007 000007/1111 000000000011-222111001001111000- 0. (Cited on page 3)
Aleksandr Beznosikov and Alexander Gasnikov. Compression and data similarity: Combination of two techniques for communication--fficci solving of distributed variational inequalities. arXiv preprint arXiv:2206. 099066, abs/2206.09446,, 2022. URL https: / //t//a/xvvv/////////////////aa// www.eiiv...........ooeoee wwtp/b/////aaa//eeeoooo al/////s/22000 09446. (Cited page
Aysegul Bumin and Kejun Huang. Efficient implementation of stochastic proximal point algorithm for matrix and tensor completion. In 202/ / 29th European Signal Processing Conference (EUSIPCO). pp. 1050-1054. IEFE, 2021. (Cited on page 4)
Karan N. Chadha, Gary Cheng, and John C. Duchi. Accelerated, optimal and parallel: Some results on model-based stochastic optimization. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 2811 1-227. PMLR, 2022. (Cited on page 4)
Chih- Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http: /twp://wwwww../mmm es i ntu. edu. tw/ inn bsvm. (Cited page
10

---

Published as a conference paper at ICLR 2023
El Mahdi Chayti and Sai Praneeth Karimireddy. Optimization with access auxiliary information. arXiv preprint arXiv:2206. 2000:2206.00355,, abs/2206.00333 2022. URL https: /ttp///axxvvv... org/ abs/ 2206. 00395. (Cited pages 2, 3, and 17)
Gong Chen and Mare Teboulle. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538 -433385533, 1993. doi: 10.1137/0803026. URL htthhhtp::///ee /tti.//ooii//////////// org / 10. 1....110730000255 (Cited on page 19)
Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learning. Transactions on Machine Learning Research, 2022. URL https: http:///ppeeeeeeeeeeee net/
forum? Sooumiidd&GvRWKA..
(Cited on page 2)
Aaron Defazio. A simple practical accelerated method for finite sums. In Daniel D. Lec, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garett (eds.), Advances in Neural Information Processing Systems 29: Anmual Conference on Neu- ral Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. new.eeeddnnnnnnnnnnneeeeeee cc/paper/rrr..e. 220 6 6/hash/ aasteratt..................a.c.e html. (Cited on page
676-684, 2016. URL
Aaron Defazio, Francis R. Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradi- ent method with support for non-strongly convex composite objectives. In Zoubin Ghahra- mani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27: Anmual Conference on Neural In- formation Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 1646-1654, 2014. URL https: / http:///poece/eeeeeeeeee/eeces/e neurips cc/pppprrrrr http:sss.uuripps...ppppp////// 2204 4 /hash/ ede7e2b6d13ed 3 41dff 4bde f8 f447777777377 -bctrractt.. html. (Cited on page 6)
Radu-Alexandru Dragomir, Mathieu Even, and Hadrien Hendrikx. Fast stochastic bregman gradient methods: Sharp analysis and variance reduction. In Marina Meila and Tong Zhang (eds.), Pro- ceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2815-2825, PMLR, 2021. URL http://prrocedding ml www.ppees....t..mmmmmmmm. dragomir 121a html. (Cited on page 3)
Duistermaat. Multidimennsioaa real analysis. Cambridge University Press, 2004. ISBN 9780521551144, (Cited on page 18)
Dylan J. Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, and Blake E. Woodworth. The complexity of making the gradient small in stochastic convex optimization. In Alina Beygelzimer and Daniel Hsu (eds.), Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pp. 1319-1344 PMLR, 2019. URL http: / http:///cccceeee/ssse.s/ mlr. wwwpp//wseeeeeeeep http:///////ootereeeeeeeee wwsterssseereeeeeee 19b. 99. html. (Cited
on page 6)
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrlPS 2020, December 6-12, 2020, virtual, 2020. URL https: httpttt:tpppooeeeeeee http://pcceeee...e.ec nwwrips.......... cc ww/paper////peceeceeeccc /020/ tbt.baaaaattttaaaatatataaccaaac html. (Cited on page 17)
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5200-5209. PMLR, 2019. URL ngs ml press/es///// / v97 / / an 9b. html. (Cited on page 5)
Hadrien Hendrikx, Lin Xiao, Sébastien Bubeck, Francis R. Bach, and Laurent Massoulié. Statistically preconditioned accelerated gradient method for distributed optimization. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 4203 4227. PMLR, 2020. URL http: prw.eediniigg.... mlr, press//ss//........... /vvllll1111 httphendrixx2000 htmi. (Cited on pages 2, 3.
and 17)
11

---

Published as a conference paper at ICLR 2023
Samuel Horváth, Maziar Sanjabi, Lin Xiao, Peter Richtárik, and Michael Rabbat. FedShuffle: Recipes for better use of local work in federated learning. arXiv preprint arXiv: 14.113169, abs/2204.13169, 2022. URL https::////// http://xxvvvvvv.. abs//bb2.. (Cited page 3)
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent for least squares regression. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Conference On Learning Theory, COLT 20/8, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pp. 545-604, PMLR, 2018. URL http:////// / ptwppedince....oo//o wal..press//ee /vtess//v55// jaas/jainnlaa... html. (Cited page 8)
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceed- ings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. www.eediiinnnnu.urip...ee....e.e www.ips..p.... cw/pppprrrreeeccceteeeee / 2201 3/ hash/ 315-323, 2013. URL httes/9eeeeeeeeeee--aaatat html. (Cited on page 6)
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón. Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He. Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage. Ramesh Raskar, Dawn Song. Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. arXiv preprint arXiv: 1e1.9/92.999777 abs/1912.04977,, 2019. URL https: / / arriiv..ivvv////ii///aaaaaaaaavv . org/ abs/ 1912. 04977. (Cited on pages and 2)
Sai Praneeth Karimireddy, Martin Jaggi. Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint urXiv:2008. 003662000800666, 0bs/2008.036008 2020a. URL https:
//arXiv. wwwp/baag//ooooeeeoeeeeeeeeeeeeo www./200s 63606. (Cited on page 3)
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning. ICML. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 5132-5143. PMLR, 2020b. URL http:/ / /pppeediingg www.mmrrr.ss....... / 119 html. (Cited on pages 1, 3, 4, 8, and 17)
Junhyung Lyle Kim, Panos Toulis, and Anastasios Kyrillidis. Convergence and stability of the stochastic proximal point algorithm with momentum. In Roya Firoozi, Negar Mehr, Esen Yel, Rika Antonova, Jeannette Bohg, Mac Schwager, and Mykel Kochenderfer (eds.). Proceedings of The 4th Annual Learning for Dynamics and Control Conference, volume 168 of Proceedings of Machine Learning Research, pp. 1034-1047. PMIR, 2022. URL https:/ proceedings.. ml mlr. / v1 6 / k mm2.2 html. (Cited on page 22)
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated Learning: Strategies for Improving Communication Efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016. (Cited on page 1)
Dmitry Kovalev, Samuel Horváth, and Peter Richtárík. Don't 't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Aryeh Kontorovich and Gergely Neu (eds.), Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pp. 451-467, PMLR, 08 Feb-11 Feb 2020. URL https: http:////occeeeeneeee/ee mlr. www.ssressss.......... / v htt.///ooolvvvlv html. (Cited on page 7)
12

---

Published as a conference paper at ICLR 2023
Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander Gasnikov, and Gesualdo Scutari. Optimal gradient sliding and its application to distributed optimization under similarity. arXiv preprint wrxiv:2205.15188
2ts/2205.15136. 2022. URL htttp://aaxii....... org org/ abs/
2205. 15136. 6. (Cited on pages 2, 3, 7, 8, and 9)
Bingcong Li. Meng Ma, and Georgios B. Giannakis. On the convergence of SARAH and beyond. In Silvia Chiappa and Roberto Calandra (eds.), The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Ital],, volume 108 of Proceedings of Machine Learning Research, pp. 223-233. PMIR, 2020a. URL html. (Cited on page
http:// prwceedings mlr, press /
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Inderjit S. Dhillon, Dimitris S. Papailiopou- los, and Vivienne Sze (eds.). Proceedings of Machine Learning and Systems 2020, MLSys 2020, Austin, TX, USA, March 2-4, 2020. mlsys.org, 2020b. URL https: http::::////oceeeiieei .ww.iingn..msss.mmmmmmmmmmmmm... misys.. org/book / 316 6 påf. (Cited on pages and 4)
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimization. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Gamett (eds.), Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 3384-3392, 2015. URL https: http://epoocccccceeeeeeppoc wtwpeeeediinnnnuuiippeeeeeeeeeee ccccc//ppaee pec/paper/20 2taper/201. 201/2211552 2015/111110 5/5//110 /haah// htt.bbbbcdccc22222253cbbbbbbbbb. 26, and 30)
Abstractttbt.tt..... .atrra.tt..tl..................m html. (Cited on pages 4, 8, 25,
Ming Liu, Stella Ho, Mengqi Wang, Longxiang Gao, Yuan Jin, and He Zhang. Federated learning meets natural language processing: a survey, arXiv preprint arXiv:2107. 12603, abs/2107.12600 12603, 2021. URL https: htt.aaaxvvvv........ org.or////aa..oo.
(Cited page 1)
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL http::ttpps.cm / ppwpcedd ings neuripe ips. cc http//ppprr22000 hash/ htchhhhccccceeeeeee f 4 wttpeccccff44444eeeeeee4e 4e wwwpe/6111111111---------------- Abstract. html. (Cited on page 6)
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Proximal and federated random reshuffling. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 15718- 15749. PMLR, 2022a. (Cited on page 19)
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. ProxSkip: Yes! local gradient steps provably lead to communication acceleration! Finally! In ICML, volume 162 of Proceedings of Muchine Learning Rexearch, pp. 15750-15769. PMLR, 2022b. (Cited on page 4)
Deanna Needell, Rachel Ward, and Nathan Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27: Annual Conference on Neural Informa- tion Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. wwwrinnggn..euss.eeeeeeeeere.. neurips wwtpccpppppp/eeeec //has// html. (Cited on page 5)
1017-1025, 2014. URL 22222144811199441111113132228822
Yurii Nesterov. Lectures Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3319915770. (Cited on pages 6, 8, and 19)
Dinh C. Nguyen, Quoc- Viet Pham, Pubudu N. Pathirana, Ming Ding, Aruna Seneviratne, Zihuai Lin, Octavia A. Dobre, and Won-Joo Hwang. Federated learning for smart healthcare: survey. arXiv preprint 2 1. 108884, abs/21 1. 188834, 2021. URL https: http///rxvvvv///// .rgg abs /aaa///a11111 21111 08834. (Cited on page 1)
Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takác. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Doina Precup and Yee Whye Teh (eds.).
13

---

Published as a conference paper at ICLR 2023
Proceedings of the 34th International Conference Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 Proceedings of Machine Learning Research, pp. 2613- 2621. PMLR, 2017. URL http::/ppocceee//e httppi/s................eemmeeee wwwppppsssss/sp httpss////o//nuuen1n11 nguyen1 html.. (Cited on page 6)
mlr.
Phuong Ha Nguyen, Lam Nguyen, and Marten van Dijk. Tight dimension independent lower bound the expected convergence rate for diminishing step sizes in SGD, In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- neurips cc //pppp///19///l///e Paper--appp...ee pdf. (Cited on page 5)
ciates, Inc., 2019. URL httpp::
Andrei Pätraşcu and Ion Necoara. Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization. arXiv preprint arXiv:1706.0000 00097, abs/1706.06297, 2017.
URL https: /tttpps://aiiiii /ttp/a/iiii/./////////ee/eaeeee/ org/ /bw////////0 1000 06297. (Cited on pages 4 and 22)
Ernest K. Ryu and Stephen Boyd. Stochastic proximal iteration: A non-asymptotic improvement upon stochastic gradient descent, 2014. URL https::/sttaffrrrrrrrr// www.ordddddd//oaeeeeeeeeeee www.dbbpppddp..aa/oo..e pdf/spp pdf. (Cited on pages and 22)
Felix Sattler, Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model- agnostic distributed multitask optimization under privacy constraints. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-13, 2020. doi: 10.1 10.1109/TNLS.2000 200.......000000155555 (Cited on page 17)
Mark Schmidt, Nicolas Le Roux, and Francis R. Bach. Convergence rates of inexact proximal- gradient methods for convex optimization. In John Shawe- Shawe-Taylor, Richard S. Zemel, Peter L.. Bartlett, Fernando C. N. Pereira, and Kilian Q. Weinberger (eds.), Advances in Neural Infor- mation Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, Granada, Spain, pp. 1466, 2011. URL https: http:s::/pocceeeeneee newripe cc/ wwtppppppp/pppe//ppccccecccee.at /2011/2011111 1001/hahhhh S
html. (Cited on page 29)
Othmane Sebbouh, Nidham Gazagnadou, Samy Jelassi, Francis R. Bach, and Robert M. Gower. Towards closing the gap between the theory and practice of SVRG. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bur Auché-Buc, Emily B. Fox, and Roman Garnett (eds.). Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 20/9, Vancouver, BC, Canada, pp. 646 656,,6662200 2019, URL http::tppsssooc /ptocced//e/eee/ppeeeeeooo inpeeiiinnggs... ings neurieiripp. ps cC http//ape///eee huper/200 /tter//019/ 9 Abstract
-tt.r//ccec..ca...ooaaeeaaaaaat. html. (Cited on page 7)
Osama Shahid, Seyedamin Pouriyeh, Reza M. Parizi, Quan Z. Sheng, Gautam Srivastava, and Liang Zhao. Communication efficiency in federated learning: Achievements and challenges. arXiv preprint arXiv:2107.1 10996, 0iss21077.1996. 2021. URL https: /ttttp::/aaxv..or//// orgp//////////////// 10996. (Cited on page 2)
Ohad Shamir, Nathan Srebro, and Tong Zhang. Communication-efficceee distributed optimization using approximate newton-type method. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pp. 1000-1008. JMLR.org 2014. URL http:/ http://proccedding mlr. wttppp/ssss/s/pppppppppp....stst shamir 14, html. (Cited on pages 2, 3, and 17)
Alex Shtoff. Efficient implementation of incremental proximal-point methods. arXiv preprint arXiv:2205.0144 abs/2205.01457, 2022. URL httpt:t/aa.i....oooom http:///r///bb/......./0 (Cited on page 4)
Ying Sun, Gesualdo Scutari, and Amir Daneshmand. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. SIAM Journal Optimization, 32(2):354-385 2022. doi: 10.1137/19M1259973. URL https: 9M1 259973. (Cited pages and 3)
14

---

Published as a conference paper at ICLR 2023
Rafat Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. In International Conference on Learning Representations (ICLR), 2022. URL
hwtpeeiwwwwwweeeeeeeeeeeeeeeeeee htt.://oummmmmmmeee Ltt.r/rrnnnnn----55522222 (Cited on
page 4)
Ye Tian, Gesualdo Scutari, Tianyu Cao, and Alexander V. Gasnikov. Acceleration in distributed optimization under similarity. In Gustau Camps-Valls Francisco R. Ruiz, and Isabel Valera (eds.), International Conference on Artificial Intelligence and Statisties, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pp. 5721- 5756. PMLR. 2022. URL https: http:////occeeennss/// .mmianngssmmm......mmmmmmmmmmm.m www.:.ppess//eco.eo pppess/v1l//tiann//. html. (Cited on pages 3, 7, and 8)
Panos Toulis, Thibaut Horel, and Edoardo M. Airoldi. The proximal Robbins-Monro method. arXiv preprint arXiv: 15 10.00967, abs//511000005 2015. URL http::pss//aaxxi..gg//eeee 00967. (Cited on page 22)
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Aguera y Arcas, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, Suhas Diggavi, Hubert Eichner, Advait Gadhikar, Zachary Garrett, Antonious M. Girgis, Filip Hanzely, Andrew Hard, Chaoyang He, Samuel Horvath, Zhouyuan Huo, Alex Ingerman, Martin Jaggi, Tara Javidi, Peter Kairouz, Satyen Kale, Sai Pranceth Karimireddy, Jakub Konecny, Sanmi Koyejo, Tian Li, Luyang Liu, Mehryar Mohri, Hang Qi, Sashank J. Reddi, Peter Richtarík, Karan Singhal, Virginia Smith, Mahdi Soltanolkotabi, Weikang Song, Ananda Theertha Suresh, Sebastian U. Stich, Ameet Talwalkar, Hongyi Wang, Blake Woodworth, Shanshan Wu, Felix X. Yu, Honglin Yuan, Manzil Zaheer, Mi Zhang, Tong Zhang, Chunxiang Zheng, Chen Zhu, and Wennan Zhu. A field guide to federated optimization. arXiv preprint arXiv:2107.06%0 https: / arxiv. org/ abs watps/217..00 06917.
020/2107.06911 2021. URL
(Cited on page
Blake E Woodworth and Nathan Srebro. An even more optimal stochastic op- timization algorithm: Minibatching and interpolation learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 7333-7345. Curran Asso- ciates, Inc., 2021. URL htttpss:/prooeeedii
neurips.. cc/ pappr/2021/Eillle Paparr-ppr.... paffrr.pff... (Cited on page 6)
Blake E. Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objec- tives. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 3639-3647, 2016. URL. https: http///occeeddig/c/cc neurips cc/ cc/paper r /00 6/ hash/ 645098b08 99 1ee22
htmml (Cited on pages and 6)
Blake E. Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Mikhail Belkin and Samory Kpotufe (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 4386-4437. PMLR, 2021. URL http:// http:://prooeeee proceedingg mlr. w.a..press/vie wttpssss/v11///woorrtttt http///wwwwwwhhhhec. html. (Cited on page 1)
Xiao-Tong Yuan and Ping Li. On convergence of distributed approximate newton methods: Glob- alization, sharper bounds and beyond. arXiv preprint arXiv: 02246, http/190.0222444 2019. URL https:ttp...c.....tt
/tte://arxia aiviiiiiii org/ abs/ / 1908.0.0 0224 6. (Cited on page 3)
Xiao-Tong Yuan and Ping Li. On convergence of FedProx: Local dissimilarity invariant bounds,
non-smoothness and beyond. arXiv preprint arXiv:2206.055 25802 abs/2206.05187, 2022. URL
https://arXtt org/ abs/2206 05187. (Cited on page
Yuchen Zhang and Xiao Lin. DiSCO: Distributed optimization for self-concordant empirical loss. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 362-370. JMLR.org, 2015. URL htttp://proceedingg mmr.. press/ v wwwngb15..11. html. (Cited pages 3, 7, and 17)
15

---

Published as a conference paper at ICLR 2023
CONTENTS
Introduction
1.1 Contributions
2 Related work
3
Preliminaries
4
Algorithms and theory
4.1 Basics: stochastic proximal point method
4.2 The SVRP algorithm
4.3
Accelerating SVRP via Catalyst
Experiments
6 Conclusion
A Basic Facts and Notation
16
Applications of second-order similarity
17
Algorithm-independent results
18
C.1 Facts about the proximal operator
18
C,2 A lemma for solving recurrences
20
Proofs for SPPM (Algorithm 1)
20
Related work for SPPM
22
F Proofs for SVRP (Algorithm 2)
22
G Proofs for Catalyst+SVRR
25
G.1 Proof of Theorem
27
H Extension to the constrained setting
29
H.l Proofs for the composite setting
30
I Client-Server formulations of the algorithms
35
A BASIC FACTS AND NOTATION
We shall make use of the following facts from linear algebra: for any a, b Rd and any 0,
2 (a, b) = ||a||² + ||b||2 - Ila b11
(7)
|||| (1 <) ||a b1l2 (1+ 1-1) |1b1
(8)
16

---

Published as a conference paper at ICLR 2023
B APPLICATIONS OF SECOND-ORDER SIMILARITY
In this section we give few examples where Assumption holds. These are known in the literature, and we collect them here for motivation.
Relation to smoothness. The standard assumption in analyzing federated optimization algorithms for Problem is smoothness:
Definition 4. (Smoothness) We say that a differentiable function / is L-smooth if for all æ, y E IR we have | fz) f - L - vll.
Note that L-smoothness of each f2, f2...... .......ffa. fM implies Assumption 1 holds with 8 = L, as we have for any z, _
M
V Fm (x) Vf(x) (m -Vfm())) -ffntt--Vv(iil ff(il
M
M (m) vmm(2)) - -/WW)
1
M (m) (y)(1))
1
Σ
< L -
Thus have that, under smoothness, Assumption holds. While typically are interested in the case in which is much smaller than L, the fact that by default we have S means that we do not lose any generality by considering optimization under Assumption 1.
Relation to mean-squared smoothness. that each fm is L-smooth, only that
Observe that the preceding proof we did not actually
M
-
M m=l
This assumption is known seean-s smoothness in the literature, and this proof shows it is also a special case of second-order similarity.
Statistical Learning. Suppose that each function fm corresponds to empirical risk minimization with data drawn according to distribution Dw:
fm((x) = = E E(xx Zm,i),
where e is L-smooth and convex in its first argument and Zm, represents the i-th training point on node m. If all the training points are drawn i.i.d. from the same distribution 2m,i Z for all m E [M] and i E [n], then if the losses are quadratic, Shamir et al. (2014) show that, with high probability,
This can be much smaller than L, especially when the Assumption 1 holds with 8 = Ô Vn
number of data points per node large. Zhang Lin (2015) show that a similar concentration holds for non-quadratic minimization, albeit with extra dependence on the data dimensionality d. Hendrikx et al. (2020) remove the dependence on the data dimensionality for generalized linear models under some additional assumptions.
While clients normally do not ordinarily share the same data distribution D., federated optimization, clustering clients together such that each group of clients has similar data is common strategy (Sattler al., 2020; Ghosh et al., 2020), and as such we can apply algorithms designed for Assumption to clusters of clients with similar data.
Other examples. Karimireddy et al. (2020b) observe that Assumption holds with when using objective perturbation differential privacy mechanism for empirical risk minimization, since objective perturbation relies on adding linear noise that does not affect the differences of gradients. Chayti & Karimireddy (2022) give more examples relevant federated learning.
17

---

Published as a conference paper at ICLR 2023
Hessian formulation.
The way wrote Assumption I in the main text is
1
[m) V (x) (V/m(y) Vf(I)| s 8112 - y/1².
M
For twice-differentiable objectives, this is biproduct of the following inequality on the Hessians: for all x E R we have
M fm())
Σ m=1
S 82.
M
This motivates the name second-order similarity. To see why this the case, observe that by Taylor's theorem (Duistermaat, 2004, Theorem 2.8.3), Jensen's inequality and the convexity of the squared norm, we have
Vm Vf(x)) (mm v
2 (0x + 0)y) - 505(0r 0]w]] (o y)d0
/ V (1 0)n) f20(0x + 0)w)] (x w))l²00
$ vm (xx (1- vZ f(Or f)y)l 11 || v112
Averaging with respect to gives
VV (c)
-V V
M m=1
M
2 fm (1- -25 + (1 (7--0y0 -0)y))1 1> - =1
M
m=1
8² [x yl
82 æ y11?.
Therefore if it holds that max M| suP,ER= V
vf(=) S (a condition known as
Hessian similarity), necessarily have that Assumption also holds.
C ALGORITHN-INDEPEDDENN RESULTS
This section collects all facts and propositions that are
C.1 FACTS ABOUT THE PROXIMAL OPERATOR
In this section derive two useful facts about the proximal operator. Both facts are relatively straightforward to derive.
Fact 1. Let h Rdd + R be convex differentiable funciioo and > be a stepsize. Then for all Rdd
prox (ar v)())))
Proof. Solving the proximal is equivalent to
1 || - =11²)
prox (r)
argmin yERd
h(y) +
2n
18

---

Published as a conference paper at ICLR 2023
This is strongly convex minimization problem for any 7 0, hence the (necessarily unique) minimizer of this problem satisfies the first order optimality condition
1 =) 0.
Vh(v) + "j
Now observe that we have
Vh(x) + (x - (xr + v)((a)) = Vh(x) + V/)((( = 0.
7
follows that x = prox p (I
+ V)(()))
Fact 2. (Tight contractivity of the proximal operator). If h is p-strongly convex and differentiable, then for all > and for any 2. E IRd we have
[|prox (x) prox (v) (1 nu)² | vl1
Proof. This lemma can be seen as a tighter version of (Mishchenko et al., 2022a, Lemma 5) though our proof technique is different. Note that p(x) prox,, (x) satisfies 1/ v/((((())) [p(x) =] or equivalently p(a))
v/Vh(p(z)) Using this we have
llp(x) - p(v)1l = || x)Vh(p(=))] - ly Vh(p(())111
| y] (Vh(p()) - Vh(p(v))]1I
||. 011 v²ll)((p(=) Vh(p(t)) 2n (x - v. -kp(()))-Vh(()))) Vh(p(y)))
(10)
Now note that (x y. Vh(p(z)) Vh(p(u))) (p(x) + +)V((((>>) (p()) +,VV((())))) vh(p(=) -Vp(=)))-V((()))
(p(z) p(v). Vh(p(=) Vh(p(e))) + V\(p((()))) Vh(p(e))
(11)
Combining eqs. (10) and (11) get
llp(x) - -p())l = || vl1 + v2lVVh(p(z)) - Vn(P())) 2n (p(x) - p(v). Vh(p(=)) Vh(p())))
2n((( Vh(p(v))11
= || 31|² 7² Vh(p()))) Vh(p(r)) 2n (p(x) p(v), Vh(p(z)) Vh(p(v)))
(12)
Let () huu) h(v) (V4(v), 0) be the Bregman divergence associated with at u, It is easy to show that
(u-a v, Vh(u)= Vh(v)) = (u, v) (n(u, u). This is a special case of the three-point identity (Chen Teboulle, 1993, Lemma 3.1). Using this with u p(x) and v ply) and plugging back into (12) we get
llp(x) - 2())1 = | 0| v)((((()())) - Vh(p(v))11 - 2n (P)(p((),p())) Dx(p(v), p(x)) Note that because h is strongly convex, have that (n(p(v),p(a)) 2 #llp(v) p(=))1 and (x(p(z), p())) 2 -1p(()) p(=)11 hence
|p(x) - p()) S || =11² 1 Vh(p()) - vh(p())) -
(13)
Strong convexity implies that for any points u,
[Vh(u)) v 2 μي ||u m1|
(Nesterov, 2018, Theorem 2.1.10) for proof. Using this in eq. (13) with p(x) and p(v) yields
[|{(x) - p(u)ll < || v1l )211311((z) r(ui)l 2mplpp(a) - -
Rearranging gives
11+ + 2111] [|x(x)) p(u))12 S || -11
It remains notice that 2 1 + 222 27μ1.
19

---

Published as a conference paper at ICLR 2023
C.2 A LEMMA FOR SOLVING RECURRENCES
Lemma 1. Suppose that we have a sequence of positive values (ra)k=o satisfying, for some 0 > 0 and some >> 0
Tk+1 1 1 0 ITk + cc.
Then the sequence satisfies
K 1
TK S
(1 (1+ ro min
1 [1+ 0
Proof. We start from the recurrence to get
Tk+1 S
1+0 Th
1+0
< 1
C
+
1+0
11+0
1+0
1+0
C
(1 (1+ 1 (1+0)
(1+
Continuing similarly obtain
1 (1+0)k 1+0 Σ (1t))=
rK
(1+0)=
(14)
We can now bound the latter sum two ways, the first note that since 1 + I40 < 1, and hence
we have that
K
K-1
Σ
S
P
(15)
==
j=0
The second way is to use the convergence of the geometric series
Σ
(
K-1
Σ
(1+1)
1+0
1 + 0
(16)
0
J=0
j=
140
Using eqs. (15) and (16) in (14) gives
1 0
TK S
(1 + (1+0) To
min
K,
I+0
K 1
(1 + 0) To -im
T 0'
and this is the lemma's statement.
D PROOFS FOR SPPM (ALGORITHM 1)
Proof of Theorem I. Using eq. (8) and our assumption that the proximal operators are solved to the accuracy b we have
2b+1 prox,fer (Ix) + prox (xx) x, ||
| 2211
1
[ prox, (Ex) 1| + (1 + men proxx (xx) x. ||²
1 + mp
+ mp
b (1 + mnn prox (xx) x. 1
(17)
mp
20

---

Published as a conference paper at ICLR 2023
For the second term in eq. (17) have by Fact 1 that proxx1f,, (x, + 1/V.s (x+)), then using the contraction of the prox (Fact 2) we get
prox,fee. (Ix) 2+
= proxnfee (IR) - proxNfte (z+ + (x.
(1 + nu)a 11= (x+, + V (x.))))
(18)
Expanding out the square we have
|prox (fx) Vn 1
0h v. - -V- (s=))]
(1 + nuna
||:2 x=11 112 + フ V (ex)) 2n (ox Iu, Vfea (zx))
+ nn)²
Denote expectation conditional on my by E& [-]. Taking expectation conditional on we get
Es |prox nsc, (Ix) - Ni |
S
|| x. + 1 Vee (x.))1] - 2n (ar I., Ex [en (xx)))
(1 nu)
1
|| x= + 17 07²02
(1 + nuur
where we used that f (x:))
(f.)) 0 and the definition of of Taking conditional
expectation in eq. (17) and plugging the last line gives
Es || xc.l²]]
+ mp
1 m1
|1 - x.112 + 1²=0²
<
+
(1 m112
Tp
| x.ll + 1²022 + (1 + (1+)
+ 7/44
7/11
Taking unconditional expectation gives
E ||:0+
x. [P]
E | - x..1²)
+ 12000²
+ np)²
TH4
17p2
We then use Lemma to get that at step K have
E
| - 1=] < 1
K
|1:00
x=ll?
+
no?
+
(1 + mu)?
b.
(19)
(mμ)²
This proves the first statement of the theorem. For the second statement, observe that when 7) = (ma)² have (1+mp)²
2nr
and
n
(1 + m2)2 mp))
+ E 3c
(20)
(1
4
Moreover, we have using the inequality 1 - S expl-2x for all x >> O and our choice of K that
K
mp
K
nuK
1
exp
S 4 100
(21)
I+
+ mp
1 1 mp
x.112
Plugging eqs. (20) and (21) into eq. (19) yields
[ - x. Se,
and this is the second statement of the theorem.
21

---

Published as a conference paper at ICLR 2023
E RELATED WORK FOR SPPM
Toulis al. (2015) study SPPM where they assume each stochastic proximal operation has unbiased and bounded error from the proximal operation with respect to the full proximal, i.e. for cq(x) =
pr (x) prox,, (x) we have:
E [eg] 0,
and,
IE |lEE| |2] S 0
(22)
Under this assumption, Toulis et al. (2015) prove that the stochastic proximal point method can achieve a rate that is completely independent of the smoothness constant, and which matches the optimal rate for eq. (2) for (potentially) nonsmooth objectives. Kim et al. (2022) show similar result under the same condition for a momentum variant of SPPM. It not clear how to satisfy (22) in practice: the next example shows that even in the simple setting of quadratic minimization, the iterations are not unbiased.
Example 1. Take fi - ax² f2 2ax², and f = (fi + f2), then for any I E Rd we have for drawn uniformly at random from {1, 21:
(1 + 3(ja)
E prox nse (x)) prox (x:)
# 0.
1 6na + 81pa2 3na-
Thus the errors are not unbiased. Moreover, it can be shown that the variance scales with ||||| and thus can be made very large.
In contrast, the convergence rate given by Theorem 1 does require condition (22), and results in linear convergence for the functions of Example I (as both fi and fz share a minimizer at x = 0). We note that Ryu & Boyd (2014) also study the convergence of SPPM without condition like (22), but their theory does not show convergence to an c-approximate solution even if the stepsize taken proportional to e. Pătraşcu & Necoara (2017) also analyze the convergence of SPPM and present two different cases: if the stepsize is held constant (as in our Theorem 1), then their theory shows only convergence to a neighborhood whose size cannot be made small by varying the stepsize; Alternatively, by using decreasing stepsize they can show O (2) iteration complexity, but then this complexity requires that each fc is smooth. As mentioned previously, Asi & Duchi (2019, Proposition 5.3) show the same O (2) rate without requiring smoothness or a condition like (22), but using exact evaluations of the proximal operator. Theorem gives the same iteration complexity without requiring smoothness or bounded variance, and while allowing for approximate proximal point operator evaluations. Note that the improvement of allowing approximate evaluations & Duchi, 2019) is not very significant, as the approximation has to be very tight. The main way we depart from (Asi & Duchi, 2019) that we use the contractivity of the proximal as the main proof tool, and this extends more easily to the variance-reduced setting of SVRP.
(Asi
F PROOFS FOR SVRP (ALGORITHM 2)
Proof of Theorem 2. Let Jt-1 prox, (rk ngk). Then by eq. (8) and our assumption that ||x - T1+1ll 2 < we have for any a >
|ax+1 - I= || - Æx+1 xx+1 - 22.12
(1 + a 1 || S 11 + (1 +a)l xx1."
< + a 1) b (1 + a - x. 12.12
x²
Plugging in a
1+27a we get
( n//
b (1 + m1)
|
1=112
| 1..
(23)
np
2mp
22

---

Published as a conference paper at ICLR 2023
For the second term in eq. (23), have by Fact I that x, prox,smg (x. + v/ Smo Fmmaaaa (2x)). then using Fact we get
proxpsmy (2t - -ngh) proxnfmy (x+ + 1/V (/n)))()))) (Ixw)) ||?
| x=ll²
(1+ mu)² I1 199k (z,, + (x+)))1)1(
Expanding out the square we have
| xx.1 - (1 nu)² 26 - I. - (9k + V Vm ||1
(1 + 71) ||
x. + 1191 Vm (x=))l 2mj (ax Fz + Vima (x.))
We denote by Ex [-] the expectation conditional on all information up to (and including) the iterate
Ikk then
Es || 1 x.1l7]
S (1 muyzzllzx x.11 + RE [1ge + V Vmm (2r. {11)
(24)
2n (Ix vo, E& [gk- + V.m, (x.))))
where in the last term the expectation went inside the inner product since the expectation is conditioned on knowledge of Tg, and the randomness in m independent of mg. Note that this expectation can be computed as
E& Lok + Sm (2.)) E, V (ww)) Vm, (wx) + V (x.)]
= f f + fzx.))
0 + 0=0,
where we used that since x. minimizes we must have V (xr) O. Plugging this into (24) gives
Ex [| 2.11") (1 m/u)
[1ET x=1l² 11 17 E
|Igu
Ving (us))l
(25)
For the second term, we can add V fx.) term inside (as it a zero) to get
Eg 11gN + Vime (s.))1]]
= E2
|1g0 V (x.) [((x.)11
Ex
[[V((wx) Vmn (wx) + V Vmma (2+) V (((x))1
Es
[IV (um(w)) [Vf(z.) [mm
1
[ (wk) (v) (m. (26)
M
Using Assumption 1 with eq. (26) we have
Ex [1ox + f. (x+))
< M m=1
Vf(ww) - - (V)(=))) V.n (x+)))
< 82 Uik - x.1l²
Hence we can bound (25) as
E [aa+1 Taking conditional expectation in eq. (23) and plugging the estimate of eq. (27) we get
x. 1?
27 < (1 + nun
|| x.11 + 1,2821 1 xx 112]
(27)
Es || - 22.12 s
+ mp
+ (1 + m/1)2 E4
|| - x=.1
np
1 2n1
+ Tpp
1
[Iorae .ra112 + 1725211 x. x013]
+
(28)
np
1 2np
23

---

Published as a conference paper at ICLR 2023
Observe that by design we have
Ex
|| - x. ||] = p-- || 11:41-x10 +
+ p) 1|wx - x.11?
(29)
Let then using eqs. (28) and (29) we have
p
Ex
[| I. 12]
a.Ek || - xxa1²] + ap)BEs ||:2 - xo x=1l") + +x(11 - p) -1|wx - x=a1'
1 + op
| - 1al + 1/²0011ux, -x.11") + a(1 pp) -lUCE - x=.1² + (1 + op)
1 + 1+11
2
b
1 + 20/u
17/4
1 + ap
- -x=11² 1=1 (1 + mu)
3
|| x+ 11? + "/00211u5 - -x.11"
+ ta(1 - p) 1100
b
+ 20ju
(1
1 + op
| x.1l' 11 + a
1 1-p+ 1/000 + ap)
||1 =2.12++ + (1 + mu))
b
1 + 2nj
a(1 + 2114)
(m11²²
1 + mp
1 1-p -- + pno² 1 + nu
(1 + mp))
|
x..1 +a a
1 2.112
b.
(30)
+ 2nju
1 + 2nμ1
(1u1)²
Note that by condition on the stepsize we have n/2 / 2.2 hence
n/8²
1+ mM
1 + m/
1
1
<
<
1
1
1 + 2nj
21 1 20μ1
2
2
Using this in the second term of eq. (30) gives
Eg
|k - xx x== + aE
|| - 2=.13]
I 1 + n//4
+ a (1- (1-p ?)) |100s - xx 12 (1 m/1)3
110 - xx
(1/2)2 b
+ 2n
= 1 + qu
_ ||0x 1ra112 + (1 + nu)s
100k - x. + a
1 + 2np
(n/))2
1+ 1+n np
1 p {
(1 + nu)3
5 max
|| x=.12 + callun - 1
+
b.
[1 + 2014"
2
(n1)²
Define the Lyapunov function V22 = =1|08 be written
x2112= + TH
l x=112 Then the last equation can simply
p
1 + TH
Vv + (1 + m/)3
Es [V++1] < max
1 $
(mz)² b.
1 + 2011""
Taking unconditional expectation gives
+ mp
p
[Vi++ + (1 + mp)3
E [V++a] S max
1 + 2011"
2
(11422
Let min{ p 3). then max
1+nH
1
[/]
11 T, and we get the simple recursion
1+2mj
(1 + mu)3 b.
E [e++ S - T) [Vi+ +
(1/)²
Iterating this for ls steps and using the formula for the sum of the geometric series gives for any k < K,
(1+ m/)3
1-
E [V < (1 - 7)"E [Vo]
b
7) (1 7)
(nz)²
(1 + 3
< - =E
6
(111)²
t=0
(1 + m103 b.
(1 -
(31)
(nu))²
24

---

Published as a conference paper at ICLR 2023
Now note that
E
110k x.a
- [V(]..
(32)
And by initialization we have wi = zo, hence
E [Vo] = |00 F. 1
mp |1w0 - x=11²² 10=1==
7//4
||:00 x=.1²
(33)
Plugging eqs. (32) and (33) into eq. (31) gives for any S K,
[x I= ||] = + 7/ (1- 1| x+|1
(1 + mpn (nu)²²
E
6.
(34)
For the second statement the theorem, observe that by assumption on we can bound the right hand side of eq. (34) as
100e Ix 12] S + n/4 (1 (1-7)f x.I1 E
2
Next, we use that for all x 2 0 we have that
x S exp( -2x) hence we have after iterations SVRP
E
||EK- - x=1l²
1+
T/
exp(- -x.1l
e 2
Thus we run for the following number of iterations
2| 2.11 1 m/1
1
K 2 log 7
(35)
We get that E
| - 2.11²]
S + + f===
Choose 1j = 20 and = 17 L
then eq. (35) reduces to
21|20 x. (1
K 2 2 max
{
2 + +1, log
82
28
c
This gives the second part of the theorem.
G PROOFS FOR CATALYS++SVRP
The convergence rate of Catalyst given by the following proposition:
Proposition 1. (Catalyst convergence rate). Run Catalyst (Algorithm 3) with smoothing parameter
Y for p-sttongly convex function f. Let q = بtر and choose S /q. Assume at each timestep t= 1,,....., T we have that x; from eq. (36) satisfies
def 2 (f(xo) - f(x))) (1-p)+ p)*.
E he(xt) min he(x)
s E
(37)
ZERd
9
Then the iterates generated by Algorithm 3 satisfy
[ff(z)) fzx))) 1 (1 (1-p))*1 p)² (f(xo) f(xx)).
(38)
Proof. This (Lin et al., 2015, Theorem 3.1).
We see that in order to apply Catalyst, we have to solve the problem point iterations of eq. (36) up to the accuracy given by eq. (37). However, the accuracy e depends on the suboptimality gap fæo) (x.), which we do not have access to in general. The next proposition shows that this is not a problem for methods with linear convergence, and we can instead run the method for a fixed number of iterations:
25

---

Published as a conference paper at ICLR 2023
Algorithm 3: Catalyst
Data: Initialization zo, smoothing parameter ",, algorithm A, strong convexity constant μr.
Initialize yo = F0-
and 0gg vg- Initialize = M+7
for / ..,
do
Find 2, using A starting from the initialization 2t-1;
(h((r) def f(x) + 11 - y1 1112)
Tt. R argmin
(36)
ZER2
Update oz (0, 1) as
af (1 az)a + qar.
Compute y/ using an extrapolation step
with B, ar-1 - ac-1) af +a
y/ 2z + Br(x zt-1)
Proposition 2. (Inner method complexity in Catalyst). Consider Algorithm 3 run with smoothing parameter Y ju-strongly convex function f. with - and /q. Suppose that the method A generates iterates (2a)s20 such that
p+4
E
he(2))
min he(a)) < A(1-TA,)) (he(zo)
min he(())
(39)
xERd
#ER*
then the precision 4 from eq. (37) is reached expectation when the number of iterations s of A exceeds TA where
(1112)
2
14(1 - ()0-p)((9 p) ))
25927
TA
log A
1
TAA
Proof. This is (Lin et al., 2015, Proposition 3.2).
Thus applying Catalyst to accelerating SVRP reduces to verifying if the condition in (39) holds for SVRP. The next proposition shows it does.
Proposition 3. Define he as in eq. (36) with 7 + S. 8, and let the objective f Rd -> TR. be finite sum (as in eq. (1)) where each fm is p-strongly convex, Use SVRP (Algorithm 2) as the solver A to minimize hs then the iterates 21, ....... 2. generated p+2
L-smooth, and Assumption holds.
by SVRP with stepsize 1j 282
solution accuracy = O, and communication probability =
satisfy
E he(zs) min (x(x) $ A(1 - 77" (he(20) rend
min be (1x)
ZERd
where
A def La ++g (1 1+ (7 (1
def
and.
min
+
82
6z (1+t))
1
M
Proof. The function h4 (from Algorithm 3) is defined in eq. (36) as
(x)x)) = f(x) + 2 ||æ 1--111
By the finite-sum structure, we can write h2 as
hx()) M m=1
1
Σ
fm((x)
2111 y/ 111
(40)
26

---

Published as a conference paper at ICLR 2023
where each fm is p-strongly convex. For each m E [M]] define m (z) def Note that h is + y-strongly convex. Moreover, by direct computation we have for any 2, E IR" that
= fm(()) + 211 - yn-
he Vho(z)= = ((2- - +z - (111))))))))
fm) Vz(2).
Thus using this combined with Assumption 1 we have
M
1
Whe (x)- Vhe(x) Whem (v)ll)
M
m=1
M
Σ (m) Vf(x) (m - f
M
S 8 x y|1
It follows that problem eq. (40) satisfies the conditions of Theorem 2 the convergence of SVRP, and thus specializing the theorem we get for the iterates 21, ....... by SVRP with stepsize 1) 282 solution accuracy
0, and communication probability p that
E 1|z. - =-1p] s (1+ (μ 7)
(1 -1-r))(100 1=
(41)
28
where r
2 min
(u +1 25 and = arg ge h4 (x). Note that because f T-smooth
and p-strongly convex, we have that he is L + 7-smooth and μ + 7-sronglly convex, hence for any E Rd we have
he(x) - 1,(2²))
11 1 7
x - ==1 =='1
(42)
2
+ ?
he(x) hx(2") -
| 2²112
(43)
Using (42) with 20 and (43) with 2, and combining with (41) we obtain + 7
he(2s) - he(2*) -
2| - 2² 11
2
L + 7
(1+ (1 + 7)
(1 =1= ==1
2
28
L ++ 7
[1 (1 72
(1 7) (he(zo) - -h((2)))
# # 7
28
where 1 min
1
and 2" minimizes h,
17
G.1 PROOF OF THEOREM 3
Proof. The proof of this theorem is straighfrforward combination of Propositions 1, and 3. We
1. set p = nf 0, and shall set 1) and yy later. In Proposition 1, choose p = va Vn/(ut7) the convergence guarantee in eq. (38) is
then 2
32 E [[((x:) - [(x)))
(+1
9
2
32( + 7)
V
1+1
1
(f(2o) - f(xx))
2
32( + 7)
V (1+ (f(20) - f(x.)),
exp
27

---

Published as a conference paper at ICLR 2023
where in the last line used that 1 - I exp(-2). Thus in order to get e-approximate solution the the number of iterations of Catalyst ittor T.Caallyst should be
T Catalyst
2
log
[(xo) f((x)) 32( +7)
iter
/q
1
juth +
(f(10) (xxe) 32( + +
2
log
c
By Proposition 2, for a method A satisfying eq. (39) we need TA inner loop iterations, where TA is defined as
1- (A.(12
2
2592y
Ta
log A
111 p) - pp}
TAA
where TAAA and A are defined as in eq. (39). By Proposition we have that for SVRP with 7 μ S and stepsize =
μtz and communication probability 282
M that eq. (39) holds with
A= L + 1 (7 u)
and,
T min
+
8²
6² 2 (5tt))
2 2M
Thus the number of iterations of SVRP TA is
8²
2
M(1 - 0)3 /9 p)2 ))) )
25927
Ta max
2M (7 (7+1)² + + 2,
log A
T- p
Thus the total number of SVRP iterations is TA x
Catalyyt which is
Iter
282
25927
Titocal Beer
= =2
max
+ 2, 2M
log A
1 - + 1(1 - ()2( p)
(7 + n2)
1
f(xo) - f(xx) 32(14 + +1)
x log
μ
Let collect all the log factors, and use the looser estimate
282
82 (n + n)²
max
+ 2M
< 4 max
M
( 2)²
which holds because y + / S 5 in all cases. Thus we get 6-accurate solution if the total number of iterations is equal to or exceeds
82
Ttootl
8
7+ 1 1
max
M { (7 + 2)2 p)z.
We now have two cases: (a) if $ P
VM, then the choice
7
gives
8
7 3//3/4
(44)
P
Note that under this choice of we have 7 + vTT
I 5, and hence the precondition of
Proposition 3 holds. (b) Otherwise, choosing 7 0 yields
Iitttall = 8.
(45)
Here we have + < by assumption, and hence the precondition of Proposition 3 holds, and our usage of it justified. Thus we reach an e-accurate solution both cases when total number of iterations satisfies
Tttotal 8t max
M. 33/4
V
Finally, remains to notice that the expected number of communication steps (by the same reasoning as in Section 4.2) is E [ttoall
(2 + 3ppM)) 5Ttotal
28

---

Published as a conference paper at ICLR 2023
H EXTENSION TO THE CONSTRAINED SETTING
We consider the constrained problem defined as follows: let R be a convex constraint function with proximal operator (i.e. we can compute proxx(-) easily), then the composite finite-sum minimization problem is
1
min F(x) f(z) R(x) M fm))) R(x)
(46)
ZER
The constrained optimization problem minsec (x) can be reduced to problem (46) by letting R dc be the indicator function on the closed convex set C, and the proximal operator associated with R in this case reduces to the projection on C' (Beck, 2017, Theorem 6.24).
We shall use the following variant of SVRP solve this problem:
Algorithm SVRP for composite optimization
Data: Stepsize 1), initialization Zo, number of steps K, communication probability local solution accuracy
Initialize
for k 0, 2,,,.... K do
Sample my uniformly at random from [M]] Set
The f((w)) V fmm (wx).
Compute b-approximation of the stochastic proximal point operator associated with fmn:
Tk+1 prox +nR (Ia
119k).
(47)
Fk+1
if Ck
Sample ek Bernoulli(p) and update wi+1
Wk
if Cg
The following theorem gives the convergence rate of Algorithm 4:
Theorem 5. (Convergence of SVRP in the composite setting). Suppose that Assumptions and that each f, is p-strongly convex, and let be the minimizer of Problem (46). Suppose that each x&+1 is
b-approximation of the proximal (47). Let T = min
7ij [1+2mp'
Set the parameters of Algorithm 4
as 17 282 b
cr(nu)2 2(1+nu]3. and p M. Then the final iterate IK satisfies E
1
||zX =011²] S
provided that the total number of iterations is larger than Tion
Titer 5 ((M + n² log log !)
We first discuss the computational and communication complexities incurred by Algorithm 4 and then give the proof of Theorem 5 afterwards.
Computational Complexity. Note that this algorithm requires evaluating the proximal operator eq. (47), this equivalent to solving the local optimization problem
(fmaa())
min EER2
+
=x
R(x))
2m
for 2/ IA 79Kk- When each f.,, is p-strongly convex, this is composite convex optimization problem where the smooth part is L 1 --mooohh and + -tsronngly convex, and where the constraint has easy to compute proximal operator. This can be solved by accelerated proximal gradient descent (Schmidt et al., 2011, Proposition 4) to any desired accuracy in
L
1 b
0
7 log
11
+
29

---

Published as a conference paper at ICLR 2023
gradient and R-proximal operator accesses.
Communication complexity. The communication cost of Algorithm exactly the same as that of ordinary SVRP, as the iteration complexity of the method remains exactly the same. Thus, the discussion in Section 4.2 applies here. The communication cost is therefore of order Ô [M + nz communications.
Catalyzed SVRP. Catalyst applies tot-oo-the-box to composite optimization (Lin et al., 2015). provided that we are able to solve the composite problems. Theorem 5 shows, Algorithm can do that. Therefore we can show that Catalyzed SVRP has the communication complexity
δ M + M² / in this setting as well. The proof for this rate is straightforward extension of the proofs Section
H.1 PROOFS FOR THE COMPOSITE SETTING
Fact 3. Let h be convex function (not necessarily differentiable) and 0. Let IR, and suppose that g E 0h(x) (that is. 9 is a subgradient of h at x), then we have
proX (x + 199 = x
Proof. Solving the proximal is equivalent ot
prox yh (2) = arg min yER4
h(y) + 11v =1(
2n
This is strongly convex minimization problem for any 7) 0, hence, by Fermat's optimality condition (Beck, 2017, Theorem 3.63) the (necessarily unique) minimizer of this problem satisfies the first-order optimality condition
0 h(y) + 2 1ly -01²²)
(48)
21
Note that for any two proper convex functions fi. fz on Rd we have that the subdifferential set of their sum 0(1 + (2) is the sum of points in their respective subdifferential sets (Beck, 2017, Theorem 3.36), i.e.
a(1 + (z) = {e + + In E (1) 92
= +00
Thus the optimality condition eq. (48) reduces to
0 E ah(y) + [y - 2]
Now observe that plugging y x and = x + tlg and using the fact that g E Öh(x) have
"19
g + 7
(x (x + ng)) = g
0.
7
It follows that 0 E 0h(x:) + [x (x + ng)] and hence prox,, (x + +gg)= x.
Fact 4. (Tight contractivity of the proximal operator). If is p-strongly convex, then for all nj and for any x. y E TRd we have
Iprox,n (z) - prox nb (v)]
(1 + nu)a | - y11
Proof. This is the nonsmooth generalization of Fact Note that p(x) = prox, (x) satisfies
"19p + [p(x) x] for some Opz E Ōh(p(x)), or equivalently p(x) I -19pr. Using this we have
Ip(a) p(v))1 ||[z 7gppl [y 71ppy]1 2
= ||[x - y] n 19pp - 9pv]ll
|| y|l n² 12plpp Iru 112 2n (x: V. 9px 9py)
(49)
30

---

Published as a conference paper at ICLR 2023
Now note that (xr - y: Upm
gru) = (p(x) + 1pp - (p(()) + 11ppll -0pul-900 Upr - Ipy)
(p(x)) p(y), 9pm grnd + 7 n19gp Ipul
(50)
Combining eqs. (49) and (50) we get
Ip(x)) p(u))l = || - y11 + n7 19ppp Spull 3 2nn 2 (p(x) -pl)), Spz Ipu)
2n12 1,9 1ra
= || - yl 1p11 gryll 2nj (p(x) - ply), 9pz 9pu)
(51)
Let Du v. gv) = h(u) h(v) (ge, a u) be the Bregman divergence associated with u, with subgradient Jo E 8h(v). It is easy to show that
(u - u, Iu - go) Dz v, gn) + Du u, go).
Using this with = p(z), p(y), Iu 9px and gu Iyv and plugging back into (51) get
llp(x) - -())) = || v|l "1² 119p= Iro 1 2n (Dx (p(x)) Mp-) + Dn(p(v), (py))
Note that because h is strongly convex, have by (Beck, 2017, Theorem 5.24 (ii) that Da (p(()))((z)) gya) $ (Ip(y) p(x) and (x(p()), p(V)) p(W), 9pm) #l(p(v) p(x)]l hence
[[((x) - (rw)) - || w n 1211 gool' 112 (nll)((>) p(v)1 Strong convexity implies for any two points u, v and In. E @h(u), go E (v) that
(52)
(g. Iu. u 8) 2 p e11
see (Beck, 2017, Theorem 5.24 (iii) for proof. Using Cauchy-Schwande yields
11. - go ||u vll 2 (g.. go. u - v) 2 u||u - v/|²
Now if u then trivially have 1lgu goll ||ue o/l. otherwise, we divide both sides of the last inequality by I|u - u|| to get
11 - goll 2 1 ||u v/|.
Thus in both cases we get
119u gull2 2 1²111x =11².
Using this in eq. (52) with u = p(z), v = p(v). Iu = Jpz and gv = 9py yields
[|{()) p < || yyl2 1112221pp(x)) r(ui)1 - 2nHulp((=) p(())11
Rearranging gives
[1 [1+ n²p² + +21/4] [lp(x) p(v)11 s || 2
It remains to notice that (1+ 21+) = 1 + 77²11² + 27p..
Proof of Theorem 5. Let Æe+1 = prox proxnfm + - 19 Then by eq. (8) and our assumption
that [| - T4+1ll 2 < b we have for any a >
| 11112 || - Zz+1 Tt+1 - x.112
(1 + a 1) || - .t+1 1| + (1 + a)ll - =2.12
< (1 (1+a-1 + (1 + || 12.1.
Plugging in a
142ma we get
( =1+ n/11 )
(1 + m1)
| 121125 5
b
| 1..
(53)
npp4
27p
31

---

Published as a conference paper at ICLR 2023
Now observe that by first-order optimality of x, we have
E (F..) = Vs(x.) + aR(x.)
It follows that (xx.) E @R(x.). and thus we can apply Fact 3 to get that r., = pfox to v/V Fm (axx) - 17 fzz)) Using this in the second term in eq. (53) followed by Fact 4 we get
[8k+1 - 12112 - = prox n5m (oo - -gg))= - nf (x. + V/ V. (x..) - (V]())))
(1 + mu)a I
199k (a+ + 17 1 (x+) [V
Expanding out the square we have
[ x=11 -
11 - xx (9k + V Vmmm V (xx
(1 + mu)
|108 xx.1 + 1199 + Vime (Ix) v (x,))|
(1 + mu)²
22 (ax Te 9 + V fix (I.) ((0))-((().)) v((x)))
We denote by Ex [-] the expectation conditional on information up to (and including) the iterate
Ike then
|8
J. 1=1]"]] S (1 nnia 11 =2.1l + 2 [1.9k + V V.nn (x.) [[(x)))) )13]
2n (x Jin E& l9 + Vina (x:.) - vf(x,)
(54)
where in the last term the expectation went inside the inner product since the expectation is conditioned on knowledge of Ik, and the randomness in m is independent of øg. Note that this expectation can be computed as
Ex [gk + fmme (I+) v((())) = E& [ (wwx) - Sm (wx) + fm (x.) fx())) V vf((w) + Vf(zz) -f(aa)
= 0=0=0
Plugging this into (54) gives
Es |x+1 1p] (1+ nu)a
|1 2=11? + E 11gx + - (55)
For the second term, we have
Ex [19h + Vimu - [x(x))1
= Ex (((W)) V Sm (wx) + V V (x.) - vf(x,))]
= E2 [Vf(w)) V (wx) [V(xx) V fm (z.)
1
[V(()) (V(()) v Vm (z. [11
M
(56)
Using Assumption with eq. (56) we have
M
Ex [19x + (x=))l))1
M Σ [Vf((w) - (v) -V)(a)) V v. 111
<
< 82 Wik- 1.112
Hence can bound (55)
E2 [ x.a 112 5
[1172 11+
1
x.l12 +7282 1/ 1. 12.1
(57)
(1
muna
32

---

Published as a conference paper at ICLR 2023
Taking conditional expectation in eq. (53) and plugging the estimate of eq. (57) in get
Ex ||:0011 2-113 z
1 + Tp
+
(1 + m/))
| x=1l²]
tpp
1 20T
1 + Tp
[1ITA= - x.11² + 1/201 x. xx.1²]]
b+ +
(58)
Tpph
1 20ju
Observe that by design we have
Es
|1 - 12] = = || 1aa1-xx,11 x1 +11 - pD) -1 - x.11?
(59)
Let DM then using eqs. (58) and (59) we have p
Ex
|104111 1=]
+ +aEk [| 2.112) (1 + ap) | - ==1?? +a(1 -p) -1luk -xall
< 1 + ap
|, - xx1 -xx1
+ + - -2,11²
+ +a(1 p) -/20 - x=11 2 + (1 + ap)
1 1 1926
b
+ 27
17p1
1 + ap
a(1 p) | - x=112 22 + (1 + mu)
|| - 12 +
=z+1²] 1/²0²1uux
l
b
+ 2nju
(n
1 + op
1 1-p+ 1/282(1 ap)
| -2.112+ + (1 + n/11 b
| 1=1 + a
1 2np
a(1 21μ)
(111)²
1 + 7p
pno² 1 + qp
(1 +1+ m/1)
|
x=1 1| + a
1 1-p+
| x.11
b.
(60)
+ 2nju
1 + 201
(111)²
Note that by condition on the stepsize we have n182 / 2. hence
1/82
1+ m
1 + n/
1
<
<
1
1
1 + 2nj
21 2nj1
2
2
Using this in the second term of eq. (60) gives
Eg
[ x==
aE
[| -
-2x12==11 zx113)
< 1 + n/
+ a (1 1pp -7))) -2) ||0s - xx 12 (1 + m/)3
||08 - xx
b
+ 2nj4
(n
+ q/
10 - x=1 + a (1- P) |118 x2.12 + + 1/133
=
1 + 2np4
(n
1+ 1+ mp
p
|| x.ll" 112 + aillwx v. |²]
(1 + mu)s
< max
1
+
b.
1 + 2n14"
2
(n))²
Define the Lyapunov function Vi2 = || be written
x2.12+
TH p
l x.1la Then the last equation can simply
1 + nH
p } f
Vv + (1 + mp)3
Ex [V++]] < max
(m1)² b.
1 + 21j
Taking unconditional expectation gives
+ mp
p
[Vo] + (1 + mp)3
E [V++]] < max
1 + 2011""
2
(1/22²
Let min p 3). then max
14:p/1 I+2mj
1
T, and we get the simple recursion
(1 + 7u)3 b. (1
E [V++1] S - F Vi] +
33

---

Published as a conference paper at ICLR 2023
Iterating this for ls steps and using the formula for the sum of the geometric series gives for any $ K,
(1+ mp))
1-1
E [V - (1-+)*
[Vo]+
7)
(na)²
(1 + mp))
s E->))
6
> 7) t=
(1/1a)²
(1 m/13
7) E [Vo]
(61)
(174)2TT
Now note that
|| - 1=.1 E
S E [Vx)-
(62)
And by initialization we have wi Zg, hence
E Vol | xx
Ilw0
x=11²=
1+ 7/44
|1:0 -x=11
(63)
Plugging eqs. (62) and (63) into eq. (61) gives for any K
E
I 111 [2]
1+
(1-))) x.
T p
(1 + mp) (17
b.
(64)
For the second statement of the theorem, observe that by assumption we can bound the right hand side of eq. (64) as
|10 I= 11] $ 1+ np
(1 - (1-7)*1120 x. 2
Next, we use that for all x 2 O we have - x S exp(- x)). hence we have after iterations SVRP that
E
| x.
11 S 1 T/ exp( - rK]] xo x..12 2
Thus if we run for the following number of iterations
2|
F,,12 (1
K 2 7
log
(65)
E
We get that E |xx - 2.112
S +
Choose
25
and I
M.
then eq. (65) reduces to
22| 1. (1
2 aM
(
8 112
28
K > max
+ 1, M log
e
This gives the second part of the theorem.
34

---

Published as a conference paper at ICLR 2023
I CLIENT-SERVER FORMULATIONS OF THE ALGORITHMS
The algorithms we gave (Algorithm and Algorithm 2) are written in notation that does not make clear the exact role of server and client in the process. Below, rewrite the algorithms make clear the role of the clients and the server, in Algorithm 5 and Algorithm 2. Note that both formulations are exactly equivalent, and this is just for clarity. Both algorithms rely on evaluating the proximal operator approximately using local data: we give an example solution method using gradient descent Algorithm By standard convergence results for gradient descent, A Algorithm 7 halts in at most (+ log !) iterations. As discussed in the main text, we can also use accelerated gradient descent or other algorithms, this example just for illustration.
[+
Algorithm 5: Stochastic Proximal Point Method (SPPM) (Client-Server formulation)
Data: Stepsize 1), initialization zu, number of steps K, proximal solution accuracy Server communicates stepsize and desired proximal solution accuracy b to all clients.
for k 0, 1,
do Server samples client m E [M.
Server sends model 25 to client m.
Client m evaluates the local proximal operator up to accuracy b on its local data (e.g. using Algorithm 7):
Tk+1 prox nfmm (xk).
Client m sends the updated model # to the server.
35

---

Published as a conference paper at ICLR 2023
Algorithm Stochastic Variance-Reduced Proximal Point (SVRP) Method (Client-Server
formulation)
Data: Stepsize 7) initialization Zo, number of steps K, communication probability solution accuracy b.
probabbbbl p, local
Initialize Wo Io-
Server communicates stepsize and desired proximal solution accuracy b to all clients.
Server communicates iterate wp to all clients.
Every client computes its local gradient (wo) and sends it back to the server.
Server receives the local gradients and averages them: f((o)) = 3 SM fm
Server sends fl(o)) to all clients.
for & = 0, 2, .., K- 1 do
Server samples client my uniformly at random from [M]. Server sends model 2ą. client my.
Client m& computes its local gradient V fmm. (w)e) with the (cached) model wi and cached
10
full gradient (w(w)) and sets
9h V((w)) Vm (wx)
11 Client mg computes a b-approximation of the proximal point operator on its local data (e.g. using Algorithm 7):
Fb+1 ~ prox,fmm (Ix- - -79g).
12
Client my sends F4+1 to the server. Server samples Cą Bernooull(p)) then
14
if ca
Server notifies clients of update, W Tx+1 and sends it all clients.
16
Every client m caches the new model Wx+11 instead of the old model Wk. then computes its local gradient fm (Wk+1) and sends back the server.
17
Server receives the local gradients and averages them:
ff(w+++))
+ EM
V fm (We+1).
18
Server sends V f(w++1) all clients to cache.
else
20
Clients keep their cached vector wy as it is, setting Wk+1 = wy automatically.
36

---

Published as a conference paper at ICLR 2023
Algorithm Client m approximate proximal point evaluation using gradient descent.
Data: Proximal operator argument proximal solution accuracy b, smoothnes constant L,
strong convexity constant μ..
(This algorithm evaluutes prox,fm. (z) up to accuracy b using gradient descent.)
Set the local stepsize 3 L+I
Set the model yo
for = 0, 1, ........ do
Compute the gradient
1 A vm + -(m z).
11
Update the model
Ur+1 y/: -3.
if the gradient norm is small ||
b | "
1 then
10
Exit and return ys as it is a 6-approximate solution, since by strong convexity we have
||
1 - prox,,i., (z)]] = (1 + ) S b.
37


Reviews:
[{"review_id": "yeDjQpmmJ1", "reviewer": "Reviewer_JTga", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the federated learning optimization problem under the assumption of second-order function similarity. In contrast to the previous work that considers the full client participation model, this work studies the problem under the partial participation/client sampling model. Two communication-efficient algorithms are proposed, namely SVRP and Catalyzed SVRP, which use the stochastic proximal point method as a building block and adapt it via an SVRG-style variance reduction method. \n\nThe authors provide analysis of the stochastic proximal point method without the smoothness assumption. Moreover, the analysis of the algorithms shows the improved communication complexity of the proposed methods as compared to the prior methods. Experiments on real and synthetic data show the improved performance of the proposed methods in terms of communication.", "summary_of_the_review": "Overall, the idea of the paper is sound. However, the experiments could be made more thorough (please see the comments above). My main concern is the amount of computation which seems to be quite high. Even though communication is the bottleneck in FL, the amount of computation at each local client should also not be too high. An empirical evaluation of this aspect would be highly encouraged to demonstrate the practicality of the proposed methods on FL devices.", "strength_and_weaknesses": "* Strengths:\n\n1.\tOverall, the paper is well-written with a clear motivation. \n\n2.\tUsing stochastic proximal point framework to unify the analysis is interesting.\n\n3.\tThe authors provide an elegant combination of prior techniques used in the federated learning literature including client sampling, variance reduction, and stochastic proximal point method.\n\n* Major concerns:\n\n1.\t(Computational cost) The analysis shows that under the partial participation setting, the proposed methods improve communication complexity. However, this gain is achieved at the expense of additional computation on the local clients. Even though the experiments demonstrate superior performance in terms of communication, no experiments are provided to compare the computation trade-off. It would be interesting to evaluate this trade-off empirically. \n\n2.\t(Small-scale experiments) Moreover, the experiments are provided on relatively simpler learning problems. It would be interesting to evaluate the methods on more complex federated learning problems, e.g. using logistic regression on image data, or training a neural network, as done by the authors of SCAFFOLD (Karimireddy et al., 2022)\n\n3.\t(Limited novelty) Since distributed optimization has already been studied under assumption 1 in the full participation setting, improving the existing algorithms under the partial participation setting seems rather limited in terms of novelty.\n\n* Minor concerns:\n \n1)\tTypo: In the paragraph above section 1.1, the phrase “methods exist for” is redundant\n\n2)\tMissing word: In the third last paragraph of section 2, the sentence “Rye & Boyd (2014) convergence rates…” should instead be something like “Rye & Boyd (2014) provide convergence rates…”\n\n3)\tFigure 1: I found the font size to be very small. For better visibility, I would recommend turning the grid on and increasing the font size of the axis labels, and legends.\n\n4)\tMissing word: In the beginning of section 5, the sentence “We linear regression with…” should instead be something like “We run linear regression with…”.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nkezh_GDz4", "reviewer": "Reviewer_2cGY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies federated optimization under strong convexity and second-order similarity assumptions. Using the idea of trading off local computational cost for less communication, the paper proposes a new algorithm SVRP based on proximal point methods and variance reduction (SVRG). With client sampling, SVRP can achieve better communication cost compared to the state-of-the-art when the second-order similarity constant is small enough. Moreover, the catalyst acceleration of SVRP is also studied when assuming the exact proximal oracle. It attains strictly better complexity than all existing works.", "summary_of_the_review": "The paper provides strictly better complexity for strongly-convex federated optimization under second-order similarity, with a novel algorithm SVRP and its catalyst acceleration. I am happy to increase the score based on the discussions.", "strength_and_weaknesses": "**Strength:**\n\nThe paper achieves better communication cost than related works for strongly-convex finite-sum federated optimization under second-order similarity, showing the benefit of client sampling and the trade-offs between local computation and global communication. The novel method that incorporates SVRG into the proximal point framework can also provide new algorithmic insights. Although the use of proximal point algorithms in federated optimization and the ability of catalyst framework to accelerate convex optimization is well-known in the literature, it is still interesting to see the improved rates in this work combining all the techniques.\n\n**Weakness:**\n\n1. It is not immediately clear whether the analyses can be extended to other settings, e.g. the constrained case because it is explicitly used that $\\nabla f(x^*)=0$ in all the proofs. However, the original PPM (and also SGD) works for strongly-convex, convex, and nonconvex settings in both constrained and unconstrained regimes. The proposed algorithms also require extra memory for $g_k$.\n\n2. As mentioned in the paper, the current catalyzed SVRP requires the exact proximal oracle, and it is not clear how to satisfy eq. (41) with the inexact proximal update. The double-looped (actually tripple-loop if considering local steps) catalyzed SVRP can be complicated to implement in practice. Will it be possible to directly accelerate SVRP to design a simpler algorithm?\n\n3. It will be good to include the server and clients in the algorithms for a better understanding since some steps are only for clients and some are for the server. For the communication complexity, it should also take into account that the server needs to first communicate the stepsize $\\eta$ and accuracy $b$ to all the clients even though it does not affect the final complexity.\n\n4. More details about the experiments can be provided in the appendix, e.g. values for the stepsizes. What is the behavior if one tunes the stepsize for each algorithm instead of setting it to the optimal theoretical suggestion?\n\n5. No experiments of catalyzed SVRP are provided. In the case that $\\delta/\\mu \\leq\\sqrt{M}$, SVRP is enough and the catalyst will not bring any benefit (is there a typo in the comment after Theorem 3 stating that Catalyzed SVRP is strictly better than SVRP when $\\delta/\\mu\\leq\\sqrt{M}$), and all experiments fall into this regime. It might be good to verify the behavior of catalyzed SVRP as well when $\\delta$ is large.\n\n6. Minor: The emphasis that SPPM does not require smoothness in the abstract can be misleading and not precise. Smoothness is required to solve the proximal operator efficiently when its closed form is unknown; It is better to include the example of differentially private optimization in the main text because it is also emphasized in the abstract; It is mentioned in the related work that Kovalev et al. (2022) remove logarithmic factors but it is still $\\tilde O$ in the table; The symbol $\\mathcal{M}$ in the catalyst might cause some confusion with $M$ for the number of clients; What is the relationship between second-order similarity and other smoothness conditions used in variance reduction, e.g. average smoothness and individual smoothness, and what are the benefits of introducing it?\n\n7. Typos: \"several methods exist for solving Problem (1)\"; \"SVRP trades off a higher lower computational complexity\"; \"Ryu & Boyd (2014) convergence rates\"; $\\eta=\\mu\\epsilon/(2\\sigma^2)$? after Algorithm 1; Theorem 2: \"and and that each $x_{k+1}$\"; \"We linear regression\"; duplication in eq (17); Proposition 3 and proof of Theorem 3: should be $1/(\\cdots+2)$ in $\\tau$. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bRk9f3nvNAN", "reviewer": "Reviewer_sQ1q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors propose a new federated learning optimization based on variance reduced proximal point algorithm. Furthermore, a theoretical superiority of the proposed algorithm is derived. Preliminary experiments also demonstrate the effectiveness of the proposed algorithm. ", "summary_of_the_review": "see the comments above.", "strength_and_weaknesses": "The authors propose a new federated learning algorithm under the second-order similarity condition. Solid theoretical findings show the superiority of the proposed algorithm. However, before this work is accepted, several concerns should be resolved:  \n(i)\tMore discussion should be given on the second-order similarity. There exist several similarity conditions in analyzing the federated learning algorithms. Can the authors provide their relationships of the existing similarity conditions? In addition, do the results derived in this work still hold when assumption 1 is replaced by other similarity conditions? If not, can the authors provide several explanations?\n(ii)\tExisting experiments are too simple to demonstrate the practical effectiveness of the proposed approach. More comparisons with SOTA baselines such as FedSAM, FedDyn, FedCM, FedPD, and FedDR, should be included. \n(iii)\tIn addition, the efficacy of SPPM and Catalyzed SVRP should be verified. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "bND-p25Yjl9", "reviewer": "Reviewer_Q8H3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studied the finite-sum federated optimization under a second-order function similarity condition and strong convexity, and proposed two new SVRP and Catalyzed SVRP algorithms based on approximate stochastic proximal point evaluations, client sampling, and variance reduction. It provided the convergence analysis of the proposed algorithms, and  prove that the proposed Catalyzed-SVRP algorithm has a lower communication complexity  than the existing methods. Some experimental results demonstrate the efficiency of the proposed algorithms. ", "summary_of_the_review": "This paper studied the finite-sum federated optimization under a second-order function similarity condition \nand strong convexity, and proposed two new SVRP and Catalyzed SVRP algorithms \nbased on approximate stochastic proximal point evaluations, client sampling, and\nvariance reduction. It provided the convergence analysis of the proposed algorithms, and \nprove that the proposed Catalyzed-SVRP algorithm has a lower communication complexity \nthan the existing methods. Some experimental results domenstrate the efficiency of the proposed algorithms. \n\nSome Comments:\n\n1. It would be great if the authors would detail the second-order function similarity condition. \n\n2. It would be great if the authors would detail the reason of reducing the communication complexity in \nthe proposed methods.  \n\n3. There will be a strict upper limit of 9 pages for the main text of the submission, \nwith unlimited additional pages for citations (https://iclr.cc/Conferences/2023/CallForPapers). \nThis paper maybe not fit for this request.\n\n\n\n--------------------------------------------------------------------------------------------------------------------------------------\n--------------------------------------------------------------------------------------------------------------------------------------\nThe authors still did not solve my main concern- the limited novelty of this paper. So I keep my score.\n", "strength_and_weaknesses": "Strength:\n\nThis paper proposed two new SVRP and Catalyzed SVRP algorithms based on approximate stochastic proximal point evaluations, client sampling, and variance reduction. It provided the convergence analysis of the proposed algorithms, and \nprove that the proposed Catalyzed-SVRP algorithm has a lower communication complexity  than the existing methods.\n\nWeakness:\n\nThe novelty of this paper is limited. This paper basically combines the existing approximate stochastic proximal point evaluations, client sampling, and variance reduction. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ol0PX9X90j", "reviewer": "Reviewer_gy4c", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies Federated stochastic optimization with client sampling. Under the assumption of second-order similarity condition, the authors propose a variance-reduction based proximal point algorithm which enjoy a better convergence rate wrt the number of clients. They also proposed an accelerated version which enjoys an even tighter rate wrt to the condition number. \n\n", "summary_of_the_review": "This paper is in general easy to read, and the improvement seems significant under the corresponding assumptions. However, I have some questions/concerns, which are listed above. ", "strength_and_weaknesses": "This paper is in general easy to read and the improvement seems significant under the corresponding assumptions. However, I have the following concerns:\n\n1.\tI am slightly confused about the setting: in federated learning, one important thing is protecting the privacy of the local learners, and this is the reason why the local learner only submits their model instead of their data. However, in this paper, if my understanding if correct, the sever need to compute the full gradient. Thus, does this mean all local clints have to submit their data? If the sever has access to all gradients, and the computational complexity of gradient computation is low, we do we still need the local clients? I think I may have some misunderstandings on this paper, and I hope the authors can help me understand this point.\n\n2.\tThe experiments are not sufficient (for a stochastic optimization/federated learning paper). It is only conducted on one very simple data set. More experiments should be conducted to demonstrate the effectiveness of the proposed algorithms. \n\n3.\tThe section on Catalyst is not well-developed: It seems that the Catalyst algorithm is just being plugged-in and it is hard to tell where the novelty is. Moreover, can the authors be clearer about how Algorithm 3 works in a sever-client setting?\n\n4.\tFor assumption 1, I do not see why this inequality holds for the settings the authors mentioned. Can the authors elaborate on 1 or 2 examples?\n\n\nA small question: In experiments, how do we compute x^*?\n\nSome minor issues:\nPage 2: ” several methods exist for methods exist for solving Problem”\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster