A-FedPD: Aligning Dual-Drift is All Federated Primal-Dual Learning Needs
Authors: Yan Sun
Li Shen
Dacheng Tao
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Federated primal dual methods
dual drift
virtual dual update
generalization
Primary area: interpretability_and_explainability
TL;DR: We explore the dual drift issue in federated primal dual methods and propose the virtual dual update to further improve its efficiency.

Abstract: As a popular paradigm for juggling data privacy and collaborative training, federated learning (FL) is flourishing to distributively process the large scale of heterogeneous datasets on edged clients. Due to bandwidth limitations and security considerations, it ingeniously splits the original problem into multiple subproblems to be solved in parallel, which empowers primal dual solutions to great application values in FL. In this paper, we review the recent development of classical federated primal dual methods and point out a serious common defect of such methods in non-convex scenarios, which we say is a ``dual drift'' caused by dual hysteresis of those longstanding inactive clients under partial participation training. To further address this problem, we propose a novel Aligned Federated Primal Dual (A-FedPD) method, which constructs virtual dual updates to align global consensus and local dual variables for those protracted unparticipated local clients. Meanwhile, we provide a comprehensive analysis of the optimization and generalization efficiency for the A-FedPD method on smooth non-convex objectives, which confirms its high efficiency and practicality. Extensive experiments are conducted on several classical FL setups to validate the effectiveness of our proposed method.

A-FedPD: Aligning Dual-Drift is All Federated Primal-Dual Learning Needs
Yan Sun
Li Shen' Shenzhen Campus of Sun Yat-sen University mathshenli0gmail1 com
The University of Sydney
ysun9899@uni. . sydney. edu.
Dacheng Tao
Nanyang Technological University dacheng. taoentu. edu.sg
Abstract
As popular paradigm for juggling data privacy and collaborative training, fed- erated learning (FL. is flourishing to distributively process the large scale heterogeneous datasets edged clients. Due bandwidth limitations and security considerations, it ingeniously splits the original problem into multiple subproblems be solved in parallel, which empowers primal dual solutions great applica- tion values in FL. In this paper, we review the recent development of classical federated primal dual methods and point out serious common defect of such methods in non-conver scenarios, which we say is a "dual drift" caused by dual hysteresis of those longstanding inactive clients under partial participation training. To further address this problem, we propose a novel A Aligned Federated Primal Dual (A-FedPD) method, which constructs virtual dual updates to align global consensus and local dual variables for those protracted unparticipated local clients. Meanwhile, we provide comprehensive analysis of the optimization and general- ization efficiency for the A-FedPD method smooth non-convex objectives, which confirms high efficiency and practicality. Extensive experiments are conducted several classical FL setups to validate the effectiveness of our proposed method.
Introduction
Since McMahan et al. [2017] propose the federated average paradigm, FL has gradually become promising approach to handle both data privacy and efficient training the large scale of edged clients, which employs global server to coordinate local clients jointly train one model. Due to privacy protection, it disables the direct information interaction across clients. All clients must only communicate with an accredited global server. This paradigm creates an unavoidable issue, that is, bandwidth congestion caused by mass communication. Therefore, FL advocates training models on local clients as much as possible within the maximum bandwidth utilization range and only communicates with part of clients per communication round in partial participation manner. Under this particular training mechanism, FL needs to effectively split the original problem into several subproblems for local clients solve in parallel. Because of this harsh limitation, general algorithms are often less efficient in practice. But the primal dual methods just match this training pattern, which empowers with huge application potential and great values in FL..
"Li Shen is the corresponding author.
1 Dr Tao's research partially supported by NTU RSR and Start Up Grants.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Primal dual methods, which are specified as Lagrangian primal dual in this paper, solve the problem by penalizing and relaxing the constraints to the original objective via non-negative Lagrange multipliers, which make great progress in convex optimization. It benefits from the consideration of splitting a large problem into several small simple problems to solve, which has been widely developed and applied in the distributed framework as global consensus problem. This solution is also well suited to the FL scenarios for its effective split characteristic. Recent studies revealed the application Rachford Splitting in FL, which unblocks the study of this important branch. With further exploration of Zhang al. [2021], Durmus et al. [2021], Zhang and Hong [2021]. 2. federatte primal dual methods are proven to achieve the fast (1/TT) convergence rate. Then it is expanded to the more complicated scenarios and incorporated with several novel techniques to achieve state-of-N of-thh--tftttt--- (SOTA) performance in the FI. community, which further confirms the great contributions.
potential of such methods. Since Tran Dinh et al. [2021] propose the Randomized
However, as studies go further, series of prob- lems of federated primal dual methods in the ex- periments are also exposed. Sensitivity to hyper- parameters and fluctuations affected by the large scale makes it extremely unstable in practice, especially in the partial participation manner which is one of the most important concerns in FL. Specifically, primal dual methods success- fully solve the problems by alternately updat- ing each primal variable and each dual variable. When it is grafted onto the partial participation training in FL., most clients will remain inactive for a long time, which means most of the dual variables will be stagnant and very outdated in the training. As the training process continues, when one long-term inactive client is reactivated to participate in training, the solving process of its local subproblem will become extremely unstable due to excessive differences between the primal and dual variables, and sometimes even fail. We call this "dual drift" problem, which also one of the most formidable challenges in practice in FL. In 1 we clearly show how the "dual drift" deteriorates as the participation ratio decreases.
Partictration 10%
Porticiation 251
Particbattion 50%
Perticiaation 701
Purticaaatio 100%
Communication Rounds
Commun cation Rounds
(a) Train loss.
(b) Test accuracy.
Figure 1: "Dual drift" issue of the federated primal dual method under different participation ratios. When the participation ratio is low, dual drift intro- duces a very large variance, yielding divergence.
To efficiently expand the primal dual methods to partial participation scenarios while enhancing the training stability in practice, and further alleviate the "dual drifi" problem, we propose a novel algorithm, named Aligned Federated Primal Dual (A-FedPD), which constructs the virtual dual updates for those unparticipated clients per communication round to align with primal variables. Concretely, after each communication round, we first aggregate the local solutions received from active clients as the unbiased approximation of the local solution of those unparticipated clients. Then we provide a virtual update on the dual variables to align with the primal variable in the training. Updating errors for dual variables will be diminished as global consensus is achieved. The proposed FedPPD method enables unparticipated clients to keep up-to-date, which approximates the training, which can efficiently alleviate the "dual drift" in practice.
Furthermore, we provide a comprehensive analysis of the optimization and generalization efficiency of the proposed A-FedPD method, which also could be easily extended to the whole federated primal dual family. On smooth non-convex objectives, compared with the vanilla FedAvg method, the A A-FedPD could achieve a fast (1/TT) convergence rate which maintains consistent with SOTA federated primal dual methods. Moreover, it could support longer local training without affecting stability. Under the same training costs. the A A-FedPD method achieves less generalization error. We conduct extensive experiments to validate its efficiency across several general federated setups. We also test simple variant to show its good scalability incorporated with other novel techniques in FL.
We summarize our major contributions follows:
We review the development of federated primal dual family and point out one of its most formidable challenges in the practical application in FL, which is summarized as the "dual driff" problem in this paper.
We propose a novel A-FedPD method to alleviate the "dual drift",, which constructs the virtual update for dual variables of those unparticipated clients to align with primal variables.
2

---

. We provide comprehensive analysis of the optimization and generalization efficiency of A- A-FedPD. It could achieve a fast convergence rate and a lower generalization error bound than the vanilla FedAvg method.
Extensive experiments are conducted to validate the performance of the A-FedPI method. Furthermore, we test a simple variant of it to show its good scalability.
2
Related Work
Federated primal average. Since McMahan et al. [2017] propose the FedAvg paradigm. a lot of primal uerage-bbsse methods are learned to enhance its performance. Most of them target strengthening global consistency and alleviating the "client drift" problem [Karimireddy et al., 2020]. Li al. [2020] propose to adopt proxy terms to control local updates. Karimireddy et al. [2020] propose the variance reduction version to handle the biases in the primal average. Similar implementations include [Dieuleveut et al., 2021, Jhunjhunwala et al., 2022]. Moreover, momentum- based methods are also popular for correcting local biases. Ozfatura et al. [2021], Xu et al. [2021] propose to adopt the global consistency controller in the local training to force a high consensus. Remedios et al. [2020] expand the local momentum to achieve higher accuracy in the training. Similarly, Wang et al. [2019], Kim et al. [2022] incorporate the global momentum which could further improve its performance. Wang et al. [2020b] tackle the local inconsistency and utilize the weighted primal average to balance different clients with different computing power. Based on this, Horváth et al. [2022] further select the important clients set to balance the training trends under different heterogeneous datasets. Liu et al. [2023] summarize the inertial momentum implementation which could achieve more stable result. Qu et al. [2022] utilize the Sharpeness Aware Minimization (SAM) [Foret et al., 2020] to make the loss landscape smooth with higher generalization performance. Then Caldarola et al. [2022, 2023] propose to improve its stability via Adaptive SAM and window-base based model averaging. In summary, Federated primal average methods focus on alleviating the local inconsistency caused by "client drift" [Malinovskiy et al., 2020, Wang et al., 2020a, Charles and Konečný, 2021]. However, as analyzed by Durmus al. [2021], the federated primal dual methods will regularize the local objective gradually close to global consensus by dynamically adjusting the dual variables. This allows "client drift" be effectively translated into a dual consistency problem on cross-silo devices.
Convex optimization of federated primal dual. The primal-dual method was originally proposed to solve convex optimization problems and achieved high theoretical performance. In the FL setups, this method has also made significant advancements. Grudzien et al. [2023a] compute inexactly a proximity operator to work variant of primal dual methods. Another technique is loopless instead of an inner loop of local steps. Mishchenko et al. [2022] propose the Scaffiew method to achieve the higher optimization efficiency, which is interpreted Richtárik, 2022). These techniques can also be easily combined with existing efficient communication methods, e.g. compression and quantization [Grudzieú et al., 2023b, Condat et al., 2023].
variant of primal dual approach [Condat and
Non-convex optimization federaate primal dual. Since Tran Dinh et al. [2021] adopt the Randomized Douglas- Rachlfod Splitting, which unblocks the study of the important branch of utilizing primal dual methods in FL [Pathak and Wainwright, 2020]. With further exploration of Zhang et al. [2021], J. federated primal dual methods are proven to achieve the fast convergence rate. Yuan et al. [2021] learn the composite optimization via a primal dual method in FL. Meanwhile, Sarcheshmehpour et al. [2021] empower its potential on the undirected empirical graph. Shen et al. [2021] also study an agnostic approach under class imbalance targets. Then, Gong et al. [2022], Wang et al. [2022] expand its theoretical analysis to the partial participation scenarios with global regularization. Durmus et al. [2021] improve its implementation by introducing the global dual variable. Moreover, Zhou and Li [2023] learn the effect of subproblem precision on training efficiency. Sun al. [2023b.a] incorporate it with the SAM to achieve a higher generalization efficiency. Niu and Wei [2023] propose hybrid primal dual updates with both first-order and second-order optimization. Wang et al. [2023] propose a variance reduction variant to further improve the training efficiency. Li et al. [2023a] expand it to decentralized approach, which could achieve comparable performance in the centralized. Tyou et al. [2023] propose localized primal dual approach for FL training. Li et al. [2023b] further explore its efficiency on the specific non-convex objectives with non-smooth regularization. Current researches reveal the great application value of the primal dual methods in FL. However, most of them still face the serious "dual drift" problem at low participation ratios. Our improvements further alleviate this issue and make the federated primal dual methods perform more stably in the FL community.
3

---

3 Methodology
Table 1: Notations adopted in this paper.
We first review the primal dual meth- ods in FL and demonstrate the "dual driff" issue. Then, we demonstrate the A-FedPD approach to eliminate the "dual drift" challenge. Notations are stated in Table 1. Other symbols are defined when they are first intro-
Symbol
Notations
CIC
client set size of client set active client set size of active client set local dataset size of local dataset global parameters / local parameters global dual parameters / local dual parameters
PIP
S₁ S 01
AI AE
duced. We denote IR as the real set and as the expectation in the cor- responding probability space. Other notations are defined as first stated.
T
training round index of training round local interval index of local interval proxy coefficient
KIK
P
3.1 Preliminaries
Setups. In the general and classical federated frameworks, we usually consider the general objective as finite-sum sum minimization problem F(0) Rd R.
min F(0)
Σ F(()), SEC
F(()) é F.
(1)
C
In each client, there exists local private data set S, which is considered uniform sampling set of the distribution D, FL setups, D; is unknown to others for the privacy protection mechanism. Therefore, usually consider the local Empirical Risk Minimization (ERM) as:
min f(0) = C Σ 1iO0,, ((O) A Σ S((0E))
(2)
SES.
Our desired optimal solution is 0 arg min F(0). However, we can only approximate it the limited dataset as 03 = arg min f0), which spontaneously introduces the unavoidable biases on its generalization performance. This is one of the main concerns in the field of the current machine learning community. Motivated by this imminent challenge, we conduct a comprehensive study on the performance of primal dual-based algorithms in FL and further propose an improvement to enhance its generalization efficiency and stability performance.
3.2 Primal Dual-family in FL
Primal Dual methods optimize the global objective by decomposing into several subproblems and iteratively updating local variables incorporated by Lagrangian multipliers [Boyd et al., 2011], which gives it unique position in solving FL problems. Due to local data privacy, we have to split the global task into several local tasks for optimization on their private dataset. This similarity also provides an adequate foundation for their applications in the FL community. lot of studies extend it to the general FL framework and achieve considerable success.
We follow studies [Zhang et al., 2021, Durmus al., 2021, Wang al., 2022, Gong et al., 2022, Sun et al., 2023b, Zhou and Li, 2023, Sun et al., 2023a, Fan et al., 2023, Zhang et al., 2024] to summarize the original objective (2) as the global consensus reformulation:
1 Σ (((O.). C
min R.9;
s.t. 0. =, V.
(3)
By relaxing equality constraints 0g 0, (3) is separable across different local clients. Wang et al. [2022] demonstrate the difference between the solution on the primal problem and dual problem in detail and confirm the equivalence of these two cases in FL. By penalizing the constraint on the local objective f.. we can define the augmented Lagrangian function associated with E3) as:
C(O., 0,
C Σ
(A, 0) -) [1(00))(A,, (A.,
(4)
where / denotes the penalty coefficient. To train the global model, each local client should first minimize the local augmented Lagrangian function and solve for local parameters. Based on updated local parameters, then update the dual variable to align the Lagrangian function with the consensus

---

constraints, Finally, we minimize the augmented Lagrangian function and solve for the consensus. Objective E3.(3) could be solved after multiple alternating updates as:
{
0f = arg mine, [(0), 0r, A.) EEC,
1t1 + p(0 0²),
(5)
@
a (0 1
We then review the classical federated primal dual methods.
FedPD. Zhang et al. [2021] propose a general federated framework from the primal-dual optimization perspective which can be directly summarized (q. As underlying method in the federated primal dual-family, it requires all local clients to participate in the training per round, which also significantly reduces communication efficiency.
FedADMM. Wang et al. [2022] extend the theory of the primal-dual optimization in FL and prove the equivalence between FedDR [Tran Dinh al., 2021] and FedADMM. Furthermore, it considers the complete format composite objective f(),) + g ) To optimize the composite objective, after the iterations of (5), it additionally solves the proximal step on the function g
0+ arg mine, C(6 0t, A1) + g(0") ie
X X + p( - 8¹);
0+1 = + E (0 p )
0'+1 arg minginge g(0")+ + zp 10 1 112
FedADMM introduces more general update with the regularization term g(0) and supports the partial participation training mechanism, which also brings a great application value of primal-dual methods to the FL community. When g(-) 0, it degrades to the partial FedPD by g++1 7 When P + C, "dual driff" brings great distress for training.
FedDyn. Durmus al. [2021] utilize the insight of primal-dual optimization introduce dynamic regularization term to solve the local augmented Lagrangian function, which is actually the dual variable in FedADMM. Differently, they propose global dual variable Xf to update global parameters of instead of only active local dual variables X (i E P():
0:11 arg mino; L(O, 0", A1) i E
A = X + + 0¹)
1-1 = A + Pd E (6) - 0¹),
0 = 7 Eiere 0, + 1
Compared with FedADMM, although the global dual variable further corrects the primal parameters, it still hinders the training efficiency, which must rely on the anachronistic historical directions of the local dual variables. Moreover, the global dual variable always updates slowly, which results in consensus constraints that are more difficult to satisfy when solving local subproblems.
Dual drift. Kang et al. [2024] have indicated that the update mismatch between primal and dual variables leads to "drift". Here, we provide detailed analysis of the key differences caused by this mismatch. When adopting partial participation, each client is activated at a very low probability, especially large scale of edged devices, which widely leads to very high hysteresis between global parameters 0 and local dual variable A₁ For instance, at round i, we select a subset pP to participate in current training and then update the global parameters by gt++1 = arg ming L( 0t, X²) for i P Then at round t + when a client & (PT) - (to < t) that has not been involved in training for a long time is activated, its local dual variable X may severely mismatch the current global parameters 0', This triggers that the local subproblem C(0)+1, ge+11 XX) ) fail to be optimized properly and even become completely distorted in extreme scenarios, yielding "dual drift" issue.
3.3 A-FedPD Method
As introduced in the last part, "clual drift" problem usually results in the unstable optimization of each local subproblem under partial participation. To further mitigate the negative effects of dual drift problems and improve the training efficiency, we propose a novel A-FedPD method (see Algorithm 1), which aligns the virtual dual variables of unparticipated clients via global average models.
5

---

Algorithm A-FedPD Algorithm
Input: 0. 0., T. K. X
② LocalTrain: (Optimize Eq.(4)) Input: X, 0², "0'""'"'
Output: global average model
I: Initialization 0 0 X
Output: 0
2: fort= 0, ... 7 do
for = 0, 2,
do
3: randomly seleet active clients set P from C for client E p in parallel do
2: calculate the stochastic gradient gi
0, 6-2,- r (g + Ai p(0;, 8¹)
receive X, 0 from the global server 6: 0f+1 = LocalTrain( (X; 0", , K)
4: end for
send e to the global server
4 D- Update: (update dual variables)
8:
end for
9:
_ Eigor 0.+1
Input: X 110++1 ,0++1 p
10:
X+1 D-Update(M,, 0*, ,0,0000111 10,110011p1)
Output: X.
if P then
11:
X C Diec X+1
1
2:
A 1+1 X + pc 0¹)
getl= = p² + 1x
12:
3: else
4: A = xi pa 0¹)
13: end for
14: return global average model
end if
Specifically, we solve dual variables for unified management and distribution. At round i, we select an active client set pt and send the corresponding variables to each active client. Then local client solves the subproblem with K stochastic gradient descent steps and sends the last state 0 back
to the global server. On the global server, first aggregates the updated parameters g Then performs the updates of the dual variables. For each active client E Pt, it equally updates the local dual variable vanilla FedPD. For the unparticipated clients i $ pt, they update the virtual dual variable with the aggregated parameters 0²*1 Finally, we can update the global model with the aggregated parameters and averaged dual variables. Since each client virtually updates, we can directly use the global average as the output. Repeat this training process for a total of T communication rounds to output the final global average model.
Because the central storage and management of the dual variables on the global server, it signif- icantly reduces storage requirements for lightweight-edged devices, i.e., mobile phones. For the unparticipated clients, we use their unbiased estimations E [ w²] Ep- [ EsEpi + wt] to construct the virtual dual update, which maintains a continuous update of local dual variables.
reformulate its update x x + p(0 -²) which also could be approximated as a virtual all participation case. This efficiently alleviates the dual drift between 6 and X and also ensures fast iteration of the global dual variable in the training, which constitutes an efficient federated framework.
For the global averaged dual variable X,
Theoretical Analysis
In this part, we mainly introduce the theoretical analysis of the optimization and generalization efficiency of our proposed A-FedPD method. We first introduce the assumptions adopted in our proofs. Optimization analysis is stated in Sec.4.1 and generalization analysis is stated in Sec.4.2. Assumption (Smoothness) The local function fi(-) satisfies the L-smoothness property, i.e. (V,) - V (f((2)) s T.|01 - 82ll-
Assumption (Lipschitz continuity) For V 01,0, 02 Rd, the global function f(-) satisfies the Lipschirz-commiimiit. i.e.. (] - f(22)l s G - 02ll.
Optimization analysis only adopts Assumption Generalization analysis adopts both assumptions that were followed from the previous work on analyzing the stability [Hardt et al., 2016, Lei and Ying, 2020, Zhou et al., 2021, Sun et al., 2023e,d,cl. Moreover, we consider that the minimization of each local Lagrangian problem achieves the e-inexact solution during each local training process, i.e. ||VC, 12 < [Zhang et al., 2021, et al., 2023a, Gong et al., 2022, Wang et al., 2022]. This consideration is more aligned with the practical scenarios encountered in the empirical studies for non-convex optimization. In fact, it is precisely because the errors from local inexact solutions can be excessively large that the dual drift problem is further exacerbated.

---

4.1 Optimization
In this part, we introduce the convergence analysis of the proposed A-FedPD method.
Theorem Let non-convex objective f satisfies Assumption let p be selected non-zero positive constant, {0 Yi=o sequence generated by algorithm satisfies:
EIVIOO) ((000) f + Ro
+ (E),,
(8)
T
where I is the optimum and Ro -
=o= Diec Ee110 - 0011 is the first local training volumes.
Remark 1.1 To achieve the error, the A-FedPD requires O(e=²) rounds, yielding ((1/T)) conver- gence rate. Concretely, the federated primal dual methods can locally train more and communicate less, which empowers it great potential in the applications. Our analysis is consistent with the previous understandings [Zhang et al., 2021, Durmus et al., 2021, Gong et al., 2022, Li et al., 2023a].
Remark 1.2 Generally, the federated primal- dual methods require a long local interval. Zhang et al. [2021], Gong et al. [2022], Wang et al. [2022] have summarized the corresponding selections of K for different local optimizers. To complete the analysis, we just list a general selection of the local interval K. Specifically, to achieve the error, local interval K of A-FedPD can be selected as O(e with total ( 2) sample complexity in the training. Due to the page limitation. we state more discussions in the Appendix B.2.2.
4.2 Generalization
In this part, we explore the efficiency of FedeD from the stability and generalization perspective, which could also be extended to the common primal dual-family in the federated learning community. We first introduce the setups and assumptions and then demonstrate the main theorem and discussions.
Setups. To understand the stability and generalization efficiency, we follow Hardt et al. [2016], Lei and Ying [2020], Zhou et al. [2021], Sun et al. [2023e] to adopt the uniform stability analysis to measure its eиror bound. To learn the generalization gap EE [F(0*) f(0")] where 6² is generated by stochastic algorithm, we could study its stability gaps. We consider a joint client set C' (union dataset) for training. Each client i has a private dataset S; with total S samples which are sampled from the unknown distribution D:, To explore the stability gaps, we construct mirror dataset that there is at most one diffferent data sample from the raw dataset C. Let 0 and 0" be two models trained on C and é respectively. Therefore, the generalization of a uniformly stable method satisfies:
- -((00")((0'))]] s sup [[s(0", ,E) s(O", _0]] S..
Key properties. From the local training, we can first upper bound the local stability. To compare the difference between vanilla SGD updates and primal dual- dual-family updates, we can reformulate them:
00 -0- 0² = =00 - 0²) g 0 0 g -1 (0 8*) + (9i. + X.).
(10)
The above update is for vanilla FedAvg and the below update is for primal dual dual-family. When the dual variables are ignored, local update 0f2,- - 0t in primal dual could be considered as a stable decayed sequence with 1 - 7 p that has constant upper bound. Based on this, we can provide tighter generalization error bound for the primal dual-family methods FL. than the vanilla FedAvg method.
Theorem Let non-convex objective I satisfies Assumption I and 2 and H supa s(0, E), after T communication rounds training with Algorithm 1, the generalization error bound achieves:
- B ([F(0)) s
Ke Ifu
(HPT)
(I))
CS
where μt is constant related to the learning rate and Ki 4 (G² FIaL is constant.
Remark 2.1 We assume that the total number of data samples participating in the training is CS and the total iterations of the training are KT. Hardt et al. [2016] prove that on non-convex
objectives, vanilla SGD method achieves ((T THuE /CS) error bound. Compared with SGD, FL
7

---

Test aceuracy the CIFAR-10 / 100 dataset. We fix the total client C 100 and P = 10 under training local 50 iterations. We test setups of IID, Dir- Dir-1.0, and Dir-0.1 on each dataset. Each group is tested LeNet (upper portion) and ResNet-18 (lower portion) models. Each results are tested with 4 different random seeds. "_" means can not stably converge. "Family" distinguishes whether the algorithm is primal method (P) primal dual method (PD) and "Local Opt" distinguishes whether the algorithm adopts SGD-based or SAM-based local optimizer.
Table 2:
CIFAR-10
CIFAR- 100
FAMILY
LOCAL OPT
IID
DIR-1.0
DIR-0.1
IID
DIR-1.0
DIR-0.1
FEDAYG
SGD
81.87
80.58
40.11
39.65
38.374t.14
FEDCM
P
SGD
80. 40.34
79.31
72.89
43.31-
42.35
37.1 17.1
SCAFFOLD
SGD
84
83.61
78,66 29
49.65
49.11
46, 4..30
FEDSAM
SAM
83.22
81.941.13
77.41
43.02_.mp
4..83
42.291..1
FEDDYN
PD
SGD
84.49
84.20
79.51
50.27
49.64
46, 36
FEDSPEED
SAM
86.01
85.11+221
80.86
54.01=.15
53.45
11.28+.18
A-FEDPD
PD
SGD
85.31
84.94
80.28
51.41
51.17
48. 48.15
A- A-FERPDSAM
PD
SAM
86.47 +.47..1.
85.90
81.96
55,56 27
54.62
$3.15
FEDANG
P
SGD
81.67
10.94
76.24
44.68
44.27 1.25
41.64
FRDCM
P
SGD
84.221.17
82.85
76.93
50.04_.11
48.661.
44.07
SCAFFOLD
P
SGD
84.3 84.31 1.14
83.70
78.70 a1
50,69
50,28
47. 12.44..4
FEDSAM
SAM
83.79+.28
82.58+.19
77.83=
48.66-.29
48.42+.19
45.03+.22
FEDDYN
PD
SGD
83.7 83.71
82.66..15
79.44
PEDSPEED
SAM
86.90
85.92
81.471.19
53.22
52.751.16
19.661.13
A-FEDPD
SGD
15.11
8..33
81.05
48.15
48.02.1.2
46. 1.20
A-FROPDSAM
PD
SAM
87.44
86.461.93
82.48
55.30
53.491.17
50.31
adopts the cyclical local training and partial participation mechanism which further increases the stability error. Sun et al. [2023d] learn a fast rate on sample size as ((PKT) pl /CS) under the Lipschitz assumption only. However, primal dual-family in FI, which is due to the stable iterations in Eq.(10). It guarantees that the local training could be under the fixed learning rate. From the local training perspective,
achieve faster rate ((PPT) yrut /CS)
bounded in constant order primal dual-family in FL can support a very long local interval K without losing stability. This property is also proven in its optimization progress, that the primal dual-famity could adopt a larger local interval to accelerate the training and reduce the communication rounds. In general training, especially in situations where communication bandwidth is limited and frequent communication possible, the primal aual-family in FL could achieve a more stable result than the general methods. Our analysis further confirms its good adaptivity in FL. Due to page limitation, we summarize some recent results of the generalization error bound in Appendix B.3.2.
5 Experiments
In this section, we introduce the experiments conducted to validate the efficiency of our proposed A-FedPD and a variant A- A-FedPDSAM (see details in Appendix A. We first introduce experimental setups and benchmarks, and then we show the empirical studies.
Backbones and Datasets. In our experiments, adopt LeNet LeCun al. [1998] and ResNet He et al. [2016] as backbones. We follow previous work to test the performance of benchmarks on the CIFAR-10 100 dataset Krizhevsky et al. [2009]. We introduce the heterogeneity raw dataset to local clients with independent Dirichlet distribution Hsu et al. [2019] controlled by a concentration parameter. In our setups, we mainly test the performance of the IID, Dir-1.0, 1.0, and Dir-0.1 splitting. The 1ir- represents the low heterogeneity and Dir-0.1 represents the high heterogeneity. We also adopt the sampling with replacement to further enhance the heterogeneity.
split the
Setups. We test the accuracy experiments on = 100 and P/C = 10%, which is also the most popular setup in the FL community. In the comparison experiments. we test the participated ratio P/C = (5%, 10%, 20%, 50%, 80%, 100%] and local interval K = [10, 20, 50, 100, 200) respectively. In each setup, for fair comparison, freeze the most of hyperparameters for all methods. We fix total communication rounds = 800 except for the ablation studies.
Baselines. FedArg [McMahan et al., 2017] is the fundamental paradigm in FL scenarios. FedCM [Xu et al., 2021], SCAFFOLD (Karimiredyy et al., 2020] and FedSAM [Qu et al., 2022] are three classical SOTA methods in the federated primal average family. FedDyn [Durmus al., 2021] and
8

---

85
84
Accurecty (50
83
Accunacy
Accuracy
02
Fediwa SCArFOLD
Fedéeg
Fedtug
Fresay
FedByy
Endlinn
FedSipeed
Fudiipeed
74
78
76
50
Participation Ratios
Local Intervals
Communication Rounds
(a) Different Participation Ratios. (b) Different Local Intervals.
(c) Different Rounds.
Figure 2: Test of the proposed A- A-FedPD) method on setups of different participation ratios, different local intervals, and different rounds. In these experiments, we fix the total training data samples and total training iterations and then learn their variation trends.
FedSpeed Sun et al. [2023b] are relatively stable federated primal dual methods. A more detailed introduction of these methods is presented in Table including the family- masisy-basis and local optimizer.
5.1 Experiments
In this part, we introduce the phenomena observed in our empirical studies. We primarily investigated performance comparisons, including settings with different participation rates, various local intervals, and different numbers of communication rounds. Then we report the comparison of wall-clock time.
Performance Comparison. Table 2 shows the test accuracy on CIFAR-10 / 100 dataset. The vanilla FedAvg provides the standard bars as the baseline. In the federated primal average methods, The FedCM is not stable enough and is largely affected by different backbones, which is caused by the forced consistency momentum and may introduce very large biases. SCAFFOLD and FedSAM performs well. However, both are less than the primal dual-based methods. In summary, SCAFFOLD is on average 3.2% lower than FedSpeed. As heterogeneity increases, SCAFFOLD drops on average about 5.6% CIFAR-10 and 3.43% CIFAR- 100. In the federated primal dual methods, we clearly see that FedDyn is not stable in the training. performs well on the LeNet, which could achieve least 1% improvements than SCAFFOLD. However, when the task becomes difficult, ie., ResNet-18 on CIFAR- 100, its accuracy is affected by the "dual drift" and drops quickly. To maintain stability, we have to select some weak coefficients to stabilize it and finally get lower accuracy. Our proposed A- FeddDD could efficiently alleviate the negative impacts of the "dual drift". performs about on average 0.8% higher than FedDyn on the CIFAR-10 dataset. When FedDyn has to compromise the hyperparameters and becomes extremely unstable on ResNet-18 on the CIFAR-100 dataset, A-FedPD still performs stably. It's also very scalable. When introduce the SAM optimizer to replace the vanilla SGD, it could achieve higher performance.
Different Participation Ratios. In this part we compare the sensitivity to the participation ratios. In each setup, we fix the scale as 100 and the local interval as 50 iterations. Active ratio is selected from 15%, 10%, 20%,50% 80%, 100%] as shown in Figure 2 (a). Under frozen hyperparameters, all methods perform well on each selection. The best performance is approximately located in the range of [20%, 80%]. Our proposed methods achieve high efficiency in handling large-scale training, which performs more steadily than other benchmarks across all selections.
Different Local Intervals. In this part we compare the sensitivity to the local intervals. In each setup, we fix the scale as 100 and the participation as 10%. Local interval K' is selected from [10, 20, 50, 100, 200] shown in Figure 2 (b). More local training iterations usually mean more overfitting on the local dataset, which leads to serious "client drift" issue. All methods will be affected by this and drop accuracy. It is a trade-off in selecting the local interval K to balance both optimization efficiency and generalization stability. Our proposed methods still could achieve the best performance
the very long local training iterations.
Different Communication Rounds. this part, we compare the sensitivity to communication rounds. In each setup, we fix total iterations TK- = 40, 000. Communication round T is selected from (200, 400, 800, 2000, 4000] as shown in Figure 2 (c). We always expect the local clients can handle more and communicate less, which will significantly reduce the communication costs. In the

---

experiments, our proposed methods could achieve higher efficiency than the benchmarks. A-FedPD saves about half the communication overhead compared SCAFFOLD, and about one-third of FedDyn. Under favorable communication bandwidths, they can achieve SOTA performance.
Wall-clock Time Efficiency. In this part test the practical wall-clock time comparisons shown in Figure 3. Though some methods complicated cal- culations hinder the real efficiency in wall-clock training time. Though FedSpeed and AFed- PDSAM perform well the end, additional cal- culations per single round make their carly-stage competitiveness lower. AFedPD and SCAF- FOLD consume fewer time costs, hence achiev- ing better results the early stage. Without considering training time costs, AFedPDSAM achieves the SOTA results at the end. Detailed comparisons are stated in S.c.A.4.4
are communication--fficcinen
ACCUR 1861
Fattag
SCAFFOL3
SCafFOLD
fadipeed
Iedipeed
Tranning Time (5)
Tairing Time (s)
(a) ResNet-18.
(b) LeNet.
Figure 3: Wall-clock time test of training process
after total of 600 communication rounds.
6 Conclusion
In this paper, we first review the development of the federated primal dual methods. Under the exploration of the experiments, we point out serious challenge that hinders the efficiency of such methods, which is summarized as the "dual drift" problem due to the mismatched primal and dual variables in the partial participation manners. Furthermore, we propose novel A-FedPD method to alleviate this issue via constructing virtual dual updates for those unparticipated clients. We also theoretically learn its convergence rate and generalization error bound to demonstrate its efficiency. Extensive experiments are conducted to validate its significant performance.
10

---

References
Muhammad Asad, Ahmed Moustafa, and Takayuki Ito, Fedopt: Towards communication efficiency and privacy preservation in federated learning. Applied Sciences, 10(8):2864, 2020.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Fekstein, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 122, 2011.
Debora Caldarola, Barbara Caputo, and Marco Ciccone. Improving generalization in federated learning by seeking flat minima. In European Conference on Computer Vision, pages 654-672. 654ine2,,pringerr, 2022.
Debora Caldarola, Barbara Caputo, and Marco Ciccone. Window-based model averaging improves generalization in heterogeneous federated learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2263-2271 2023.
Zachary Charles and Jakub Konečný. Convergence and accuracy trade-offs in federated learning and meta- learning. In International Conference on Artificial Intelligence and Statistics, pages 2575-2583. PMLR, 2021.
Laurent Condat and Peter Richtárik. Randprox: Primal-dual optimization algorithms with randomized proximal updates. arXiv preprint arXiv:220.12891, 2022.
Laurent Condat, Ivan Agarský. Grigory Malinovsky, and Peter Richtárik. Tamuna: Doubly accelerated federated learning with local training, compression, and partial participation. arXiv preprint arX1v:2302.09882, 2023.
Aymeric Dieuleveut, Gersende Fort, Eric Moulines, and Geneviève Robin. Federated-em with heterogeneity mitigation and variance reduction. Advances in Neural Information Processing Systems, 34:29553-29566, 2021.
Alp Emre Durmus, Zhao Yue, Matas Ramon, Mattina Matthew, Whatmough Paul, and Saligrama Venkatesh. Federated learning based on dynamic regularization. International Conference on Learning Representations, 2021.
Ziqing Fan, Yanfeng Wang, Jiangchao Yao, Lingjuan Lyu, Ya Zhang, and Qi Tian. Fedskip: Combatting statistical heterogeneity with federated skip aggregation. 2022 IEEE International Conference on Data Mining (ICDM). pages 131-140. JEEE, 2022.
Ziqing Fan, Jiangehao Yao, Ruipeng Zhang, Lingjuan Lyu, Yanfeng Wang, and Ya Zhang. Federated learning under partially disjoint data via manifold reshaping. Transactions on Machine Learning Research, 2023.
Ziqing Fan, Shengchao Hu, Jiangchao Yao, Gang Niu, Ya Zhang, Masashi Sugiyama, and Yanfeng Wang- Locally estimated global perturbations are better than local perturbations for federated sharpness-aware minimization. arXiv preprint ar 2iv: 18890, 2024a.
Ziqing Fan, Jiangehao Yao, Bo Han, Ya Zhang, Yanfeng Wang, al. Federated learning with bilateral curation for partially class-disjoint data. Advances in Neural Information Processing Systems, 36, 2024b.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-awarc minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412. 2020.
Yonghai Gong, Yichuan Li, and Nikolaos M Freris. Fedadmm: A robust federated deep learning framework with adaptivity to system heterogeneity. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 2575-2587. IEEE, 2022.
Michal Grudzieú. Grigory Malinovsky, and Peter Richtárik. Can 5th generation local training methods support client sampling? yes! In International Conference on Artificial Intelligence and Statistics, pages 1055-1092. PMLR, 2023a.
Michat Grudzieñ, Grigory Malinovsky, and Peter Richtárik. Improving accelerated federated learning with compression and importance sampling. arXiv preprint 03X222300..32400 2023b.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225 1234. PMLR, 2016
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
Samuel Horváth, Maziar Sanjabi. Lin Xiao, Peter Richtárik, and Michael Rabbat. Fedshuffle: Recipes for better use of local work in federated learning arXiv preprint arXiv:2204.13760 2022.
11

---

Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint urXiv:1909006333 2019.
Xiaolin Hu, Shaojie Li, and Yong Liu. Generalization bounds for federated learning: Fast rates, unparticipating clients and unbounded losses. In The Eleventh International Conference on Learning Representations, 2022.
Divyansh Jhunjhunwala. Pranay Sharma, Aushim Nagarkatti, and Gauri Joshi, Fedvarp: Tackling the variance due to partial client participation in federated learning. In Uncertainty in Artificial Intelligence, pages 906-916. PMLR, 2022.
Heejoo Kang. Minsoo Kim, Bumsuk Lee, and Hongseok Kim. Fedand: Federated learning exploiting consensus admm by nulling drift. IEEE Transactions on Industrial Informatics, 2024.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sehastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning. pages 5132-5143, PMLR, 2020.
Gecho Kim, Jinkyu Kim, and Bohyung Han. Communication-cfffccce federated learning with acceleration of global momentum. arXiv preprint arXiv:2201 03112, 2022.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applicd to document recognition. Proceedings of the IEEE, 86(11 (6(1)):227-2333 1998.
Yunwen Lei and Yiming Ying. Fine- Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference Machine Learning, pages 5809 5819. PMLR, 2020.
Qinglun Li, Li Shen, Guanghao Li, Quanjun Yin, and Dacheng Tao. Dfedadmm: Dual constraints controlled model inconsistency for decentralized federated learning. arXiv preprint arXiv:2308.0853 08290. 2023a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in hetcrogeneous networks. Proceedings of Machine learning and systems,
2020.
Yiwei Li, Chien Beie Huang, Shuai Wang. Chong Yung Chi, and Tony QS Quek. Privacy-preserving preserving feder- ated primal-dual learning for non-convex problems with non-smooth regularization. In 2023 IEEE 33rd International Workshop on Machine Learning for Signal Processing (MLSP), pages 1-6. IEEE, 2023b.
Yixing Liu, Yan Sun, Zhengtao Ding, Li Shen, Liu, and Dacheng Tao. Enhance local consistency in federated learning: A multi-step inertial momentum approach. arXiv preprint arXiv:2302.05726, 2023.
Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local sgd to local fixed-point methods for federated learning. In International Conference Machine Learning, pages 6692-6701. PMIR, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas, Communication- efficient lcarning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282, PMLR, 2017.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference Machine Learning, pages 15769- PMLR, 2022.
Mchryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. International Conference on Machine Learning, pages 4615-4625. PMLR, 2019.
Xiaochun Niu and Ermin Wei, Fedhybrid: A hybrid federated optimization method for heterogeneous clients. IEEE Transactions Signal Processing, 71:150- 163,0066611160111033301111 2023.
Emre Ozfatura. Kerem Ozfatura, and Deniz Gündüz. Fedade: Accelerated federated learning with drift control. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 467-472. IEEE, 2021.
Reese Pathak and Martin Wainwright. Fedsplit: An algorithmic framework for fast federated optimization. Advances in neural information processing systems, 33:7057-7066, 2020.
Zhe Qu, Xingyu Li, Rui Duan. Yao Liu, Bo Tang, and Zhuo Lu. Generalized federated learning via sharpness aware minimization. In International Conference on Machine Learning, pages 18250-18280. PMLR, 2022.
12

---

Samuel W Remedios, John A Butman, Bennett A Landman, and Dzung L Pham. Federated gradient averaging for multi-site training with nommnttum-based optimizers. In Domain Adaptation and Representation Transfer, and Distributed and Collaborative Learning: Second MICCAI Workshop, DART 2020, and First MICCAI Workshop, DCL 2020, Held in Conjunction with MICCAI 2020, Lima, Peru, October 4-8, 8, 2020, Proceedings 2. pages 170-180. Springer, 2020.
Yasmin Sarcheshmchpour, M I Leinonen, and Alexander Jung. Federated learning from big data over networks. In ICASSP 2021 1 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3055-3059. IEEE, 2021.
Zebang Shen, Juan Cervino, Hamed Hassani, and Alejandro Ribeiro. An agnostic approach to federated learning with class imbalance. In International Conference on Learning Representations, 2021.
Yan Sun, Li Shen, Shixiang Chen, Liang Ding, and Dacheng Tao. Dynamic regularized sharpness aware minimization in federated learning: Approaching global consistency and smooth landscape. arXiv preprint arXiv:2305. 1584, 2023a.
Yan Sun, Li Shen, Tiansheng Huang, Liang Ding, and Dacheng Tao. Fedspeed: Larger local interval, less communication round, and higher generalization accuracy. arXiv preprint 10444 2023b.
Yan Sun, Li Shen, Hao Sun, Liang Ding, and Dacheng Tao. Efficient federated learning via local adaptive amended optimizer with linear speedup. arXiv preprint arXiv:2308.00522 2023c.
Yan Sun, Li Shen, and Dacheng Tao. Which mode is better for federated learning? centralized or decentralized. arXiv preprint arXiv:2310.0346) 2023d.
Yan Sun, Li Shen, and Dacheng Tao. Understanding how consistency works in federated learning via stage-wise relaxed initialization. arXiv preprint urXiv:2306.05706 2023e.
Quoc Tran Dinh, Nhan H Pham, Dzung Phan, and Lam Nguyen. Feddlr-randomized douglas-rachford splitting algorithms for nonconvex federated composite optimization. Advances in Neural Information Processing Systems, 34:30326 30338, 2021.
lifan Tyou, Tomoya Murata, Takumi Fukami, Yuki Takezawa, and Kenta Niwa. A localized primal-dual method for contralizzedddeeenttaiizd federated learning robust to data heterogeneity. IEEE Transactions on Signal and Information Processing over Networks, 2023.
Han Wang, Siddartha Marella, and James Anderson. Fedadmm: A federated primal-dual algorithm allowing partial participation. In 2022 IEEE 61st Conference on Decision and Control (CDC), pages 287-294, IEBE, 2022.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication-efficienn distributed sgd with slow momentum, arXiv preprint
2019.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33: 7611-7623 2020a.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33: 7611-7623, 2020b.
Shuai Wang. Yanqing Xu, Zhiguo Wang. Tsung-Hui Chang, Tony QS Quek, and Defeng Sun. Beyond admm: unified client- veduence-reduced adaptive federated learning framework. In Proceedings the AAAI Conference on Artificial Intelligence, volume 37, pages 10175 -1083,, 2023.
Zheshun Wu, Zenglin Xu, Hongfang Yu, and Jie Liu. Information thherrrttotttottcctccoo generalization analysis for topology- aware heterogencous federated edge learning over noisy channels. JEEE Signal Processing Letters, 2023.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. arXiv preprint arXiv:2 10874, 2021.
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference on Machine Learning, pages 12253 12266. PMLR, 2021.
Ruipeng Zhang, Ziqing Fan, Jiangehao Yao, Ya Zhang, and Yanfeng Wang. Domain-inspirel sharpness-aware minimization under domain shifts, arXiv preprint arXiv:2405. 18861, 2024.
Xinwei Zhang and Mingyi Hong. On the connection between fed-dyn and fedpd. FedDyn FedDyn_FePDD, pdf. 2021.
13

---

Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A federated learning framework with adaptivity non-iid data. IEEE Trunsactions Signal Processing. 69:6055-6070, 2021.
Pan Zhou, Hanshu Yan, Xiaotong Yuan, Jiashi Feng, and Shuicheng Yan. Towards understanding why lookahead generalizes better than sgd and beyond. Advances in Neural Information Processing Systems, 34:27290-27366 2021.
Shenglong Zhou and Geoffrey Ye Li. Federated learning via inexact admm. IEEE Transactions Pattern Analysis and Machine Intelligence, 2023.
14

---

In this part, we introduce the appendix. We introduce the additional experiments in Sec.A including backgrounds, setups, hyperparameters selections, and some figures of experiments. We introduce the theoretical proofs in S.
Limitations. To avoid the dual drifts, we propose the virtual dual updates to align the old dual variables with the new global model. This requires those dual variables of non-active clients to be updated on the global server, yielding more storage costs. As a trade-off, our method applies additional variable assistance to greatly improve the stability of such algorithms. It also is an interesting future study to approximate the virtual dual update on the local clients.
A
Additional Experiments
A.1 Benchmarks
We select 6 classical state-of-the-arr (SOTA) benchmarks baselines in our paper, including (a)
primal: FedAvg McMahan et al. [2017], SCAFFOLD Karimireddy et al. [2020], FedCM Xu et al. [2021], FedSAM Qu et al. [2022]; (b) primal dual: FedADMM Wang et al. [2022], FedDyn Wang et al. [2022), FedSpeed Sun et al. [2023b]. We mainly focus on infrastructure improvements instead of combinations of techniques. In the primal group, SCAFFOLD and FedCM alleviate "client drift" via variance reduction and client-level momentum correction respectively. FedSAM introduce the Sharpeness Aware Minimization (SAM) Foret et al. [2020] in vanilla FedArg smoothen the loss landscape. In the primal dual group, we select the FedDyn as the stable basis under partial participation. We also show the instability of the vanilla FedADMM to show the negative impacts of the "dual driff". FedSpeed introduces the SAM in vanilla FedADMM FedDyn. We also test the variant of SAM version of our proposed A-FedPD method, which is named A A-edPDDSM..
Algorithm 2 A-FedPDSAM Algorithm
Input: 8", 8f.0 K. X², p
& LocalTrain: (Optimize Eq.(4)) Input: X₁, 0', 1//,, K
Output: global average model
I: Initialization : 0 80 X -0
Output: 02,x
2: for = 1, 7 1 do
1: for k = 0, 2,, .... K do
3: randomly select active clients set p' from C
2: select minibatch B
4: for client E P' in parallel do
V.] B8) 4: 0 = f - n/' (gf,x k + X + p(ff, - 8¹)
3: - (i P V.J.0.,..1.B)
5: receive X,, 0² from the global server
6: 0c+11 Loca/Train (X, 00,0 n K) send p,. to the global server end for
5: end for
7:
2 D- D-Uppate: (update dual variables)
8:
9:
0' +1
1 Eiept 0
Input: Nr,0% 0++1 0++1 pt
10:
x D-Uppatte oft1 10t1,00+,pp
Output: X
x _/2 Evee X411
1: if pt then
11:
2:
X A X
pa p0(0t 1 0¹)
g'+l_ = d 441
12:
3: else
13: end for
4: A = Xi + p1 0²)
14: return global average model
5: end if
A.2 Hyperparameters Selection
We first introduce the hyperparameter selections. To fairly compare the efficiency of the benchmarks, we fix the most of hyperparameters, including the initial global lcarning rate, the initial learning rate, the weight decay coefficient, and the local batchsize. The other hyperparameters are selected properly on a grid search within the valid range. The specific hyperparameters of specific methods are defined in the experiments. We report the corresponding selections of their best performance, which is summarized in the following Table 3.
The global learning rate is fixed in our experiments. Though Asad et al. [2020] propose to adopt the double learning rate decay both on the global server and local client can make training more efficient, we find some methods will easily over-fit under a global learning rate decay. For the weight decay coefficient, we recommend to adopt 0.001. Actually, we find that adjusting it still can improve the performance of some specific methods. One of the most important hyperparameters is learning rate
15

---

Table 3: Hyperparameters selections of benchmarks.
Grid Search
FedAvg
FedCM
SCAFFOLD
FedSAM
FedDyn
FedSpeed
global learning rate
[0.1, 1.0]
1.0
local learning rate
10.01. 0.1. 1.0]
0.1
weight decay
[0.0001. 0.001, 0.01]
0.001
leaminn rate decay butchsize
[0.995, 0.998, 0,9998,
0,998 50
0.998
0.998
0.998 50
0.998/1 20/30
0.998
[10, 20, 50, 100)
50
50
50
client-level momentum
[0.05. 0.1, 0.2, 0.5]
0.1
proxy coefficient
10.001, 0.1. 1.0]
0.000.001
0.1
SAM perturbation
[0.01, 0.05, 0.5]
0.05
0.1
SAM eps
[le-2, le-5, le-8]
le-2
all
Labal imbalance
Label Imbalance
44-
64-
0.-
90
Clients
Clients
Clients
(a) IID splitting.
(b) 1.0 splitting.
(c) Dir-0.1 splitting.
Figure 4: Label ratios under different splitting manners. Different color means the samples are in
different labels. We show the different splitting distributions total of 100 clients.
decay. Generally, we use d = 0.8 0.1 0.005 to select the proper d as decayed coefficient, which means the level of the initial learning rate will be decayed after 7 communication rounds. We follow previous studies to fix the learning rate within the communication round. Another important hyperparameter is the batchsize. In our experiments, we fixed the local interval which means the fixed local iterations. Due to the sample size being fixed, diffferent batchsizes mean different training epochs. Generally speaking, training epochs always decide the optimization level on the local optimum. A too-long interval always leads to overfitting to the local dataset and falling into the serious "client drift" problem [Karimireddy et al., 2020]. our experiments, we control it to stop when the local client optimized well enough, i.e., a proper loss accuracy. For the specific hyperparameters for each method, we directly grid search from the selections. For A-FedPDSAM method, the selections consistent with the FedDDnn and FedSpeed methods except for the learning rate decay is fixed as 0.998. To alleviate the "dual drift", we properly reduce the proxy coefficient for the FedDyn on those difficult tasks to maintain stable training.
A.3 Dataset and Splitting
We use the CIFAR-10 10/ / 100 datasets to validate the efficiency, which widely used verify the federated efficiency [McMahan et al., 2017, Karimireddy et al., 2020, Li et al., 2020, Xu et al., 2021, Durmus al., 2021, Gong et al., 2022, Wang al., 2022, Fan al., 2022, Caldarola et al., 2022, Sun al., 2023b,a, Li et al., 2023a, Fan et al., 2024a.b]. The total dataset of both contain 50,000 training samples and 10,000 test samples of 10 100 classes. Each a colorful image in the size of 32x32. We follow the training as the vanilla SGD to add data augmentation without additional operations.
Label Heterogeneity. For the dataset splitting, we adopt the label imbalanced splitting under the Dirichlet manners. We first generate a distribution matrix and then generate random number to sample each data. To further enhance the local heterogeneity, we also adopt the sampling with replacement, which means one data sample may exist on several clients simultaneously. This is more related real-world scenarios because of the local unknown dataset distribution. We generate the matrices in Fig. 4 to show their distribution differences. We can clearly see that Dir-0.1 I introduces a very large heterogeneity in that there is almost one dominant class client. Dir-1.0 handles approximately 3 classes in one client. Actually, in practical scenarios, label imbalance may be the most popular heterogeneity because we often expect both the local task and local dataset be still unknown to others. For instance, client may be expert on task A, and client may be an expert
16

---

on another task B. To combine the tasks A and B. if we can directly merge them with training policy without beforehand knowing the tasks, then it must further enhance local privacy.
Brightness Heterogeneity. To further simulate the real-world manners, we allow different clients to change the brightness and ratios of different color channels. This corresponds different sources of data collected by different local clients. We show some samples in Fig. 5 to show how different they are on different clients. Specifically, after splitting the local dataset, we will caleulate the average brightness of each local dataset. Then we generate a noise from Gaussian to randomly change the brightness and one of the color channels, which means that even similar samples have large color differences on different clients.
Client
.v
N(.1
x(o.1)
Raw Dataset
Figure 5: Introducing the brightness biases different clients. We calculate the average brightness control each sample to a proper state. Each client will randomly sample a Gaussian noise to perturb the local samples.
A.4 Additional Experiments
A.4.1 Some Training Curves
In Figure 6 we can see some experiment curves. From the (a), (b), (c), and (d), we can clearly see that the A-FedPD method achieves the fastest convergence rate on each setup. Due to the virtual update on the dual variables, we can treat those unparticipated clients as virtually trained ones. This empowers the A-FedlPD method with a great convergence speed. Especially on the IID dataset, due to the local datasets being similar (drawn from a global distribution). the expectation of the updated averaged models is the same as that of the updated local model with lower variance. Then we could approximate the local dual update as the global one. This greatly speeds up the training time. We also can see the fast rate of the FedDyn method. However, due to its lagging dual update, it will be slower than the A-FedPD method. As for the SAM variant, it introduces an additional perturbation step that could avoid overfitting. Therefore, its loss does not drop quickly because the additional ascent step.
From the (e), (f). (g), and (h), we can clearly see the improvements of A-FedPD and A A-FedPDSAM methods. From the basic version, A-FedPD could achieve higher performance due to the virtual dual updates. After incorporating SAM, local clients could efficiently alleviate overfitting. The global model becomes more stable and could achieve the SOTA results. We will learn the consistency performance in the next part.
17

---

Rounds
Rounds
Rounds
Rounds
(a) Loss IID.
(b) Loss Dir-1.0.
(c) Loss Dir-0.6.
(d) Loss Dir-0.1.
Accuracy of Global Mode
Accuracy of Giobal Model
Accuracy of Glbal Model
Acc of Glopal Model
Tacles
Teclng
Fechue
0.5
010
38
Rounds
Rounds
RO
Rounds
(c) Acc IID.
(f) Acc Dir-1.0.
(g) Ace Dir-0.6.
(h) Ace Dir-0.1.
Figure Loss and accuracy curves the experiments.
A.4.2 Primal Residual and Dual Residual
In the primal dual methods, due to the joint solution on both the primal and dual problems, it leads to an issue that both residuals should maintain a proper ratio. Therefore, the quantity of global updates in the training could be considered as a residual for the dual feasibility condition. The same, the constraint itself could be considered as the primal residual. Then we consider (3) objectives. The constraint is the global consensus level - 0, and the global update is gc+1 0², To generally express them, we define the primal residual pf - Σx |0 0f and the dual residual de p||0' 0--1 || Actually, the primal residual could be considered as the consistency, and the dual residual could be considered as the update. In the training, if we focus more on the dual residual, it leads to fast convergence on an extremely biased objective that is far away from the true optimal. If we focus more the primal residual, the local training cannot perform normally for its strong regularizations. Therefore, we must maintain stable trends on both p, and d, to implement stable training. In this part, we study the relationships between primal and dual residuals.
As shown in Figure 7, we can clearly see the lower stable ratio between the primal and dual residuals on the A-FedPD and A-FedPDSAM methods, which indicates that both the primal training and dual training are performed well simultaneously. However, the federated primal average-based methods, i.e. FedAvg and SCAFFOLD, focus more the primal training which leads to the dual residuals are too small (dual residuals measure the global update: primal residuals measure the global consistency).
18

---

Dual Residuals
Primal Residuals
Ratios of Primal/Dual
Fediwp
Fedlus
Festug
Fedzal
TeaCH
FedCM
SCAFFOLD
SCAFFOLD
SCARRUL
FedSAM
2.0
FedSAM
FodSAM
Fediiyn
FedDyn
Redtyyn
Fediipeed
FedSppesd
Redfooeed
AFLLTO
AR22PD
APraP
AFLOPOSAM
ARCIFDSAN
APcdPSSAM
03
0.5
0.-
Rounds
(a) Residuals on the CIFAR-I4 10 test.
Residuals
Primal Residuals
Ratios Primal/Dual
Fodiog
Fookee
20-
3.0
Afficto
Aflesro Afs:FDSAN
Afwdh0 AFedPOSAM
SA
20
25
1.2
10
120
620
622
201
8.00
Rounds
Rounds
Rounds
(b) Residuals the CIFAR-100 test.
Figure 7: Loss and accuracy curves the experiments.
A.4.3 Communication Efficiency
In this part, we learn the general communication efficiency. We fix local intervals, clients, participation ratios, and hyperparameters for faimess.. We select the different targets as the objective to calculate the communication efficiency.
Table 4: Communication rounds required to achieve the target accuracy.
CIFAR-10
FedAvg
SCAFFOLD
FedSAM
FedDyn
FedSpeed
A-FedPD
A-FedPDSAM
81%
345
156
1x
2.42x
1.45x
3.21
2.94x
3,82x
3.21x
83.5%
355
268
252
218
1x
1.31x
1.74x
1.85x
2.14x
CIFAR-100
FedAvg
SCAFFOLD
FedSAM
FedDyn
FedSpeed
A-FedPD
A-FedPDSAM
40%
772
162
572
173
222
123
126
4,76x
1.34x
4.46x
3.47
6.27x
6.12x
49%
677
495
421
303
220
1x
1.36x
1.61
2.23x
3.07x
Table 4 shows the communication efficiency among different methods on the CIFAR-10 / 100 dataset trained with LeNet. We calculate the first communication round index of achieving the target accuracy
19

---

for comparison. We can clearly see that the communication rounds required for training are saved lot on the A A-FedPD and A-FedPDSAM methods. It generally accelerates the training process by at least 3 CIFAR-10 10 and 6x on CIFAR-100 100 than the vanilla FedAvg method. Compared with the other benchmarks, our proposed method performs stably and efficiently.
A.4.4 Wall clock Time for Training Costs
Then we further study the wall clock time required in the training. We provide the experimental setups follows.
Platform: Pytorch 2.0.1
Cuda: 11.7
Hardware: NVIDIA GeForce RTX 2080 Ti
Table 5: Wall clock time required to train round (100 iterations) on ResNet.
FodAvg
SCAFFOLD
FedSAM
FodDyn
FedSpeed
A-FedPD
A-FedPDSAM
s/ round
22.06
36.01
39.21
34.03
56.10
37.61
60.63
1x
1.63x
1.77
1,54x
2.54x
1.70x
2.74x
Table 6: Wall clock time required to train I round (100 iterations) on LeNet.
FedAvg
SCAFFOLD
FedSAM
FedDyn
FedSpeed
A-FedPD
A-FedPDSAM
s/ round
9.82
11.42
12.53
11.76
13.61
11.71
13.90
1x
1.16x
1.27
1.19x
1.38x
1.19x
1.41
Actually, the LeNet is too small for the GPU and the training time does not achieve the capacity, which leads the close time costs in Table 6. We recommend referring the ratio the ResNet (Table 5), which is much closer to the real algorithmic efficiency.
20

---

B Proofs.
In this part, we mainly show the proof details of the main theorems in this paper. We will reiterate the background details in Sec.B.1. Then introduce the important lemmas used in the proof in Sec.B.3.1, and show the proof details of the main theorems Sec.B.3.2.
B.1 Preliminaries
Here we reiterate the background details in the proofs. To understand the stability efficiency, we follow Hardt et al. [2016], Lei and Ying [2020], Zhou et al. [2021]. Sun et al. [2023e] to adopt the uniform stability analysis our analysis. Through refining the local subproblem of the solution of the Augmented Lagrangian objective, we provide the error term of the primal and dual terms and their corresponding complexity bound in FL.
Before introducing the important lemmas, we re-summarize the pipelines in the analysis. According to the federated setups, we assume global server coordinates set of local clients C _ {i) to train one model. Each client has a private dataset S, = {Gr)) We assume that the global joint dataset is the union of {S) U US2 U ... ). To study its stability, we assume there is another global joint dataset that contains most one different data sample from C. Let the index of the different pair be (""; We train two global models H and fr on these two global joint datasets respectively and gauge their gaps during the training process.
Then we rethink the local solution of the local augmented Lagrangian function. According to the basic algorithm, we have:
-() = (2, 0²) - 1 0'1/2.
(12)
To upper bound its stability without loss of generality, consider adopting the general SGD optimizer to solve the sub- uub-problem via total K iterations with the local learning rate ry":
0 f 0 1/ (C, 1,k, X₁ 0¹) = 8 -n [oh + A$ + (0/,e 0¹)]
(13)
where k is the index of local iterations (0 S k < K).
B.2
Optimization
B.2.1
Important Lemmas
In this part, we mainly introduce some important lemmas adopted in the optimization proofs.
Motivated by Durmus al. [2021], we assume the local client solves the inexact solution of each local Lagrangian function, therefore have V (0 ) X + p(0+ 0¹) e, where can be considered as an error variable with |e||2 < e. This can characterize the different solutions of the local tot--prolless. We always expect the error achieve zero. Durmus et al. [2021] only assume that the local solution is exact and this may be not possible in practice.
Lemma ([Durmus et al., 2021]) The conditionally expected gaps between the current averaged local parameters and last averaged local parameters satisfy:
Ballo' +1 00112 < C
Ball0t+1 0'112.
SEC
Proof. According to the averaged randomly sampling, we have:
1 -1112
11
EE
Σ
0
1 EE Σ
110 1 -011
iEP
iEPL
1 F,
10
Σ Eel10t+1 0113.
P
iec
iEc
L is the indicator function as 1, 1 if
pt
else 0.
21

---

Lemma 2 Under Assumption and let the local solution be an c-inexact solution, the conditionally expected averaged local updates satisfy:
(1-1)) 41,2
-1 812
41,2 p² E.IIVS + 4e
2 p² C
E.10; - -11
(14) p²
p
iEC
REC
Proof. First, we reconstruct the update of the dual variable. From the updated rules, we have X; ー = p(0 0¹). From the first order condition of V f.(+t=) X p(0,tt] 04)
By expanding Lemma 11 in (Durmus et al., 2021], then we have:
Bell0 - -0/122
iEC
Eel10, 0 + 1 11112
P
IEC
4L
BBell0 - o' +
2E, 110 - 00112 +
4c p
<
+
p
C
REC
Therefore, we can reconstruct its relationship as:
(1-
41. 0²
1
E. 10
81.2 1 p²
Bel10: - -0'112
41.2 p²
Eg
V
| )|
4e
C
iEC
REC
This completes the proofs.
Lemma Under Assumption I, the conditionally expected averaged local consistency satisfies:
EELO
-
E2 10,10 0'
(15)
iEC
iEC
Proof. According to the update rules, we have:
Eg
10 +1
0 0²+1
1
1
E
0² + 00' - -0
C
C
IEC
REC
2
Egll0t+1 -01122 + 2E, O" - -
$
C
FEC
2
Σ
Be
0'112 + Σ iEC
E, 10 0'112
C
IEC
4
Eel10,+1 8112.
$
C
IEC
This completes the proofs.
B.2.2 Proofs
According to the smoothness, we take the conditional expectation on round and expand the global function as:
E2 100 ) -s(0')
< B. "1, -8'12 (V
4 1.,100
L
1
Σ
L
$1, 41
-1100 -0
1
Σ
(0.42 04) + 000-00
331
L 1, ++
1 -0'10 -
1
(4) + X -e) -
p
22

---

L
1B.110
Σ
V (i((ttt))
2
iEC
- 2
L
= - -0-112= + 1
E.l V
_
Σ
V (i(0
-
1
V (1)
2p
2p
iEc
$
L
B E,110*=1
- 02113 +
1
E EVIVV/(( v.
1
E,
V (('))1'
2
2p C
2p
sec
$
4 E
-01132+
L2
Eel10' - 0,
Er
| (0')))
2p C
2p
i50
$ 2/ |+ 2
L
L
1
Σ SEC
E2 110
1,+1112
1
E, V
l 1(0')12
2p
To simplify the expression, we define R2 = Eiec -01 = _ &iEc Be - -0'1/2. Actually from Lemma and 3, we can reconstruct the relationship as:
| } (1 413 R
E2
10 (1+ R
2p E. [ ||?
بيية R + 2 E.IV || +
Let the second inequality be multiplied by and add it to the first, we have:
[110
[0(1-
4T2
L.
Es
1+
R4
12
2
$ r0 +
32L² p² R4-1
1
4qL²²
E 100') + p2
4ge
2p
p2
Then we discuss the selection of q. First, let Then we let the following relationship hold:
19 g²
> 0 be positive, which requires g < gL.
2p
of (1
41,2
L
L
321,2
p²
2
1
p
=
p²
I(o2+ah)
Thus it requires 2q-
< 41 We can solve this to get the range of the coefficient, as:
p" 361*
p² 41 - 36I. - 4I. > 0.
Then O(L3) satisfies all the conditions above.
Therefore, let उ27, and then q
3212 / 1. By further relaxing the last coefficient we have:
E, [ 1 R. 100)
1 R
P P
8L2P"
Taking the full expectation and accumulating the above inequality from / = to T - 1, we have:
B < f(0')
1(00
Ro
Rr
T
PT
8T2p
p [5(0') pr Ro
8L2p' p
In the last inequality, f* is the optimum of the function f. For the R_1 term, we have Ro = t Eiec E, 100 - 0 l|2 = t Evec EE - 001 for 0 0"
Discussions of the optimization errors. We show some classical results of the generalization errors in the following Table 7. Zhang et al. [2021] provides a first optimization analysis for the federated primal-dual methods. However, it requires all clients to participate in the training in each
23

---

round (do not support partial participation). Wang et al. [2022], Gong et al. [2022] proposes to adopt partial participation for the federated primal-dual method and adopt a stronger assumption on the local solution. It proves that even though each local solution is different, the total optimization error can be bounded by the average of the trajectory of each local client. However, the initial bias may be affected by the factor C under some special learning rate. Durmus et al. [2021] further provides a variant to calculate the global dual variable. It provides lower constant for the term, which is DD (faster than CDD in FedADMM), Our proposed method A-FedPD updates the virtual dual variables, which could approximate the full-participation training under the partial participation case. Therefore, compared with the result in [Durmus et al., 2021], we further provide a faster constant for the term D ( x faster than FedDyn on the first term when p is selected properly). If the initialization bias D dominates the optimization errors, i.c. training from scratch, A-FedPD can greatly improve the training efficiency.
Table 7: Optimization rate of federated smooth non-convex objectives.
Assumption
Optimization
reduce dual-drift?
Zhang et al. [2021]
smoothness, e-inexact solution
O
T
+ +()
Hu et al. [2022]
smoothness, éi, -inexact solution
0
C2 PT
+ CT
Σ Ei,e)
Durmus et al. [2021]
smoothness, exact solution
our
smoothness, e-inexact solution
0 + Ra
7
+
Our Improvements. In [Zhang et al., 2021], it must rely the full participation. In [Gong et al., 2022. Wang et al., 2022], the impact of the initial bias is E rely on the local exact solution, which is extremely ideal condition. Our results can achieve the (++)
p times. In [Durmus et al., 202 I], it must
rate under the general assumptions and support the partial participation case.
B.3
Generalization
B.3.1
Important Lemmas
In this part, we mainly introduce some important lemmas adopted in our proofs. Let be the corresponding variable trained on the dataset and then we can explore the gaps of corresponding terms. We first consider the stability definition.
Lemma (Hardt et al. [2016] Under Assumption and 2, the model 4 and êT are generated on the two different datasets and Ć with the same algorithm. We can track the difference between these two sequences. Before we first select the different sample pairs, the difference is always Therefore, we define an event Ç to measure whether 0² = 6t still holds at To-th round. Let H = supo.g E(),E) < +oo, if the algorithu is uniform stable, we can measure its uniform stability by:
cG sup E [F -)) -S(OT,)) .5) s GEI -0T c.O.E
HP
sup
(16)
CS
Proof. By expanding the inequality, we have:
E [1100" 5 - -(0",E))
< P()E [1(00 ,E) -(0'" .EN + P(5)B [IF(0 .E) (10 5*]
GR |10 - -0 + HP((S).
Here assume that the difference pairs selected on T-th round, therefore we have:
Pro
P({9) = P(T S T0)
P(r t) t) Σ
P(i E P')
CS
1=0
1=0
This completes the proofs.
24

---

Specifically, because C only differs from on client i", we could bound each term on two different situations respectively.
We consider the difference of the local updates on the client (i + it).
Lemma Under Assumption we can bound the difference of the local updates on the active client i (i + ).). The local update satisfies:
(0 -0") (0iut1- - -0) n/' KLEBI0 0-1 + KE -Xil-
(17)
Proof. Reconstructing (q.(13) we can get the following iteration relationship:
07,,+1 6r = (1-n'p) p) (0
-0)) n/' (gi,e + X!).
On each client (i + )²), each data sample is the same, thus we have:
E|| k01, 0¹) - (0ix+1 01)
Ell (1 r/ p) [60 8*) (0 - }} n (gi. - k1,k) 1/ (x: X:)
< (1 - npp)) p) |E|| (0f 0¹) (0% k 8*) | + 'f LB.. - Nil + +1) 1 X3I
S <1 - n² PL) [B|| (0 0²)
(0 0²) nj LIEIIO* - 0011 + n E'EI Atll
where PL L is constant.
Unrolling the recursion from k = 10 K 1, and adopting the factors 0.+1 0i and 02,0 0% have:
E| (0,+1- - 0²) - (0,42 -0+) || = TE|| (0 - 0²) -00% - 0-) II
K- (1 of pL)
B|l (0%.0 - 8²) - -0% - -81)
k=0
K-1
K-1
II (1 pi)))) j=++1
(LE) - 0011 + E A51)
+
k=0
K-1
K
II (1 - p' j=b+1
[LEIIO - 0.11 + E -x111
K=
Simplifying the relationships, we have:
Ell (05+1-00 (0, 0¹) || 1- (1 (1-11'pL)* (LEIJO - +EI 1-1---180 -Xal)
Pr.
S S <n'KLE 0" + KEIA Xi11
The last inequality adopts the Bernoulli inequality (1+ x) 21+ Kr for K Z and -1.
Then we consider the difference of the local updates on client i*
Lemma 6 Under Assumption I and 2, can bound the difference of the local updates on the active client i The local update satisfies:
Ell -0) - -00%441- - -0)) s KLL 0' - Mil + 2n KG
(18)
Proof. Reconstructing Eq.(13) we can get the following iteration relationship:
0 - - (1- (0) - -0) - r/" (gi,r + +)).
Lemma 5 shows the recursive formulation when we select the same data sample. However, on the client it, it also may select the different sample pairs. Therefore, first study the recursive
25

---

formulation of this situation. When the stochastic gradients are calculated with different sample pairs (,,E), we have:
E (0) i,4l 0²) (0/:11 - 87)
E|| (1 pp [00k 0²) (0i -0'] n/ (1i. -bi.)) nn' (x: - 21)
s (1-nn p) E|| (0i, 0²) - (0i - 00) 11+ 2n' G B' - XiI-
For every single sample, the probability of selecting the Ey- 3.. Therefore, combining Lemma 5, we have:
E1 (0/, - -0') - (0i,411 - -8-) 11
(1 1
8 [1- n/ PL) B|| (02,5- - -0-) - (0% - 8y) + n' LEI + -X51]
+ * g (1 - p) Eil (0 -0') - -08% -0¹ || + 2n + 11 -X81
< (1 11- pr.) B|| (0t 0²) - (0t - + LBI - 6-1 + n/ B'EI - 2111 + 2n//
Generally, we consider the size of samples S to be large enough. In current deep learning, the dataset adopted usually maintains even millions of samples, which indicates that 1 $ 1.
Unrolling the recursion from lo to K 1 and adopting the f =fi,x and 0%,00 6*, we have similar relationship:
(0!+1 -0¹) - (,++1 - 0²) || E|| (0 - 0¹) - (0% - 0¹) ||
|
K
II (1 - pp) f=k+1
K-1
LEII0 - 8011 + E X11 + 2G
5
k=0
Simplifying the relationships, we have:
El (0, - -00) -08, - -80) |1 - 1- 1- (1))'
[EE|0' 0011 -001--0111 + EII - X + 2G
PL
S 1) KTKE -011 + - X/11 2 KG
The last inequality adopts the Bernoulli inequality.
B.3.2 Proofs
Table 8: Notations in the proofs.
Symbol
Formulation
Description
A
1E|00* 0¹11
difference of the global parameters discrete difference of the local parameters discrete difference of the dual variables discrete difference of the local updates
8t
C Σ iEc E X
Σ
iec El10; 1/11
at
n² 1/ Eiec E
[
0 1)
(0)
0 !Ill
In this part, we mainly introduce the proof of the main theorems. Combining the local updates and global updates, we can further upper bound both the primal and dual variables. Before proving the theorems, we first introduce the notations of updates of the global parameters and dual variables in Table 8.
A measures the difference of the primal models during the training. 8 the local separate difference when the local objective is solved. o¹ measures the difference of the dual gaps. T' measures the
26

---

difference of the local updates, which is also an important variable to connect global variables and dual variables. our proofs, we first discuss the process of the primal variables and dual variables respectively. Then we can use the æ term to construct an inequality to eliminate redundant terms, which could further provide the recursive relationship of the primal variables and dual variables separately. Next, we introduce these three processes one by one.
From the global updates, according to the global aggregation and let 11 be the indicator function, we have:
A A++ 11 11+1||
E1l
1
Σ
x R 0 0 || T, +
0,+11)
1 p +
x,
)
1 p
E
Σ
x
++1 - x;
*t+1
||
IEC
1
B110+t1
0,+
1
Σ
1
+1
++1
l| 8 + 1 -
C
c
IEC
iEC
From the dual updates, according to the local dual variable, we have two different cases. Combing the D- D-Update we have:
1
Σ
X
C
1
Σ
p00t 04) + T
1 Σ p 0²)
C
EEC
IEC
iEP
P
x
P
0*) +
C C
P
p(0 - -8 = p(0-11 0¹)
c
C
iEC
Considering the randomness of selecting Pt and expectation A, we have g++l S of + pm
Here we add the additional definition of the unparticipated clients. We let the 0.+1 = 0c where i á pt, which enlarge the summation from pt to C. Then we summarize Lemma and 6 as the following formulation:
n 1+1
1
El| (0!+1 - 8¹) (0.+1 0¹) 11 1 Σ
El (0 00) (00+1 -8)
8') II
C
C
SEC
2n KG
< r/
A - 8'11 + 7/
Σ
E - X|I +
= ci A + c2o' t
C
CS
SEC
Finally, we can directly expand the π term by the triangle inequality:
1
ge+1
- 0.+211
C
iEC
<< Σ
1
E|| (0 8¹)
(0)t 8¹) 11+
Σ
El
0'1l xx s+1 + A
C
iEC
Combing the above recursive formulations, we have:
A++ s 5++1 + 1ott1
al+1
S a² + ptt+1
ge+1
I sttt1 A
n'+1 SqA' + C20 + C3.
By multiplying three additional positive coefficients a, B, and y on the last three inequalities respectively, and adding them to the first one, we have:
A++1_ (x (a-1) 1 r+ (B 1) 1 + (7 ap 3) +1 S (8 701) A + (a + 7702) of + 703- -11
27

---

By observing the LHS and RHS of the inequality, we notice that it could be summarized as recursive formulation of A and of terms by selecting proper coefficients. Therefore, let the following conditions hold,
B - 1-22 0,
7- - 3 2 0.
By simply selecting the minimal values
and 7 = + ap, we have:
1) s+ o = = a g + (3 8 + - 3) a
A [+|
+
a
$ (3 + 701) A' + (02) 0f + 703
a (1 + ap)n'K
2m/ KG CS
$ (1 KL)
A'
1 (1 + ap)n' KL
Here we further let a 1 a+(++ap)n K this, we can solve the following inequality:
(( KT. to support the above recursive relationships. To satisfy
L(ap)² - -(ap)= ( T/'K 20.
From the fundamental knowledge of quadratic equations, we know that there must exist positive number belonging interval [x +o0| satisfy the condition, where + is the larger zero point
of the equation Lx - pr - 10--(++ pL+ ,²x) = 0. We can solve x+ p+ 42 5tx)
2L
(
K <1+ L 2 +x 7 TKK When we select the proper op 2 xt, the above inequality
2L always holds. This also indicates that the previous definition 1 + ap two constant coefficients, relationship as:
2 - +. Here we denote ap
and
simplify the final iteration
A [+] + app < (1 +1+KkK (A' + tapo') + 7hs KG KG
CS
Unrolling this from 1 = To T and adopting the factors of A To 0 and A 0, we have:
(1) When the global learning rate selected as constant ry ná where the initial learning rate vá S KL
2 KG
2G (1+
+ < Σ (1+
CS
LCS
t=ro
no (2) When the global learning rate is selected as a decayed sequence ry' = 1+1 learning rate 7o
where the initial
S
a where μ is a positive constant, we have:
7
T
T-1
2r1rKG CS(++1)
T-1
2G
T + aPp &
Σ
II
1+
S
Σ cxp
CS(++1)
1=
2
K KG KL
KL
T-1
1+mLKKL
2G LCS
T
uL
CS
t+1
TO
Here we mainly focus on the case of the decayed learning rates. According to Lemma 4, we have:
HP CS
2G2
T aL
HP
Ea S GAT +
LCS
TO
CS
By selecting the proper To =
2G HPL
FluE
TI
we can get the minimal error bound as:
2
(2G2
ITPE
EG < CS
(HPT) 1426.
L
28

---

Discussions of the generalization errors. We show some general results of the generalization errors in the following Table 9. We prove that the federated primal-dual family can benefit from the local interval K than the vanilla SGD methods, which is one of the key properties of the primal-dual methods.
Table 9: Generalization enror bounds of smooth non-convex objectives.
Assumption
Generalization
Hardt et al. [2016]
Lipschitz
0 (KT))
Mohri al. [2019]
Lipschitz, VC
TK TK
Hu et al. [2022]
Lipschitz, Bemsteii
Wu et al. [2023]
Lipschitz, Stochastic
CvCs Ph. (PKT) STRL C8
Sun et al. [2023d]
Lipschitz
Lipschitz
0 (PT) ITAZ
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We illustrate the dual drift issues and propose the A-FedPD with the virtual up- dates of the dual variables. We prove its efficiency from the optimization and generalization analysis. Extensive experiments are conducted to validate its performance.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the storage cost limitations at the beginning of the Appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
30

---

Answer:
[Yes]
Justification:
We introduce all assumptions in our analysis and clearly note their adaptivity.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We submit our code demo to reproduce the experiments and all hyperparame- ters can be found in our paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
31

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We submit the code demo to reproduce the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/ Baalliic/uiidee/ooSSSuubaae wwi.iiiisssiiiiiioooooooommiiiii for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ cttppssccppbbccccc/peecepcpccclh hwwubblc/guide..... /Ct////oooeeeeeeeeeeeeeeee /otaai/eedee//eeeeubiiiiiiee
onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We detail all selections of each hyperparameter in our paper with corresponding experiments. Some of them are based on the previous classical work, and we also note where they are adopted.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In the performance comparison and main table, we report both mean accuracy with its variance under different random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We submitted the code demo and it has the instructions for reproducing the experiments, We report the hardware sources and time cost details in Appendix A.4.4.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
cttprippp.cppppppie htc//ublic//Etiie htt//Etthiiisiieeeeeeeeeeeeee esGuidelinees
Answer: [Yes]
Justification: Ethics.
This research conducted in the paper conforms with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There no obvious socictal impact of the work performed since our research focuses more general studies the FL frameworks.
Guidelines:
33

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite all papers on the models and datasets used in our paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
34

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasttss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
35

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "vdFbbjTjtd", "reviewer": "Reviewer_6Q4p", "summary": "This paper studies the primal-dual-based FL algorithm with partial client participation. The inactiveness of the local clients causes both local primal and dual variables to drift from their expected value and slows down FedPD's convergence. This paper provides a fix to the FedPD algorithm in the partial participation setting by moving the dual update to the server side and allowing the server to store the dual variables. The theoretical result shows that A-FedPD can achieve the same convergence rate as FedPD ($O(1/T)$), and the error bound is better than the prima-only FL algorithm. Numerical results also show that the proposed algorithm achieves the best accuracy in different settings.", "questions": "How would A-FedPD (and other algorithms) perform when the communication patterns of different clients are different, i.e., $\\mathbb{E}_P[\\theta_i] \\neq \\bar{\\theta}$?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Soundness: the theoretical analysis provides a clear convergence and generalization result for the proposed algorithm. Numerical results also show that the proposed algorithm outperforms the existing algorithms on different models and data distributions.\n2. Clarity: the paper is clearly written with adequate reference to prior works and clear notations and results.", "weaknesses": "1. Memory inefficiency: The algorithm requires saving the local dual variable of all clients. When C is large, this might cause a large memory cost on the server, especially in the FL setting. This might restrict the proposed algorithm's use case. This is discussed in the limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: The algorithm requires saving the local dual variable of all clients. When C is large, this might cause a large memory cost on the server, especially in the FL setting. This might restrict the proposed algorithm's use case. This is discussed in the limitations.**\n\nThank you very much for pointing this out. As we discussed in the limitations, although our proposed method achieves state-of-the-art (SOTA) performance, it could be further improved in scenarios with a very large client scale, such as cross-device federated settings. Our paper primarily reviews and summarizes the issue of experimental non-stability caused by increased model scale and more complex datasets in FedADMM-like methods. Then we organize this issue between the primal and dual problems as dual drift. Virtual dual updates are a simple and effective solution, and the storage cost is acceptable in cross-silo federated scenarios. We also look forward to further researching more efficient techniques for cross-device federated scenarios in the future.\n\n\n**Q1: How would A-FedPD (and other algorithms) perform when the communication patterns of different clients are different, i.e., $\\mathbb{E}_P[\\theta_i]\\neq\\overline{\\theta}$?**\n\nThank you very much for raising this interesting question. First, we clarify that the vanilla definition of $\\overline{\\theta}$ is not the absolute average $\\frac{1}{P}\\sum \\theta_i$, but a weighted average $\\sum p_i \\theta_i$ where $p_i$ corresponds to the importance. In most work, the global objective is set as $F(w)=\\frac{1}{m}\\sum f_i(\\theta)$, yielding that the global consistency we are solving for is simplified on the absolute average form.\n\nTherefore, based on your question, the corresponding issue I understand is: (1) global objective is still $F(w)=\\frac{1}{m}\\sum f_i(\\theta)$ so the global consensus is still the absolute average form $\\overline{\\theta}$; (2) due to certain algorithm designs, such as importance sampling or client dropout, the sampling probability $p_i$ for each client is no longer consistent with the original global objective. This generates a new gap between the true global objective and the constructed objective.\n\nThis discussion requires some supporting assumptions, which we will briefly discuss here. From the perspective of optimization, the constructed objective should play a similar role of the vanilla global objective which can guarantee the training process converges. Under this condition, the gap between $\\mathbb{E}\\Vert\\nabla F(\\mathbb{E}_P[\\theta_i])\\Vert$ and $\\mathbb{E}\\Vert\\nabla F(\\overline{\\theta})\\Vert$ must be upper bounded and can deminished to zero. We refer to this as \"different but bounded\". We have not thoroughly derived the impact that the distribution $P$ might have on the optimization results. However, given that the optimization results still converge, we can assume that the gap here remains bounded during training. Thus, adopting $\\overline{\\theta}$ is still applicable, but with an additional error term at the final convergence rate.\n\nThere is another scenario that corresponds to this, which is the asynchronous setup. This situation appears to be more complex, but we believe we can draw on some ideas from asynchronous distributed ADMM methods [X1, X2]. Some related techniques like \"partial barrier\" and \"bounded delay\" can be introduced to mitigate the risk of unstable updates. The core idea is to specify the error between the global objective and global consensus, and then consider further optimization of this error.\n\nWe think this would be a good academic perspective, and indeed a topic worth exploring further in the future. To further answer this question in detail, we may need more conditions and problem definitions for a more specific analysis. We hope that our current response addresses your concerns.\n\n[X1] Zhang R, Kwok J. Asynchronous distributed ADMM for consensus optimization[C]//International conference on machine learning. PMLR, 2014: 1701-1709.\n\n[X2] Hong M. A distributed, asynchronous, and incremental algorithm for nonconvex optimization: An ADMM approach[J]. IEEE Transactions on Control of Network Systems, 2017, 5(3): 935-945.\n\n\nThank you again for reading our rebuttal. If you have any further questions, we would be very happy to continue the discussion, as it will help further refine our submission.", "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": "lC6MiLidOx", "reviewer": "Reviewer_YYQB", "summary": "A primal-dual-based federated learning algorithm (A-FedPD) is proposed to mitigate the drift of local dual variables. In federated learning with partial participation training, the local dual variables in inactive clients can be drifted. To mitigate this issue, the propose A-FedPD would be effective since the local dual variables in unparticipated clients are aligned with the global average models. Through extensive experiments, including nonconvex neural network models, the effectiveness of the A-FedPD was empirically investigated.", "questions": "(Q1) Could you provide proof sketch for theoretical analysis in Sec. 4? I would particularly like to know about the novel points in comparison with analyses in prior studies, such as FedPD. \n\n(Q2) On line 309, it is written that “we freeze most of the hyperparameters for all methods,” however these were searched in the list written in the Grid Search column of Table 3, right? I think it would be better to clearly write in the main paper that a hyperparameter search was conducted (see Appendix).\n\n(Q3) In Figure 2(b), it seems that accuracy is lower when the local interval is short. Does the total number of updates differ according to the local interval?", "limitations": "Limitations are noted in the Appendix. Social impact is not mentioned.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(S1) Simple but effective method: It is well known that the local dual variables in unparticipated clients can be drifted in the primal-dual based federated learning algorithms. The idea of modifying the unparticipated local dual variables to bring them closer to the global model is simple but effective. \n\n(S2) The proposed Algorithm 1 has been theoretically analyzed under certain assumptions, demonstrating a near-optimal convergence rate. One point of dissatisfaction is the comparison of convergence rates with several primal-dual based methods that will not be affected by dual drift in Table 7. Such an important results are to be included in the main paper.\n\n(S3) The effectiveness of the proposed method has been validated through several image classification benchmark tests using neural network models. Its robustness against various stresses (participation ratio, local interval, data heterogeneity) has also been empirically investigated.", "weaknesses": "(W1) In the experiments of Sec. 5.2, there seems to be no significant difference between the proposed method FEDPD and the comparison method FEDSPEED. The reviewer has serious concerns about this point. Without introducing SAM, can the superiority not be empirically demonstrated?\n\n(W2) In addition, the consideration of comparison methods in Sec. 5.2 seems insufficient. FEDSPEED performs better, but why is this? It also compares with primal methods such as SCAFFOLD and FedSAM, but why is the proposed method better than these methods?\n\n(W3) Some relevant literature might be missing.\n\n[a] R. Pathak et al., “FedSplit: An algorithmic framework for fast federated optimization,” NeurIPS 2020.\n\n[b] G. Zhang et al., “Revisiting the Primal-Dual Method of Multipliers for Optimisation Over Centralised Networks”, IEEE Transaction on Signal and Information Processing, pp. 228-243, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: The reviewer has serious concerns about this point. Without introducing SAM, can the superiority not be empirically demonstrated?**\n\nFedSpeed method essentially uses **a variant of the local SAM optimizer.** To illustrate this, we can recall its implementation:\n$$\ng_{i,k,1}^t = \\nabla F_i(x_{i,k}^t,B),\n$$\n$$\ny_{i,k}^t = x_{i,k}^t + \\rho g_{i,k,1}^t,\n$$\n$$\ng_{i,k,2}^t = \\nabla F_i(y_{i,k}^t, B),\n$$\n$$\ng_{i,k}^t = (1-\\alpha)g_{i,k,1}^t + \\alpha g_{i,k,2}^t.\n$$\nThe ascent learning rate is set as $\\rho=\\frac{\\rho_0}{\\Vert\\nabla F_i\\Vert}$. Then we have:\n$$\ng_{i,k}^t = (1-\\alpha)\\nabla F_i(x_{i,k}^t,B) + \\alpha\\nabla F_i(x_{i,k}^t + \\rho_0\\frac{\\nabla F_i(x_{i,k}^t,B)}{\\Vert\\nabla F_i(x_{i,k}^t,B)\\Vert}, B).\n$$\n**It is a combination of the SGD gradient and the SAM gradient, the second part is actually the SAM gradient.** Therefore for a fair comparison, from the perspective of local optimizers, the corresponding version of FedPD/FedADMM/FedDyn is A-FedPD, while the corresponding version of FedSpeed is A-FedPDSAM (both of them adopt SAM-based optimizer in the local client). As observed by the reviewer, our method makes the performance of SGD-based optimizers approach that of SAM-based optimizers, which is a significant improvement.\n\n**W2: FEDSPEED performs better, but why is this? It also compares with primal methods such as SCAFFOLD and FedSAM, but why is the proposed method better than these methods?**\n\nThank you for pointing out this. In W1, we have already explained above why the FedSpeed method is superior to A-FedPD, primarily because its local optimizer is essentially a variant of SAM. For a fair comparison, it should be compared with the variant A-FedPDSAM.\n\nAs for the second question, when the FedDyn method was proposed [X1], it already summarized that due to the correction of the dual variable, **local models will converge to the global model.** This means that the primal-dual methods will adjust the local heterogeneous objective to ultimately align with the global objective. Our proposed method is primarily designed to address the training instability issues and some inherent shortcomings in primal-dual methods. For clearer comparisons, we classify some methods and list some results from Table 3.\n\n|    | type  | local optimizer | Acc in Dir-1.0 | Acc in Dir-0.1 |\n|  :----:  | :----:  | :----:  | :----:  | :----:  |\n| SCAFFOLD  | primal | SGD | 83.61 | 78.66 |\n| FedDyn  | primal-dual  | SGD | 84.20 | 79.51 |\n| A-FedPD | primal-dual  | SGD | 84.94 | 80.28 |\n| FedSpeed | primal-dual  | SAM | 85.11 | 80.86 |\n| A-FedPDSAM  | primal-dual  | SAM | 85.90 | 81.96 |\n\n[X1] Acar D A E, Zhao Y, Navarro R M, et al. Federated learning based on dynamic regularization[J]. arXiv preprint arXiv:2111.04263, 2021.\n\n**W3: Some relevant literature might be missing.**\n\nThank you for pointing out these two important works. We will add them in the Related Work.\n\n**Q1: Could you provide proof sketch for theoretical analysis in Sec. 4? I would particularly like to know about the novel points in comparison with analyses in prior studies, such as FedPD.**\n\n(1) For optimization: [X2] provides classical proofs by independently bounding each term in the smoothness inequality, ultimately forming the final convergence conclusion. However, due to the complexity of the intermediate variables and relationships that need to be analyzed, the proof introduces a large number of constants. Then FedDyn employs a more refined technique [X1]. Instead of independently bounding each term, the proof in FedDyn combines the global update gaps and the local update gaps by a specific coefficient, yielding an arithmetic sequence. However, proofs in FedDyn must rely on the assumption of the local exact solution, i.e. $\\nabla L_i=0$. Clearly, this is overly idealized, as optimization will always introduce some errors. Therefore, to make the proof process more general, we adapt the assumption of gradient error from [X2], i.e. $\\nabla L_i=e$ where $e$ is treated as a bounded error. Our proof extends the simplified version of FedDyn to a more general version that allows for local inexact solutions and re-evaluates the necessary conditions for constructing the combined terms.\n\n(2) For generalization: **To our knowledge, current works have not provided generalization analysis for federated primal-dual methods.** We provide error bounds based on stability analysis here and prove that the generalization error bound of our proposed A-FedPD is lower than the FedAvg method. The main property is reflected through Eq.(10) in our paper. The local updates in primal-dual methods can be decayed by a coefficient less than 1 ($1-\\eta^t\\rho$), which implies fewer stability errors compared with the FedAvg method.\n\n[X1] Acar D A E, Zhao Y, Navarro R M, et al. Federated learning based on dynamic regularization[J]. arXiv preprint arXiv:2111.04263, 2021.\n\n[X2] Zhang X, Hong M, Dhople S, et al. Fedpd: A federated learning framework with adaptivity to non-iid data[J]. IEEE Transactions on Signal Processing, 2021, 69: 6055-6070.\n\n**Q2: I think it would be better to clearly write in the main paper that a hyperparameter search was conducted (see Appendix).**\n\nThank you for pointing out this. We will add the sentence \"Detailed hyperparameter search was conducted (see Appendix A.2)\" in section 5.1.\n\n\n**Q3: In Figure 2(b), it seems that accuracy is lower when the local interval is short. Does the total number of updates differ according to the local interval?**\n\nThank you for this question. In the experiments of Figure 2 (b), we fix the communication rounds as $800$ and change the local intervals from $[10,20,50,100,200]$. Since the learning rate is decayed by each communication round, we must ensure that the learning rate is reduced to the same after all experiments are finished. We will further clarify the experimental setup.\n\nThank you again for reading our rebuttal. If you have any further questions, we would be very happy to continue the discussion with you.", "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": "TEl7jE5y9U", "reviewer": "Reviewer_b9A4", "summary": "This paper investigates the issue of dual drift caused by the mismatch between primal and dual variables when using partially participated training in federated learning (FL). It proposes a novel method, A-FedPD, which employs virtual dual updates to mitigate these negative impacts. Comprehensive theoretical analysis and extensive experiments are presented to verify the effectiveness of the proposed method.", "questions": "The same with the weaknesses part.", "limitations": "The same with the weaknesses part.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The experiment in Figure 1 vividly illustrates the source of defects in primal dual methods under partial participation.\n2. The study presented in this paper is novel. Federated primal dual methods have long exhibited varying degrees of instability in experiments. The analysis based on dual drift provided in this paper is robust and useful.\n3. The quadratic term in the primal dual method is used in this paper to obtain a reduced form of the stability bound in the iterative process, ultimately achieving a constant bound in Equation (10). This demonstrates that the proposed method is superior to the federated averaging method in terms of generalization under the same training process. This conclusion is broad and can be extended to other primal dual methods.\n4. The experiments were solid and comprehensive in their analysis. In terms of both communication efficiency and wall-clock time testing, the A-FedPD method shows strong performance.", "weaknesses": "1. What is the variant A-FedPDSAM? I didn’t see an introduction to this algorithm in the text; please remind me if I missed this part.\n2. The performance of the algorithm is improved by trading space for time. During a global update, storing the dual variables requires considerable resources. Although federated learning primarily considers communication bottlenecks, this still increases server-side consumption.\n3. I noticed that the FedDyn column in the main table indicates failure. Were all hyperparameters tested in the experiment? There should be an additional discussion to clarify whether this failure is a special case or not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: What is the variant A-FedPDSAM? I didn’t see an introduction to this algorithm in the text; please remind me if I missed this part.**\n\nDue to space constraints in the main text, we have noted at the bottom of page seven (in the first paragraph where the Experiments section begins) that the method A-FedPDSAM is introduced in appendix A.1.\n\nActually, A-FedPDSAM is a straightforward but useful variant to improve the generalization efficiency in the experiments. The vanilla A-FedPD adopts the SGD as the local optimizer to solve the local lagrangian objective. While in A-FedPDSAM, we use SAM [X1] as the local optimizer to solve the local lagrangian objective. The design of SAM can provide better generalization performance. We list the main differences in the following.\n\nLocal SGD optimizer:\n$$\n\\theta_{i,k+1}^t=\\theta_{i,k}^t - \\eta^t(\\nabla f_i(\\theta_{i,k}^t,B) + \\lambda_i + \\rho(\\theta_{i,k}^t - \\theta^t)).\n$$\nLocal SAM optimizer:\n$$\n\\theta_{i,k+1}^t=\\theta_{i,k}^t - \\eta^t(\\nabla f_i(\\theta_{i,k}^t + \\rho\\frac{\\nabla f_i(\\theta_{i,k}^t,B)}{\\Vert\\nabla f_i(\\theta_{i,k}^t,B)\\Vert},B) + \\lambda_i + \\rho(\\theta_{i,k}^t - \\theta^t)).\n$$\nOther operations are essentially consistent with the A-FedPD method.\n\n\n\n**W2: The performance of the algorithm is improved by trading space for time. During a global update, storing the dual variables requires considerable resources. Although federated learning primarily considers communication bottlenecks, this still increases server-side consumption.**\n\nThank you very much for pointing this out. As we discussed in the limitations, although our proposed method achieves state-of-the-art (SOTA) performance, it could be further improved in scenarios with a very large client scale, such as cross-device federated settings. Our paper primarily reviews and summarizes the issue of experimental non-convergence caused by increased model scale and more complex datasets in FedADMM-like methods. Then we organize this issue from the perspective of symmetry between the primal and dual problems as dual drift. Virtual dual updates are a simple and effective solution, and the storage cost is acceptable in cross-silo federated scenarios. We also look forward to further researching more efficient techniques for cross-device federated scenarios in the future.\n\n\n**W3: I noticed that the FedDyn column in the main table indicates failure. Were all hyperparameters tested in the experiment? There should be an additional discussion to clarify whether this failure is a special case or not.**\n\nWe conducted all hyperparameter searching as shown in Table 3 (page 21) and tried almost all possible hyperparameter combinations. In fact, we also observed that while FedDyn performs reasonably well in CIFAR-10 experiments, it has a very high requirement for learning rate decay, necessitating a very slow learning rate decay. However, on CIFAR-100 (where the model structure and tasks become more complex), its stability drops sharply, requiring continuous reduction of the penalty term in the Lagrangian function to maintain stability. This observation inspired us to consider whether the asymmetry between the primal and dual objectives is causing this instability. When the penalty coefficient decreases to nearly zero, the dual variables almost stop updating and remain the initial zero vector, causing the entire Lagrangian function to nearly degenerate into the original function $f_i(\\theta)$. This phenomenon can also be observed in the experiments reported in [X1]. We also encountered similar issues in the FedADMM experiments. This is not a coincidence or an anomaly, but a genuine issue.\n\n[X1] Xu J, Wang S, Wang L, et al. Fedcm: Federated learning with client-level momentum[J]. arXiv preprint arXiv:2106.10874, 2021.\n\nThank you again for reading our rebuttal. We are also honored to have this discussion with you, which has made our submission more complete. If you have any further questions or issues to address, we would be very happy to continue discussing them with you.", "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": "Wt2CBxvIgJ", "reviewer": "Reviewer_c2hH", "summary": "The authors propose an algorithm for distributed optimization of a sum of nonconvex smooth functions, with partial participation. They obtain a O(1/T) rate.", "questions": "* Theorem 1 \"let rho > O(L^3) be positive with lower bound\": what does it mean ?\n\n* rho proportional to $L^3$ is weird, the left hand side and right hand side of (8) are not homogeneous. Looking at the proof, Line 987: is is not clear at all what the condition on rho is.\n\n* line 3: \"randomly select active clients set\" : do you mean choose a subset of size P uniformly at random?\n\n* Why does the number P of active clients not appear in Theorem 1? This is strange.\n\n* Line 972: how do you get the factors 4 and the 2, this looks like Young's inequality but not clear at all.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The study of convergence of algorithms adapted to federated learning is an important topic.", "weaknesses": "* There is no discussion of the O(1/T) rate in Theorem 1 with respect to existing results, for instance on Scaffold. I don't think the method improves on the SOTA. \n* In Federated Learning (FL), the bottleneck is communication. The complexity in number of communication rounds is only one part of it, sending full vectors is not reasonable in FL, compression must be used to reduce dramatically the number of communicated bits, which is the right criterion to study.\n* There is a lack of comparison to existing methods.  Here the local steps are performed to find a stationary point of the augmented Lagrangian. This is equivalent to compute, inexactly, a proximity operator. This is exactly what the 5GCS algorithm does, proposed in \nGrudzien et al. \"Can 5th generation local training methods support client sampling? yes!\" AISTATS 2023. 5GCS has been extended to compression in Grudzien et al \"Improving Accelerated Federated Learning with Compression and Importance Sampling\", arXiv:2306.03240. Another technique is loopless: instead of an inner loop of local steps, communication is triggered randomly. This is the technique used in Scaffnew, an important algorithm since which demonstrates that local training yields acceleration of communication in FL: Mishchenko et al. \"ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally!\" ICML 2022. Scaffnew has been interpreted as a primal-dual algorithm in Condat and Richtárik, \"RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates\" ICLR 2023. Scaffnew has been extended to partial participation, and also compression, as TAMUNA in Condat et al. \"TAMUNA: Doubly Accelerated Federated Learning with Local Training, Compression, and Partial Participation\" arXiv:2302.09832. \n\n* In these algorithms, such as 5GCS and TAMUNA, the dual variables of the inactive clients are not modified. This is fine, because the aggregated model from the active clients does not contain any information about the inactive clients, so we cannot expect to use the new model to update these dual variables. So, I don't see what the challenge addressed in the paper is, because combining local training and partial participation can been done successfully, as these papers show.\n\n* The writing is not good. The first 3 pages contain only vague statements, without the problem being defined. The paper contains a lot of unusual or weird expressions, such as \"imminent challenge\" \"brings great distress for training\". What does the sentence \"Ozfatura et al. [2021], Xu et al. [2021] propose to adopt the global update consistently control the local training to force a high consensus.\" mean?\n* I don't see what \"dual drift\" actually means.  If the dual variables of inactive clients remain the same for a long time, this is not a drift. The only explanation of this notion is that there is \"excessive differences between the primal and dual variables\", which is unclear, one cannot compare a primal and dual variable. If you mean that the primal and dual variables become inconsistent with each other, this inconsistency should be made precise. So, the paper title should be modified. Also, it is not grammatically correct, this should be \"Needs\", not \"Need\".\n\n\n\n\nTypos\n\n* (5) first update: this should be $\\theta_i$, not $\\theta_i^t$\n\n* Algorithm 1, line 4: this should be $P^t$, not $N^t$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1 and W2:  I don't think the method improves on the SOTA and compression must be used to reduce dramatically the number of communicated bits, which is the right criterion to study.**\n\nThe main contribution of this paper is neither proposing a theory that achieves faster optimization rates than SOTA nor introducing a compression technique to reduce communication bits. Moreover, we have never claimed in this paper that our method can achieve a faster rate than the SOTA  results. **The primary focus of this paper is on addressing the training instability issues encountered in experiments of existing primal-dual methods.** Our research is not directly related to these two fields. We introduce our main contribution **in the overall response above**.\n\n**W3: There is a lack of comparison to existing methods.**\n\nThank you very much for pointing out these excellent works. We will cite these theory-related works in section 2. We also summarize the differences between these works and ours **in the overall response above**.\n\n**W4 and W6: I don't see what \"dual drift\" actually means.**\n\nThank you for this concern. Since this is the main issue studied in this paper, we specifically introduce this **in the overall response above**.\n\n**W5: The writing is not good.**\n\nWe are sorry if some sentences may have caused misunderstandings. We will clarify their expressions and revise them to make them more straightforward and understandable.\n\n**Q1 and Q2: Theorem 1 \"let rho > O(L^3) be positive with lower bound\": what does it mean? Looking at the proof, Line 987: it is not clear at all what the condition on rho is.**\n\nThank you for this question and we will revise this ambiguous expression.\n\n**Is $\\rho$ proportional to $L^3$ ?**\nNo. $\\rho$ is just a general constant. We follow the proof techniques in [X1] to construct the recurrsive relationship on the combination of $\\mathbb{E}[f(\\overline{\\theta}^t)]$ term and $R_t=\\frac{1}{C}\\mathbb{E}\\Vert\\theta_i^{t+1}-\\overline{\\theta}^t\\Vert$ term. We can construct an arithmetic sequence when the following condition is satisfied (line 987 in our paper):\n$$\n\\rho^2 - 4L^3\\rho - 36L^2-4L^4>0.\n$$\nThis can be regarded as a quadratic function, using the basic knowledge of the roots of quadratic functions, we have:\n$$\n\\rho > \\frac{4L^3 + \\sqrt{16L^6 + 16L^4 + 144L^2}}{2} \\ \\ \\text{or} \\ \\ \\rho<\\frac{4L^3 - \\sqrt{16L^6 + 16L^4 + 144L^2}}{2}.\n$$\nSince $4L^3 - \\sqrt{16L^6 + 16L^4 + 144L^2}<0$ but we need $\\rho$ to be positive. Therefore, the required range of $\\rho$ is $\\rho > \\frac{4L^3 + \\sqrt{16L^6 + 16L^4 + 144L^2}}{2}$ only.\n\nSorry for using an ambiguous expression here and $\\rho=\\mathcal{O}(L^3)$ is different from our $\\rho>\\mathcal{O}(L^3)$. The form of this constant is quite cumbersome when written in the theorem. Therefore, we used $O(L^3)$ as a placeholder, which has caused some ambiguity. We apologize for this and will correct it to $\\rho > \\frac{4L^3 + \\sqrt{16L^6 + 16L^4 + 144L^2}}{2}$.\n\n[X1] Acar D A E, Zhao Y, Matas R, et al. Federated Learning Based on Dynamic Regularization[C]//International Conference on Learning Representations.\n\n**Q3: line 3: \"randomly select active clients set\": do you mean to choose a subset of size P uniformly at random?**\n\nIt means that before each round of local training begins, the server will activate a batch of local clients to participate in the training, with each client having the same probability of being activated. After completing the training, they will remain inactive until they are selected to be activated again.\n\n**Q4: Why does the number P of active clients not appear in Theorem 1? This is strange.**\n\nVirtual updates can be understood as a form of synchronization for non-participating clients, and can also be seen as a form of virtual full-participation training. The conclusions drawn from this approach would not exceed those given in FedPD [X2], as the algorithmic proof in FedPD requires strict full participation. We present the comparison of the theoretical results in Table 7. For FedPD, even in the case of full participation, it does not indicate that the results are related to $C$. For FedDyn, the proofs indicate that the final convergence rate achieves $\\mathcal{O}(\\frac{C}{PT})$ (slower than $\\mathcal{O}(\\frac{1}{T})$). Our analysis shows that, with virtual updates and appropriate parameter choices to avoid excessive errors, the convergence rate of partial participation can achieve a similar complexity as full participation, thus reducing the impact of the $\\frac{C}{P}$ constant term in FedDyn.\n\n[X2] Zhang X, Hong M, Dhople S, et al. Fedpd: A federated learning framework with adaptivity to non-iid data[J]. IEEE Transactions on Signal Processing, 2021, 69: 6055-6070.\n\n**Q5: Line 972: how do you get the factors 4 and the 2, this looks like Young's inequality but not clear at all.**\n\nThank you for pointing out this.\n\nThis is the noised version of proof of Lemma 11 in [X1] (page 35 in their paper). The coefficients $4$ and $2$ in our conclusion are consistent with those in their proof. This is because the proof in [X1] uses Young's inequality to first divide these terms into four groups, thus enlarging the coefficients by a factor of $4$. They then merge the dual updates and local update terms into a single upper bound, resulting in the constant $2$. Our conclusion additionally considers a case with local error, which introduces a constant $\\epsilon$ due to the local inexact solution. We apologize for the lack of clarity here. **We will directly copy the lemma they used and cite it as their Lemma 11 in the next version. We hope this resolves your concerns.**\n\n[X1] Acar D A E, Zhao Y, Matas R, et al. Federated Learning Based on Dynamic Regularization[C]//International Conference on Learning Representations.\n\nThanks for reading our rebuttal and we are happy to continue discussions if there are some other concerns unsolved.", "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:
**We thank the four reviewers for their valuable time and effort in reviewing our submission.** Reviewers 6Q4p, b9A4, and YYQB provided positive feedback with rates of 7, 7, and 5, respectively. After reading all the review comments, we noticed that the response from reviewer c2hH mentioned some concerns regarding the main contributions and research objectives of this paper, such as the 'definition of dual drift' and 'whether it should be named as dual drift'. Given that this is the main issue studied in this paper, we hope to provide a comprehensive summary in this overall response to clarify misunderstandings.

**A. Main Contributions**

(1) We want to emphasize that the target of this paper is neither to propose a better theoretical framework to surpass the SOTA convergence rate nor to explore how federated learning can achieve lower communication bits. This paper investigates the training instability phenomenon widely observed in some classic federated primal-dual methods (we name it the "dual drift" issue) in experiments and proposes a simple and effective solution to avoid this issue.

(2) The optimization proof is provided to demonstrate that our proposed technique does not cause the primal-dual methods to diverge. Meanwhile, it can significantly improve the test performance in experiments.

(3) To the best of our knowledge, this paper is the first to provide a generalization error based on stability analysis for federated primal-dual methods. We explain the superior stability over the classical FedAvg method from the perspective of local training stability.

**B. Dual Drift**

We appreciate the reviewer c2hH for listing a series of works to demonstrate that partial participation in primal-dual methods is theoretically feasible. We have never claimed in this paper that they are theoretically infeasible. In fact, the FedADMM method, which exhibits training instability as shown in our Figure 1, is also theoretically proven to support partial participation [X1]. **However, we have verified that this method encounters significant challenges in experiments, with severe fluctuations as the participation rate decreases.** We believe that theoretical proofs are one of the assurances of an algorithm's validity, but they are not everything. In practice, various detailed issues still need to be effectively addressed.

Based on extensive experiments and analysis, we attribute the cause of this instability phenomenon as follows. Methods like ADMM require alternating updates of the primal and dual variables to ensure that the Lagrangian function eventually converges to the original objective. Under the low participation ratio, a client waits for a long time to be activated. For the local client, it is as if the primal variables are continuously being updated, while the dual variables remain in a stagnant state. When it is suddenly activated, the lagging dual variables result in the current primal variables being in a very poor initialization state for the local Lagrangian function. Therefore, we have named this phenomenon ``dual drift". Our solution is to perform virtual dual updates on the dual variables based on estimated primal variables for those unparticipated clients, to ensure they do not lag too far behind.

[X1] Wang H, Marella S, Anderson J. Fedadmm: A federated primal-dual algorithm allowing partial participation[C]//2022 IEEE 61st Conference on Decision and Control (CDC). IEEE, 2022: 287-294.


**C. A series of works [X1-X5] mentioned by Reviewer c2hH**

We are very grateful to reviewer c2hH for introducing us to this series of excellent theoretical works [X1-X5]. We will add a section on the theoretical advancements of federated primal-dual methods in the related work section to introduce them. However, as mentioned above, the goal of this paper is not to propose an optimization convergence analysis that surpasses existing methods but rather to address the currently widespread training instability phenomenon in experiments. 

**We need to emphasize that this phenomenon is not easily observed on small datasets and small models.** For example, FedDyn may perform normally with the ResNet-18 model on the CIFAR-10 dataset but shows unstable training on CIFAR-100. When the model size is further increased, e.g. Transformers, this phenomenon becomes even more pronounced. [X1-X5] primarily focus on the progress of optimization proofs, with experiments mostly centered around the tiny logistic regression models and smaller libsvm datasets. Additionally, the experimental scales they used are typically smaller than 50. The focus of the work's analysis scenarios and experimental setups differs from ours significantly, which makes it difficult for us to make a unified comparison. 

[X1] Grudzień M, Malinovsky G, Richtárik P. Can 5th generation local training methods support client sampling? yes![C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2023: 1055-1092.

[X2] Grudzień M, Malinovsky G, Richtárik P. Improving accelerated federated learning with compression and importance sampling[J]. arXiv preprint arXiv:2306.03240, 2023.

[X3] Mishchenko K, Malinovsky G, Stich S, et al. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally![C]//International Conference on Machine Learning. PMLR, 2022: 15750-15769.

[X4] Condat L, Richtárik P. RandProx: Primal-dual optimization algorithms with randomized proximal updates[J]. arXiv preprint arXiv:2207.12891, 2022.

[X5] Condat L P, Malinovsky G, Richtárik P. Tamuna: Accelerated federated learning with local training and partial participation[J]. 2023.

Thank all reviewers for reading our rebuttal. We hope this summary clarifies the main research objectives and contributions of this paper. Responses to other concerns are provided in separate replies. If there are any unresolved concerns, we are more than happy to engage in further discussion with the reviewers.

Meta-review: This paper studies primal-dual federated learning algorithms. It demonstrates that primal-dual methods can suffer from a so-called "drift" in the dual variables of inactive clients on non-convex problems. The paper proposes updating the dual variables of non-participating clients via global average models to mitigate the drift. The effectiveness of the approach is demonstrated through numerical experiments and is theoretically verified under smoothness and Lipschitz assumptions.

The dual drift phenomenon does not exist in the convex setting, for which most of these methods were originally developed. The reviewers remarked that the differences between these cases should be discussed more prominently in the work, and that the findings and phenomena should be contrasted with existing theoretical work on the convex setting. The changes proposed by the authors during the lengthy discussion with the reviewers appear sufficient if they can be integrated into the revision.

The reviewing committee finds that the paper has the merit of stimulating discussion on this important topic and can advance research on practical federated learning algorithms.
Decision: Accept (spotlight)