On the Convergence of FedProx with Extrapolation and Inexact Prox

We thank you for taking time to review our paper.

---

Weakness 1:

The reviewer may have misinterpreted our assumptions. We assume each function $f_i$ is convex (could have multiple minimizers). and operate under the interpolation regime, where the intersection of the set of minimizers of $f_i$ is nonempty. Additionally, we assume the global objective $f$ is strongly convex (Assumption 5), which suggests that the intersection is a singleton.

The strong convexity assumption simplifies our presentation. Without it, the same reformulation applies to biased SGD in the general convex case, which we can analyze similarly using biased SGD theories.

Without the interpolation, the algorithm converges to a neighborhood of the true solution. As discussed in Appendix E, the interpolation assumption aligns with FedExProx when viewed through the lens of parallel projection methods.

---

Weakness 2:

The referenced work is relevant but was posted after ours, so it wasn’t initially included. Their work provides improved guarantees on PL objectives compared to the original FedExProx algorithm introduced in [2]. Our objective is somewhat 'orthogonal' to theirs, as we focus on removing the impractical assumption of exact proximal operator evaluations. We agree that this reference adds clarity, and it's included in the latest version of our paper.

[2] The Power of Extrapolation in Federated Learning, H. Li, K. Acharya, P. Richtárik

---

Weakness 3:

Yes, indeed. For exact proximal operators, FedExProx yields an unbiased SGD, where adaptive step sizes are well-understood. However, for inexact FedExProx, literature on adaptive step sizes for biased SGD is lacking, and we are investigating this gap. Preliminary results (Figures 6 and 7) show that gradient diversity accelerates the algorithm, while the stochastic Polyak step size is less effective, highlighting the need for tailored adaptive step size strategies for biased SGD.

For the case of client samping, the algorithm performs suboptimally due to the added stochasticity—an expected outcome, as client sub-sampling does not inherently benefit biased compression, as noted in [1]. To address this, one could apply the well-known Error Feedback-21 strategy [1], [2] for biased compression; however, implementing this requires modifying the original FedExProx algorithm, which falls outside the scope of our current focus.

[1] EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. P. Richtárik, I. Sokolov, I. Fatkhullin [2] EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression. K. Gruntkowska, A. Tyurin, P. Richtarik.

---

Weakness 4 & Question 2:

(1): We have added in the lastest version of the paper that the local convergence rates are derived based on existing theories.

(2): We have changed accordingly in the lastest version of the paper that the local convergence rates are derived based on existing theories.

(3): Unfortunately, it is not possible to achieve convergence to the exact solution even if $\varepsilon_1$ is sufficiently small; there will always be a neighborhood in this case, determined by the value of $\varepsilon_1$. With relative approximation, however, this neighborhood vanishes as the bias term in (12) diminishes near the optimum. Thus, these two approximation approaches are not directly comparable. Smaller values of $\varepsilon_1$ or $\varepsilon_2$ generally require more local client steps. With absolute approximation, $\varepsilon_1$ determines the neighborhood size but does not affect total communication rounds directly (Theorem 1). In contrast, a smaller $\varepsilon_2$ in relative approximation increases local computation but reduces total communication rounds, akin to the difference between standard SGD and variance-reduced SGD.

(4): Thank you for the suggestion. We have now added a note in Table 1 to highlight this.

(5) & Question $2$: Thanks the suggestion. We include Theorem 2 to illustrate that directly applying results from the biased SGD perspective yields a suboptimal convergence bound and a much restrictive condition on accuracy of the approximation. In contrast, Theorem 3, with a reformulated approach, offers a tighter bound and a relaxed condition, supporting the effectiveness of extrapolation in the inexact case. We include Theorem 2 only to highlight the improvement achieved with Theorem 3.

(6) Thank you for pointing this out; this is indeed a relevant paper. We have now added this reference to our paper to enhance readability.

Typos: We have corrected this typo.

---

Question 1:

There may be some confusion here. As shown in Fig. 1(a), FedExProx outperforms exact FedProx (without extrapolation) even with inexact proximal updates, though its convergence rate is slower than exact FedExProx, consistent with our theoretical predictions.

We thank you for taking time to review our paper.

---

Weakness $1$:

We agree with the reviewer that detailing the behavior of the algorithm in the non-interpolated setting is essential. To address this, we have added the following discussion to the appendix of our paper in Appendix E:

In the absence of the interpolation regime assumption, the algorithm converges to a neighborhood of the true minimizer $x_\star$ of $f$. This occurs because $f$ and $M^{\gamma}$ have the same minimizer only under the interpolation regime assumption, as established by Fact 7 and [2]. Since inexact FedExProx can be formulated as biased SGD on the objective $M^{\gamma}$, it converges to the minimizer $x_{\star}^{\prime}$, provided that inexactness is properly bounded. As a result, the algorithm converges to $x_\star^{\prime}$, located within a $\|\|x_\star - x_\star^{\prime}\|\|$-neighborhood of $x_\star$ whose size depends on $\gamma$. Notably, the effects of inexactness and interpolation are, in some sense, 'orthogonal', meaning they do not interfere with each other.

In addition, FedProx does not require the interpolation regime assumption. However, like FedExProx and its inexact variant, it converges to a neighborhood of the solution. The interpolation assumption was initially introduced based on the motivation behind FedExProx. It is known that the parallel projection method for solving convex feasibility problems is accelerated by extrapolation. Given the similarity between projection operators and proximal operators (which are, in fact, projections onto certain level set of the function), FedExProx was proposed. The interpolation assumption here corresponds to the assumption that the intersection of these convex sets is non-empty in the convex feasibility problem. Although seemingly arbitrary for FedProx, the interpolation assumption aligns naturally with FedExProx when viewed through the lens of parallel projection methods.

---

Weakness $2$:

Theorem 4 and 5 provide both local computational complexities to achiveve absolute approximation (definition 3) and relative approximation (definition 4) using local gradient descent and accelerated gradient descent respectively. It’s possible the reviewer may have missed the second part regarding relative approximation, as both are currently presented in one line due to space constraints. If the paper is accepted and additional space is available, we will separate these results to prevent any misunderstanding.

---

Weakness $3$:

Thank you for your feedback. We have removed some redundancies and streamlined the statement of Theorem 1 for greater clarity.

---

Weakness $4$:

Thanks for pointing this out. We have corrected the typo.

---

Question $1$:

Good question. Unfortunately, we believe it's not possible to achieve an exact solution under conditions of arbitrary inexactness. For the reformulation of inexact FedExProx, the gradient estimator comprises a gradient term and a bias term. Unlike absolute approximation, relative approximation bounds the bias so it decreases near the solution. Allowing arbitrary inexactness means the bias could vary widely, resulting in convergence only within a neighborhood, similar to absolute approximation.

From the perspective of biased SGD, this would be equivalent to assuming that we could use a random vector as a gradient estimator and still converge to the exact minimizer, which is unlikely to hold true.

---

Question $2$:

For relative approximation in Theorem 3, $\varepsilon_2$ must be sufficiently small, specifically $\varepsilon_2 < \frac{\mu}{4L_{\max}}$. If $\mu$ and $L_{\max}$ are known, we select $\varepsilon_2$ accordingly; otherwise, we estimate these values or choose a very small $\varepsilon_2$. A smaller $\varepsilon_2$ increases local computations per communication round but also accelerates progress per round, similar to local training methods.

In practice, the server can broadcast an accuracy level $\varepsilon_2$ to each client, directing them to perform local SGD, AGD, or other methods during each communication round. The required local iterations will depend on $\varepsilon_2$ and the local objective's characteristics.

---

Question $3$:

In general, we believe that extrapolation would be beneficial across a broader range of conditions. As explained in our response to Weakness 1, if we do not assume the interpolation regime, the FedExProx algorithm still converges to a neighborhood around $x_\star$ with radius $\|\|x_\star - x_\star^{\prime}\|\|$, where $x_\star^{\prime}$ is the minimizer of $M^{\gamma}$. This occurs because, without the interpolation assumption, the minimizers of $f$ and $M^{\gamma}$ do not necessarily coincide. In this setting, the size of the neighborhood depends on both $\gamma$ and $\alpha$, imposing additional constraints if we aim to reach a specific level of accuracy.

We thank you for taking time to review our paper.

---

Weakness $1$: "The theoretical analysis is restricted to globally strongly convex problems, ... Extending this analysis to non-convex cases would significantly increase the paper’s impact."

We agree with the reviewer that extending the analysis to non-convex cases could significantly enhance the paper's impact. However, it remains unclear whether extrapolation would indeed accelerate the convergence of the algorithm in this case, even when proximal operators are assumed to be solved exactly. This uncertainty stems from the foundational motivation behind the FedExProx algorithm, which is based on the parallel projection method for solving convex feasibility problems. Initially, it was observed that extrapolation can accelerate the parallel projection method (in this convex interpolated setting). Given the similarity between projection operators and proximal operators (the latter can be viewed as a projection to a level set of the function), the FedExProx algorithm was developed. In this context, extrapolation is considered in conjunction with convexity; whether it remains beneficial in non-convex settings is still unclear. This rationale led us to focus on the convex case first.

We have added the above discussion in Appendix E to the latest version of the paper as a clarification.

---

Weakness $2$: "The assumption of smoothness might not always hold in federated learning, particularly when clients have heterogeneous data distributions. A discussion on how the proposed approach might generalize or be adapted for non-smooth settings would strengthen the paper."

The smoothness assumption is pretty common in convex optimization, and we adopt it here for simplicity of discussion and presentation. In fact, even if we do not assume each local objective function $f_i$ to be $L_i$-smooth, the corresponding Moreau envelope $M^{\gamma}_{f_i}$ is still $\frac{1}{\gamma}$ -smooth as illustrated in [1]. Consequently, the inexact FedExProx still yields a form of SGD with a biased gradient estimator on the convex smooth objective $M^{\gamma}$. This allows us to leverage the relevant theoretical framework to analyze the convergence result in this scenario. Although some technical nuances arise, they do not impact the validity of our conclusion.

We have added the above discussion in Appendix E to the latest version of the paper as a clarification.

[1] The Power of Extrapolation in Federated Learning, H. Li, K. Acharya, P. Richtárik

---

Weakness $3$: "The experimental part is the weakest part of this work."

Thank you for your feedback. In this work, our primary focus has been on the theoretical aspects. Could you please indicate which specific parts of the experimental section you feel could be strengthened, or suggest any additional experiments you would find valuable?

We thank you for taking time to review our paper.

---

Weakness $1$ & Question $1$: "While the question is natural and important, the solution is quite straightforward, and does not introduce any novel tools or analysis. Excluding the approximation 2 which is nice." & "What is the main challenge and main novelty in your paper?"

We respectfully disagree with the reviewer’s assessment that the straightforward analysis in our paper is a limitation. While our analysis does not introduce novel tools, this choice is intentional. Our approach reformulates the inexact FedExProx algorithm in terms of established algorithms, such as SGD (stochastic gradient descent) with a biased gradient estimator and CGD (compressed gradient descent) with biased compression. This reformulation enables us to leverage existing analytical tools effectively. Without those connections, the relatively straightforward analysis presented would not be feasible. In summary, to address this natural and important problem, we opted for a reformulation that allows us to apply existing methodologies, rather than developing entirely new tools.

The primary challenge in our paper lies in formulating the problem appropriately and establishing optimal complexity bounds for the algorithm. For instance, to reach the conclusion that 'extrapolation aids the convergence of FedExProx, even with inexact proximal operators, provided that inexactness is bounded in a certain manner,' we first needed to recognize an intrinsic connection between FedExProx and biased compression in CGD. This insight allows us to apply existing theoretical frameworks to demonstrate the algorithm’s effectiveness. Without identifying this relationship, reaching such a conclusion would not have been feasible. In addition, it was essential to identify an appropriate way to bound the inexactness, allowing us to eliminate the neighborhood effect. This step was crucial in ensuring that our analysis remains rigorous and aligns with optimal complexity bounds.

The main novelty of our paper lies in providing an analysis of FedExProx when proximal operators are evaluated inexactly, a scenario that has not been previously studied. Our analysis leads to the new insight that extrapolation remains effective even with inexact proximal operators—a conclusion not previously established. Additionally, as the reviewer noted, we introduce a relative approximation approach that eliminates the neighborhood effect, thereby making the algorithm more practical and applicable in real-world settings.

---

Weakness $2$ & Question $2$: "The paper does not consider stochastic gradients which is the more relevant case in practice, it is important to understand how will the results change in light of this?" & "Why do you not take stochastic gradients into account? How will the results change assuming this?"

We do consider stochastic gradients in our analysis. Specifically, in Appendix F, we provide a convergence guarantee for inexact FedExProx with $\tau$-nice sampling of clients (which results in stochastic gradients) and $\varepsilon_2$ relative approximation, as detailed in Theorem 8 based on biased SGD theory. In the specific case of client sub-sampling, the algorithm performs suboptimally due to the added stochasticity—an expected outcome, as client sub-sampling does not inherently benefit biased compression, as noted in [1]. To address this, one could apply the well-known Error Feedback-21 strategy [1], [2] for biased compression; however, implementing this would require modifications to the original FedExProx algorithm, which falls outside the scope of our current discussion. For inexact FedExProx with $\varepsilon_1$ direct approximation, a convergence guarantee can be similarly derived, as outlined in Appendix F.2.

[1] EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. P. Richtárik, I. Sokolov, I. Fatkhullin [2] EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression. K. Gruntkowska, A. Tyurin, P. Richtarik.