Tighter Performance Theory of FedExProx
optimization;federated learning;proximal methods
Yes
No ethics review needed.
1. In your quadratic problems, I think the proximal operator attains a closed-form expression (as Eq(22) in Appendix C), why do you still use GD as the subroutine, rather than directly use the closed-form solution in Section 4.1?
1. Provided a refined analysis for FedExProx in some cases
2. Extend the analysis to more cases like partial participation and PL condition.
3. The paper is clearly written.
This work revisited FedExProx, a recently proposed algorithm for FL, and furthered the convergence analysis. They first found the existing analysis of FedExProx is not as good as vanilla GD on quadratic problems. Then they provided a refined analysis for FedExProx on non-strongly convex quadratic problems regarding the time complexity, which beats GD. They also provided the analysis in partial participation, adaptive extrapolation strategy, and PL condition, and complete the story with numerical experiments.
1. The scope of research is restricted to quadratic problems only, which may limit the significance of the work without enough motivation.
2. The claimed outperformance compared to GD (Theorem 4.3) is achieved with additional information on the communication protocol parameter $\mu$, computation protocol parameter $\tau$. I am skeptical that such setting are a bit coarse, I am not sure whether the communication parameter $\mu$ is easy to detect in the system, also $\tau$ corresponds to uniform computation cost for all devices, which may disregard the heterogeneity in computation among devices. Regarding authors claimed to study an empirically promising algorithm, I think authors should add more discussion on it for clarification, and to further improve the significance.
3. The stepsize choice in Theorem 6.1 depends on the exact value of the Moreau envelope or its lower bound, which is impractical in my opinion. 
4. I suggest adding vanilla GD into your experiments to verify that your outperformance theory works in practice.

With that I think the work can be benefited a lot with a revision to further clarify the motivation and some technical details. Thank you.
Yes
No ethics review needed.
Have the authors considered running experiments on more realistic datasets?
The analysis of the algorithm seems to be solid. It seems to improve over previous results. The authors also extended the results to partial participation scenarios.
This paper proposes a new analysis for FedExProx algorithm.
The experiments only involves synthetic data.
Yes
No ethics review needed.
) Please compare to FedAvg in the quadratic case, what do you get?

2) The parameter $L_{S,\gamma}$ is confusing to me, shouldn't it increase with $S$, similarly to randomized coordinate descent?
1) The authors make a good job by taking into consideration also practical considerations like lags in communication and computation and reflecting them in the overall performance of the method

2) The authors illustrate a specific diagonal case where the improvement of what they suggest is obtained
The authors re-examine a new approach to federated learning called FedExProx. 
They analyze it in the case of convex quadratic objectives all while taking lags in computation and communication under consideration, 
and show that it benefits standard approaches. This improves over previous analysis of the method.
1) The paper does not take the noise due to the samples into account: this is missing both in the convergence rates as well as not taken into account in
the cost of computing the prox operation

2) Focusing on quadratic functions is very limiting and does not properly reflect the more general case. Indeed, in the quadratic case, the gradients are linear in the weights which is a unique property that does not generalize

3) For quadratic functions, the authors should compare their approach to the FedAvg algorithm. 
Noticelbly, the work of (Woodworth et al): (Is Local SGD Better than Minibatch SGD?) shows that for quadratic functions then FedAvg obtains the best possible convergence guarantees. So it is not clear what is the benefit of FedExProx on FedAvg in this case?

4) The extension to the case where the Moreu envelope is PL is nice, but it is not clear if it applies in any interesting case?
@inproceedings{
anonymous2024tighter,
title={Tighter Performance Theory of FedExProx},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=q2VK1Z8XFo},
note={under review}
}
We revisit FedExProx -- a recently proposed distributed optimization method designed to enhance convergence properties of parallel proximal algorithms via extrapolation. In the process, we uncover a surprising flaw: its known theoretical guarantees on quadratic optimization tasks are no better than those offered by the vanilla Gradient Descent (GD) method. Motivated by this observation, we develop a novel analysis framework, establishing a tighter linear convergence rate for non-strongly convex quadratic problems. By incorporating both computation and communication costs, we demonstrate that FedExProx can indeed provably outperform GD, in stark contrast to the original analysis. Furthermore, we consider partial participation scenarios and analyze two adaptive extrapolation strategies-based on gradient diversity and Polyak stepsizes --- again significantly outperforming previous results. Moving beyond quadratics, we extend the applicability of our analysis to general functions satisfying the Polyak-Łojasiewicz condition, outperforming the previous strongly convex analysis while operating under weaker assumptions. Backed by empirical results, our findings point to a new and stronger potential of FedExProx, paving the way for further exploration of the benefits of extrapolation in federated learning.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
optimization federated learning proximal methods
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/455b8335f000560279f10ff98058a9e57c49594b.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Tighter Performance Theory of FedExProx
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission