#  Single-shot Hyper-parameter Optimization for
Federated Learning:
A General Algorithm & Analysis

Yi Zhou Parikshit Ram Theodoros Salonidis
Nathalie Baracaldo Horst Samulowitz Heiko Ludwig
IBM Research
{yi.zhou<EMAIL_ADDRESS>
{tsaloni, baracald, samulowitz<EMAIL_ADDRESS>
###### Abstract

We address the relatively unexplored 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 and therefore 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. We theoretically characterize the
optimality gap of FLoRA, which explicitly accounts for the heterogeneous non-
iid nature of the parties’ local data distributions, a dominant characteristic
of FL systems. Our empirical evaluation of FLoRA for multiple ML algorithms on
seven OpenML datasets demonstrates significant model accuracy improvements
over the considered baseline, and robustness to increasing number of parties
involved in FL-HPO training.

##  1 Introduction

Traditional machine learning (ML) approaches require training data to be
gathered at a 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 European 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. (2017b), 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 (Kairouz et al., 2019; Khodak et al., 2021), one of which is
hyper-parameter optimization for FL. Existing FL systems require a user (or
all participating parties) to pre-set (agree on) multiple hyper-parameters
(HPs) (i) for the model being trained (such as number of layers and batch size
for neural networks or tree depth and number of trees in tree ensembles), and
(ii) for the the aggregator (if such hyper-parameters exist). Hyper-parameter
optimization (HPO) for FL is important because the choice of HPs can have
dramatic impact on performance (McMahan et al., 2017b).

While HPO has been widely studied in the centralized ML setting, it comes with
unique challenges in the FL setting. First, existing HPO techniques for
centralized training often make use of the entire dataset, which is not
available in FL. Secondly, they train a vast variety of models for a large
number of HP configurations which would be prohibitively expensive in terms of
communication and training time in FL settings. Thirdly, one important
challenge that has not been adequately explored in FL literature is support
for tabular data, which are widely used in enterprise settings (Ludwig et al.,
2020). One of the best models for this setting is based on gradient boosting
tree algorithms (Friedman, 2001) which are different from the stochastic
gradient descent algorithm used for neural networks. Recently, a few
approaches have been proposed for FL-HPO, however they focus on handling HPO
using personalization techniques (Khodak et al., 2021) and neural networks
(Khodak et al., 2020). To the best of our knowledge, there is no HPO approach
for FL systems to train non-neural network models, such as XGBoost (Chen and
Guestrin, 2016) that is particularly common in the enterprise setting.

##### Scope.

In this paper, we address the aforementioned challenges of FL-HPO. We focus on
the problem where the model HPs are shared across all parties and we seek a
set of HPs and train a single model that is eventually used by all parties for
testing/deployment. Moreover, we impose three further requirements that make
the problem more challenging: (C1) we do not make any assumption that two
models with different HPs can perform some form of “weight-sharing” (which is
a common technique used in various HPO and neural architecture search (NAS)
schemes for neural networks to reduce the computational overhead of HPO and
NAS), allowing our solution to be applied beyond neural networks (Khodak et
al., 2020). (C2) we seek to perform “single-shot” FL-HPO, where we have
limited resources (in the form of computation and communication overhead)
which allow training only a single model via federated learning (that is, a
single HP configuration), and (C3) we do not assume that parties have
independent and identically distributed (IID) data distributions.

##### Contributions.

Given the above FL-HPO problem setting, we make the following contributions:

  * •

(§3) We present a novel framework Federated Loss SuRface Aggregation (FLoRA)
that leverages meta-learning techniques to utilize local and asynchronous HPO
on each party to perform single-shot HPO for the global FL-HPO problem.

  * •

(§4) We provide theoretical guarantees for the set of HPs selected by FLoRA
covering both IID and Non-IID cases. To the best of our knowledge, this is the
first rigorous theoretical analysis for FL-HPO problem and also the first
optimality gap constructed in terms of the estimated loss given a target
distribution.

  * •

(§5) We evaluate FLoRA on the FL-HPO of Gradient Boosted Decision Trees
(GBDTs), Support Vector Machines (SVMs) and Multi-layered Perceptrons (MLPs)
on seven classification datasets from OpenML (Vanschoren et al., 2013),
highlighting (i) its performance relative to the baseline, (ii) the effect of
various choices in this scheme, and (iii) the effect of the number of parties
on the performance.

##  2 Related work

##### Performance optimization of FL systems.

One of the main challenges in FL is achieving high accuracy and low
communication overhead. FedAvg (McMahan et al., 2017a) is a predominant
algorithm used for training in FL and several optimization schemes build on
it. It is executed in multiple global rounds. At each round, the clients
perform stochastic gradient descent (SGD) updates on their parameters based on
their local objective functions. They subsequently send their updates to the
server, which averages them and transmits their mean back to the clients.
Several approaches have been devised for optimizing the communication
performance of FL systems. Initially, communication optimizations included
performing multiple SGD local iterations at the clients and randomly selecting
a small subset of the clients to compute and send updates to the server
(McMahan et al., 2017a). Subsequently, compression techniques were used to
minimize the size of model updates to the server. It has been shown that the
accuracy and communication performance of these techniques depend highly on
their HPs (McMahan et al., 2017a).

#####  FL-HPO approaches.

Recent optimization approaches adapt HPs such as the local learning rate at
each client (Koskela and Honkela, 2019; Mostafa, 2019; Reddi et al., 2020),
the number of local SGD iterations (which affect the frequency of server
updates) (Wang et al., 2019). In Dai et al. (2020, 2021), Dai et.al. address
Federated Bayesian Optimization. Although using HPO with multiple HPs, the
problem setup is quite different than Federated Learning: 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
Network Architecture Search (FNAS) approaches search for architectural HPs of
deep learning 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 et al., 2020). These approaches have shown
empirical gains but lack theoretical analysis. Inspired from the NAS technique
of weight-sharing, (Khodak et al., 2020, 2021) proposed FedEx, a FL-HPO
framework to accelerate a general HPO procedure, i.e., successive halving
algorithm (SHA), for many SGD-based FL algorithms. Fedex focuses on building
personalized models for parties by tuning local HPs of the parties. They
provide a theoretical analysis for a special case of tuning a single HP
(learning rate) in a convex optimization setting.

Our framework improves on the above approaches in several ways. 1) It is more
general, as it can tune multiple HPs and is applicable to non SGD-training
settings such as gradient boosting trees. This is achieved by treating FL-HPO
as a black-box HPO problem, which has been addressed in centralized HPO
literature using grid search, random search (Bergstra and Bengio, 2012) and
Bayesian Optimization approaches (Shahriari et al., 2016). The key challenge
is the requirement to perform computationally intensive evaluations on a large
number of HPO configurations, where each evaluation involves training a model
and scoring it on a 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 a
brute force application of centralized black-box HPO approaches that select
hyper-parameters 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 a single optimized HP configuration used to train a global model
with a single FL training. 3) It is the first that theoretically characterizes
optimality gap in an FL-HPO setting, for the case we focus in this paper
(creating a global model by tuning multiple global HPs).

##  3 Methodology

In the centralized ML setting, we would consider a model class $\mathcal{M}$
and its corresponding learning algorithm $\mathcal{A}$ parameterized
collectively with HPs $\boldsymbol{\theta}\in\boldsymbol{\Theta}$, and given a
training set $D$, we can learn a single model
$\mathcal{A}(\mathcal{M},\boldsymbol{\theta},D)\to m\in\mathcal{M}$. Given
some predictive loss $\mathcal{L}(m,D^{\prime})$ of any model $m$ scored on
some holdout set $D^{\prime}$, the centralized HPO problem can be stated as

$\min\nolimits_{\boldsymbol{\theta}\in\boldsymbol{\Theta}}\mathcal{L}(\mathcal{A}(\mathcal{M},\boldsymbol{\theta},D),D^{\prime}).$
(3.1)

In the most general FL setting, we have $p$ parties $P_{1},\dots,P_{p}$ each
with their private local training dataset $D_{i},i\in[p]=\\{1,2,\ldots,p\\}$.
Let $D=\cup_{i=1}^{p}D_{i}$ denote the aggregated training dataset and
$\overline{D}=\\{D_{i}\\}_{i\in[p]}$ denote the set of per-party datasets.
Each model class (and corresponding learning algorithm) is parameterized by
global HPs $\boldsymbol{\theta}_{G}\in\boldsymbol{\Theta}_{G}$ shared by all
parties and per-party local HPs
$\boldsymbol{\theta}_{L}^{(i)}\in\boldsymbol{\Theta}_{L},i\in[p]$ with
$\boldsymbol{\Theta}=\boldsymbol{\Theta}_{G}\times\boldsymbol{\Theta}_{L}$. FL
systems usually include an aggregator with its own set of HPs
$\boldsymbol{\phi}\in\boldsymbol{\Phi}$. Finally, we would have a FL algorithm

$\mathcal{F}\left(\mathcal{M},\boldsymbol{\phi},\boldsymbol{\theta}_{G},\\{\boldsymbol{\theta}_{L}^{(i)}\\}_{i\in[p]},\mathcal{A},\overline{D}\right)\to
m\in\mathcal{M},$ (3.2)

which takes as input all the relevant HPs 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 dataset
$D^{\prime}$ (a.k.a validation set, possibly from the same distribution as the
aggregated dataset $D$), the target problem is:

$\min_{\boldsymbol{\phi}\in\boldsymbol{\Phi},\boldsymbol{\theta}_{G}\in\boldsymbol{\Theta}_{G},\boldsymbol{\theta}_{L}^{(i)}\in\boldsymbol{\Theta}_{L},i\in[p]}\mathcal{L}\left(\mathcal{F}\left(\mathcal{M},\boldsymbol{\phi},\boldsymbol{\theta}_{G},\\{\boldsymbol{\theta}_{L}^{(i)}\\}_{i\in[p]},\mathcal{A},\overline{D}\right),D^{\prime}\right).$
(3.3)

(ii) An alternative target problem would involve per-party holdout datasets
$D_{i}^{\prime},i\in[p]$ as follows:

$\min_{\boldsymbol{\phi}\in\boldsymbol{\Phi},\boldsymbol{\theta}_{G}\in\boldsymbol{\Theta}_{G},\boldsymbol{\theta}_{L}^{(i)}\in\boldsymbol{\Theta}_{L},i\in[p]}\mathsf{Agg}\left(\left\\{\mathcal{L}\left(\mathcal{F}\left(\mathcal{M},\boldsymbol{\phi},\boldsymbol{\theta}_{G},\\{\boldsymbol{\theta}_{L}^{(i)}\\}_{i\in[p]},\mathcal{A},\overline{D}\right),D^{\prime}_{i}\right),i\in[p]\right\\}\right),$
(3.4)

where $\mathsf{Agg}:\mathbb{R}^{p}\to\mathbb{R}$ is some aggregation function
(such as average or maximum) that scalarizes the $p$ per-party predictive
losses.

Contrasting problem (3.1) to problems (3.3) & (3.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 (3.3) although our proposed single-
shot FL-HPO scheme can be applied and evaluated for problem (3.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
$\boldsymbol{\theta}_{L}^{(i)},i\in[p]$, (ii) we only focus on the model class
HPs $\boldsymbol{\theta}_{G}$, deferring HPO for aggregator HPs
$\boldsymbol{\phi}$ for future work, and (iii) we assume there is a global
holdout/validation set $D^{\prime}$ which is only used to evaluate the final
global model’s performance but can not be accessed during HPO process. Hence
the problem we will study is stated as for a fixed aggregator HP
$\boldsymbol{\phi}$:

$\min\nolimits_{\boldsymbol{\theta}_{G}\in\boldsymbol{\Theta}_{G}}\mathcal{L}\left(\mathcal{F}\left(\mathcal{M},\boldsymbol{\phi},\boldsymbol{\theta}_{G},\mathcal{A},\overline{D}\right),D^{\prime}\right).$
(3.5)

This problem appears similar to the centralized HPO problem (3.1). However,
note that the main challenges in (3.5) is (i) the need for a federated
training for each set of HPs $\boldsymbol{\theta}_{G}$, and (ii) the need to
evaluate the trained model on the global validation set $D^{\prime}$ (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
off-the-shelf HPO schemes to problem (3.5). In the subsequent discussion, for
simplicity purposes, we will use $\boldsymbol{\theta}$ to denote the global
HPs, dropping the “$G$” subscript.

###  3.1 Leveraging local HPOs

Algorithm 1 Single-shot FL-HPO with Federated Loss Surface Aggregation (FLoRA)

1:
Input:$\boldsymbol{\Theta},\mathcal{M},\mathcal{A},\mathcal{F},\\{(D_{i},D_{i}^{\prime})\\}_{i\in[p]},T$

2: for each party $P_{i},i\in[p]$ do

3: Run HPO to generate $T$ (HP, loss) pairs
$E^{(i)}=\left\\{(\boldsymbol{\theta}_{t}^{(i)},\mathcal{L}_{t}^{(i)}),t\in[T]\right\\},$
(3.6) where
$\boldsymbol{\theta}_{t}^{(i)}\in\boldsymbol{\Theta},\mathcal{L}_{t}^{(i)}:=\mathcal{L}(\mathcal{A}(\mathcal{M},\boldsymbol{\theta}_{t}^{(i)},D_{i}),D_{i}^{\prime})$.

4: end for

5: Collect all $E=\\{E^{(i)},i\in[p]\\}$ in aggregator

6: Generate a unified loss surface
$\widehat{\ell}:\boldsymbol{\Theta}\to\mathbb{R}$ using $E$

7: Select best HP candidate
$\displaystyle\widehat{\boldsymbol{\theta}}^{\star}\leftarrow\arg\min\limits_{\boldsymbol{\theta}\in\boldsymbol{\Theta}}\widehat{\ell}(\boldsymbol{\theta}).$
(3.7)

8: Invoke federated training
$m\leftarrow\mathcal{F}(\mathcal{M},\widehat{\boldsymbol{\theta}}^{\star},\mathcal{A},\overline{D})$

9: Output: FL model $m$.

While it is impractical to apply off-the-shelf HPO solvers (such as Bayesian
Optimization (BO) (Shahriari et al., 2016), Hyperopt (Bergstra et al., 2011),
SMAC (Hutter et al., 2011), and such), we wish to understand how we can
leverage local and asynchronous HPOs in each of the parties. We begin with a
simple but intuitive hypothesis underlying various meta-learning schemes for
HPO (Vanschoren, 2018; Wistuba et al., 2018): if a HP configuration
$\boldsymbol{\theta}$ has good performance for all parties independently, then
$\boldsymbol{\theta}$ is a strong candidate for federated training.

With this hypothesis, we present our proposed algorithm FLoRA in Algorithm 1.
In this scheme, we allow each party to perform HPO locally and asynchronously
with some adaptive HPO scheme such as BO (line 3). Then, at each party
$i\in[p]$, we collect all the attempted $T$ HPs
$\boldsymbol{\theta}_{t}^{(i)},t\in[T]=\\{1,2,\ldots,T\\}$ and their
corresponding predictive loss $\mathcal{L}_{t}^{(i)}$ into a set $E^{(i)}$
(line 3, equation (3.6)). Then these per-party sets of (HP, loss) pairs
$E^{(i)}$ are collected at the aggregator (line 5). This operation has at most
$O(pT)$ communication overhead (note that the number of HPs are usually much
smaller than the number of columns or number of rows in the per-party
datasets). These sets are then used to generate an aggregated loss surface
$\widehat{\ell}:\boldsymbol{\Theta}\to\mathbb{R}$ (line 6) which will then be
used to make the final single-shot HP recommendation
$\widehat{\boldsymbol{\theta}}^{\star}\in\boldsymbol{\Theta}$ (line 7) for the
federated training to create the final model $m\in\mathcal{M}$ (line 8). We
will discuss the generation of the aggregated loss surface in detail in §3.2.
Before that, we briefly want to discuss the motivation behind some of our
choices in Algorithm 1.

##### Why adaptive HPO?

The reason to use adaptive HPO schemes instead of non-adaptive schemes such as
random search or grid search is that this 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.

##### Why asynchronous HPO?

Each party executes 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.

###  3.2 Loss surface aggregation

Given the sets of (HP, loss) pairs
$E^{(i)}=(\boldsymbol{\theta}_{t}^{(i)},\mathcal{L}_{t}^{(i)}),i\in[p],t\in[T]$
at the aggregator, we wish to construct a loss surface
$\widehat{\ell}:\boldsymbol{\Theta}\to\mathbb{R}$ that best emulates the
(relative) performance loss $\widehat{\ell}(\boldsymbol{\theta})$ we would
observe when training the model on $\overline{D}$. Based on our hypothesis, we
want the loss surface to be such that it would have a relatively low
$\widehat{\ell}(\boldsymbol{\theta})$ if $\boldsymbol{\theta}$ has a low loss
for all parties simultaneously. However, because of the asynchronous and
adaptive nature of the local HPOs, for any HP
$\boldsymbol{\theta}\in\boldsymbol{\Theta}$, 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. In the following, we present four ways of constructing such loss
surfaces:

##### Single global model (SGM).

We merge all the sets $E=\cup_{i\in[p]}E^{(i)}$ and use it as a training set
for a regressor $f:\boldsymbol{\Theta}\to\mathbb{R}$, which considers the HPs
$\boldsymbol{\theta}\in\boldsymbol{\Theta}$ as the covariates and the
corresponding loss as the dependent variable. For example, we can train a
random forest regressor (Breiman, 2001) on this training set $E$. Then we can
define the loss surface
$\widehat{\ell}(\boldsymbol{\theta}):=f(\boldsymbol{\theta})$. 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 a low loss to any HP $\boldsymbol{\theta}$ which has
a low loss at 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 on all parties.

##### Single global model with uncertainty (SGM+U).

Given the merged set $E=\cup_{i\in[p]}E^{(i)}$, we can train a regressor that
provides uncertainty quantification around its predictions (such as Gaussian
Process Regressor (Williams and Rasmussen, 2006)) as
$f:\boldsymbol{\Theta}\to\mathbb{R},u:\boldsymbol{\Theta}\to\mathbb{R}_{+}$,
where $f(\boldsymbol{\theta})$ is the mean prediction of the model at
$\boldsymbol{\theta}\in\boldsymbol{\Theta}$ while $u(\boldsymbol{\theta})$
quantifies the uncertainty around this prediction $f(\boldsymbol{\theta})$. We
define the loss surface as
$\widehat{\ell}(\boldsymbol{\theta}):=f(\boldsymbol{\theta})+\alpha\cdot
u(\boldsymbol{\theta})$ for some $\alpha>0$. This loss surface does prefer HPs
that have a low loss even in just one of the parties, but it penalizes a HP if
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 are multiple
samples in the region around this HP but parties do not collectively agree
that this is a 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 to be promising to multiple parties.

##### Maximum of per-party local models (MPLM).

Instead of a single global model on the merged set $E$, we can instead train a
regressor $f^{(i)}:\boldsymbol{\Theta}\to\mathbb{R},i\in[p]$ with each of the
per-party set $E^{(i)}$. Given this, we can construct the loss surface as
$\widehat{\ell}(\boldsymbol{\theta}):=\max_{i\in[p]}f^{(i)}(\boldsymbol{\theta})$.
This can be seen as a much more pessimistic loss surface, assigning a low loss
to a HP only if it 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^{(i)},i\in[p]$ instead of the
maximum, defined as
$\widehat{\ell}(\boldsymbol{\theta}):=\nicefrac{{1}}{{p}}\sum_{i=1}^{p}f^{(i)}(\boldsymbol{\theta})$.
This is also less optimistic than SGM since it will assign a low loss for a HP
only if its average across all per-party regressors is low, which implies that
all parties observed a relatively low loss around this HP.

Intuitively, we 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. In the following section, we theoretically quantify the performance
guarantees for MPLM and APLM, and in §5, we evaluate all these loss surface
empirically in the single-shot FL-HPO setting.

##  4 Optimality analysis

In this section, we provide a rigorous analysis of the sub-optimality of the
HP selected by FLoRA. Let us first define some notation we will use throughout
this section.

######  Definition 4.1 (Loss functions).

For a given set of parties’ data $\overline{D}=\\{D_{i}\\}_{i\in[p]}$ and any
$\boldsymbol{\theta}\in\boldsymbol{\Theta}$, the true target loss (any
predictive performance metric, such as, the training loss) can be expressed
as:

$\ell(\boldsymbol{\theta},\mathcal{D}):=\underbrace{\mathbb{E}_{(x,y)\sim\mathcal{D}}}_{\text{test
perf. of trained
model}}\mathcal{L}(\underbrace{\mathcal{A}(\boldsymbol{\theta},\overline{D})}_{\text{trained
model}},(x,y)).$ (4.1)

Here $\mathcal{D}$ is the data distribution of the test points. Let
$\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})$ be an estimate of the loss
defined in (4.1) given some validation (holdout) set $D^{\prime}$ sampled from
$\mathcal{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 $\overline{D}$ is fixed and unchanged during the HPO and FL
processes, in order words, we do not consider streaming data setting.

Now we are ready to provide a more general definition of the unified loss
surface constructed by FLoRA as follows:

######  Definition 4.2 (Unified loss surface).

Given the local loss surfaces
$\widehat{\ell}_{i}:\boldsymbol{\Theta}\to\mathbb{R}$ for each party $i\in[p]$
generated by $T$ (HP, loss) pairs
$\\{(\boldsymbol{\theta}^{(i)}_{t},\mathcal{L}_{t}^{(i)})\\}_{t\in[T]}$, we
can define the global loss surface
$\widehat{\ell}:\boldsymbol{\Theta}\to\mathbb{R}$ as

$\widehat{\ell}(\boldsymbol{\theta})=\textstyle{\sum}_{i=1}^{p}\alpha_{i}(\boldsymbol{\theta})\cdot\widehat{\ell}_{i}(\boldsymbol{\theta}),\alpha_{i}(\boldsymbol{\theta})\in[0,1],\textstyle{\sum}_{i=1}^{p}\alpha_{i}(\boldsymbol{\theta})=1.$
(4.2)

In particular,

  * i)

If $\alpha_{i}(\boldsymbol{\theta})=\nicefrac{{1}}{{p}},\ \forall
i\in[p],\boldsymbol{\theta}\in\boldsymbol{\Theta}$, then this reduces to APLM
loss surface.

  * ii)

If
$\alpha_{i}(\boldsymbol{\theta})=\mathbb{I}\left(\widehat{\ell}_{i}(\boldsymbol{\theta})=\max_{j\in[p]}\widehat{\ell}_{j}(\boldsymbol{\theta})\right)$,
then this reduces to the MPLM loss surface (assuming all
$\widehat{\ell}_{j}(\boldsymbol{\theta})$s are unique).

We formalize the distance metric used in our analysis to evaluate the distance
between two given data distributions.

######  Definition 4.3 (1-Wasserstein distance (Villani, 2003)).

For two distributions $\mu,\nu$ with bounded support, the 1-Wasserstein
distance is defined as

$\mathcal{W}_{1}(\mu,\nu):=\sup_{f\in\mathsf{F}_{1}}\mathbb{E}_{x\sim\mu}f(x)-\mathbb{E}_{x\sim\nu}f(x),$
(4.3)

where $\mathsf{F}_{1}=\\{f:f\text{ is continuous},\textsf{Lipschitz}(f)\leq
1\\}$.

To facilitate our analysis later, we make the following Lipschitzness
assumptions regarding the loss function $\tilde{\ell}$ and also the per-party
loss surface $\widehat{\ell}_{i}$.

######  Assumption 4.4 (Lipschitzness).

For a fixed data distribution $\mathcal{D}$ and
$\forall\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}\in\bar{\boldsymbol{\Theta}}\subset\boldsymbol{\Theta}$,
we have

$\displaystyle|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta}^{\prime},\mathcal{D})|$
$\displaystyle\leq\tilde{L}(\mathcal{D})\cdot
d(\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}),$ (4.4)
$\displaystyle|\widehat{\ell}_{i}(\boldsymbol{\theta})-\widehat{\ell}_{i}(\boldsymbol{\theta}^{\prime})|$
$\displaystyle\leq\widehat{L}_{i}\cdot
d(\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}),$ (4.5)

where $d(\cdot,\cdot)$ is a certain distance metric defined over the hyper-
parameter search space, see Appendix A.1 for one definition. For a fixed set
of hyper-parameters
$\boldsymbol{\theta}\in\bar{\boldsymbol{\Theta}}\subset\boldsymbol{\Theta}$
and some data distributions $\mathcal{D}$ and $\mathcal{D}^{\prime}$, we have

$|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}^{\prime})|\leq\tilde{\beta}(\boldsymbol{\theta})\cdot\mathcal{W}_{1}(\mathcal{D},\mathcal{D}^{\prime}).$
(4.6)

##### Remark.

Note that we explicitly use a
$\bar{\boldsymbol{\Theta}}\subset\boldsymbol{\Theta}$ to highlight that we
need Lipschitz-ness only in particular parts of the HP space. In fact, our
analysis only requires the Lipschitz-ness at
$\widehat{\boldsymbol{\theta}}^{*}$, the optimal HP and a HP space containing
these two HPs and the set of HP tried in local HPO runs, i.e.,
$\boldsymbol{\theta}_{t}^{(i)}$, which most of the time does not cover the
entire HP search space. Moreover, the above Lipschitzness assumption w.r.t. a
general HP space, which could be a combination of continuous and discrete
variables, may be strong. We also show in Appendix A.2 and B.4 that it can be
relaxed to a milder assumption based on the modulus of continuity without
significantly affecting our main results. For simplicity, we can always assume
that $\tilde{L}(\mathcal{D})\leq\tilde{L},\ \forall\mathcal{D}$ and
$\tilde{\beta}(\boldsymbol{\theta})\leq\tilde{\beta},\
\forall\boldsymbol{\theta}$.

Recall that the HP $\widehat{\boldsymbol{\theta}}^{\star}$ selected by FLoRA
is defined as in (3.7). We then define the optimal HP given by the estimated
loss function for a desired data distribution $\mathcal{D}$ we want to learn
as,

$\boldsymbol{\theta}^{\star}\in\arg\min_{\boldsymbol{\theta}\in\boldsymbol{\Theta}}\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}).$
(4.7)

We are interested in providing a bound for the following optimality gap:

$\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta}^{\star},\mathcal{D}).$
(4.8)

Note that this bound is the optimality gap for the output of FLoRA in terms of
the estimated loss $\tilde{\ell}$. We state our main results in the following
theorem. Informally speaking 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.

######  Theorem 4.5.

Consider the optimality gap defined in (4.8), where
$\widehat{\boldsymbol{\theta}}^{*}$ is selected by FLoRA with each party
$i\in[p]$ collecting $T$ (HP, loss) pairs
$\\{(\boldsymbol{\theta}_{t}^{(i)},\mathcal{L}_{t}^{(i)})\\}_{t\in[T]}$ during
the local HPO run. For a desired data distribution
$\mathcal{D}=\sum_{i=1}^{p}w_{i}\mathcal{D}_{i}$, where
$\\{\mathcal{D}_{i}\\}_{i\in[p]}$ are the sets of parties’ local data
distributions and $w_{i}\in[0,1],\forall i\in[p]$, we have

$\displaystyle\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta}^{\star},\mathcal{D})$
$\displaystyle\ \leq
2\max_{\boldsymbol{\theta}\in\bar{\boldsymbol{\Theta}}}\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\left\\{\tilde{\beta}(\boldsymbol{\theta})\textstyle{\sum}_{j\in[p],j\not=i}w_{j}\mathcal{W}_{1}(\mathcal{D}_{j},\mathcal{D}_{i})+\left(\tilde{L}(\mathcal{D}_{i})+\widehat{L}_{i}\right)\min_{t\in[T]}d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)})+\delta_{i}\right\\},$
(4.9)

where $\delta_{i}$ is the maximum per sample training error for the local loss
surface $\widehat{\ell}_{i}$, i.e.,
$\delta_{i}=\max_{t}|\mathcal{L}_{t}^{(i)}-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})|$.
In particular, when all parties have i.i.d. local data distributions, (4.5)
reduces to

$\displaystyle\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta}^{\star},\mathcal{D})\leq
2\max_{\boldsymbol{\theta}\in\bar{\boldsymbol{\Theta}}}\sum_{i=1}^{p}\alpha_{i}(\boldsymbol{\theta})\left\\{\left(\tilde{L}(\mathcal{D}_{i})+\widehat{L}_{i}\right)\min\limits_{t\in[T]}d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)})+\delta_{i}\right\\}.$

We make some observations regarding the above results. Firstly, the first term
in our bound characterizes the errors incurred by the differences among
parties’ local data distributions, i.e., the magnitude of Non-IIDness in a FL
system. In particular, we can see it vanish under the IID setting. Secondly,
the last two terms measure the quality of the local HPO approximation, which
can be reduced if a good loss surface is selected. Thirdly,
$\min_{t\in[T]}d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)})$ indicates
that the optimality gap depends only on the HP trials
$\boldsymbol{\theta}_{t}^{(i)}$ that is closest to the optimal HP setting.
Finally, if we assume each party’s training dataset $D_{i}$ is of size $n_{i}$
sampled as $D_{i}\sim\mathcal{D}_{i}^{n_{i}}$, we can view
$w_{i}=\tfrac{n_{i}}{n}$ where $n=\sum_{i=1}^{p}n_{i}$, i.e., with probability
$w_{i}$ the desired data distribution $\mathcal{D}$ is sampled from
$\mathcal{D}_{i}$.

In order to obtain the result in (4.5), we first analyze (4.8) in Proposition
4.6, see its proof in Appendix B. Note that the local loss surfaces
$\widehat{\ell}_{i},\ i\in[p]$ are computed at a certain test/validation set
sampled from the parties local data distribution $\mathcal{D}_{i}$. We
quantify the relationship between $\widehat{\ell}_{i}(\boldsymbol{\theta})$
and the estimated loss function
$\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})$ as follows:

$|\widehat{\ell}_{i}(\boldsymbol{\theta})-\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})|:=\epsilon_{i}(\boldsymbol{\theta},T).$
(4.10)

######  Proposition 4.6.

Consider $\widehat{\boldsymbol{\theta}}^{\star}$ and
$\boldsymbol{\theta}^{\star}$ are two sets of HP defined in (3.7) and (4.7),
respectively, and $\\{\mathcal{D}_{i}\\}_{i\in[p]}$ and $\mathcal{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
$\widehat{\boldsymbol{\theta}}^{\star},\boldsymbol{\theta}^{\star}\in\bar{\boldsymbol{\Theta}}\subset\boldsymbol{\Theta}$,
we have

$\displaystyle\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta}^{\star},\mathcal{D})\leq
2\max_{\boldsymbol{\theta}\in\bar{\boldsymbol{\Theta}}}\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\left\\{\tilde{\beta}(\boldsymbol{\theta})\mathcal{W}_{1}(\mathcal{D},\mathcal{D}_{i})+\epsilon_{i}(\boldsymbol{\theta},T)\right\\}.$
(4.11)

We now dive into each term in (4.11) to provide tight bounds for
$\mathcal{W}_{1}(\mathcal{D},\mathcal{D}_{i})$ and
$\epsilon_{i}(\boldsymbol{\theta},T)$ in the following propositions. All the
proofs can be found in Appendix B.

######  Proposition 4.7.

Consider 1-Wasserstein distance we defined in (4.3), for a local data
distribution $\mathcal{D}_{i}$ of any party $i,\ i\in[p]$, and
$\mathcal{D}=\sum_{i=1}^{p}w_{i}\mathcal{D}_{i}$ for some
$w_{i}\in[0,1],\forall i\in[p]$, we have

$\mathcal{W}_{1}(\mathcal{D},\mathcal{D}_{i})\leq\textstyle{\sum}_{j\in[p],j\not=i}w_{j}\mathcal{W}_{1}(\mathcal{D}_{j},\mathcal{D}_{i}).$
(4.12)

In particular, when $\mathcal{D}_{i},\ i\in[p]$ are i.i.d. data distribution,
i.e., all parties in a federated learning system possess i.i.d. local data
distribution – that is,
$\mathcal{W}_{1}(\mathcal{D}_{j},\mathcal{D}_{i})=0\forall i,j\in[p]$ – then
$\textstyle{\sum}_{j\in[p],j\not=i}w_{j}\mathcal{W}_{1}(\mathcal{D}_{j},\mathcal{D}_{i})=0$.
Therefore, $\mathcal{W}_{1}(\mathcal{D},\mathcal{D}_{i})=0,\ \forall i\in[p]$.

######  Proposition 4.8.

For any party $i,\ i\in[p]$, consider a (HP, loss) pair
$(\boldsymbol{\theta}_{t}^{(i)},\mathcal{L}_{t}^{(i)})$ collected during the
local HPO run for party $i$, for any
$\boldsymbol{\theta}\in\bar{\boldsymbol{\Theta}}\subset\boldsymbol{\Theta}$,
we have

$\epsilon_{i}(\boldsymbol{\theta},T)\leq\left(\tilde{L}(\mathcal{D}_{i})+\widehat{L}_{i}\right)\min_{t\in[T]}d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)})+\delta_{i},$
(4.13)

where
$\delta_{i}=\max_{t}|\mathcal{L}_{t}^{(i)}-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})|$
is the maximum per sample training error for the local loss surface
$\widehat{\ell}_{i}$.

Note that if we use non-parametric regression models as the loss surfaces
(such as Gaussian Processes, Random Forests, etc), the per-sample training
error can be made arbitrarily small (that is $\delta_{i}\approx 0$), but at
the cost of increasing $\widehat{L}_{i}$ for $\widehat{\ell}_{i}$.

##  5 Empirical evaluation

Table 1: Comparison of 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 | [0.04, 0.38, 1.11] | [0.04, 0.48, 1.07] | [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.99] |  [0.36, 0.57, 0.79]
FLoRA | HGB | 6/0/1 | 6/0/1 | 7/0/0 | 7/0/0
Wins/Ties/Losses | 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
Wilcoxon Signed-Rank Test | HGB | (26, 0.02126) | (27, 0.01400) | (28, 0.00898) | (28, 0.00898)
1-sided | SVM | (18, 0.05793) | (17, 0.08648) | (9, 0.62342) | (15, 0.17272)
(statistic, p-value) | MLP | (21, 0.11836) | (15, 0.17272) | (18, 0.05793) | (24, 0.04548)
| Overall | (174, 0.00499) | (164, 0.00272) | (141, 0.03206) | (183.5, 0.00169)

In this section, we evaluate our proposed scheme FLoRA with different loss
surfaces for the FL-HPO on a variety of ML models – histograms based gradient
boosted (HGB) decision trees (Friedman, 2001), Support Vector Machines (SVM)
with RBF kernel and multi-layered perceptrons (MLP) (using their respective
scikit-learn implementation (Pedregosa et al., 2011)) on OpenML (Vanschoren et
al., 2013) classification problems. The precise HP search space is described
in Appendix C.2. First, we fix the number of parties $p=3$ and compare FLoRA
to a baseline on $7$ datasets. Then we study the effect of increasing the
number of parties from $p=3$ up to $p=100$ on the performance of our proposed
scheme on $3$ datasets. The data is randomly split across parties. We also
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. Finally, we evaluate FLoRA in a real FL testbed IBM FL
(Ludwig et al., 2020) using its default HP setting as a baseline. More
experimental results can be found in Appendix C.

##### Single-shot baseline.

To appropriately evaluate our proposed single-shot FL-HPO scheme, we need to
select a 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 configuration in scikit-learn is set manually
based on expert prior knowledge and extensive empirical evaluation, and (ii)
these are also used as the defaults in the Auto-Sklearn package (Feurer et
al., 2015, 2020), one of the leading open-source AutoML python packages, which
maintains a carefully selected portfolio of default configurations.

##### Dataset selection.

For our evaluation of single-shot HPO, we consider $7$ binary classification
datasets of varying sizes and characteristics from OpenML (Vanschoren et al.,
2013) such that there is at least a significant room for improvement over the
single-shot baseline performance. We consider datasets which have at least
$>3\%$ potential improvement in balanced accuracy for gradient boosted
decision trees. See Appendix C.1 for details on data. 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.

##### (Dis-)Regarding other baselines.

While there are some existing schemes for FL-HPO (as discussed in §2), we are
unable to compare FLoRA to them for the following reasons: (i) As noted by
Khodak et al. (2021, Section 1, Related Work), existing schemes focus “on a
small number of hyperparameters (e.g. the step-size and sometimes one or two
more) in less general settings (studying small-scale problems or assuming
server-side validation data)” whereas we explicitly assume no access to such a
“server-side validation data”. (ii) Furthermore, we noted in §1 (C1), we do
not assume any “weight-sharing” type capability, and hence it is not clear how
FedEx (Khodak et al., 2021) can be applied to FL-HPO in the
general111Moreover, (Khodak et al., 2021) claim that FedEx can handle
architectural hyper-paramters but it is never demonstrated and discussed
explicitly. In contrast, our proposed algorithm can handle architectural
hyperparameters (as we do with HGB (tree depth) and MLP (width of the
layer))..

##### Implementation.

We consider two implementations for our empirical evaluation. In our first
three sets of experiments, we emulate the final FL (Algorithm 1, line 8) with
a centralized training using the pooled data. We chose this implementation
because we 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-validation)
instead of evaluating the performance on a 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.

##### Evaluation metric.

In all datasets, we consider the balanced accuracy as the metric we wish to
maximize. For the local per-party HPOs (as well as the centralized HPO we
execute to compute the regret), we maximize the 10-fold cross-validated
balanced accuracy. For Table 1-2, we report the relative regret, computed as
$\nicefrac{{(a^{\star}-a)}}{{(a^{\star}-b)}}$, where $a^{\star}$ is the best
metric obtained via the centralized HPO, $b$ is the result of the 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
baseline.

##### Comparison to single-shot baseline.

In our first set of experiments for 3-party FL-HPO ($p=3$), we compare our
proposed scheme with the baseline across different datasets, machine learning
models and FLoRA loss surfaces. The aggregated results are presented in Table
1, with the individual results detailed in Appendix C.3. For each of the three
methods, we report the aggregate performance over all considered datasets in
terms of (i) inter-quartile range, (ii) Wins/Ties/Losses of FLoRA w.r.t. the
single-shot baseline, and (iii) a 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 also report an “Overall” performance, further
aggregated across all ML models.

All FLoRA loss surfaces show strong performance 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-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 to $10^{-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 a couple of very hard cases with SVM (see
Appendix C.3 for detailed discussion). Otherwise, MPLM performs second best
both for FL-HPO with HGB and MLP.

Table 2: Effect of increasing the number of parties on FLoRA with different loss surfaces for HGB.  Data | $p$ | $\gamma_{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 | 3 | 1.01 | 0.17 | 0.14 | 0.09 | 0.12
45312 samples | 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 | 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 samples | 6 | 1.10 | 1.02 | 0.91 | 0.54 | 0.56
| 10 | 1.16 | 1.05 | 0.73 | 0.75 | 1.12

##### Effect of increasing number of parties.

In the second set of experiments, we study the effect of increasing the number
of parties in the FL-HPO problem on 3 datasets and HGB. 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 in Table 2. It also displays
$\gamma_{p}:=\nicefrac{{\left(1-\min_{i\in[p]}\mathcal{L}_{\star}^{(i)}\right)}}{{\left(1-\max_{i\in[p]}\mathcal{L}_{\star}^{(i)}\right)}}$,
where $\mathcal{L}_{\star}^{(i)}=\min_{t\in[T]}\mathcal{L}_{t}^{(i)}$ is the
minimum loss observed during the local asynchronous HPO at party $i$. This
ratio $\gamma_{p}$ is always greater than 1, and highlights the difference in
the observed performances across the parties. A ratio closer to 1 indicates
that all the parties have relatively similar performances on their respective
training data, while a ratio much higher than 1 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 $\gamma_{p}$ for the Electricity dataset until $p=100$, but
significantly increases for the Pollen dataset earlier (making the problem
harder). For the EEG eye state, the increase in $\gamma_{p}$ with increasing
$p$ is moderate until $p=50$. The results indicate that, with low or moderate
increase in $\gamma_{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 $\gamma_{p}$ (Pollen, Electricity with $p=50,100$
and EEG Eye State with $p=50$), we see a significant increase in the relative
regret (eventually going over 1 in a 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.

(a) # local HPO rounds.

(b) # (HP, loss) pairs communicated to aggregator

Figure 1: 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 C.4 and C.5.

##### 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 1(a). 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 to its
best possible value. We present the results for other loss surfaces in
Appendix C.4.

We also study the effect of the communication overhead of FLoRA for fixed
level of local HPO thoroughness. We assume that each party performs $T=100$
rounds of local asynchronous HPO. However, instead of sending all $T$ (HP,
loss) pairs, we consider sending $T^{\prime}<T$ of the “best” (HP, loss) pairs
– that is, (HP, loss) pairs with the $T^{\prime}$ lowest losses. Changing the
value of $T^{\prime}$ trades off the communication overhead of the FLoRA step
where the aggregators collect the per-party loss pairs (Algorithm 1, line 5).
The results for this study are presented in Figure 1(b), and indicate that,
for really small $T^{\prime}$, the relative regret can be really high.
However, for a moderately high value of $T^{\prime}<T$, FLoRA converges to its
best possible performance. Results on other loss surfaces and further
discussion can be found in Appendix C.5.

Table 3: Performance of FLoRA with the IBM-FL system in terms of the balanced accuracy on a holdout test set (higher is better). The baseline is still the default HP configuration of HistGradientBoostingClassifier in scikit-learn. Data | # parties | # training data per party | Baseline | SGM | SGM+U | MPLM | APLM
---|---|---|---|---|---|---|---
Oil spill | $3$ | $200$ | 0.5895 | 0.7374 | 0.5909 | 0.7061 | 0.7332
EEG eye state | $3$ | $3,000$ | 0.8864 | 0.9153 | 0.9211 | 0.9251 | 0.9245
Electricity | $6$ | $4,000$ | 0.8448 | 0.8562 | 0.8627 | 0.8621 | 0.8624

##### 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 as global hold-out set only for evaluating the final FL model
performance. Each party randomly sampled from the rest of the original dataset
to obtain their own training dataset. We use the same HP search space as in
Appendix C.2. We report the balanced accuracy of any HP (baseline or
recommended by FLoRA) on a single train/test split. Given balanced accuracy as
the evaluation metric, we utilize (1 - balanced accuracy) as the loss
$\mathcal{L}_{t}^{(i)}$ in Algorithm 1 Each party will run HPO to generate
$T=500$ (HP, loss) pairs and use those pairs to generate loss surface either
collaboratively or by their own according to different aggregation procedures
described in §3.2. Once the loss surface is generated, the aggregator uses
Hyperopt (Bergstra et al., 2011) to select the best HP candidate and train a
federated XGBoost model via the IBM FL library using the selected HPs. Table 3
summarizes the experimental results for $3$ datasets, indicating that FLoRA
can significantly improve over the baseline in IBM FL testbed.

##  6 Conclusions

How to effectively select hyper-parameters in FL settings is a challenging
problem. In this paper, we introduced FLoRA, a single-shot FL-HPO algorithm
that can be applied to a variety of ML models. We provided a theoretical
analysis which includes a bound on the optimality gap incurred by the hyper-
parameter selection performed by FLoRA. Our experimental evaluation shows that
FLoRA can effectively produce hyper-paramater configurations that outperform
the baseline with just a single shot.

## References

  * Bergstra and Bengio (2012) James Bergstra and Yoshua Bengio.  Random search for hyper-parameter optimization.  _Journal of Machine Learning Research_ , 13(Feb):281–305, 2012.
  * Bergstra et al. (2011) 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_ , pages 2546–2554, 2011.
  * Breiman (2001) Leo Breiman.  Random forests.  _Machine learning_ , 45(1):5–32, 2001.
  * Chen and Guestrin (2016) 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, pages 785–794, New York, NY, USA, 2016. ACM.  ISBN 978-1-4503-4232-2.  doi: 10.1145/2939672.2939785.  URL http://doi.acm.org/10.1145/2939672.2939785.
  * Dai et al. (2020) Z. Dai, B.K.H. Low, and P. Jaillet.  Federated bayesian optimization via thompson sampling.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Dai et al. (2021) Z. Dai, B.K.H. Low, and P. Jaillet.  Differentially private federated bayesian optimization with distributed exploration.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Feurer et al. (2015) 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_ , pages 2962–2970, 2015.
  * Feurer et al. (2020) Matthias Feurer, Katharina Eggensperger, Stefan Falkner, Marius Lindauer, and Frank Hutter.  Auto-sklearn 2.0: The next generation.  In _arXiv:2007.04074 [cs.LG]_ , 2020.
  * Friedman (2001) Jerome H Friedman.  Greedy function approximation: a gradient boosting machine.  _Annals of statistics_ , pages 1189–1232, 2001.
  * Garg et al. (2020) Anubhav Garg, Amit Kumar Saha, and Debo Dutta.  Direct federated neural architecture search.  _arxiv.2010.06223_ , 2020.
  * He et al. (2020) Chaoyang He, Murali Annavaram, and Salman Avestimehr.  Towards non-i.i.d. and invisible data with fednas: Federated deep learning via neural architecture search.  _arxiv.2004.08546_ , 2020.
  * Hutter et al. (2011) Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown.  Sequential model-based optimization for general algorithm configuration.  In _International Conference on Learning and Intelligent Optimization_ , pages 507–523. Springer, 2011.
  * Kairouz et al. (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.  Advances and open problems in federated learning.  _arXiv preprint arXiv:1912.04977_ , 2019.
  * Khodak et al. (2020) Mikhail Khodak, Tian Li, Liam Li, M Balcan, Virginia Smith, and Ameet Talwalkar.  Weight sharing for hyperparameter optimization in federated learning.  In _Int. Workshop on Federated Learning for User Privacy and Data Confidentiality in Conjunction with ICML 2020_ , 2020.
  * Khodak et al. (2021) 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 arXiv:2106.04502_ , 2021.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _ICLR (Poster)_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * Koskela and Honkela (2019) A. Koskela and A. Honkela.  Learning rate adaptation for federated and differentially private learning.  _arXiv preprint arXiv:1809.03832_ , 2019.
  * Ludwig et al. (2020) Heiko Ludwig, Nathalie Baracaldo, Gegi Thomas, Yi Zhou, Ali Anwar, Shashank Rajamoni, Yuya Ong, Jayaram Radhakrishnan, Ashish Verma, Mathieu Sinn, et al.  IBM Federated Learning: an enterprise framework white paper v0. 1.  _arXiv preprint arXiv:2007.10987_ , 2020.  URL https://github.com/IBM/federated-learning-lib.
  * McMahan et al. (2017a) B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Proc. International Conference on Artificial Intelligence and Statistics_ , pages 1273–1282, Ft. Lauderdale, FL, 20–22 Apr 2017a.
  * McMahan et al. (2017b) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, 2017b.
  * Mostafa (2019) H. Mostafa.  Robust federated learning through representation matching and adaptive hyper-parameters.  _arXiv preprint arXiv:1912.13075_ , 2019.
  * Oh et al. (2019) Changyong Oh, Jakub M Tomczak, Efstratios Gavves, and Max Welling.  Combinatorial bayesian optimization using the graph cartesian product.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , pages 2914–2924, 2019.
  * Ong et al. (2020) Yuya Jeremy Ong, Yi Zhou, Nathalie Baracaldo, and Heiko Ludwig.  Adaptive histogram-based gradient boosted trees for federated learning.  _arXiv preprint arXiv:2012.06670_ , 2020.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, 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–2830, 2011\.
  * Reddi et al. (2020) 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.
  * Shahriari et al. (2016) 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\.
  * Vanschoren (2018) Joaquin Vanschoren.  Meta-learning: A survey.  _arXiv preprint arXiv:1810.03548_ , 2018.
  * Vanschoren et al. (2013) Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo.  OpenML: Networked science in machine learning.  _SIGKDD Explorations_ , 15(2):49–60, 2013.  doi: 10.1145/2641190.2641198.  URL http://doi.acm.org/10.1145/2641190.2641198.
  * Villani (2003) Cedric Villani.  Topics in optimal transportation.(books).  _OR/MS Today_ , 30(3):66–67, 2003.
  * Wang et al. (2019) 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.
  * Williams and Rasmussen (2006) Christopher K Williams and Carl Edward Rasmussen.  _Gaussian processes for machine learning_ , volume 2.  MIT press Cambridge, MA, 2006.
  * Wistuba et al. (2018) Martin Wistuba, Nicolas Schilling, and Lars Schmidt-Thieme.  Scalable gaussian process-based transfer surrogates for hyperparameter optimization.  _Machine Learning_ , 107(1):43–78, 2018.
  * Xu et al. (2020) Mengwei Xu, Yuxin Zhao, Kaigui Bian, Gang Huang, Qiaozhu Mei, and Xuanzhe Liu.  Federated neural architecture search.  _arxiv.2002.06352_ , 2020.

##  Appendix A Technical Definitions

###  A.1 Distance in $\boldsymbol{\Theta}$

Here we will define a distance metric
$d:\boldsymbol{\Theta}\times\boldsymbol{\Theta}\to\mathbb{R}_{+}$. Assuming we
have $m$ HPs, if $\boldsymbol{\Theta}\subset\mathbb{R}^{m}$, then there are
various distances available such as
$\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{\rho}$ (the
$\rho$-norm). The more general case is where we have $R$ continuous/real HPs,
$I$ integer HPs, and $C$ categorical HPs; $m=R+I+C$. In that case,
$\boldsymbol{\Theta}\subset\mathbb{R}^{R}\times\mathbb{Z}^{I}\times\mathbb{C}^{C}$,
and any
$\boldsymbol{\theta}=(\boldsymbol{\theta}_{\mathbb{R}},\boldsymbol{\theta}_{\mathbb{Z}},\boldsymbol{\theta}_{\mathbb{C}})\in\boldsymbol{\Theta}_{\mathbb{R}}\times\boldsymbol{\Theta}_{\mathbb{Z}}\times\boldsymbol{\Theta}_{\mathbb{C}}$,
where
$\boldsymbol{\theta}_{\mathbb{R}}\in\boldsymbol{\Theta}_{\mathbb{R}},\boldsymbol{\theta}_{\mathbb{Z}}\in\boldsymbol{\Theta}_{\mathbb{Z}},\boldsymbol{\theta}_{\mathbb{C}}\in\boldsymbol{\Theta}_{\mathbb{C}}$
respectively denote the continuous, integer and categorical HPs in
$\boldsymbol{\theta}$. Distances over $\mathbb{R}^{R}\times\mathbb{Z}^{I}$ is
available, such as $\rho$-norm. Let
$d_{\mathbb{R},\mathbb{Z}}:(\boldsymbol{\Theta}^{\mathbb{R}}\times\boldsymbol{\Theta}_{\mathbb{Z}})\times(\boldsymbol{\Theta}_{\mathbb{R}}\times\boldsymbol{\Theta}_{\mathbb{Z}})\to\mathbb{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 $\boldsymbol{\theta}_{\mathbb{C},k},k\in[C]$
have $n_{k}$ categories $\\{\xi_{k1},\xi_{k2},\ldots,\xi_{kn_{k}}\\}$. Then we
define a complete undirected graph $G_{k}=(V_{k},E_{k}),k\in[C]$ where

  * •

There is a node $N_{kj}$ in $G_{k}$ for each category $\xi_{kj}$ for each
$j\in[n_{k}]$ and $V_{k}=\\{N_{k1},\ldots N_{kn_{k}}\\}$.

  * •

There is an undirected edge $(N_{kj},N_{kj^{\prime}})$ for each pair
$j,j^{\prime}\in[n_{k}]$, and
$E_{k}=\\{(N_{kj},N_{kj^{\prime}}),j,j^{\prime}\in[n_{k}]\\}$.

Given the per-categorical HP graph $G_{k},k\in[C]$, we define the graph
Cartesian product $\mathsf{G}=\bigotimes_{k\in[C]}G_{k}$ and
$\mathsf{G}=(\mathsf{V},\mathsf{E})$ such that

  * •

$\mathsf{V}=\\{\mathsf{N}_{(j_{1},j_{2},\ldots,j_{C})}:(\xi_{1j_{1}},\xi_{2j_{2}},\ldots\xi_{kj_{k}},\ldots,\xi_{Cj_{C}})\in\boldsymbol{\Theta}_{\mathbb{C}},j_{k}\in[n_{k}]\forall
k\in[C]\\}$.

  * •

$\mathsf{E}=\\{(\mathsf{N}_{(j_{1},j_{2},\ldots,j_{C})},\mathsf{N}_{(j^{\prime}_{1},j^{\prime}_{2},\ldots,j^{\prime}_{C})}):\text{\sf
IFF}\exists t\in[C]\text{ such that }\forall
k\not=t,\xi_{kj_{k}}=\xi_{kj^{\prime}_{k}},\text{ and
}\exists(N_{tj_{t}},N_{tj^{\prime}_{t}})\in E_{t}\\}$.

Then for any
$\boldsymbol{\theta}_{\mathbb{C}},\boldsymbol{\theta}^{\prime}_{\mathbb{C}}\in\boldsymbol{\Theta}_{\mathbb{C}}$
with corresponding nodes $\mathsf{N},\mathsf{N}^{\prime}\in\mathsf{V}$, Oh et
al. [2019, Theorem 2.2.1] says that the length of the shortest path between
nodes $\mathsf{N}$ and $\mathsf{N}^{\prime}$ in $\mathsf{G}$ is a distance. We
can consider this distance as
$d_{\mathbb{C}}:\boldsymbol{\Theta}_{\mathbb{C}}\times\boldsymbol{\Theta}_{\mathbb{C}}\to\mathbb{R}_{+}$.
Of course, there are other ways of defining distances in the categorical
space.

Then we can define a distance
$d:(\boldsymbol{\Theta}_{\mathbb{R}}\times\boldsymbol{\Theta}_{\mathbb{Z}}\times\boldsymbol{\Theta}_{\mathbb{C}})\times(\boldsymbol{\Theta}_{\mathbb{R}}\times\boldsymbol{\Theta}_{\mathbb{Z}}\times\boldsymbol{\Theta}_{\mathbb{C}})\to\mathbb{R}_{+}$
between two HPs $\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}$ as

$d(\boldsymbol{\theta},\boldsymbol{\theta}^{\prime})=d_{\mathbb{R},\mathbb{Z}}((\boldsymbol{\theta}_{\mathbb{R}},\boldsymbol{\theta}_{\mathbb{Z}}),(\boldsymbol{\theta}^{\prime}_{\mathbb{R}},\boldsymbol{\theta}^{\prime}_{\mathbb{Z}}))+d_{\mathbb{C}}(\boldsymbol{\theta}_{\mathbb{C}},\boldsymbol{\theta}^{\prime}_{\mathbb{C}}).$
(A.1)

######  Proposition A.1.

Given distance metrics $d_{\mathbb{R},\mathbb{Z}}$ and $d_{\mathbb{C}}$, the
function $d:\boldsymbol{\Theta}\times\boldsymbol{\Theta}$ defined in (A.1) is
a valid distance metric.

###  A.2 Continuity in the space of HPs $\boldsymbol{\Theta}$

In the simple case, we can assume Lipschitz continuity of estimated loss
$\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})$ and the loss surface
$\widehat{\ell}_{i}(\boldsymbol{\theta}),i\in[p]$ as follows:

$\displaystyle|\ell(\boldsymbol{\theta},\mathcal{D})-\ell(\boldsymbol{\theta}^{\prime},\mathcal{D})|$
$\displaystyle\leq\tilde{L}(\mathcal{D})\cdot
d(\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}),$ (A.2)
$\displaystyle|\widehat{\ell}_{i}(\boldsymbol{\theta})-\widehat{\ell}_{i}(\boldsymbol{\theta}^{\prime})|$
$\displaystyle\leq\widehat{L}\cdot
d(\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}).$ (A.3)

For a more general handling, we can consider the notion of modulus of
continuity in the form of a increasing real-valued functions
$\omega:\mathbb{R}_{+}\to\mathbb{R}_{+}$ with $\lim_{t\to
0}\omega(t)=\omega(0)=0$. Then we can say that the estimated loss
$\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})$ and the loss surface
$\ell_{i}(\boldsymbol{\theta})$ admits $\tilde{\omega}_{\mathcal{D}}$ and
$\widehat{\omega}$ as a modulus of continuity (respectively) if

$\displaystyle|\ell(\boldsymbol{\theta},\mathcal{D})-\ell(\boldsymbol{\theta}^{\prime},\mathcal{D})|$
$\displaystyle\leq\tilde{\omega}_{\mathcal{D}}(d(\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}))$
(A.4)
$\displaystyle|\widehat{\ell}_{i}(\boldsymbol{\theta})-\widehat{\ell}_{i}(\boldsymbol{\theta}^{\prime})|$
$\displaystyle\leq\widehat{\omega}(d(\boldsymbol{\theta},\boldsymbol{\theta}^{\prime})).$
(A.5)

If we further assume that $\tilde{\omega}_{\mathcal{D}},\widehat{\omega}$ to
be concave, then we can say that these functions are sublinear as follows:

$\displaystyle\tilde{\omega}_{\mathcal{D}}(t)$
$\displaystyle\leq\tilde{A}_{\mathcal{D}}\cdot t+\tilde{B}_{\mathcal{D}},$
(A.6) $\displaystyle\widehat{\omega}(t)$ $\displaystyle\leq\widehat{A}\cdot
t+\widehat{B}.$ (A.7)

These conditions give us (indirectly) something similar in spirit to the
guarantees of Lipschitz continuity, but is a more rigorous way of achieving
such guarantees.

##  Appendix B Proofs for optimality analysis

We provide detailed proofs of the propositions stated in Section 4.

###  B.1 Proof of Proposition 4.6

###### Proof.

Consider the definition of $\widehat{\boldsymbol{\theta}}^{\star}$ and
$\boldsymbol{\theta}^{\star}$, we can obtain

$\displaystyle\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta}^{\star},\mathcal{D})$
$\displaystyle=\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})-\widehat{\ell}(\widehat{\boldsymbol{\theta}}^{\star})+\widehat{\ell}(\widehat{\boldsymbol{\theta}}^{\star})-\widehat{\ell}(\boldsymbol{\theta}^{\star})+\widehat{\ell}(\boldsymbol{\theta}^{\star})-\tilde{\ell}(\boldsymbol{\theta}^{\star},\mathcal{D})$
$\displaystyle\leq
2\max_{\boldsymbol{\theta}\in\bar{\boldsymbol{\Theta}}\subset\boldsymbol{\Theta}}\left|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})-\widehat{\ell}(\boldsymbol{\theta})\right|,$

where the inequality follows from the fact that
$\widehat{\ell}(\widehat{\boldsymbol{\theta}}^{\star})-\widehat{\ell}(\boldsymbol{\theta}^{\star})\leq
0$. Moreover, observe that for any
$\boldsymbol{\theta}\in\bar{\boldsymbol{\Theta}}\subset\boldsymbol{\Theta}$,
by the definition of $\widehat{\ell}(\boldsymbol{\theta})$ in (4.2), we have

$\displaystyle|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})-\widehat{\ell}(\boldsymbol{\theta})|$
$\displaystyle=\left|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})-\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\cdot\widehat{\ell}_{i}(\boldsymbol{\theta})\right|$
$\displaystyle=\left|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})-\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\cdot\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})+\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\cdot\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})-\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\cdot\widehat{\ell}_{i}(\boldsymbol{\theta})\right|$
$\displaystyle\leq\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\left|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})\right|+\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\left|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})-\widehat{\ell}_{i}(\boldsymbol{\theta})\right|$
$\displaystyle\leq\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\tilde{\beta}(\boldsymbol{\theta})\mathcal{W}_{1}(\mathcal{D},\mathcal{D}_{i})+\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\epsilon_{i}(\boldsymbol{\theta},T),$

where the last inequality follows from assumption (4.6) and definition (4.10).
∎

###  B.2 Proof of Proposition 4.7

###### Proof.

By the definition of 1-Wasserstein distance in (4.3) and the fact that
$\mathcal{D}=\sum_{i\in[p]}w_{i}\mathcal{D}_{i}$, we can obtain

$\displaystyle\mathcal{W}_{1}(\mathcal{D},\mathcal{D}_{i})$
$\displaystyle=\sup_{f\in\mathsf{F}_{1}}\mathbb{E}_{(x,y)\sim\mathcal{D}}f(x,y)-\mathbb{E}_{(x_{i},y_{i})\sim\mathcal{D}_{i}}f(x_{i},y_{i})$
$\displaystyle=\sup_{f\in\mathsf{F}_{1}}\textstyle{\sum}_{j\in[p]}w_{j}\mathbb{E}_{(x_{j},y_{j})\sim\mathcal{D}_{j}}f(x_{j},y_{j})-\mathbb{E}_{(x_{i},y_{i})\sim\mathcal{D}_{i}}f(x_{i},y_{i})$
$\displaystyle=\sup_{f\in\mathsf{F}_{1}}\textstyle{\sum}_{i\not=j,j\in[p]}w_{j}\left(\mathbb{E}_{(x_{j},y_{j})\sim\mathcal{D}_{j}}f(x_{j},y_{j})-\mathbb{E}_{(x_{i},y_{i})\sim\mathcal{D}_{i}}f(x_{i},y_{i})\right)$
$\displaystyle\leq\textstyle{\sum}_{i\not=j,j\in[p]}w_{j}\left(\sup_{f\in\mathsf{F}_{1}}\mathbb{E}_{(x_{j},y_{j})\sim\mathcal{D}_{j}}f(x_{j},y_{j})-\mathbb{E}_{(x_{i},y_{i})\sim\mathcal{D}_{i}}f(x_{i},y_{i})\right)$
$\displaystyle\leq\textstyle{\sum}_{i\not=j,j\in[p]}w_{j}\mathcal{W}_{1}(\mathcal{D}_{j},\mathcal{D}_{i}).$

∎

###  B.3 Proof of Proposition 4.8

###### Proof.

By the definition of $\epsilon_{i}(\boldsymbol{\theta},T)$

$\displaystyle\epsilon_{i}(\boldsymbol{\theta},T)$
$\displaystyle=\left|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})-\widehat{\ell}_{i}(\boldsymbol{\theta})\right|$
$\displaystyle=\left|\underbrace{\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})-\tilde{\ell}(\boldsymbol{\theta}_{t}^{(i)},\mathcal{D}_{i})}_{\text{Smoothness
of
}\tilde{\ell}}+\underbrace{\tilde{\ell}(\boldsymbol{\theta}_{t}^{(i)},\mathcal{D}_{i})-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})}_{\text{Modeling
error}}+\underbrace{\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})-\widehat{\ell}_{i}(\boldsymbol{\theta})}_{\text{Smoothness
of }\widehat{\ell}}\right|,$

where $\boldsymbol{\theta}_{t}^{(i)},t\in[T]$ is any one of the HP tried
during local HPO run on party $i\in[p]$.

First note that

$\displaystyle|\tilde{\ell}(\boldsymbol{\theta}_{t}^{(i)},\mathcal{D}_{i})-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})|$
$\displaystyle=|\mathcal{L}_{t}^{(i)}-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})|$
$\displaystyle\leq\max_{t}|\mathcal{L}_{t}^{(i)}-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})|$
$\displaystyle\leq\delta_{i}.$

In view of (4.4) and (4.6), we have

$\displaystyle\epsilon_{i}(\boldsymbol{\theta},T)$
$\displaystyle\leq\tilde{L}(\mathcal{D}_{i})d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)})+\delta_{i}+\widehat{L}_{i}d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)}),$

which immediately implies the result in (4.13). ∎

###  B.4 Proposition 4.8 using modulus of continuity instead of Lipschitz
continuity

######  Proposition B.1.

Assume that the estimated loss
$\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})$ and the loss surface
$\ell_{i}(\boldsymbol{\theta})$ admit concave functions
$\tilde{\omega}_{\mathcal{D}_{i}}$ and $\widehat{\omega}_{i}$ respectively as
a modulus of continuity with respect to
$\boldsymbol{\theta}\in\boldsymbol{\Theta}$ for each party $i\in[p]$. Then,
for any party $i,\ i\in[p]$, with the set of (HP, loss) pairs
$\\{(\boldsymbol{\theta}_{t}^{(i)},\mathcal{L}_{t}^{(i)})\\}_{t\in[T]}$
collected during the local HPO run for party $i$, for any
$\boldsymbol{\theta}\in\bar{\boldsymbol{\Theta}}\subset\boldsymbol{\Theta}$,
there exists
$\tilde{A}_{\mathcal{D}_{i}},\widehat{A}_{i},\tilde{B}_{\mathcal{D}_{i}},\widehat{B}_{i}\geq
0$ such that

$\epsilon_{i}(\boldsymbol{\theta},T)\leq\left(\tilde{A}_{\mathcal{D}_{i}}+\widehat{A}_{i}\right)\min_{t\in[T]}d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)})+\tilde{B}_{\mathcal{D}_{i}}+\widehat{B}_{i}+\delta_{i},$
(B.1)

where
$\delta_{i}=\max_{t}|\mathcal{L}_{t}^{(i)}-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})|$
is the maximum per sample training error for the local loss surface
$\widehat{\ell}_{i}$.

###### Proof.

By the definition of $\epsilon_{i}(\boldsymbol{\theta},T)$

$\displaystyle\epsilon_{i}(\boldsymbol{\theta},T)$
$\displaystyle=\left|\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})-\widehat{\ell}_{i}(\boldsymbol{\theta})\right|$
$\displaystyle=\left|\underbrace{\tilde{\ell}(\boldsymbol{\theta},\mathcal{D}_{i})-\tilde{\ell}(\boldsymbol{\theta}_{t}^{(i)},\mathcal{D}_{i})}_{\text{Smoothness
of
}\tilde{\ell}}+\underbrace{\tilde{\ell}(\boldsymbol{\theta}_{t}^{(i)},\mathcal{D}_{i})-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})}_{\text{Modeling
error}}+\underbrace{\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})-\widehat{\ell}_{i}(\boldsymbol{\theta})}_{\text{Smoothness
of }\widehat{\ell}}\right|,$

where $\boldsymbol{\theta}_{t}^{(i)},t\in[T]$ is any one of the HP tried
during local HPO run on party $i\in[p]$.

First note that

$\displaystyle|\tilde{\ell}(\boldsymbol{\theta}_{t}^{(i)},\mathcal{D}_{i})-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})|$
$\displaystyle=|\mathcal{L}_{t}^{(i)}-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})|$
$\displaystyle\leq\max_{t}|\mathcal{L}_{t}^{(i)}-\widehat{\ell}_{i}(\boldsymbol{\theta}_{t}^{(i)})|$
$\displaystyle\leq\delta_{i}.$

In view of (A.4) and (A.5), we have

$\displaystyle\epsilon_{i}(\boldsymbol{\theta},T)$
$\displaystyle\leq\tilde{\omega}_{\mathcal{D}_{i}}(d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)}))+\delta_{i}+\widehat{\omega}(d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)})),$
$\displaystyle\leq\delta_{i}+\min_{t\in[T]}\left(\tilde{\omega}_{\mathcal{D}_{i}}(d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)}))+\widehat{\omega}(d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)}))\right).$

Concavity of a function $\omega:[0,\infty]\to[0,\infty]$ implies that there
exists $A,B>0$ such that $\omega(t)\leq At+B$. Using that, we can find some
$\tilde{A}_{\mathcal{D}_{i}},\widehat{A}_{i},\tilde{B}_{\mathcal{D}_{i}},\widehat{B}_{i}>0$
which allows us to simplify the above to

$\displaystyle\epsilon_{i}(\boldsymbol{\theta},T)$
$\displaystyle\leq\delta_{i}+(\tilde{A}_{\mathcal{D}_{i}}+\widehat{A})\cdot\min_{t\in[T]}d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)})+(\tilde{B}_{\mathcal{D}_{i}}+\widehat{B}).$

∎

###  B.5 Relative regrets

As a byproduct, we can also provide a bound for the following relative regret
we use in our experiments.

######  Corollary B.2.

Let us assume $\widehat{\boldsymbol{\theta}}^{\star}$ and
$\boldsymbol{\theta}^{\star}$ are defined in (3.7) and (4.7), and
$\bar{\boldsymbol{\theta}}^{\star}$ and $\boldsymbol{\theta}_{b}$ 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 $\mathcal{D}$, we have

$\displaystyle\frac{\tilde{\ell}(\bar{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})}{\tilde{\ell}(\bar{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta}_{b},\mathcal{D})}$
$\displaystyle\quad\leq\frac{2\max_{\boldsymbol{\theta}\in\bar{\boldsymbol{\Theta}}}\textstyle{\sum}_{i\in[p]}\alpha_{i}(\boldsymbol{\theta})\left\\{\tilde{\beta}(\boldsymbol{\theta})\textstyle{\sum}_{j\in[p],j\not=i}w_{j}\mathcal{W}_{1}(\mathcal{D}_{j},\mathcal{D}_{i})+\left(\tilde{L}(\mathcal{D}_{i})+\widehat{L}_{i}\right)\min_{t\in[T]}d(\boldsymbol{\theta},\boldsymbol{\theta}_{t}^{(i)})+\delta_{i}\right\\}}{\widehat{\ell}(\boldsymbol{\theta}_{b},\mathcal{D})-\widehat{\ell}(\bar{\boldsymbol{\theta}}^{\star},\mathcal{D})}.$
(B.2)

###### Proof.

By the definition of relative regret, we have

$\displaystyle\frac{\tilde{\ell}(\bar{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})}{\tilde{\ell}(\bar{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta}_{b},\mathcal{D})}$
$\displaystyle=\frac{\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\bar{\boldsymbol{\theta}}^{\star},\mathcal{D})}{\tilde{\ell}(\boldsymbol{\theta}_{b}.\mathcal{D})-\tilde{\ell}(\bar{\boldsymbol{\theta}}^{\star},\mathcal{D})}$
$\displaystyle\leq\frac{\tilde{\ell}(\widehat{\boldsymbol{\theta}}^{\star},\mathcal{D})-\tilde{\ell}(\boldsymbol{\theta}^{\star},\mathcal{D})}{\widehat{\ell}(\boldsymbol{\theta}_{b},\mathcal{D})-\widehat{\ell}(\bar{\boldsymbol{\theta}}^{\star},\mathcal{D})},$

where the last inequality follows from the fact that
$\boldsymbol{\theta}^{\star}$ is the minimizer of
$\tilde{\ell}(\boldsymbol{\theta},\mathcal{D})$. Moreover, in view of the
result in Theorem 4.5, the result in (B.2) follows. ∎

##  Appendix C Experimental Setting

###  C.1 Dataset details

The details of the binary classification datasets used in our evaluation is
reported in Table 4. We report the 10-fold cross-validated 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 §C.3 denote
the difference between the best 10-fold cross-validated balanced accuracy
obtained via centralized HPO and the 10-fold cross-validated balanced accuracy
of the default HP configuration.

Table 4: OpenML binary classification dataset details Data | rows | columns | class sizes
---|---|---|---
EEG eye state | 14980 | 14 | (8257, 6723)
Electricity | 45312 | 8 | (26075, 19237)
Heart statlog | 270 | 13 | (150, 120)
Oil spill | 937 | 49 | (896, 41)
Pollen | 3848 | 5 | (1924, 1924)
Sonar | 208 | 61 | (111, 97)
PC3 | 1563 | 37 | (1403, 160)

###  C.2 Search space

We use the search space definition used in the NeurIPS 2020 Black-box
optimization challenge (https://bbochallenge.com/), described in details in
the API
documentation222https://github.com/rdturnermtl/bbo_challenge_starter_kit/#configuration-
space.

####  C.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 HistGradientBoostingClassifier in scikit-learn:

    api_config = {
        "max_iter": {"type": "int", "space": "linear", "range": (10, 200)},
        "learning_rate": {"type": "real", "space": "log", "range": (1e-3, 1.0)},
        "min_samples_leaf": {"type": "int", "space": "linear", "range": (1, 40)},
        "l2_regularization": {"type": "real", "space": "log", "range": (1e-4, 1.0)},
    }

The HP configuration we consider for the single-shot baseline described in §5
is as follows:

    config = {
        "max_iter": 100,
        "learning_rate": 0.1,
        "min_samples_leaf": 20,
        "l2_regularization": 0,
    }

####  C.2.2 Kernel SVM with RBF kernel

For SVC(kernel="rbf") in scikit-learn, we use the following search space:

    api_config = {
        "C": {"type": "real", "space": "log", "range": (0.01, 1000.0)},
        "gamma": {"type": "real", "space": "log", "range": (1e-5, 10.0)},
        "tol": {"type": "real", "space": "log", "range": (1e-5, 1e-1)},
    }

The single shot baseline we consider for SVC from Auto-sklearn [Feurer et al.,
2015] is:

    config = {
        "C": 1.0,
        "gamma": 0.1,
        "tol": 1e-3,

####  C.2.3 Multi-Layered Perceptrons

For the MLPClassifier(solver="adam") from scikit-learn, we consider both
architectural HP such as hidden-layer-sizes as well as optimizer parameters
such as alpha and learning-rate-init for the Adam optimizer [Kingma and Ba,
2015]. We consider the following search space:

    api_config = {
        "hidden_layer_sizes": {"type": "int", "space": "linear", "range": (50, 200)},
        "alpha": {"type": "real", "space": "log", "range": (1e-5, 1e1)},
        "learning_rate_init": {"type": "real", "space": "log", "range": (1e-5, 1e-1)},
    }

We utilize the following single shot baseline:

    config = {
        "hidden_layer_sizes: 100,
        "alpha": 1e-4,
        "learning_rate_init": 1e-3,
    }

We fix the remaining HPs of MLPClassifier as with values used by Auto-sklearn.

    activation="relu",
    early_stopping=True,
    shuffle=True,
    batch_size="auto",
    tol=1e-4,
    validation_fraction=0.1,
    beta_1=0.9,
    beta_2=0.999,
    epsilon=1e-8,

###  C.3 Detailed results of comparison against baselines

Here we present the relevant details and the performance of FLoRA on the FL-
HPO of (i) histograms based gradient boosted trees (HGB) in Table 5), (ii)
nonlinear support vector machines (SVM) in Table 6, and (iii) multi-layered
perceptrons (MLP) in Table 7. We use the search spaces and the single-shot
baselines presented in §C.2. We utilize all 7 datasets for each of the method
except for the Electricity dataset with SVM because of the infeasible amount
of time taken by SVM on 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”
$:=\min_{i\in[p]}\max_{t}(1-\tilde{\ell}(\boldsymbol{\theta}_{t}^{(i)},\mathcal{D}_{i}))$

  * •

the maximum accuracy of the best local HP across all parties “PMax”
$:=\max_{i\in[p]}\max_{t}(1-\tilde{\ell}(\boldsymbol{\theta}_{t}^{(i)},\mathcal{D}_{i}))$

  * •

$\gamma_{p}=\nicefrac{{\text{PMax}}}{{\text{PMin}}}$, and finally

  * •

the regret for each of the considered loss surfaces in FLoRA.

For each of the three methods, we also report the aggregate performance over
all considered datasets in terms of mean $\pm$ standard deviation
(“mean$\pm$std”), inter-quartile range (“IQR”), Wins/Ties/Losses of FLoRA with
respect to the single-shot baseline (“W/T/L”), and a 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 is negative (implying
FLoRA improves over the baseline).’ These aggregate metrics are collected in
Table 8 along with a set of final aggregate metrics across all datasets and
methods.

Table 5: 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.16 | 82.16
EEG Eye State | 89.96 | 94.66 | 4.70 | 91.80 | 92.29

Data | $\gamma_{p}$ | 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
mean$\pm$std |  |  0.56 $\pm$ 0.37 |  0.52 $\pm$ 0.32 |  0.47 $\pm$ 0.31 |  0.45 $\pm$ 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.02126) | (27, 0.01400) | (28, 0.00898) | (28, 0.00898)

##### HGB.

The results in Table 5 indicate that, in almost all cases, with all loss
functions, FLoRA is able to improve upon the baseline to varying degrees
(there is only one case where SGM performs worse than the baseline on Sonar).
On average (across the datasets), SGM+U, MPLM and APLM perform better than SGM
as we expected. MPLM performs better than SGM both in terms of average and
standard deviation. Looking at the individual datasets, we see that, for
datasets with low $\gamma_{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 $\gamma_{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).

Table 6: 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 | $\gamma_{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
Heart 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
mean$\pm$std |  |  0.56 $\pm$ 0.57 |  0.59 $\pm$ 0.58 |  1.95 $\pm$ 2.35 |  0.72 $\pm$ 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)

##### SVM.

For SVM we continue with the datasets selected using HGB (datasets with a
“Gap” of at least 3%). Of the 7 datasets (Table 4), 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 6 datasets in this evaluation and
present the corresponding results in Table 6. Of the 6, note that 2 of these
datasets (Pollen, Heart Statlog) have really small “Gap” (highlighted in red
in Table 6). Moreover, 2 of the datasets (Heart statlog, Oil Spill) also have
really high $\gamma_{p}$ indicating a high level of heterogeneity between the
per-party distributions (again highlighted in red). In this case, there are a
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 6),
but both these cases either have a small or moderate “Gap” and/or have a high
$\gamma_{p}$. Moreover, in one case, MPLM incurs a regret of 6.8, but this is
a case with really high $\gamma_{p}=1.14$ – MPLM rejects any HP that has a low
score in even one of the parties, and in that process reject all promising HPs
since the local HPOs on these disparate distributions did not concentrate on
the same region of the HP space, thereby incuring a high MPLM loss in almost
all regions of the HP where some local HPO focused on. Other than these
expected hard cases, FLoRA is able to improve upon the baseline in most cases,
and achieve optimal performance (zero regret) in a few cases (EEG Eye State,
Heart Statlog).

Table 7: 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 | $\gamma_{p}$ | 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
mean$\pm$std |  |  0.80 $\pm$ 0.53 |  0.83 $\pm$ 0.37 |  0.78 $\pm$ 0.40 |  0.74 $\pm$ 0.34
IQR |  | [0.36, 0.80, 0.97] | [0.48, 0.99, 1.01] | [0.47, 0.89, 1.00] | [0.46, 0.79, 0.95]
WTL |  | 6/0/1 | 4/1/2 | 5/1/1 | 6/0/1
WSRT |  | (21, 0.11836) | (15, 0.17272) | (18, 0.05793) | (24, 0.04548)

##### MLP.

We consider all 7 datasets for the evaluation of FLoRA on FL-HPO for MLP HPs
and present the results in Table 7. As with SVM, there are a few datasets with
a small room for improvement (“Gap”) and/or high $\gamma_{p}$, again
highlighted in red in Table 7. In some of 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 baseline, with APLM performing the best.

Table 8: Aggregate Table Agg. | Method | SGM | SGM+U | MPLM | APLM
---|---|---|---|---|---
mean $\pm$ std. | HGB |  0.56 $\pm$ 0.37 |  0.52 $\pm$ 0.32 |  0.47 $\pm$ 0.31 |  0.45 $\pm$ 0.23
| SVM |  0.56 $\pm$ 0.57 |  0.59 $\pm$ 0.58 |  1.95 $\pm$ 2.35 |  0.72 $\pm$ 0.76
| MLP |  0.80 $\pm$ 0.53 |  0.83 $\pm$ 0.37 |  0.78 $\pm$ 0.40 |  0.74 $\pm$ 0.34
| Overall | 0.64 $\pm$ 0.51 | 0.64 $\pm$ 0.51 |  1.02 $\pm$ 1.46 | 0.63 $\pm$ 0.50
IQR | 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]
| SVM | [0.04, 0.38, 1.11] | [0.04, 0.48, 1.07] | [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.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 1 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.17272)
| MLP | (21, 0.11836) | (15, 0.17272) | (18, 0.05793) | (24, 0.04548)
| Overall | (174, 0.00499) | (164, 0.00272) | (141, 0.03206) | (183.5, 0.00169)

##### Aggregate.

The results for all the methods and datasets are aggregated in Table 8. 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 to $10^{-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.

###  C.4 Effect of the number of local HPO rounds per party

In this experiment, we report additional results to study the effect of the
“thoroughness” of the local HPO runs (in terms of the number of HPO rounds
$T$) on the overall performance of FLoRA for all the loss surfaces in Table 9.
In almost all cases, FLoRA does not require $T$ to be too large to get enough
information about the local HPO loss surface to get to its best possible
performance.

Table 9: Effect of $T$. Method | data | $T$ | $\gamma_{p}$ | SGM | SGM+U | MPLM | APLM
---|---|---|---|---|---|---|---
MLP | Heart Statlog | 5 | 1.13 | 0.58 | 0.33 | 0.22 | 0.56
|  | 10 | 1.13 | 0.33 | 0.16 | 0.60 | 0.39
|  | 20 | 1.13 | 0.49 | 0.15 | 0.24 | 0.44
|  | 40 | 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 | 5 | 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
|  | 40 | 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 | 5 | 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
|  | 40 | 1.06 | 0.17 | 0.17 | 0.22 | 0.27
|  | 60 | 1.06 | 0.17 | 0.17 | 0.17 | 0.17
|  | 80 | 1.06 | 0.17 | 0.11 | 0.27 | 0.17
SVM | EEG | 5 | 1.03 | -0.01 | -0.01 | 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
|  | 40 | 1.03 | -0.02 | -0.02 | 0.01 | 0.00
|  | 60 | 1.03 | -0.01 | -0.01 | 0.02 | 0.03
|  | 80 | 1.03 | -0.01 | -0.01 | 0.01 | -0.0‘

###  C.5 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 $T=100$ rounds of local
asynchronous HPO. However, instead of sending all $T$ (HP, loss) pairs, we
consider sending $T^{\prime}<T$ of the “best” (HP, loss) pairs – that is, (HP,
loss) pairs with the $T^{\prime}$ lowest losses. Changing the value of
$T^{\prime}$ trades off the communication overhead of the FLoRA step where the
aggregators collect the per-party loss pairs (Algorithm 1, line 5). We
consider 2 datasets each for 2 of the methods (SVM, MLP) and all the loss
surfaces for FLoRA, and report all the results in Table 10.

Table 10: Effect of the number of best (HP, loss) pairs $T^{\prime}<T$ sent to aggregator by each party after doing local HPO with $T=100$. Method | data | $T^{\prime}<T$ | $\gamma_{p}$ | SGM | SGM+U | MPLM | APLM
---|---|---|---|---|---|---|---
MLP | Heart Statlog | 5 | 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
|  | 60 | 1.13 | 0.38 | 0.22 | 0.31 | 0.32
|  | 80 | 1.13 | 0.34 | 0.38 | 0.22 | 0.33
MLP | Sonar | 5 | 1.14 | 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
|  | 60 | 1.14 | 0.10 | 0.33 | 0.55 | 0.26
|  | 80 | 1.14 | 0.47 | 0.41 | 0.34 | 0.32
SVM | EEG Eye State | 5 | 1.03 | -0.02 | -0.01 | 0.39 | 1.02
|  | 10 | 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
|  | 80 | 1.03 | -0.01 | -0.01 | -0.01 | -0.01
SVM | Sonar | 5 | 1.06 | 0.17 | 0.17 | 0.43 | 1.43
|  | 10 | 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
|  | 80 | 1.06 | 0.17 | 0.43 | 0.27 | 0.17