Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper extends the server model averaging step in FedAvg to a more general adaptive optimization step on the global model, specifically, by writing the model averaging as a gradient descent step using a pseudo gradient. Three variants of this scheme (FedOpt) are presented, based on three adaptive optimizers, including AdaGrad, ADAM, and YOGI. While there exist works applying the server-side momentum method, the paper argues that the proposed framework is more general since any adaptive optimizer can be applied to extend FedAvg. Under three assumptions (Lipschitz gradient, bounded gradients, bounded variances), the paper provides a local convergence analysis with nonconvex objectives. The achieved bounds match the best-known convergence rate for FL under reasonable conditions (i.e., T is sufficiently large compared to K). They also provide guidance for how to decay the local learning rate to avoid client drift, and show that increasing local steps can help to reduce the communication rounds (under certain conditions). They also reflect the dependency of these bounds on client heterogeneity measured by global variance and indicates how to mitigate the problem in FedOpt. Experimental comparison to FedAvg, FedAvgM, and SCAFFOLD on seven benchmark FL tasks show that the proposed three adaptive FL methods are better or comparable on early-stage convergence and final validation-set performance. A study about tuning the local and global learning rate is also presented.

Pros:

(1) The paper is well written and easier to understand for most parts. The authors moved the proof and experiment details to the appendix, which largely improves the readability. 

(2) The proposed FedOpt, as an extension of FedAvg, can incorporate adaptive optimizers for the server-side model update, and thus provide a general framework that can potentially cover a family of FL algorithms, which can be an important contribution to the FL community. 

(3) The interpretation of the bounds is also informative: showing several expected or preferred trade-offs in FL and sheds light on how to reduce the communication costs and the negative effects of client heterogeneity. 

(4) The experiments show the compelling performance of the proposed methods, especially on Stack Overflow LR and EMNIST AE, on which the improvements over the other two baselines are remarkable.

Cons and suggestions:

(1) One main novelty and focus of this paper is the server-side adaptive optimization, and the purpose is to combat client drift and reduce the variance of stochastic gradient, especially in the cross-device FL setting. However, is it the case that improving client-side optimization can be more effective in resolving these two issues? FedOpt covers the client-side optimization in its framework but did not expand it on possible options, while other works like FedProx focus more on it. It would be helpful to provide a discussion and comparison of the two strategies and their advantages/disadvantages on the two issues.

(2) The theoretical bounds show the trade-off between T and K, the client and server learning rates, and the client heterogeneity. In experiments, only different options of client and server learning rates have been studied. It would be more sound to show the other trade-offs indicated by the bounds.

(3) In experiments, FedAvgM is a very competitive baseline since on most tasks, its performance is very close to the proposed methods, except on SO LR and EMNIST AE. Considering its similarity in methodology with FedOpt, it reduces the novelty of the paper.

(4) There are only three FL baselines that have been compared in the experiments. Is there a specific reason for not including other FL methods into the comparison? In addition, it is interesting to compare with (i) FedOpt with both adaptive client optimizer (or FedProx) and adaptive server optimizer and (2) FedOpt with only adaptive client optimizer.
review_title: A general framework for cross-device FL, focus on adaptive server optimizers, interpretable convergence bounds, comparison to adaptive client optimizer and experiments can be strengthened.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes several federated variants of adaptive stochastic gradient methods.   Moreover,  the convergence rates of the proposed algorithms are also provided.  Based on the current submission,  The reviewer has several concerns: 

1. The adaptive learning rates in FedAdagrad/FedYogi/FedAdam are all related to parameter $\tau$.  According to Theorem 1-2, Corollary 1-2,   $\tau$ needs to set as a large constant $G/L$.   When  $\tau$ is sufficiently large, FedAdagrad/FedYogi/FedAdam is actually reduced to FedSGD. Can the authors give several comments on this parameter? 

2. The second question is about the generalization ability of federated adaptive stochastic gradient methods.   It has been demonstrated in [1] that adaptive SGD generalizes poorly compared with SGD.  A natural question is that "  does this dilemma still exists in federated stochastic gradient methods? " 

[1] Wilson AC, Roelofs R, Stern M, Srebro N, Recht B. The marginal value of adaptive gradient methods in machine learning. In Advances in neural information processing systems 2017 (pp. 4148-4158).
review_title: The relationship between the proposed FedAdagrad/FedYogi/FedAdam and FedSGD

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the convergence of well-known adaptive methods, ADAM, ADAGRAD, and YOGI, for the federated learning problem. In particular, while the nodes (clients) still use SGD for their local computations (same as Fed-Avg), the server uses one of the three adaptive methods mentioned above to update the model. The authors have provided convergence rates (based on gradient norms) for all three methods for the nonconvex settings. Moreover, various experiments have been conducted to compare the strengths of these methods against classic FedAvg. Overall, this paper is well-written, and the problem statement and the goal of the paper are clear. Moreover, the authors have shown the success of using adaptive methods in numerical settings.

My main questions are regarding the theoretical analysis of the paper. First, the analysis of adaptive methods in the nonconvex setting has been studied in the literature (as mentioned by the authors as well in the related work). Given the bounded gradient assumption imposed in this paper, I am not sure what would be the main challenge in extending those analyses to the federated setting. I encourage the authors to highlight possible novelties in their analysis compared to prior works on adaptive methods for nonconvex objective functions.   


Second, it is not clear to me how this paper's theoretical results would imply that adaptive methods enjoy better convergence rates compared to regular Fed-Avg. In particular, all the algorithms achieve the rate of $O(1/\sqrt{T})$, and do not differ from each other in that aspect. To better highlight my point, for instance, let's consider the convex setting. There, Duchi et al. show that while AdaGrad has $O(1/\sqrt{T})$ convergence rate in the worst case (same as SGD), it can achieve better rates in certain scenarios, such as gradients being sparse over coordinates, etc. Hence, this way, the theoretical result shows the advantage of using adaptive methods over the standard SGD method. From my understanding, this paper does not provide that kind of results, and so one important question remains unanswered: Why switching to adaptive methods after all? I would appreciate it if the authors provide further discussions on this matter.

-----

Post rebuttal comment: I appreciate the authors' responses, especially on highlighting the theoretical challenges. I have raised my score accordingly.
review_title: Characterizes the convergence of adaptive methods for federated learning; the necessity of using adaptive methods remains open

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: This paper presents an adaptive federated optimization framework that induces three different adaptive federated learning algorithms, which are proposed to address the issues of client drift due to data heterogeneity and lack of adaptivity. The authors presented thorough literature survey on the federated learning and formulated the meta-algorithm, FedOpt, introducing both server and client optimizers. Different from the popular FedAvg, the server optimizer in this work is an adaptive protocol which is originated from the client drift. The authors analyzed mathematically the convergence rates of the proposed framework and showed extensive experimental results on different benchmark datasets to validate the efficacy of the developed algorithms.

Overall, this paper is well organized and technically sound. It is also easy to follow. The overall proof ideas are also correct, though I didn’t derive step by step. However, the authors need to pay attention to the following points to improve the current draft.

1. Server optimizer can be confusing. The server optimizer developed in this study generalizes to a more adaptive one. But it is not really an optimization in the server, instead just another form of local model averaging in order to obtain the global model. I completely understand the motivation for this is to improve the performance beyond FedAvg, which may not necessarily perform well with non-IID data. However, without using zeroth order or first order information of objectives, to me, the so-called server optimizer is just a nonlinear local model averaging.
2. The server learning rate is bit counterintuitive. In Corollary 1 and 2, when defining the learning rate for the server, it looks like $\eta$ can be quite large. Of course, given the fact that the server optimizer is not really an optimization, that could be understandable. Additionally, the authors empirically investigated the relationship between the server and client learning rates in the appendix. But to me, it is naturally a parameter that plays a similar role as learning rate, not exactly the learning rate. 
3. The communication efficiency needs more discussion. In Section 3, the authors presented one discussion on the communication efficiency, particularly quantifying $K$. I wonder how the authors obtained that. Also, it would be great to see more quantitative results on the communication efficiency. 
4. Client heterogeneity is only qualitative in the paper. Based on the empirical implementation, I couldn’t find out how the authors simulated the non-IID data distributions for different clients for each benchmark task. This needs more detail. Also, the authors mentioned that the proposed framework can work effectively for moderate and naturally arising heterogeneity. But under how much heterogeneity does the algorithms work well? For example, for CIFAR 10, if having 10 clients, each client has only one class without any overlapping, is FedOpt still effective?
5. The experimental results look promising, but not showing significant outperforming capability. From Table 1, we can still observe that for some tasks, the AvgM is still favorably comparable. Also, when to select which method among FedAdam, FedAdaGrad, and FedYOGI is unclear. The authors need to give more discussion.
6. Based on the Corollary 1 and 2, it looks like when $T$ is sufficiently large, the FedOpt can achieve linear speed up, correct? However, the authors failed to give the specific lower bound for $T$, even if they only mentioned the dominating term that induced a sublinear rate.

***********************************
After carefully considering the rebuttal from the authors, I think I am more positive about the paper so I raised my score. The rebuttal clarifies most of my confusion about the paper, though more improvement can be done. 
review_title: Review of "Adaptive Federated Optimization"

Meta-review: The paper proposes adaptive optimization algorithms for federated learning that are federated versions of existing adaptive algorithms such as Adam, Adagrad, and Yogi. The paper establishes convergence guarantees for the proposed algorithms and performs an extensive experimental evaluation. Following the discussion, the reviewers were positive about the paper and felt that the author responses addressed their concerns. I recommend accept.
Decision: Accept (Poster)