FedDA: Faster Adaptive Gradient Methods for Federated Constrained Optimization
Authors: Junyi Li
Feihu Huang
Heng Huang
Venue: ICLR 2024 poster (2024)
Keywords: Federated Learning
Adaptive Gradient Methods
Primary area: general machine learning (i.e., none of the above)

Abstract: Federated learning (FL) is an emerging learning paradigm where a set of distributed clients learns a task under the coordination of a server. The FedAvg algorithm is one of the most widely used methods in FL. In FedAvg, the learning rate is a constant rather than changing adaptively. Adaptive gradient methods have demonstrated superior performance over the constant learning rate schedules in non-distributed settings, and they have recently been adapted to FL. However, the majority of these methods are designed for unconstrained settings. Meanwhile, many crucial FL applications, like disease diagnosis and biomarker identification, often rely on constrained formulations such as Lasso and group Lasso. It remains an open question as to whether adaptive gradient methods can be effectively applied to FL problems with constrains. In this work, we introduce \textbf{FedDA}, a novel adaptive gradient framework for FL. This framework utilizes a restarted dual averaging technique and is compatible with a range of gradient estimation methods and adaptive learning rate schedules.  Specifically, an instantiation of our framework FedDA-MVR achieves sample complexity $\tilde{O}(K^{-1}\epsilon^{-1.5})$ and communication complexity $\tilde{O}(K^{-0.25}\epsilon^{-1.25})$ for finding a stationary point $\epsilon$ in the constrained setting with $K$ be the number of clients. We conduct experiments over both constrained and unconstrained tasks to confirm the effectiveness of our approach.

Published as a conference paper at ICLR 2024
FEDDA: FASTER ADAPTIVE GRADIENT METHODS FOR FEDERATED CONSTRAINED OPTIMIZATION
Junyi Li
Feihu Huang
Department of Computer Science University of Maryland College Park College Park, MD 20742 junyili. ai 1000mmmalll.. com
Electrical and Computer Engineering University of Pittsburgh
Pittsburgh, PA 15261
huangfeihu200 01 80 com
Heng Huang"
Department of Computer Science
University of Maryland College Park
College Park, MD 20742
henghuanghh&@mal com
ABSTRACT
Federated learning (FL) is an emerging learning paradigm where set distributed clients learns a task under the coordination of server. The FedAvg algorithm is one of the most widely used methods FL. In FedAvg, the learning rate is a constant rather than changing adaptively. Adaptive gradient methods have demonstrated superior performance over the constant learning rate schedules in non-distributed settings, and they have recently been adapted to FL. However, the majority of these methods are designed for unconstrained settings. Meanwhile, many crucial FL applications, like disease diagnosis and biomarker identification, often rely on constrained formulations such as Lasso and group Lasso. It remains an open question as whether adaptive gradient methods can be effectively applied to FL problems with constrains. In this work, we introduce FedDA, a novel adaptive gradient framework for FI.. This framework utilizes a restarted dual averaging tech- nique and is compatible with range of gradient estimation methods and adaptive learning rate schedules. Specifically, an instantiation of our framework FedDA- MVR achieves sample complexity OKK-1, and communication complexity Ō(K -0.25 c for finding a stationary point e in the constrained setting with K be the number of clients. We conduct experiments over both constrained and unconstrained tasks to confirm the effectiveness of our approach.
INTRODUCTION
As an emerging machine learning technique, federated learning (FL) has recently been applied to many important health and biomedicine applications (Moshawrab et al., 2023) Joshi et al. [022]] Antunes et al., 22022 Xu et al. [2021a] Rahman et al. 2022). The FL enables big data analyses in healthcare (especially for rare diseases) via allowing set of distributed located hospitals, medical centers, insurance companies, etc., jointly perform machine learning task under the coordination of a central server over their privately-het held data. For example, in a recent FL study, the data from 71 sites across 6 continents used generate automatic tumor boundary detector for the rare disease of glioblastoma (Pati et al. 2022). Among these FI. healthcare applications, federated biomarker identification (Sheller et al. 2020 is one of the most important learning tasks help researchers and clinicians detect informative biomarkers from distributed biomedical datasets to understand the underlying disease mechanisms, diagnose disease earlier, and design drugs. Different to prediction tasks, the federated biomarker identification often utilizes the constrained formulations, such as Lasso and group Lasso, which often requires specific optimization solvers.
"Tiis work was partially supported by NSF IIS 2347592, 2347604, 2348159, 2348169, DBT 2405416, CCF 2348306, CNS 2347617.

---

Published as a conference paper at ICLR 2024
Table 1:
Comparisons of representative Federated Learning algorithms for finding an e- stationary point of equation 1 i.e. [=)] S E or its equivalent variants. Golf, e) denotes the number of gradient queries w. w.r.t. f(k) (x) for k E [K]; Cc(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.
Type
Algorithm
Gd
Coffe)
State
Local-Adaptive
Constrained
EsdAAgg/MMMaaa et al
OUR
Ole OLK-L-3 oix- Ole-la) Oi
FrimalDual Dual
FedDualAyg Your Clala
0
Non-adaptive
FedCM Xu a
1021b
0ix-1-2)
Primal/Dal
FelGL ch
200
OrK-n5,-
Primal)Dual
STEM STEM/Kanninn Khandiri of
X121
O1K-ir11
Primal/Dull
FedAdam Redili
2020
O1K-1,-
OfN (1y1-
Primal
Adaptive
Local-AMSGra all
20/06]
OiK D(K-2,23
O OCK-uap-1ny
Primal
MIME-MVR K Karhminskl di al
Primal
FAFED Wu al 2122
O1X c.5)
Oie"
Primal
FodDAA-MYYR OOu((
O1K-1-10)
0(K-020,1130
Dual
A widely used method in Federated Learning (FL.) is the FedAvg (Local-SGDD algorithm (McMahan
et al. 2017). As indicated by its name, FedAvg performs (stochastic) gradient descent steps on each
client and averages local states periodically. Recently, researchers incorporated adaptive gradient methods to the FL setting (Reddi et al.) [2200] KKrrmireddy et al., 2020a; Chen et al., 2022bb) to accelerate FedAvg. For instance, Reddi et al. (2016) introduced FedAdam, which incorporates the Adam optimizer for server updates; Karimireddy et al. (2020a) proposed MIME, which supports adaptive gradients in local updates. These adaptive gradient methods have demonstrated significant performance enhancements compared to FedAvg. However, these methods are designed for the unconstrained setting and cannot be directly applied over the constrained formulations in the biomarker identification tasks. In fact, FL problems with constraints remain under-explored in the literature. In Yuan et al. 202T), authors proposed FedDualAvg to solve FL problems with non- smooth regularizers. In FedDualAvg, model parameters are transformed into a dual space using a map determined by the regularizer. Averaging is then conducted in this dual space across all clients. FedDualAvg can be used to solve federated constrained optimization problems when regularizers are indicator functions defined over the constraints set. However, FedDualAvg uses constant learning rate as FedAvg, thus suffers the same slow convergence rate. In fact, it is an open question if adaptive learning rates can be used to accelerate the solving federated constrained optimizations.
In this work, we propose the Federated Dual-averaging Adaptive-gradien (FedDA). a general adaptive gradient framework for federated constrained optimization. FedDA is based on the dynamic mirror descent view of adaptive gradients (Huang et al. 202I). In fact, suppose we have an adaptive matrix such that it is diagonal and its 4 diagonal element represents the adaptive gradient for the ieh coordinate of the model parameter. Then if we view the parameter space as the primal space and the matrix as a linear mirror map, the adaptive gradient update step is equivalent to a mirror descent update step. Since adaptive gradients are updated at each iteration, the mirror map H is also dynamic. Our FedDA is inspired by this mirror descent view of adaptive gradients.
In FedDA, the server maintains the global adaptive matrix and the global model weight. In each epoch, each client receives the current global adaptive matrix and global model weight. Then performs multiple steps of dual--verrging' style mirror descent (Nesterov) 2009). More specifically, the client aggregates dual states, and only recover model weight (primal states) through the adaptive matrix (mirror map) when the gradient query is needed. Note that the adaptive matrix is fixed during local updates. After local updates, the server averages the dual states and then updates the global primal state and the adaptive matrix. There are two important characteristics of FedDA. Firstly, we fix the adaptive matrix during local updates to makes sure that all clients share the same dual space. Secondly, the aggregation and averaging is performed in the dual space instead of the primal space. In fact, in the constrained case, the mapping from dual space to the primal space involves the non-linear projection operation. Although averaging dual states leads to an unbiased estimate of the global gradient, averaging primal states leads to biased estimation due to projection. In summary, FedDA adopts the restarted aver-ingg strategy, where the adaptive matrix (mirror map) is refreshed at each global epoch and clients perform dual averaging locally with fixed mirror map. Our FedDA is a general framework: is flexible to the choices of adaptive gradient methods and also can combine with various gradient estimation methods. Furthermore, although it is designed for the constrained
2

---

Published as a conference paper at ICLR 2024
case, FedDA works well in the unconstrained FL setting too. We highlight our contribution as follows:
(i) We propose FedDA, a fast adaptive gradient framework for constrained federated opti- mization problems. The framework is based a restarted dual averaging technique and incorporates large family of adaptive gradient methods.
(ii) FedDA-MVR, instantiation of our framework, obtains the sample complexity of ((K-1_115) and communication complexity of O(K-0.2x-1.26) The iteration com- plexity matches the optimal rate of non-adaptive federated algorithms. FedDA-MVR uses the momentum-based variance-reduction gradient estimation, and exponential moving average of the gradient square as adaptive learning rates.
(iii We empirically verify the efficacy of the FedDA in solving biomarker identification tasks: the colorrectal cancer prediction task and the splice site detection task. Furthermore, we also verify the efficacy of FedDA over non-constrained FL tasks through classification tasks over CIFAR-10 and FEMNIST datasets.
Notations. (x)) denotes the first-order derivatives of the function f(x) w.E. variable x.. & denotes a random sample and f {) is the stochastic estimate f(x). O(-) is the big O notation, and Ó(.) hides logarithmic terms. Ia denotes a d-dimensional identity matrix. Diag(x) denotes the matrix whose diagonal is the vector || denotes the l norm for vectors and the spectral norm for matrices, respectively. (:: denotes the Fuclidean inner product. [K] denotes the set of {1, 2, .... K}. For random variable X, E[X] denotes its expectation.
RELATED WORKS
Federated Learning (McMahan et al., 2017) defines the task to learn from set of distributed located clients under the coordination of a server. McMahan et al. (2017) proposed the FedAvg algorithm where each client performs multiple steps of gradient descent with its local data and then sends the updated model to the server for averaging. The FedAvg algorithm resembles the Local- general distributed setting for longer time (Mangasarian & Solodov] 1993). The convergence of the local-SGD method has been heavily analyzed in the literature (Stich 2018 Karimireddy et al. 2019 Dieuleveut & Patel 2019 Khaled et al. 2020 Yu
Federated Learning.
SGD algorithm, which is studied in
et al. 2019 Woodworth et al.) 2020) Woodworth 2021 Glasgow et al. [022]. Various acceleration
methods of FedAvg are considered and we list few representatives here. Karimireddy 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 used to correct the bias of local gradients. Karimireddy et al. (2020a) proposed general framework (MIME) to translate centralized optimizer into the FL. setting, including adaptive gradient methods. In Das et al. (2020); Khanduri al. (2021a), momentum-based variance reduction is applied to the FL setting to control the noise of the stochastic gradients. In Das et al. (2020), server momentum state and client momentum state are maintained, while in Khanduri et al. (2021b), a momentum state and is matinained the momentum 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 used to update the states of the adaptive gradient methods. [Tong al. (2020); Wang let al. (2022) extend the method in Reddi et al. (2020) to include the AMSGrad method. In Chen al. 2020b), the authors first showed the divergence of a naive local AMSGrad method that directly averages the primal states periodically. The authors then proposed Local-AMSGrad,, method in which clients update adaptive learning rates locally and average at the synchronization step. At the server average step, both primal states and local adaptive learning rates are averaged to replace the old states. More recently/[Chen [Cen et al. (2020b); Wu et al. (2022) proposed to use fixed adaptive learning rates locally. Finally, another line of research Tang al. (2020) (02T): : Lu et al. (2022); 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. All these methods study federated adaptive methods in the unconstrained case. For solving problems with constraint in FL, related work is (Yuan et al. 2021), where authors propose a modified local-SGD method based on the averaiiggg,ng, however, it does not support the adaptive gradient methods.
3

---

Published as a conference paper at ICLR 2024
Adaptive Gradients in the Non-distributed Learning. Adaptive gradient methods widely used in the non-distributed machine learning setting. Adagrad Duchi et al. (201T) was one of the the first adaptive gradient method proposed in literature, and was shown to 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 are proposed, such SC-Adagra (Mukkamala & Hein (017) and S SAdagrad (Chen et al. 201 Furthermore, Adam (Kingma & Ba 2014) and YOGI (Zaheer al. 2018) proposed use the exponential moving average instead of the arithmetic average used in Adagrad. Adam/YOGi is widely used 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 in information to handle the convergence issue of Adam. The convergence of Adam-type methods is also studied in the literature (Chen et al. 2019. /hhou et al. 2018: Liu et al. 2019 Guo et al., [2021] Huang et al., 202I). Adaptive gradient methods with good generalization performance are also proposed, such as AdamW (Loshchilov & Hutter [0188), Padam (Chen et al.)
2018a). Adabound (Luo et al. 2019)). Adabelief (Zhuang et al. 2020) and AaGrad-Norm (Ward et al.
2019)
PRELIMINARIES
In this section, we introduce some preliminaries. We consider the following formulation of Federated Learning (FL) with K clients:
1 {16) = K min REXCRd
K Σ k=1
(x) = Bon (x: (x))))))))
(I)
For the kis client, we optimize the loss objective (xx : X + which smooth and possibly
non-convex, and x denotes the variable of interest. X C Rd is a compact and convex set. g(k) (())
a random example that follows an unknown data distribution D(k), The formulation in equation 1
includes both the homogeneous case iee. ((8) (1r) (x)) for any j,j E [K], and the heterogeneous
case Lee. y(k (xx) * f())()) for some j. E [K].
Next, we introduce some basics of adaptive gradient methods from a mirror-descen perspective. Generally, mirror descent is associated with mirror map ((z). Given the objective fax) and the primal state Te E X' at 4h step, we first map the primal state to the mirror space via the mirror map Yt ())())) then we perform the gradient descent step in the mirror space: Vi+1 Yt f(x), where 17 is the learning rate, finally, we map yt+1 back to the primal space as Iz+1 = argmin min D4 ē2+1), where yt+1 (f2++)) and D4 (xr denotes the Bregman Divergence #EX
associated Φ: (1 v) F(x) - (v) (v)) x - v). Equivalently, the mirror descent step can also be written as a Bregman proximal gradient step as follows: Z1+1 = arg min 17( V fzx), x) xeX
D& (xr xt). For the adaptive gradient methods, we uses the following mirror map: (xx) f Ha, where H is a positive definite adaptive matrix. Many adaptive gradient methods can be written in the following proximal gradient descent form:
1 T++1 = arg min 17(,,, xT) 2 x1) Hr - xz)),
aEX
we replace the gradient (xx with the generalized gradient estimation vs, besides, we replace Hl with H, based on the fact that the adaptive matrix is 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. 2011) method, we set
vt = V Vf(a,,))) He = Diag(VPi). b =
(3)
t
i=1
For Adam (Kingma & Ba 2014 we have:
0: = - (1= + 31 fit (1 V5 (,)2+ 3201-1
1/2 = 71), Me fa. -0), H, Diag(VHi +c)
(4)
where 31,82 71, 72 are some constants.
4

---

Published as a conference paper at ICLR 2024
Algorithm FedDA-Server
1: Input: Number of global epochs E, size of the first mini-batch 61, tuning parameters {3, )
2: Initialize: Choose zo E X and each client selects a mini-batch samples B8¹²) of size 61 to evaluate V f (z.. B)
(=) locally and the server averages local gradients to compute 1/;
3: for
E do
4: for the client k E [K] in parallel do
5: (2,+1,1 n. (R)
7-1.1 PredDA-clientt(e Vy. H,)
6: end for
7: Compute 2++1 K k= 7+1,11
E
(k)
8: Compute 4++1 arg min (x, 2r+1) 1 x,, xr) }: TEA
9: Compute 1-- K
E
(R)
H++1
++1,1
10: end for
Algorithm FedDA-Client (Iy, Mr, H,)
1: Input: Number of local steps I, mini-batch size tuning parameters (Mr+1a) 1/11
far+ndles
(k) 2: Initialize: x 1,0 = Fri
(k)
r+10 = Uri =+ O;
3: for i = 0 to I
do
4: Compute (k)
711, 1 (R)
(k)
5: Compute (k)
7+1,+1 arg min (I, 2
(k)
+ f 100--771.00 27,1,0) H, -2-2
2f41,0)
NEX
6: Compute 7+1,1+1 = ((v+() 7 7+1.+1 7+1
(k)
11+1,1+1 +,,60 (k)
(k)
7+1,141); where ((k)
7+1,141 is
minibatch of size b of random samples from the client k;
7: end for
8: Output: Send 1,,1 771, to the server
4 LOCAL ADAPTIVE GRADIENTS VIA DUAL AVERAGING
In this section, we introduce FedDA, a fast adaptive gradient framework for federated constrainted optimization problems. The procedure FedDA is summarized Algorithm Algorithm we perform E global steps and at each global step, every client runs Algorithm 2
In Algorithm 2, clients receive the current model weight Zy, gradient estimation M4 and adaptive gradient matrix Hr, The clients then perform / local training steps: line 3- line 7 in Algorithm 2
For each step, we first accumulate the dual state in the variable 2(6) (line 4), then we calculate the
2 The function of this step map the aggregated dual state -,, back to the primal space, and we use the primal
local primal state - (line 5), which is proximal gradient step similar to equation
state query the gradient to update the estimation the gradient (k)) (line 6). Note that we use fixed adaptive matrix H, during local steps, this makes the clients share the same dual space. In line
of Algorithm 2 we update the gradient estimation (k) The update rule u(.) general, ghe
momentum-baas variance reduction update equation 5 and the momentum update equation 6 as follows (a,,, is momentum coefficient):
(M) 77111-1
V (()) (a(()
(K) (1 B (k)
1 + (141)14)(11))) (x)
((k)
(+1,41)
(5)
and
M++1,441 0r41.i4 (x)
(k)
(1 (41,04) + (1 0.41. 1)
(k)
(k)
(6)
After the client finishes Algorithm it returns the aggregated local dual states 2741,7 and the local gradient estimation y (k)
741, the server. The server first averages the local dual states (line 8 of
5

---

Published as a conference paper at ICLR 2024
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 1++1 1 as in line 9 of Algorithm I Next, the gradient estimation V4 is also updated by averaging local gradient estimates (line 9 of Algorithm Finally, we update the adaptive matrix H, (line 9 of Algorithm The update rule V is general, e.g.
M++1 PT 2 / + (1 BT+1) H7+1 = Ding( BBag(V/=s VPr +
and
(8) where we set An = 0, is some constant. In summary, Algorithm| aggreggtes and averages dual states each global round. The adaptive matrix H, is fixed during local updates and is refreshed on the server side at each global round. Since the algorithm uses a new mirror map (adaptive gradient matrix) at each global round, we name the strategy as restarted dual averaging.
M++ = 9-+1||2++1111 1 + (1 Br+1) )),, H = (1++1 + 6)
Remark 4.1. A notable characteristic of FedDA is the dual-averaging strategy in local updates. this contrasts with the 'primal averaging' strategy used by many existing adaptive FL algorithms (Karim ireddy et al., 2020a). In fact, dual-averaging is essential for FedDA solve federated constrained optimization problems, due to the fact that primal and dual states are connected through non-linear mapping (i.e. the projection operation).
Remark 4.2. By choosing different update rules and V, we can create many variants FedDA.
An representative is FedDA-MVR, in which we update V with momentum-biee based variance reduc- tion equation 5) and the adaptive matrix H, with an exponential average of the gradient square ( eqquatinn?) 77
Remark 4.3. The argmin operation in line 8 of Algorithm [ (line 5 of Algorithm 2 does not lead to extra computational cost. We solve it through two steps: solving the quadratic optimization problem (a generalized adaptive gradient step) and projection. The projection is necessary to make the solution feasible and for many constraints, the proximal operators are well defined.
THEORETICAL ANALYSIS
In this section, we provide the theoretical analysis of our FedDA. More specifically, we focus on the analysis of FedDA-MVR. We first state the assumptions we need in our analysis:
5.1 SOME MILD ASSUMPTIONS
Assumption 5.1 (Bounded Client Heterogeneity). The difference of gradients between different workers are bounded: V| (Ae) (x) - (z) <² Vk, E [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 FL Algorithms, such in Khanduri et al.
a02 Das et al. (2020).
Assumption 5.2. The function ff (z)) is bounded from below in X, i... f inf f(x).
Assumption 5.3 (Unbiased and founded-varianee Stochastic Gradient). The stochastic gradients are unbiased with bounded variance, i.c. E E (æ; {()))] = f (x) and there exists a constant such that (())
(2; (())) v (()) (x) 1 o2 V ((k) D(k), v K [K]
Assumption 5.2 guarantees the feasibility of the Federated I Learning problem equation I and As- sumption 5.3 is widely used stochastic optimization analysis.
Assumption 5.4. The adaptive matrix H, is symmetric positive definite, i.c. there exists a constant p > such that H,, 2 pla 0, Vt 2 1,
In our analysis, we assume the adaptive matrix is 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 4 To make it positive, we can add bias term such as in the Adam update rule equation
Assumption 5.5 (Sample Gradient Lipschitz Smoothness). The stochastic functions ((8 (x. g()))
with g(k) Dik) for all k E [K]. satisfy the mean squared smoothness property, i.e, we have E (x; (()) v ( (y: g (k) M12 T.2 T.2 v/l2 for all xr y E T

---

Published as a conference paper at ICLR 2024
The smoothness assumption above is slightly stronger requirement than the standard smooth condition, but this assumption is widely used the analysis of variance reduction methods, such as SPIDER Fang et al. (2018) and STORM (Cukkosky & Orabona 2019).
5.2 CONVERGENCE PROPERTY FEDDA-MVR
In this subsection, we study the convergence property of our FedDA-MVR variant. For convenience of discussion, we redefine the subscript -/ + i.c. we denote the /. step as the local step in the r global round. Similarly, we denote the total number of running steps as T ET. We analyze our algorithm through the following measure:
G. = 0 J 2141 1| f((.a))
(9)
where v, denotes the average gradient estimation the t.p step and V, denotes the virtual global primal state at the lad step (see Section B.2 in the appendix for formal definitions). In Remark B.18 of the appendix, we discuss the intuition of the measure Gr. particular, in the unconstrained case i.e. when X' Rd the measure upper- bounds the square norm of the gradient. Therefore, the convergence our measure G. means the convergence to first-order stationary point. Now, we are ready provide the main result of our convergence theorem.
Theorem 5.6. In Algorithm 1 given the parameter O and choose learning rate T) (wi+t+iju7 the
pk3/3 L.c= K
96L2
L2o.5.
m2 48.48/1 1 K3.5,, bi 2 1, 1,
momentum coefficient an cnt, the adaptive gradient coefficient Br and the mini-batch size of by for the first iteration and for other iterations, then we have:
T
96LKu.5
2L
72KI
3K
B|G.] <
(f(zo) - -
+
0²
T 1=0
T
K2/372/3
bi
2b
K2/312/3
4.. 12
o²
2ç²
+922
T
K2/3T2/3
x
21
log(T + +
Note, by choosing a proper value of local updates / and using minibatch of samples for the first iteration to decrease the noise, our result matches the best known convergence rate for stochastic federated gradient methods (Khanduri et al., 2021a),, i.e. our algorithms has sample complexity of ((55).)) with linear speed up w.r. the number of clients K. More formally, we have:
Corollary 5.7. Suppose in Algorithm 7 we set ((TT/K35))/6) and use sample minibatch of size 12) in the initialization, then have: + E[Go] -((K-2/3-22/3)
and to reach an e-stationary point, we need to make -1- number of steps and need -0250.25
number of communication rounds.
FedDA-MVR achieves iteration complexity O(K -1-5511 which matches the optimal rates of non-convex stochastic optimization (Arjevani et al., 2019). In contrast, FedDu- alAvg Yuan et (021 shows the convergence rate of O(c 2) for the general non-convex objective under the strong bounded gradient assumption. Our FedDA-MVR achieves faster convergence rate and does not require the bounded gradient assumption. As for the communication complexity, we reach Ö(K -0.25 -1.25 Some methods achieve O communication rate such as STEM (Khan duri et al., 2 and FAFED (Wu et al.) 2022). However, STEM does not consider the adaptive gradient methods nor the constrained setting; FAFED considers the adaptive gradient methods, but requires the strong assumption of bounded gradient and only considers the unconstrained setting.
As shown by Corollary 5.7
EXPERIMENTS
In this section, perform experiments to verify the efficacy of our proposed FedDA federated biomarker identification task and the general classification tasks. More specifically, we consider the variant of FedDA-MVR here, and defer experiments for other variants to Section A of the appendix.
7

---

Published as a conference paper at ICLR 2024
Number
of
Namber
Figure I: Results for the PATHMNIST Yang et al. (2021) dataset. Plots show the Train Accuracy, Test Accuracy, Density of Model parameters vs Number of Rounds (E in Algorithm [ respectively. The post-fix of L1 means the L1 constraints. Number local steps is chosen as
Namner Rinandds
Figure 2: Results for the MEMset Donar Dataset Meier et al. (2008). Plots show the Train Loss, Train Accuracy and the Pearson Correlation Coefficient (between prediction and targets). The post-fix of Li means L1 constraints and GL means Group Lasso constraints. Number of local steps / is 5.
We consider three sets of experiments: Colorrectal Cancer Survival Prediction, Splice Site Detection and general multiclass image classification task. All experiments are run machine with an Intel Xeon Gold 6248 CPU and 4 Nvidia Tesla V100 GPUs. The code written in Pytorch, We simulate the Federated Learning environment through the Pytorch. dootrh.distributed package.
6.1 COLORRECTAL CANCER SURVIVAL PREDICTION WITH BIOMARKER IDENTIFICATION
In this subsection, we consider colorrectal cancer prediction task on the PATHMNIST dataset (Yang) ctt al. 2021; Kather et al. 2019). which contains diffcrent classes and 89996 training images. We equally randomly split the training set into 10 clients. We use the original test set for the metric. In this task, we impose the L1 sparsity constraint to identify biomarkers. We compare with the following baselines: FedAvg (McMahan et al. 2017) and FedDualAvg (Yuan al. 2021). For our FedDA-MVR, we train with and without the L2 constraint.
The results are summarized in Figure [ the plots averaged over 5 independent runs and then smoothed. In Figure I FedDualAvg and FedDA--MYR-A consider the T., constraint, while FedAvg and FedDA-MVR do not. We show results of Train/Test Accuracy and also the number of non-zero (below threshold) elements in the parameter (the rightmost plot in Figure [ As shown in the plots, FedDA-MVR-Ly outperforms unconstrained FedDA-MV in all metrics, particular, FedDA learns much sparser model and therefore can better identify important factors for cancer survival than other methods. Furthermore, FedDA-Mi metrics. This shows that our algorithm can effectively exploit adaptive gradient information in the constrained case. For more details of this experiment, please refer to Section A. of the appendix.
L1 also outperforms FedAvg and FedDualAvg in all
6.2 SPLICE SITE DETECTION WITH BIOMARKER IDENTIFICATION
In this subsection, we consider splice site detection task on the MEMset Donar Dataset (Meier et al.) 2008). Splice sites are the regions between coding (exons) and non-coding (introns) DNA segments. Splice site detection plays an important role in gene finding. We follow the train/test split (Meier) al.) 2008) and then randomly split the training set to 10 clients. Group Lasso is widely used to solve the splice site detection problem, so we use FedDA-M experiments. For the baselines, compare with FedAvg (McMahan al., 2017). FedDualAvg Yuan et al. (2021) and FedDA-MVR without constraints. For FedDualAvg, we consider the L₁ constraint and Group Lasso constraint.
with the Group Lasso constraint in the
The results are summarized in Figure 2 the plots are averaged over independent runs and then smoothed. As shown in the plots, FedDA-MVR--O outperforms unconstrained FedDA-MVR and
8

---

Published as a conference paper at ICLR 2024
11
Homber bouec)
Figure 3: Results for (Homogeneous) CIFARIO dataset (Top) and FEMNIST (Bottom). From left to right, we show Train Loss, Train Accuracy, Test Loss, Test Accuracy w.zf the number of rounds (E in Algorithm [] respectively. I is chosen as 5.
FedDA-MVR-Lj. In fact, feature groups. Furthermore, FedDA-MVR- also outperforms FedAvg and Avd Avg--uG (FedDualAvg-A L1). This shows that our algorithm can effectively exploit acceleration of adaptive gradients. For more details of this experiment, please refer to Section A.I of the appendix.
-VRR-GL gets better performance by identifying meaningful
6.3 IMAGE CLASSIFICATION TASK WITH CIFARIO AND FEMNIST
FedDA is general framework for FL and also solve unconstrained tasks. In this subsection, we consider an unconstrained image classification task. More specifically, we consider two datasets: CIFARIO KKizhevsky et 2009) and FEMNIST (Caldas al. 2018). We construct both homo- geneous and heterogencous cases based on CIFAR IO. For the homogeneous case, we uniformly randomly distribute them into 10 clients and for the heterogeneous case, we create imbalanced class distribution among clients (please see Appendix A.3). FEMNIST is a Federated dataset of hand-written digits; contains hand-written digits of 3550 users. Data distribution FEMNIST heterogeneous for different writing styles of people. We compare our method with following baselines:
non-adaptive methods: FedAvg (McMahan et al.) a (017). FedCM (Xu et al. 2021b), STEM (Khanduri
al. 202 la) and adaptive methods: FedAdam (Reddi et al. 2020). Local-Adap (Wang et al. 2021
Local AMSGrad (Chen et al. 20205). HIME-MVE (Karimireddy et al. 2020a).
For all methods, tune their hyper-parameters find the best setting. The results are summarized in Figure 3] the plots are averaged over runs and then smoothed. As shown the figures, our FedDA- MVR outperforms all baselines. 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-basee variance reduction technique, but it fixes all optimizer states during local updates, in contrast, only fix the adaptive matrix but update the momentum (+ k [K] every step. For the full set of experiments, please refer to Section A. 1 and A.2 of the appendix.
CONCLUSION
In this paper, we proposed FedDA, an adaptive gradient framework for federated constrained opti- mization. FedDA incorporates various adaptive gradients and momentum- -basd acceleration methods. More specifically, we adopt the Mirror Descent view of adaptive gradients and propose to maintain and average the dual states in the training, meanwhile we fix the adaptive matrix during local training such that the dual spaces aligned among clients. We also analyze the convergence property of our Framework: for the variant FedDA-MVR, we proved that it reaches an e-optimal stationary point with Ō(K ( gradient queries and Ō(K 20 1.25) communication rounds. Finally, we validate algorithm for both biomarker identification tasks and general unconstrained image classification tasks. The numerical results show the superior performance of our algorithm compared to various baseline methods.

---

Published as a conference paper at ICLR 2024
REFERENCES
Rodolfo Stoffel Antunes, Cristiano André da Costa, Ame Küderlee Imrana Abdullahi Yari, and Bjöm Eskofier. Federated learning for healthcare: Systematic review and architecture proposal. ACM Trans. Intell. Syst. Technol., 13(4). 2022.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02..0 2019.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.0109) 2018.
Congliang Chen, Li Shen, Haozhi Huang, Wei Liu, and Zhi-Quan Luo. Communication--ffiiinn 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 arXiv: 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, 2018b.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, pp. 15236-15245, 2019.
Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topeu. Faster non-convex federated learning via global and local momentum. arXiv preprint arXiv:2012.04066, 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), 2011.
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 on Artificial Intelligence and Statistics, pp. 9050000000000 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. 148400, 2021.
Feihu Huang, Junyi Li, and Heng Huang. Super-adam: Faster and universal framework of adaptive gradients. arXiv preprint arXiv:2106. 08208, 2021.
Madhura Joshi, Ankit Pal, and Malaikannan Sankarasubbu. Federated learning for healthcare domain
pipeline, applications and challenges. ACM Trans. Comput. Healthcare, 3(4), 2022.
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. 3252-3261. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2024
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 arXiv:2008. 03606, 2020a.
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 on Machine Learning, pp- 5132-5143, PMLR, 2020b.
Jakob Nikolas Kather, Johannes Krisam, Porpimol Charoentong, 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, :6 ( 1002730, 2019.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd identical and heterogeneous data. International Conference on Artificial Intelligence and Statistics, pp. 4519-4529. PMLR, 2020.
Prashant Khanduri, Pranay Sharma, Haibo 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. A 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 1rXiv:14/2.69880 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 arXiv::908.. 03265, 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:2202.06009 2022.
Liangehen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate, arXiv preprint arXiv:1902 1902.0983, 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-efffiiic learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
Lukas Meier, Sara Van De Geer, and Peter Bühhmann. The group lasso for logistic regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(1):53-71) 2008
M Moshawrab, Adda M, Bouzouane A, Ibrahim H, and Raad Reviewing federated machine learning and its use in diseases prediction. Sensors, 23(4)22112, 2023.
Mahesh Chandra Mukkamala and Matthias Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. International Conference on Machine Learning, pp. 2545-2553. PMLR, 2017.
Yurüi Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming, 122. 2009.
11

---

Published as a conference paper at ICLR 2024
S Pati, Baid U. Edwards B, al. Federated learning enables big data for rare cancer boundary detection. Nat Commun. 13(1):7346, 2022.
Rahman, Hossain MS, Muhammad G, Kundu D. Debnath T, Rahman M, Khan MSI, Tiwari P. and Band SS. Federated learning-based ai approaches in smart healthcare: concepts, taxonomies, challenges and open issues. Cluster Comput.. pp. 1-41, 2022.
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 Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference machine learning, pp- 314-323, 2016.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference Learning Reprexentations, 2018.
M.J. Sheller, B. Edwards, G.A. Reina, al. Federated learning in medicine: facilitating multi- institutionall collaborations without sharing patient data. Sci Rep, 10:12590 2020.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.097 2018.
Hanlin Tang, Shaoduo Gan, Samyam Rajbhandari, Xiangru Lian, Ji Liu, Yuxiong He, and Ce Zhang. Apmsqueeze: A communication efficient adam- cuuu--rccondiiooeed momentum sgd algorithm. arXiv preprint arXiv:2008. / 1343, 2020.
Hanlin Tang, Shaoduo Gan, Ammar Ahmad Awan, Samyam Rajbhandari, Conglong Li, Xiangru Lian, Ji 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.
Qianqian Tong, Guannan Liang, and Jinbo Bi. Effective federated adaptive gradient methods with non-iid decentralized data. arXiv preprint urXiv:2009.06557 2020.
Jianyu Wang, Zheng Xu, Zachary Garrett, Zachary Charles, Luyang Liu, and Gauri Joshi. Local adaptivity in federated learning: Convergence and consistency. arXiv preprint arXiv:2106.02300, 2021.
Yujia Wang, Lu Lin, and Jinghui Chen. Communication--ffiiienn adaptive federated learning. In International Conference on Machine Learning, pp. 22802-22838. PMLR, 2022.
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 preprint arXiv:2109.00533. 2021.
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.
Xidong Wu, Feihu Huang, Zhengmian Hu, and Heng Huang. Faster adaptive federated learning. arXiv preprint 4rX1:2211..00974, 2022.
J. Xu, B.S. Glicksberg, C. Su, al. Federated learning for healthcare informatics. J Healthe Inform Res, 5:1-19, 2021a.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint arXiv:2 106. 10874, 2021b.
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:2 10. 14795, 2021.
12

---

Published as a conference paper at ICLR 2024
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-570000 2019.
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference on Machine Learning, pp. 12253-12266 PMLR, 2021.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances 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:/808.0567), 2018.
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon Pa- pademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in Neural Information Processing Systems, 33, 2020.
13


Reviews:
[{"review_id": "JoWXl90o44", "reviewer": "Reviewer_VFUm", "summary": "The authors propose an adaptive gradient approach for federated constraint optimization. While existing schemes have focused separately on federated optimization and adaptive gradient approaches for the centralized setting, they combine these two lines of research. Specifically, they derive order results for the convergence and the communication complexity of their proposed scheme and perform numerical experiments for a variety of homogenous and non-homogenous datasets.", "questions": "What is the comparison of the sample and communication complexity to other non-adaptive schemes? A little table containing these results would be useful.\n\nIn Figs. 1 and 2, the third plot from the right is not explained in the text. Also, here, essentially the gain of FedDA is due to the addition of a regularization constraint (Lasso). Is there also a gain over benchmark schemes (as FedAvg) for settings where these schemes are not overfitting and why?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors have filled a missing gap in proposing adaptive gradient schemes for FL, which did not seem to exist in the open literature before. This is useful for constraint optimization in a federated setting, for example for regularization.", "weaknesses": "To my opinion, there are two major weaknesses. First, I think that the underlying idea of combining dual averaging with federated constraint optimization is fairly straightforward. The merit of the work is rather in the theoretical order complexity results.\n\nSecond, the paper lacks important information, and thus it is difficult to evaluate their results, specifically with respect to the adaptive gradient results. Specifically, they state on page 5 that the mapping matrix H is updated in line 11 of Algorithm 1, however, line 11 is not present in that algorithm.", "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": "", "extra_scores": {}}, {"review_id": "zoHSxneQdF", "reviewer": "Reviewer_hZzf", "summary": "This paper introduces a novel approach to addressing the problem of constrained federated learning by leveraging adaptive gradient methods. In conventional, non-federated contexts, various techniques and algorithms are available for finding local minimizers of functions, with adaptive gradient methods being particularly effective. The authors extend this idea into the federated learning framework by creating a general adaptive gradient framework.\n\nThis framework includes multiple adaptive gradient methods that rely on a restarted dual averaging technique. The authors begin by adopting a mirror descent perspective of adaptive gradient methods. The central concept in this paper is that if all clients share a common mirror map, they will operate in the same dual space. Consequently, the server can aggregate the local dual states of different clients effectively.\n\nThe paper provides a theoretical analysis of the convergence rate for a specific instantiation of this framework, which employs a momentum-based variance reduction technique. To validate their approach, the authors conduct empirical experiments on various datasets, demonstrating its effectiveness.", "questions": "- Can we check that assumption 5.4 really holds for the provided update of the adaptive matrix in the case of the momentum-based variance reduction instantiation?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "- The authors propose an algorithm that solves the under-explored field of constrained federated learning with optimal convergence rates for the constrained setting (up to my knowledge).\n- The algorithm proposed by the authors is projection-free which is remarkable in a constrained optimization problem.", "weaknesses": "- I found the paper to be poorly written and presented.\n- While I did not found the proposed method to be highly competitive in the unconstrained setting, I believe it holds significant promise in the constrained setting. In my view, the authors should have emphasized the motivation and results from this perspective, rather than aiming to compete with potentially more efficient existing methods.\n- This algorithm is more computationally demanding compared to other algorithms. The added computational cost arises from computing an argmin at each iteration. It remains unclear whether, with this additional step, the proposed algorithm maintains the same level of computational efficiency as its competitors and achieves similar theoretical and experimental results within the same computational budget.\n- While the assumptions made by the authors are common in the analysis of adaptive gradient methods, I find some of them to be rather restrictive, particularly Assumptions 5.1 and 5.4. In light of this observation, the comparison with non-adaptive methods seems somewhat unfair.", "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": "", "extra_scores": {}}, {"review_id": "J3wntHlQ5u", "reviewer": "Reviewer_pEfb", "summary": "In this work, the authors propose FedDA, an adaptive gradient method for constrained optimization in the Federated Learning context. The proposed method builds on top of previously released approaches in local adaptive gradients, and Federated composite optimization. The authors make their claims clear with both theoretical and experimental results (under homogeneous and heterogeneous data distributions). The main motivation behind their approach is to accelerate federated constrained optimization, by adopting the Mirror Descent view of momentum-based acceleration methods.", "questions": "1- At the end of page.5, I think there is a typo about lines 9, 10, 11 of your Algo.1. In particular there is no line.11 in your Algo.1.\n\n2- Minor: Please check your references before updating the final version. For instance the MiME paper is cited twice (on page.11 and on page.12). There is also a typo at the beginning of Section.6.1: PATHMN(I)ST.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1- The method FedDA is general and can incorporate several adaptive gradient methods.\n\n2- FedDA-MVR, the momentum-based variance-reduction gradient estimation, achieves the optimal  iteration complexity rates of non-convex stochastic optimization, without bounded gradient assumption.\n\n3- FedDA performs better or on par with existing methods, on constrained biomarker identification tasks. FedDA-MVR performs well on image classification tasks, even on the challenging non-i.i.d. setting (Fig.12 in appendix).\n\nOverall, the authors provide a clear overview of dual and/or adaptive Federated methods both theoretically (Table.1) and numerically (>5 concurrent methods tested in Fig.3).", "weaknesses": "1- $\\tilde{x}_t$ in equation.9 is not defined in the main text. In particular, how do you compute the L2 distance in between $x_t$ and $\\tilde{x}_t$? Your random variable $\\mathcal{G}_t$ gives an upper-bound (rk.B.17) of L2-norm of the gradient on $\\tilde{x}$ in the unconstrained case. Can we obtain the same for $x$? If yes, is the convergence rate to first order stationary point the same ?\n\n2- I understand fine-tuning NNs on large image classification tasks can be time consuming. However, did you carefully tune the hyper-parameters for FedAvg method? FedAvg is known to perform well under the unconstrained homogeneous setting, but is below $45$% of test accuracy in your experiment on CIFAR-10 (homogeneous; Fig.3). Maybe playing on the local step value $I$, or increasing the batch size (fixed at $16$ in your experiments) can give better gradients estimates, and better performances for FedAvg.\n\n3- Some typos about referencing your algorithms can be confusing (see details in the Questions section below).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)