Single-shot General Hyper-parameter Optimization for Federated Learning
Authors: Yi Zhou
Parikshit Ram
Theodoros Salonidis
Nathalie Baracaldo
Horst Samulowitz
Heiko Ludwig
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Federated Learning
Hyperparameter Optimization
Optimality Gap Analysis

Abstract: We address the problem of hyper-parameter optimization (HPO) for federated learning (FL-HPO). We introduce Federated Loss SuRface Aggregation (FLoRA), a general FL-HPO solution framework that can address use cases of tabular data and any Machine Learning (ML) model including gradient boosting training algorithms, SVMs, neural networks, among others and thereby further expands the scope of FL-HPO. FLoRA enables single-shot FL-HPO: identifying a single set of good hyper-parameters that are subsequently used in a single FL training. Thus, it enables FL-HPO solutions with minimal additional communication overhead compared to FL training without HPO. Utilizing standard smoothness assumptions, we theoretically characterize the optimality gap of FLoRA for any convex and non-convex loss functions, which explicitly accounts for the heterogeneous nature of the parties' local data distributions, a dominant characteristic of FL systems. Our empirical evaluation of FLoRA for multiple FL algorithms on seven OpenML datasets demonstrates significant model accuracy improvements over the baselines, and robustness to increasing number of parties involved in FL-HPO training.

Published as a conference paper at ICLR 2023
SINTLE-SHOT GENERAL HYPER-PARAMETER OPTIMIZATION FOR FEDERATED LEARNING
Y. Zhou, P. Ram, T. Salonidis, N. Baracaldo, H. Samulowitz, H. Ludwig
IBM Research
{yi zhou, parikshit. ram) bm. com,
(tsaloni, baracald, samulowitz, hludwi euus b.m. com
ABSTRACT
We address the problem of hyper-parameter optimization (HPO) for federated learning (FL-HPO). We introduce Federated Loss SuRface Aggregation (FLoRA), general FL-HPO solution framework that can address use cases of tabular data and any Machine Learning (ML) model including gradient boosting training al- gorithms, SVMs. neural networks, among others and thereby further expands the scope of FL-HPO. FLoRA enables single-shot FL-HPO: identifying a single set good hyper-paramettrs that are subsequently used in single FL training. Thus, it enables FL-HPO solutions with minimal additional communication overhead compared FL training without HPO. Utilizing standard smoothness assumptions, we theoretically characterize the optimality gap of FLoRA for any convex and non-convex loss functions, which explicitly accounts for the heterogeneous nature of the parties" local data distributions, a dominant characteristic of FL systems. Our empirical evaluation of FLoRA for multiple FL. algorithms on seven OpenML. datasets demonstrates significant model accuracy improvements over the baselines, and robustness to increasing number of parties involved in FL-HPO training.
INTRODUCTION
Traditional machine learning (ML) approaches require training data to be gathered at central location where the learning algorithm runs. In real world scenarios, however, training data is often subject to privacy or regulatory constraints restricting the way data can be shared, used and transmitted. Examples of such regulations include the Huropean General Data Protection Regulation (GDPR), California Consumer Privacy Act (CCPA), Cybersecurity Law of China (CLA) and HIPAA, among others. Federated learning (FL), first proposed in McMahan et al. (2117)), has recently become a popular approach to address privacy concerns by allowing collaborative training of ML models among multiple parties where each party can keep its data private.
FL-HPO problem. Despite the privacy protection FL brings along, there are many open problems in FL domain, of which is hyper-parameter optimization for FL or FL-HPO (Kairouz al. 2019
Khodak et al., 2021). Existing FL. systems require a user (or all participating parties) to pre-set (agree on) multiple parrae-arreeeers (HPs) (i) for the model being trained (such as number of layers for neural networks or tree depth and number of trees in tree ensembles), (ii) for the FL algorithms, and (iii) for aggregation (if such syper-parameter exist). flyper-paramedt optimization (HPO) for FL is important because the choice of HPs can have dramatic impact on model performance much like in traditional centralized ML MMMMahan al. 2017b)
While HPO has been widely studied in the centralized ML setting (Hutter et al. 2019), it comes with unique challenges in the FL. setting. First, existing HPO techniques often make use of the entire dataset, which is not available centrally in FL. Secondly, they need to train many models for large number of HP configurations which is prohibitively expensive in terms of communication and training time in FL settings; training single model already has a high communication overhead (Kairouz et al.) 2019). Thirdly, one important challenge that has not been adequately explored in FL-HPO literature support for tabular data, which are widely used in enterprise settings, such financial services and other traditional industries, preferring traditional models with some explanability (Ludwig et al.) 2020). Although few approaches have been recently proposed for FL-HPO, they focus on handling

---

Published as a conference paper at ICLR 2023
HPO using personalization techniques (Khodak et al. 2021) and neural networks (Khodak et al. 2020). To the best of our knowledge, there is no FL-HPO approach to train non-neural network models, such gradient boosted decision trees (Friedman 2001) (e.g., XGBoost (Chen & Guestrin
2016)) that are particularly common in the enterprise setting, even though there are existing FL.
algorithms for such models (Li et al. 2020 Ong al. 2020). This leads our motivating question:
Can we develop FL-HPO scheme that performs HPO for any MI. model in FL. environment without significantly increasing the already-high communication overhead of FI.2
In this paper, we address the aforementioned challenges of FL-HPO and our motivating question. We focus on the problem where the model HPs are shared by all parties and we seek a set of HPs and train a single model that is used by all parties. Our motivating question leads to four further requirements that make the problem challenging: (C1) To perform FL-HPO with any ML model, we cannor make any assumption that two models with different HPs can perform some "weight- sharing", allowing our solution to be applied beyond fixed architecture neural networks. (C2) To be general across ML models, we do not assume the ability to perform "multi-fidelity" HPO to reduce the communication overhead of FL-HPO (see discussion in Appendix A. (C3) To avoid increasing the FL communication overhead, we seek to perform "single-shor" FL-HPO, where can perform FL-HPO while requiring only single FL model training. (C4) To be applicable to FL with data heterogeneity, we cannot assume that parties have independent and identically distributed (IID) data.
Contributions. Given the above FL-HPO problem setting, we make the following contributions:
We present novel framework Federated Loss SuRface Aggregation (FLoRA) that leverages meta-learning techniques enabling asynchronous local HPOs on each party to perform single-shot
HPO for the global FL-HPO problem.
(2.3) We provide theoretical guarantees for the set of HPs selected by FLoRA covering both III) and Non-IID cases regardless of the convexity of the loss function. To the best of our knowledge, this is the first rigorous theoretical analysis for FL-HPO problem and also the first optimality gap constructed terms of the estimated loss given a target distribution.
(3) We evaluate FLoRA on the FL-HPO of Histogram based Gradient Boosted Decision Trees (HGB), Support Vector Machines (SVM) and Multi-layered Perceptrons (MLP) on seven classification datasets from OpenML. (Vanschoren et al., 2013). highlighting (i) its performance relative to baselines, and (ii) the effect of data heterogeneity.
In Figure [ we present snapshot of our empirical results which highlights the communication overhead re- duction we achieve from FLoRA while producing higher quality models. As baselines, we directly adopt an ex- isting centralized HPO scheme that requires federated training of multiple models and term this a "multi-shot" FL-HPO baseline. The figure also shows "single- shot" baseline that uses curated HPs (described in ( and FLoRA is also single-shot. Figure [ shows that the "multi-shot" approach requires a sigmificantly large number of FL model trainings (39 for MLP and 24 for HGB) and hence more communication to find a HP that matches the performance of the HP found by FLORA, highlighting the efficiency and effectiveness of FLORA. This result demonstrates that FLoRA is a FL- HPO scheme that works with any ML model (HGB, MLP, etc), providing competitive performance without significantly increasing the communication overhead of FL by only requiring a single FL. model training.
10
Singleschot baseline
R.oRA
Relative Ragret
Mulb shot baseline
MLP
39
HGB
24
Federated Model Trainings
Communication overhead savings of FLoRA compared to "multi-shot" FL-HPO for the same level of performance. We con- sidering 2 FL-HPO problems on the Electricity dataset (with HGB and MLP). We use the rel- ative regret (defined in B of cach scheme as the performance metric (lower is better), where regret of 1 denotes performance of the single- shot baseline while regret of implies optimal performance. FLoRA and the single-shot base- line require single federated model training.
Figure 1:
1.1 RELATED WORK
Performance optimization of FL systems. One of the main challenges in FL is achieving high accuracy with low communication overhead. FedAvg (McMahan et al. 2017a) is a predominant FL algorithm and several optimization schemes build on it. Initially, communication optimizations
2

---

Published as a conference paper at ICLR 2023
included performing multiple stochastic gradient descent (SGD) local iterations at the clients and ran- domly selecting a small subset of the clients to compute and send updates to the server. Subsequently, compression techniques were used to minimize the size of model updates to the server. The accuracy and communication overhead of these techniques are sensitive to their HPs (McMahan et al. 2017a).
FL-HPO of neural networks. Recent optimization approaches adapt HPss such as the local learning rate at each client (Koskela & Honkela 2019 Mostafa 2019; Reddi et al.) (020). the number of local
SGD epochs (Wang et al. 2019). Dai et al. (2020) 2021) address Federated Bayesian Optimization. Although using HPO with multiple HPs, the problem setup is quite different than FL: they focus on a single party using information from other parties to accelerate its own Bayesian Optimization, instead of building a model for all parties. Federated Neural Architecture Search (FNAS) approaches search for architectural HPs of CNN models by running locally NAS algorithms and then aggregating the NAS architecture weights and model weights using FedAvg (He et al. 2020 Garg et al., 2020 Xu jt al., 2020). These approaches have shown empirical gains but lack theoretical analysis. Inspired from the NAS technique of weight-sharing, Khodak al. (2020 2021) proposed FedEx, FL-HPO framework to accelerate a centralized HPO procedure, i.c., successive halving algorithm (SHA), for many SGD-based FL algorithms. FedEx focuses on building personalized models for parties by tuning local HPss of the parties. They provide theoretical guarantee only for a special case of tuning a single HP, the local learning rate, in an online convex optimization setting. To optimize global HPs, FedEx requires multiple rounds of communication, and hence is not single-shot FL-HPO (Khodak ct al.) 2020 202I. Note that these above techniques are multi-shot, leveraging both the idea of weight-sharing and multi-fidelity HPO for improving the communication efficiency of FL-HPO. The FedHPO-B benchmark (Wang al. 2022) primarily focuses on neural-networks and multi-fidelity FL-HPO and is useful to evaluate the above schemes across various problems.
Need for FL-HPO of tabular data models. As most existing FL-HPO approaches focus on SGD- based algorithms and neural networks, one major limitation they share is that they do not support tree-hased models, such as gradient boosted trees (Friedman 200T), a popular model for enterprise setting. These models provide explanability for predictions which is required for financial and healthcare FL use-cases, As laid out in a policy paper by the OECD, numerous regulations of member countries govern the use of analytics and data (OECD 2021): GDPR, for example, requires decision- making models for financial services and insurance to be explainable, which is mostly achieved using traditional models such as decision tree variants (Goodman & Flaxman, 2017). Outside consumer finance, governance rules require explanability of portfolio and risk management for auditing purposes (Gensler & Bailey| 2020). Again, DNNs (deep neural networks) are not satisfactory from a current regulatory point of view and, thus, the financial services and insurance sectors rely on more explainable models (such as tree-based ones), also in federation.
This paper. Our framework improves on the above approaches in several ways, summarized also in Table [ (1) It is more general, as it can tune multiple HPs and is applicable non SGD-training settings such as gradient boosting trees. This is achieved by treating FL-HPO as black-box HPO problem (as opposed to grey-box HPO where we can leverage techniques such as weight-sharing and multi-fidelity). which has been addressed in centralized HPO literature using grid search, random search (Bergstra & Bengio 2012) and Bayesian Optimization approaches (Shahriari et al., 2016). The key challenge is the requirement to perform computationally intensive evaluations on large number of HPO configurations. where each evaluation involves training a model and scoring it on validation dataset. In the distributed FL setting this problem is exacerbated because validation sets are local to the parties and each FL. training/scoring evaluation is communication intensive. Therefore brute force application of centralized black-box HPO approaches that select HPs in an outer loop and proceed with FL training evaluations is not feasible. (2) It yields minimal HPO communication overhead. This is achieved by building a loss surface from local asynchronous HPO at the parties that yields single optimized HP configuration used to train global model with a single FL training. (3) It is the first that theoretically characterizes the optimality gap in an FL-HPO setting, for the case we focus in this paper: creating a global model by tuning multiple global HPs without accessing global validation dataset (as opposed to existing work either optimizing wrt parties' validation datasets or assuming access to a global validation dataset during HPO).
3

---

Published as a conference paper at ICLR 2023
Table I: Positioning of our proposed framework FLoRA against existing literature. single-shot, MF: fillii-iielity. WS: weight-sharing. dc: global model HPPs. Φ: aggregator HPs. See 2 f: FedHPO-B is benchmarking suite and not an algorithm, and the properties correspond to the problems in the suite.
Mothod
Any ML model
58
No MF req.
No WS req.
Handles Og
Handles &
Black-box
Black-box HPO
/
NA NA
Grey-box HPO
x
FNAS
x
x
x
x
NA
X
FedEx
x
FLoRA (Ours)
/
x
FedHIPO.B'
X
2 METHODOLOGY
In the centralized ML setting, we would consider model class M and its corresponding learning algorithm A parameterized collectively with HPs 0 E O and given training set D, we can learn single model A(M, 0, D) + m E M. Given some predictive loss [(m, D*) of any model m scored on some holdout set D', the centralized HPO problem can be stated
mingge C(A(M, 0, D), D')
(2.1)
In the most general FL setting, we have p parties P1. ................................ Pp each with their private local training dataset D,, í E [p] = (1,2.....,P) Let D = -.= D; denote the aggregated training dataset and D = (i denote the set of per-party datasets. Each model class (and corresponding learning algorithm) is parameterized by global HPs 0g E Og shared by all parties and per-party local HPs
o E L,, E [p] with e = -G x Or. FL systems usually include an aggregator which introduces an additional set of HPs & ob Finally, we have FL algorithm F
F (M, 0g, 0G h A.D)) + m M,
(2.2)
which takes as input all the relevant HPss and per-party datasets and generates a model. In this case, the FL-HPO problem can be stated in the two following ways depending on the desired goals: (i) Ideally, for a global holdout/validation dataset D' (possibly from the same distribution as the aggregated dataset D), the target problem is:
2 {F &, 0c. heb): A.D) .
min de + o E O 0 0 selp
(2.3)
(ii) An alternative target problem would involve per-party holdout datasets D/, E [p] as follows:
((E(( (M. (MM.000..0 oc, hEl)) (E A. D.) i E bn))) (2.4)
min $ 0..00 (ep)
Agg
where Agg: IPP - IR is some aggregation function (such as average or maximum) that scalarizes the p per-party predictive losses.
Contrasting problem (2.1) to problems 2.3 & 2.4). we can see that the FL-HPO is significantly
more complicated than the centralized HPO problem. In the ensuing presentation, we focus on problem (2.3) although our proposed single-shot FL-HPO scheme can be applied and evaluated for
problem 2.4 We simplify the FL-HPO problem in the following ways: (i) we assume that there is
no personalization so there are no per-party local HPs 006 i [p]. (ii) we only focus on the model class HPs Oc. deferring HPO for aggregator HPs for future work as many of them are set based on the communication and computational resources available in the FL system and cannot be directly optimized with regards to some predictive performance metries, and (iii) we assume there is a global holdout/validation set D' which is only used to evaluate the final global model's 's performance but can not be accessed during HPO process. And parties can only access their own private training D, and validation D' sets. Hence the problem we will study is stated as for fixed aggregator HP Ø;:
(2.5) This problem appears similar to the centralized HPO problem (2.1). However, note that the main challenges in (2.5) is (i) the need for federated training for each set of HPs Oc. and (ii) the need to evaluate the trained model on the global validation set D' (which is usually not available in usual FL- HPO setting). Hence it is not practical (from a communication overhead and functional perspective) to apply existing thf--ff HPO schemes to problem (..5). In the subsequent discussion, for simplicity purposes, we will use 0 to denote the global HPs, dropping the "G" subscript.
mingaee: L (F (M, d, Oc, D) D').
4

---

Published as a conference paper at ICLR 2023
2.1 LEVERAGING LOCAL HPOS
While it is possible but extremely expensive to ap- ply off-the-shelf HPO solvers (such as Bayesian
Algorithm 1 FL-HPO with FLORA
1: I F. F...F.DD........ DOHEE F.((D...)))ee
Optimization (BO) (Shahriari et al] 2016). Hyper- opt (Bergstra et al.) 2011), etc.), we wish to under- stand how we can leverage local and asynchronous HPOs in each of the parties. We begin with a sim- ple but intuitive hypothesis underlying various meta- learning schemes for HPO (Vanschoren 2018 Wis-
2: for each party P..
do Run HPO to generate T (HP, loss) pains
3:
F {1o) (.0 E
(2.6)
0.50 E @ cf == L(A(M, D..
4: end for
tuba et al. 2018 Ram 2022); if HP configuration has good performance for all parties independently, then O is a strong candidate for federated training.
5: Collect all (E E [p]] in aggregator
Generate a unified surface 8. using
7: Select best HP candidate
With this hypothesis, we present our proposed FLoRA in Algorithm TT In this scheme, we allow each party to perform HPO locally and asynchronously with some adaptive HPO scheme such as BO (line 3).
0'
+
min ²(0). OCO
(2.7)
8: Invoke federated training F(M, (.M.)
9: Output: FL model m.
Then, at each party E [p]. we collect all the attempted T HPs , [T] = (1,2,..... .). and their corresponding predictive loss c( into set E(0 (line 3, equation (266)) Then these per-party sets of (HP, loss) pairs E00) are collected at the aggregator (line 5). This operation has at most O(p7') communication overhead (note that the number of HPs are usually much smaller than the number of columns number of rows in the per-party datasets). These sets then used to generate an aggregated loss surface f + (line 6) which will then be used to make the final
single-shot HP recommendation 0 - (line 7) for the federated training to create the final model m E M (line 8). We will discuss the generation of the aggregated loss surface in detail in 2.2 Before that, we briefly want to discuss the motivation behind some of our choices in Algorithm
Using adaptive HPO schemes instead of non-adaptive schemes (such as random search or grid search) allows us to efficiently approximate the local loss surface more accurately (and with more certainty) in regions of the HP space where the local performance is favorable instead of trying to approximate the loss surface well over the complete HP space. This has advantages both in terms of computational efficiency and loss surface approximation. Morcover, each party exccutes HPO asynchronously, without coordination with HPO results from other parties or with the aggregator. This is in line with our objective to minimize communication overhead. Although there could be strategies that involve coordination between parties, they could involve many rounds of communication. Our experimental results show that this approach is effective for the datasets we evaluated for.
Remarks.
2.2 LOSS SURFACE AGGREGATION
Given the sets of (HP, loss) pairs E = (,)", [p]. E [T] at the aggregator, we wish to construct a loss surface ?: θ + R that best emulates the (relative) performance loss {()) we would observe when training the model on D. Based on our hypothesis, we want the loss surface to be such that it would have relatively low (()) if 0 has low loss for all parties simultaneously. However, because of the asynchronous and adaptive nature of the local HPOs, for any HP E O we would not have the corresponding losses from all the parties. For that reason, we will model the loss surfaces using regressors that try to map any HP to their corresponding loss. We present four ways of constructing such loss surfaces, and we also briefly summarize them in Table 2
The most straightforward way to construct such loss surface is to merge all the per-party sets E to get a single set E' = Upeip g(i) and use it to train a regressor f θ - IR (such as Random Forest Regressor (Breiman) (001)) using the HPs as the covariates and the corresponding loss as the dependent variable. Then we can define the loss surface as this single global model or SGM ((0) := f()). However, this loss surface is extremely optimistic, assigning a low loss to HP if it had a low loss estimate on any one of the parties, making it unsuitable in the presence of data heterogeneity. We can leverage uncertainty quantification
θ + R, around regressor predictions to get loss surface (()) = [(0 + cf)(f) for some a > 0 the single global model with uncertainty
5

---

Published as a conference paper at ICLR 2023
or SGM+U. This would improve the robustness of SGM by penalizing parts of the HP space which were not well explored by all parties' local HPOs.
Instead of merging the per-party E(i,, we can also use them to train a per-party local regressor model f(²) + R and use their ensemble as the loss surface. One way is to use the average of the per-party local models or APLM as the loss surface {()) :=
Table 2: Loss surfaces: f + R is the global loss surface generated using the aggregated set Use Ex() the per-party set loss pairs g(9) from each party i E [p]. u 2 + R is an uncertainty model generated using the aggregated set Usete] E and IR for any E [p] is the per-party loss surface generated using the party's loss pairs g
t/v Eie(p) (0). This less optimistic than SGM and provides some level robustness in the presence of non-IID heterogencous per-party distributions since will assign a low loss for a HP only if its average across all per-party regressors is low, which implies that most parties observed a relatively low loss around this HP. An even more robust loss surface would be the maximum of the per-party local models or MPLM (() = maxie[pl (0) which would only assign a low loss to HP only it has low loss estimate across all parties, making it extremely capable of handling data heterogeneity (as we will also highlight in our empirical evaluations). We discuss these loss surfaces in detail in Appendix B In [2.3] we theoretically quantify the performance guarantees for MPLM and APLM, and [ we empirically evaluate all these loss surfaces.
0s a constant. fi A
Surface
8(0) ==
Optimism
Non-IID
SGM
f(0)
High Medium Low
SGM+U
((0) + ut0)
Partial
MPLM
max.ebe f:(0)
APEM
1/2 2ich) f.(0)
Medium
2.3 OPTIMALITY ANALYSIS
We now rigorously analyze the outtoapimll of the HP selected by FLoRA. We are interested in providing bound for the following optimality gap:
= 100 D) - ((",))), where 0 E mingee ε(0, D).
(2.8)
Here ?(0, D) is an estimate of the true loss E D) == ((t.)))DD((((A.).. D), (I, y)) (see Defini- tion C.I) given some validation set D' sampled from D, which is the model performance metric during evaluation and/or inference time. Recall that 0* selected by FLoRA is defined as in (2.7)... and 0" denotes the optimal HP given by & for desired data distribution D we want to learn.
We present our main results Theorem 2.1 Informally, we show how to bound the optimality gap by picking the 'worst-case" HP setting that maximizes the combination of Wasserstein distances of the local data distributions and actual quality of local HPO approximation across parties. The more precise theorem statement and its proof with formal discussion of technical definitions and assumptions can be found in Appendix C
Theorem 2.1. Suppose that the loss estimate i and the unified loss surface i are Lipschitz continuous.
Consider the optimality gap G defined in (2.8) where 0 is selected by FLoRA with each party i E [p] collecting T (HP, loss) pairs {() c.( HearT during the local HPO run. For a desired data distribution D = Σi= Di, where (Di) (Dieeeto) are the sets of parties' local data distributions and w; E [0, 1], Vi [p], we have
g < max Ca ( WE WiD + CC,L mingetr d(0, 0(9) 6i}. (2.9) PE
In particular, when all parties have i..d. local data distributions, 2.9 reduces to
g S maxoce Eier (a(( {Ci,t, mineejyy d(e.0 0 6.}
Here Co. C3 and Ci.i. are constants only related to the unified loss surface and Lipschitz-ness, respectively, Wi(:.)) and .).,-) distance metrics defined over data distribution and hyper- parameter space θ respectively, and o, is the maximum per sample training error for the local loss surface E, i.e. 5, max, (c()) }
There are several interesting observations from Theorem 2.1 (i) The first term in our bound 2.9 characterizes the errors incurred by parties' data heterogeneity, measured via the 1-Wasserstein

---

Published as a conference paper at ICLR 2023
Table 3: Comparison different loss surfaces (the 4 rightmost columns) for FLoRA relative to the baseline for single-shot 3-party FL-HPO in terms of the relative regret (lower is better).
Aggregate
ML Method
SGM
SGM+U
MPLM
APLM
Regret
HGB
[0.30, 0,47, 0.68]
[0.27, 0.54, 0.64]
[0.25, 0.43, 0.67]
[0.25, 0.50, 0.65]
Inter-quartile range
SVM
10.04, 0.38. 1.11]
10,04, 0,48,
[0.38, 0.91, 2.41]
[0.23, 0.54, 0.76]
MLP
[0.36, 0.80, 0.97]
[0.48, 0.99, 1.01]
[0.47, 0.89, 1.00]
[0.46, 0,79, 0.95]
Overall
[0.22, 0.53, 0.97)
[0.32, 0.55, 1.01]
[0.36, 0.61,
[0.36, 0.57, 0.79)
FLoRA
HGB
6/01
6//1
7/0/0
7/0/0
Wins/Ties/Losses
SVM
4/02
4/02
3/03
5/0/1
MLP
6/1/1
4/1/2
5/1/1
6/1/1
Overall
16/0/4
14/1/5
15/1/4
18/0/2
Wileoxon Signed-Rank Test I-sided (statistic.--value)
HGB
(26, 0,02126)
(27. 0.01400)
(28, 0.00898)
(28, 0.008998
SVM
(18, 0.05793)
(17, (17.0.08648)
(9, 0.62344)
(15, 0.17272)
MLP
(21. 0.11836)
(15,0. 0.17272))
(18, 0.05793)
(24. 0,045588 (183.5, 0.00169)
Overall
(174, 0.004999
(164, 0.00272)
(141, 0.03206)
the magnitude of Non-IIDness in a FL system; we can see it vanish under the IID setting, (ii) The last two terms measure the quality of the local HPO approximation, which can be reduced if good loss surface is selected. For example, if we use non- non-parametric regression models as the loss surfaces, the per- per-sample training error can be arbitrarily small (that is 6, = 0), but at the cost of increasing Li for f. (iii The min d(0, 0 term indicates that the optimality
distance (Villani 2021
gap depends only on the HP trials o that are closest to the optimal HP setting. (iv) If we assume each party's 's training dataset D; is of size n, sampled as D; D we can view w; "; where Ee=1 ny i..., with probability w, the desired data distribution D is sampled from D;.
Now we would like to compare our theoretical results with existing analyses such as Khodak et al.) (202T) and He et al. (2020). Among many differences in the FL-HPO problem setting, there two key points we want to emphasize: (i) Theorem presents the first optimality gap in terms of loss function value for the single-shot FL-HPO setting, and can be applied to both algorithmic and model architecture HPs, while existing works either lack theoretical guarantees or establish weaker optimality gap measured by the regret defined for an online setting and are only applicable single HP optimization. (ii) We only make mild Lipschitz assumption regarding the loss function, and do not require any assumptions on the convexity of the loss function, the parties' local data distributions. or the training al algorithms, while existing works usually require convexity and certain restrictions on the MI. training algorithm to obtain their convergence guarantees.
EMPIRICAL EVALUATION
In this section, we evaluate FLoRA with different loss surfaces for the FL-HPO problems on a variety of ML models - histograms based gradient boosted (HGB) decision trees (Friedman 200T), Support Vector Machines (SVM) with RBF kernel and mullti-layered perceptrons (MLP), using their respective scikit-learn implementations (Pedregosa et al.) 2011) OpenML (Vanschoren et al. 2013) classification problems. First, we fix the number of parties = 3 and compare FLoRA to a baseline on 7 datasets. Then we study the data heterogeneity effect the performance of FLoRA. Finally, we evaluate FLoRA with different parameter choices, in particular, the number of local HPO rounds and the communication overhead in the aggregation of the per-party (HP, loss) pairs. More comprehensive experimental results and FLoRA performance on real FL systems can be found in Appendix D
Baselines. To appropriately evaluate our proposed single-shot FL-HPO scheme, we need to se- lect meaningful single-shot baseline. For this, we choose the default HP configuration of scikit-learn as the single-shot baseline for two main reasons: (i) the default HP configu- ration in sci taikiiteeaaa rn is set manually based on expert prior knowledge and extensive empirical evaluation, and (ii) these are also used as the defaults the Auto-Sklearn package (Feurer et al.. 2015; 2020), one of the leading open- AutoML python packages, which maintains carefully selected portfolio of default configurations. While there are some existing schemes for FL-HPO, we unable to compare FLoRA to them see Table for detailed comparison.
Implementation and evaluation metric. We emulate the final FL (Algorithm line 8) with a centralized training using the pooled data. We chose this implementation because want to evaluate the final performance of any HP configuration (baseline or recommended by FLoRA) in a statistically robust manner with multiple train/validation splits (for example, via 10-fold cross- voss-validation) instead
7

---

Published as a conference paper at ICLR 2023
of evaluating the performance on single train/validation. This form of evaluation is extremely expensive to perform in a real FL system and generally not feasible, but allows us to evaluate how the performance of our single-shot HP recommendation fairs against that of the best-possible HP found via a full-scale centralized HPO. In all datasets, we consider the balanced accuracy as the metric wish to maximize. For the local per-party HPOs (as well as the centralized HPO execute to compute the regret), we maximize the 10-fold cross-validated balanced accuracy. For Table 344 we report the relative regret, computed as (a-= where a* is the best metric obtained via the centralized HPO, 6 is the result of the above single-shot baseline, and a is the result of the HP recommended by FLORA. The baseline has a relative regret of 1 and smaller values imply better performance. A value larger than 1 implies that the recommended HP performs worse than the single-shot baseline.
Comparison to single-shot baseline. We first compare FLoRA with the baseline across different datasets, ML models and FLoRA loss surfaces summarized in Table with the individual results detailed in Appendix DD3 For each method, we report the aggregate performance over all considered datasets in terms of (i) inter-quartile range, (ii) Wins/Ties/LLosee of FLORA w.r.t. the single-shot baseline, and (iii) one-sided Wilcoxon Signed Ranked Test of statistical significance with the null hypothesis that the median of the difference between the single-shot baseline and FLoRA is positive against the alternative that the difference is negative (implying FLoRA improves over the baseline). Finally, we report an "Overall" performance, further aggregated across all ML models.
All FLoRA loss surfaces show strong per- formance w.r.t. the single-shot baseline, with significantly more wins than losses, and 3rd-quartile relative regret values less than 1 (indicating improvement over the baseline). All FLORA loss surfaces have a p- p-value of less than 0.05, indicating that we can reject the null hypothesis. Over- all, APLM shows the best performance over all loss surfaces, both in terms of Wins/ Tinssiics/Loses over the baseline as well as in terms of the Wilcoxon Signed Rank Test, with the highest statistic and a p- p-value close to 10-3, APLM also has significantly lower 3rd-quartile than all other loss surfaces. MPLM appears to have the worst performance but
Table 4: Effect of increasing the number of parties on FLoRA
with different loss surfaces for HGB.
Data
P
Tp
SGM
SGM+U
MPLM
APLM
EBG
3
0.14
0.12
0.11
14980 rows
10
1.03
0.08
0.00
0.16
0.01
25
1.08
0.35
0.92
0.17
0,04
50
1.20
0.20
0.23
0.67
0.12
Electricity
3
0.17
0.14
0.09
45312 rows
10
1.02
0.03
0.06
0.32
0.14
25
0.40
0.42
1.42
50
1.07
1.57
1,57
0.89
1.13
100
1.14
1.45
1.47
0.48
1.11
Pollen
3
1.02
0.43
0.54
0.43
0.69
3848 rows
1.10
1.02
0.91
0.54
10
1.16
1.05
0.73
0.75
1.12
much of that is attributable to a couple of very hard cases with SVM (see Appendix [D.3 detailed discussion). Otherwise, MPLM performs second best both for FL-HPO with HGB and MLP.
Effect of data heterogeneity. In the second set of experiments, we study the effect of increasing the number of parties in the FL-HPO problem. For each data set, we increase the number of parties up until each party has at least 100 training samples. We present the relative regrets in Table 4 It also
displays 7p- == (1-minuejs) <! (5() (1//(11mmmm) (1-maxxxem)) ). where c(() = minge(r) - is the minimum loss observed during the local HPO at party This ratio 7/p is always greater than 1, and quantifies the
inter-party data heterogeneity - prrciselly % ~ 1 Ô (max (D, D)) (Appendix C.5
The results indicate that, with low moderate increase in 7pp (EEG eye state, Electricity for moderate p). the proposed scheme is able to achieve low relative re- gret. However, with significant increase in ii (Pollen, Electricity with p 50, 100 and EEG Eye State with p 50), the relative regret increases as well (even > 1 in a few cases).
Table 5: Effecct of data hetergeneity FLoRA with MNIST.
Method
SGM
SGM+U
MPLM
APLM
MLP
1.01
0.85
0.56
0.29
0.06
HGB
1.01
0.51
0.92
0.64
0.51
We also simulate different form of data heterogeneity based on the MNIST dataset and present the results in Table [ In particular, there are parties in total, with half of the parties having 4 times higher probability to have more even digits while the other half have more odd digits. In most challenging cases, MPLM (the most pessimistic loss function) has the most graceful degradation in relative regret compared to the remaining loss surfaces.
Communication savings over multi-shot. Figure presents the communication overhead savings (in terms of the number of FL. model trainings) from FLoRA over multi-shot HPO by applying
8

---

Published as a conference paper at ICLR 2023
MLP:Heart MLP:Sonar
SVMIEEG Sonar
MoP-
Relative regret
Relative regret
1.0
SonaS
1.25
SEM
05
SVM Sonar
04
0.75
01
035
00
0.00
2'
2
# local HPO rounds T
Communication overhead
(a) Regret vs # local HPO rounds.
(b) Regret vs # (HP, loss) pairs communicated
Figure 3: Effect of different choices on FLoRA with the APLM loss surface for different methods and datasets.
More results and other loss surfaces are presented in Appendix D.6 and D.7
standard HPO to FL-HPO. For ease of exposition, we present results with HGB with 2 loss surfaces MPLM and APLM. More results are presented in Appendix[D.4 DD4] Similar to Figure [ we report the number of FL model trainings required for multi-shot to match the relative regret achieved by FLoRA (+), with the single-shot baseline performance (relative regret of 1 with 1 FL model training,
denoted by .) presented as a reference. In aggregate, FLoRA with APLM achieves median savings of 8x, 15x and 10x over the multi-shot baseline for HGB, SVM and MLP respectively.
Effect of different choices in FLoRA. In this set of experiments, we consider FLORA with the APLM loss surface, and ablate the effect of different choices in FLoRA on 2 datasets each for SVM and MLP. First, we study the impact of the thoroughness of the per-party local HPOs, quantified by the number of HPO rounds T in Figure 3a The results indicate that for really small T' (< 20) the relative regret of FLoRA can be very high. However, after that point, the relative regret converges its best possible value. We present the results for other loss surfaces in Appendix D.6
We also study the effect of the communication overhead of FLoRA for fixed level of local HPO thoroughness. We assume that each party per- forms 7 = 100 rounds of local asynchronous HPO. However, instead of sending all T' (HP, loss) pairs, we consider sending 7" < T of the "best" (HP, loss) pairs- - that is, (HP, loss) pairs with the T' lowest losses. Changing the value of T" trades off the communication overhead of the
MPLM
APLM
Relative Regret
Naaii
# Federated Model Trainings
Figure 2: Communication savings of FLoRA compared to "multi-shot" FL-HPO for the same level of relative regret (lower better). Each pair of (*, connected by a dashed line corresponds to a dataset labeled as D1-D7 for ease of visualization. See Table 6l Appendix D.I for dataset names.
FLoRA step where the aggregators collect the per-party loss pairs (Algorithm) [] line 5). The results for this study are presented in Figure (b) and indicate that, for really small T", the relative regret can be really high. However, for mod- erately high value of T < T, FLoRA converges to its best possible performance. Results and discussions on other loss surfaces are in Appendix D.7
CONCLUSION AND FUTURE WORK
Effective selection of HPs in FL settings is a challenging problem. In this paper, we introduced FLoRA, single-shot FL-HPO algorithm that can be applied any ML model. We provided theoretical analysis which bounds the optimality gap incurred by the HP selected by FLoRA. Our experiments show that FLoRA can effectively select HPs that outperform the baseline with just a single FL training. As future work, we wish to extend FLoRA to the Combined Algorithm Selection and HPO (CASH) problem (Thortton et al. 2012 Feurer et al. 2015) with or without fixed MI. pipeline architecture (Baudart et al.) 2021| Hirzel et al. 2022. Katz et al.; 2020; Marinescu et al.) 202I), especially in the presence of computational and fairness constraints (Liu et al. 2020 Ram et al. 2020), and understand the various theoretical trade-offs in FL-HPO (Ram et al. 2023). One limitation of FLoRA is that it cannot handle HPs that are inactive during local HPO. These include aggregator specific and some FL training specific HPs. It is unlikely that such HPs can be handled in single-shot FL-HPO without any additional information or structure. As future work, we wish to extend FLoRA to handle such HPs in "few-shot" FL-HPO, potentially in conjunction with multi-fidelity HP evaluations.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
The code and instructions to reproduce our numerical results can be found in suppiemental materials. For formal definitions, assumptions and proofs of Theorem 2.1 one can find them in Appendix C We provide description of the datasets used in our experiments in Appendix D.1 One can also find original datasets in supplemental materials.
ACKNOWLEDGEMENTS
We would like to thank Martin Wistuba for his input during the initial discussions on this research thread. We would also like thank the organizers of the NFFL workshop at NeurIPS'21 for allowing us to present an initial version of this work to a wider audience (Zhou et al. (02TT).
REFERENCES
Guillaume Baudart, Martin Hirzel, Kiran Kate, Parikshit Ram, Avi Shinnar, and Jason Tsay. Pipeline combinators for gradual AutoML. Advances in Neural Information Processing Systems, 34: 19705-19718, 2021.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13(Feb):281-305. 2012.
James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper-parameter
optimization. In Advances in neural information processing systems, pp.
2011.
Leo Breiman. Random forests. Machine learning, +5(1):5-32, 2001.
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 16, pp. 785-794, New York, NY, USA, 2016. ACM. ISBN 978 45033-4232-2. doi: 10.1 10.1145/9939772.293777
1001/115//2 020444/2239672 2939785 URL http://ttt//o. acm. org 10. /t.g///..11..111
Z. Dai, B.K.H. Low, and Jaillet. Federated Bayesian Optimization via Thompson Sampling. Advances in Neural Information Processing Systems, 33, 2020.
Z. Dai, B.K.H. Low, and Jaillet. Differentially private federated Bayesian optimization with distributed exploration. Advances in Neural Information Processing Systems, 34, 2021.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter op- timization at scale. In International Conference on Machine Learning, pp. 1437-1446. PMLR, 2018.
Matthias Feurer, Aaron Klein, Katharina Eggensperger, Jost Springenberg, Manuel Blum, and Frank Hutter. Efficient and robust automated machine learning. In Advances in Neural Information Processing Systems, pp. 2962-297777 2015.
Matthias Feurer, Katharina Eggensperger, Stefan Falkner, Marius Lindauer, and Frank Hutter. Auto- skleam 2.0: The next generation. In arXiv:2007.04074 [cs.LG], 2020.
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Anubhav Garg, Amit Kumar Saha, and Debo Dutta. Direct federated neural architecture search. arxiv.2010.06223, 2020.
Gary Gensler and Lily Bailey. Deep learning and financial stability. Available at SSRN 3723132, 2020.
Bryce Goodman and Seth Flaxman. European union regulations on algorithmic decision-makinn and "right explanation". Al magazine, 38(3):50-57, 2017.
10

---

Published as a conference paper at ICLR 2023
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Towards non-ii.d. and invisible data with FedNAS: Federated deep learning via neural architecture search. wwxi:2004.085455 2020.
Martin Hirzel, Kiran Kate, Parikshit Ram, Avraham Shinnar, and Jason Tsay. Gradual AutoML using Lale. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 4794-4795, 2022.
Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren (eds.). Automated Machine Learning Methods, Systems, Challenges. Springer, 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems federated learning. arXiv preprint arXiv: /ttp::/922.44250 2.00977, 2019.
Michael Katz, Parikshit Ram, Shirin Sohrabi, and Octavian Udrea. Exploring context-free languages via planning: The case for automating machine learning. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pp. 403-411, 2020.
Mikhail Khodak, Tian Li, Liam Li, M Balcan, Virginia Smith, and Ameet Talwalkar. Weight sharing for hyperparameter optimization in federated learning. In Ini. Workshop on Federated Learning for User Privacy and Data Confidentiality in Conjunction with ICML 2020, 2020.
Mikhail Khodak, Renbo Tu, Tian Li, Liam Li, Maria-Florina Balcan, Virginia Smith, and Ameet Talwalkar. Federated hyperparameter tuning: Challenges, baselines, and connections to weight- sharing. arXiv preprint urXiv:2106.04502 2021.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster),
2015. URL BRtthtt/p//axxi org/ abs 111//11111.. 6980
Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast Bayesian optimization of machine learning hyperparameters on large datasets. In Artificial intelligence and statistics, pp. 528-536. PMLR, 2017.
A. Koskela and A. Honkela. Learning rate adaptation for federated and differentially private learning. arXiv preprint arXiv: 039333 2019.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. HyperBand: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(185):1-52, 2018.
Qinbin Li, Zeyi Wen, and Bingsheng He. Practical federated gradient boosting decision trees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4642-4649, 2020.
Sijia Liu, Parikshit Ram, Deepak Vijaykeerthy, Djallel Bouneffouf, Gregory Bramble, Horst Samu- lowitz, Dakuo Wang, Andrew Conn, and Alexander Gray. An ADMM based framework for ShiirtyFFurth AAAI Conference on Artificial Intelligence, 2020. URL httpp:://a.ii...tttt http://aawxxxpxpaa///a///
AutoML pipeline configuration.
00424v5
Heiko Ludwig, Nathalic Baracaldo, Gegi Thomas, Yi Zhou, Ali Anwar, Shashank Rajamoni, Yuya Ong, Jayaram Radhakrishnan, Ashish Verma, Mathicu Sinn, et al. IBM Federated Learning: an enterprise framework white paper vO. arXiv preprint arXiv:2007.10987, 2020. URL
https:://ithhin com BMM
Radu Marinescu, Akihiro Kishimoto, Parikshit Ram, Ambrish Rawat, Martin Wistuba, Paulito P Palmes, and Adi Botea. Searching for machine learning pipelines using context-free grammar. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8902-8911, 2021.
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Arcas. Communication-efficiine learning of deep networks from decentralized data. In Proc. International Conference on Artificial Intelligence and Statistics, pp. 1273-1282, Ft. Lauderdale, FL, 20-22 Apr 2017a
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. coamuuiccatio--fffiiiee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 177--1282. PMLR, 2017b.
11

---

Published as a conference paper at ICLR 2023
H. Mostafa. Robust federated learning through representation matching and adaptive hyper- parameters, arXiv preprint arXiv:1912.13073. 2019.
OECD. Artificial intelligence, machine learning and big data finance: Opportunities, challenges.
and implications for policy makers, 2021. URL https: wwww www.. http://wwwwwwwww//aaaaaae..aeeae
artificial-intell wtw.::/www..........aaaaaaaaaaaa -nnn----aaa-----aanee.. finance.
htm
Changyong Oh, Jakub M Tomezak, Efstratios Gavves, and Max Welling. Combinatorial Bayesian optimization using the graph cartesian product. In Proceedings the 33rd International Conference on Neural Information Processing Systems, pp. 2914 2924, 2019.
Yuya Jeremy Ong, Yi Zhou, Nathalie Baracaldo, and Heiko Ludwig. Adaptive histogram- gradient boosted trees for federated learning. arXiv preprint arXiv:2012.06677 2020.
Pedregosa. G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-28835 2011.
Parikshit Ram. On the optimality gap of warm-started hyperparameter optimization. In International Conference on Aulomated Machine Learning, pp. 12-1. PMLR, 2022.
Parikshit Ram, Sijia Liu, Deepak Vijaykeerthi, Dakuo Wang, Djallel Bouneffouf, Greg Bramble, Horst Samulowitz, and Alexander G Gray. Solving constrained CASH problems with ADMM. In 7th ICML Workshop on Automated Machine Learning (AutoML), 2020.
Parikshit Ram, Alexander G Gray, Horst C Samulowitz, and Gregory Bramble. Toward theoretical guidance for two common questions in practical crossvvalddttion based hyperparameter selection. In SIAM International Conference on Data Mining (SDM23), SIAM, 2023.
S.J. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konecny, S. Kumar, and H.B. McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2020.
B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. De Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1):148-175 2016.
Kevin Swersky, Jasper Snoek, and Ryan Prescott Adams. Freeze-thaw Bayesian optimization. arXiv preprint 14.6::1446.38888 2014.
Chris Thornton, Holger H. Hoos, Frank Hutter, and Kevin Leyton-Brown. Auto-WEKA: Automated selection and hyper-parameter optimization of classification algorithms. arXiv, 2012. URL
httt::/aaxiv.oogg/aa//
3319
Joaquin Vanschoren. Meta-learning: survey. arXiv preprint arXiv:1810.03544 2018.
Joaquin Vanschoren, Jan N. Rijn, Bernd Bischl, and Luis Torgo. OpenML: Networked science in machine learning. SIGKDD Explorations, 15(2):49 60, 2013. doi: 10.1145/2641199.26411999
URL http::/tt//o..../ acm. wtt.a/..r.01111111.11111111 2641199999922
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. Journal Selected Areas in Communications (JSAC), 2019.
Zhen Wang, Weirui Kuang, Ce Zhang, Bolin Ding, and Yaliang Li. FedHPO-B: A benchmark suite for optiiiiitt optimization. arXiv preprint arXiv:2206.03800000 2022. URL/tttps://
federated hyperparameter
Christopher K Williams and Carl Edward Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
Martin Wistuba, Nicolas Schilling, and Lars Schmidt-Thiee Scalable Gaussian process- based transfer surrogates for hyperparameter optimization. Machine Learning, 107(1):43-78, 2018.
12

---

Published as a conference paper at ICLR 2023
Mengwei Xu, Yuxin Zhao, Kaigui Bian, Gang Huang, Qiaozhu Mei, and Xuanzhe Liu. Federated neural architecture search. arxin.2002.06552, 2020.
Yi Zhou, Parikshit Ram, Theodoros Salonidis, Nathalie Baracaldo, Horst Samulowitz, and Heiko Ludwig. FLoRA: Single-shot hyper-parameter optimization for federated learning. Ist Workshop on New Frontiers in Federated Learning: Privacy, Fairness, Robustness, Personalization and Data Ownership at NeurlPS'21 21, 2021.
13

---

Published as a conference paper at ICLR 2023
A ADDITIONAL DISCUSSION ON RELATED WORKS
In this section, we provide further discussion of related work and how our work compares against them.
A.1 MULTI-FIDELITY HPO AND FL-HPO
In centralized HPO, the evaluation of single HP configuration entails the training the MIL model with the provided HP and training data, the inference of the trained model on some held-out samples (validation data) to get predictions, and the evaluation of the quality of these predictions against available ground-truth. The most computationally expensive part of this process is the model training. Multi-fidelity HPO seeks to reduce the overall computational cost of HPO with cheap evaluations that essentially reduce the model training cost (Swersky al. 2014 Klein et al. 2017 Li et al.) 20188) Falkner et al. 2018). For models trained via some form of (stochastic) gradient descent, a cheap evaluation of HP configuration is obtained by computing the predictive performance of the model trained with limited number of gradient descent iterations - the number of iterations is the notion of budget. Under the assumption that more budget does not degrade the performance of any given HP configuration, multi multi-fidelity HPO solvers adaptively allocate more budget to more promising HP configurations while discarding low- low-perfrrming HP configurations cheaply by evaluating them with a low budget.
With models not trained by gradient descent, such as decision-tree based models or nearest-neighhor models or some kernel machines, a commonly used notion of budget is the training set size cheap ovaluations are performed by training the model for any given HP configuration with just a smaller training set size, with the assumption that smaller training set sizes usually speed up the training, which is usually true for most MI. models.
One significant distinction between the two notions of budget: With the iteration budget, we able to progressively train the models for the high performing HP configurations (albeit with additional storage by checkpointing the models after each evaluation with every budget allocation). With the training size budget, we usually have to train the models from scratch for each budget allocation; for example, there is no standard way of progressively updating decision tree trained on 100 samples with new training size allocation of 500 samples.
A.1.1 MULTI-FIDELITY IN FL-HPO
In FL-HPO, one of the main bottlenecks is the communication overhead and cheap evaluation in multi-fidelity FL-HPO would require to control the number of communication rounds in a particular FL training. For gradient descent based training scheme, the number of iterations is a commonly used notion of budget (Khodak al. (02T since this number of iterations is a good surrogate for the number of communication rounds that gets allocated to the (cheap) FL training. Hence, multi -idelityy FL-HPO is useful for neural networks.
the training set size as a notion of budget (used for other ML models) does not necessarily control the number of rounds of communication in FL-HPO. For example, when training decision tree of depth in a FL. setting (Ong et al. 2020), one would require around 5-6 rounds of communication regardless of the per-party training set sizes reducing the training set size on each party would not reduce the number of communication rounds in the FL training. Hence, the training set size is not a useful notion of budget for where we cannot make use of milti-fidelity HP evaluations. This does not consider the checkpointing overhead present in multi-fidell fideliyyy FL-HPO with iteration budget.
However,
FL-HPO. For this reason, focus on the FL-HPO problem
Precise communication overheads of differrnt schemes. We would like to highlight that, even when comparing to some multi-fidelity FL-HPO scheme, the single-shot FLORA can still provide communications savings. Consider simplistic setup where each FL training requires C' communica- tion rounds. For the single-shot FLoRA, the overall communication overhead will be OCC) since we would need a single FL training and some additional communication which is much much smaller than the FL training communication overhead (see 12.1 Figure 4c and 3b). If multi-shot FL-HPO tries NN HP configurations, then the communication overhead will be OCC N) (see Fig 4b). For multi- fidelit FL-HPO which leverages some form of successive halving'elimination, it can be shown that the total communication overhead for attempting N HP configurations is O(C log N) which is
14

---

Published as a conference paper at ICLR 2023
Agpregator
Appregator
Agpoggeer
<(Rc
Ma 4
(b) Multi-shot FL-HPO,
(c) FL-HPO with FLoRA.
(a) A single FL. training.
Figure 4: Visualizations of the communication in FL training and different FL-HPO setup. 4a single FL training involves multiple communication rounds. {4b) Multi-shot FL-HPO requires
A
multiple FL trainings for each of the different HPs 0g evaluated.
(4c FL-HPO with FLoRA requires
single FL training for the selected HP 0
significantly smaller than the communication overhead of multi-shot HPO, but still higher than that of FLoRA for moderately high N.
B ADDITIONAL DISCUSSIONS ON LOSS SURFACES
Single global model (SGM). We merge all the sets E Uigin) E(1) and use it training set for a regressor f' θ - R, which considers the HPs E θ as the covariates and the corresponding loss the dependent variable. For example, we train a random forest regressor (Breiman (001)
on this training set E. Then we can define the loss surface {(0) == f(). While this loss surface is simple to obtain, it may not be able to handle Non-iid party data distribution well: it is actually overly optimistic - under the assumption that every party generates unique HPs during the local HPO, this single global loss surface would assign low loss any HP which has low loss any one of the parties. This implies that this loss surface would end up recommending HPs that have low loss in just one of the parties, but not necessarily all parties.
Single global model with uncertainty (SGM+U), Given the merged set E = Usg E we can train a regressor that provides uncertainty quantification around its predictions (such as Gaussian Process Regressor (Williams & Rasmussen 2006)) as ʃ θ + R, u: O - Rt, where s(0) is the mean prediction of the model at f E while u(6) quantifies the uncertainty around this prediction
f()). We define the loss surface as {()) == f(0) + a u(0) for some > 0. The uncertainty function u depends on the regressor used model the loss surface. Gaussian Process Regressors naturally provide uncertainty estimates for predictions. For Random Forest Regressors, uncertainty estimates for predictions have been generated based on the variance the individual tree predictions in the Random Forest, and we use this in our experiments. For all our experiments, that we are considering a loss value that is a single standard deviation away from the predicted loss.
1, implies
This loss surface does prefer HPs that have a low loss even in just one of the parties, but it penalizes HP the model estimates high uncertainty around this HP. Usually, a high uncertainty around a HP would be either because the training set E does not have many samples around this HP (implying that many parties did not view the region containing this HP as one with low loss), or because there multiple samples in the region around this HP but parties do not collectively agree that this is promising region for HPs. Hence this makes SGM+U more desirable than SGM, giving us a loss surface that estimates low loss for HPs that are simultaneously thought be promising to multiple parties.
Maximum of per-party local models (MPLM). We can train one regressor f()) + RR [p]
with each of the per-party set E(), Given this, we can construct the loss surface as ( maXie(r) (*) This can be seen as much more pessimistic loss surface, assigning a low loss to
HP only if has a low loss estimate across all parties.
Average of per-party local models (APLM). A less pessimistic version of MPLM would be to construct the loss surface as the average of the per-party regressors f()) E [p] instead of the maximum, defined as {()) 1/p ( (0). This is also less optimistic than SGM since it will assign a low loss for a HP only its average across all per-party regressors is low, which implies that all parties observed relatively low loss around this HP.
15

---

Published as a conference paper at ICLR 2023
Intuitively, believe that loss surfaces such as SGM+U or APLM would be the most promising while the extremely optimistic and pessimistic SGM and MPLM respectively would be relatively less promising, with MPLM being superior to SGM. But MPLM would also be most robust to data heterogeneity, as evidenced by our empirical evaluations.
C THEORETICAL ANALYSIS
In this section, we will provide a detailed and rigorous proof to Theorem 2.1 some notation will use throughout this section in Section C.1 and then discuss the Lipschitz smoothness assumptions (and possible relaxation) we require to obtain our optimality guarantee in Section C.2 Finally, we establish the sub-optimality of the HP selected by FLoRA in Section C.3 and a byproduct of the result in presented in Section C.4
We first formally define
C.I TECHNICAL DEFINITIONS
Definition C.1 (Loss functions). For given parties' data = (iitie and any 0 E O, the true target loss (any predictive performance metric, such the training loss) can be expressed as:
e D) =
B(z.g)-D
C A(O, D) (z. v)).
(C.1)
test perf. of trained model
trained model
Here D is the data distribution of the test set. Let ē(0, D) be estimate of the loss defined in C.. given some validation (holdout) set D' sampled from D, which is the model performance metric during evaluation and/or inference time.
We assume the parties' training sets are collected before the federated learning such that 7) is fixed and unchanged during the HPO and FL processes, order words, we do not consider streaming data/online setting.
Now we are ready to provide a more general definition the unified loss surface constructed by FLoRA as follows:
Definition C.2 (Unified loss surface). Given the local loss surfaces & θ - IR for each party E [p]
generated by 7 (HP, loss) pairs {( _c()) ]terr). and the weight vector (a .... ap) where
(0) E [0, 1]. vi E (p), Ei (0) = 1, we can define the global loss surface i θ + R as
(() 1 (0) (.)
(C.2)
In particular,
i) If (f) = 1/2, Vi E [p], 0 E θ, then this reduces to APLM loss surface.
ii) If (0) I (Z)(0)= ma (0)) then this reduces to the MPLM loss surface (as- suming all Ł, (0)s are unique).
We formalize the distance metric used our analysis to evaluate the distance between two given data distributions using I-Wasserstein distance (Villani 2021).
Definition C.3 (1- (1-Wasserstein distance Villani 2021 For two distributions with bounded support, the I-Wasserstein distance defined as
Wi (M, v) sup Ez-n (x) - Exwuf(x),
(C.3)
seF,
where F, {ff continuous, Lipschitz(f)) 17.
We now define distance metric d + + + R4 used in the rest of our analysis. Assuming we have
m HPs, if e C RT then there are various distances available such as || 0'llp (the p-norm). The more general case is where
have R continuous/real HPs, I integer HPs, and C categorical HPs; m = R + I + C. In that case, c R z x CC, and any = (0 0z, 0c) E θ x O X Oc, where f Og, R Oz Oz, Oc Oc respectively denote the continuous, integer and categorical HPs
16

---

Published as a conference paper at ICLR 2023
in 0. Distances over IR x Z is available, such as p-norm. Let d2,z (@* 22) (O2 (2) + R+
be some such distance. To define distances over categorical spaces, there are some techniques such as one described by Oh et al. (2019)
Assume that each of the C' HPs Oz.k, k E [C] have nu categories (Éx1, Ek2........... Ekn, Then we define complete undirected graph G+= (Vk, E&), E [C] where
There is a node NEj in Gk for each category Exj for each j E [nt]] and Vi (N Neng..
There is an undirected edge (Nuj. Ney.) for each pair j,j E [n*] and Ex {(Nej, Nup)), E [nu]].
Given the per-categorical HP graph Gk. k E [O], we define the graph Cartesian product G 8 OkELoy G3 and G = EV, such that
V = {N (isdemne)))))
Ekfa.......e Oc. E [R E [C]}.
E {(N (NN de) N (())))))))))) : IFF3t E
[C] such that Wk + t. Ekju
Skyg and 3(Neje Noz)) E.J.
Then for any Oc, 0'c E Og with corresponding nodes N' E V, (O et al.
2019 Theorem 1)
says that the length of the shortest path between nodes N and N' in G is distance. We can consider this distance as de Ø x Or + R,. Of course, there are other ways of defining distances in the categorical space.
Then we can define distance d (Ox Oz x Oc) x (OR Oz x Oc) > IR,, between two HPs 0, 0' as
d(0, 0') = dR (0p, Oz), (Og. 02)) + de (0c, 0'c).
(C.4)
Proposition C.4. Given distance metrics dR,2 and de, the function d A x O defined in CC.4 is valid distance metric.
C.2 LIPSCHITZ CONTINUITY ASSUMPTIONS
To facilitate our analysis later, we make the following Lipschitz smoothness assumptions regarding the loss function É and also the per-party loss surface L, Assumption C.5 (Lipschitz smoothness). For fixed data distribution and V0, 0' E e C O we have
Ê( () - ((0'')))) < ((D)-d(0,0')
(C.5)
(²,(0) -,(00) < L, d(),0')
(C.6)
where d(.,)) is the distance metric (see C.4) )) defined over the hyper-paramett search space For
fixed set of hyper-parameters 0 + + and some data distributions D and D', we have
i, 0 D') < 3()) (D,,D')
(C.7)
Remark. Note that we explicitly use θ C θ to highlight that we need Lipschitz smoothness only some particular parts the HP space. In fact, our analysis only requires the Lipschitz smoothness at 0 (HP selected by FLoRA), 0" (the optimal HP) and a HP space containing the aforementioned two HPs and the set of HPs tried in local HPO runs, i.c., (0( ).E(T)- which most of the time much smaller than the entire HP search space. Moreover, the above Lipschitz smoothness assumption w.r.t. a general HP space, which could be a combination continuous and discrete variables, may be strong. We will show later in this section that it can be relaxed to milder assumption based on the modulus continuity without significantly affecting our main results. For simplicity, we can always assume that T.(D) S T., YD and ((0) S 3, VO.
*
For more general handling, we can consider the notion of modulus of continuity in the form of increasing real-valued functions w : R4 + R4, with lim;- wt) = w()) = 0. Then we can say that the estimated loss ε(0 D) and the loss surface (0) admits Wp and as a modulus of continuity (respectively) if
17

---

Published as a conference paper at ICLR 2023
|e(0, D) ()) @p(d(0,6)) 8)) (?((0) -())))((00)) (0)) @d (0)))))))
(C.8)
(C.9)
we further assume that Wp, @ to be concave, then we can say that these functions are sublinear as follows:
(t(t)= S Ap + BD, (()) S A. + B.
(C.10)
(C.11)
These conditions give (indirectly) something similar in spirit to the guarantees of Lipschitz continuity, but is more rigorous way achieving such guarantees.
C.3 PROOF TO THEOREM
In this section, we provide detailed proofs the result stated in Theorem 2.1 in Section 2.3
We are interested in providing a bound for the optimality gap defined in 2.8 we restate as following
g = 1(0 D) E(0", D),
where
0' arg min E D).
(C.12)
mE
Note that this bound is the optimality gap for the output of FLoRA in terms of the estimated loss غ. We (re)state our main results in the following theorem (in a more precise manner than Theorem 2.1).
Theorem C.6. Consider the optimality gap defined in 2.8 where Ø is selected by FLoRA with each party i [p] collecting T (HP, loss) pairs {((( c! DEe(T) during the local HPO run. For desired data distribution D Ei=1 W;D,, where (Di)eel) are the sets of parties' local data distributions and w, [0, 1], E [p), we have
g S 2 max ax OEG
"3 + (i(D.) + L.)
min d(O 0 + +5,1 1E(2
(C.13)
where 5g is the maximum per sample training error for the local loss surface E, i.e., 6. max, | (.( ). In particular, when all parties have i.i.d. local data distributions, C.I3)
reduces
{ (I(D.) + +Li) min d(0, (00) + +. a:
S max BEG
rE(T)
We quantify the relationship between (0) and the estimated loss function ē(0, D.) follows: (Z,(0) ē D.) (0.T".
(C.14)
Proposition C.7. Consider O- and 0* are two of HP defined in 2.7 and (C.12) respectively, and {D. and D are the sets of parties' local data distributions and the target (global) data
distribution we want to learn, for a given HP space such that Ø* , E c O, we have
i(0" D) E(0", D) < 2 max
{ (D + (
(C.15)
Proof. Consider the definition of 0" and 0*, we can obtain
?0 D) (('"')) = i D) ?00) 70') + ;(0'
(( 100)
< 2 max ocèce
18

---

Published as a conference paper at ICLR 2023
where the inequality follows from the fact that ?(0') ?(0)) 0. Moreover, observe that for any
c θ by the definition of (() in C.2)) we have
(( D) - [00) - ((0,D) - Li (1((0) (0)(0) 20)
((0,D) -.1
(
a ((),D.)) - aa [0(
$ 2i ((0, D) - i(0, D:) + ai ((,. 2.(
Liepp (0) D,) (0)
where the last inequality follows from assumption
(C.7 and definition (C.14).
We now dive into each term in (C.15) to provide tight bounds for (I(D,)) and (0, in the following propositions.
Proposition C.8. Consider J-Wasserstein distance defined (C. for local data distribution DD of any party i, i E [p), and = Di= for some w; E [0, 1J, vi E [p), we have
WiDD, S EzEloss4: WDD
(C.16)
In particular, when D;, E (p] are i.idd data distribution, i.e., all parties federated learn- ing system possess i.i.d. local data distribution that is, (D, Di) = Ovi,j E [p] -then "1 D.) Therefore, Wi(D. (.) vi pl.
Proof. By the definition of 1- Wasserstein distance in (C.3 and the fact that D Eiely WiD,, obtain
Wi D.) sup ((2,))~D (1r v) E (a.,))) (3i,
SEFi
sup Σje wy wy f( M3) (e,,)) fla,
fEF,
sup Σ Eitsje My (E( (1,, Wj) 1l0--EE-eee B(D. (wi,
feFi
EMAdeM w/ (sup/EFi E f(z, - BL
< E E WD D:).
Proposition C.9. For any party i, i E [p), consider a (HP, loss) pair (0!", c()) collected during the local HPO run for party i, for any 0 E C. O we have
c(0,T)= = (L(D.) + La
min d(0 (0)) + 8 EE
(C.17)
where 6; = maxt (c - (0) is the maximum per sample training error for the local loss surface
Proof. By the definition of (0,T))
(0,T) (((,D.)) D.) 2,(00)
(1) D.)
2.(00 2(00
2,(0)
Smoothness of
Modeling
Smoothness of F
where 0,0, E [7] any of the HP tried during local HPO party i [p].
19

---

Published as a conference paper at ICLR 2023
First note that
|²(0,") D.) - -1(00))1=
= =-- - )0
S maxx |c, [((0 s 8,
In view of (C.5) and C.7 we have
(0, S L(D.)d(0,0))) + + L,d(0,
which immediately implies the result in (C.17)
In view of the results established in Proposition
C.7
C.9
we immediately obtain the optimality
guarantee presented in Theorem C.6 (also Theorem
The following proposition characterizes c (0, T) when we relax the Lipschitz continuity assumption with respect to the HP space 0 (required by Proposition C.9 to only modulus continuity defined at the end of Section C.2
Proposition C.10. Assume that the estimated loss ε(O, D:) and the loss surface (0) admit concave functions WD, and Wi respectively
modulus of continuity with respect to O E f each party
i [p]. Then, for any party i, E [p], with the set of (HP, loss) pairs {10() Li )eEm collected during the local HPO run for party i, for any O E @ C O. there exists AD,, A.. BD, B, 2 0 such that
((0,T) - (Av. + A1)
min d(e, (() + BD, + B + 8, KETT
(C.18)
where o; = max, |C ((((()) | is the maximum per sample training error for the local loss surface C,
Proof.
By the definition of (T,
c;(,,T) = ((0, D;) - [0)
= - - Dz) +
- ) 200)
Smoothness of
Modeling error
Smoothness
where 0 e [I'] is any one of the HP tried during local HPO run on party E [p].
First note that
? ,D) - 2((()) |c - (0())
S max |c - (
s 6,.
In view of (C.8) and (C.9. have
(0,T) S wD, (d(O, + 6, - +(((0000000)
@d(( (D. (d(e) . + 1))
< 6 + min
rE[T]
Concavity of a function w [0, xo| + [0, oo| implies that there exists A, B > such that w(t) < Al + B. Using that, we can find some AD, A,, BD, B, > 0 which allows us simplify the above
to
GO 5 5 (ÅD. + A) min d(0,0)") + (Bp, + B).
[E[7]
20

---

Published as a conference paper at ICLR 2023
C.4 RELATIVE REGRETS
As byproduct, we can also provide a bound for the following relative regret we use in our experi- ments.
Corollary C.11. Let us assume Ø and 0 are defined in (.7 and (C12). and 0' and 0, are the hyper-parameter settings selected by centralized HPO and some baseline hyper-parameters. respectively, then we can bound the relative regret as follows, for a given data distribution DD we have
E(O", D) -(000
e(0", D) ((0b. D)
2 max Ei=1 (;( " + (L(D.) + -2,) min d(0, (0) + 8; ME
{(,,, D) E(00, D)
(C.19)
Proof. By the definition of relative regret, we have
i(0", D) i(0", (D) f(0", D) D)
10 D) - ((0' D) (()..)) - -(0"
i D) (()"
(0.. D) (()"
where the last inequality follows from the fact that 0" is the minimizer of Ê(0, D). Moreover, in view of the result in Theorem C.6 the result (C.19) follows.
C.5 QUANTIFYING DATA HETEROGEEEITY IN FL-HPO
As defined in utilize %p surrogate to quantify the heterogeneity between the per-party data distributions. Here we will motivate this choice. By definition
(
1 min [ C
7
max4epp min [(0)
min
where
7 : arg min min C and <E(pl [E[2]
7:= arg max min c
min
re(pl rE[T]
mintely
C
+ min.e(T)
min E
- mingerr]
=1 mineery C
min c
1 min c.
0 D.) i(0 Dz)
where 1 .00 are the best HPs parties 7, resp.
+
1 min,g(7] 2.00
=1 0 D2) ((0 D2) + ( D.) 2(0 Dz)
min C.
8 wi (D; Dr) < 1
3 max WI Dj) 100
11 +
max W WI D,)
1- min
c(
min (
i.EEpp)
This implies that Yp is closely tied to the maximum I-Wassertein distance between any pair of per-party distributions.
21

---

Published as a conference paper at ICLR 2023
D EXPERIMENTAL SETTING
D.1 DATASET DETAILS
For our evaluation of single-shot HPO, we consider binary classification datasets varying sizes and characteristics from OpenML (Vanschoren et al. 2013) such that there is least significant room for improvement over the single-shot baseline performance. We consider datasets which have least 3% potential improvement in balanced accuracy for gradient boosted decision trees. Note that this only ensures room for improvement for HGB, while highlighting cases with no room for improvement for SVM and MLP as we see in our results.
The details of the binary classification datasets used in our evaluation is reported in Table 6 We report the 10-fold valldaaald balanced accuracy of the default HP configuration on each of datasets with centralized training. The "Gap" column for the results for all datasets and models in $D3 denote the difference between the best 10-fold cross-vale validated balanced accuracy obtained via centralized HPO and the 10-fold cross-validated balanced accuracy of the default HP configuration.
Table 6: OpenML binary classification dataset details
Index
Data
columns
class sizes
DI
EEG eye state
14980
14
(8257, 6723)
D2
Electricity
45312
(26075, 19237)
D3
Heart statlog
270
13
(150, 120)
Oil spill
937
49
(896, 41)
D5
Pollen
3848
(1924, 1924)
D6
Sonar
208
61
(111, 97)
D7
PC3
1563
37
(1403, 160)
D.2
SEARCH SPACE
We use the search space definition used in the NeurIPS 2020 Black-box optimization challenge (https:/ (tttps:://bbcchallengg... com/), described in details in the API documentation
D.2.1
HISTOGRAM BASED GRADIENT BOOSTED TREES
Given this format for defining the HPO search space, we utilize the following precise search space for the wettrraaienttoossinnnl..eec fier in scikit-learn:
api_config
tmax_iter's ("type": "int", "space": "linear", "range": (10, 200) "learning_rate", ("type": "real", "space": "log", "range": (le-3, 1.0)), "min "min_samples__edt ("type": "int", "space": "linear", "range": (1, 40)), "12 reguragaaiii ("type": "real", "space"; "log", "range": (le-4, 1.0)),
The HP configuration we consider for the single-shot baseline described in 3 as follows:
config
"max_iter": 100,
"learning_rate rate": 0.1,
"min sat__sampess_eeeee leaf": 20, "12 #12_regularizationn: 0,
D.2.2 KERNEL SVM WITH RBF KERNEL
For SVC (kernel= "rbf") scikit- we use the following search space:
https://github. http:///gghhoo.ccooooootmmmemmm http://turrreett//bbbb/bbebbb/aa 1/bbo_cha waachaallengeessaarrrrae starter_kit. icon firrttigaaiiioo space
22

---

Published as a conference paper at ICLR 2023
api config "c": ("type": "real", "space"; "log", "range"; (0.01, 1000.00
"gamma": :"type"; "real", "space": "log", "range"; (1e-5, 10. b
"tol": {"type": "real", "space"; "log", "range"; (1c-5, 1e-1)
The single shot baseline we consider for SVC from Auto-sklearn (Feurer et al. 2013) is:
config "C": 1.0, "gamma": 0.1, "tol": 10-3,
D.2.3 MULTI-LAYERED PERCEPTRONS
For the MLPClasS fier (solver=aadd from tectural HP such as pandddn-layer-ssee as well as optimizer parameters such as alpha and learning-rate- for the Adam optimizer (Kingma Ba 2015). We consider the following search space:
we consider both archi-
api _oi__onfig
("type": "int", "space": "linear", "range": (50, 2001), "alpha": {"type": "real", "space": "log", "range": (le-5, lel) "Learning rate init": ("type": "real", "space": "log", "range": (le-5, 1e-1))
We utilize the following single shot baseline:
config
Leaddn__lyye___e layer_sizes, 100, "aapha": 1e-4, Bearriin_rate_inite 1e-3,
"hidden_
We fix the remaining HPs of MiClassifier as with values used by Auto-sklearn.
activation="rclu",
eazly_stopping--tuu,,
shuffle=True, batch_size="aatto"
tol=1e-4, validation_frretionn0)
beta 1=0.,,
beta 299. epsilon=le-8,
D.3 DETAILED RESULTS OF COMPARISON AGAINST BASELINES
Here present the relevant details and the performance of FLORA the FL-HPO of (i) histograms based gradient boosted trees (HGB) in Table 77 (ii) nonlinear support vector machines (SVM) in Table 8 and (iii) multi-layered perceptrons (MLP) in Table 9 We the search spaces and the single-shot baselines presented in (D.2 We utilize all 7 datasets for each of the method except for the Electricity dataset with SVM because the infeasible amount of time taken by SVM this dataset. For each setup, we report the following:
Performance of the single-shot baseline ("SSBaseline"),
the best centralized HPO performance ("Best"),
the available "Gap" for improvement,
the minimum accuracy of the best local HP across all parties "PMin" mineepi max,
f P.))
23

---

Published as a conference paper at ICLR 2023
the maximum accuracy of the best local HP across all parties "PMax" == maxielp max; (1
e( D:))
= PMax/PMin,, and finally
the regret for each of the considered loss surfaces in FLoRA.
For each of the three methods, also report the aggregate performance over all considered datasets in terms of mean + standard deviation ("mean=std"), inter-quartile range ("IQR"). Wins/Ties/Lossee of FLoRA with respect to the single-shot baseline ("W/T/L"") and one-sided Wilcoxon Signed Ranked Test of statistical significance ("WSRT"") with the null hypothesis that the median of the difference between the single-shot baseline and FLoRA is positive against the alternative that the difference negative (implying FLoRA improves over the baseline). These aggregate metrics are collected in Table aolong with set of final aggregate metrics across all datasets and methods.
Table 7: HGB
Data
SSBaseline
Best
Gap
PMin
PMax
PC3
58.99
63.81
4.82
61.67
64.37
Pollen
48.86
52.21
3.35
51.83
52.64
Electricity
87.75
92.84
5.10
88.42
89.19
Sonar
87.43
91.25
3.82
83.75
88.33
Heart Statlog
79.42
85.58
6.17
78.00
86,50
Oil Spill
63.22
74.58
11.36
68.
82.16
FEG Eye State
89.96
94.66
4.70
91.80
92.29
Data
%
SGM
SGM+U
MPLM
APLM
PC3
1.04
0.66
0.72
0.39
0.38
Pollen
1.02
0.43
0.54
0.43
0.69
Electricity
1.01
0.17
0.14
0.09
0.12
Sonar
1.05
1.33
0.41
0.92
0.71
Heart Statlog
1.11
0.69
0.55
0.89
0.50
Oil Spill
1.21
0.47
1.13
0.46
0.61
EEG Eye State
1.01
0.14
0.12
0.11
0.12
meantsstd
0,56 + 0.37
0.52 + 0.32
0.47 + 0.31
0.45 + 0.23
IQR
[0.30, 0.47, 0.68]
[0.27, 0.54, 0.64]
[0.25, 0.43, 0.67]
[0.25, 0.50, 0.65]
WTL
6/0/1
6/0/1
7/0/0
7/0/0
WSRT
(26, 0.02 126)
(27, 0.01400)
(28, 0.00898)
(28, 0.00898)
HGB. The results in Table T indicate that, almost all cases, with all loss functions, FLoRA is able to improve upon the baseline varying degrees (there is only one case where SGM performs worse than the baseline on Sonar). On average (across datasets), SGM+U, MPLM and APLM perform better than SGM standard deviation. Looking at the individual datasets, we see that, for datasets with low "p (EEG eye state, Electricity), all the proposed loss surface have low relative regret, indicating that the problem is easier as expected. For datasets with high "/p (Heart statlog, Oil spill), the relative regret of all loss surfaces are higher (but still much smaller than 1), indicating that our proposed single-shot scheme can show improvement even in cases where there is significant difference in the per-party losses (and hence datasets).
expected. MPLM performs better than SGM both in terms of average and
SVM. For SVM we continue with the datasets selected using HGB (datasets with a "Gap" of at least 3%). Of the 7 datasets (Table we skip Electricity because it takes a prohibitively long time for SVM to be trained on this dataset with a single HP. So we consider datasets in this evaluation and present the corresponding results in Table 8 Of the 6, note that of these datasets (Pollen, Heart Statlog) have really small "Gap" (highlighted in red in T). Moreover, 2 of the datasets (Heart statlog, Oil Spill) also have really high 7, indicating a high level heterogeneity between the per-party distributions (again highlighted in red). In this case, there are couple of datasets (Oil Spill and Pollen) where FLoRA is unable to show any improvement over the single-shot baseline (see underlined entries in Table 8). but both these cases either have small moderate "Gap" and/or have a high 7,. Moreover, in one case, MPLM incurs a regret of 6.8, but this is a case with really high of the parties, and in that process
Op 1.14 MPLM rejects any HP that has low score in
24

---

Published as a conference paper at ICLR 2023
Table 8: SVM
Data
SSBaseline
Best
Gap
PMin
PMax
Pollen
49.48
50.30
0.82
51.55
53,55
Sonar
80.20
89.29
9.09
83.33
87.92
Heart Statlog
83.67
84.92
1.25
77.00
88.00
Oil Spill
82.76
86.54
3.78
77.14
88,45
EEG Eye State
50.24
60.51
10.28
69.54
71.72
PC3
74.03
77.96
3.92
75.26
76.95
Data
"p
SGM
SGM+U
MPLM
APLM
Pollen
1.04
1.35
1.45
2.84
2.30
Sonar
1,06
0.17
0.17
0.27
0.17
Hcart Statlog
1.14
0.00
0,00
6,80
0.67
Oil Spill
1.15
1.28
1.16
1.12
0.41
EEG Eye State
1.03
-0.01
-0.01
-0.02
-0.01
PC3
1.02
0.59
0.79
0.70
0.79
isdd
0.56 + 0.57
0.59 + 0.58
1.95 + 2.35
0.72 + 0.76
IQR
[0.04, 0.38, 1.11]
[0.04, 0.48, 1.07]
[0.38, 0.91, 2.41]
[0.23, 0.54, 0.76]
WTL.
4/0/2
4/0/2
3/0/3
5/0/1
WSRT
(18. 0.05793)
(17, 0.08648)
(9, 0.62342)
(15, 0.17272)
reject all promising HPs since the local HPOs these disparate distributions did not concentrate the same region of the HP space, thereby incuring high MPLM loss in almost all regions the HP where some local HPO focused Other than these expected hard cases, FLoRA able improve upon the baseline in most cases, and achieve optimal performance (zero regret) in few cases (EEG Eye State, Heart Statlog).
Table 9: MLP-Adam
Data
SSBaseline
Best
Gap
PMin
PMax
Pollen
50.39
51.26
0.87
51.46
52.23
Electricity
76.95
78.06
1.11
77.01
77.39
Sonar
61.63
79.32
17.69
69.17
78.75
Heart Statlog
72.17
85.17
13.00
79.50
89,50
Oil Spill
50.00
65.22
15.22
54.83
63.63
EEG Eye State
49.99
51.66
1.67
50.02
51,84
PC3
50.00
59.56
9.56
53.47
56.60
Data
%
SGM
SGM+U
MPLM
APLM
Pollen
1.02
1.88
1.45
1.45
1.31
Electricity
1.00
0.24
0.41
0.16
0.53
Sonar
1.14
0.26
0.55
0.52
0.39
Heart Statlog
1.13
0.46
0.37
0.42
0.28
Oil Spill
1.16
0.80
1.03
1.00
0.79
EEG Eye State
1.04
0.99
0.99
0.99
0.99
PC3
1.06
0.96
1.00
0.89
0.90
istd
0,80 + 0.53
0.83 + 0.37
0.78 + 0.40 [0.47, 0.89, 1.00]
0.74 + 0.34
IQR
[0.36, 0.80, 0.97]
[0.48, 0.99, 1.01]
[0.46, 0.79, 0.95]
WTL.
6/0/1
4/1/2
5/1/1
6/0/1
WSRT
(21, 0.1 1836)
(15, 0.17272)
(18, 0.05793)
(24, 0.04548)
MLP. We consider all datasets for the evaluation of FLoRA on FL-HPO for MLP HPs and present the results in Table 9 As with SVM, there are few datasets with small room for improvement ("Gap") and/or high 7pp. again highlighted in red in Table 9 some these cases, FLoRA is unable to improve upon the single-shot baseline (Pollen, EEG Eye State). Other than these hard cases, FLoRA again able to show significant improvement over the single-shot bascline, with APLM performing the best.
25

---

Published as a conference paper at ICLR 2023
Aggregate. The results for all the methods and datasets are aggregated in Table T0 All FLORA loss surfaces show strong performance with respect to the single-shot baseline, with significantly more wins than losses, and 3rd-quartile regret values less than 1 (indicating improvement over the baseline). All FLORA loss surfaces have a p-value of less than 0.05, indicating that we can reject the null hypothesis. Overall, APLM shows the best performance over all loss surfaces, both in terms of Wins/Ties/Losses over the baseline as well as in terms of the Wilcoxon Signed Rank Test, with the highest statistic and a p-value close 10-3 3, APLM also has significantly lower 3rd-quartile than all other loss surfaces. MPLM appears to have the worst performance but much of that is attributable to the really high regret of 6.8 and 2.84 it received for SVM with Heart Statlog and Pollen (both hard cases as discussed earlier). Otherwise, MPLM performs second best both for FL-HPO with HGB and MLP.
D.4 COMMUNICATION SAVINGS OF FLoRA OVER MULTI-SHOT FL-HPO
Here we compare the communication savings one would obtaín from FLoRA relative to a multi-shot FL-HPO scheme. FLoRA is single-shot FL-HPO scheme and hence utilizes a single federated model training (Algorithm
! line 8). contrast to a single-shot solution, we can try to solve the FL-HPO problem (2.5) in manner that allows multiple federated model trainings. In that case, could utilize existing HPO schemes such a HyperOpt (Bergstra et al. 2011) for FL-HPO, where each HP proposal is evaluated with complete federated model training. While this multi-shot FL-HPO scheme would have a very high communication overhead, we expect this scheme to find HPss and corresponding models that have better predictive performance than single-shot schemes. In fact, given enough number of federated model trainings, we expect this multi-shot FL-HPO scheme to achieve 0 relative regret.
With such a baseline, we perform a comparison with FLoRA where we note the number of federated model trainings required by the multi-shot FL-HPO reach the predictive performance (in terms of the relative regret) of FLoRA. Since each federated training incurs a large amount of communication overhead, a larger number of federated model trainings imply larger communication overhead. This number of federated model training serves the multi-shot baseline to achieve the same level of performance. We present these results for FL-HPO of HGB (Figure 5). SVM (Figure 6) and MLP (Figure 77. In each of these figures, we present the communication savings for all the four different loss surfaces, and each pair of (+, connected by a dashed line corresponds to single dataset label from D1-D7. The names (and details) of the dataset corresponding to these dataset labels provided in Table
surrogate for the communication gain of FLoRA over
The results for HGB in Figure 5 indicate that, in most datasets, across all loss surfaces, FLoRA can provide almost 10x savings and upto 20 - 30 in a few cases. Overall, SGM performs the worst with
Table 10: Aggregate Table
Agg.
Method
SGM
SGM+U
MPLM
APLM
mean + std.
HGB
0.56 = 0.37
0.52 + 0.32
0.47 + 0.31
0.45 + 0.23
SVM
0.56 = 0.57
0.59 + 0.58
1.95 + 2.35
0.72 0.76
MLP
0.80 = 0.53
0.83 1 0.37
0.78 0.40
0.74 0.34
Overall
0.64 - 0.51
0.64 1 0.51
1,02 1 1.46
0.63 1 0.50
IQR
HGB
10.30, 0.47, 0.68)
[0.27, 0.54, 0.64]
[0.25, 0.43, 0.67] [0.38, 0.91, 2.41]
[0.25, 0.50, 0.65]
SVM
[0.04, 0.38, 1.11]
[0.04, 0.48, 1.07]
[0.23, 0.54, 0.76]
MLP
[0.36, 0.80, 0.97]
[0.48, 0.99, 1.01]
[0.47, 0.89, 1.00]
[0.46, 0.79, 0.95]
Overall
[0.22, 0.53, 0.97]
[0.32, 0.55, 1.01]
[0.36, 0.61, 0.99]
[0.36, 0.57, 0.79]
W/T/L
HGB
6/0/1
6/0/1
7/0/0
7/0/0
SVM
4/0/2
4/0/2
3/0/3
5/0/1
MLP
6/0/1
4/1/2
5/1/1
6/0/1
Overall
16/0/4
14/1/5
15/1/4
18/0/2
WSRT sided
HGB
(26, 0.02126)
(27, 0.01400)
(28, 0.00898)
(28, 0.00898)
SVM
(18. 0.05793)
(17. 0.08648)
(9. 0.62342)
(15, 0. 07172
MLP
(21. 0.1 1836)
(15, 0.17272)
(18, 0.05793)
(24, 0.04548)
Overall
(174, 0.00499)
(164, 0.00272)
(141. 0.03206)
(183.5, 0.00169)
26

---

Published as a conference paper at ICLR 2023
HGB
MPLM
Soge harthraa TUBAA
Relative Regret
01
p
01
32
100
Federated Model Train ngs
Figure 5: Communication overhead of multi-shot HPO compared to FLoRA to match the relative regret of FLoRA for FL-HPO with Histogram based Gradient Boosted Decision Trees (HGB). The dataset indices are based on the Table 6
a inter-quartile range (IQR) of 3.5 8.5x savings. SGM+U improves over provide a savings IQR of 5.5 16x, while MPLM and APLM provide savings IQR of 3.5 18.5x and 3.5 16x respectively.
SGM
SGM-U
SVM
MPLM
APLM
Sinc diet baceiie
Relative Regret
bassline
00
300
# Federated Model Trainings
Figure 6: Communication overhead of multi-shot HPO compared to FLoRA to match the relative regret of FLoRA for FL-HPO with Support Vector Machines (SVM). The dataset indices are based on the 6
The results for SVM in Figure indicate that the communication savings of FLoRA are much more spread out. Note that, as mentioned Appendix D.3] Electricity dataset (D2) not considered in the SVM FL-HPO since it takes prohibitively long to execute the centralized HPO. Furthermore, we have also excluded the datasets in each plot where the relative regret for FLoRA is greater than 1 (see Table
8h since in that case. FLoRA is not even able to improve upon the single-shot baseline. There are more cases in this set of results where the savings from FLoRA are less than 10x, but there also cases where FLoRA provides close to 100x savings. Overall, APLM provides the most robust performance in terms of savings with savings IQR of 7.25 29.75x, while MPLM provides the worst performance with savings IQR of 1.75 9.75x. SGM and SGM+U provide similar wide-ranging savings IQR of 2.25 80x.
MLP
MPI
DN
terreie "LatA
Relative Regret
nr.
Federated Model Trainings
Figure 7: Communication overhead of multi-shot HPO compared to FLoRA to match the relative
regret of FLoRA for FL-HPO with Multi-layered Perceptrons (MLP). The dataset indices are based on the Table 6
27

---

Published as a conference paper at ICLR 2023
Table 11: Effect of increasing number parties on FLoRA with loss surfaces for HGB.
Data
p
"p
SGM
SGM+U
MPLM
APLM
EEG Eye State
3
1.01
0.14
0.12
0.11
0.12
14980 samples
6
1.01
0.07
0.00
0.07
0.09
10
1.03
0.08
0.00
0.16
0.01
25
1.08
0.35
0.92
0.17
0.04
50
1.20
0.20
0.23
0.67
0.12
Electricity 45312 samples
3
0.17
0.14
0.09
0.12
6
1.01
0.25
0.21
0.18
0.13
10
1.02
0.03
0.06
0.32
0.14
25
1.04
0.40
0,42
1.42
0.89
50
1.07
1.57
1.57
0.89
100
1.14
1.45
1.47
0.48
1.11
Pollen
3
1.02
0.43
0.54
0.43
0.69
3848 samples
6
1.10
1.02
0.91
0.54
0.56
10
1.16
1.05
0.73
0.75
1.12
The results for MLP are presented in Figure 7 In this case, the communication savings from FLoRA again range from less than 10x to over 90x. APLM again provides the most robust performance with savings IQR of 5.5 16x. SGM+U and MPLM have the same savings IQR of 13x. SGM has the most wide-ranging savings IQR
33x.
Overall, the results across all loss surfaces, datasets and ML models indicate that FLoRA with any loss surface leads to a significant communication savings over multi-shot FL-HPO. Among the loss surfaces, APLM provides of the best savings among the loss surfaces, while being the most robust across MI. models and datasets. SGM+U also provides better savings than SGM. MPLM has the least favorable savings because of its pessimism. However, shown in other experiments, MPLM able to provide strong performance relative to the remaining loss surfaces especially when the FL-HPO problem is especially challenging (as with the case of increasing number of parties discussed in Appendix D.5 or the non-IID-ness of the per-party data distribution highlighted in Appendix D.8).
D.5 EFFECT OF INCREASING THE NUMBER PARTIES
We now study the effect of increasing the number of parties in the FL-HPO problem on training HGB model on 3 datasets. For each data set, we increase the number of parties p up until each party has at least 100 training samples. We present the relative regrets for all the loss surfaces in Table 11 (A complete version of Table in Section 3). It also displays 7pp := (1-minuejal < (/11/mxxee c:0)
where c( min L," is the minimum loss observed during the local asynchronous HPO at party i. This ratio "pp is always greater than 1, and highlights the difference in the observed performances across the parties. A ratio closer to indicates that all the parties have relatively similar performances on their respective training data, while ratio much higher than indicating significant discrepancy between the per-party performances, implicitly indicating the difference in the per-party data distributions.
We notice that increasing the number of parties does not have a significant effect on %p for the Electricity dataset until = 100, but significantly increases for the Pollen dataset earlier (making the problem harder). For the EEG eye state, the increase "p with increasing p moderate until 50. The results indicate that, with low or moderate increase in "p (EEG eye state, Electricity for moderate p), the proposed scheme is able to achieve low relative regret - the increase in the number of parties does not directly imply degradation in performance. However, with significant increase in " (Pollen, Electricity with 50, 100 and EEG Eye State with p = 50), we see a significant increase in the relative regret (eventually going over I in few cases). In this challenging case, MPLM (the most pessimistic loss function) has the most graceful degradation in relative regret compared to the remaining loss surfaces.
28

---

Published as a conference paper at ICLR 2023
Table 12: Effect of
Method
data
T
Pp
SGM
SGM+U
MPLM
APLM
MLP
Heart Statlog
1.13
0.58
0.33
0.22
0.56
10
1.13
0.33
0.16
0.60
0.39
1.13
0.49
0.15
0.24
0.44
1.13
0.44
0.30
0.42
0.29
60
1.13
0.37
0.15
0.33
0.22
80
1.13
0.35
0.40
0.35
0.26
MLP
Sonar
1.14
0.38
0.38
0,51
0.78
10
1.14
0.45
0.23
0.43
0.62
20
1.14
0.39
0.24
0.36
0.30
1.14
0.23
0.37
0.65
0.49
60
1.14
0.53
0.14
0.34
0.48
80
1.14
0.46
0.07
0.19
0.30
SVM
Sonar
1.06
0.17
0.17
1.16
0.28
10
1.06
0.17
0.43
0.34
0.27
20
1.06
0.17
0.17
0.17
0.17
0.17
0.17
0.22
0.27
1.06
0.17
0.17
0.17
0.17
80
1.06
0.17
0.11
0.27
0.17
SVM
EEG
1.03
-0.01
00.11
0.92
0.16
10
1.03
-0.01
-0.01
-0.01
0.14
20
1.03
-0.01
-0.01
-0.00
-0.00
-0.02
-0.02
0.01
0.00
1.03
-0.01
-0.01
0.02
0.03
80
1.03
-0.01
-0.01
0.01
-0.0*
D.6 EFFECT OF THE NUMBER OF LOCAL. HPO ROUNDS PER PARTY
In this experiment, report additional results study the effect of the "thoroughness" of the local HPO runs (in terms of the number of HPO rounds 7' on the overall performance FLoRA for all the loss surfaces in Table 12 In almost all cases, FLoRA does require T be too large get enough information about the local HPO loss surface to get to its best possible performance.
D.7 EFFECT OF COMMUNICATION OVERHEAD
While in the previous experiment, we studied the effect of the thoroughness of the local HPO runs on the performance of FLoRA, here we consider a subtly different setup. We assume that each party performs 7' = 100 rounds of local asynchronous HPO. However, instead of sending all T (HP, loss) pairs, we consider sending T' lowest losses. Changing the value of 7" trades off the communication overhead of the FLoRA step where the aggregators collect the per-party loss pairs (Algorithm [ line 5). We consider datasets each for 2 of the methods (SVM, MLP) and all the loss surfaces for FLoRA, and report all the results Table
of the "best" (HP, loss) pairs - that is, (HP, loss) pairs with the T
D.8 EFFECT OF NON-IID PARTY DATA DISTRIBUTION
In this section, we simulate different degree of non-iidness for parties' local data distribution based on MNIST datase In particular, for "imbl" there are parties in total, half of the parties (with times more probability to) have more even digits while the other half have more odd digits. In "imb2" case, parties' local data distributions are more heterogeneous, as there with first 3 parties having distinguish class labels and the last parties have the rest class labels, i.e. each party only accesses unique subset class labels. For both simulated imbalanced datasets, all parties have 500 training images and 2500 testing images. We use again balanced accuracy as the target performance metric, and relative regret as the metric to measure the performance of FLoRA.
4 parties in the FL system
We download MNIST dataset from http://yann. 1ecun www.n.coo/eee. www.////ww///mnccoo
29

---

Published as a conference paper at ICLR 2023
Table 13: Effect of the number of best (HP, loss) pairs T" T sent to aggregator by each party after doing local HPO with 7 = 100.
Method
data
T" < T
SGM
SGM+U
MPLM
APLM
MLP
Heart Statlog
1.13
0.33
0.27
0.38
0.71
10
1.13
0.35
0.31
0.33
1.72
20
1.13
0.42
0.39
2.02
0.55
40
1.13
0.34
0.44
0.88
0.51
1.13
0.38
0.22
0.31
0.32
80
1.13
0.34
0.38
0.22
0.33
MLP
Sonar
0.39
0.50
1.78
0.65
10
1.14
0.73
0.18
1.66
0.58
20
1.14
0.20
0.41
1.23
0.37
40
1.14
0.60
0.42
0.18
0.51
1.14
0.10
0.33
0.55
0.26
1.14
0.47
0.41
0.34
0.32
SVM
EEG Eye State
-0.02
-0.01
0.39
1.03
-0.01
-0.01
1.02
1.02
20
1.03
-0.01
-0.01
0.01
-0.01
40
1.03
-0.01
-0.01
-0.00
-0.01
60
1.03
-0.01
-0.01
-0.01
-0.01
-0.01
-0.01
-0.01
-0.01
SVM
Sonar
1.06
0.17
0.17
0.43
1.43
1.06
0.17
0.17
0.17
0.17
20
1.06
0.17
0.17
0.22
0.17
40
1.06
0.17
0.38
0.27
0.17
60
1.06
0.17
0.43
0.27
0.17
0.17
0.43
0.27
0.17
Table 14: Effect of Non-iidness among parties' local data distribution.
Method
data
Tp
SGM
SGM+U
MPLM
APLM
MLP
MNIST-imbl
1.01
0.85
0.56
0.29
0.06
MLP
MNIST-imb2
1.03
20.63
1.53
0.71
1.10
SVM
MNIST-imbl
1.01
0.01
0.02
0.01
0.02
HGB
MNIST-imbl
1.01
0.51
0.92
0.64
0.51
We summarize the results in Table 14 First of all, FLoRA can improve over the baseline HPs in all imbalance scenarios for both MLP and SVM models. Secondly, we can see that overall MPLM (the most pessimistic loss surface) is the most robust loss surface which can always obtain improvements over the baseline HPs for all scenarios. More specifically, when the degree of non-iidness mild the baseline HPs. In "imb2" case when the degree
("imb1" case), all loss surfaces of non-iidness is more intense, we can see that the performance of FLoRA with SGM loss surface drops significantly. This also supported by our intuitions and theoretical analysis.
improve
D.9 FEDERATED LEARNING TESTBED EVALUATION
We now conduct experiments for histrogram boosted tree model in a FL testbed, utilizing IBM FL library (Ludwig et al. 2020 Ong et al. 2020), More specifically, we reserved 40% of oil spill and electricity and 20% of EEG eye state global hold-out set only for evaluating the final FL model performance. Each party randomly sampled from the rest the original dataset to obtain their own training dataset. We the same HP search space in Appendix D.2 We report the balanced accuracy of any HP (baseline or recommended by FLoRA) on a single train/test split. Given balanced accuracy the evaluation metrie, utilize (1 balanced accuracy) the loss C in Algorithm | Each party will run HPO to generate 500 (HP, loss) pairs and use those pairs to generate loss surface either collaboratively by their according different aggregation procedures described
30

---

Published as a conference paper at ICLR 2023
Table 15: Performance of FLoRA with the IBM-FL system in terms the balanced accuracy on a holdout test set (higher is better). The baseline is still the default HP configuration of
in scikit-learn.
Data
parties
# training data per party
Baseline
SOM
SGM+U
MPLM
APLM
Oil spill
200
0.5895
0.7374
0.5909
0.7061
0.7332
EEG eye state
3, 000
0.8864
0.9153
0.9211
0.9251
0.9245
Electricity
4, 000
0.8448
0.8562
0.8627
0.8621
0.8624
Once the loss surface is generated, the aggregator uses Hyperopt (Bergstra al. 2011 to select the best HP candidate and train a federated XGBoost model via the IBM FL library using the selected HPs. Table 15 summarizes the experimental results for 3 datasets, indicating that FLoRA can significantly improve over the baseline in IBM FL. testbed.
in 2.2
31


Reviews:
[{"review_id": "_gfu87sDqIY", "reviewer": "Reviewer_rh1d", "summary": "", "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": "", "summary_of_the_paper": "Authors address the problem of hyper-parameter optimization (HPO) for federated learning (FL-HPO). Authors propose FLoRA, which (1) enables one-shot FL-HPO: identifying a single set of good hyper-parameters in a single FL training, (2) can be applied to tabular data and any machine learning models. FLoRA is mainly composed of (1) locally hyper-parameter optimization on each client (2) aggregate local hyperparameter into a global loss surface. Authors theoretically characterize the optimality gap of FLoRA for any convex and non-convex loss functions, which explicitly accounts for the heterogeneous nature of the parties’ local data distributions. Authors use  default HP configuration of scikit-learn as the single-shot baseline. Compared with such a baseline, FLoRA shows significant improvement in final accuracy in several datasets and models. Authors further shows their method achieve significant communication savings compared with multi-shot HPO.\n", "summary_of_the_review": "I recommend weak accept of this paper. I must say I am not very familiar with FL-HPO and its related literature. I think the overall paper is well written and the proposed method is novel and effective. The only major concern is about the main baseline choice, which might be replaced with other one shot FL-HPO.  ", "strength_and_weaknesses": "Strength:\n\n1: The paper is well motivated. As stated by authors, FL-HPO is very important due to unavailability of global data and limitations on communication and computation budget.\n\n2: The proposed method focuses on general one-shot FL-HPO, which is very challenging and useful. Authors utilize fully independent local HPO and aggregate them into a global loss surface, which is a very novel idea. Further, authors propose several regressor methods to constrict such a loss surface.\n\n3: Authors provide a thorough theoretical analysis on the proposed method. \n\n4: Authors perform extensive experiments on different proposed methods on different models and tasks. In all experiments, the proposed method seems to be better than the baseline.\n\nWeakness:\n\n1: The major concern is that the main baseline, which is simply the default HP configuration in certain package, might not be a strong enough baseline. First of all, such baseline will not adjust HP based on current tasks and datasets (it is more like a zero-shot HPO baseline). I would suggest find other one-shot HPO methods or communication-restricted multi-shot HPO as main baseline, if it is possible. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YECiayOxg-", "reviewer": "Reviewer_mUdQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "This paper focuses on hyper-parameter optimization for the federated learning (FL- HPO) problem which is important because the choice of the HPs can have a dramatic impact on the performance. However, there are still some challenges in this area, including the unavailability of the whole dataset, high communication costs, and no FL-HPO approach dealing with a non-neural network. In this case, the author put forward a general algorithm called FLoRA which can train both neural networks and non-neural networks in a single-shot way so that the number of communication rounds is highly saved. The single-shot method is to use different HPs in each client and calculates the loss, forming (HP, loss) pairs. Then, the center collects all (HP, loss) pairs from all clients and generates a loss surface using these data so that the best model can be selected. Moreover, how to generate loss surfaces is also discussed in detail, including SGM, SGM+U, APLM, and MPLM whose performances are also compared in the experiment.", "summary_of_the_review": "Overall, this paper provides a neat method with good explanations and some theoretical justifications. The experiments seem to support the proposed method. I tend to weakly accept this paper given some concerns above and my low confidence score. However, I am happy to adjust my scores based on other reviewers’ comments and the authors’ response. ", "strength_and_weaknesses": "Pros: \n1. The studies problem is very important because hyperparameter tuning for federated learning under some privacy considerations and distributed nature turns out to be not trivial. The theory is a good plus with milder assumptions and higher generality. \n\n2. It is a general method that can be used in any ML model and the tabular data can also be trained, which is a great expansion in FL-HPO. The number of communication rounds is small since it utilizes a single-shot way that all the (HP, loss) pairs are transferred at a time.  \n\n3. The article is logical and most parts are clearly explained. The proposed algorithm (combined with some popular solvers like Bayesian Optimization) is reasonable and seems to work well given the results in the experiments.  \n\nCons: \n\n1. Some parts can be more clearer. For example, on page 6, what is the uncertainty function $u(\\theta)$, and how to choose the regularization parameter $\\alpha$ ?\n\n2. One key step in my opinion is the regression step to find the mapping f from HP to loss, i.e., line 6. This provides a possibility to reduce the communication rounds because the form of the regressor f is explicitly obtained. However, how does this regression step performs? Is it a linear regression or more complicated processes? How about the computational overhead of this process? I may miss something here, but I wish a clarification here. \n\n3. Figure 4 is a good visualization of the idea, which can be put in a more conspicuous way so that readers can understand it more rapidly.\n\n4. The authors mention that the considered setting has an asynchronous HPOS, but it seems to me that Federated Learning often follows a synchronized nature. Can the authors elaborate this a little bit? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SaLwBy6zyAp", "reviewer": "Reviewer_4yTc", "summary": "", "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": "", "summary_of_the_paper": "The paper proposes a method for tuning the hyperparameters of ML models in the federated setting which only requires a single round of communication. The proposed method is general-purpose since it can be applied to tune the hyperparameters of any ML model, not only neural networks as in some of the previous works. The proposed method firstly lets every agent run local hyperparameter optimization, and then collect all hyperparameters from all agents to fit a loss function, which is then minimized to select the final hyperparameters.", "summary_of_the_review": "The method of this paper is well motivated, but I have many major concerns regarding the method and the empirical evaluations. I've listed my concerns under \"Weaknesses\" above, the first 5 points under \"Weaknesses\" are my most important concerns.", "strength_and_weaknesses": "Strengths:\n- The studied problem, i.e., hyperparameter tuning in the federated setting, is highly relevant.\n- The single-shot nature of the proposed method is particularly desirable, since previous methods usually require a lot of additional communication rounds.\n- Some of the theoretical insights in Section 2.3 are very interesting, such as those which show the dependence of the optimality gap on the data heterogeneity and the quality of the local HP optimizations.\n\nWeaknesses:\n- The proposed method does not allow tuning per-party local HPs (paragraph above equation 2.5), I think this may be a limitation of the proposed method, since due to the heterogeneity of the agents, the best HPs for different agents are highly likely to be different.\n- The proposed algorithm (Algorithm 1) requires every agent to pass the raw HP observations to the central server, but wouldn't this lead to concerns regarding privacy? An important principle in FL is that the raw data of an agent can never be passed, and previous papers (see paper [1] below) have pointed out that the hyperparameters of an ML model can indeed contain sensitive information.      \n[1] Differentially private Bayesian optimization, ICML 2015.\n- In the experiments, the proposed method is only compared with a very weak baseline which simply uses the default HP from the package (it is not even optimized by any algorithm). I understand that most of the previous works on FL-HPO may not be comparable, but I think the proposed algorithm should have been compared with more competitive baselines. For example, a natural baseline I can think of is that after collecting all HP observations from all agents, you can simply return the HP that gives the lowest loss (among all HP observations from all agents). I think this makes sense because the loss surface aggregation is the most important technical contribution of the paper, hence this baseline which simply removes this component can be used to evaluate whether the proposed loss surface aggregation is actually useful. Furthermore, when comparing the \"communication savings over multi-shot\" (top paragraph of page 9), can you compare with some of the previous works on FL-HPO (i.e., those mentioned in Section 1.1) which are multi-shot methods?\n- Another important weakness of the empirical evaluation is that the FL algorithm is in fact emulated using centralized training (mentioned at the bottom of page 7). I think this makes the empirical evaluations unrealistic, and may not be able to reflect some unique features/challenges of the FL setting such as heterogeneity.\n- Table 4: some of the results are in fact worse than the baseline (which is in fact not so competitive as I discussed above) especially when the number of agents is large, which is worrying for the practical deployment of the proposed method especially in problems with a large number of agents.\n- Top paragraph of page 6: how exactly is the uncertainty quantification function u designed? I guess it's supposed to be larger if an HP has been explored by a smaller number of agents?\n- Top paragraph of page 7: it is claimed that the theoretical results imply that \"the optimality gap depends only on the HP trials $\\theta^{(i)}_t$ that are closest to the optimal HP setting\". However, I think this may not be accurate. This is because there is a max over all $\\theta\\in\\mathcal{\\Theta}$ on the right hand side of equation 2.9, therefore, to make the term $\\min\\_{t\\in[T]}d(\\theta,\\theta^{(i)\\_t})$ small for all $\\theta$, we need to make sure that the HPs $\\theta^{(i)}\\_t$'s are uniformly distributed in the entire domain. Please correct me if my understanding is incorrect here.\n- How exactly does the \"Multi-shot baseline\" in Figure 1 and Figure 2 work? This was never explained.\n- This may not be a weakness but rather a suggestion. The local HP optimization step for every agent (line 3 of Algorithm 1) may have room for improvement. Since now we have the opportunity to let every agent independently run HP optimization, we can in fact coordinate the local HP optimizations such that they can combine to lead to more accurate global loss surface estimation. For example, you can consider the method of \"distributed exploration\" from the work of Dai et al. (2021), and let every agent explore only a small local region of the entire search space.\n- [minor] I think it will be very helpful if you could explain in the introduction and abstract that being \"single-shot\" means only requiring a single-round of communication. It may be misleading to those not from the field.\n- [minor] Section 1.1, second paragraph: in \"Federated Network Architecture Search\", I think Network should be Neural.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JjuYjfs7fL", "reviewer": "Reviewer_wq54", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper studies how to perform hyper-parameter optimization in the context of federated learning, with minimal additional communication overhead. The authors propose a framework ---Federated Loss SuRface Aggregation(FLoRA)--- that requires only single-shot HPO for hyper-parameter optimization for FL. Theoretically, this paper provides an upper bound on the optimality gap, which captures the influence of parties’ data heterogeneity (Non-IID-ness) and the quality of the local HPO approximation. Empirically, the proposed new approach could largely reduce the number of communications while maintains similar model performance. ", "summary_of_the_review": "Given the importance of the problem and new approach for handling such problem, together with strong empirical results and interesting theoretical results, I recommend acceptance. ", "strength_and_weaknesses": "Strength:\n\n1. The problem studied in this work is well-motivated and important in practice.\n2. This work provides a neat solution for solving the problem of hyper-parameter optimization (HPO) for federated learning, with only single shot HPO.\n3. The theoretical results covers the non-iid setting in FL.\n4. Empirically, the proposed approach largely improves upon previous methods in terms of communication overhead.\n\nWeaknesses:\n1. (minor) The experiments mainly focus on the non-deep learning approaches and MLP architectures, it might be interesting to include some modern deep network architectures, e.g., ResNet/ViT etc. \n\nQuestions:\n1. Regarding the loss surface $\\hat{\\ell}$, under certain assumptions on $f(\\theta)$, e.g. $f$ is (strongly) convex, can the upper bound in Eq.(2.9) be further improved? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%