Federated Hyperparameter Tuning: Challenges, Baselines, and Connections to Weight-Sharing
Year: 2021

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.

heading: 1 Introduction
text: Federated learning (FL) is a popular distributed computational setting where training is performed locally or privately [30, 36] and where hyperparameter tuning has been identified as a 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. In this work, we first formalize the problem of hyperparameter optimization in FL, introducing the following three key challenges:
1. Federated validation data: In federated networks, as the validation data is split across devices, the entire dataset is 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 a few runs of local training and validation. Thus, because the standard measure of complexity in FL is the number of communication rounds, computing validation metrics exactly dramatically increases the cost.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
2. Extreme resource 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 hyperparameter optimization methods to standard personalized FL approaches (such as finetuning) can be costly because evaluation may require performing many additional training steps locally.
With these challenges1 in mind, we propose reasonable baselines for federated hyperparameter tuning by showing how to adapt standard non-federated algorithms. We further study the challenge of noisy validation signal due to federation, and show that simple state-estimation-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, we observe that weight-sharing 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 weightsharing only handles architectural hyperparameters such as the choice of layer or activation, and not critical settings such as those of local stochastic gradient descent (SGD), we develop a formulation that allows us to tune most of these as well via the relationship between local-training and fine-tuningbased personalization. This make FedEx a general hyperparameter tuning algorithm applicable to many local training-based FL methods, e.g. FedAvg [36], FedProx [31], and SCAFFOLD [19].
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-learning [20], we show that a variant of FedEx correctly tunes the on-device step-size to minimize client-averaged 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 baselines already obtain performance similar to past hand-tuning, 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 formulation and challenges of hyperparameter 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) in less general settings (studying small-scale problems or assuming server-side validation data). In contrast our methods are able to tune a 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 is 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 formulation and guarantees use this relationship, the method itself is general-purpose
1A further challenge we do not address is that of the time-dependency of federated evaluation, c.f. [9].
and applicable to federated training of a 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 weightsharing to regular hyperparameter search. Furthermore, meta-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-principle our algorithms can also be used for federated NAS.
Theoretically, our work makes use of the average regret-upper-bound analysis (ARUBA) framework [20] to derive guarantees for learning the initialization, i.e. the global model, while simultaneously tuning the step-size of the local algorithm. The step-size of gradient-based algorithms has also been tuned on its own in the settings of data-driven algorithm design [14] and of statistical learning-to-learn [45].

heading: 2 Federated Hyperparameter Optimization
text: In this section we formalize the problem of hyperparameter optimization for FL and discuss the connection of its personalized variant to meta-learning. We also review FedAvg [36], a 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 heterogeneous clients i = 1, . . . , n, each with training, validation, and testing sets Ti, Vi, and Ei, respectively. We use LS(w) to denote the average loss over a dataset S of some w-parameterized ML model, for w ∈ Rd some real vector. For hyperparameter optimization, we assume a class of algorithms Alga hyperparameterized by a ∈ A that use federated access to training sets Ti to output some element of Rd. Here by “federated access" we mean that each iteration corresponds to a communication round at which Alga has access to a batch of B clients 2 that can do local training and validation.
Specifically, we assume Alga can be described by two subroutines with hyperparameters encoded by b ∈ B and c ∈ C, so that a = (b, c) and A = B × C. Here c encodes settings of a local training algorithm Locc that take a training set S and initialization w ∈ Rd as input and outputs a model Locc(S,w) ∈ Rd, while b sets those of an aggregation Aggb that takes the initialization w and outputs of Locc as input and returns a model parameter. For example, in standard FedAvg, Locc is T steps of gradient descent with step-size η and Aggb takes a weighted average of the outputs of Locc across clients; here c = (η, 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∈A n∑ i=1 |Vi|LVi(Alga({Tj} n j=1)) (1)
In many cases we are also interested in obtaining a device-specific local model, where we take a 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 Locc used by Alga. 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,c)∈A n∑ i=1 |Vi|LVi(Locc(Ti, Alga({Tj} n j=1)) (2)
Our approach will focus on the setting where the hyperparameters c of local training make up a significant portion of all hyperparameters a = (b, c); by considering the personalization objective we will be able to treat such hyperparameters as architectural and thus apply weight-sharing.
Algorithm 1: Successive halving algorithm (SHA) applied to personalized FL. For the non-personalized objective (1), replace LVti(wi) by LVti(wa). For random search (RS) with N samples, set η = N and R = 1. Input: distribution D over hyperparameters A,
elimination rate η ∈ N, elimination rounds τ0 = 0, τ1, . . . , τR
sample set of ηR hyperparameters H ∼ D[ηR] initialize a model wa ∈ Rd for each a ∈ H for elimination round r ∈ [R] do
for setting a = (b, c) ∈ H do for comm. round t = τr−1 + 1, . . . , τr do
for client i = 1, . . . , B do send wa, c to client wi ← Locc(Tti,wa) send wi, LVti(wi) to server wa ← Aggb(wa, {wi}Bi=1) sa ← ∑B i=1 |Vti|LVti(wi)/ ∑B i=1 |Vti|
H ← {a ∈ H : sa ≤ 1η -quantile({sa : a ∈ H})} Output: remaining a ∈ 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 overA, run Alga to completion, and evaluate 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 Alga 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 a 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-practice 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 a limited number of accesses to the data of any individual user.
3. Evaluating personalization: While personalization is important in FL due to client heterogeneity, checking the performance of the current model on the personalization objective (2) is computationally 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-backward passes, making it many times more expensive if this loss is needed to make a tuning decision such as eliminating a 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 a single round as a noisy surrogate for the full validation objective. Specifically, one can use random search (RS)—repeatedly evaluate random configurations—and a simple generalization called successive halving (SHA), in which we sample a 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.
2For simplicity the number of clients per round is fixed, but all methods can 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 state-estimation: 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 we can use a weighted sum of the performances 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.
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 (1) 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 on this more expensive objective.

heading: 3 Weight-Sharing for Federated Learning
text: 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 on several FL methods in Section 5.
Weight-Sharing for Architecture Search We first review the weight-sharing approach in NAS, which for a set C of network configurations is often posed as the bilevel optimization
min c∈C Lvalid(w, c) s.t. w ∈ arg min u∈Rd Ltrain(u, c) (3)
where Ltrain, Lvalid evaluate a single configuration with the given weights. If, as in NAS, all hyperparameters 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 c∈C,w∈Rd L(w, c) = min c∈C,w∈Rd Ltrain(w, c) + Lvalid(w, c) (4)
Solving this instead of the bilevel problem (3) has been proposed in several recent papers [24, 27].
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 a supernet is via a “stochastic relaxation" where the loss is an expectation w.r.t. sampling c 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 ∇wL(w, c) to update w. The distribution over C may itself be adapted or stay fixed. We focus on the former case, adapting some θ-parameterized distribution Dθ; this yields the stochastic relaxation objective
min θ∈Θ,w∈Rd Ec∼DθL(w, c) (5)
Since architectural hyperparameters are often discrete decisions, e.g. a choice of which of a fixed number of operations to use, a natural choice of Dθ is as a product of categorical distributions over simplices. In this case, any discretization of an optimum θ 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 θ exp(−η∇̃), η is a step-size, and ∇̃ an unbiased estimate of ∇θEc∼DθL(w, c) that can be computed using the re-parameterization trick [42]. By alternating this exponentiated update with the standard SGD update to w discussed earlier we obtain a simple block-stochastic minimization scheme that is guaranteed to converge, under certain conditions, to the ERM objective, and also performs well in practice [27].
The FedEx Method To obtain FedEx from weight-sharing we restrict to the case of tuning only the hyperparameters c of local training Locc.3 Our goal then is just to find the best initialization w ∈ Rd and local hyperparameters c ∈ C, i.e. we replace the personalized objective (2) by
min c∈C,w∈Rd n∑ i=1 |Vi|LVi(Locc(Ti,w)) (6)
Note Alga outputs an element of Rd, so this new objective is upper-bounded by the original (2), i.e. any solution will be at least as good for the original objective. Note also that for fixed c this is equivalent to the classic train-validation split objective for meta-learning with Locc 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 c. We thus apply a NAS-like stochastic relaxation:
min θ∈Θ,w∈Rd n∑ i=1 |Vi|Ec∈DθLVi(Locc(Ti,w)) (7)
In NAS we would now set the distribution to be a 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 an 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 Dθ to use. Nevertheless, we find that crudely imposing a categorical distribution over k > 1 random samples from some distribution (e.g. uniform) over C and updating θ using exponentiated gradient over the resulting k-simplex works well. We alternate this with updating w ∈ Rd, which in a NAS algorithm involves an SGD update using an unbiased estimate of the gradient at the current w and θ.
We call this alternating method for solving (7) FedEx and describe it for a general Alga consisting of sub-routines Aggb and Locc 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 θ. 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 and an approximation ∇̃ of the gradient w.r.t. θ; for the latter we obtain an estimate ∇̃j of each gradient entry via the reparameterization trick, whose variance we reduce by subtracting a baseline λt. How we set ηt and λt is detailed in the Appendix.
To see how FedEx is approximately optimizing the relaxed objective (7), we can consider the case where Alga is Reptile [39], which was designed to optimize some approximation of (6) for fixed c, or equivalently the relaxed objective for an atomic distribution Dθ. The theoretical literature on meta-learning [20, 21] shows that Reptile can be interpreted as optimizing a 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 Aggb of Alga 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 w and the parameter at the last iterate of Locc; the second is the exponentiated gradient update that is directly using an unbiased estimate of the derivative of the second objective w.r.t. the distribution parameters θ. Thus, roughly speaking FedEx runs simultaneous stochastic gradient descent on the relaxed objective (7), although for the variables w we are using a 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 1 that implements federated training of a supernet parameter (w, θ), with the local training routine Loc including a step for sampling c ∼ Dθ and the server aggregation routine including an exponentiated update of θ. 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 Aggb, which FedEx cannot. • FedEx itself has a few hyperparameters, e.g. how to set the baseline λt, which can be tuned. 3We will use some wrapper algorithm to tune the hyperparameters b of Aggb. 4Formally they study a sequence of upper bounds and not a surrogate objective, as their focus is online learning.
Algorithm 2: FedEx Input: configurations c1, . . . , ck ∈ C, setting b for
Aggb, schemes for setting step-size ηt and baseline λt, total number of steps τ ≥ 1
initialize θ1 = 1k/k and shared weights w1 ∈ Rd for comm. round t = 1, . . . , τ do
for client i = 1, . . . , B do send wt, θt to client sample cti ∼ Dθt wti ← Loccti(Tti,wt) send wti, cti, LVti(wti) to server wt+1 ← Aggb(w, {wti}Bi=1) ∇̃j ← ∑B i=1 |Vti|(LVti (wti)−λt)1cti=cj
θt[j] ∑B i=1 |Vti|
∀ j
θt+1 ← θt exp(−ηt∇̃) θt+1 ← θt+1/‖θt+1‖1
Output: model w, hyperparameter distribution θ
Figure 3: Comparison of the range of performance values attained using different perturbation settings. Although the range is much smaller for = 0.1 than for = 1.0 (the latter is the entire space), it still covers a large (roughly 10-20%) range of different performance levels on both FEMNIST (left) and CIFAR (right).
• By running multiple seeds and potentially using early stopping, we can 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 to both wrap FedEx and tune FedAvg.
• Using the wrapper allows us to determine the configurations c1, . . . , ck given to Algorithm 2 using a local perturbation scheme (detailed next) while still exploring the entire hyperparameter space.
Local Perturbation It remains to specify how to select the configurations c1, . . . , ck ∈ C to pass to Algorithm 2. While the simplest approach is to draw from Unifk(C), we find that this leads to unstable behavior if the configurations are too distinct from each other. To interpolate between sampling ci independently and setting them to be identical (which would just be equivalent to the baseline algorithm), we use a simple local perturbation method in which c1 is sampled from Unif(C) and c2, . . . , ck are sampled uniformly from a local neighborhood of C. For continuous hyperparameters (e.g. step-size, dropout) drawn from an interval [a, b] ⊂ R the local neighborhood is [c± (b−a)ε] for some ε ≥ 0, i.e. a scaled ε-ball; for discrete hyperparameters (e.g. batch-size, epochs) drawn from a set {a, . . . , b} ⊂ Z, the local neighborhood is similarly {c− b(b− a)εc, . . . , c+ d(b− a)εe}; in our experiments we set ε = 0.1, which works well, but run 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 to 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 on such algorithms as wrappers for tuning its own hyperparameters and certain FL hyperparameters such as server learning rate.

heading: 4 Theoretical Analysis for Tuning the Step-Size in an Online Setting
text: As noted in Section 3, FedEx can be viewed as alternating minimization, with a gradient step on a surrogate personalization loss and an exponentiated gradient update of the configuration distribution θ. We make this formal and prove guarantees for a 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 a meta-learning (personalization) result. The performance measure here is task-averaged regret, which takes the average over τ clients of the regret they incur on its loss:
R̄τ = 1
τ τ∑ t=1 m∑ i=1 `t,i(wt,i)− `t,i(w∗t ) (8)
Here `t,i is the ith loss of client t, wt,i the parameter chosen on its ith round from a compact parameter space W , and w∗t ∈ arg minw∈W ∑m i=1 `t,i(w) the task optimum. In this setting, the Average Regret-Upper-Bound Analysis (ARUBA) framework [20] can be used to show guarantees for a Reptile (i.e. FedEx with a server step-size) variant in which at each round the initialization is updated as wt+1 ← (1 − αt)wt + αtw∗t for server step-size αt = 1/t. Observe that the only difference between this update and FedEx’s is that the task-t optimum w∗t is used rather than the last iterate of OGD on that task. Specifically they bound task-averaged regret by
R̄τ ≤ Õ (
1 4 √ τ + V
)√ m for V 2 = min
w∈W
1
τ τ∑ t=1 ‖w −w∗t ‖22 (9)
Here V—the average deviation of the optimal actions w∗t across tasks—is a measure of task-similarity: V is small when the tasks (clients) have similar data and thus can be solved by similar parameters inW but large when their data is different and so the optimum parameters to use are very different. Thus the bound in (9) shows that as the server (meta-learning) sees more and more clients (tasks), their regret on each decays with rate 1/ 4 √ τ 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(W). Since single-task regret has lower bound Ω(D √ m), achieving asymptotic regret V √ m thus demonstrates successful learning of a useful initialization inW 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-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, we 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 a discretization of potential client step-sizes as the configurations in Algorithms 2 we can obtain the following task-averaged regret:
Theorem 4.1. LetW ⊂ Rd be convex and compact with diameter D = diam(W) and let `t,i be a sequence of mτ b-bounded convex losses—m for each of τ tasks—with Lipschitz constant ≤ G. We assume that the adversary is oblivious within-task. Suppose we run Algorithm 2 with B = 1, configurations cj = DGj√m for each j = 1, . . . , k determining the local step-size of single-epoch SGD (OGD), wti = w∗t , regret ∑m i=1 `t,i(wt,i)−`t,i(wt) used in place ofLVti(wti), and λt = 0 ∀ t ∈ [τ ].
Then if ηt = 1mb √ log k kτ ∀ t ∈ [τ ], k 3 2 = DGb √ τ 2m , and Aggb(w,w ∗ t ) = (1 − αt)w + αtw∗t for αt = 1/t ∀ t ∈ [τ ] we have (taking expectations over sampling from Dθt )
ER̄τ ≤ Õ ( 3 √ m/τ + V )√ m (10)
The proof of this result, given in the supplement, follows the ARUBA framework of using meta OCO algorithm to optimize the initialization-dependent 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 a 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-applicable algorithm our bound also improves the dependence on τ , albeit at the cost of an additional m 1 3 factor. Note that that the sublinear term can be replaced by 1/ √ τ 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.

heading: 5 Empirical Results
text: 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 t these algorithms use the aggregation
Aggb(w, {wi} B i=1) = (1− αt)w + αt∑B i=1 |Tti| B∑ i=1 |Tti|wi (11)
for some learning rate αt > 0 that can vary through time; in the case of FedAvg we have αt = 1 ∀ t. The local training sub-routine Locc is SGD with hyperparameters c over some objective defined by the training data Tti, which can also depend on c. For example, to include FedProx we include in c 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, a 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.e. when elimination 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 η = 3, the latter following Hyperband [26]. To both wrappers we allocate the same (problem-dependent) tuning budget. To obtain the elimination rounds in Algorithm 1 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 to any configuration a; as detailed in the Appendix, this allows us to determine T1, . . . , TR 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.
2. Each device holds non-i.i.d. data. In Shakespeare, each device is an 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, we do not consider a non-i.i.d. setting.
For Shakespeare and FEMNIST we use 80% of the data for training and 10% each for validation and testing. In CIFAR-10 we hold out 10K examples from the usual training/testing split for validation. The backbone models used for Shakespeare and CIFAR-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 1 presents our main results, displaying the final test error of the target model after tuning using either a wrapper algorithm alone or 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 everywhere 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.

heading: 6 Conclusion
text: In this paper we study the problem of hyperparameter optimization in FL, 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.e. doing federated NAS, and tuning initialization-based meta-learning algorithms such as 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 our work must consider tools being developed by the community for mitigating such issues [32, 37].

heading: Acknowledgments
text: This material is based on work supported by the National Science Foundation under grants CCF1535967, CCF-1910321, IIS-1618714, IIS-1901403, SES-1919453, IIS-1705121, IIS-1838017, IIS-2046613 and IIS-2112471; the Defense Advanced Research Projects Agency under cooperative agreements HR00112020003 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; a 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.

Review summaries:
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. 

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.

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.