Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: - In federated learning settings, aggregating the learning of all participating clients has always been a challenging issue in cases of data heterogeneity across clients which is very probable in real world scenarios. To tackle this, recent works have optimized the server aggregation process of FedAvg algorithm by treating client updates as "pseudo gradients" with fixed server step size. However, using a fixed step size is not ideal for varying data distribution across clients.
- To tackle this issue, this paper proposes a novel federated learning algorithm FedExP which adaptively determines the server step size in each round of federated learning such that it can handle varying degree of similarity in data distribution across clients. In doing so, the authors first establish a novel connection between FedAvg and POCS algorithms for overparameterized convex objectives and further draw the inspiration from the EPPM extrapolation algorithm (used to speed up POCS algorithm) resulting in adaptively determining server step size in FedExP for better and fast convergence of global model.
- Key feature of FedExP is that there is virtually no requirement for additional communication, computation, or storage at clients or the server.
- Experimental evaluation demonstrates that FedExP algorithm converges faster and consistently outperforms baselines over 5 datasets.
- novelty is simple and limited yet effectively applied to federated learning paradigm and have shown improved performance in terms of speed-up/efficiency and client-server data communication


strength_and_weaknesses: Strengths:
- novelty is simple yet effective application in federated learning paradigm
- The motivation is well founded and the claims are sound.
- Paper is clearly presented and easy to follow.
- Mathematical formulation is very detailed and explanatory.
- Proposed FedExP model is effective and efficient.
- Proposed FedExP model consistently outperforms two strong federated learning baseline methods on global model convergence time and test accuracy over multiple datasets.

Weaknesses:
- inspired by related works, especially the application of extrapolation in federated learning
- novelty is limited (yet effective)
- Missing comparison with the relevant FedProx method.
	Li, Tian, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. "Federated optimization in heterogeneous networks." Proceedings of Machine Learning and Systems 2 (2020): 429-450.


clarity,_quality,_novelty_and_reproducibility: Quality:
- Recently proposed federated learning algorithm FedProx has tackled the data heterogeneity problem by adapting the optimization objective of FedAvg on local clients. Although FedProx increases computation on client-side, it still has similar motivation. So, it would be interesting to see the comparison of FedExp with FedProx method.

Clarity:
- A figure of the proposed FedExP model with client-server communication would improve understanding of the method setup and working.
- A table of notations would improve readability of the mathematical formulation.

Novelty:
- Drawing a connection between FedAvg method and POCS algorithm is novel. Furthermore, adaptation and application of EPPM extrapolation algorithm in FedAvg method for adaptive server step size in each round is novel too.
- novelty is simple yet effective application in federated learning paradigm

Reproducibility:
- Experimental setup and hyperparameter settings are described in detail.

summary_of_the_review: The dynamic tuning of server step size results in efficient (faster) convergence and performance boost across multiple datasets while efficiently tackling the issue of knowledge interference during server aggregation due to heterogeneous data distribution across clients.

- The novelty is limited and simple yet effective in Federated learning paradigm 
- the proposed method is effective both in terms on efficiency and prediction performance 
- addresses the sustainability concerns and may be applicable and scale when a number of clients participate in Federated averaging, especially in IOT scenarios and cloud-edge continuum
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies adaptive server step sizes for federated learning (FL). The authors propose a method called FedExP, which uses a server step size akin to the POCS algorithm from the literature on finding feasible points inside the intersections of sets. The authors use a similar expression to estimate how much one can extrapolate in the direction proposed by FedAvg.

The authors prove convergence of the method for convex and nonconvex problems. They also run experiments on convex problems that clearly illustrate the theory, as well as on FL benchmarks.

-------------
## update after reading authors' feedback

The authors addressed my main concern about the short runs. I can see the figures in the appendix that include longer runs.  
The authors also added the missing assumptions to Theorem 2.  
I believe it is very clear that the paper should be accepted.
strength_and_weaknesses: ## Strength
1. The work is written in a clear and intuitive way.  
2. The considered problem is quite meaningful as server side stepsizes have been shown to give an improvement in practice and building better adaptive estimates is a promising direction.  
3. The theory is rigorous and considers both convex and nonconvex settings.  
4. There are experiments to support the theory as well as to show that the method will be useful in practice. 

## Weaknesses:  
1. In the experiments, it appears that most algorithms were terminated before convergence. Therefore, we do not see the final values of the test accuracy. In practice, these values are very important, so I would like to know if the authors can present plots with longer training.  
2. Theorem 2 is analyzed under the assumption that the gradients are deterministic and I do not see if this stated anywhere in the text.

clarity,_quality,_novelty_and_reproducibility: I found the paper to be written very clearly. Some minor issues/typos:  
Algorithm  1: "Global server do" -> "Global server does" or maybe "On global server do"?
equations (1), (8), (10) and (11) should end with a comma  
Page 7, "has a oscillating" -> "has an oscillating"  
Equations (71) and (72) include $\nabla \mathbf{h}_i^{(t)}$, which seems to be a typo, it should have been $\mathbf{h}_i^{(t)}$  
What is the point of introducing $\mathbf{h}_i^{(t)}$ in the proof of Theorem 2, isn't it the same as $\Delta_i^{(t)}$?  
What's the point of dividing by $\eta_g^{(t)}$ in (73) if you then multiply back by $\eta_g^{(t)}$ to get (76)?
summary_of_the_review: The paper shows a good mixture of theoretical and empirical results, both of which seem of sufficient quality. There are a couple of ways the paper can be improved, but I believe that it meets the bar for acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the problem of federated optimization. It shows a connection between FedAvg and Projection Onto Convex Sets algorithm (under overparametrized convex setting) and based on this proposes a method (FedExP) with adaptive server step-size strategy by using the gradient diversity measure. The authors perform a theoretical analysis of FedExP and show convergence under standard reasonable assumptions in convex and non-convex settings. In the experimental section proposed method is studied in both illustrative and realistic FL settings and is shown to outperform selected baselines.
strength_and_weaknesses: ## Strengths

1. Novel and insightful view of an important Federated Averaging algorithm, which has the potential for fruitful theoretical and practical advancements in the area of federated optimization. 

3. The suggested step-size strategy can be applicable to a wider set of local gradient methods, which was illustrated for SCAFFOLD in the Appendix.

2. Thorough empirical study of the proposed method, which shows its insightful properties on toy problems and promising results for synthetic and realistic benchmarks.

## Weaknesses

1. Convergence analysis focuses on the local full-batch and full client participation. which is quite far from current practical federated learning settings. Although I do not consider it a big issue, as almost all local optimization methods do not provide any theoretical benefits over simplest distributed (mini-batch stochastic) gradient descent baseline for heterogenous problems.
clarity,_quality,_novelty_and_reproducibility: - The paper is well-written and easy to follow. Contributions and limitations are made quite clear. The work quality is good and it is fairly original.

- Experimental result for EMNIST looks contradicting to the Adaptive FedOpt work (Reddi et al., 2021) as in the original paper SCAFFOLD performed significantly worse than FedAvg and FedAdagrad. Could you please comment on what could be the reasons for these different behaviors?

- I would like to as the authors why the proposed method was not compared to FedAdam which achieves the best empirical performance on some of the benchmarks. I understand that it does not have such a nice theory, but still think that it would be very useful for practitioners to include it in the comparison at least in the appendix (or how it can be combined with FedExP).

- How well can FedExP be combined with client and server momentum techniques?

- How sensitive is the proposed method to the choice of parameter $\epsilon$? Does it require a lot of tuning for achieving good performance or the same value can be used across a variety of settings like for some Adam parameters? I think that an experiment or at least a comment on this is needed for publication.

**Minor comments and typos**

- I do not quite get the phrase from the Abstract 
> practical benefit of the server step size has not been seen in most existing works

The works of Hsu et al., 2019 and Reddi et al., 2021 address this question, don't they?

- Why the number of local updates is fixed to 20 instead of 1 epoch over the local data like it was done in the paper of Reddi et al., 2021?

- It would be helpful to include the result of Khaled et al., 2020 on local GD (FedAvg) in the main body for a clearer comparison to FedExP. I would also like to ask the authors to comment and point to (also add it to the Appendix) the adjustments they made to the analysis from previous works.

- Probably missed word on page 7 (Figure 2 caption): *"the last iterate of has an oscillating"*.

- Looks like there is an issue in this sentence *"FedExP is now trying to minimize $\Delta_2^{(t+1)}$"*, as it is not clear how a vector can be minimized.
summary_of_the_review: This work is insightful from theoretical perspective and presents useful practical results. I have some comments and questions (in the previous section) on parts of the paper, which will be hopefully addressed. Overall, I think that submission is worth publishing after the minor revision.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors developed FedExp, a federated learning algorithm with an adaptive server step-size strategy, to resolve the known issue of data heterogeneity across clients. Reviewers anonymously agree that the paper is clearly written. The algorithm is simple and shown to be effective empirically. The experiments in the initial submission had some issues (about the short-runs) as raised by a reviewer, but the revision and rebuttal have addressed the concern. Overall reviewers agree that the experiment are convincing for validating the effectiveness of the FedExp.  For the theoretical analysis of FedExp, the authors first established the connection between FedAvg and the Projection Onto Convex Sets (POCS) algorithm under the overparametrization convex setting. The analysis, although it is based on standard assumptions, is sufficient for the purpose of proving the convergence of FedExp. 
justification_for_why_not_higher_score: The novelty is to some extent limited. The algorithm is simple and the analysis is based on standard technique and assumptions. 
justification_for_why_not_lower_score: The algorithm is effectiveness and the theoretical analysis, although it is quite standard, is convincing to prove the convergence.
Decision: Accept: notable-top-25%