Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes to optimize the hyperparameters and parameters of a federated learning model jointly via gradient descent in an online fashion. To achieve this, the paper extends previous works on hypergradient to derives analytical gradients with respect to the local learning rate and the number of gradient steps. The paper analyzes the convergence of the proposed method and verifies the empirical improvement over FedAvg using real-world FL experiments.
strengths_and_weaknesses: Strengths:
- The proposed method is able to jointly optimize the hyperparameters and weight parameters of an FL model in a one-shot online manner, which is a natural and promising direction.
- The approach taken by the paper is reasonable: derive the gradient w.r.t. the hyperparameters of interest, and then use gradient descent to optimize them together with model parameters.

Weaknesses:
- A few related works are missing which I have listed below. Reference [*a*] aims at single-shot hyperparameter optimization for FL, i.e., they aim to identify a single set of hyperparameters which work well for multiple applications, and hence should be cited in the first paragraph of Section 2; [*b*] also used Bayesian optimization for hyperparameter optimization in FL and hence should be added to lines 114-116; [*c*] provided a benchmark for federated hyperparameter optimization.     
[*a*] Single-shot Hyper-parameter Optimization for Federated Learning: A General Algorithm & Analysis, 2022.   
[*b*] Differentially Private Federated Bayesian Optimization with Distributed Exploration, NeurIPS 2021.   
[*c*] FedHPO-B: A Benchmark Suite for Federated Hyperparameter Optimization, 2022.   
- In the experiments, the proposed method is only compared with vanilla FedAvg, which may not be enough especially since a number of related works on single-shot federated hyperparameter optimization have been listed in Section 2. Even if comparisons are not possible, some justifications should be given.
- Theorem 3: instead of listing the detailed expressions of the entire theorem, I would prefer to see some interpretations/insights regarding the theoretical results. For example, how do the additional components introduced by the proposed algorithm (i.e., adaptive tuning of $\eta$ and $K$) affect the convergence of FedAvg? Are there conditions under which these additional components can lead to better convergence then standard FedAvg according to Theorem 3?
- Perhaps partially due to my unfamiliarity with gradient-based optimization, I feel that some of the technical details should be given more explanations. Firstly, Assumption 2 may need some further explanations and justifications. For example, $x_t$ and $\mathbb{E}_t$ haven't been introduced till this point. A justification should be given as to how realistic this assumption is. Secondly, in Equation (5), some more explanations on how the last $\approx$ is derived are needed. Next, in equations (14) and (15), why are these two equations designed in this way?
- The paper has many typos, for example:   
-- line 34: a -> an
-- line 56: justify -> justifying; a -> an
-- line 104: directing -> directly
-- line 145: $K$ should be $K_i$?
questions: I've listed a few questions and comments as "Weaknesses" in the section above.
limitations: A limitation and potential negative societal impact are both discussed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: I am not an expert in this area and do not know anything about federated learning. The last time I worked directly with hyperparameter optimization approaches was in 2017 but was focused on offline hyperparameter optimization and not in the context of federated learning. As such, my review is not very insightful.

---

The paper proposes an approach for online hyperparameter optimization in a federated learning setting. The proposed approach (FATHOM) is more communication efficient than previous approaches and achieves better results than previous approaches with manually fine-tuned hyperparameters. However, since it assumes access to gradients it is restricted to a certain set of hyperparameters that can be optimized and the paper evaluates the approach by optimizing the client learning rate, number of local steps, and batch size. Compared to a baseline (FedAvg) the proposed approach is more efficient and obtains better final test accuracy.
strengths_and_weaknesses: The paper motivates its approach well and clearly states its advantages and limitations compared to other approaches. The comparison to FedAvg is based on different hyperparameter initializations and shows improved results on most of them.
I did not check the theoretical convergence part.
The evaluation of the approach seems clear.
questions: I can't comment on the evaluation protocol itself since I don't know the related work. The target accuracy numbers seem somewhat arbitrary (86% and 23%) but may be standard for this kind of evaluation.
limitations: The paper itself mentions several limitations, such as applicability only to specific hyperparameters for which gradients can be obtained.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a method for tuning the client step-size, number of epochs, and batch-size of FedAvg in a oneshot manner. They propose hypergradient-style updates to these quantities that can be done simultaneously with updating the parameters. The algorithm is evaluated on FEMNIST and StackOverflow.
strengths_and_weaknesses: **Post-rebuttal:** 
Following clarification from the authors, I have decided to raise my score slightly but still cannot fully endorse this submission. Overall I think it is somewhat unsatisfactory to have to make such a strong assumption (convexity of the loss w.r.t. the batch-size in the sense of Murota (1990)) just to obtain subgradients. In particular, what is a bit jarring is the fact that it is still unclear whether there is *any* scenario under which this assumption holds. Standard regularity assumptions, while restrictive, at least come with specific model classes and loss functions under which they hold. Here are some things that would strengthen the theoretical component of the work:
1. Including a statement of the definition from Murota (1998) in the paper explicitly and showing where it is used in the proofs. 
2. Defining subgradients for non-convex functions in the discrete setting, as they can be for the continuous setting (Clarke, 1990).
3. Providing an explicit setting where Assumption 2 holds.
4. Providing experimental evidence that Assumption 2 holds in practice. In particular, this type of convexity should be easy to measure because the underlying set is not uncountable.

Summary:
The paper is reasonably well-motivated, and the approach of targeting a few hyperparameters seems sensible. The experimental results indeed seem to demonstrate the utility of the proposed method. However, I have strong concerns regarding the assumptions the theoretical results and other concerns regarding the experimental comparison and discussion of past work that make me hesitant to accept the paper. 

Strengths:
1. The paper tackles an important and timely problem in federated learning.
2. The authors devote a good deal of time to the communication and local computation complexity of their approach, both in the method development and empirical comparison sections.
3. The method is evaluated on relevant benchmarks in computer vision and NLP.
4. Code is included.

Weaknesses:
1. The derivation of the hypergradients lack a lot of detail. Theorem 1 introduces a great deal of machinery to try and define a sub-gradient w.r.t. a continuous surrogate variable of a discrete function. How the piecewise function L corresponds to the objective, what l represents precisely (rather than in words), and how Theorem 1 is used in the later proofs should be explained more precisely. The derivation of the gradients for the batch size and number of epochs in (14) and (15) is also not thoroughly explained.
2. Assumption 2, used by all three theorems in the paper, seems extremely strong. Is there at least an example of a function class in which this holds? Otherwise it seems the paper is avoiding the need to take derivatives through local iterations by optimizing an upper bound, and also hiding this in an assumption without discussing whether it is reasonable.
3. The experimental evaluation does not compare to baselines other than FedAvg, such as general hyperparameter tuning methods or the FL-specific methods discussed in the related work.
4. Some of the discussion of past federated hyperparameter optimization work is incorrect (see notes).
5. The method only works for tuning three hyperparameters. The authors do acknowledge this limitation, and it is indeed reasonable to focus on specific hyperparameters, e.g. if they are especially important. However, it would be good to have a discussion of whether the ones chosen here are indeed the most impactful.

&nbsp;  
**References:**  
1. Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
2. Murota. Discrete convex analysis. Mathematical Programming, 1998.
questions: Notes:
1. 12: what does “open-boxed” mean?
2. 56: having difficulty following what this sentence is saying
3. 68: what is a “relaxed condition”?
4. 98: the two papers use different models and subsets of the data and so their settings are incomparable
5. 129: I suggest using \mathbb R instead of \mathcal R to denote the set of real numbers
6. 150: what do A, B, and I represent? also B was used earlier to denote the batch size
7. 169: I do not believe either paper states this as their objective
8. Theorem 1: this theorem also requires Assumption 1
9. Theorem 2: this theorem requires Assumptions 1 and 2
10. 225: the choice of using the bias is itself a hyperparameter
11. 263: this is an online convex optimization method? My understanding was the function f itself is non-convex. 
limitations: The authors address the limitation of only being able to tune a few hyperparameters. Other limitations, especially the theoretical assumptions made and in the empirical evaluation, are less-discussed.
review_title: null

Meta-review: metareview: We thank the authors and the reviewers for their involvement in this interactive reviewing process. While the paper clearly generated interest and brings new notions to the community, we felt that a major revision is necessary before the paper can be a successfull NeurIPS submission. Consequently, we unfortunately recommend rejection. Points that stood out are 

1. at least one essential assumption is simultaneously strong, hard to check in practice, and not appropriately discussed in the original version;
2. unusual but central notions like discrete convexity and hypergradients are not appropriately introduced. This made important technical parts of the paper hard to proofread;
3. lack of some natural baselines.

We hope that the detailed discussions will be useful in further improving the manuscript.



confidence: Certain
Decision: Reject