A-FedPD: Aligning Dual-Drift is All Federated Primal-Dual Learning Needs

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.

The 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.

W3: There is a lack of comparison to existing methods.

Thank 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.

W4 and W6: I don't see what "dual drift" actually means.

Thank you for this concern. Since this is the main issue studied in this paper, we specifically introduce this in the overall response above.

W5: The writing is not good.

We are sorry if some sentences may have caused misunderstandings. We will clarify their expressions and revise them to make them more straightforward and understandable.

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.

Thank you for this question and we will revise this ambiguous expression.

Is $\rho$ proportional to $L^3$ ? No. $\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):

$$\rho^2 - 4L^3\rho - 36L^2-4L^4>0.$$

This can be regarded as a quadratic function, using the basic knowledge of the roots of quadratic functions, we have:

$$\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}.$$

Since $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.

Sorry 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}$.

[X1] Acar D A E, Zhao Y, Matas R, et al. Federated Learning Based on Dynamic Regularization[C]//International Conference on Learning Representations.

Q3: line 3: "randomly select active clients set": do you mean to choose a subset of size P uniformly at random?

It 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.

Q4: Why does the number P of active clients not appear in Theorem 1? This is strange.

Virtual 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.

[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.

Q5: Line 972: how do you get the factors 4 and the 2, this looks like Young's inequality but not clear at all.

Thank you for pointing out this.

This 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.

[X1] Acar D A E, Zhao Y, Matas R, et al. Federated Learning Based on Dynamic Regularization[C]//International Conference on Learning Representations.

Thanks for reading our rebuttal and we are happy to continue discussions if there are some other concerns unsolved.

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.

Due 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.

Actually, 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.

Local SGD optimizer:

$$\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)).$$

Local SAM optimizer:

$$\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)).$$

Other operations are essentially consistent with the A-FedPD method.

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.

Thank 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.

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.

We 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.

[X1] Xu J, Wang S, Wang L, et al. Fedcm: Federated learning with client-level momentum[J]. arXiv preprint arXiv:2106.10874, 2021.

Thank 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.

W1: The reviewer has serious concerns about this point. Without introducing SAM, can the superiority not be empirically demonstrated?

FedSpeed method essentially uses a variant of the local SAM optimizer. To illustrate this, we can recall its implementation:

$$g_{i,k,1}^t = \nabla F_i(x_{i,k}^t,B),$$ $$y_{i,k}^t = x_{i,k}^t + \rho g_{i,k,1}^t,$$ $$g_{i,k,2}^t = \nabla F_i(y_{i,k}^t, B),$$ $$g_{i,k}^t = (1-\alpha)g_{i,k,1}^t + \alpha g_{i,k,2}^t.$$

The ascent learning rate is set as $\rho=\frac{\rho_0}{\Vert\nabla F_i\Vert}$. Then we have:

$$g_{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).$$

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.

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?

Thank 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.

As 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.

[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.

W3: Some relevant literature might be missing.

Thank you for pointing out these two important works. We will add them in the Related Work.

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.

(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.

(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.

[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.

[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.

Q2: I think it would be better to clearly write in the main paper that a hyperparameter search was conducted (see Appendix).

Thank you for pointing out this. We will add the sentence "Detailed hyperparameter search was conducted (see Appendix A.2)" in section 5.1.

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?

Thank 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.

Thank you again for reading our rebuttal. If you have any further questions, we would be very happy to continue the discussion with you.

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.

Thank 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.

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}$?

Thank 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.

Therefore, 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.

This 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.

There 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.

We 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.

[X1] Zhang R, Kwok J. Asynchronous distributed ADMM for consensus optimization[C]//International conference on machine learning. PMLR, 2014: 1701-1709.

[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.

Thank 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.