Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a method for learning client-side hyperparameters in the federated setting by parameterizing the distribution of these hyperparameters and estimating gradients with respect to this parametererization. This approach is connected to weight-sharing methods in neural architecture search.

This paper provides a theoretical statement in a simplified setting justifying the approach taken--showing that for some settings this approach can improve average regret.

This paper also provides a reasonably thorough empirical evaluation of this approach, along with standalone implementations in the supplementary material.
main_review: Some fine-grained notes:

1. I find the formulation (1) a little strange--that is, there seems to be a suppressed dependence on the parameter w, or a suppressed integration over time. The output of Alg_a depends not just on T_j but also on w--so without express dependence here (or something more explicitly e.g. variational in nature) I think the formulation (1) is somewhat confusing.

2. Is there a silent assumption in SGD_c that we are actually doing SGD on something? The name gives me this intuition, but I can’t spot this in the paper itself. If not, maybe consider a rename (e.g. to Loc_c for ‘local update parameterized by c’ or something).

3. There is an additional and somewhat subtle difficulty in evaluating hyperparameters in FL which could profitably be further highlighted in the challenges and baselines section. This is the *time*-dependence of evaluation metrics in many real world FL applications. There isn't a tremendous amount of literature on this phenomenon, but one paper I am aware of is here: https://arxiv.org/pdf/1904.10120.pdf.

4. Nit: it seems like Alg1 and Fig 2 dont quite match--that is, it seems to me that Alg 1 corresponds to ‘last only’ and cant capture the other discount factors? This mismatch makes a quick read a little more difficult.

5. Another nit: a further natural baseline here (one that actually does seem relevant to me): how does performance scale here with respect to clients per round? This is relevant because of the calling-out of unnaturalness of only using last-round validation data--this becomes more reasonable as round size blows up. This would make the baselines much more compelling to me, to have a dataset of essentially unbounded scale (e.g. StackOverflow next-word-prediction) on which very large-scale training was analyzed.

6. (this is potentially genuine confusion, as I am no expert in the NAS literature) It seems to me that the connection to NAS is a little unnatural. In my mind it seems easier to consider (6) and (7) direct from (2). So it seems like NAS and weight sharing...is only there to say ‘introducing this sampling/reparameterization procedure is not a crazy thing to do’? I think this is a reasonable framing, but I'm not sure it fits with the rest of the positioning of the paper--the rest of the paper positions a little too front-and-center if my understanding is correct.

7. Nit typo (L269): s/shws/shows

8. The error bars for these table entries are *really* large. I for sure appreciate their inclusion! Checking my understanding here: these error bars represent more or less a single standard deviation around the estimated mean? IE, this std dev represents the uncertainty in the estimate of the mean itself? Assuming this is true, it seems to me that I can't really in good faith consider virtually any of these empirics to be informative. There is an alternative possibility here: that these std dev numbers rather represent the empirical standard deviation of the e.g. accuracy estimates (so that they can't be easily reduced by collecting more samples from the accuracy distribution).

This comment began as an ask for explanation of the behavior of shakespeare under random search--thinking about this is what led to closer scrutiny of the associated error bars, and made me think that this difference in point estimates may have simply been random fluctuation. This got me to thinking more deeply about the meaning of these error bars--and this thinking became a crux of the review.

If I am reading these error bars correctly (would love some clarification if I'm not), very few of these empirical differences are even a standard deviation away from those generated without FedEx. These variance estimates make it *very* difficult (maybe impossible?) to evaluate the empirical value of this approach. Given that this paper is mostly framing / empirical in nature, and as far as I read the theoretical statement is there mostly to support the idea that this approach is reasonable, I would need to see more precise empirical results to raise my score.

This in fact raises a question: assuming my understanding of the error bars is correct, why weren't these numbers reduced simply by running *more* iterations--with different seeds, different client orders, etc (abstractly, taking more samples from the well-defined random variable, test error on dataset X)? Assuming that these samples are independent (and given the ability to fairly precisely specify the randomness in the algorithm, this does not seem like a crazy assumption to me), and the boundedness (and hence necessarily sub-Gaussian nature) of the metrics of interest, an out-of-the-box Chernoff-like bound should apply and the precision on the point estimates should be able to be driven as small as desired (given enough samples).

If my guess for the meaning of the error bars is incorrect (and they represent something like empirical std dev of independent runs of the algorithm), then I think the paper needs to be updated with some more detail of experimental setup, what precisely these numbers mean, how we should interpret the point estimates and the associated variances, probably a computation like the one just described, etc. 

Either way, I think given the mostly-practical nature of this paper, there is some clarification to be done around the meaning of these numbers. Either these numbers should be driven down, or some explicit quantification of uncertainty around the point estimates should be provided. It is very difficult to evaluate the empirical contributions of this paper without this information, or with such wide uncertainty estimates.
limitations_and_societal_impact: Societal impact is a potential strength of this paper, which could be highlighted further: the methods this paper proposes are eminently composable with standard privacy-preserving techniques in FL (like differential privacy and secure aggregation), whereas this is not necessarily the case for every imaginable approach to automating hyperparameter tuning in the federated setting.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper analyzes three challenges in hyperparameters tuning under the federated learning setting. The paper proposed two straightforward solutions (random search and successive halving) as baselines and one method, namely FedEx, as the solution to tackle those challenges. The two baselines tune hyperparameters directly. FedEx tunes hyperparameters via learning the relationship between validation scores and the hidden variables of hyperparameters. The proposed method was experimentally validated by tuning regular hyperparameters on three datasets.

main_review: Originality:
The targeting problem is to tune hyperparameters for machine learning models in federated settings. The proposed method FedEx is an interesting idea to build links between weight-sharing mechanisms and hyperparameter tuning. This mitigation allows a simultaneous searching for multiple hyperparameters in a very efficient way.

Quality:
The quality of the paper could be improved. The paper title is "Federated Hyperparameter Tuning." However, the paper only targets tuning non-architectural parameters. For non-architectural parameters tuning, the paper has a good experiment and ablation study to support the claims.

Clarity: The paper is clearly written and well organized. Details of proof and experiments are given in the supplement.

Significance: The result is important in a practical setting. Despite the paper only testing the idea with regular hyperparameter tuning. Using it on architecture search would have a promising future.

=== Post Rebuttal ===

The paper is well written, and its claims are well supported by the experiments. The connection between hyperparameter tunning and weight-sharing mechanism is an interesting point, however, it also makes the paper looks like an ensemble of two pieces. 
limitations_and_societal_impact: I have a few questions about the paper.

1. How many GPU hours does it take to reproduce the experiment?
2. The argument that "personalized losses require several forward-backward passes"(line 130 to line 135) is a little bit confusing. 
3. What does this mean, and how does FedEx tackle the problem? Any example that personalized FL uses several forward-backward passes?
4. In algorithm 2, what's the meaning of "1 ctj=cj" (the Fourth line from last)
5. What’s the meaning of the shadow in figure 4. Std for multiple runs or std for clients?
6. Is Dθt (algorithm 2) different across different clients?
7. How to obtain the personalized model by FedEx?
8. The FedEx is tested with FedAvg, FedProx, and Reptile. But there is only one set of results.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a general hyperparameter tuning framework for federated learning based on the weight-sharing technique. In contrast to tuning architectural parameters as in NAS, this paper focus on tuning non-architectural parameters. The proposed framework is general enough to be applied to many FL algorithms including FedAvg, FedProx, and SCAFFOLD. A theoretical study is offered for tuning client step-size. Empirical experiments on Shakespeare, FEMNIST, and CIFAR-10 show promising results.
main_review: **Originality**: the paper presents an interesting formulation for hyperparameter tuning in federated learning. Although weight-sharing is a well-known technique in NAS for tuning architectural parameters, the formulation of adopting weight-sharing for tuning local SGD parameters in FL is an interesting idea.

**Quality**: the paper is technically sound. It gives a clean mathematical formulation with thorough explanation of motivations.

**Clarity**: the paper is well written and easy to follow.

Minor presentation issues: 
- Algorithm 1, on page 4, is not introduced in the text of section 2, while being referred to a few times starting page 6.
- Equation 4, RHS misses min variable $w$ for $w \in \mathbb{R}^d$.
- Title and axis labels in all plots can be bigger for better readability.

**Strengths**

1. The proposed FedEx method is a simple and clean framework that integrates well with the local-optimization + aggregation style algorithms, such as FedAvg, FedProx, Reptile.

1. The method respects the resource limitation on federated clients and does not incur excessive computation cost. Only sampling a configuration, the client side does not have much increased workload; whereas on the sever side takes  update steps with exponentiated gradients.

1. By using weight-sharing technique and sampling from the hyperparameter distribution, the proposed method does not suffer from premature stopping from noisy elimination decisions as in SHA.

**Weaknesses**

1. Although the authors in Eq 1 and 2 present a rounded formulation on optimizing hyperparameters $a = (b, c) \in \mathcal{B} \times \mathcal{C}$, by looking at algorithm 2, FedEx can only be applied to optimizing local SGD parameters $c$ while not aggregation parameters $b$. The authors state in L214 that the wrapper in Algorithm 1 can help turning $b$, but wouldn't that mean the tuning of $b$ may suffer from issues outlined in page 4 (such as premature early stopping)?

1. The tuning scheme relies on using personalized validation error from individual clients. However, looking at Table 1, the global models obtained after aggregation almost always have lower error than personalized models for all datasets except FEMNIST, regardless of RS or SHA wrapper. Can authors offer some insights?
limitations_and_societal_impact: N/A
review_title: null

Meta-review: This paper studies hyperparameter optimization in FL, which is often neglected but a crucial part of FL. The paper provides interesting ideas to tackle this challenging problem. After the discussion phase, the reviewers are all in favor of accepting the paper. I recommend acceptance. I suggest the authors revise the paper to address the reviewers' concerns.
Decision: Accept (Poster)