Federated Hyperparameter Tuning: Challenges, Baselines, and Connections to Weight-Sharing
Authors: Mikhail Khodak
Renbo Tu
Tian Li
Liam Li
Nina Balcan
Virginia Smith
Ameet Talwalkar
Venue: NeurIPS 2021 Poster (2021)
Keywords: federated learning
hyperparameter optimization
meta-learning
personalization

Abstract: Tuning hyperparameters is a crucial but arduous part of the machine learning pipeline. Hyperparameter optimization is even more challenging in federated learning, where models are learned over a distributed network of heterogeneous devices; here, the need to keep data on device and perform local training makes it difficult to efficiently train and evaluate configurations. In this work, we investigate the problem of federated hyperparameter tuning. We first identify key challenges and show how standard approaches may be adapted to form baselines for the federated setting. Then, by making a novel connection to the neural architecture search technique of weight-sharing, we introduce a new method, FedEx, to accelerate federated hyperparameter tuning that is applicable to widely-used federated optimization methods such as FedAvg and recent variants. Theoretically, we show that a FedEx variant correctly tunes the on-device learning rate in the setting of online convex optimization across devices. Empirically, we show that FedEx can outperform natural baselines for federated hyperparameter tuning by several percentage points on the Shakespeare, FEMNIST, and CIFAR-10 benchmarks—obtaining higher accuracy using the same training budget.

Federated Hyperparameter Tuning: Challenges, Baselines, and Connections to Weight-Sharing
Mikhail Khodak, Renbo Tu, Tian Li Carnegie Mellon University [ichodakrrenbo tianli)@cmu.ce
Liam Li
Hewlett Packard Enterprise me01 m00liamcli..m com
Maria-Florina Balcan, Virginia Smith Carnegie Mellon University ninamf$cs. cmu edu, smi tarietheem...mmm edu
Ameet Talwalkar
Camegie Mellon University & Hewlett Packard Enterprise talvalkar@cmu. edu
Abstract
Tuning hyperparameters crucial but arduous part of the machine learning pipeline. Hyperparameter optimization is even more challenging in federated learn- ing, where models are learned over distributed network of heterogeneous devices; here, the need to keep data on device and perform local training makes it difficult to efficiently train and evaluate configuratio configurations. In this work, investigate the prob- lem of federated hyperparameter tuning. We first identify key challenges and show how standard approaches may be adapted to form baselines for the federated setting. Then, by making a novel connection to the neural architecture search technique of weight-sharing, we introduce new method, FedEx, to accelerate federated hyperparameter tuning that is applicable to widely-used federated optimization methods such as FedAvg and recent variants. Theoretically, we show that a FedEx variant correctly tunes the on-device learning rate in the setting of online convex optimization across devices. Empirically, we show that FedEx can outperform natural baselines for federated hyperparameter tuning by several percentage points on the Shakespeare, FEMNIST, and CIFAR-10 benchmarks obbaaninn higher accuracy using the same training budget.
Introduction
Federated learning (FL) a popular distributed computational setting where training is performed locally or privately [30, 36] and where hyperparameter tuning has been identified as critical problem [18]. Although general hyperparameter optimization has been the subject of intense study [3, 16, 26), several unique aspects of the federated setting make tuning hyperparameters especially challenging. However, to the best of our knowledge there has been no dedicated study on the specific challenges and solutions in federated hyperparameter tuning. this work, we first formalize the problem of hyperparameter optimization in FL., introducing the following three key challenges:
1. Federated validation data: the entire dataset not available at any one time; instead a central server is given access to some number of devices at each communication round, for one or at most few runs of local training and validation. Thus, because the standard measure of complexity in FL the number of communication rounds, computing validation metrics exactly dramatically increases the cost.
In federated networks, as the validation data is split across devices,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

FedEx
hyperparameters
exponentiated update
local training
local evaluation
model update
model parameters
FedAvg
Figure 1: FedEx can be applied any local training- based FL method, e.g. FedAvg, by interleaving standard updates to model weights (computed by aggregating results of local training) with exponen- tiated gradient updates to hyperparameters (computed by aggregating results of local validation).
2. Extreme resouree limitations: FL applications often involve training using devices with very limited computational and communication capabilities. Furthermore, many require the use of privacy techniques such as differential privacy that limit the number times user data can be accessed. Thus we cannot depend on being able to run many different configurations to completion.
3. Evaluating personalization: Finally, even with non-federated data, applying common hyperpa- rameter optimization methods standard personalized FL approaches (such as finetuning) can be costly because evaluation may require performing many additional training steps locally.
With these challenges' in mind, we propose reasonable baselines for federated hyperparameter tuning by showing how adapt standard non-federated algorithms. We further study the challenge of noisy validation signal due to federation, and show that simple caate-estimation-beee based fixes do not help.
Our formalization and analysis of this problem leads us to develop FedEx, a method that exploits a novel connection between hyperparameter tuning in FL and the weight-sharing technique widely used in neural architecture search (NAS) [4, 34, 40]. In particular, is a natural way of addressing the three challenges above for federated hyperparameter tuning, as it incorporates noisy validation signal, simultaneously tunes and trains the model, and evaluates personalization as part of training rather than as a costly separate step. Although standard weight- sharing only handles architectural hyperparameters such the choice of layer or activation, and not critical settings such as those of local stochastic gradient descent (SGD), we develop formulation that allows us tune most of these as well via the relationship between local- -ecal-training and fine-tuning, based personalization. This make FedEx a general hyperparameter tuning algorithm applicable to many local training- based FL methods, c.g. FedAvg [36], FedProx [31], and SCAFFOLD [19].
observe that weight-sharing
In Section 4, we next conduct a theoretical study of FedEx in a simple setting: tuning the client step-size. Using the ARUBA framework for analyzing meta-leariig [20], we show that variant of FedEx correctly tunes the on-device step-size to minimize aieerged regret by adapting to the intrinsic similarity between client data. We improve the convergence rate compared to some past meta-learning theory [20, 25] while not depending on knowing the (usually unknown) task-similarity.
Finally, in Section 5, we instantiate our baselines and FedEx to tune hyperparameters of FedAvg, FedProx, and Reptile, evaluating on three standard FL benchmarks: Shakespeare, FEMNIST, and CIFAR-10 [5, 36]. While our basclines already obtain performance similar to past FedEx further surpasses them in most settings examined, including by 2-3% on Shakespeare.
Related Work To the best of our knowledge, we are the first to systematically analyze the formu- lation and challenges of hyperparamettr optimization in the federated setting. Several papers have explored limited aspects of hyperparameter tuning in FL [7, 23, 38), focusing on a small number of hyperparameters (e.g. the step-size and sometimes one or two more) less general settings (studying small-scale problems or assuming server-side validation data). In contrast our methods are able to tune wide range of hyperparameters in realistic federated networks. Some papers also discussed the challenges of finding good configurations while studying other aspects of federated training [41]. We argue that it critical to properly address the challenges of federated hyperparameter optimization in practical settings, as we discuss in detail in Section 2.
Methodologically, our approach draws on the fact that local training- based methods such as FedAvg can be viewed as optimizing a surrogate objective for personalization [20], and more broadly leverages the similarity of the personalized FL setup and initialization-based meta-learning [6. 11, 17, 25). While FedEx's 's formulation and guarantees use this relationship, the method itself is general-
'A further challenge do address is that of the dependdenyy of federated evaluation, c.f. [9].

---

and applicable to federated training of single global model. Many recent papers address FL personalization more directly [13, 29, 35, 43, 47]. This connection and our use of NAS techniques also makes research connecting NAS and meta-learning relevant [10, 33], but unlike these methods we focus on tuning non-architectural parameters. In fact, we believe our work is the first to apply weight- sharing to regular hyperparameter search. Furthermore, mneta-learning does not have the data-access and computational restrictions of FL, where such methods using the DARTS mixture relaxation [34] are less practical. Instead, FedEx employs the lower-overhead stochastic relaxation [8, 28], and its exponentiated update is similar to the recently proposed GAEA approach for NAS [27]. Running NAS itself in federated settings has also been studied [12, 15, 46]; while our focus is on non-architectural hyperparameters, in- in-principle our algorithms can also be used for federated NAS.
Theoretically, our work makes use of the average regret-upper-bound analysis (ARUBA) frame- work [20] to derive guarantees for learning the initialization, i.e. the global model, while simul- taneously tuning the step-size of the local algorithm. The step-size of gradient-basee algorithms has also been tuned on its own in the settings of data-driven algorithm design [14] 4] and of statistical leaming-to-leam [45].
2 Federated Hyperparameter Optimization
In this section we formalize the problem of hyperparameter optimization for FL and discuss the con- nection of its personalized variant meta-learning. We also review FedAvg [36], common federated optimization method, and present a reasonable baseline approach for tuning its hyperparameters.
Global and Personalized FL. In FL we are concerned with optimizing over a network of heteroge- neous clients = 1, ......;7 n. each with training, validation, and testing sets T,, Vi, and E,, respectively. We use [s(w) to denote the average loss over dataset S of some w-parameterized ML model, for W E Idd some real vector. For hyperparameter optimization, we assume a class of algorithms Alg, hyperparameterized by a E that use federated access to training sets T; to output some element of communication round at
RR. Here by "federated access" we mean that each iteration corresponds which Alg, has access to batch of B clients² that can do local training and validation.
Specifically, we assume Alg. can be described by two subroutines with hyperparameters encoded by E B and E C. so that a = (b, c) and A B C. Here encodes settings of local training algorithm Loc, that take training set S and initialization E Rd input and outputs model (S, w) E Rd, while sets those of an aggregation Agg, that takes the initialization w and outputs of Loc, as input and returns a model parameter. For example, in standard FedAvg, Loc, is T steps of gradient descent with step-size and Agg, takes a weighted average of the outputs of Loc, across clients; here c = (17, T) and b (). As detailed in the appendix, many FL methods can be decomposed this way. including well-known ones such as FedAvg [36], FedProx [31], SCAFFOLD [19], and Reptile [39] as well as more recent methods [1. 2, 29]. Our analysis and our proposed FedEx algorithm will thus apply to all of them, up to an assumption detailed next.
Starting from this decomposition, the global hyperparameter optimization problem can be written as
min A
LV, ((
((T))
In many cases we are also interested in obtaining a device-specific local model, where we take model trained on all clients and finetune it on each individual client before evaluating. A key assumption we make is that the finetuning algorithm will be the same as the local training algorithm Loc, used by alg.- This assumption can be justified by recent work in meta-learning that shows that algorithms that aggregate the outputs of local SGD can be viewed as optimizing for personalization using local SGD [20]. Then, in the personalized setting, the tuning objective becomes
min a=(b,o)AA
Σ
A1g ((T)),
(2)
Our approach will focus the setting where the hyperparameters of local training make up significant portion of all hyperparameters a = c); by considering the personalization objective we will be able treat such hyperparameters architectural and thus apply weight-sharing.
3

---

Algorithm I: Successive halving algorithm (SHA) ap- plied to personalized FL. For the non-personalized ob- jective (1), replace Lv, (w;) by Lv., VV..(w.. (w.). For random search (RS) with N samples, set 17 = N and R 1.
baring rommer wedldd
onl (overago)
distribution D over hyperparameters A, elimination rate 7) E N, elimination rounds = 7 TR sample set of r hyperparameters H ~ Dbr"1
Input:
initialize a model Wa E RR for each a E H for elimination round r E [R] do
0.0 last only [sswee dbcccnt)
(avemge)
for setting a = (b, c) E H do for comm. round
-- +1,
Tr do
for client i = 1,... do send Wa, C to client
w; + LTc. Wa)
send w., Lvv (w;) to server
Tuning FL with SHA but mak- ing elimination decisions based on vali- dation estimates using different discount factors. On both FEMNIST (top) and CI- FAR (bottom) using more of the validation data does not improve upon just using the most recent round's validation error.
Figure 2:
Wa + Agg, (Wa: (wa, [w:) 1B
So Ei=1 | Lv, ww.) )/ Ei= VVall
H fa E H Sn } -
H}))
Output: remaining a E H and associated model Wa
Tuning FL Methods: Challenges and Baselines In the non-federated setting, the objective (1) is amenable to regular hyperparameter optimization methods; for example, a random search approach would repeatedly sample a setting a from some distribution over A, run Alg,, to completion, and eval- uate the objective, saving the best setting and output [3]. With a reasonable distribution and enough samples this is guaranteed to converge and can be accelerated using early stopping methods [26], in which Alg., is not always run to completion if the desired objective is poor at intermediate stages, or by adapting the sampling distribution using the results of previous objective evaluations [44]. As mentioned in the introduction, applying such methods to FL. is inherently challenging due to
1. Federated validation data: Separating data across devices means we cannot immediately get a good estimate of the model's validation performance, as we only have access to a possibly small batch of devices at time. This means that decisions such as which models to flag for early stopping will be noisy and may not fully incorporate all the available validation signal.
2. Extreme resource limitations: As FL algorithms can take a very long time to run in in-raactice due to the weakness and spotty availability of devices, we often cannot afford to conduct many training runs to evaluate different configurations. This issue is made more salient in cases where we use privacy techniques that only allow limited number of accesses to the data of any individual user.
Evaluating personalization: While personalization is important in FL due client heterogeneity, checking the performance of the current model on the personalization objective (2) is computation- ally intensive because computing may require running local training multiple times. In particular, while regular validation losses require computing one forward pass per data point, personalized losses require several forward-haad -ackkrdd passes, making many times more expensive if this loss is needed to make tuning decision such as eliminating configuration from consideration.
Despite these challenges, we can still devise sensible baselines for tuning hyperparameters in FL., most straightforward of which is to use a regular hyperparameter method but use validation data from single round noisy surrogate for the full validation objective. Specifically, one can use random search (RS) repeatepyyy evaluate random configurations-an a simple generalization called successive halving (SHA), in which we sample set of configurations and partially run all of them for some number of communication rounds before eliminating all but the best 1 fraction, repeating until only one configuration remains. Note both are equivalent to a "bracket" in Hyperband [26) and their adaptation to FL. is detailed in Algorithm 1.
For simplicity the number of clients per round is fixed, but all methods be easily generalized to varying B.

---

As shown in Section 5, SHA performs reasonably well on the benchmarks we consider. However, by using validation data from one round it may make noisy elimination decisions, early-stopping potentially good configurations because of a difficult set of clients on a particular round. Here the problem is one of insufficient utilization of the validation data to estimate model performance. A reasonable approach to use more is to try some type of sttteeestimttion:: using the performance from previous rounds to improve the noisy measurement of the current one. For example, instead of using only the most recent round for elimination decisions at all past rounds. To investigate this, we study a power decay weighting, where a round is discounted by some constant factor for each time step it is in the past. We consider factors 0.0 (taking the most recent performance only, as before), 0.5, and 1.0 (taking the average). However, in Figure 2 we show that incorporating more validation data this way than is used by Algorithm 1 by default does not significantly affect results.
can use a weighted sum of the performances
Thus we may need a better algorithm to use more of the validation signal, most of which is discarded by using the most recent round's performance. We next propose FedEx, a new method that does so by using validation on each round to update a client hyperparameters distribution used to sample configurations to send to devices. Thus it alleviates issue (I) above by updating at each step, not waiting for an elimination round as in RS or SHA. By simultaneously training the model and tuning (client) hyperparameters. it also moves towards a fully single-shot procedure in which we only train once (we must still run multiple times due to server hyperparameters), which would solve issue (2). Finally, FedEx addresses issue (3) by using local training to both update the model and to estimate personalized validation loss, thus not spending extra computation this more expensive objective.
3 Weight-Sharing for Federated Learning
We now present FedEx, a way to tune local FL hyperparameters. This section contains the general algorithm and its connection to weight-sharing; we instantiate it several FL methods in Section 5.
Weight-Sharing for Architecture Search which for set C of network configurations is often posed as the bilevel optimization
We first review the weight-sharing approach in NAS,
min oEC
Lvatid (w, c) s.t. w E arg min Lurai (u, c)
(3)
uERd
where Turain; Tevali evaluate single configuration with the given weights. If, as in NAS, all hyperpa- rameters are architectural, then they are effectively themselves trainable model parameters [27], so we could instead consider solving the following "single-level" empirical risk minimization (ERM):
min oEC, WER4
c(w.c)
min Lurin Lmminw,e c) + Lvatia (w, c)
(4)
wEC,
Solving this instead of the bilevel problem (3) has been proposed in several recent papers [24, 27J.
Early approaches to solving either formulation of NAS were costly due to the need for full or partial training of many architectures in a very large search space. The weight-sharing paradigm [40] reduces the problem to that of training a single architecture, a "supernet" containing all architectures in the search space C. A straightforward way of constructing supernet is via a "stochastic relaxation" where the loss is an expectation w.r.t. sampling e from some distribution over C [8]. Then the shared weights can be updated using SGD by first sampling an architecture c and using an unbiased estimate of V L(w, c) to update w. The distribution over C may itself be adapted or stay fixed. We focus on the former case, adapting some 0-parameterized distribution De; this yields the stochastic relaxation objective
min wER
BoND,L(W,,
(5)
Since architectural hyperparameters are often discrete decisions, e.g. choice of which of a fixed number of operations to use, a natural choice of DD is as a product of categorical distributions over simplices. In this case, any discretization of an optimum 0 of the relaxed objective (5) whose support is in the support of will be an optimum of the original objective (4). A natural update scheme here is exponentiated gradient [22], where each successive is proportional to O Vx 7 is a step-size, and V an unbiased estimate of VgE..,, L(w, c) that can be computed using the re- re-aaammetrrizttoon trick [42]. By alternating this exponentiated update with the standard SGD update to w discussed earlier we obtain a simple block-stochasttic minimization scheme that is guaranteed to converge, under certain conditions, the ERM objective, and also performs well in practice [27].
5

---

The FedEx Method To obtain FedEx from weight-sharing we restrict to the case of tuning only the hyperparameters c of local training Lo 3 Our goal then is just to find the best initialization w R" and local hyperparameters c E C, i.e. we replace the personalized objective (2) by
min wEC,
Σ
(Lo,,, w))
(6)
Note Alg, outputs an element of IRd, so this new objective is upper-bounded by the original (2), i.e. any solution will be least as good for the original objective. Note also that for fixed e this is equivalent to the classic train-validation split objective for meta-learning with Loc, as the base-learner. More importantly for us, it is also in the form of the r.h.s. of the weight-sharing objective (4), i.e. it is a single-level function of w and
We thus apply NAS-like stochastic relaxation:
min BE W E
LV, w))
In NAS we would now set the distribution to be product of categorical distributions over different architectures, thus making an element of a product of simplices and making the optimum of the original objective (6) equivalent to the optimum of the relaxed objective (7) as extreme point of the simplex. Unlike in NAS, FL hyperparameters such as the learning rate are not extreme points of a simplex and so it is less clear what parameterized distribution D3 to use. Nevertheless, we find that crudely imposing a categorical distribution over & > random samples from some distribution (e.g. uniform) over C and updating A using exponentiated gradient over the resulting k-simplex works well. We alternate this with updating w E IR, which in a NAS algorithm involves an SGD update using an unbiased estimate of the gradient at the current W and A.
We call this alternating method for solving (7) FedEx and describe it for a general Alg. consisting of sub-routines Agg, and Loc, in Algorithm 2: recall from Section 2 that many FL methods can be decomposed this way, so our approach is widely applicable. FedEx has a minimal overhead, consisting only of the last four lines of the outer loop updating 0. Thus, as with weight-sharing, FedEx can be viewed as reducing the complexity of tuning local hyperparameters to that of training a single model. Each update to requires a step-size T/r and an approximation V of the gradient w.r.t. 0; for the latter we obtain an estimate V, of each gradient entry via the reparameterization trick, whose variance we reduce by subtracting baseline Ae. How set π7 and X is detailed in the Appendix.
To see how FedEx is approximately optimizing the relaxed objective (7), we can consider the case where Alg,, is Reptile [39], which was designed to optimize some approximation of (6) for fixed e, or equivalently the relaxed objective for an atomic distribution Dy. The theoretical literature on meta-learning [20, 21] shows that Reptile can be interpreted as optimizing surrogate objective minimizing the squared distance between w and the optimum of each task i, with the latter being replaced by the last iterate in practice. It is also shown that the surrogate objective is useful for personalization in the online convex setting.* 4 As opposed to this past work, FedEx makes two gradient updates in the outer loop, on two disjoint sets of variables: the first is the sub-routine Age, of Alg. that aggregates the outputs of local training and is using the gradient of the surrogate objective, since the derivative of the squared distance is the difference between the initialization and the parameter at the last iterate of Loc,: the second is the exponentiated gradient update that is directly using unbiased estimate of the derivative of the second objective w.r.t. the distribution parameters f. Thus, roughly speaking FedEx runs simultaneous stochastic gradient descent on the relaxed objective (7), although for the variables w are using first-order surrogate. In the theoretical portion of this work we employ this interpretation to show the approach works for tuning the step-size of online gradient descent in the online convex optimizations setting.
Wrapping FedEx We can view FedEx as an algorithm of the form tuned by Algorithm that implements federated training of supernet parameter (w, 0). with the local training routine Loc including a step for sampling ~ Dø and the server aggregation routine including an exponentiated update of 9. Thus we can wrap FedEx in Algorithm 1, which we find useful for a variety of reasons:
The wrapper can tune the settings of b for the aggregation step Agg,- which FedEx cannot.
FedEx itself has a few hyperparameters, e.g. how to set the baseline X which can be tuned.
We will use some wrapper algorithm to tune the hyperparameters of Aggs- Formaall they study sequence of upper bounds and not surrogate objective, as their focus is online learning.

---

Algorithm 2: FedEx
Input: configurations c . Ck C, setting b for AgEs- schemes for setting step-size т) and baseline λ₁, total number of steps т 2 1 initialize 01 1 k and shared weights W1 E Rd for comm. round
15.1
......T do do send Wt, to client
for client i = 1,
1poilon110 Epallce-.11
sample Cts ~ Do.
Wis Locc., (Tis: we)
Comparison of the range of perfor- mance values attained using different pertur- bation settings. Although the range is much smaller for c = 0.1 than for c = 1.0 (the lat- ter is the entire space), it still covers large (roughly 10-20%) range of different perfor- mance levels both FEMNIST (left) and CIFAR (right).
Figure 3:
send Wei Ces: (We:) to server
W++1 t- Aggo(w. (Wis
El [allLy, - Vj
V t
Beps Din Mi
0.41 <- Og ④ exp( (-))
ot+1 <- 0/41/1100++1
Output: model w. hyperparameter distribution 0
By running multiple seeds and potentially using early stopping, run FedEx using more aggressive steps-sizes and the wrapper will discard cases where this leads to poor results.
We can directly compare FedEx to a regular hyperparameter optimization scheme run over the original algorithm, e.g. FedAvg, by using the same scheme both wrap FedEx and tune FedAvg.
Using the wrapper allows us determine the configurations C1,.... Cj given to Algorithm 2 using local perturbation scheme (detailed next) while still exploring the entire hyperparameter space.
Local Perturbation It remains to specify how to select the configurations CI..... C E C to pass to Algorithm 2. While the simplest approach is to draw from Unir* (C), we find that this leads to unstable behavior if the configurations are too distinct from each other. To interpolate between sampling e, independently and setting them be identical (which would just be equivalent the baseline algorithm), we use a simple local perturbation method in which Cj is sampled from Uni and ....... Ck sampled uniformly from a local neighborhood of C. For continuous hyperparameters (e.g. step-size, dropout) drawn from an interval (a, bj C R the local neighborhood is (c (b a)e) for some 0, i.e. scaled e- e-ball; for discrete hyperparameters (e.g. batch-size, epochs) drawn from [(b a)el} in our
set (a.....b b} C Z, the local neighborhood is similarly fc [bb (a)aaa)........ experiments we set e 0.1, which works well, but ablation studies varying these values in the appendix showing that a wide range of them leads to improvement. Note that while local perturbation does limit the size of the search space explored by each instance of FedEx, as shown in Figure 3 the difference in performance between different configurations in the same ball is still substantial.
Limitations of FedEx While FedEx is applicable many important FL algorithms, those that cannot be decomposed into local fine-tuning and aggregation should instead be tuned by one of our baselines, e.g. SHA. FedEx is also limited in that it is forced to rely such algorithms wrappers for tuning its own hyperparameters and certain FL hyperparameters such as server learning rate.
Theoretical Analysis for Tuning the Step-Size in an Online Setting
As noted in Section 3, FedEx can be viewed as alternating minimization, with gradient step on surrogate personalization loss and an exponentiated gradient update of the configuration distribution We make this formal and prove guarantees for simple variant of FedEx in the setting where the server has one client per round, to which the server sends an initialization to solve an online convex optimization (OCO) problem using online gradient descent (OGD) on a sequence of m adversarial convex losses (i.e. one SGD epoch in the stochastic case). Note we use "client" and "task" interchangeably, as the goal is meta-learning (personalization) result. The performance measure here is task-averaged regret, which takes the average over 7 clients of the regret they incur on its loss:
7

---

R2
lea (wa.)) - (ex(w()
Here &,j is the ith loss of client I, We. the parameter chosen on its ith round from a compact parameter space W, and w E arg wew >i1&,, (.,(w) the task optimum. In this setting, the Average Segget-Upper-Beee
Analysis (ARUBA) framework [20] can used to show guarantees for Reptile (i.e. FedEx with server step-size) variant in which at each round the initialization is updated as Wi+1 + (1 - a;),; + a.w? for server step-size a = l/t.. Observe that the only difference between this update and FedEx's 's is that the task-t optimum w is used rather than the last iterate of OGD on that task. Specifically they bound task-averaged regret by
R, S ( VF +
v) vm for V²= min = WEW 7 [=1
Σ 1|w wil2
Here V-the average deviation of the optimal actions w; across tasks is a measure of similarry, V is small when the tasks (clients) have similar data and thus can be solved by similar parameters in W but large when their data is different and so the optimum parameters to use are very different. Thus the bound in (9) shows that the server (meta-learning) sees more and more clients (tasks), their regret on each decays with rate 1/ / to depend only on the task-similarity, which is hopefully small if the client data is similar enough that transfer learning makes sense, in particular if V & diam(WW. Since single-task regret has lower bound 52 (2m))m), achieving asymptotic regret V //m thus demonstrates successful learning of useful initialization in W that can be used for personalization. Note that such bounds can also be converted to obtain guarantees in the statistical meta-learning setting as well [20].
A drawback of past results using the ARUBA framework is that they either assume the task task-similarity V is known in order to set the client step-size [25] or they employ an OCO method to learn the local step-size that cannot be applied to other potential algorithmic hyperparameters [20]. In contrast, prove results for using bandit exponentiated gradient to tune the client step-size, which is precisely the FedEx update. In particular, Theorem 4.1 shows that by using discretization of potential client step-sizes as the configurations in Algorithms 2 we can obtain the following task-averaged regret:
Theorem 4.1. Let W C. Rdd be convex and compact with diameter D = diam(W) and let les be a sequence of MT b-bounded convex losses-m for each of tasks-with Lipschitz constant S G. We assume that the adversary is oblivious within-task. Suppose
Algorithm 2 with B 1, configurations Cj- = Givm eacch j = 1....,k determining the local step-size of single-epoch SGD
(OGD), Wti wi, regret Exn ly (a(W.)))-e..
used in place of Lvv.(Wis), (W:z), and A 1 [7] Vt [T], k3 = DG IT, and Agg,(w, w() = (1 - a:) + a,w; for b 2m
Then if 17t = mb V
log ke
V
at = ///tttt [T] we have (taking expectations over sampling from Do.)
ER, < =0(mm/T+V) +V vm
(10)
The proof of this result, given in the supplement, follows the ARUBA framework of using meta OCO algorithm to optimize the vutialization-deeeddee upper bound on the regret of OGD; in addition we bound errors to the bandit setting and discretization of the step-sizes. Theorem 4.1 demonstrates that FedEx is sensible algorithm for tuning the step-size in the meta-learning setting where each task is an OCO problem, with the average regret across tasks (clients) converging to depend only on the task-similarity V. which we hope is small in the setting where personalization is useful. As we can see by comparing to the bound in (9), besides holding for a more generally-applicabb) algorithm our bound also improves the dependence on т. albeit at the cost of an additional m factor. Note that that the sublinear term be replaced by 1 1/v7 in the full-information setting, i.e. where required the client to try SGD with each configuration Cj at each round to obtain regret for all of them.
8

---

Table 1: Final test error obtained when tuning using standard hyperparameter tuning algorithm (SHA or RS) alone, or when using it for server (aggregation) hyperparameters while FedEx tunes client (on-device training) hyperparameters. The target model is the one used to compute on-device validation error by the wrapper method, as well as the one used to compute test error after tuning. Note that this table reports the final error results corresponding the online evaluations reported in Figure 4, which measure performance as more of the computational budget is expended.
Wrapper method
Target
Tuning
Shakespeure
FEMNIST
CIFAR-10 i.i.d.
model
method
i.i.d.
non-i.i.d
i..d.
non-i.id.
global
RS (server & client)
60.32 + 10.03
64.36
14.19
22.81 = 4.56
22.98
3.41
30.46 9.44
Random Search (RS)
FedEx (client)
63.94 + 9.13
57.70 + 17.57
20.96 = 4.77
22.30
+ 3.66
31.83 + 14.74
person-
RS (server & client)
61.10 = 9.32
61.71
= 9.08
17.45
= 2.82
17.77
= 2.63
31.89
+ 10.06
alized
FedEx (client)
54.90 + 9.97
56.48 +: 13.60
16.31 = 3.77
15.93
3.06
39.13
4: 15.13
SHA (server & client)
47.38 = 3.40
46.79 3.51
18.64 = 1.68
20.30
= 1.66
21.62 + 2.51
globul
Successive
FedEx (client)
44.52 ::
45.24
19:22 = 2.05
19.43
1.45
20.82 +: 1.37
Halving
person- alized
SHA (server & client) 46.77 3.61
48.04 + 3.72
14.79 + 1.55
14.78
= 1.31
24.81
= 6.13
(SHA)
FedEx (client)
46.08 = 2.57
45.89 + 3.76
14.97 = 1.31
14.76
+ 1.70
21.77 + 2.83
5 Empirical Results
In our experiments, we instantiate FedEx on the problem of tuning FedAvg, FedProx, and Reptile; the first is the most popular algorithm for federated training, the second is an extension designed for heterogeneous devices, and the last is a compatible meta-learning method used for learning initializations for personalization. At communication round these algorithms use the aggregation
Agg (w, (w:) (1 at
O7
Σ
TT/W;
(11)
T
2i=1
for some learning rate a 0 that can vary through time; in the case of FedAvg we have a 1 The local training sub-routine Loce is SGD with hyperparameters c over some objective defined by the training data Ta. which can also depend on For example, to include FedProx we include in an additional local hyperparameter for the proximal term compared with that of FedAvg.
We tune several hyperparameters of both aggregation and local training; for the former we tune the server learning rate schedule and momentum, found to be helpful for personalization [17]; for the latter we tune the learning rate, momentum, weight-decay, the number of local epochs, the batch-size, dropout, and proximal regularization. Please see the supplementary material for the exact hyperparameter space considered. While we mainly evaluate FedEx in cross-device federated settings, which is generally more difficult than cross-silo in terms of hyperparameter optimization, FedEx can be naturally applied to cross-silo settings, where the challenges of heterogeneity, privacy requirements, and personalization remain.
Because our baseline is running Algorithm 1, standard hyperparameter tuning algorithm, to tune all hyperparameters, and because we need to also wrap FedEx in such an algorithm for the reasons described in Section 3, our empirical results will test the following question: does FedEx, wrapped by random search (RS) or a successive halving algorithm (SHA), do better than RS or SHA run with the same settings directly? Here "better" will mean both the final test accuracy obtained and the online evaluation setting, which tests how well hyperparameter optimization is doing at intermediate phases. Furthermore, we also investigate whether FedEx can improve upon the wrapper alone even when targeting a good global and not personalized model, i.c. when climination decisions are made using the average global validation loss. We run Algorithm 1 on the personalized objective and use RS and SHA with elimination rate 7) = 3, the latter following Hyperband [26]. To both wrappers we allocate the same (problem-dew) dependent) tuning budget. To obtain the elimination rounds in Algorithm I for SHA, we set the number of eliminations to R = 3, fix a total communication round budget, and fix a maximum number of rounds to be allocated any configuration a; detailed in the Appendix, this allows us to determine Ti,..., R so as to use up as much of the budget as possible.
We evaluate the performance of FedEx on three datasets (Shakespeare, FEMNIST, and CIFAR-10) on both vision and language tasks. We consider the following two different partitions of data:
1. Each device holds i.i.d. data. While overall data across the entire network can be non-i.i.d., we randomly shuffle local data within each device before splitting into train, validation, and test sets.

---

Shakespeare fily
evaluation, filly
34c
SHW
FodEx
Fa
Fedx
200
480
27
100
106
10
378
2013
040
Shakesspare online non- ..d.......
FENNIST onine evaluation. fully non-ii.d
CIFAR orline evaluation, L. dient data
SHA
SHA
02
1000 20 750
1500
1150
2710
2000
150 2003 2003
Figure 4: Online evaluation of FedEx on the Shakespeare next-character prediction dataset (left), the FEMNIST image classification dataset (middle), and the CIFAR-10 10 image classification dataset (right) in the fully non-i.i.d. setting (except CIFAR-10). We report global model performance on the top and personalized performance on the bottom. All evaluations are run for three trials.
2. Each device holds non-i..d. data. In Shakespeare, each device is actor and the local data is split according to the temporal position in the play; in FEMNIST, each device is the digit writer and the local data is split randomly; in CIFAR-10,
do not consider non-i.id. setting.
For Shakespeare and FEMNIST we 80% of the data for training and 10% each for validation and testing. In CIFAR-10 10 we hold out 10K examples from the usual training/testing split for validation. The backbone models used for Shakespeare and CIFAR-10 10 follow from the FedAvg evaluation [36] and use 4K communications rounds (at most 800 round for each arm), while that of FEMNIST follows from LEAF [5] and uses 2K communication rounds (at most 200 for each arm).
Table I presents our main results, displaying the final test error of the target model after tuning using either wrapper algorithm alone its combination with FedEx. The evaluation shows that using FedEx on the client parameters is either equally or more effective in most cases; in particular, a FedEx-modified method performs best everywhes except i.i.d. FEMNIST, where it is very close. Furthermore, FedEx frequently improves upon the wrapper algorithm by 2 or more percentage points.
We further present online evaluation results in Figure 4, where we display the test error of FedEx wrapped with SHA compared to SHA alone as a function of communication rounds. Here we see that for most of training FedEx is either around the same or better then the alternative, except at the beginning; the former is to be expected since the randomness of FedEx leads to less certain updates at initialization. Nevertheless FedEx is usually better than the SHA baseline by the halfway point.
Conclusion
In this paper we study the problem of hyperparameter optimization in FI., starting with identifying the key challenges and proposing reasonable baselines that adapts standard approaches to the federated setting. We further make a novel connection to the weight-sharing paradigm from NAS- to our knowledge the first instance of this being used for regular (non-architectural) hyperparameters- and use it to introduce FedEx. This simple, low-overhead algorithm for accelerating the tuning of hyperparameters in federated learning can be theoretically shown to successfully tune the step-size for multi-task OCO problems and effectively tunes FedAvg, FedProx, and Reptile on standard benchmarks. The scope of application of FedEx is very broad, including tuning actual architectural hyperparameters rather than just settings of local SGD, i.c. doing federated NAS, and tuning initialization-hatt meta-learning algorithms such Reptile and MAML. Lastly, any work on FL comes with privacy and fairness risks due its frequent use of sensitive data; thus any application of work must consider tools being developed by the community for mitigating such issues [32, 37].
10

---

Acknowledgments
This material is based on work supported by the National Science Foundation under grants CCF- 1535967, CCF-19111 IIS-2046613 and IIS 11121;; the Defense Advanced Research Projects Agency under cooperative agreements HR001 12020003 and FA875017C0141; an AWS Machine Learning Research Award; an Amazon Research Award; a Bloomberg Research Grant; a Microsoft Research Faculty Fellowship; an Amazon Web Services Award; Facebook Faculty Research Award; funding from Booz Allen Hamilton Inc.; a Block Center Grant; and a Two Sigma Fellowship Award. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of any of these funding agencies.
191021,,,,,, IIS-1618714, DSS-190443, SES- 191419, NSS-170121, LIS-1838017
References
[1] Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N. What- mough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In Proceedings of the 9th International Conference on Learning Representations, 2021.
[2] Maruan Al-Shedivat, Jennifer Gillenwater, Eric Xing, and Afshin Rostamizadeh. Federated learning via posterior averaging: A new perspective and practical algorithms. In Proceedings of the 9th International Conference on Learning Representations, 2021.
[3] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13:281-305. 2012.
[4] Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In Proceedings of the 7th International Conference Learning Representations, 2019.
[5] Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: benchmark for federated settings. arXiv, 2018.
[6] Fei Chen, Zhenhua Dong, Zhenguo Li, and Xiuqiang He. Federated meta-learning for recom- mendation. arXiv, 2018.
[7] Zhongxiang Dai, Kian Hsiang Low, and Patrick Jaillet. Federated bayesian optimization via thompson sampling. In Advances Neural Information Processing Systems, 2020.
[8] Xuanyi Dong and Yi Yang. Searching for robust neural architecture four GPU hours. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
[9] Hubert Eichner, Tomer Koren, H. Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi- eyclic stochastic gradient descent. In Proceedings of the 36th International Conference Machine Learning, 2019.
[10] Thomas Elsken, Benedikt Staffler, Jan Hendrik Metzen, and Frank Hutter. Meta-learning of neural architectures for few-shot learning. arXiv, 2019.
[11) Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta-learning approach. In Advances in Neural Information Processing Systems, 2020.
[12] Anubhav Garg, Amit Kumar Saha, and Debo Dutta. Direct federated neural architecture search. arXiv, 2020.
[13] Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. arXiv, 2020.
[14] Rishi Gupta and Tim Roughgarden. A PAC approach to application-specifie algorithm selection. SIAM Journal on Computing, 46(3);992-1017, 2017.
[15] Chaoyang He, Murali Annavaram, and Salman Avestimehr. Towards non-i.i.d. and invisible data with FedNAS: Federated deep learning via neural architecture search. arXiv, 2020.

---

[16] Frank Hutter, Holger H. Hoos, and Kevin Leyton- Broow.. Sequential model- optimization for general algorithm configuration. In Proceedings of the International Conference on Learning and Intelligent Optimization, 2011.
[17] Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning. arXiv, 2019.
[18] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveirs Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Koneõný, Alcksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tancrède Lepoint, Yang Liu, Prateek Mittal, Mchryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. arXiv, 2019.
[19] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning. 2020.
[20] Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient- based meta- learning methods. In Advances in Neural Information Processing Systems, 2019.
[21] Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning. In Proceedings of the 36th International Conference on Machine Learning. 2019.
[22] Jyrki Kivinen and Manfred K. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132:1-63, 1997.
[23] Antti Koskela and Antti Honkela. Learning rate adaptation for federated and differentially private learning. arXiv, 2018
[24] Guilin Li, Xing Zhang, Zitong Wang, Zhenguo Li, and Tong Zhang. StacNAS: Towards stable and consistent differentiable neural architecture search. arXiv, 2019.
[25] Jeffrey Li, Mikhail Khodak, Sebastian Caldas, and Ameet Talwalkar. Differentially private meta-learning. In Proceedings the 8th International Conference on Learning Representations, 2020.
[26] Liam Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hy- perband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(18)):1-52, 2018
[27] Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Geometry-avee aware gradient algorithms for neural architecture search. In Proceedings of the 9th International Conference on Learning Representations, 2021.
[28) Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2019.
[29] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. arXiv, 2020.
[30] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Processing Magazine, 37, 2020.
[31] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Proceedings of the Conference on Machine Learning and Systems, 2020.
12

---

[32] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in feder- ated learning. In Proceedings of the 6th International Conference on Learning Representations. 2020.
[33] Dongze Lian, Yin Zheng. Yintao Xu, Yanxiong Lu, Leyu Lin, Peilin Zhao, Junzhou Huang, and Shenghua Gao. Towards fast adaptation of neural architectures with meta-learning. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[34] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In Proceedings of the 7th International Conference Learning Reprexentations, 2019.
[35] Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning. arXiv, 2020.
[36] H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artifical Intelligence and Statisties, 2017.
[37] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In Proceedings of the 6th International Conference on Learning Representations, 2018.
[38] Hesham Mostafa. Robust federated learning through representation matching and adaptive ppper-parameters... arXiv, 2019.
[39] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv, 2018.
[40] Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In Proceedings of the 35th International Conference on Machine Learning, 2018.
[41] Jashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný. Sanjiv Kumar, and H. Brendan McMahan. Adaptive federated optimization. In Proceedings of the 9th International Conference on Learning Representations, 2021.
[42] Reuven Y. Rubinstein and Alexander Shapiro. Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method. John Wiley & Sons, Inc., 1993.
[43] Virginia Smith, Chao- Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. In Advances in Neural Information Processing Systems, 2017.
[44] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems, 2012.
[45] Xiang Wang, Shuai Yuan, Chenwei Wu, and Rong Ge. Guarantees for tuning the step size using a learning-to-ler -o-lenr-----ernn---- approach. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[46] Mengwei Xu, Yuxin Zhao, Kaigui Bian, Gang Huang, Qiaozhu Mei, and Xuanzhe Liu. Federated neural architecture search. arXiv, 2020.
[47] Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging federated learning by local adaptation. arXiv, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See end of Section 3.
13

---

(c) Did you discuss any potential negative societal impacts of your work? [Yes] See end of Section 6.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section and the Appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] See link the Appendix.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the Appendix.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] See Table and Figure 4.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No] The main unit of cost in our setting is communication round, which we do report in e.g. Figure 4.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes] see link in the Appendix.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "fef8H8_IJo2", "reviewer": "Reviewer_onB2", "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.\n\nThis paper provides a theoretical statement in a simplified setting justifying the approach taken--showing that for some settings this approach can improve average regret.\n\nThis paper also provides a reasonably thorough empirical evaluation of this approach, along with standalone implementations in the supplementary material.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Some fine-grained notes:\n\n1. 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.\n\n2. 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).\n\n3. 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.\n\n4. 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.\n\n5. 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.\n\n6. (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.\n\n7. Nit typo (L269): s/shws/shows\n\n8. 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).\n\nThis 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.\n\nIf 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.\n\nThis 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).\n\nIf 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. \n\nEither 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "_YK3k0TkcF-", "reviewer": "Reviewer_2myh", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nThe 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.\n\nQuality:\nThe 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.\n\nClarity: The paper is clearly written and well organized. Details of proof and experiments are given in the supplement.\n\nSignificance: 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.\n\n=== Post Rebuttal ===\n\nThe 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have a few questions about the paper.\n\n1. How many GPU hours does it take to reproduce the experiment?\n2. The argument that \"personalized losses require several forward-backward passes\"(line 130 to line 135) is a little bit confusing. \n3. What does this mean, and how does FedEx tackle the problem? Any example that personalized FL uses several forward-backward passes?\n4. In algorithm 2, what's the meaning of \"1 ctj=cj\" (the Fourth line from last)\n5. What’s the meaning of the shadow in figure 4. Std for multiple runs or std for clients?\n6. Is Dθt (algorithm 2) different across different clients?\n7. How to obtain the personalized model by FedEx?\n8. The FedEx is tested with FedAvg, FedProx, and Reptile. But there is only one set of results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "JdpeaP6HZYI", "reviewer": "Reviewer_c2J3", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n**Quality**: the paper is technically sound. It gives a clean mathematical formulation with thorough explanation of motivations.\n\n**Clarity**: the paper is well written and easy to follow.\n\nMinor presentation issues: \n- Algorithm 1, on page 4, is not introduced in the text of section 2, while being referred to a few times starting page 6.\n- Equation 4, RHS misses min variable $w$ for $w \\in \\mathbb{R}^d$.\n- Title and axis labels in all plots can be bigger for better readability.\n\n**Strengths**\n\n1. 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.\n\n1. 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.\n\n1. 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.\n\n**Weaknesses**\n\n1. 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)?\n\n1. 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)