FedDA: Faster Framework of Local Adaptive Gradient Methods via Restarted Dual Averaging
Authors: Junyi Li
Feihu Huang
Heng Huang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Federated learning (FL) is an emerging learning paradigm to tackle massively distributed data. In Federated Learning, a set of clients jointly perform a machine learning task under the coordination of a server. The FedAvg algorithm is one of the most widely used methods to solve Federated Learning problems. In FedAvg, the learning rate is a constant rather than changing adaptively. The adaptive gradient methods show superior performance over the constant learning rate schedule; however, there is still no general framework to incorporate adaptive gradient methods into the federated setting. In this paper, we propose \textbf{FedDA}, a novel framework for local adaptive gradient methods. The framework adopts a restarted dual averaging technique and is flexible with various gradient estimation methods and adaptive learning rate formulations. In particular, we analyze \textbf{FedDA-MVR}, an instantiation of our framework, and show that it achieves gradient complexity $\tilde{O}(\epsilon^{-1.5})$ and communication complexity $\tilde{O}(\epsilon^{-1})$ for finding a stationary point $\epsilon$. This matches the best known rate for first-order FL algorithms and \textbf{FedDA-MVR} is the first adaptive FL algorithm that achieves this rate. We also perform extensive numerical experiments to verify the efficacy of our method.

Under review as a conference paper at ICLR 2023
FASTER FRAMEWORK OF LOCAL ADAPTIVE GRADIENT METHODS VIA RESTARTED DUAL AVERAG- ING
FEDDA:
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) is an emerging learning paradigm tackle massively distributed data. In Federated Learning, set of clients jointly perform machine learning task under the coordination of a server. The FedAvg algorithm one of the most widely used methods to solve Federated Learning problems. In FedAvg, the learning rate is a constant rather than changing adaptively. The adaptive gradient methods show superior performance over the constant learning rate schedule; however, there is still no general framework to incorporate adaptive gradient methods into the federated setting. In this paper, we propose FedDA, novel framework for local adaptive gradient methods. The framework adopts a restarted dual averaging technique and is flexible with various gradient estimation methods and adaptive learning rate formulations. In particular, we analyze FedDA-MVR, instantiation of our framework, and show that it achieves gradient complexity (c-115) and communication complexity Ó(c-1) for finding stationary point This matches the best known rate for first-order FL algorithms and FedDA-MVR is the first adaptive FL algorithm that achieves this rate. We also perform extensive numerical experiments to verify the efficacy of our method.
INTRODUCTION
Federated Learning denotes the process in which set of distributed located clients jointly perform a machine learning task under the coordination of a central server over their privately-held data. A widely used method in FL. is the by its name, FedAvg performs (stochastic) gradient descent steps on each client and averages local states periodically. This method can be shown to converge Stich (2018) Haddadpour & Mahdavi (2019); Woodworth et al. (2020) when the distributions of the chients are homogeneous or with bounded heterogeneity. Recently, large amount of literature has focused accelerating FedAvg. In particular, many research works use momentum-baan basse methods to accelerate FL,, and significant progress has been made in this direction with improved gradient complexity and communication complexity Das et al. (2020); Karimireddy et al. 90); Khanduri et al. (2011)). However, another important category methods: adaptive gradient methods have received much less attention, and there is still no general framework to incorporate adaptive gradient methods into the federated setting.
McMahan et al. (2017) algorithm. As indicated
Adaptive gradient methods such as Adagrad Duchi al. (20TT) Adam Kingma & Ba (2014) and AMSGrad Reddi et al. (2018) are widely used in the non-distributed setting. The gradient descent method uses either fixed learning rate or fixed learning rate schedule, In contrast, adaptive gradient methods set the learning rate to be inversely proportional to the magnitude of the gradient; this can incorporate the local curvature structure of the problem. Adaptive gradient methods perform well in practice; meanwhile, they also enjoy useful theoretical implications that make them outperform the vanilla gradient descent method Duchi et al. (2011): Guo et al. (202I). For example, a recent study Staib al. (2019) showed that adaptive gradients help escape saddle points. Furthermore, some studies Loshchilov & Hutter (2018); Chen et al. (2018a) showed that adaptive gradients improve the generalization performance of the model.
Adaptive gradient methods can be viewed as a type of generalized mirror descent Huang et al. (2021) methods, where the associated mirror map is defined according to adaptive learning rates. However,

---

Under review as a conference paper at ICLR 2023
Table 1: Comparisons of representative Federated Learning algorithms for finding an e-stationary point of Objective equation D i.ee [V]())] S E or its equivalent variants. Go(fe e) denotes the number of gradient queries w.r.t. ((k)))) for à E [K]; Ce(f. e) denotes the number of communication rounds; State means what state the algorithm maintains locally (Primal/Dual); Local-Adaptive means whether the algorithm performs adaptive gradient descent locally or not: Constrained means whether the algorithm can solve both constrained and unconstrained problems or not. The first three algorithms are not adaptive gradient methods, and the last four methods support some form of adaptive gradients.
Algorithm
Gdl.c)
Cclf.c)
State
Local-Adaptive
Constrained
FedAvg McMahan et al.
2017
Oie
Primal/Dual
X
K
FedCM Khanduri et al.
2021a
Primal/Dual
x
x
STEM Khanduri et al.
2021a
((r-1.)
Primal/Dual
x
x
FedAdam Reddi et al. 2020
2
2
Primal
x
x
Local-AMSSGral(hen et al. (020bb
O O
Primal
/
x
MIMF-MVR Karimireddy et al. 2020a
O
Primal
/
x
FedDA-MMVK(Ous))
Ole
Dual
the mirror map is dynamic and changes at every training step. As a special case, the gradient descent method can be viewed as a mirror descent method with the mirror map being the L2 distance function. Following the convention in the mirror descent literature, we denote the parameter space as the primal space and the gradient space as the dual space. The primal and dual space differ in adaptive gradient methods, but they coincide in the gradient descent method. We can exploit this primal-dual view to understand existing FL algorithms and design new algorithms. FedAvg actually exploits the usefulness of average dual states. In FedAvg, the gradient average approximates the true gradient evaluated at an average point of the client states, and the approximation error is upper-bounded by the client states difference; therefore, clients can perform multiple local steps without communication. Although in FedAvg, we do not differentiate the primal and dual space as they are the same, but the dual state average and primal state average are not equivalent for adaptive gradient methods.
Current federated adaptive gradient methods in the literature either only perform adaptive gradient steps on the server side, or ignore this primal-dual nuance when supporting local adaptive gradient steps. An early work is Reddi et al. (2020), the authors proposed applying adaptive gradients in the server-average step, while performing normal gradient descent updates locally. This method is simple to implement and gets better performance than FedAvg, but the adaptive information is not exploited during local updates; this weakens the usage of adaptive gradients. Recently, some work KKarmireddy al. (2020a): Chen et al. (2020b) exploited adaptive information during local update steps; however, a common characteristic of these methods is that they average the primal states (parameters) of the problem during the synchronization step. This will cause some problems. Firstly, since adaptive learning rates define the mirror map, updating adaptive learning rates locally makes the dual space not aligned, thus we not average the primal states directly. Then even if the adaptive learning rates are fixed locally, the primal space might be nonlinear w.r.f. the dual space, e.g., when we solve a constrained optimization problem. In summary, we propose two principles to apply adaptive gradients in FL. First, the local dual spaces should be aligned with each other, Second, we should average dual states.
More specifically, we propose the FL adaptive gradients framework FedDA, which is short for Federated Dual-averaging Slaptive-gradient In each global round of FedDA, the clients aggregate gradients (dual states) locally, and the server averages the dual states of the clients in the synchroniza- tion step. Local weights (primal states) are used as gradient query points in local updates and are recovered through the inverse mirror map (defined by the adaptive gradients). The global primal state is updated on the basis of the averaged dual states and the inverse mirror map. In addition, we utilize restarting technique to make sure that all clients share the same dual space during local updates; more precisely, we refresh the adaptive gradients at every global epoch and use a fixed one in the local update. Our FedDA framework is general and can incorporate a large family of adaptive gradient methods to the FL setting. In particular, FedDA-MVR, an instantiation of our framework, achieves the best-known gradient complexity and communication complexity in the FL setting. Finally, we highlight our contribution as follows:
2

---

Under review as a conference paper at ICLR 2023
(i) We propose FedDA, framework for federated adaptive gradient methods. The framework uses a restarted dual averaging technique and adapts a large family of adaptive gradient methods to the FL setting;
(ii) FedDA-MVR, an instantiation of our framework, obtains the gradient complexity of (5- and communication complexity of Ó(c-)). This matches the optimal rate of non-adaptive federated algorithms and outperforms existing adaptive federated algorithms. FedDA-MVR uses the momentum-bant -basdd variance-reduction gradient estimation, and expo- nential moving average of the gradient square as adaptive learning rates;
(iii) We empirically verify the efficacy of the framework FedDA by performing a colorrectal cancer prediction task and a classification task over the CIFARIO and FEMNIST datasets.
Notations. (z) (V (( (x)) denotes the first-order derivatives of the function f(x) (f(() w.E.t variable x. & denotes a random sample and (ar; f( {)) is the stochastic estimate V (x) (x)) (()) is the big O notation, and (c)) hides logarithmic terms. La denotes d-dimensional identity matrix. Diag(x) denotes the matrix whose diagonal is the vector x. |I denotes the &2 norm for vectors and the spectral norm for matrices, respectively. (. denotes the Euclidean inner product. [K] denotes the set of (1.2.... K}. For a random variable X, [[X] denotes its expectation.
2 RELATED WORKS
Optimization Algorithms in Federated Learning. The term Federated Learning was first coined in McMahan et al. (2017), where the task is learned from a set of distributed located clients under the coordination of a server. In the paper[Mccahan et al. (2017), the authors proposed the FedAvg algorithm, in which each client performs multiple steps of gradient descent with its local data and then sends the updated model to the server for averaging. The idea of FedAvg algorithm resembles the Local-SGD algorithm, which is studied in more general distributed setting for longer time Mangasarian & Sooodov (1993). The convergence of the local-SGD method has been heavily analyzed in the literature Stich 2018); Karimiirdy al. (2019b); Dieuleveut & Patel (2019); Khaled et al. (2020)g Yu et al. (2019): Woodworth et al. (2020): Woodworth 2021); Glasgow et al. (2022). Recently, Glasgow et al. (2022) proved a convergence rate of the Local-SGD under convex setting that matches the lower bound. On top of the vanilla Local-SGr SGD, various acceleration methods are considered; we list few representatives here. KKarmirredy et al.] (2020b) adopted the idea of variance reduction technique for non-distributed finite sum problems: a 'control variate" which contains historical full gradient information is used correct the bias of local gradients. Then in Karimireddy et al. (2020a). the authors proposed general framework (MIME) to translate centralized optimizer into the FL setting, including adaptive gradient methods. In MIME, the states of an optimizer are fixed during local update steps and only updated at the server-average step. In Das jtt al. (2020); ; Khanduri et al. (2021b). momentum- -base variance reduction is applied to the FL setting to control the noise of the stochastic gradients. In Das et al. (2020), the authors maintained server momentum state and a client momentum state, while in Khanduri et al.) (2021b), the authors maintained momentum state and the momentum was averaged periodically similar to the primal state.
Adaptive gradient methods are also studied in the FL setting. The 'Adaptive Federated Optimiza- tion' Reddi et al. (2020) method proposed to use adaptive gradients on the server side while the local gradients are used to update the states of the adaptive gradient methods. In Chen al. (20205), the authors first showed the divergence of a naive local AMSGGad method that directly averages the primal states periodically. The authors then proposed
method in which clients update adaptive learning rates locally and average at the synchronization step. Finally, another line of research TTag et al. (2020) 202T): [Lu et al. (2022p: Chen et al. (2020a) considers federated adaptive learning rates through the compression approach, these methods communicate local gradients at every step, but the compression techniques are used to reduce the communication cost.
Adaptive Gradients in the Non-distributed Learning. Adaptive gradient methods are widely used in the non-distributed machine learning setting. The first adaptive gradient method i.e. Adagrad was proposed in (Duchi et al. 2011), where the method was shown outperform SGD in the sparse gradient setting. Since Adagrad does not perform well under dense gradient setting and non-convex setting, some of its variants proposed, such as SC-Adagra Mukkamala & Hein (007))
3

---

Under review as a conference paper at ICLR 2023
and SAdagrad Chen et al. 2018b). Furthermore, Adam Kingma & Ba (014) and YOG! Zaheer et al. (2018) proposed to use the exponential moving average instead of the arithmetic average used in Adagrad. Adam/YOGI is widely used and very successful in deep learning applications; however, Adam diverges in some settings and the gradient information quickly disappears, so AMSGrad Reddi et al. (2018) is proposed, and it applies an extra 'long term memory' variable to preserve the past gradient information to handle the convergence issue of Adam. The convergence of Adam-typp methods is also studied in the literature Chen et al. (2019); Zhou al. (2018); [iu et al.) (2019); Guo
et al. (2021]; 3: Huang et al. (2021). Adaptive gradient methods with good generalization performance are also proposed, such as AdamW (Loshchilov & Hutter (018), Padam (Chen et al.) 2018a)) 8a).
Adabound Luo et al. (2019), Adabelief AdabeliefZZhanng et al. (2020) and AaGrad-Norm Ward et al. (0019)
PRELIMINARIES
In this section, we introduce some preliminaries before introducing our framework. First, we consider the following formulation of Federated Learning:
K
{I(=) =
1 K
Σ
( (k) (z)= BEw (F
(x; {10111}
min #EXCR
(1)
which considers K clients. For the ken client, we optimize the loss objective f(8) (x) - R which smooth and possibly non-convex, and x denotes the variable of interest. X' C I2d is compact and convex set. <(k) (D(k) is a random example that follows an unknown data distribution D(k), The formulation in equation I includes both the homogeneous case i.e. f( (x) for any j,j E [K] and the heterogeneous case i.e. (x) + (() for some k,j [K].
Next, we introduce some basics of adaptive gradient methods from a mirror-descent perspective. Generally, mirror descent is associated with mirror map ((z). Given the objective f(x and the primal state 2; E X' at ty step, we first map the primal state to the mirror space as yr = ( then we perform the gradient descent step in the mirror space: Ut+1 y/- -)) where is the learning rate, finally, we map 1+++ back to the primal space as T++1 = arg min (I, 1t+1), where D (x. v)
=EA
denotes the Bregman Divergence associated to o i.e. D& y) = f(x) f(v) (Vf(v), y). In summary, the mirror descent step can be written Bregman proximal gradient step as follows:
F++1
arg min 7/ (V))) + (x,,, xEX
For the adaptive gradient methods, uses the following mirror map: o(x) 1/=²' Ha. where H is the adaptive matrix and is positive definite. Many adaptive gradient methods can be written in the following proximal gradient descent form:
1 Fe++1 = arg min 17(2,, v) (1s H.(x x2), aEX
we replace the gradient fx(x) with the generalized gradient estimation vi, besides, we replace H with H, based on the fact that the adaptive matrix updated at every step. Next, we show some examples of adaptive gradients methods that can be phrased as the above formulation. For the Adagrad Duchi et al. (201I) method, we set
1
Vf(a,,))) H. = Diag( p4 =
Σ
v
(3)
1=1
For Adam Kingma & Ba 2014). have:
i. (1 3:) f + B10-11 = - V + B2f4-1 1/4 /, - ~1), μ4 = fm/ -201-))), 75), H. = Diag( +))
where 3, 32. 71 7/2 are some constants. For other adaptive gradient methods, please refer to Huang al. (2021).
4

---

Under review as a conference paper at ICLR 2023
Algorithm FedDA-Server
1: Input: Number of global epochs E, tuning parameters {3, h=
2: Initialize: Choose z0 A' and compute vo 1 شラ= E= V (20, b)a) where (B())
kk=1 are
mini-batch of random points selected from each of K clients;
3: for T- 0 to E - 1 do
4: Server selects set S+ of clients chosen uniformly random w/o replacement;
5: for the client E S in parallel do
6: (2,,, 1 (k)
1,17 1,1) TreDDA-clientee V, H,)
7: end for
8: Compute 2r+1 = ト Ekes, 7+,11
9: Compute F++1 arg min (- (- 2r+1) + 2x 2x -x,) x.) #Edt
10: Compute 4--1 EKES, (b)
14,,,
11:
Compute Hy+1 2(H,,,2++1) 2r+1);
12: end for
Algorithm 2 FedDA-Client (Ir, Vr, H,)
1: Input: Number of local steps I, tuning parameters (M+4,,E0 1/11 (art1,)lm
(k) 2: Initialize: x 1,0 = Iri 7+1,0 Vt: 2 ++1.0 = 0;
(b)
(k)
3: for = 0 to 1
do
4: Compute (k)
(k)
(k)
+,141 7+11, 1 1+1,8
5: Compute ++1+11 arg min (I, 24+1,41/ 2x (0- x x++1,0) H. (x x++1100) };
(k)
(K)
sEX
6: Compute 7+1.1+1 = U(v(4) ++1,5 + +1,+1 F
(K)
(N)
0r (R)
7+1,111) where (kk)
7+1,141 is
7+1,6
minibatch of random samples from the client k;
7: end for
8: Output: Send (K)
2,,, 7+11 to the server.
4 LOCAL ADAPTIVE GRADIENTS VIA DUAL AVERAGING
In this section, we introduce FedDA, a framework of federated adaptive gradient methods. The procedure of FedDA is summarized in Algorithm
In Algorithm| I we perform E global steps and at each global step, we select a subset clients for training. All selected clients at each step will run Algorithm 2 In Algorithm 2 clients receive the current model weight ær, gradient estimation V, and adaptive gradient matrix H,. The clients then perform I local training steps: line 3- line 7 in Algorithm 2
For each step, first accumulate the dual state in the variable 2! (line 4), then we calculate the local primal state x (line 5), which is proximal gradient step similar to equation 2 The function of this step is to map the aggregated dual state 27.) back to the primal space, and we use the primal state to query the gradient
to update the estimation of the gradient (k) (line 6). Note, we use a fixed adaptive matrix H, during local steps, this makes the clients share the same dual space. In line 6 of Algorithm 2 we update the gradient estimation (k) The update rule Ud()) is general, e.g momentum based variance reduction update equation 5 and the momentum update equation alas follows (a,,) is some constant):
(A) 7
V (k) (K) B 1 (1 a a.+1.41)(1 (1( (x) (())
741,41))
7+1.41
(5)
and
(k) V 17 0.41.41 ( (2:0) (k) B.
(K)
(1 (4.))) + ar+1.41))
(6)
(k) After the client runs Algorithm it returns the aggregated local dual states 2,-1, and the local gradient estimation y (kk
741 the server. The server first averages the local dual states (line 8 of
5

---

Under review as a conference paper at ICLR 2023
Algorithm! to get 2,+1- We average local dual states as all clients have a common dual space.
The server then calculates the new primal states 2++1 1 as in line 9 of Algorithm [] Next, the gradient estimation V, is also updated by averaging local states (line 10 of Algorithm
Finally, we update
the adaptive matrix H, (line 11 of Algorithm D. The update rule V is general. 6.8.
PT+1 = 1
+ (1 1r+1)pr+1, Hr+1 = Diag( /ur+1
(7)
and
M++1 = 1
(1 3r+1)01-11 H,41 (M++1 + tcIa
(8)
where we set /40 = 0, is some constant. In summary, Algorithm aggregates and averages dual states at each global round. The adaptive matrix H, is fixed during local updates and refreshed on the server side at each global round. Since the algorithm uses new mirror map (adaptive gradient matrix) at each global round, we call our framework to be restarted dual averaging.
Remark 1. In contrast to our dual-averaging strategy, some existing adaptive FL algorithms Pra neeth Karimireddy al. (2020) average the local primal states. In the unconstrained case, the primal and dual spaces are linear with each other, but in the constrained case, the linearity does not exist, and the averaging in the primal space and dual space is not equivalent. As we show the subsequent theoretical analysis, dual averaging leads to the convergence in the constrained case.
Remark 2. Note that 11 of Algorithm]] D. An alternative choice to use the most recent gradient Praneeth Karimireddy ct al. (2020). comparison, the dual state aggregates information of whole round and offers smoother estimation of the problem's 's local curvature. Another possible choice, as used in the Local-AMSGrad method Chen et al. (020b), to update the state of the adaptive matrix P4 (see equation 7 locally and then average in the server synchronization step. The limitation of this approach is that μt; is linear w.r. gradient, and thus averaging /4 does not offer a linear speed-up w.r.t the number of clients; in contrast, the dual state satisfies linearity.
the averaged dual states 2r+11 when update the adaptive matrix (line
Remark 3. By choosing different update rules U and V, representative is FedDA-MVR, which we update (k) with momentum-based variance reduction equution 5) and the adaptive matrix H, with exponential average of the square of the gradient ( equation 7 In the subsequent discussion, we focus on this variant and perform both theoretical and empirical analysis.
create many variants of FedDA. An
THEORETICAL ANALYSIS
In this section, provide the theoretical analysis of our FedDA framework; more specifically, focus on the analysis of FedDA-MVR, FedDA-MVR uses equation 7 to update the adaptive matrix (M) H, and equation to update the gradient estimation 7,, We first state the assumptions need in our analysis:
5.1 SOME MILD ASSUMPTIONS
Assumption 1 (Bounded Client Heterogeneity). The difference of gradients between different workers are bounded:
[|))()()) - (x)11 < Vk, l [K].
We measure the heterogeneity of the clients in terms of gradient dissimilarity. The above assumption
or its similar form is also exploited in the analysis of other Federated Learning Algorithms, such as Khanduri et al. 12021a); Das et al. (2020).
Assumption 2. The function f (x) is bounded from below in X, i.e., f infzex f(x).
Assumption (Unbiased and Bounded-variance Stochastic Gradient). The stochastic gradients unbiased with bounded variance, i.e.
E E (k) (z; (I: = (x)
and there exists a constant o such that
E V
(x;
(())
()(() 0² v(()) (()), Vk [K].

---

Under review as a conference paper at ICLR 2023
Assumption 2 guarantees the feasibility of the Federated Learning problem equation I and Assump- tion 3 is widely used in stochastic optimization analysis.
Assumption 4. The adaptive matrix H; is symmetric positive definite, i.e. there exists a constant p > such that
Hr ž pla > 0, 1
In our analysis, we assume the adaptive matrix positive definite, and this requirement can be easily satisfied by many adaptive gradient methods. Firstly, most adaptive gradient methods always have non-negative adaptive learning rates, such as equation [ and equation add bias term such as in the Adam update rule equation
To make it positive, we can
Assumption 5 (Sample Gradient Lipschitz Smoothness). The stochastic functions ((() (xx, g()) with ((k) (()) for all E [K]. satisfy the mean squared smoothness property, i.e, we have
V (k) (z; (()) V (y: (1)) s - v/l² for all x, E.R.
(y:
The smoothness assumption above is slightly stronger requirement than the standard smooth condition, but this assumption is widely used in the analysis of variance reduction methods, such as SPIDER Fang et al. (2018) and STORM Cutkosky & Orabona (2019).
Assumption 6. All clients participate in the training at each step, i.e. choose r = K in Algorithm !
We make the full participation assumption to simplify the exposition of the theoretical results. All the results presented can be casily generalized to the partial participation case.
5.2 CONVERGENCE PROPERTY FED-MVR
In this subsection, provide the convergence property of our FedDA-MVR variant. For convenience of discussion, we redefine the subscript t = rI + i, i.e. we denote the t step as the i local step in the t global round. Similarly, denote the total number of running steps T El. We analyze our algorithm through the following measure:
G:
2 1
112
||0 ((())1
where Di denotes the average gradient estimation at the step and ã denotes the virtual global primal state the step (see Section in the appendix for formal definitions). Remark of the appendix, we discuss the intuition of the measure G. In particular, in the unconstrained case i.e. when X' Rd. the measure -buudd the square norm of the gradient. Therefore, the convergence of our measure G, means the convergence to first-order stationary point. Now, we are ready to provide the main result of our convergence theorem.
pK2/3
96X
P ALI
Theorem 5.1. In Algorithm
choose the parameters
AL
Kp²
Wy = max
483 -1 1,143 J. A >>> O, and choose
(witt+ then we have:
8
1
2L
721
31
Σ
E <
(f(xo) -f)+
T t=0
T
K2/372/3
bT
26K2/372/3
(4822
0²
2
+ 1922
T
K2/372/3
x
4b
21
log(T + +1)
Note, by choosing a proper value of local updates and using a minibatch of samples for the first iteration decrease the noise, result matches the best known convergence rate for stochastic federated gradient methods Khanduri et al. (2021a), i.e. our algorithms has gradient complexity of Ō(e 1.5) and communication complexity of O ). moreover we achieve linear speed up w.nf the number of clients K. More formally, have the following corollary:
7

---

Under review as a conference paper at ICLR 2023
Train Accuracy
Accuri
Denstty
Tollig bodlidhg
Tollig holtidhg
0.3
PeDDaadky
Number Rounds
Numbar Rounds
Number Rounds
Figure I: Results for the PATHMNIST Yang et al. (2021) dataset. Plots show the Train Accuracy, Test Accuracy, Density vs Number of Rounds (E in Algorithm T respectively. The post-fix of T. means we consider the L1 constraints. is chosen as
Corollary 1. Suppose in Algorithm /
size we set I = ( and use sample minibatch size
O(I2) in the iitiaaization, then we have:
1
Σ
E[G.l
T
K2/372/3
and to reach an e-stationary point, need to make 01551.511 number of steps and need Ō (1) number of communication rounds.
6 NUMERICAL EXPERIMENTS
In this section, we perform numerical experiments to verify the efficacy of the proposed adaptive federated learning framework iee. FedDA. More specifically, we consider the variant of FedDA-MVR here, and defer experiments for other variants to Section [ of the appendix. We performed two sets of experiments. In the first experiment, we consider a biomedical prediction task: predicting the survival of colorectal cancer. In this task, we impose Lı sparsity constraint. L1 constraint improves the explainability of the model, which is essential for biomedical applications. Then the second experiment, consider federated multiclass image classification task. More specifically, consider two datasets: CIFARIO 10 Krizhevsky et al. (2009) and FEMNIST [allas et al. (2018). All experiments
machine with an Intel Xeon Gold 6248 CPU and Nvidia Tesla V100 GPUs. The code written in Pytorch. We simulate the Federated Learning environment through the aitorch.iistibutee package.
6.1 COLORRECTAL CANCER SURVIVAL PREDICTION WITH SPARSE CONSTRAINTS
In this subsection, consider colorrectal cancer prediction task the PATHMNST dataset Yang ct al. (202T); Kather et al. (2019). which contains different classes. It has 89996 training images, and we equally randomly split the training set into 10 clients. We used the original test set for the metric. In this task, we impose the I, sparsity constraint to improve the explainability of the model.
In this task, compare with the following baselines: FedAvg McMahan et al. (2017) and FedDu- alAvg Yuan et al. (222T). FedDualAvg is recently proposed federated algorithm that deals with composite optimization problems. In FedDualAvg, clients maintain dual states locally, but adaptive gradients are not applied. For our FedDA-MVR, we train with and without the L1 constraint. We tune the Figure I the plots are averaged over independent runs and then smoothed. In Figure FedDualAvg and FedDA-MVR-I results of Train/Test Accuracy and also the number of non-zero (below threshold) elements in the parameter (i.e. the rightmost plot in Figure П). As shown in the plots, FedDA-MVR-Li outperforms unconstrained FedDA-MVR in all metrics. This shows the importance of considering constrained problems in Federated Learning. Furthermore, FedDA-MVR-L, also outperforms FedAvg and FedDualAvg in all metrics. This shows that our algorithm effectively exploit adaptive gradient information in the constrained case. For more details of this experiment, such as the parer-par choices, please refer to Section of the appendix.
for each method and choose the best setting. The results are summarized in
consider the I, constraint, while FedAvg and FedDA-MVR not. We show
8

---

Under review as a conference paper at ICLR 2023
Burtee of PoazOs
Figure 2: Results for CIFARIO dataset. From left to right, we show Train Loss, Train Accuracy, Test Loss, Test Accuracy w.rd the number of rounds (E in Algorithm D. respectively. is chosen as 5.
bocka
Land Jilie
Namber
of ThArcs
Narber fog
Manntr of Faunnds
Figure 3: Results for FEMNIST dataset. From left to right, we show Train Loss, Train Accuracy, Test Loss, Test Accuracy w.t the number of rounds (E in Algorithm D.. respectively. is chosen as 5.
6.2 IMAGE CLASSIFICATION TASK WITH CIFAR1O AND FEMNIST
In this subsection, we consider an unconstrained image classification task for both homogeneous and heterogeneous cases. More specifically, consider two datasets: CIFAR 10 Krizhevsky et al.) (2009) and FEMNIST Caldas et al. (2018). CIFAR 10 is a widely used image classification benchmark dataset which contains 50000 training images, and construct both homogeneous and heterogeneous cases based on it. For the homogeneous case, we uniformly randomly distribute them into 10 clients. The Heterogeneous case is deferred to Appendix 8.3. FEMNIST is a Federated dataset of hand- written digits; it contains hand-writter digits of 3550 users (we randomly sample 500 users in our experiments). Data distribution of FEMNIST heterogeneous for different writing styles of people.
In this task, we compare our method with the following baselines: the non-adaptive methods: FedAvg McMahan et (2017), FedCM[Xu et al. (202T), STEM Khanduri et al. (2021a) and adaptive methods: FedAdam (Reddi et al. 2020), Local-Adapt Wang et al. (2021), Local-AMSGrad Chen al. (2020b), MIME-MVR Praneeth Karimireddy et al. (2020). For all methods, we tune their paper-parameters find the best setting. The results are summarized in Figure 2 (CIFARIO) and Figure 3) (FEMNIST), the plots are averaged over runs and then smoothed. As shown in the figures, our FedDA-MVR outperforms all baselines. In addition, the FedAvg algorithm has competitive training performance; however, it tends to overfit the training data severely. Then we observe that adaptive methods in general get better train and test performance. Finally, the superior performance of our method compared with the three adaptive baselines shows that our method exploits adaptive information better; for example, MIME-MVR also exploits the momentum-based variance reduction technique, but it fixes all optimizer states during local updates, in contrast, we only fix the adaptive matrix but update the momentum e(()), k E [K] at every step. For more details, including the hyper-parameter selection, please refer to Section g of the appendix.
7 CONCLUSION
In this paper, we proposed the FedDA framework to incorporate adaptive gradients into the Federated Learning environment. More specifically, we adopted the Mirror Descent view of adaptive gradients, furthermore, we proposed to maintain and average the dual states in the training, meanwhile we fixed the adaptive matrix during local training such that the dual space shared by all clients. We also analyze the convergence property of our Framework: for the variant FVRDA-MVR, we proved that it reaches an e-optimal stationary point with Õ gradient queries and Ô(E-1) communication rounds, these results match the best known gradient complexity and communication complexity of stochastic federated algorithms under the non-convex case. Finally, validate our algorithm for both constrained and unconstrained tasks. The numerical results show the superior performance of algorithm compared various baseline methods.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sehastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: benchmark for federated settings. arXiv preprint arXiv:1812.01097, 2018.
Congliang Chen, Li Shen, Haozhi Huang, Wei Liu, and Zhi-Quan Luo. Communication-effiiie distributed adam with complexity analysis. 2020a.
Efficient-adam:
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, and Quanquan Gu. Closing the gener- alization gap of adaptive gradient methods in training deep neural networks. arXiv preprint 1XXv:1880600666. 2018a.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam- type algorithms for non-convex optimization. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
Xiangyi Chen, Xiaoyun Li, and Ping Li. Toward communication efficient adaptive gradient method. In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference, pp. 119-128, 2020b.
Zaiyi Chen, Yi Xu, Enhong Chen, and Tianbao Yang. Sadagrad: Strongly adaptive stochastic gradient methods. In International Conference on Machine Learning, pp. 913-921. PMLR, 2018 8b.
Ashok Cutkosky and Francesco Orabona. Momentum-bassee variance reduction in non-convex sgd. In Advances Neural Information Processing Systems, pp. 15236-15245, 2019.
Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topcu. Faster non-convex federated learning via global and local momentum. arXiv preprint arXiv:2012.04061, 2020.
Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size. Advances in Neural Information Processing Systems, 32, 2019.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 201
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex opti- mization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pp. 689-699, 2018
Margalit R Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. In International Conference Artificial Intelligence and Statistics, pp. 9050-9090. PMLR, 2022.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. On stochastic moving-average estimators for non-convex optimization. arXiv preprint arXiv:2104.14840. 2021.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint wwXiv:1910.14422 2019.
Feihu Huang, Junyi Li, and Heng Huang. Super-adam: Faster and universal framework adaptive gradients. arXiv preprint arXiv:2106.08208, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for on-device federated learning. arXiv preprint arXiv: 2019a.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pp. 3262-3261. PMLR, 2019b.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning, arXiv preprint 200i:20008.00000 2020a.
10

---

Under review as a conference paper at ICLR 2023
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp- 1132-5143, PMLR, 2020b.
Jakob Nikolas Kather, Johannes Krisam, Pompimol Charventong, Tom Luedde, Esther Herpel. Cleo- Aron Weis, Timo Gaiser, Alexander Marx, Nektarios A Valous, Dyke Ferber, et al. Predicting survival from colorectal cancer histology slides using deep learning: A retrospective multicenter study. PLoS medicine,
2019.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp- 4519-4529. PMLR, 2020.
Prashant Khanduri, Pranay Sharma, Haiho Yang. Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod Varshney, Stem: A stochastic two-sided momentum algorithm achieving near-optimal sample and communication complexities for federated learning. Advances in Neural Information Processing Systems, 34, 2021a.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. near-optimal algorithm for stochastic bilevel optimization via double-momentum arXiv preprint arXiv:2102.07367, 2021b.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv preprint /00i::9900.032000 2019.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2018
Yucheng Lu, Conglong Li, Minjia Zhang, Christopher De Sa, and Yuxiong He. Maximizing communication efficiency for large-scale training via 0/1 adam. arXiv preprint arXiv:220..06009 2022.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv: 1902.0984, 2019.
Olvi Mangasarian and Mikhail V Solodov. Backpropagation convergence via deterministic nonmonotone perturbed minimization. Advances in Neural Information Processing Systems, 6, 1993.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication--fficieee learning of deep networks from decentralized data. Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
Mahesh Chandra Mukkamala and Matthias Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. In International Conference Machine Learning, pp. 2555-2553. PMLR, 2017.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv e-prints, pp. arXiv-2008, 2020.
Sashank Reddi, Zachary Charles, Manzil Zaheer. Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003. 00295, 2020.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference Learning Representations, 2018.

---

Under review as a conference paper at ICLR 2023
Matthew Staib, Sashank Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. In International Conference on Machine Learning, pp. 5956- 5965. PMLR, 2019.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv: 2018.
Hanlin Tang, Shaoduo Gan, Samyam Rajbhandari, Xiangru Lian, Ji Liu, Yuxiong He, and Ce Zhang. Apmsqueeze: communication efficient adam adam-preconen preconditioned momentum sgd algorithm. arXiv preprint arXiv:2008. /343, 2020.
Hanlin Tang, Shaoduo Gan, Ammar Ahmad Awan, Samyam Rajbhandari, Conglong Li, Xiangru Lian, Liu, Ce Zhang, and Yuxiong He. 1-bit adam: Communication efficient large-scale training with adam's 's convergence speed. In International Conference on Machine Learning, pp. 10118-10129. PMLR, 2021.
Jianyu Wang. Zheng Xu, Zachary Garrett, Zachary Charles, Luyang Liu, and Gauri Joshi. Local adaptivity federated learning: Convergence and consistency. arXiv preprint wxiv:2206.00:300 2021.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In International Conference on Machine Learning, pp. 6677-6686. PMLR, 2019.
Blake Woodworth. The minimax complexity of distributed optimization. arXiv:2109.00534 2021.
arXiv preprint
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Memahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343. PMLR, 2020.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint arXiv:2106. 10874, 2021.
Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu, Anarchic federated learning. In International Conference on Machine Learning, pp. 25331-25363 PMLR, 2022.
Jiancheng Yang. Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. Medmnist v2: A large-scale lightweight benchmark for 2d and 3d biomedical image classification. arXiv preprint arXiv: 10.199//..447..... 14795, 2021.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 5693-5700, 2019.
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference on Machine Learning, pp. 12266. PMLR, 2021.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances in neural information processing systems, pp. 9793-9803, 2018.
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the conver- gence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv:1808.0567/ 2018.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvorekk, Xenophon Pa- pademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in Neural Information Processing Systems, 33, 2020.
12

---

Under review as a conference paper at ICLR 2023
8 MORE EXPERIMENTAL DETAILS AND RESULTS
In this section, we add additional experiments. In Section 8, we consider more variants of FedDA besides FedDA-MVR. More specifically, we consider four variants of FedDA. We introduce two cases for the update of the adaptive matrix H- in equation / and equation 8 and we denote them as case 1 and case 2, similarly, we denote equation [5] and equation 6 as case and case of gradient estimation respectively. So we have four different variants, we denote them as FidDA-i-j, for i,j E (1, where shows the choice of gradient estimation and j shows the choice of adaptive matrix update rule. Note FedDA-MVR corresponds to FedDA-1-1 estimation and Case of adaptive matrix update in Algorithm!! [ We also introduce more details such as the hyper-ppramen parameereet choices. Then in Section 8.2, we perform some ablation studies and compare our FedDA with other baselines in more detail; In Section 8.3, we include experiments when we construct heterogeneous dataset from CIFARIO; Finally in Section 8.4, show the form of our FedDA when / = 1, i.e. no local steps.
we choose Case 1 of gradient
8.1 OTHER VARIANTS OF FEDDA FOR TASKS IN SECTION 6
8.1.1
COLORRECTAL CANCER SURVIVAL PREDICTION WITH SPARSE CONSTRAINTS
TedRA 15
043
Thain Accurscy
Test Accuracy
Density
0.43
Fed 1-1-L
h
Fed
171
3011
AKG 90/1
3911
AKG
301
120:
2013
201
Number of Rounds
Number Hounds
Number of Hounds
Figure 4: Results for the PATHMNIST dataset. Plots show the Train Accuracy, Test Accuracy, Density vs Number of Rounds (E in Algorithm I respectively. The post-fix of L1 means we consider the L1 constraints.
In this task, we use 4-layer convolutional neural network with 32 filters each layer. We have 10 clients and run 20000 steps (T), average states with interval 5 (!) and use mini-batch size of 16. Besides, we calculate density with threshold 0.01. For other hyper-parameters, we perform grid search and choose the best setting for each method. More specifically, for the SGD method, we use learning rate 0.01; for the FedDualAvg algorithm, we use local learning rate 0.1. global learning rate learning rate 0.01, as 100000, c 5000000, we also add L.2 constraint
0.1, L1 constraint 0.01; for our FedDA-MVE
( as 0.999 and r as 0.01, for the L, regularized version 0.01. For other variants of FedDA: for FedDA-2-1, we learning rate 0.001,
0.9, /3 0.999, as 0.01; for 1--,,-1-2,, we use learning rate 1, w as 10000, e as 200, / as 0.999, T as 0.001, L1 constraint 0.01: for FedDA-2-2, we use learning rate 0.01, a 0.9, 3 as 0.999, 7 as 0.01, Lj constraint 0.01. The experimental results for different variants of FedDA is summarized in Figure 4 As shown by the plots, all variants of FedDA get good performance, but we find FedDA-MVE (FedDA-1-1) gets most sparse model as measured by the density metric.
8.1.2 IMAGE CLASSIFICATION TASK WITH CIFARIO AND FEMNIST
In this unconstrained federated image classification task, we use a 4-layer convolutional neural network with 64 filters each layer. For the FEMNIST dataset, we randomly sample 50 users at each global round. We run 20000 steps (T), average states with interval 5 (7) and use mini-batch size of 16. For other hyper-parameters, we perform grid search and choose the best setting for each method. In the CIFAR1O 10 related experiments, for the SGD method, we use learning rate 0.005; for the FedCM algorithm, we use learning rate 0.01, momentum coefficient a as 0.9; for the FedAdam algorithm, use local learning rate 0.001, global learning rate 0.002, momentum coefficient 0.9, coefficient for adaptive matrix 3 as 0.999; for the Local-Adapt algorithm. we use local learning rate 0.001, global learning rate 0.002, momentum coefficient 0.9, coefficient for adaptive matrix / as
13

---

Under review as a conference paper at ICLR 2023
FARAL
Number Toards
Bumber of Touric
Namber Tounds
Norbor Dsents
Figure 5: Results for CIFARIO dataset. From left to right, we show Train Loss, Train Accuracy, Test Loss, Test Accuracy w.rl the number of global rounds (E in Algorithm T. respectively.
0.999; for the Local-AMSGrad algorithm, we use learning rate 0.001, momentum coefficient 0.9, adaptive matrix coefficient 0.999; for the MIME-MVR algorithm, we use learning rate 0.1, w 100, as 2000; for the STEM algorithm, we use learning rate 0.1, w 100 and 2000; for our FedDA-MVRR 10000, as 1000000, 3 as 0.999 and FedDA: for FedDA-2-1, 1, we use learning rate 0.001, a as 0.9, / as 0.999, t as 0,01; for FedDA-1-2. we use learning rate 1, as 5000, as 100, 8 as 0.999, as 0.01; for FedDA-2-22 we use learning rate 0.01, a 0.9, 3 as 0.999, T as 0.01.
we use learning rate 0.02,
0.01. For other variants of
Nutber
nutber MAREEE
Figure 6: Results for FEMNIST dataset. From left to right, we show Train Loss, Train Accuracy, Test Loss, Test Accuracy W.E. the number of global rounds (E in Algorithm I respectively.
Then in the FEMNIST experiments, for the SGD method, we use learning rate 0.1; for the FedCM algorithm, we use learning rate 0.1, momentum coefficient a as 0.9; for the Fed/ddam algorithm, we use local learning rate 0.02, global learning rate 0.04, momentum coefficient 0.9, coefficient for adaptive matrix 3 as 0.999; for the Local-Adapt algorithm, learning rate 0.02, momentum coefficient 0.9, coefficient for adaptive matrix as 0.999; for Local-AMSGrad algorithm. coefficient 0.999; for the MIME-MVR algorithm, we use learning rate 1, w 10000, as 400; for the learning rate 10000 and 400; for FedDA-MVR,
use local learning rate 0.02, global
learning rate 0.0005. momentum coefficient 0.9, adaptive matrix
STEM algorithm, rate 0.02, w as 10000, c as 1000000, 33 as 0.999 and 7 as 0.01. For other variants of FedDA: for learning rate 0.001, learning rate 1, w as 5000, as 100, /3 as 0,999, T as 0.01; for FedDA-2-2, we use the learning rate 0.01, 0.9, 8 0.999, as 0.01.
use learning
FedDA-2211,
0.9, 3 0.999,
0.01; for FedDA-1-2, we
The experimental results for different variants of FedDA is summarized Figure and 6 As shown by plots, all variants of FedDA get good performance. FedDA-MVR (FedDA-1-I) gets the best performance in most metrics, we observe that its test loss show some extent of overfitting in the late training stage.
8.2 MORE DISCUSSION OF EXPERIMENTAL RESULTS
In this subsection, we make more detailed comparison between our FedDA and other baselines (The experiments are over homogeneous CIFAR10 dataset). In Figure 7 we compare FedCM with FedDA-2-1 and FedDA-2-2 for different values of local steps /. Since FedDA-2-1 and FedDA-2-2 do not use variance reduction acceleration, the superior performance shows the effectiveness of using adaptive gradients in our framework. Next, In Figure g we compare -ocal-AMMGrad vs FedDA-2-1 for different values of I, FedDA-2-1 outperforms AMSS-dd for all I and with greater margin for larger I. Note both Local-AMSGres and FedDA use Adam-style adaptive gradients (equation 6 and equation 7) and have communication cost per epoch. In Figure
14

---

Under review as a conference paper at ICLR 2023
compare FedAdam and Local-Adape with 2--1. All methods use Adam-style adaptive gradients. FedAdam only performs adaptive gradients over the server, Local-Adapt performs both local and global adaptive gradients, but the state of the local adaptive gradient is refreshed per epoch. We have two observations: First, the Local-Adapt method has very marginal improvement over FedAdam, which shows the restarted strategy used by Local-Adapt is less effective than our method; Second, both FedAdam and Local-Adapt benefit little from increasing the I value (compared to our FedDA-2-1). For FedAdam, this shows the limitation of only applying adaptive gradients at the server level. Finally, in Figure [0] we change I for all four variants of our FedDA. As shown by the figure, our framework can benefit from more local steps.
Thiy
Naster Reands
2013
D51 25. Surver R2a00.
2011
201 Rusterd Roaess
103 Sarepor 200
Munca Aourd
Number of Plores
eooe Sards
Nartor ef Raunds
Figure 7: Comparison between FedCM vs 2-dDA-2-1 and FedDA-2-2. From top to bottom, we show I 5, 10, 20 respectively. The number inside the parentheses is the value of 1.
TM4 1001
Narber of Sounds
Surroe o' kbunds
Burber of Rounds
Murrzar of kounds
201
251
2013
From top to bottom, we show I = 5, 10, 20 respectively. The number inside the parentheses is the value of Z.
Figure& 8: Comparison between LMsal-AMSGrad vs 1-
15

---

Under review as a conference paper at ICLR 2023
Raddec lear
Becter Stean
Sucver Roarr
200 Number Flancc
Tounh
Nanter Faunds
Figure 9: Comparison between FedAdam and Local-Adapt vs FedDA-2-1. The number inside the parentheses is the value of
horterr (1 Roundh
Surver Raare
Rurter of Roaess
Bumber Rounds
200
2011 Burber Rourds
Mumnaar
1A00U0 CR
Mumraa Aaunds
Number of Rourcs
MunDa lound
Nanbor Aqundds
Figure 10: Ablation study of local steps 1. From top row to the bottom row, we show results for FedDA-I-I, FedDA-1-2, FedDA-2-1 and FedDA-2-2. The number inside the parentheses is the value of I.
8.3 IMAGE CLASSIHCATION TASK WITH HETEROGENEOUS CIFAR10
Besides the FEMNIST dataset considered in the main text, we validate our FedDA over a manually crafted heterogeneous dataset based on CIFARIO (Similar approaches are seen in literature such as Das al. 20200; Yang al. (022)), ). Note For CIFARIO, we have 50000 training images and 5000 images per class. We create heterogeneity in the training set as follows: Suppose we have 10 clients, for 4th client, classes, where 0 < p < 1. Note for close to 1, the é client will be dominated by images of in class, thus the data distribution among clients will be very different. In experiments, choose
distribute p-percent samples of iy class, and (1 (00-pp))pppcleeee /9ppereeent samples of other
16

---

Under review as a conference paper at ICLR 2023
p= 0.8. This means the in client has 4000 images of ith class and 111 images of other classes. This creates a high level of heterogeneity. Note that we use the original test set of CIFARIO. The results summarized in Figure II Note compare with the same set of baseline methods in the homogeneous case. FedDA-i-1 represents different variants of our framework, in particular, F 1-1 represents FedDA-MVR. As shown by the figure, all of our variants outperform the baselines. FedAvg suffers most due to heterogeneity and is much worse than other methods. Compared to the homogeneous case (Figure 2 and Figure 5). the methods overfit to the training data slightly more.
Nxuth
201 Numberrd PoarES
2013 Suamorr PALIESS
Figure 11: Results for heterogeneous CIFAR10 dataset. From left to right, we show Train Loss, Train Accuracy, Test Loss, Test Accuracy w.r.f the number of rounds (E in Algorithm respectively. is chosen 5.
For syper-paramett we perform grid search and choose the best setting for each method. For the SGD method, use learning rate 0.01; for the FedCM algorithm, we use learning rate 0.01, momentum coefficient a as 0.9; for the FedAdam algorithm, we use local learning rate 0.001, global learning rate 0.002, momentum coefficient 0.9, coefficient for adaptive matrix 3 as 0.999; for the Local-Adapt algorithm, we use local learning rate 0.001, global learning rate 0.002, momentum coefficient 0.9, coefficient for adaptive matrix 33 0.999; for the Local-AMSGrad algorithm, learning rate 0.001, momentum coefficient 0.9, adaptive matrix coefficient 0.999; for the MIME-MVR algorithm, use learning rate 0.1, 100, c 2000; for the STEM algorithm, 0.1, w 100 and с 2000; for our FodDA-MVR/FedDA--L11 we use learning rate 0.02, w as 10000, c as 1000000, B as 0.999 and T as 0.01. For other variants of FedDA: for FedDA-2-1, we use learning rate 0.001, a as 0.9, 8 as 0.999, r as 0.01; for FedDA-1-2, we use learning rate 1, w as 5000, e as 100, B as 0.999, as 0.01; for 2-d2A-2-2, we use learning rate 0.01, a 0.9, 0.999, 0.01.
learning rate
8.4 SPECIAL CASE OF FEDDA:
To better illustrate the structure of our FedDA, we give the form of a special case in this subsection, iee = The pseudo code is summarized
Algorithm 3 at each epoch, the server first gets new primal state through equation 2 (line 4); then each client (we assume full participation for simplicity) updates gradient estimate Vr locally (line 6), and the server average these states (line 8), the adaptive matrix is also updated by the server (line 8).
Algorithm 3 CodDA--issributted
1: Input: Number global epochs E, tuning parameters {a,, 3r. 17 1E
2: Initialize: Choose zo X' and compute vo 1 E ( B(()) where (B(()) jk=1
mini-batchhae of random points selected from each of K clients;
3: for 7 = to E 1 do
4: Compute 27 +1 arg min (2, (I, U+) + Ex (x xz )z xz) ) ):
=EX
5: for the client k [K] in parallel do
6: Compute (N) = L1,,, 27 Fri a1 ((k)) where ((A)) a minibatch of random
samples from the client k;
7: end for
8: Compute 1/-1 1 Exe[K] u and Hr+1 V(H,,
9:
end for
17

---

Under review as a conference paper at ICLR 2023
PROOF OF THEOREMS
In this section, we provide the convergence analysis of our algorithm.
9.1 PRELIMINARY PROPOSITIONS
Proposition 1. Let {0k},k E K be K vectors. Then the following are true: |10 + 0,l1 I
(1+ 1)1 + (1 + 1)11 for any > and Ex=1 02 < K Σ ||0x||2
Proposition 2. For a finite sequence 2()) E Rd for E [K] define = 1 E 2(0) we then have
Σ (R)(0) 2 - Σ k=1 11
Proposition 3. Let 0 and 21, 22. 28 O. We have Ei zo Eime
log(1
Eist )) 20
These propositions are standard results. For proofs, the reader can refer to Lemma 3 of Karimireddy al. (2019a) for Proposition and Lemma C.I and Lemma C.2 in Khanduri et al. (2021a) for Propositions 2 and 3.
9.2 PRELIMINARY LEMMAS IN LOCAL UPDATES
We first introduce some notation. For 0 S I, we denote:
P (x) = (x,
(k) zx11 + 2 x7,0) TH, H1 (x x0,0),
(10)
then, by definition (Line 4 of Algorithm
2). we have:
(k) = arg min (i (2r),
(11)
r.a
xEX
also define
(..(1)) = (2, 2T,)) + 21 (x - xT,0) H7 - 17,0);
(12)
(k) where 2r,J = E 2, the virtual average of 2! and NT.00 vy. Then we define
H arg min (x),, x
(13)
Remark 4. In Algorithm I at each epoch we only sample r clients from the K clients to perform an update. For k & S,, define the relevant variables for convenience of analysis and they really calculated.
Remark 5. Note that the global primal state म. is not the arithmetic mean of the local states x; in general.
Finally, we also define
dr,s = (5r, - 1r,s+1), d00)
1
1
(z).)
(N) 1. [K] e [4],
(14)
Th.
17.3
Furthermore, recall that by the procedure of Algorithm
2 (line 6). we have
Dr,6 1 (Zr,1 2r,441, ((0) 1
(2 7.tt)) k [K], i [7],
(N)
(15)
T7
17..
Remark 6. When it is clear from the context, we omit the global epoch in the subscript of the definitions, L.e. we use (/(a))) (z), (1(x). 22(h) 2, d, d.aa) D4, vi and H.
(k)
Next, we introduce the following lemma related to local updates. We omit the global epoch number in the subscript.
Lemma 1. For any E [T] and E [K]. we have the following inequalities be satisfied:
1. Xx (k) L,nnyy 11 (1 1
18

---

Under review as a conference paper at ICLR 2023
2. X(F,, d pl 1| A | 2 pl p||dا|]:
3. A| (k) 2,11 -||= :|||:
Proof. The first and second claims follow similar derivations, and we provide only the derivations for the first claim. First, if i we have
(k) arg min (z, 21 2A (x , H(x 10 )
by the first-order optimality condition, we have:
(-21 (+2 + H(x (R) (1))
xn ) u x
(()) 2 0, VuE
(l) choose a T0 and use the fact that (k) 1o we have:
(*) || ||
(h) - 11 Z (o
(R)
(1)) (k))
1 [1]
(b)
1u (2) H No 2
(k) (
(8)
0
(K)
11
x
we use the assumption of the adaptive matrix in the rightmost inequality, we get the result in the lemma.
inequality in the leftmost inequality and use the strong convexity
Next if i > 0, by the definition of v/ (8) (x), we have:
v/ (1) (18
1 (1) (x.44) 2 (1) (z, -(((() 2141 x (1))) +
(k) (8)
21 (+it1 2; ((
(c (K) H (2141 + 2;; -x00 (k))
(k)
(16)
Then by the definition of x; (k)
and the first order optimality condition, we have
X M (k) (k)
2,
we pick u = x 2:+1 we have (2,
(k) (k)
F++1
x (K)) ス - (1 - (1) (( xx)),, plug this
inequality to equation [6] we have:
(m)+1) 1// (k) (mx(t)
(M)
2 1 (2t [x]4] - -1 H (z) (8)
(k)
+
21
1
(2
4+1
(k)
- 11
(2)
(2)
(1) - 2x (K) + +1,
2 21 (m n / H (1x (1)
(4 x14 1k)
Similarly for 4i+1, we have:
(1 (k) (1 (1((1) = - 1, - x
(K)
(k) (M)
1
(c -x 2 (1 + xx (k) - (0)
2X
and by the definition of x and the first order optimality condition, we can get
2- + A H (k)) ) (k) 2 0, VuE
pick u = x;²² we have (k) 24 - -x,t)) (1)) S - (1 - xz (1) (8) - 1o (k)), plug this
inequality to the above equality, have:
(/()) (x) ( (M)
< 1 (++ - 21 (
H (1: (k)
x6 21 (1
(k0)
(k)
(:: (k)
x (k) (K)
2x
< 2X (+++1 2 (k) H
1
(k)
(k)
i+1
I
Next, by definition of w (x) and (k) (I)), we have: ((+((a))
/ 10t (K)
vi4i ( (1.(a) 3/ (c(aa) w/ (x())( (x mndeh (K) (k)
19

---

Under review as a conference paper at ICLR 2023
Finally, combine the above relations and have:
X
| (8) - 2 To ( (1) - 2 7 (a:41 (x0) - ( 2
(12)
(k) 1|?
we use the Cauchy-Sehie Schwartz inequality in the leftmost inequality and use the strong convexity assumption of the adaptive matrix in the rightmost inequality, we get the result in the claim of the lemma.
Next, we prove the third claim, by the definition of (k) (+1, have:
(K) (1 (o(41) Vit1
(R) wit Vi+1 (Z++1) (2 (2 24+1 T++1) 2X (oit) #141)" + 3++1 2.00 (k)
(k) By the definition of #241 and first order optimality condition, we have
++1 + 1 [|
(k)
(K)
=00)),, u- (k)
Ii+1) 2 0, VuEX,
(k) (k) $;+1) S - 1 (1/41 3++1) 7 (x xo (²)).. Plug this
pick u 1, we have - (22 2i4l
inequality back to the above inequality, we have:
(14)) (m=+1) - (
5 (fit1 -=-1)" H (2 Io ) +
1 (k)
(k) (k)
1 (k)
(+it1 -++1)² H (x T -2x²²)
(k)
2x
1 (k)
< 21 (1² ( ) H #141)
Then for tit (I), we have:
Witi (x(4)) W (#++1) - (Z++1, " (8) 8++1) + 1 (6)
((k)
2x (1it1 #411 H (k)
(a
8441 270)
By the definition of 8441 and first order optimality condition, we have:
(-ē++1 + = H(i+1) To), -ii+1) 2 0, Vu
pick u 2;+1 have - -E x.+1 f1+1) 2 (1 8.41) H H( 20). Plug this inequality back to the above inequality, we have:
(k)
(K)
(k)
Jes (1 (5x+1)
1 (1:4 Ti+1) ) H H(i++1 -To) + 1 (k)
21 (1it1 T.+1) H (k) + -25o)
2 21
(1 - T.+1> )²d H (x - Ti+1)
(K)
(k)
Next, since we have Io To. then by the definition of (((h) (x) and 1 we have:
(K)
(#:41) (x(1( ( (2(4)) - E 2441 2(t1)
(K)
Next, we combine the above relations and have:
11 E111l
(k) [|=
(k) L+41ll 2 (2 Et+i (K)
x141 Z(41)
A [+++ 2 (= 2(41) 2 p|l - ă141l12
where the first inequality is by the Cauchy-Schwartz inequality and the last inequality is by the positive definiteness of H. This concludes the proof of the first inequality in the lemma.
20

---

Under review as a conference paper at ICLR 2023
9.3 STATE CONSENSUS ERROR
As each client performs local update, the states i.e. 2,, and vr. drift away, the following lemmas bound this difference. We omit the global epoch number in the subscript.
(())
Lemma 2. For each 0 v i < I, and suppose iterates 2 k E [K] are generated from Algorithm we have:
(k)
K
K (8)
B
2112 5 (I-1)
BlluA
0zl1?
t=1
k=1
where the expectation is w.r.t the stochasticity of the algorithm.
(R) 0, the inequality in the lemma holds trivially.
Proof. Based on Algorithm we have 20 Eg Otherwise, we have
(k)
and 2, = - Σ
neve
neP..
t=
8=0
So we have:
Σ
1:11
(neve (k) - me0e
5
Σ
2 f1
(k) 1/
Dell
(k) vo for [K], the inequality uses the Proposition and the where the equality uses the fact vn fact that we have i < 7. We get the claim in the lemma by taking expectation on both sides of the above inequality. This completes the proof.
Lemma 3. For i [7. we have:
K
4X2
p²TR?
ME
B (k)
1el1
where the expectation w.r.t the stochasticity of the algorithm.
Proof. Firstly, when = 0, . = Ty.
21 = =1 so we have 11 = 7g by Line 5 of Algorithm 2
(kk
and then we have nod xo x1 $o #1 ne the inequality in the lemma holds trivially.
(k) (k)
Next when i > 0, we have:
Th (loftt 111
|| (1) (k)
x;+1 (o. 1+11)11 < 2/112 (K) -x11² ++11=174 (R) 51+1l 11
2X2
(11=) 2
2
|| - 2++1|13) 112)
The last inequality uses claim 3 of Lemma
Sum over E [K] and use Lemma 2
we have:
K
1-1
K
K
(a d,11 2 1)
E VE
(k)
Del1 + 2X - 1) Σ mp
(k)
1e
K
4x2(1 1)
E 10
(k)
Del12
1=1
1=1
This completes the proof.
21

---

Under review as a conference paper at ICLR 2023
9.4 DESCENT LEMMA
In this subsection, we bound the descent of function value (ūr,z) over the virtual sequence Zr,
Lemma 4. Suppose that the sequence {x)))) [-1
Ji=0 be generated from Algorithm then we have
f(x+11) S f(x,)
3p1
)
||d++1ol1+
ET+1a
4A
2
P
where B,, = D
1 R EKEn V / (G,,)).
Proof. Since the function f(x) L-smooth, we have (we omit the global epoch number for ease of notation):
L f(al===
Luk
f(1 S f(..)+ (Vf(,,) -,)
+ 12
|
2
2
= f(i,) - (p,, d.) - 17. (V D4, d+) + LMZ ||db12
(0)
LuZ
S f(a.) PT
|| (Vf((.) Dr di)
2
(
2 f(a.)
pT)
L
||d:|] 1|2 + PTh
| 1
An 1 2
A
2
41
19)
3pp%
nfL
An
2 f(z.)
|| +
|2,1|
4X
2
In inequality (a), we use claim of Lemma 1 inequality (b) uses Young's 's inequality; inequality (c)
denotes E, i/ R Ek (z.).
For the t global epoch, we sum over to - 1, we have:
((r++11) S ((+++100)
3pp+11
12+12
l 1 +
A
4X
2
1=0 P
E
Follow the update rules in Algorithm T Tand Algorithm This completes the proof.
2 we have F,+10 Hr and Ty41.1
9.5 GRADIENT ERROR CONTRACTION
In this subsection, we bound the gradient estimation error ε7,i, where we have ε.,i D7,7 K EK (ār,) as defined in Lemma additionally, we also define the global gradient estima- tion error e, as e, = 14- K Σk= ( (x+) 14 (=(=)). Note we have e, = G,, = 6,+1.0- We first show a fact about ég. the initial gradient estimation error.
Lemma 5. For eo == 1/o
ΣK (x))) suppose we choose mini-batch size of |B(
b, k E [K]. we have: E KK
Proof. By line 1 of Algorithm
we have:
E
El
E
(k) (5o)
K
K
K
E
(k)
(xi: (3)
V
(k) (zo)
K
K km
K
2 (M) 0²
E
V p( (k)
(woi (6(
v (x0)
(xo)
K2
bk
22

---

Under review as a conference paper at ICLR 2023
where (a) follows from the following: From the unbiased gradient assumption, we have: E V ( (2) bb (zg)) for k [K]. Moreover, the samples B8 and B/a) at the hthh and the eth clients are chosen uniformly randomly, and independent of each other for all k, l E [K] and l L.
) v ((th (V) (ap 0 :B:)) - v(())) } (m)
E
(1) (1) - | (E[V)<
BB V (a))
)|
Inequality (c) results from the bounded variance assumption. This completes the proof.
Lemma 6. Define Er,i -
K Eke (T+s). then for every T 2 1 and i 2 0, suppose
ag < and clients use batchsize b1 in the training, then we have:
40A² 1)L2
K
Bl S (1 ax,,)
E| 1 T,e - Dr,ell?
(k)
R2k
17
t=1
k=1
8n L
4a
+
B|d---111"
K
where the expectation is w.r.f the stochasticity of the algorithm.
Proof. Consider the error term || 2 1 (we omit the global epoch number 7 for ease of notation),
we have:
E
(z,)
K
K
E
B
(1 an)
1/-1
1
(k) (x
(2(2), 1,,))
Σ
(5:)
K
K
E
Σ
(
:, v (
-11- a.) v (k)
((= - + - (11-aa));111
K
(1
1| +
E
((a)) - (x()
K2
1=1
- -11
(-, v (1)
K
(1 EE
+
E
(vF(h) (1+ (k), B - v (())
K
1=1
- -(1 (,) - ((
where the first equality uses the definition of i;; last equality follows from expanding the norm using the inner products across k [K] and noting that the cross term is zero in expectation because of the
23

---

Under review as a conference paper at ICLR 2023
samples are sampled independently at different workers. Now we consider the 2nd term above
(V
(1); - -
1
E
(8) B3 (1) 4/ - (1 (1-))
(x) (K)
- (1- - -1----))
< 2 / (4) 1 (00 (-))), (1-0) (1
(x (k) || / ((-1))
21E V (z. (1) (F)) (1 -
+
For the first term of the above inequality, we have:
{ (8) (z. (b) 10())) - (a())) - (1 as) (s) B(a)) - (2 (K) 1
RII(1 a:) ((tt)) 4 (1) - (4 B (1)
(b) (x
2 3E
(x) (00)
(1)) v(((""")))
+ +2 s 2 - n:) ) ",, 2
(z)
(a(")) 2
2 ox) - ||
2a /bi
$ 4(1 a, )2 E
+220022 /b
where uses Proposition in the first inequality and the bounded variance assumption in the second inequality. For the second inequality, we have:
in
v (2 - - -- (1)0))))))
(0)
5 21 V / (1 ( -- - ((.))) 1
< <2L'E|10 (K) 2.1" 2 - 21 -- 1/
(k)
2 22
13 11| - (1) = 2X a.)2 E |/ - 1|
/2
24

---

Under review as a conference paper at ICLR 2023
where (a) uses Proposition D (b) uses claim 3 of Lemma 1 Next, combine the above inequalities together to get:
4af0² b
8(1 -
L2 k
E &
2 $ (1 - a;) 2 11 12+
E (k) 1-1
d
K
A=
8(1 - -0:1-;)²21 01)) 1,2
4
+
1Bld; 11
E 2
(8)
K²p²
42212(11 a2)
K Σ
T3
4-1 - 23-1|1 111
K2
k=1
40,0
32 1)(1 - -2
$ (1 a:) B 211 12
b K
K2p²
118
2
B| Bl
(k)
Dell
1=1
k=
8(1 an)²m1 L²
4X2(T 1)I.
i-1
K
B|
11
K²p²
11
B
E
(R)
1212
412 ()
04-1) )2
1-2
K
Σ
1/
DEl1
K2
1=1
k=1
4a70²
40A
1)T
i-1
K
8 L2 E
S (1 (1- -
E
(K)
12l1
E
Eldd
k
K²p²
K
t=1
The second inequality uses Lemma and Lemma 0g < 1. This completes the proof.
3 and the last inequality uses the assumption that
Lemma 7. For 2 0. Suppose we choose Th., (w: +i+ 1/) additionally, suppose a;
w; I wi-1, wi 2 2, Vr, TXLTTT be satisfied, we huve:
pk
E 1B 1|
E 1|2
1-1
31
22 1r +1.
El E1
647,2
7
MT
2p
161.
0=
1=
51(1 1)
4Kp E=1
1,+
K
B
Bllb
7+1.1
- 1r+1.
(K)
k=1
Proof. Using Lemma the global epoch then for i 2 (we denote 77,-1 17--1,1-1 for
all 7 2 1), we have:
El
El
Tr, 77,1-1
(1 a²
1
E E
4T - 1)
2
E
1 (K)
Dr.e1
n7,
1r.-1
p²127Tr.s
km
8L SL' E. 11,
4a $0
+
K
Dr b, K
(a)
80A2 (I 1)L2
K
-1 I (nr 1 B)),,)
Σ
(k)
Dr.ell2
p²1²
The
k=1
402 202
+
El dr,
K
b,K
where incquality (a) utilizes the fact that (1-a,,)) < - ar S and ar,i = cni,, for all
i [7], and the following fact: suppose choose 7r,1 K/ + then for 0 s
25

---

Under review as a conference paper at ICLR 2023
have:
(w; + +
w/ + i 1z - 1
1/3
1
TT
(w) + l + T1)2/3
w1 1 rT
1 (1 (1-1) 1)
1/3
(1-1) (wm) + + +1+ 2
S
(17)
un 1 +
The first incquality is by the fact that < - - 1, the second last inequality uses the concavity
of 1/3 as: (ar + y) 1/3 x// < 3/3x2/3, while the last inequality uses the fact that wi 2 0, / 2 1,
0, 2 1.
For the difference ni=
-1 111-1, we have:
(wi + i +itt0 =1)1/3
(wi-1 + i - 1 11)
7r,1
Tr,i-1
K
(wy + i + 1//
(w; + i - 1 + T TI)//3
k
1 3k(w; i + +/)2/3
22/3
(d) 22/3 (e) 3x3 n S
p
3x Wi + 1i+1/)2/3
72k
XLI2
ni
(18)
where inequality (a) is because that choose wa S w;-1, (6) results from the concavity of x 1/3 as: (x+ y)/3)/// 1/3 y/ /3x22/3), (c) used the fact that w, 2, finally, (d) and (e) utilize the definition
of 7r,i and the condition that V/. S respectivvl.. So if we choose
Kp
72k ALL
96X2
we have: 77.5 17,6-1 Crs S
Kp 77,1
Therefore, we have:
E 1,111
11
7T,i-1
96A2 L n Kp²
E3 Ee 1 +
80A2 - 1)L²
0²k²
Tr, k=
E
(K) r.6
Dr.ell
8T. 8L22
Mr
Blidr.:11 +
40 2022212n
K
biK
Multiplying pK /64AL2 on both sides, we have:
pK
E E
Blea.il" 12
3A
Bl|e,,
5A(T 1)
Tr.
K
E
Ellp
-,6 Dr.el?
(k)
64XL2
1/41-1
2p
4Kp
8=1
k=1
0²c² 22c2112.p
+
Tr
EE 111dr..1?
+ 16X1,2
8A
Then sum the above inequality from 0 to I - and get:
pK
E
E.
1|
E
|
3
E
5A(T 1)
Σ 118
(k) Bllb
Dr.ell
64XL2
1T.1-1
111-111
2p
4Kp
T.l
1-1
1-1 0²
Σ
NT.iP
Elldr,111
+ Σ 16XLab
8A
1=0
1=0
32111
5A1(1-1 -1)
K
E. 1ET,ii11
12
Bllu
7.6
(k)
v=.e
2p
4Kp
1=0
k=1
I-1
Mr.i
Elld
11
Σ
82
16A
1=0
By definition, have εG,0 cr-1 and ē,, e,, then we get the results in the lemma by replacing
7 by T + 1.
26

---

Under review as a conference paper at ICLR 2023
9.6 DESCENT IN POTENTIAL FUNCTION
We define the potential function as follows:
p
1|+|11
2 = f(t,) + 64AL2
(19)
11--1
Next, we characterize the descent in the potential function.
Lemma 8. For wny 2 O, we have:
B -,,|
5p1r+1,4
1
Bl|de|12
A
Σ
1-1
1|+,, B 11,
82
2
2p
i=0
&Cp
5AI(I -1]
Σ
Σ
1,+
E
(1)
Ur+1,el??
16AL2b
4Kp
where the expectation is w.r. the stochasticity of the algorithm.
Proof. We can the inequality in the lemma by combining Lemma and Lemma
7
9.7 ACCUMULATED GRADIENT ERROR
In this subsection, we bound the gradient consensus error given by term Σx= El|s! Dr.e1l?.
Lemma 9. For i 2 1 and a; < 1, we have:
K
K
8KIo2 2KIOzennt..
E El (8) - 01,111 S (1 + 7
E
T - D7,5
+ f.
b
16
16KIC2 &
11,
E| (R) U.
1r
k=1
where the expectation is w.t.. the stochasticity of the algorithm.
v/ (k) (we omit the global epoch step for convenience), we have:
Proof. By the update rule of
E
(k) 12
E
V (k)
(1. 1 1k!b)) (k)
(k)
+ (1 (1- (u V (z :z(a
K Σ v { (3))) (,
(1-1
K Σ
1
|
1=1
(1
(v(h) - ))-1) + V ((())) ())
(z) B!
K
j=1
K
- -(1-
V
(1 ((t)))){{{{)))))
1
Σ
( (1)
- (
K
j=1
$ $1+ -0.0daa)2/// 21) p 1/:-1
(k)
+ (1+
1
E
V
(o)
(c)
B,
1
V
3
K
j=1
(1- az)
( v ()( (k)
(a.))
((a)
(k)
1
K
B
?
(00)
K
where the last inequality uses Proposition
27

---

Under review as a conference paper at ICLR 2023
Next, we consider the second term:
E
V (((i)) K
(1)))
1(0))
1 K
(1) )|'
-(1 - aa)
V (x) (8) (,; (kK)
Σ
K
(a)
K
$ 2F
(1)) :B(t)))
Σ
(1))
K
ド=1
(r)
(8) B
(k))
1
(12;)))))))))
K j=1
+ 220
B(ah) (k)
1
K
v
(1) 1²
K
(6)
x 2E
(
(z) (((t)))
(+),
V )(()) (4) :1:11)))1))))
|
2
202F
4 (()
(I (1] BB(1))
V
(1)
j=1
(0)
2
x
(k)
(k)
+
2a
E
V 10) (k)
B(b))
(k))
1
Σ
K
2
(21)
K
where inequality (a) uses Proposition smoothness assumption.
inequality (b) uses Proposition 2
inequality (c) uses the
28

---

Under review as a conference paper at ICLR 2023
Next, we consider the second term in equation 21 above, we have
1 K
E
V
= =E
V
( v (z,
(1)
k
K
Σ
(1
- --)0))
v
13
(3
(
K
K
j=1
2B
(
k
Σ
(V (v (6) (x (,))
K
j=1
1 k
+ 2E
V
(1)
Σ
(x))
K
22 2F
( (b) (1) ((0)) - // (1)
+ 21
(2)
V
(
K
2
(+)) (2)
44
1) - Vf 1)
(,(ي)) 2
+ +8E|
V ( || + 8E
Vf 1) K Σ
(b) 20
4
E V (h) (1: V (
K |=1
8L2
+ 8L8 2 E 1,
1- 7.-1 11
(k)
(1)
11
K
j=1
(e) I
20
8L2
K Σ j=1
+ 4(2 + 81
112
El 1
( 1-1 - 11
(22)
b
K
where inequality (a) uses Proposition 2 inequality (b) utilizes bounded variance assumption; (c)
uses the bounded heterogeneity assumption. Finally, substituting equation 22 and equation 21 into equation 20 and sum over all K workers, we get
K
E| Bl|gAA (k) 2ill
1=1
K
11-111 + 2I. 1+ 1) K
$ (1 - (1 + B3
Σ
E
(k)
Σ
B1|a? (k)
-12)11 1|2
8) k=1
A=1
+ b,
4Ko²
1
1
a3 + +SKç
(+ (1+ 3
a + +321?2
(1+ 3
2 k
EE 10 i-1 - -1,-11?
3
I (1- + 9)
Σg
E
(b) - -1-111 2| + 2
1+ 3
E
ld 1|
k=1
k=1
4Ko2
(1+2) a3
SK32 (1+
3 a +
1
32X"
1+
1
Σ
K
E (-
(k)
112
b
3
where the second inequality uses claim 3 of the Lemma
29

---

Under review as a conference paper at ICLR 2023
Next using Lemma
2 we have:
K
K
E ( Di 1 S (1-0)) a1)
(3)
Σ
(k)
(1+
1 3
Σ
B
10 11
+
4Ko²
1+ 3
1
a + +KK²
(1+
1
ap
1i
3
32X²LLa?
(1 1
(1-1)
Σ
i-1
K
E8
E1|b
(k) - -D21? (23)
t=1
k=1
For the second term of the above inequality, we have:
K
212112-1 1+
1
E
ld
(k)
1|
B
1==1
K
d + 4KT.-1/1 (1+ 1
< 41221211 (1+
E Bl|at
[k]
Bl|dg-111
3)
i-1
3
k=1
16A2L2 -1)
1)
1
Σ
i-1
n2
K
(k) E
sell? + 4KL
n
[1 B
2²
3
where the first incquality uses Proposition and the second inequality uses Lemma above inequality back to Eq. equation 23
3
Next plug the
we have:
(R) El 1
111 s (1 (1) + 3)
E D 1-1
(R)
Di-1
+
4KKL2
(1
1 +
1 3
E
[|d;-1? 1|3
2Ko² +
1+
3)
1
ot 8KK
(1
3 a3
b
16X²L2
+ 2a (I-)
(1+
1
1-1
K
B
B 8
11
p²
8=1
k=1
1
8KI02 12
s (1+ +
Σ
E (K)
11-1
+ 1KKKK'' 1/ El Bld
11 +
7
1=1
16
i-1
K
+ 16K1
Bllb
(N) - 1El12
0²
t=1
k=1
In the last inequality, we choose , = 1/T, then we have (1 + 1/5) < (1 + 1) S 2T, we also use the fact that (1 o:)² 1 and a; en 1 < 1. This completes the proof.
30

---

Under review as a conference paper at ICLR 2023
Lemma 10. For no 48L72, then we have
12
1-1
(
poo22
26
pK
B 1
(K)
84
P
Σ
L2
+
42I.
k=1
Proof.
By Lemma 9 (we omit the global epoch number for convenience) we have:
K
Bllugt) (+) - 2:l1 s (1 + 1 K
8KIOP
[ (2) - 1--1 2--11++KKII
SKI +
16
i-1
K
+
+ 2 1
1/
E Ellug (R) - Dell?
p²
k=
S (11 +
1 7 Σ
E V
D1-1 1111
(k)
12+
KLp
E El|d;-1 112
Kpo²c?n2
6A1
6d
K 2pp²c 1
96r2
i-1
K
1
Dell
(24)
3ALL
p
k=1
where in the second incquality, we use the condition that m S recursively from 1 to i. We have:
p
Applying equation 24
48ALE
K
KLp
8-1-1
K Kpo 2
1-1- (177)
Ellp
(8)
0.112 5
1eElddel1 +
m1
GAT
GAILbi
E=0
c2
1 i-1-8
+ 3NIL
1 1+ 1
12
i-1
1-1-E
K
1 (+77
Σ
El (K) - 1212
P
7
k=1
(0) KLp
1+
1)
1-11
Σ
Kpo Kpo?c 2
(1+1)
1 1-1
Σ n
GY1
GAI
8=0
+ 3ATT.
KpC²2²
(1+
Σ
1-1
11e
16X2
I+ (1+
1)
1
Σ 0
Σ
K
El
(k)
- 1211
P²
ビ=
(M) KLp 1-1
K Kpo 2 2
i-1
2pc
22 {-1
Σ
7e dell 2
Σ
THe
Σ m
2A1
2
ALL
2=
0
28
1-1
K
+ 12
2
B1i - 12
(25)
2=0
k=1
where inequality (a) is by the fact that 1+ 1/11 > 1 and i 1 - l $ I for i E
[1]
and E
E [[] and
inequality (b) is because that (1 + 1/T)² <.
31

---

Under review as a conference paper at ICLR 2023
Next, multiplying both sides of equation 25
by Y/s and summing over i = 1 to I:
K
KLp
Kpo c
i-1
Bll (8)
-
ddel
13
211
Ł=0
k
i-1
288
1
i-1
K
Σ
1/1
71
B1
1/
1E
XIL
p²
1=1
8=0
t=0
k=1
(a)
KLp
2A1
N/i
dell? +
Lb
+
ALL
Σ
7/
i=1
==O
1=1
==
288A2L214 p²
Σ Th
Σ
E
(K) Drll
k=1
(6)
Kpp
1-1
1:Blldd de
K Kpp
Kp²S²0²
Σ
K
Elpy
(k)
96
96
48X21212
m18
1=0
E=1
k=1
where inequality (a) uses the fact that S I and (b) uses that we choose TT- S p/(48AL13). Rearranging the terms we have:
7
mh
K
E
(k)
1112
96X212
Kp²
Σ
1-1
nEldd,1
96X2121261 48x21213
Kp'odd
KP
Σ
1=1
k=1
1=0
Multiplying 8A12 (7Kp on both sides, we have:
2
K
po²2²
R
22l12 S
Σ
BBddd +
Σ T
Kp
84X T=0
84XL2b
42XL2
k=1
1=0
This completes the proof.
9.8 PROOF OF THE MAIN CONVERGENCE THEOREM
In this subsection, we prove Theorem 5.1 and Corollary 5.7. To prove Theorem 5.1 the following theorem hold:
we firstly show
pK2/3
96X2
Theorem 9.1. Choosing the parameters as K
C
72 ALI U1 =
AL
K
48 - t 1,142 ). X > O, and choose 17s
max
(we+++T)/88
x
then we have:
X2 Ellea11
El|cb.11 1
L12
2X2L
72X214
3X212
(f(20)-8")
+
2bp² K2/3T223 0²
PTT
1
K2//3332/3
bp²T
19
14812
1
002
25²²
X
T
+
K2/372/3
x
46
+
21
log (T + 1).
Proof. By definition, we have 77
S nu
<
k//w
1/3 = pK3/3
(332/3/48XLE
/SAAL P/48ALI2, then
c= =2122
Kpd
96
+
T2K2
<
192
Kpa
and:
1
x²
1921
K2/333
192K1/3
192
chi < a
< 1, 196
K
W
2/3
Kpp
L
2/3
w
2/3
So we have 0e 1, then the conditions of Lemma
8 Lemma 10
satisfied.
32

---

Under review as a conference paper at ICLR 2023
Firstly, substitute the gradient consensus error in Lemma potential function as:
10 to Lemma
write the descent of
5p7
A
E
Elid
E
+1,
22
7
Fr+11,BBlen 11
82
2
2p 1=0
o²c²p p
T-1
1-1
pooc²
PC
T-1
+
Σ
1741, +
3
P
11 BI Blid
1,
3
16AL2b
42X
42XL2b,
21AL2
i=0
i=0
1=0
3p
11
2
13-
A
7 11 ,1,
5
2
2p
1=
pa²²
PS
1-1
+
Tr+1
8AL2b1
21AL2
(0)
1-1
A
1-1
(
ppo²
PS2
1-1
22
El
111
2p 1=0
71+1,
E
8AL2b
21AL2
M
1,5
1=0
1=0
where (a) follows from the fact that 7) S 4 I
8
P
48AL.
Suppose we denote T EI, and t = rI + for 2 0 and 2 Then we have 17 171+1,
de d1+1,1, & = + 1. In particular, we denote 77-1 = 70 for convenience.
Then we sum the above inequality for from to E 1. and get:
B tols
PT) t=0 22
Bldd
Xm Elea11 + 2p
/p0222
+
PC
Σ
3
(8L2bb
21A1?
t=
1=0
Rearranging terms, we get:
T
pTl
B||de|1
+
AnR
B 12
< El - x +
po0²2
+
PC
T-1 Σ 1==0
1/e
2X
2p
8AT2b1
21AT2
pK
E|leol?
pof²2
PC
f(0o)) -f+
+
+
mp
64AL2 170
8AL2b1
21AL2
( - [(x0) f +
Q²p
1
2C
T-1
+
64XbL2n
8ALPb
21
(26)
where (a) follows from the fact that f < gg and (b) results from application of Lemma 5 and b is the minibatch size at the first iteration.
Next for the last term of the equation
26 above, we have:
T-1 Σ
(a)
Σ
Σ " lit S 3 In
T-1 1
(27)
W
where inequality (a) above follows from the fact that we have wi and inequality (b) follows
from the application of Proposition 3
Substituting equation 27 in equation 26 multiplying both sides by 2\/ (p and using the fact that n is non- -on-inceaasing in f we have
B| E| <
2X(f(zo)= - - P
1
K3
o²c²
2c222
In(T + 1).
T 32bT.mpo
T
4h
T2
211
(28)
Now considering each term of equation
28
above separately. For the first term:
(wr + 1/3
(a)
WT
1/3
1
4
XL
(29)
T
KT
KT
K/3
oT
2/2/3T2/3
33

---

Under review as a conference paper at ICLR 2023
where inequality (a) follows from identity (z y) xx1/3 y//3 and inequality (6) follows from the definition of K and wT
Wr max
11 - #2, 320
00.3
_ 48 k
Similarly, for the second term of equation
28
we have from the definition of /Jo and 1/r
o²
48ALI
AL
o²
D
1/3
1/ T 32bL2
pT
PK2/37213
32bT,2
K
48XTT1
AL
d²
48ALI2
pT
PK2/3T2/33
32bL2
P
72X²14
32212
+
(30)
TpПT
Finally, for the last term in equation
28 above, we have from the definition of the stepsize, !).
0²
25²
+
In(T +1)
1/
L2
4b1
21
48AL12
AL
1922
0²
2²²
pT
pK2/332/33
x
Lp
x
4b
+
21
log(T (T + 1)
19
4812
0²
20
p²
T
+
K2/3T2/3
X
46
+
21
log(T + +1).
(31)
Finally, substituting the bounds obtained in equation we get
equation 30 and equation into equation
T
X² 2
Ellde
ElEe213
T
0²
1=0
LI?
2X²1
72X214
3X212
(f(20) - (r) +
P²T
K2K2/822/3
Dp2T
26p² K2/3//233
19
4
1
0²
25²1
+
K2/3T2/3
+
log(T + 1).
T
4b
21
This completes the proof of the theorem.
Now we are ready to show Theorem
5.1
Firstly notice that:
X
X2
X²
J.
112
ll+ ff())))
||
le.1
Combine with Theorem
9.1
we have:
T-1
16L12
2L
7214
312
E[G.] <
(5(ro) - -
+
T
K2/372/33
bT
2bK22/372/3
48122
022
2C
+ 1922 x
T
K2/3T2/3
x
4b
+
21
log(T + 1).
Remark 7. For the measure G., we discuss its intuition under both the unconstrained and constrained case. First, for unconstrained case, i.e. when X' = =Rd, we have:
||H, V (111) V1H;
|H; (V)+)) H Dr, + H, Dr.: S म (V((T))) - " ||,,, ||,,,''r.) 'r.sll
Dr.s vf(Er.)) + Anr. |ل E 111l /
34

---

Under review as a conference paper at ICLR 2023
In the last inequality, use Jensen inequality, and in the second last inequality, use Assumption -
and the fact that 77,1+1 = 2,,0 0 + AH, 27,1+1 and Tr,i - Στ, and Dr, = 27,1+1
in the unconstrained case. other words, we have [[;](l Σ -|| G.. Note the coefficient of the right-side an upper bound of the square condition number Hf, common assumption in the analysis of adaptive gradient methods that Hr has finite condition number Huang et al. (2021). In sum, the convergence our measure Gt means the convergence to a first order stationary point in the unconstrained case.
Next, for the constrained case, our measure upper bounds the gradient mapping 1r41, n,,, - 27 +1,1, ot is defined as follows:
1 x.) H- xr))
+1, arg min{ (< +,,1,) NEX
2X
-1e V. f( is the accumulation of true gradient. Next follow Lemma where +,, Σi= =
we have:
| 1,+1, S -1ett11-- -
X [VS((++1,) - 2++1,el
7 (V (++1,)))
where inequality (a) is due the triangle inequality. Next we have:
||,, +1,ll = ||, - I + B741,5 +1,1l S ||,, - -r+1,il+ + | x1-1
dل + | -
[drtzelll + AB V [f - Br+t,ell
P
1=0
By Jensen inequality and the definition of the measure equation
we have
||dell + A
V2 Vor.
(V))) all S
P
So we have
+lll S
V2X
Brt1l Br+1a
2/21 i-1 /9+11 S
7.
P
1=0
the last inequality is because of Eq. equation 17 In all, when the measure Gr+1, 0, the gradient mapping n-.... ||,, +1,ll converges to O.
Corollary With the exper-parameters chosen as in Theorem 9.1 Suppose we set 1= O(TT/K3)1/6
and use sample minibatch of size O(I2) in the first step, Then we have:
E 0 ( [(x0)) -
+ +0
+ Ō
K2/3T2/33
K2/3T2/3
K2/37213
and to reach an c-stationary point, we need to make Ó(c-1.5 (c) number of steps and need (c-1) number of communication rounds.
Proof. is straightforward to verify the expression for ElG.] in the corollary by applying Theorem 9.1 and choosing and b as corresponding values. As for the gradient and communication complexity of the algorithm. We have the following results: The number of total steps T' needed achieve an e-stationary point, i.e. ((77))77)))
are O x ), i.e. the gradient complexity. Total rounds of 1, as we have = O(T/K33) then T/I = -((K/877//6) Assume we have large number of clients compared, more specifically, assume K 2 vT. Then we have T/I = ((K1/3756/) = 2 in other words, we have E = Ō This completes the proof of the corollary.
communication steps to achieve an c-stationary point is E = T/I,
35


Reviews:
[{"review_id": "uwW1JzsgN9F", "reviewer": "Reviewer_M1w3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 proposes FedDA, which is a federated learning algorithm that uses adaptive gradient and local steps. Different from the previous work, this paper supports the clients to run the adaptive gradient locally and update the global model using dual averaging - average the gradient information in the dual space. Theoretical analysis shows the effectiveness of the method, and numerical experiments are presented to corroborate the theoretical findings.", "summary_of_the_review": "Although there are some weaknesses, I still think that the contribution is enough and I would like to weakly accept this paper.\n\nAfter rebuttal:\nI still vote for weak accept of this paper.", "strength_and_weaknesses": "Strength:\n\n1. Introduce a new federated learning algorithm that combines adaptive gradient and local steps\n2. The proposed algorithm supports the clients to use adaptive gradient because it averages the gradient information in the dual space\n3. The theory looks good, since it has the $1/T$ communication round.\n4. Numerical experiments corroborate the theoretical findings.\n\nWeakness:\n\n1. For theory, it needs the bounded dissimilarity assumption, which is a huge drawback for federated learning scenarios but it is acceptable for the analysis of adaptive gradient methods.\n2. In the numerical experiment, current discussion cannot conclude that FEMNIST experiment is heterogeneous. It is not clear how you split the data to client: if you have 500 clients and each client has the data of a single person, then maybe you can say it is heterogeneous. If you only has 10 clients and each client random get 50 people's data, then maybe it is not heterogeneous enough.\n3. To me, more ablation studies/numerical experiments on the effectiveness of the local steps are needed, e.g., compare the difference between $I=1$ and $I=5$ and $I=50$ etc.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ms6emNrNUR", "reviewer": "Reviewer_pitV", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 papers proposes a meta algorithm for the federated learning optimization problem with heterogeneous data. This algorithm uses adaptive learning rates. The authors view the adaptive methods from the point of view of mirror descent: the proposed algorithm ressembles a Federated mirror descent algorithm where the clients perform several steps and the central server aggregates the dual vectors. The proposed algorithm has some flexibility in the way the gradients are computed. When the gradient are variance reduced and some momentum is introduced (algo FedDA-MVR), the authors show a gradient complexity 1/eps^1.5 and communication complexity 1/eps for the resulting adaptive method to find an eps stationary point.", "summary_of_the_review": "Good theory contribution which fits well with ICLR and the practice of Federated Learning", "strength_and_weaknesses": "Strength\n\n- While this is a theory paper, the authors provide numerical evidence for the effectiveness of FedDA-MVR in a ML context\n\n-The paper is clearly written and fits with ICLR in terms of topic (adaptive gradient methods for FL) and format (one algo, one clear theorem with a clear contribution and some numerical exp)\n\n-I didn't check the proofs, but the main theorem and its Lyapunov approach seem reasonable.\n\nWeaknesses\n\n-Why do we need to assume the variance of the gradient bounded if we use variance reduction later on?\n\n-It seems that the theory only cover the case of minimization over a compact set. \n\n\n\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jxqNXCvvsEN", "reviewer": "Reviewer_rANd", "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": "The authors have considered the standard problem of federated learning (FL) and proposed an adaptive gradient method to solve the problem. The paper is written and theoretical convergence analysis is provided for the proposed approach. The experimental results are also mentioned to further support the claims. My main comments are provided below. ", "summary_of_the_review": "Please refer to the weakness mentioned above. ", "strength_and_weaknesses": "*Strengths*\n\nThe paper is well written. The theoretical analysis is well done and experimental results are detailed. \n\n*Weakness*\n\n- My main concern is regarding the motivation. If the eventual convergence rate is similar to other wxisting works, then what is the additional benefit to consider this approach?  The experimental gain alone is also not significant enough. And that too coming at the cost of added computatinal complexity at the device to perform argmin operation. \n\n- Also, it seems the comparison to FedAvg is also not fair because the proposed algorithm requires to share some gradient information with the server, which is not needed in FedAvg. How to incorporate that fact during the comparisons? Also, isn't that against the spirit of federated learning in general to share the gradient information with the server? \n\n- The dual state is not defined before it's use in Line 4 in the description of Algorithm 4. \n\n- Is it true that via $\\nu$, the information of global gradient is getting used for the local updates at each client? If yes, this needs to be discussed in detail. \n\n- In the proposed algorithm, because it is assumed that we can share the estimated gradients with the server, then what if we evaluate the average of these local gradients at the server, and then run the update at the server.  What is the additional benefit of running local gradient updates, except for the linear speedup?\n\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": "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": "gsPwKBpKQl", "reviewer": "Reviewer_u8LZ", "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": "The paper proposes a novel framework of adaptive gradient methods for Federated Learning. By incorporating momentum-based variance reduction techniques, the proposed method is able to achieve acceleration in computation complexity $O(\\epsilon^{-1.5})$ and communication complexity $O(\\epsilon^{-1})$. Experiments are provided to demonstrate the acceleration in practice. ", "summary_of_the_review": "The paper proposes a novel framework of adaptive gradient methods for Federated Learning. The framework is base on a dual averaging step along with Bregman proximal gradient step. By setting the Bregman distance with a quadratic mirror map, the proposed framework enables adaptive stepsizes where AdaGrad and Adam can be retrieved. The main contribution of the paper is to combine a momentum based variance reduction step in the local update to achieve faster computational and communication complexity. \n\n**My main concern is how exactly is the theoretical acceleration achieved? As far as I understand, the adaptiveness does not contribute to the theoretical acceleration. Moreover, I don't think the algorithm has the \"momentum-based variance reduction\" component, the equation 5 and 6 are simple average, which is neither extrapolation not variance reduction. Hence I am confused how the acceleration is achieved.**\n\nFirst, from Theorem 5.1, the analysis only requires the adaptive matrix is larger than $\\rho Id$. In other words, the acceleration does not come from the adaptive step. This is also commonly known in standard stochastic optimization literature where adaptive method has better practical performance but no theoretical improvement. Hence the theoretical acceleration is not coming from the adaptiveness. \n\nSecond, usually acceleration is achieved by extrapolation. In equation 5 and 6 where the paper claims as momentum-based variance\nreduction update, it is a simple weighted average, it is neither variance reduction nor momentum-based, see for example [1] for an example algorithm with variance reduction and dual averaging. Hence I don't fully understand how the acceleration is achieved. Please clarify this point, if possible provide some details within the simplest unconstraint case with adaptive matrix being constant i.e. $\\rho Id$. \n\n[1] Song et al, Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization\n", "strength_and_weaknesses": "Strength: \n- Theoretical strong\n\nWeakness \n- Lack of explanation on theoretical analysis \n- The experimental section can be improved, for example, include non iid experiments ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9rNGrPnPHzL", "reviewer": "Reviewer_7JLR", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 how to apply adaptive gradient methods into federated learning. Although there are many existing works in this direction, this paper brings up a very novel view. A key problem in adaptive gradients in FL is that there are too many ways to combine the model parameters and local optimizer states at different clients. The authors mentioned that most previous works do not make sense or have obvious drawbacks if we view adaptive methods as a mirror gradient descent algorithm. Instead, in this paper, the authors proposed a more theoretically meaningful framework to aggregate primal (i.e. model parameter) and dual states (i.e. gradients) separately. Under this framework, they provide convergence analysis to an instantiation with momentum-based variance reduction. Experiments on some classification datasets validate the performance of the proposed algorithm.", "summary_of_the_review": "I acknowledge that this paper makes some contribution in getting a better understanding on the adaptive federated optimization methods. But I am not convinced that the proposed framework is better than previous works, given the fact that without MVR, it only provides marginal improvements but costs 2-3x more communication. ", "strength_and_weaknesses": "Strength\n1. I really enjoy reading the introduction. I think this paper brings a very novel and important view to adaptive federated learning optimization algorithms. This provide meaningful guidance on how to combine different local optimizer states.\n2. The theoretical results are solid. It is not easy to derive the convergence guarantee for adaptive methods with momentum-based variance reduction. I appreciate the authors' efforts.\n\nWeakness\n1. While I acknowledge the theoretical contributions of this paper, I'm not very convinced that the proposed method is better than existing much simpler ones.\n    - First of all, the comparisons in figure 2 are not fair. In FedDA, clients use local momentum based variance reduction. But for other methods, clients just perform local SGD (even without local momentum for FedAdam). So it is really unclear whether the performance improvements came from momentum-based variance reduction or the new adaptive optimization framework. Although the authors presented MIME-MVR, I think this is not enough. A more convincing way is to just remove the VR part at clients and compare it with all other methods. I found these results in Appendix and actually if we compare figure 5 option 2-1/2 with other methods in figure 2, the improvements due to a better adaptive optimization framework is very marginal and even worse than FedCM. Also, this new framework comes with additional price. Compared to FedAdam, the clients need to download 3x more parameters and upload 2x more. This additional communication overhead does not appear in the experiments. Given the marginal accuracy improvement and much more additional communication, I'm not convinced that this is a better algorithm.\n    - Similar to the above point, if you want to show this is a better adaptive optimization framework, then you need to analyze it without any VR and compare it with FedAvg. Analysis of FedMVR is valuable, but it should be treated as an extension.\n    - Also, the authors missed a very simple baseline [1], where clients just run any adaptive optimizer from scratch at each round, and the server averages accumulated model changes to uses it in a server-side adaptive optimizer. This simple solution does not introduce any additional communication costs and can work with any optimizer (although not theoretically). But it is worth to discuss and compare with it to see whether the proposed method is unnecessarily complicated.\n\n[1] Wang et al. ICML 2021 workshop. \"Local Adaptivity in Federated Learning: Convergence and Consistency\"", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject