Budgeted Online Model Selection and Fine-Tuning via Federated Learning
Authors: Pouya M. Ghari
Yanning Shen
Venue: Accepted by TMLR ()

Abstract: Online model selection involves selecting a model from a set of candidate models `on the fly' to perform prediction on a stream of data. The choice of candidate models henceforth has a crucial impact on the performance. Although employing a larger set of candidate models naturally leads to more flexibility in model selection, this may be infeasible in cases where prediction tasks are performed on edge devices with limited memory. Faced with this challenge, the present paper proposes an online federated model selection framework where a group of learners (clients) interacts with a server with sufficient memory such that the server stores all candidate models. However, each client only chooses to store a subset of models that can be fit into its memory and performs its own prediction task using one of the stored models. Furthermore, employing the proposed algorithm, clients and the server collaborate to fine-tune models to adapt them to a non-stationary environment. Theoretical analysis proves that the proposed algorithm enjoys sub-linear regret with respect to the best model in hindsight. Experiments on real datasets demonstrate the effectiveness of the proposed algorithm.

Published in Transactions on Machine Learning Research (02/2024)
Budgeted Online Model Selection and Fine-Tuning via Federated Learning
Pouya M. Ghari
pmollaeb@uci.co edu
Deportment of Electrical Engineering and Computer Science Center for Pervasive Communications and Computing University of California Irvine
Yanning Shen"
yavnnings@@uci.cm edu
Deportment of Electricol Engineering and Computer Science
Center for Pervasive Communications and Computing University of California Iroine
Reviewed on OpenReview: https: openreview. net/forun?s id= WeaRRSN87X
Abstract
Online model selection involves selecting a model from a set of candidate models 'on the fly' to perform prediction on a stream of data. The choice candidate models henceforth has a crucial impact on the performance. Although employing a larger set of candidate models naturally leads more fiexibility in model selection, this may be infeasible in cases where prediction tasks are performed on edge devices with limited memory. Faced with this challenge, the present paper proposes online federated model selection framework where group of learners (clients) interacts with server with sufficient memory such that the server stores all candidate models. However, each client only chooses to store a subset of models that can be fit into its memory and performs its own prediction task using one of the stored models. Furthermore, employing the proposed algorithm, clients and the server collaborate to fine-tune models lo adapt them non-stat ionary environment. Theoretical analysis proves that the proposed algorithm enjoys sub-linear regret with respect to the best model in hindsight. Experiments real datasets demonstrate the effectiveness of the proposed algorithm.
1 Introduction
The performance of prediction tasks can be heavily influenced by the choice of model. As a result, the problem of model selection arises in various applications and studies, such as reinforcement learning (scc, c.g., DDai et al. 2020 Farahmand & Szepesvari 2011 Lee al. 2021 )) where a learner selects a model from a set. of candidate models to be deployed for prediction. Furthermore, in practical scenarios, data often arrives in sequential manner, rendering the storage and processing of data in batches impractical. Consequently, there is need to conduct model selection in online fashion. In this regard, the learner chooses one model among diclionary of models at each learning round, and after performing prediction with the chosen model, the learner incurs a loss. The best model in hindsight refers to the model with minimum cunulative loss over all learning rounds while regret is defined as the difference between the loss of the chosen model and the best model hindsight. Performing model selection online, the goal to minimize cumulative regret. Depending on the available information about the loss, different online model selection algorithms have been proposed in the literature (see, e.g.,, (Foster al., 2017 Muthhukunar al. 2019 Foster et. al., 2019 Cella
et al. 2021 Pacchiano et. al.) 2020 Reza Karimi et al.) 2021)) which are proven to achieve sub-linear regret.
The performance of existing online model selection algorithms depends on the performance of models in the
* *Corresponding author: Yanning Shen. Work in this paper was supported by NSF FCCS 2207457.

---

Published in Transactions on Machine Learning Research (02/2024)
dictionary. The choice of dictionary requires information about the performance of models on unseen data, which may not be available a priori. In this case, richer dictionary of models may improve the performance. However, in practice, the learner may face storage limitations, making storing and operating with a large dictionary infeasible. For example, consider the Iearner as an edge device performing an online prediction task such as image or document classification using a set of pre-trained models. In this case, the learner may be unable to store all models in the memory. Faced with this challenge, the present work aims at answering the following critical question: How can learners perform online model selection with a large dictionary of models that requires memory beyond their storage capacity?
To tackle this problem, the present paper proposes an online federated model selection and fine-tuning algorithm called OFMS-FT to enable a group of learners to perform online prediction employing a large dictionary of models. To this end, the online model selection is performed in a federated manner in the sense that the group of learners, also known as clients, interacts with a server to choose a model among all models stored in the server. Specifically, a server with a significantly larger storage capacity than clients stores a large number of models. At each round, each client chooses to receive and store subset of models that can be fit into its memory and performs its prediction using one of the stored models. Each client computes the losses of received models and leverages these observed losses to select model for prediction in future rounds. Moreover, the distribution of data streams observed by clients may differ from the distribution of data that models are pre-trained on. At each round, clients employ the proposed OFMS-FT to adapt models to their data and send the updates to the server. Upon receiving updates from clients, the server updates models.
In addition to the storage capacity of clients, there are some other challenges that should be taken into account. Communication efficiency is a critical issue in federated learning (see e.g., (Konečný et al. 2017 Karimireddy et al. 2020 Rothchild et al. 2020 Hamer et al., 2020 The available bandwidth for client-to-serve communication is usually limited which restricts the amount of information that can be sent to the server. To deal with limited communication bandwidth, using the proposed OFMS-FT, at each round the server chooses a subset of clients to fine-tune their received models. Morcover, in some cases, the distribution of data samples may be different across clients (Smith el al., 2017 Zhang et al.) 2021a Li el al. 2021b). Thus, different clients can have different models as the best model in hindsight. Through regret analysis, it is proven that by employing OFMS-FT, each client enjoys sub-linear regret with respect to its best model in hindsight. This shows that OFMS-FT effectively deals with heterogencous data distributions among clients. In addition, the regret analysis of the present paper proves that the server achieves sub-linear regret with respect to the best model in hindsight. Furthermore, regret analysis shows that increase in communication bandwidth and memory of clients improves the regret bounds. This indicates efficient usage of resources by OFM--FT. Experiments on regression and image classification datasets showcase the effectiveness of OFMS-FT compared with state-of-tho-art alternatives.
2 Problem Statement
Consider set of N clients interacting with server to perform sequential prediction. There are set of K models fi fi(:-),...; (x((s)) stored at the server. The set of models Ji fi(:))...., ".....,,[([;]] fx((;)) is called dictionary of models. Due to clients' limited memory, clients are not able to store all models
and a server with larger storage capacity stores models. Let [K] denote the set {l,..., KJ. At each learning round t, client i receives a data sample Hi, and makes a prediction for Hi,e- Specifically, at learning round t, client picks a model among the dictionary of models fi(::),.... fx(:). (x3-)) and makes prediction St,, (Zi.:; (1,,,)) where Ii, denote the index of the chosen model by client learning round f and OR,t represents the parameter of model i at learning round t. After making prediction, client i, Vi E [N] incurs loss L(fr. (Z..; 1),..)), vi,)) and observes label Ye. associated with T,,t. This continues until the time horizon T. The loss function L(.-)) is the same across all clients and depends on the task performed by clients. For example, if clients perform regression lasks, the loss function -(.,)) can be the mean square error function while if clients perform classification tasks the loss function -(.-)) can be chosen to be cross-entropy loss function. Furthermore, the present paper studies the adversarial setting where the label Vr, for any i and determined by the environment through a process unknown to clients. This means that the distribution of the data stream (a (== observed by client can be non-stationary (i.e., it can change over learning rounds) while client.
2

---

Published in Transactions on Machine Learning Research (02/2024)
i, Vi [N] does not know the distribution from which (ær,, Br.),, Vt is sampled. Moreover, data distribution can be different across clients.
The performance of clients can be measured through the notion of regret which is the difference between the client's 's incurred loss and that of the best model in hindsight. Therefore, the regret of the i-th client can be formalized as
T E. [CC[ 01. 0l...)..1..))
R
Σ C(fa(asstti Ok.), wt.), RE K
min
(1)
where [.[-] denote the conditional expectation given observed losses in prior learning rounds. The objective for each client is to minimize their regret by choosing model from dictionary in each learning round. This can be accomplished if clients can identify subset of models that perform well with the data they have observed. Assessing the losses of multiple models, including the selected one, can help clients better evaluate model performance. This can expedite the identification of models with superior performance, ultimately reducing prediction loss. However, due to memory constraints, clients cannot compute the loss for all models. To address this limitation, clients must select subset of models that can fit within their memory and calculate the loss for this chosen subset. This information aids in selecting a model for future learning rounds. Furthermore, to enhance model performance, clients and the server collaborate fine-tuning models. Let 0% be the optimal parameter for the k-th model which is defined as
0% arg min ΣΣ (().(a).)......)))
(2)
In this context, the regret of the server in fine-tuning model defined as
N T
N
T
SK. N
ΣΣ
C(Je(an; va.)) - N
(() Σ M
(3)
The objective of the server is to orchestrate model fine-tuning to minimize its regrets. This paper introduces an algorithmic framework designed to enable clients with limited memory to conduct online model selection demonstraates that employing this algorithm leads to sub-linear regret for clients and the server. Additionally, the analysis in Section illustrates that increasing the memory budget for clients results in tighter upper bound on regret for the proposed algorithm.
and fine-tuning. Regret analysis in Section !
3 Online Federated Model Selection
The present section introduces a disciplined way to enable clients to pick model among dictionary of models beyond the storage capacity of clients while clients enjoy sub-linear regret with respect to the best model in the dictionary. The proposed algorithm enables clients to collaborate with each other to fine-tune models in order to adapt models to clients' data.
3.1 Online Federated Model Selection
Let C be the cost to store model k. For example, C can be the amount of memory required to store the k-th model. Let B, denote the budget associated with the i-th client, which can be the memory available by the i-th client store models. At cach lcarning round, each client stores subset of models that can be fit into the memory of client The i-th client. fine-tunes and computes the loss of the stored subset of models. Computing the loss of multiple models at each learning round enables clients to obtain better evaluation the performance of models which can lead to identifying the best model faster. Moreover, fine-tuning multiple models can result in adapting models to clients' data faster. In Section A it is demonstrated that an increase in the number of models that clients can evaluate and fine-tune leads to tighter regret bounds for the proposed algorithm
At learning round t, the i-th client assigns weight 2 to the k-th model, which indicates the credibility of the k-th model with respect to the i-th client. Upon receiving new data sample, the i-th client updates the
3

---

Published in Transactions on Machine Learning Research (02/2024)
weights (2uk 1k= based on the observed losses. The update rule for weights (2 will be specified later in equation g Using (= k= at learning round 6, the i-th client selects one of the models according to the probability mass function (PMF) Pi, as
Zik. PRR 7
vk [K],
(4)
where Zi = -=;==
=E Z.R. Let Li, denote the index of the selected model by the i-th client at learning round t. Then client splits all models except for 11t model into clusters Di........ Di..s...,DDau.... Dimu,.. such that the cumulative cost of models in each cluster Byy, does not exceed B, CIa.-- Note that maj. denote the number of clusters constructed by client at learning round t if I,, = j. As it will be clarified in Section 4 packing models into minimun number of clusters helps clients to achieve tighter regret bound. Packing models into the minimum number of clusters can be viewed as a bin packing problem (see e.g.,. (Garey et al..
1972) which
is NP-hard (Crrstensenn et al. 2017). Several approximation methods have been proposed and analyzed in
the literature (Johnson 1973 de la Vega & Lucker 1981 Dósa 2007: Hoberg & Rothvoss) 2017 In the present work, models are packed into clusters using the first fireefii-decreasiing (FFD) bin packing a algorithm (see
Algorithm 2 in Appendix Ap. It has been proved that FFD can pack models into most 9 m² clusters
where m² is the minimum number of clusters (i.c., optimal solution for the clustcring problem) (Dósal 2007
After packing models into clusters, the i-th client chooses one of the clusters Dai,,,..., Dimar, uniformly at random. Let Ji, be the index of the cluster chosen by client i at learning round t. The i-th client downloads and stores all models in the cluster D.r,,,t along with the -, model. Since the cumulative cost of models in D.J..., does not exceed B, - CI,,, the cumulative cost of models in D.J,... in addition to the 44.th model does not exceed the budget B;. Let S.. represents the subset of models stored by client i at learning round Upon receiving new datum at learning round 6, the i-th client performs its prediction task using the 44ttth model. Then, the i-th client incurs loss [(fi,, (Z., ()...)) Vr.)). After observing yı,,, the i-th client computes the loss [(fa( (x,)), Ii,, Vk E Sy,.- After computing the losses, the i-th client obtains the importance sampling loss estimate for the k-th model as
likt [(fe(x OK.)) Bi.e) I(k E St,))
5
qake
where I(-) denote the indicator function and lik,t is the probability that the i-th client stores the k-th model at round L. In order to derive qik,t, note that the probability of storing model & at learning round t can be conditioned on 4t and based on the total probability theorem, it can be obtained that
Liki Σ PriL,, ji Pr[k S,,144, =] -1= Pisa Pr(k St,ll4, = j].
(6)
where Pr[A[[] denote the probability of event A given that event B occurred. If client i chooses the k-th
model at learning round & (i.e., T,, = k), then client i stores model & meaning that Pr[k: E St. = k] = 1. Let mija denote the number of clusters when client i chooses Iie- = j. Note that if li, = j client i splits all models except for model j into Mija clusters. If client i chooses It, = j such that j / k; then client stores model & at learning round t the chosen cluster contains model k. Since only one cluster among myj. clusters contains model and client chooses one cluster uniformly at random, it can be concluded that the probability qu,e can be obtained
Pr[k: E Si, = j.j A k) mig.t" Therefore, according to equation 6
Σ Pijat
qik.r = Pik.t +
Maj.t
At learning round t, client updates the weights of models using the multiplicative update rule as
2ik,t+1 = Z exp (-nilst,)),
(8)
where T) is the learning rate associated with the i-th client. According to equation 5 and equation g if client does not observe the loss of model is at learning round t, client keeps the weight 20.4+1 the same as 20h Conversely, when the loss is observed, a higher loss corresponds to greater reduction in the weight 2,
4

---

Published in Transactions on Machine Learning Research (02/2024)
3.2 Online Model Fine- Tuninn
This subsection presents principled way lo enable clients to collaborate with the server to fine-tune models. If client i participates in fine-tuning at learning round t, client locally updates all its stored models in S and sends updated models' parameters to the server. Sending updated parameters of a model to the server occupies a portion of communication bandwidth. Therefore, the available communicttion bandwidth may not be enough such that all clients can send their updates every learning round. In this case, at learning round t, the server has choose a subset of clients G such that the available bandwidth is sufficient for all clients in G, to send their updates to the server.
Let by be the bandwidth required to send the updated parameters of the k-th model. If E Gr, then the i-th client needs the bandwidth = Exes,, by to send updated parameters of its stored models. Let the available communication bandwidth be denoted by E. Given e;, Vi E [N], the server splits clients into a groups ,,,...,, No such that Eie,, e < E, Vj E [a]. This means that all clients in each group N,, Vj E [a] can send their updated model parameters to the server given the available bandwidth. At each learning round f, the server draws one of the client groups No uniformly at random. Clients in the chosen group send their updated models' parameters to the server. In other words, G2 == N., where 4 represents the index of the chosen client group at learning round L. Since the probability of choosing a client group is 4. the probability that client chosen by the server to send its updated models parameters 1 as well. Therefore, to maximize the probability that client is chosen by the server to be in G2 the server can split clients into minimum number of groups. To do this, bin-packing algorithms such FFD (Dósa 2007 can be employed.
a
Define the importance sampling loss gradient estimate Vlace associated with client and model k
Visk. VL(fa((m,,;) W..))) Gr, E S.,)).
Iiket
Recall that Z(-) denote the indicator function. The i-th client updates the models' parameters as
0urt41 Oz,t ny VlanA, Vk St,t.
(10)
where ny the fine-tuning learning rate. According to equation and equation 10 chosen for fine-tuning (i.e., i & Gt), then OiR OR,-- Thus, if G2, the i-th client sends locally updated models parameters (0 to the server. Let Va.2 denote the index set of clients such that i e Vx,e if
the i-th client is not
the server receives the update of the k-th model 0 from the i-th client. Upon aggregating information from clients, the server updates model parameters (0k,e) as:
N
0k141 Og.
Σ (Ok, 0s.(411) Og. LEV
n
(11)
N
The proposed Online Federated Model Selection and Fine-Tuning (OFMS-FT) algorithm is summarized in Algorithm 0 Steps 5 to IO in Algorithm [ outline how client i selects subset of models during each learning round f. Subsequently, each client i, Vi E [,], transmits its required bandwidth e, (acquired in step 10 to the server. Upon receiving e,, Vi E [M], the server, following steps 12 to 14 determines a subset of clients
G, eligible to send their updates. Each client then utilizes its selected model for prediction (step 16 and computes the loss of its stored model subset, updating the weights 2sk, (step 17). If client i is included in the server's selected subsot G. it transmits its local updates to the server, as depicted in step 19 Finally,
step 22 the server updates the model parameters for use in the subsequent learning round.
4 Regret Analysis
The present section analyzes the performance OFMS-FT in terms of cumulative regret. To analyze the performance of OFMS-FT, it is supposed that the following assumptions hold:
(al) For any (z. 3) and 0, the loss bounded as E [(fx(=;;)))) 0), < 1.
(a2) The budget satisfies B, 2 ck + oj j E [K], Vi [N].
5

---

Published in Transactions on Machine Learning Research (02/2024)
Algorithm OFMS-FT: Online Federated Model Selection and Fine- Fine-Tuning
Input: Models (k(o)),.o), costs Ck: by and budgets B,, E, Vi, Vk. Initialize: k, = Yk, Vi.
for 1= 1...... .....; 7 do
for all i E [ the ith client do
5:
Chooses a model using PMF Pa, in equation 4 I denote the index of the chosen model. Splits all models except for 1i, model into clusters Dai, Dim such that
6:
Σ KED
% s B, CIa Vj vj:1sja ma.-
Chooses cluster among {D 1ー uniformly at random where Jr,c is the chosen cluster index. Constructs the set of model indices S {T,+} U (k|bk E (...,)) Downloads all models whose indices are in Si from the server. Sends the bandwidth cost e; = Ekes. by to the server. end for
8:
9:
10:
11:
12:
The server splits clients into a groups ,I,...,,N, Na such that EIEN, 4 E, [a].
13:
The server draws one the groups {Ny}ş=ı uniformly at random.
14:
The server finds G. == N., with 4 as the chosen client group index.
15:
for all E [N], the ith client do
16:
Makes prediction fi., (2 (1,..) and computes C(fu(ar, On.). Ak E St
17:
Updates Zik,t, vk E S,, according equation
18:
if E G. then
19:
Sends Os.cc1, vk E S obtained by equation 10 to the server.
20:
end if 21: end for
22:
The server updates models parameters as in equation 11
23:
end for
(a3) The loss function ((f 0), v) is convex with respect to O, Ak E [K].
(a4) The gradient of the loss function is bounded as (), v)ll s G, V0, Ak E [K]. Also, O belongs to bounded set such that | < R.
Let miy be the minimum number clusters if client splits all models except for model j such that the cumulative cost of each cluster does not exceed B, - cy- Define μ4 = max, myy. which can be interpretod the upper bound for the minimum number of clusters that can be constructed by client at each learning round. It be concluded that μ4 K and increase in budget B; leads to decrease in μ4- The following theorem obtains the upper bound for the regret of clients and the server in terms of pa.
Theorem Assume that clients ulilize the first fit decrensing algorithm order to split models inlo clusters I... Dimm,tt- Under (al) and (a2), the expected cumulative regret of the i-th client using OFMS-FT is bounded by
RrT S In K + THTT,
(12)
1
which holds for all i E [N]. Under (a1) (a4), the cumalaatve regret of the server in fine-tuning model k using OFMS-FT FT is bounded by
R 1
SK. S
G...
(13)
21f
Proof. see Appendix
B

---

Published in Transactions on Machine Learning Research (02/2024)
If the i-th client sets 7/4 = O
In p:T
then the i-th client achieves sub-linear regret of
Ri S SO &rsSOV(m (v(nK))
(14)
If the server sets the fine-tuning learning rate as T)
then the server achieves regret of
2im1 Ar
aT
SK.T 0
Pi
(15)
N
The regret bounds in equation I4 and equation 13 show that a decrease in ii leads to tighter regret bound. If the i-th client has a larger budget B;, the upper bound for the minimum number of model clusters μ4 decreases since client can split models into clusters with larger budgets. As an example, consider the special case that all models have the same cost Cg c, Ak [K] while B; = dee where d 2 2 is an integer. In this case, according to step G in Algorithm [ the upper bound for the minimum number of clusters is [K-1]e- . Therefore, as the budget of client increases, the client can achieve lighter regret bound. In addition, larger communication bandwidth enables the server to partition clients into smaller number of groups a. Thus, according to equation 15 larger communication bandwidth leads to tighter regret bound for the server.
14 = (6,-1)e
Challenges of Obtaining Regret in equation 15 Limited memory of clients brings challenges for obtaining the sub-linear regret in equation 15 since clients cannot calculate the gradient loss of all models every learning round. To overcome this challenge, the present paper proposes update rules equation g and equation [0] along with the novel model subset selection presented in steps 3 G and of Algorithml [] In what follows the effectiveness of the proposed update rules and model subsct selection explained. Employing vanilla online gradient descent update rule 0 0x, ff 0k.)) y(.)) locally by clients, can result in regret of (VVT) if client knows (ff(f (Zi,,; O2.)), Vk E [K] at every learning round (see e.g., (Hazan ). This is not possible since client has limited memory and is not able to calculate the gradient loss of all models every learning round. To overcome this challenge, the present paper proposes the local update rules in equation and equation 10 which use the gradient loss estimate VêskA instead of true loss gradient. Using equation 37 of Appendix
can be concluded that Vlea, is an unbiased estimator of V VL(ff ( Vi.e) meaning that IE, [V V[(fu( Ok,z), Bis)) According to equation g obtaining VLSR does not require storing model & and calculating V.(ff Ox.)), vı.e) every learning round. Hence, Vis can be obtained every learning round given the limited memory of client However, according equation 36 equation 38 and equation 39 of Appendix B employing update rule of equation 10 the regret. of the server grows with E, [IV which upper bounded as E&ll V S aG" (sco equation 37b د where lik,s is the probability that client stores model & and fine-tunes it at learning round t. Using model subset selection method presented in 1 and 7 of Algorithm [ the probability lik,t is obtained as in equation 7 In equation 2 of Appendix
Appendix B Therefore, the regret of the server grows with gen.r
steps
B it proven that if clients employ FFD algorithm cluster models in step 6 then it is guaranteed that
1. This lead to guarantecing the regret upper bound in equation 15
Gaket
2y.
5 Related Works and Discussions
This Section discusses differences, innovations, and improvements provided by the proposed OFMS-FT compared to related works in the literature.
Online Model Selection. Online model selection algorithms by Foster et al. (0117) huthukumar et al. 2019 : Foster et al. (2019) Cella et al. (2021); Pacchiano et al. (2020): Reza Karimi et al. (2021) have studied either full-ifformation or bondit settings. Full-information refers to cases where the loss of all models can be observed every round while in bandit setting only the loss of the chosen model can be observed. Regret bounds obtained by full-information based online model selection algorithms cannot be guaranteed if the
7

---

Published in Transactions on Machine Learning Research (02/2024)
learner (i.e,, client) cannot store all models. Moreover, it is useful to mention that the present paper studies the adversarial setting where the losses observed by clients at each round are specified by the environment and may not follow any time-inaariant distribution. It is well-known that in the adversarial bandit setting the learner achieves regret upper bound of ((VKT) (sec c.g., (Pacchiano et al. 2020))- The proposed OFMS-FT utilizes the available memory of clients to evaluate a subset of models every round (see step 16
in Algorithm ! which helps client i to achieve regret of (V(1,)) as presented in equation 14 If client is able to store more than one model, then 14 < K (see below equation 3 and the discussion below Theorem which shows that OFMS-FT utilizes the available memory of clients to improve their regret bound compared to bandit setting. Moreover, aforementioned online model selection works have not studied online fine-tuning of models. A model selection algorithm proposed by PPachiinoo et al. (2022) assumee that each model (called base learner) comes with a candidate regret bound and utilizes this information for model selection. By contrast, the present paper assumes that there is no available prior information about the performance of modcls. Morcover, Muthukumar & Krishnamurthy (2022) has studied the problem of model selection in linear contextual bandits where the reward (can be interpreted as negative loss in our work) is the linear function of the context (can be interpreted Di in our work). However, the present paper does not make this assumption in both theoretical analysis and experiments. Furthermore, online model selection when models are kernels has been studied in the literature (sec e.g.. (Yang et al. 2012 Zhang et al., 2021b Ghari & Shen 2023a)) ) where the specific characteristies of kernel functions are exploited to perform model selection to alleviate computational complexity of kernel learning.
& Liao 2022
Online Learning with Partial Observations. Another line of research related to the focus of the present paper is online learning with expert advice where a learner interacts with a set of experts such that at each learning round the learner makes decision based on advice received from the experts (Cosa-Bianchi & Lugosi 2006). The learner may observe the loss associaled with subset of experts after decision making, which can be modeled using graph called feedback graph (Mannor & Shamir 2011 Amin et al.] 2015 Cohen et al.) 2016 Alon et al. 2015; Cortes et al.] 2020 Ghari & Shen, 2023b). In online federated model selection, each model can be viewed as an expert. Employing the proposed OFMS-FT, in addition to performing online model selection, clients and the server collaborate to fine-tune the models (experts). However, the aforementioned online learning algorithms do not study the case where the learner can influence experts. Performing online model selection and fine-tuning jointly in a federated fashion brings challenges for guarantying sub-lincar regret that cannot be overcame using the existing online learning algorithms. Specifically, due to limited client-to-server communication bandwidth and limited memory of clients, all clients are not able to fine-tune all models every learning round. The proposed OFMS-FT introduces a novel model subset selection in steps 6 and 7 of Algorithm [ and a novel update rule in equation g and equation I0 to fine-tune models locally by clients in such a way that given limited memory of clients and limited communication bandwidth, the server achieves sub-linear regret of equation
Online Federated Learning. The problem of online federated model selection and fine-tuning is related to online federated learning (Chen et al. 2020; Mitra et al. 2021 Damaskinos et al. 2022). Chen et al. (2020) has studied learning a global model when clients receive new data samples while they participate in federated learning. Online decision-making by clients has not been studied by [Chen et al. (2020) and hence the regret bound for clients cannot be guaranteed. An online federated learning algorithm has been proposod by Damaskinos et al. (2022) to cope with the staleness fodcrated lcarning. However, it lacks theoretical analysis when clients need to perform online decision-making. An online mirror descent--bsse federated learning algorithm called Fed-OMD has been proposed in Mitra et al. (2021). Fed-OMD obtains sub-linear regret when clients perform their ouline learning task while collaborating with the server to learn a single model. However, Fed-OMD cannot guarantee sub-linear regret when it comes to performing online model selection if clients are unable to store all models in the dictionary. Furthermore, Hong & Chae (2022); ; Gogineni et al. (2022): ; Ghari & Shen (2022) have studied the problem of online federated learning where each client learns a kernel-based model employing specific characteristics of kernel functions.
Personalized Model Selection and Fine-Tuning: In addition to online model selection, online learning and online fedcrated learning discussed in Section 5 personalized federated learning can be related to the focus of this paper. Employing the proposed OFMS-FT, model selection and fine-tuning is personalized for clients. According to step 5 in Algorithm [ each client chooses a model locally using the personalized
8

---

Published in Transactions on Machine Learning Research (02/2024)
PMF Pa, in equation to make prediction at round t. This helps each client i, Vi E [M] to achieve the sub-linear regret in equation 14 Furthermore, the choice of models to be fine-tuned locally by each client is personalized according to step 19 in Algorithm [ Particularly, qukt in equation 7 is the probability that the client i fine-tunes the model & at round t. The probability qak. is determined by client i and can be inferred that the probability to participate in fine-tuning a model is determined by client. i based on its preferences given the limited memory budget. It is useful add that personalized federated learning is well-studied topic related to the focus of the present paper. In personalized federated learning framework, aggregating information from clients the server assists clients to learn their own personalized model. Several personalized federated learning approaches have been proposed in the literature for example inspired by model-agnostic meta-learning (Finn et al.) 2017 Fallah et al. 2020 Acar et al.,
2021p, adding a regularization term to the Li et al. 2021a Liu el al. 2022), among others (see
objective function (Hanzely el. al. 2020 Dinh et. al. 2020
e.g., Deng et al. 2020; Collins et al. 2021 Marfoq et al. 2021 Shamsian et al. 2021)) ). However, none of the
aforementioned works have studied online decision making, online foderatod model selection and finc-tuning
when clients have limited memory and employing them, sub-linear regrets cannot be guaranteed for clients
and the server.
Client Selection. Client selection in federated learning has been extensively explored in the literature Chen
et al. 2018 Huang et al. 2021 Balakrishnan et al., 2022 Németh et al. 2022; Fu et al., 2023p. However, none of the aforementioned works have specifically studied client selection for online federated learning, where clients utilize the trained model from federated learning for online predictions. In the proposed OFMS-FT, the server selects clients for their participation in model fine-tuning uniformly at random. This choice aims to avoid differentiating among clients and fine-tune models in the favor of any clients. Nevertheless, an intriguing direction for future rescarch is to investigate how alternative client selection strategies, beyond uniform selection, could enhance client regret in the context of online federated learning.
6 Experiments
We tested the performance of the proposed OFMS-FT for online model selection through a set of experiments. The performance of OFMS-FT is compared with the following baselines: MAB (Auer et al. 2003). Non-Fed- OMS, RMS-FT, B-Fed-OMFT, FedOMD (Mitra et al. 2021) and PerFedAvg (Fallah et al., 2020). J MAB refers to the case where the server chooses a model using Exp3 algorithm (Auer et al. 2003) and transmits the chosen model to all clients. Then, each client sends the loss of the reccived model to the server. Non-Fed-OMS refers to fod-reddetted online model selection where each client stores fixed subset of models that can be fit into its memory. At each learning round, each client chooses one model from the stored subset of models using Exp3 algorithm. RMS-FT denote a bascline where at each lcarning round each client chooses a subset of models uniformly at random to fine-tune them. The prediction task is then carried out by selecting one of the chosen models uniformly at random. Furthermore, B-Fed-OMFT stands for Budgeted Federated Online Model Fine-Tuning, In this approach, the server maintains a set of models that can be fit into the memory of all clients. Clients collaborate with the server to fine-tune all models in each learning round. In the B-Fed-OMFT framework, each client employs the Exp3 algorithm to choose one model to perform the prediction task. Using Fed-OMD (Mitra et al. 2021). given a pre-trained model, clients and the server fine-tune the model. PerFedAvg refers to the case where given a pre-trained model, clients and the server fine-tune the model using Personalized FedAvg (Fallah et al. 2020). The performance of the proposed OFMS-FT and baselines are tested on online image classification and online regression tasks. Image classification tasks are performed over CIFAR-10 (Krizhevsky] (009) and MNIST (Lecun al.) 1998) datasets. Online regression tasks are performed on Air (Zhang et al.) 2017) and WEC (Neshat et al. 2018 datasets. For both image classification
datasets, the server stores 20 pre-trained convolutional neural networks (CNNs). Based on the number of paramcters required to store models, for CIFAR-10 the normalized costs of storing CNNs are cither 0.89 or 1, and for MNIST the normalized costs are either 0.66 or 1. The experiments were conducted with a single meta-replccation, utilizing a consistent random seed for both the proposed OFMS-FT and all baseline mothods. Morcover, for both regression datasots, the server stores 20 pre-trained fully-conneeted foedforward neural networks. Since all neural networks have the same size, the normalized costs of all of them are 1. More details about models and datasets can be found in Appendix
9

---

Published in Transactions on Machine Learning Research (02/2024)
Table 1: Average and standard deviation of clients' accuracy over CIFAR-10 and MNIST datasets. MSE (x10-3) and its standard deviation (x10-3) across clients over Air and WEC datascts.
Algorithms
CIFAR-10
MNIST
Air
WEC
MAB
61.14% + 10.12%
84.37% + 5.18%
8.97 6.82
36.96 + 8.52
Non-Fed-OMA
65.76% = 12.24%
85.06% 7.30%
8.82
64.84 + 40.30
RMS-FT
57.86% + 9.75%
88.33% + 4.25%
7.87
18.89 + 4.02
B-Fed-OMFT
67.83% + 12.28%
89.46% 4.71%
5.09
31.94 7.97
Fed-OMD
64.34% + 9.89%
88.69% + 5.16%
11.37 7.16
30.89 + 10.06
PerFedAvg
55.65% 11.94%
89.71% = 4.93%
11.29 + 7.08
30.09 + 10.17
OFMS-FT
76.77% + 4.46%
92.05% + 2.69%
7.46 5.10
7.09 + 1.67
17.5
8-2
16
FT.
CENS-FL 11mb
15.0
12.5
1.0
Average
20.0
0.8
0.2
0.0
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Learning Round
Learning Round
(a) MNIST
(b) WEC
Figure 1: Average regret of clients using OFMS-FT with the change in budget B
There are 50 clients performing image classification task, and 100 clients performing online regression task. Note that clients are performing the learning task an online fashion such that at each learning round each client observes one data sample and predicts its label in real time. The learning rates 7i for all methods are set to be 10/vT where T 200. Furthermore, the fine-tuning learning rate is to Ty = 10 10-3/vTT Since the required bandwidth to send model is proportional to the model size, the normalized bandwidth by associated with the k-th model are considered to be the same as the normalized cost Ck.
Table [ demonstrates the average and standard deviation of clients' accuracy over CIFAR-10 and MNIST when the test set is distributed in non-i.id manner among clients. For CIFAR-10, cach client receives 155 lesting data samples from one class and 5 samples from each of the other nine classes. In the case of MNIST, each client receives at least 133 samples from one class and at least 5 samples from the other classes. The 200 testing data samples are randomly shuffled and are sequentially presented to each client over T = 200 learning rounds. The accuracy of the client is defined as Accuracy; = ΣT- I(fr.t yi.1) where d., denote the class label predicted by the algorithm. The memory budget. is B, 5, Vi E [N]. Each client is able to store up to 50 images. In order to fine-tune models, clients employ the last 50 observed images. Moreover, Fed-OMD and Avg fine-tune one of the 20 pre-trained models such that both fine-tune the same pre-trained model. As can be observed from Table ! the proposed OFMS-FT achieves higher accuracy than Non-Fod-OMS and B-Fed-OMFT. This corroborates that having access to larger number of models helps learners to achieve better learning performance, especially in cases where the learners are faced with heterogeneous data, and performance of models are unknown in priori. Moreover, from Table I it can be seen that OFMS-FT achieves higher accuracy than MAB which admits the effectiveness of observing losses of multiple models at each learning round. Higher accuracy of OFMS-FT compared with Fed-OMD and PerPedAvg indicates the benefit. of fine-tuning multiple models rather than one. The superior performance of OFMS-FT in comparison to RMS-FT highlights the efficacy employing model selection through the PMF defined equation equation A as opposed to choosing models uniformly at random. In addition, as can be seen from Table ! the standard deviation of clients' accuracy associated with OFMS-FT considerably lower than other baselines. This shows that using OFMS-FT, accuracy across clients shows less variations
10

---

Published in Transactions on Machine Learning Research (02/2024)
compared with other baselines. Therefore, the results confirm that OFMS-FT can cope with heterogeneous data of clients in more flexible and henceforth more effective fashion.
Furthermore, Table presents the mean square eгror (MSE) of online regression and its standard de- viation across clients for Air and WEC datasets. Specifically, MSE of client is defined as MSE; = J. + (fr, 9. In both the Air and WEC datasets, individual data samples are associated with one of four geographical areas. The distribution of data samples across clients is non-i..d, with 50 clients observing data samples from one specific site, while the remaining 50 clients observe data samples from another geographical site. At each round, only half of clients are able to send their updated models to the server. All other settings are the same online image classification setting. Results for online regression tasks are consistent with the conclusions obtained from the results of online image classification task. Moreover, Figure [ illustrates the average regret of clients using the proposed OFMS-FT through learning rounds for different values of memory budget B,. Figure [ depicts the regret of OFMS-FT through learning on MNIST and WEC datasets. As can be scen, the increase in B, leads to obtaining lower regret by clients. Therefore, the results in Figure are in agreement with the regret analysis in Section 4 Table 2 illustrates the sensitivity of the MSE and its standard deviation, as achieved by the proposed OFMS-FT, to the budget B, (Vi E [M]) over the WFC dataset. In this configuration, the budget varies across clients, with a subset having B, = 3 and the remainder B; = 5. The improvement in MSE becomes evident as the number of clients with budget of B 5 increases. This observation indicates that an increase in budget enhances the performance of OFMS-FT, aligning with the theoretical findings presented in Section
T
Table 2: MSE (x10 and its standard de- viation (x10-3) of OFMS-FT across clients over WEC dataset under varying budgets among clients.
B, = 3
B: 5
MSE
60%
40%
7.96 + 1.49
50%
50%
7.85 + 1.66
40%
60%
7.32 + 1.54
7 Conclusion
Performing online model selection with a large number of models can improve the performance of online model selection especially when there is not prior information about models. The present paper developed a federated learning approach (OFMS-FT) for online model selection when clients cannot store all models due to limitations their memory. To adapt models to clients' data, employing OFMS-FT clients can collaborate to fine-tune models. It was proved that both clients and the server achieve sub-linear regret with respect to regression and image classification datasets were carried out
the best model in hindsight. Experiments to showcase that the proposed OFMS-FT achieved better performance in comparison with non-federated online model selection approach and other state-of-tho-art federated learning algorithms which employ a single model rather than a dictionary of models.
References
Durmus Alp Emre Acar, Yue Zhao, Ruizhao Zhu, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Debiasing model updates for improving personalized federated training. Tn Proceedings of International Conference on Machine Learning, volume 139, pp. 21-31. Jul 2021.
Noga Alon, Nicolò Desa-Bianche Ofer Dekel, and Tomer Koren. Online learning with feedback graphs:
Beyond bandits. In Proceedings of Conference on Learning Theory, volume 40, pp. 23-35, Jul 2015.
Kareem Amin, Satyen Kale, Gerald Tesauro, and Deepak Turaga. Budgeted prediction with expert advice. In AAAI Conference on Artificial Intelligence, Feb 2015.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, Jan 2003.
Ravikumar Balakrishnan, Tian Li, Tianyi Zhou, Nageen Himayat, Virginia Smith, and Jeff Bilmes. Diverse client selection for federated learning via submodular maximization. In International Conference on Learning Representations, 2022.
11

---

Published in Transactions on Machine Learning Research (02/2024)
Leonardo Cella, Massimiliano Pontil, and Claudio Gentile. Best model identification: A rested bandit formulation. In Proceediiggs of International Conference on Machine Learning, volume 139, pp. 1362-1372) Jul 2021.
Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, USA, 2006.
Tianyi Chen, Georgios B. Giannakis, Tao Sun, and Wotao Yin. Lag: Lazily aggregated gradient for communiation--ffiient distributed learning. In Proceedings of International Conference on Newral Infor- mation Processing Systems, pp. 5055 5065, 2018.
Yujing Chen, Yue Ning, Martin Slawski, and Huzefa Rangwala. Asyuchronous online federated learning for edge devices with non-iid data. In JEEE International Conference on Big Data (Big Data), pp. 15-24, Dec 2020.
Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimmesiooal bin packing: A survey. Computer Science Review, 24:63 79, May 2017.
Alon Cohen, Tamir Hazan, and Tomer Koren. Online learning with feedback graphs without the graphs. In Proceedings of International Conference on Machine Learning, pp. 811 819, Jun 2016.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations
for personalized federated learning. In Proceedings of the International Conference on Machine Learning, volume 139, pp. 2089 2099, Jul 2021.
Corrina Cortes, Giulia DeSalvo, Claudio Gentile, Mchryar Mohri, and Ningshan Zhang. Online learning with dependent stochastic feedback graphs. In Proceedings of International Conference on Machine Learning, Jul 2020.
Zhenwen Dai, Praveen Chandar, Ghazal Fazelnia, Benjamin Cartorette, and Mounia Lalmas. Model selection for production system via automated online experiments. In Proceedings of International Conference on Neural Information Processing Systems, volume 33, pp. 1106- 11661116,-11 2020.
Georgios Damaskinos, Rachid Guerraoui, Anno-Marie Kermarree, Vlad Nitu, Rhichook Patra, and Francois Taiani. Fleet: Online federated learning via staleness awareness and performance prediction. ACM Transactions Intelligent Systems and Technology, 13(5). Sep 2022.
W. Fernandez de la Vega and George S. Lucker. Bin packing can be solved within + in linear time. Combinatorica, 1:349 355, 1981.
Yuyang Deng, Mohammad Mahdi Kamani, and Mchrdad Mahdavi. Adaptive personalized federated learning. Xrxio preprial ar 2ri:20003 13461, 2020.
Canh T. Dinh, Nguyen H. Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. In Proceedings of International Conference on Neural Information Processing Systems, pp. 21394 21405, Dec 2020.
György Dósa, The tight bound of first fit decreasing bin-packing algorithm is ffd(1) S 11/9opt(i) + 6/9. In International Conference on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, pp. 11, Apr. 2007.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar, Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. In Advances Neural Information Processing Systems, volume 33, pp. 3557 3568, Dec 2020.
Amirmassoud Farahmand and Csaba Szepesvari. Model selection in reinforcement learning. Machine Learning, Jun 2011.
12

---

Published in Transactions on Machine Learning Research (02/2024)
Chelsea Finn, Picter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of International Conference on Machine Learning, volume 70, pp. 1126-1135, Aug 2017.
Dylan Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter-Fre free online learning via model selection. In Proceedings of International Conference Neural Information Processing Systems, 2017.
Dylan Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. In Proceedings of International Conference on Neural Information Processing Systems, volune 32, 2019.
Lei Fu, Huanle Zhang, Ge Gao, Mi Zhang, and Xin Liu. Client selection in federated learning; Principles, challenges, and opportunities. IEEE Internet of Things Journal, 2023.
M. Garey, R. L. Graham, and J. D. Ullman. Worst-case analysis of memory allocation algorithms. In
ACM Symposium on Theory of Computing, pp. 143 150, 1972.
Pouya M. Ghari and Yanning Shen. Personalized online federated learning with multiple kernels. In Advances in Neural Information Processing Systems, 2022.
Pouya. M. Ghari and Yanning Shen. Graph-aided online multi-kernel learning. Journal of Machine Learning Research, 24(21):1 44, 2023a.
Pouya M. Ghari and Yanning Shen. Online learning with uncertain feedback graphs. IEEE Transactions on Neural Nelworks and Learning Systems, pp. 1-15, 2023b.
Vinay Chakravarthi Gogineni, Stefan Werner, Yih-Fang Huang, and Authony Kuh. Communication-elliiiie online federated learning framework for nonlinear regression. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.
2022.
Jenny Hamer, Mehryar Mohri, and Ananda Theertha Suresh. FedBoost: A communictiion-effiieet algorithm for federated learning. In Proceedings of International Conference on Machine Learning, volume 119, pp. 3973 -983,, Jul 2020.
Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik. Lower bounds and optimal algorithms for personalized federated learning. In Proceedings of International Conference on Neural Information Processing Systems, pp. 2304-2315, Dec 2020.
Elad Hazan. Introduction to Online Conver Optimization. MIT Press, 2022.
Rebecca Hoberg and Thomas Rothvoss. A logarithmic additive integrality gap for bin packing. In Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 2616 2625, 2017.
Songnam Hong and Jeongmin Chae. Communicationneffiiieent randomized algorithm for multi-kernell online federated learning. IEFE Transactions on Pattern Analysis and Machine Intelligence, 44(11):9872-9886, 2022.
Tiansheng Huang, Weiwei Lin, Wentai Wu, Ligang He, Keqin Li, and Albert Y. Zomaya. An efficiency- boosting client selection scheme for federated learning with fairness guarantce. IEFE Transactions on Parallel and Distributed Systems, 32(())1552 1564, 2021.
David S. Johnson. Near-optimal bin packing algorithms. PhD thesis, MIT, 1973.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda. Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for fedoratod learning. In Proceedings of International Conference on Machine Learning, volume 119, pp. 5132-5143, Jul 2020.
Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. UCI machine learning repository, 2023.
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency, 2017.
13

---

Published in Transactions on Machine Learning Research (02/2024)
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 2224, 1998.
Jonathan Lee, Aldo Pacchiano, Vidya Muthukumar, Weihao Kong, and Emma Brunskill. Online model selection for reinforcement learning with function approximation. In Proceedings of the International Conference on Artificial Intelligence and Stafistics, volume 130, pp. 3340-3 3348, Apr 2021.
Junfan Li and Shizhong Liao. Worst-case regret analysis of computationally budgeted online kernel selection. Machine Learning, 111(3))937 976, Mar 2022.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In Proceedings of International Conference on Machine Learning, volume 139, pp. 6357-6368, Jul 2021a.
Xiaoxiao Lí, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. FedBN: Federated learning on non-ITD features via local batch normalization. In International Conference on Learning Representations, 2021b.
Ken Liu, Shengyuan Hu, Steven Wu, and Virginia. Smith. On privacy and personalization in cross-silo federated learning. In Advances in Neural Information Processing Systems, 2022.
Shie Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations. In Proceedings of International Conference on Neural Information Processing Systems, pp. 684 192, 2011.
Othmane Marfoq, Giovanni Neglia, Aurélien Bellet, Lactitia Kameni, and Richard Vidal. Federated multi-task learning under mixture of distributions. In Proceedings of International Conference on Neural Information Processing Systems, volume 34, pp. 15434-15447, Dec 2021.
Aritra Mitra, Hamed Hassani, and George J. Pappas. Online federated learning. In IEEE Conference Decision and Control (CDC), pp. 4083 4090, Dec 2021.
Vidya Muthukumar, Mitas Ray, Anant Sahai, and Peter Bartlett. Best of many worlds: Robust model selection for online supervised learning. In Proceedings of the International Conference on Artificial Intelligence and Statistics, volume 89, pp. 1177-3186, Apr 2019.
Vidya K Muthukumar and Akshay Krishnamurthy, Universal and data-adaptive algorithms for model selection in linear contextual bandits. In International Conference on Machine Learning, pp. 16197 16222, 2022.
Gergely Dániel Németh, Miguel Angel Lozano, Novi Quadrianto, and Nuria M Oliver. A snapshot of the frontiers of client selection in federated learning. Transactions Machine Learning Reseurch, 2022. ISSN 2835-8856. Survey Certification.
Mehdi Neshat, Bradley Alexander, Markus Wagner, and Yuanzhong Xia. A detailed comparison of meta- houristic methods for optimising wave energy converter placoments. In Proceedings of the Genetic and Evolutionary Compulation Conference, pp. 1318 1325, Jul 2018.
Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. In Advances in Neural Information Processing Systems, volume 33, pp. 10328 10337, 2020.
Aldo Pacchiano, Christoph Dann, and Claudio Gentile. Best of both worlds model selection. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL htccps://ooenreveeeeeeet// net.:forumm.dee--v8Buc.....
Mohammad Reza Karimi, Nezihe Merve Gürel, Bojan Karlaš, Johannes Rausch, Ce Zhang, and Andreas Krause. Online active model selection for pre-trained classifiers. In Proceedings of The International Conference Artificial Intelligncce and Statistics, volume 130, pp. 307-315, Apr 2021.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, lon Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. FetchSGD: Communication-elicienn federated learning with sketching. In
Proceedings of International Conference on Machine Learning, volume 119, pp. 8253 8265, Jul 2020.
Aviv Shamsian, Aviv Navon, Fthan Fetaya, and Gal Chechik. Personalized federated learning using hypernet- works. In Proceedings of International Conference Machine Learning, volume 139, pp. 9489-9500 Jul 2021.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for largo-scale image recognition. In International Conference Learning Represenlalions, May 2015. URL htttp://aarii..rrg//bbba
1556
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. In Advances in Neural Information Processing Systems, volume 30, pp. 4424-4434, Dec 2017.
Tianbao Yang, Mehrdad Mahdavi, Rong Jin, Jinfeng Yi, and Steven C. H. Hoi. Online kernel selection: Algorithms and evaluations. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 1197 1203, 2012.
Michael Zhang, Karan Sapra, Sanja. Fidler, Serena Yeung, and Jose M. Alvarez. Personalized federated learning with first order model optimization. In International Conference on Learning Representations, 2021a.
Shuyi Zhang, Bin Guo, Anlan Dong, Jing He, Ziping Xu, and Song Xi Chen. Cautionary tales on air-quality improvement in beijing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 473(2205) 2017.
Xiao Zhang, Shizhong Liao, Jun Xu, and Ji-Rong Wen. Regret bounds for online kernel selection in continuous kernel space. Proceedings of the AAA Conference Artificial Intelligence, 35(12): 10931-13883,,, May 2021b.
15

---

Published in Transactions on Machine Learning Research (02/2024)
A First Fit Decreasing Algorithm
In this paper, first fit decreasing algorithm is employed to split models into clusters. To begin with, order models by decreasing cost. Let s(1)...., s(K - 1) denote the indices of all models except for the I,t- model ordered in ascending manner according to models' costs such that if S j, then Ca(() S Ce())- At the k-th step of clustering, client checks whether the s(k)-th model can be fit into any currently existing clusters according to budget B; Cr.,. The s(k)--h model is put into the first cluster that it can be fit into. Otherwise, if it cannot be fit into any opened cluster, then it is assigned to new cluster indexed by my. 1. This continues until all models except for the 1tt model are corresponded to a cluster. Algorithm summarizes the clustering procedure performed by the i-th client.
A Agorithh Cluster Generation by Client i at Learning Round /
Input: Chosen model index J costs Ck. Vk E [K] and budget B₁. Initialize: m4, 1.
Order all models except for the 1i, model by decreasing cost. to obtain s(I), (.))),,......... 1).
for k = ,,..., K - do and d 0 6: while d = and j S miy do
5: Set
7:
if EmmDiy Cm + C(k)) I B; CI then
Set d - and j =
end if end while
10:
11: if mi,t + 1 and d 0 then
12:
Assign the s(k)-th model to a new cluster Di(ma +1) Update mi, = mi, + 1.
13:
14:
end if
15:
end for
16: Output: Bhai....,,m....
B Proof of Theorem
In order prove Theorem ! the following Lemma is used the step-stone.
Lemma 2. Under (al) and (a2), the regret of the i-th client with respect to any model k is bounded from above as
In K
Σ EelCffn (1i,e; O (,,,)),
Σ ((l)(a..
n.PTT.
(16)
17
Proof. Recall that Zi,1- = Ex= Zik.r. Therefore, we can write
K
Zi,+1
Zik,t+1
2skit Zr
exp (-m,ea,)).
(17)
Zz
Zz
k=l
A=
According equation
Pik,t and result equation
17 can be rewritten
2,,
Zi,t1
Σ Pik exp (-mlaa))
(18)
Zi
Combining the inequality - < x + 2
Vx 2 0 with equation 17 we can conclude that
K
Zi,t+1
Pik,t 1 11 milit, + ((llmn)))
(19)
Zin
k=1
16

---

Published in Transactions on Machine Learning Research (02/2024)
Employing the inequality 1 + S c" and taking logarithm from both sides of equation 19
arrive at
Zi,t1 Zz,t
(-illike + ((ndemn)))
In
Pik,a
(20)
kmm
Summing equation 20 over learning rounds leads to
K
7,,++1
(-nfeiee + ((nlass))))
In
Pik,s
(21)
2
Rm
In addition, 2. Z,,
can be bounded from below as
T Σ
Zir+1
ZskT+1
In
2 In
like - In K,
(22)
Z
Z₁,
t=1
which holds for any k E [K]. Combining equation
21 with equation
22
we get
T
K
Panalina
Σ
In
K
1
K
P
62
(23)
2
k=1
k=1
Considering equation 5 and equation can be obtained as
given the observed losses in prior rounds the expected value of likes
E2 [1 = (a Og.e).
Clfalarse OK.)s Ha.) Pijaa
DikA +
Qik,t
Qiket
Mija
C(fa(a,, Og.e), Va.1)
Pik,t +
Pij.
C(fulor,es Ou.)),
(24)
Qik,t
Mijit
Moreover, based the assumption that 0 s L(fe(ar, Ok.)). va,)) 1, given the observed losses in prior rounds, the expected value of ER can be bounded from above
C"(Jaaaz Ow.e), Mile)
E2 [C
Pik.t +
Pijat
Pi
majae
C2 (xi, Ok.) vie)
(25)
Giket.
gik.t
Taking the expectation from both sides of equation
we obtain
K
K
Pa. 0x.). v..))
Σ
In K
1
Pik.t
(26)
7
2
liket
In addition, it can be written that
E,[C(fr, (I.,;; vi.1]
Pik. C(fa( Pu.)..v.d
(27)
[=1
Therefore, from equation 26 we arrive at
T Σ
T
E. E,[C(Sr (21, Or...), Wo,e]l
In K
Pik.t
(28)
1K
Isk,t
t=
k=
17

---

Published in Transactions on Machine Learning Research (02/2024)
According to Algorithm 1 at each learning round, client splits all models except for the chosen model into clusters. Let Vij be the minimum number of clusters when client. chooses T and splits all models except. for model j into clusters. If client i employs FFD algorithm to split models, the number of clusters might when client i chooses I = satisfies Maj. Σ 11 Vij + (Dósa 2007p. Let μz be defined as μr = max, Vij- Therefore, can be concluded that maja g 14 + E/ S 2p,. Thus, can be written that
1 Pik,t 2
Piket 2 Pik, +
(29)
2/44
2/4
Combining equation 28 with equation
29 yields
T
In K
Σ
(allf (n..)) B(,e)
Σ
n.4T..
(30)
77
which proves the lemma.
In what follows the server regret upper bound fine-tuning model & obtained. Let lece denote the fine-tuning importance sampling loss estimate learning round associated with the i-th client and the k-th model, defined as
lsk.
C(fx( On.)). Mt E G. S,,)).
(31)
qiket
According to equation 11 for any fixed 0 and & E [K], it can be written that
N
10 01
Ok. 0
T N
V sk.t
1k,, 011
2
(ok. 0) +
M N
V
Vlrae
(32)
Moreover, due to the convexity of the loss function C(, -), for any learning round t, we find that
VJ C'LA(FEE 0x.))
(0 0x.)) s L(fx (x;,; vc.) - ((ff(a 2..))
(33)
Multiplying both sides of equation
33 by AEB..) we get
V Vulun (0- 02,)) S () G. Bx,)) Pix.
(34)
giktt
Summing equation 34 over clients, we obtain
(( 0), G., Si,))
V
(on, 0)-
(35)
lik,t
Combining equation 32 with equation 35
leads to
a
(). E G k E Sa,e)
i= Piket
N
N
(10k,1 01 - -110 - 0112) +
" 2N
Σ
V
ik.t
(36)
201
18

---

Published in Transactions on Machine Learning Research (02/2024)
Moreover, the expected value of lit. and |/ with respect to I(i Gr k E St,1) can be obtained as
E, [1a
a ((iLe (k x
Pikit
Pistt
qiket
( On.t), wh.e)
(37a)
B Ren.el
|V (2 On.
Pikie
+
Σ
Pija
Uiket
VjJfk
aG² gik.t
VV(ff 0n.), v6,01 v
(37b)
gike
where the last inequality in equation 37b can concluded from the assumption (a3) where ( (aa).3..)) I G. In addition, using arithmetic mean geometric mean (AM-GM) inoquality find
N
N
Σ
v
N
V 12
(38)
Therefore, using equation 37 and equation be written that
38
taking the expectation from both sides of equation
it can
(f Ow.))..)))
$ 2ms
N
(110k.: - -0122
-110R.1 -
0| +
15 2
N
a
(39)
2
liket
-=1
Summing equation 39
learning rounds yiclds
T ((Ja(2 0x.))
T
Σ
(2: 0),
t=1
1=1=]
N
n5 G2
(1
0112 110..111
(40)
2n1
lsket
1=1
Plugging in 0 0% in equation
40
and considering the facts that ox.1 = 0 and |R, 011 2 0, we arrive at
N
N
T
c(fa(a,,) 02.0).0..)
C(fa(ar,e: 02).
N
GB
|
(41)
2n
2
Piket
According equation get
29
it can be concluded that
S 244. Therefore, considering assumption (a4), we Wake
N
T
N T
NR
N
((aaaa M..))
Σ I (Ull
S
Σ iml
G.
(42)
2nf
which proves equation
13 and completes the proof of Theorem
19

---

Published in Transactions on Machine Learning Research (02/2024)
C Supplementary Experimental Results and Details
The performance of both the proposed OFMS-FT method and other baseline approaches is evaluated through online image classification and online regression tasks. The image classification experiments involve the utilization of the CIFAR-10 and MNIST datascts. CIFAR-10 and MNIST are well-known computer vision datasets, comprising a total of 60, 000 and 70, 000 color images, respectively, distributed across 10 distinct classes. Each dataset includes 10, 000 test samples, with the remaining samples designated for training. To facilitate model selection, as outlined in Section G we train a set of 20 models using the training data from CIFAR-10 and MNIST. These models encompass two distinct architectural designs, resulting in ten models trained under each architecture. For each class label within these dat datasets, two models with differing architectures are trained. These models exhibit bias towards the specific class label they are trained on, utilizing portion of the training dataset that contains greater number of samples from that class compared to the other classes. For the CIFAR-10 dataset, len CNNs are trained using the VGG architecture (Simonyan & Zisserman 2015) with 2 blocks, while the remaining ten are trained using VGG architecture with 3 blocks. The training data for each model is non-i..d. sampled from the 50, 000 training samples. Precisely, each CNN is trained on 9, 500 training data samples, consisting of 5, 000 samples from one class and 500 samples drawn from the training set of each of the other nine classes. Similarly, for the MNIST dataset, ten CNNs are trained using VGG with one block, and the other ten are trained using VGG with 2 blocks. To train each model, 6, 900 data samples are drawn from the training set, with 6, 000 samples belonging to one class and 100 samples from each of the other nine classes. Additionally, the testing data samples for CIFAR-10 10 and MNIST are distributed among clients in a non-i.id. manner. For CIFAR-10, each client receives 155 testing data samples from one class and 5 samples from each of the other nine classes. In the case of MNIST, each client receives at least 133 samples from one class and at least 5 samples from the other classes. The 200 testing data samples are randomly shuffled and are sequentially presented to each client over T = 200 learning rounds. Morcover, for online regression task, the performance of algorithms are tested on the following datasets (Kelly et al. 2023
Each data sample has 14 features including information related to air quality such as concentra- tion of some chemicals in the air. Data samples are collected from different goographical sites. The goal is to predict the concentration of CO in the air (Zhang el al. 2017).
Air:
WEC: Each data sample has 48 features of wave energy converters. Data samples are collected from 4 different geographical sites. The goal is to predict total power output (Neshat et al. 2018
For each regression dataset, 20 fully-connected feedforward neural networks are trained. All neural networks have 5 hidden layers each with 100 hidden ncurons. ReLU activation function is employed for all hidden neurons in all nelworks. In order to train models for Air datasel, 10 neural networks are trained on 30, 000 samples from the site Dongsi with different initialization while other 10 neural networks are trained on 30, 000 samples of Dingling site with different initialization. In the experiments, data samples of Air dataset are distributed non-i.i.d among clients such that 50 clients observe data samples from Aotizhongxin site while other 50 clients observe data samples from Changping site. To train models for WEC dataset, 10 neural networks are trained on 70, 000 samples from the site in Sydney with different initialization. The remaining 10 neural networks are trained on 70, 000 samples from the site in Tasmania with different initialization. Data samples of WFC dataset are distributed non-i.i.d among clients such that 50 clients observe data samples from Adelaide site while other 50 clients observe data samples from Perth site. In the experiments, using Fed-OMD and PerFedAvg, each client performs one epoch of stochastic gradient descent (SGD) with learning rate of 0.001 on its batch of data to fine-tune the model. In order to perform fine-tuning, clients start to update models after 50 learning rounds so that clients can store 50 samples in batch. All experiments were carried out using Int)l(R) (T)) 17-10510U CPU @ 1.80 GHz 2.30 GHz processor with a 64-bit Windows operating system.
Table 3 shows the average accuracy of clients along with its standard deviation on CIFAR-10 and MNIST datasets with the change in the memory budget when clients employ OFMS-FT. Moreover, Table 4 demon- strates the average MSE and its standard deviation across clients for different memory budgets on Air and
20

---

Published in Transactions on Machine Learning Research (02/2024)
Table 3: Average and standard deviation of clients' accuracy using OFMS-FT over CIFAR-10 and MNIST with the change in budget.
Budget
CIFAR-10
MNIST
B: Vi E [N]
70.01% + 6.96%
89.87% + 3.33%
B; = 5, vi E [N]
76.77% + 4.46%
92.05% + 2.69%
B, = 10, E [N]
79.90% + 4.23%
92.93% + 2.58%
Table 4: Average and standard deviation of clients' MSE (x10 using OFMS-FT over Air and WEC with the change in budget
Budget
Air
WEC
B, = 2, E [N]
7.51 + 4.82
8.27 + 1.56
B. 5, [N]
7.46 5.10
7.09 + 1.67
B, 10, Vi [N]
7.38 4.86
6.99 + 1.63
WEC datasets when clients use OFMS-FT. Results in Tables 3 and confirm that if clients have larger memory, the accuracy of OFMS-FT improves.
We report the times of algorithms in Table 5 Run time refers to average total run time of clients to perform their prediction task on the entire data samples that they observe up until time horizon T. In Table 5 OFMS-FT, B; = 5, and OFMS-FT, B; refer to the proposed algorithm with budgets B, = 5 and B, = 2, respectively. Table 5 shows that other algorithms run faster than OFMS-FF ST while OFMS-FT outperforms others terms of accuracy (see Table D.. OFMS-FT runs slower since OFMS-FT evaluates and fine-tunes multiple models each round. Comparing the run times of OFMS-FT,, B, with OFMS-FT B, shows that the time complexity of OFMS-FT can be controlled by budget. In time-sensitive scenarios, the budget can be chosen such that OFMS-FT can fulfill required computations before the start of the next round.
D Supplementary Discussions and Analysis
This section presents extended discussions on performance analysis of OFMS-FT.
D.1 Supplementary Analysis
In sections 3 and it is assumed that at each learning round t, each client observes one data sample and commmicate with the server every learning round. This subscction analyzes the regret of OFMS-FT when clients communicate with the server every n 2 1 learning rounds. Every round that clients communicate with the server called communication round. Therefore, the number of communication rounds U is [_]. Let the communication occurs at learning round Tu- Without loss of generality, we assume that Tu n(uu - 1) ++ 1. In this case, at commmication round u, client i draws the model index I,, using the PMF specified in equation Then client splits all models except for model I,,, into clusters DI Dim;. such that the cumulative cost of models in each cluster does not exceed B, - Cl.. Then client i draws one of the clusters uniformly at random. Let Jim denote the index of the selected cluster. Client i downloads all models in th cluster in addition to model I Upon receiving models, client computes the importance loss estimate as
Tuti11
[(fa( Ok.u): I(k E Si,u)
lika
(43)
qsk.u
t=Tu
21

---

Published in Transactions on Machine Learning Research (02/2024)
Table 5: Average run time (s) of clients on CIFAR-10, MNNST, Air and WEC datasets.
Algorithms
CIFAR-10 10
MNIST
Air
WEC
MAB
9.43
9.34
8.89
9.51
Non-Fed-OMS
57.38
62.09
57.56
52.70
Fed-OMD
32.80
23.24
15.86
15.64
PerFedAvg
47.61
32.21
19.29
22.03
OFMS-FT, B; 5, Vi
145.91
99.49
55.59
55.69
OFMS-FT, B; 2, Vi
64.42
43.06
27.78
28.82
where 4 denote the parameter of model k between communications rounds and u+ and S is subsot of models stored by client between communications rounds u and u + 1. Also, lik,u can be obtained
Pij.ru
Pik,ru
(44)
Mijau
where aijaa denote the number of model clusters at communication round u if Iz = Morcover, importance sampling gradient estimate is calculated as follows by client
Tutl-1
Viskku
a VL(fl(E OR.). E Da, k E Si,.)
(45)
qik,u
where D,, represents a subset of clients chosen by the server at communication round to fine-tune models. The rest of procedures and definitions are the same as Algorithm [ and Section 3 Moreover, when clients communicate with the server every n learning rounds, the i-th client regret R1, and the server regret Sk, associated with model & are defined as
Tuti-1
R4T
E,
C(f (xI,,) On.)..
min KE(K]
(
(46a)
Tuti-1
N
U
Tuti-1
Sk. = N
C(falze, Ox.)),
C(fa(ru,) 07). vs.))
(46b)
N
t=
where E.[t] denote the expected value given observed losses up until communication round The following Theorem obtains the regret upper bound for OFMS-FT when clients communicate with the server every n learning rounds.
Theorem 3. Assume that client i, Vi [N] communicates with the server every n learning rounds. Under (a1) and (a2), the expected cumulative regret of the i-th client using OFMS-FT bounded by
RLT S In K
+ TmuaT.
(47)
T
which holds for all i E [N]. Under (a1) (a4), the cumalative regret of the server in fine-tuning model k using OFMS-F" is bounded by
1 N
R
SET S
+
Σ
(48)
2ns
N
1=1
Proof. see subSection D.2
If client sets
(Vinns)
In
7i 0
(49)
22

---

Published in Transactions on Machine Learning Research (02/2024)
then the i-th client achieves sub-linear regret of while the server achieves sub lincar regret of by setting
RT S O ( ()na))
(50)
an? N Σ
SE.T
S0
14
(51)
7 0
(52)
TnT NNN
Zi=1 14g
As be inferred from theorem 3 and regret analysis presented in this subsection, the increase in n, degrades the regret upper bound of both clients and the server. Increase in causes that clients update their stored models fewer times and this reduces the flexibility of model selection for clients. Also, increase in n leads to fine-tuning models less often which can adversely affect the prediction accuracy of models.
D.2 Proof of Theorem 3
Substituting lkg with Esk,u in equation 17 and following the steps from equation 17 Lo equation 23
get
U
K
U
K
In
7
Pik.T lik
Cak.u
Psk.Tu
(53)
76b
2
u= 1
u=1
u=1
km
Moreover, the expected value of ls and Ge given observed losses till communication round u, can be obtained as
Ey Bal
[(fe(ar, Ok, va.e)
Pik,
Pajsta
Mijaa
Tu41
(if Ok,w),
(54)
Furthermore, using arithmetic-mean geometric-mean (AM-GM) inequality, li can bounded from above as
Σ [(fa(Ei, Ok.a)) Vi.e) I(k: E Sinaa)
L. S n
(55)
Morcover, based the assumption that 0 I C(fe(as, Ok.)). vi.e) I given the observed losses in prior rounds, expected value of Ce can be bounded from above
En qik,u
[(fa(zn,e Ou.)). 21.e) I(k St.w)) )
Cf OR.W..
Pikira
Σ
Pitfta
Pik.
Mijaa
L (fr (ab O O.. Vaeed
1
(56)
qik
qik.a
Combining equation 55 with equation
56
we arrive at
n2
E2 L2 <
(57)
Gek,u
23

---

Published in Transactions on Machine Learning Research (02/2024)
Taking the expectation from both sides of equation 53 and considering the fact that 2 0, it can be concluded that
U Tu+t
K
Tu+t
Σ
(f On.)), y1.))
Σ
E t=Tu
((f On,)),
Pik,r
U
K
In
K
m
Pik,7u
(58)
qikiu
Moreover, it can be written that
Tu+t1
Tu++1 K
E
Σ
( Ox,),
Σ
Pik.Ta
(( Ok,): Mi.e)
(59)
T-T
I k=1
Considering the facts that equation
29 holds true for Pik,ra and Tik,us wk: E [K] and nU T, conclude
that
-1
Eu
Clfre, (k.),,
M=
In K
(60)
which obtains the regret of client using OFMS-FT when the i-th client communicates with the server every n lcarning rounds. Similar to Est,e, define lik, as
Tu+t
lsk
( Vi E Da, S.,.)
(61)
qik,u
Moreover, substituting lute with lsk in equation 32 equation 36
and following the derivation steps from equation to
we obtain
N Bit
N Tw---1
[(fa(ai,1 0), Ii, E Da. &c E Si.w)
1=1
i=l
N (10x,u
011
110 - -112))+ +
V Veska
(62)
2nf
2NV
Expected value of Eix, and ||V 1|? can be obtained as
Tul1
Ey Eitul
C(fa Ox.a). vk.e) x
Pik,Ta
Pij.ru
qik.u
a
am.jj.
Tutt-1
Σ
[(fx(
Ox.u), Vi.e)
(63a)
a²
E.
V
Pik,tu a
PijiTa
Tik.u
amija
Futi-1
VC(ff Ok,)), ve..)
qikau
Tut1-1
an?G²
on
<
(63b)
qikuu
aik.u
24

---

Published in Transactions on Machine Learning Research (02/2024)
where the last two inequalities in equation 63b obtained using AM-GM incquality and the assumption that (V vi,)ll v G Moreover, using AM-GM inequality and equation 63b we can write that
N
an
En
Σ i=1
S
B. [
S
(64)
Taking the expectation from both sides of equation 62
we get
To+1 -1
Tut1-1
((fe(zl, (..)
((fa(or.)))
t=1
T
an
7
(1 -
+
(65)
2nf
2
Qik,a
Following derivation steps from equation 39 to equation
41
using equation
65 we can obtain
Tut1-1
N Tut1-1
ΣΣ
Σ
11
T
an2
(66)
2ns
2
qikeu
i=
Considering the fact that qik,u 2
(see equation
29
using equation 66
we arrive at
2pc
N
Tut1-1
Σ
11 u=1
u=1
N N1
(67)
2nf
which proves the theorem.
25


Reviews:
[{"review_id": "ha0ESjx0DW", "reviewer": "Reviewer_EDLF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper are 1. That the problem is fairly interesting -  model selection in online learning is a popular and important topic, and methods which are aware of storage and computational budgets are likely to become more and more popular as models continue to become larger, and sustainability/efficiency becomes increasingly important in ML. 2. That the problem is well specified and the contribution of the paper is well-defined, and (as far as I am aware) novel. 3. That the proposed method is effective on the provided experiments, outperforming some reasonable competitors.\n\nMy biggest concern is around the definition of (and subsequent results on) the server’s regret (12). I think it is possible for this term to become negative for sufficiently large $T$, since the performance of the best possible single action in hindsight could be beaten by the performance of actions which are optimised on a per-client basis, which I believe the OFMS-FT algorithm allows for. As such, it’s not obvious how good $\\tilde{O}(\\sqrt{T})$ regret is for this problem, without further lower bound analysis of this quantity. Curiously $S_T$ is actually higher than $\\sum_{i=1}^N {R}_{i,T}/N$, the opposite of what I would have expected. I would like to be convinced either that I am mistaken in my concerns about ${S}_T$, that something can be added to justify the usefulness of the ${S}_T$ result, or that something can be added to justify how difficult it would be to go further than this and that what is presented is state-of-the-art and raises an interesting open question. To be sure, I believe that while the section ‘Challenges of Obtaining Regret in (16)’ does consider the challenges induced by communication constraints, it doesn’t address the fact that there may exist a combination of models per agent that may have lower loss in hindsight than the best model overall in hindsight. This is an essential change for me, and currently is preventing me giving a positive score. My subsequent paragraphs of comments are ordered in decreasing importance.\n\nI’m not totally clear on how Fed-OMD is being used – is it that a single model is picked rather than the dictionary, or a subset? If so, which model(s) (is it at random)? Similarly, I don’t think the nature of PedFedAvg is clear to the reader from the short comments made about it, and I was curious why it is not mentioned in the main related work section if it is related enough to run in the experiments? Section 5 should at least reference the existence of the material in Section D.\n\nTwo questions re the experiments: 1. I found it hard to figure out how many meta-replications the experimental results are averaged over – can you clarify that, and 2. Did you do experiments with different learning rates? If not, how would you recommend someone applying this model chooses the learning rate for a new problem?\n\nI was curious as to whether you think the selection of clients for parameter fine-tuning could be done better than uniformly at random. Would it have benefitted the server to know which clients have larger/smaller gradients and adjust for this somehow? Or is it expected that the randomised choice of $\\mathbb{C}_t$ will work as well as can be achieved given the budget $\\Omega$?  \n\nThere are parts where the notation could be more intuitive. For instance, decision variables could all be the same kind of symbol, but there are some which are upper case Latin letters, some are lower case and some are Greek. Similarly it is often intuitive to keep similar letters for similar purposes – this is sometimes done k indexes the set {1,…,K} but $b_k$’s sum to $\\beta$ which is bounded by $\\Omega$, while $B$ is being used to bound a different notion of cost for instance; elsewhere $c$ is a cost, $\\mathcal{C}$ is a cluster, $\\mathbb{C}$ is a group of clients, and $C$ is a bound on the norm of regression parameters. There is a lot going on notationally and algorithmically in the paper and I feel the reader has to work harder to follow it because of some of these choices of notation.\n\n\nSome points that are minor, but I think easy to fix and worth raising:\n-\tSection 1 Paragraph 1: ‘the sheer volume of data’ is a weird phrasing here, maybe just ‘the data’ would be fine.\n-\tSection 2: I don’t think $T$ is ever formally defined.\n-\tSection 2 Paragraph 1: ‘larger storage capacity store models’ should be ‘larger storage capacity stores models’\n-\tSection 2 Para 1: ‘Let [K] denotes the set’ should be ‘Let [K] denote the set’ (similar on page 3 and with other verbs in multiple parts of the manuscript)\n-\tSection 2 Para 1: ‘studies adversarial setting’ should be ‘studies the adversarial setting’ (again occurs in multiple instances)\n-\tSection 2 Para 1: should it be that the environment chooses the label rather than the loss adversarially? If it chooses loss, and different labels could have the same loss, then you need to assume another rule for how losses map to labels; or explicitly assume a 1-1 mapping from loss to label for all x, theta, and I. If you just let the environment choose the label, you shouldn’t need to worry about this.\n-\tSection 3.1 Para 1: there are grammar issues in the last sentence\n-\tSection 3 and onwards: I think there are a lot of equations numbered that are not referenced?\n-\tSection 4: Should (a1) also be an assumption on all $k \\in [K]$?\n-\tReferences: Cella et al. and Deng et al. do not have a publication venue associated with the reference.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of online model selection - where data arrives sequentially and an agent wishes to select an appropriate prediction model from a set ('dictionary') of candidate models. The particular novelty in this paper is to consider a budgeted setting, where an agent has constraints on how many candidate models it can consider. This is motivated by learning on devices with limited storage.\n\nThis broad challenge is tackled in a specific setting where a group of learners ('clients'), who have limited storage capacity, learn in a federated manner governed by a server, which has sufficient capacity to store all models in the dictionary. Clients store (time-varying) subsets of models from the dictionary and send updated parameters (the 'fine-tuning' step referenced in the title) to the server following rounds of prediction.\n\nThe contribution of the paper is an algorithm for clients to employ in this regime (OFMS-FT), an analysis of the regret of OFMS-FT (which yields a sub-linear upper bound in an adversarial setting with constraints on the amount of communication between clients and the server), and experimental results which compare OFMS-FT to other algorithms which are not designed for the present task but for online federated learning (without model selection), or online model selection (without federation), or federated model selection (but offline). OFMS-FT outperforms these in terms of cumulative prediction accuracy metrics.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My requested changes follow from the weakness mentioned above. The most critical is to address the point about server's regret, but I would also consider clarity on the competitor algorithms and questions about the experiments critical to securing an acceptance recommendation. The remainder are just points to consider to strengthen, but I'd be disappointed if the bullet pointed minor remarks couldn't be addressed as I think they are straightforward and not contentious.", "broader_impact_concerns": "This isn't explicitly so far as I can see. I would consider it good practice to add a reflection on this in the Appendix, but I don't think it is critical for this paper, as the work is fairly far from applications and I see any discussion of negative impacts as likely being highly speculative, as is typical for this flavour of theoretical/methodological online learning papers.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XHdYNzTH8i", "reviewer": "Reviewer_qwhj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think that the motivation for the setting is strong, however, the assumption that the losses are adversarial is not realistic to me. I think that a more suitable modeling would either assume a stochastic stationary setting, in which the dataset we are using for the online learning processs are fixed, or a non.stationsary setting, in which the dataset presents a variation over time for stochastic reasons.\n\nFollowing the description of the algorithm is difficult. I would suggest providing the description with the corresponding lines of the pseudocode.\nMoreover, adding an overall description of the algorithm could be beneficial for its comprehension.\n\nThe experimental part is convincing. I would have also appreciated a more detailed sensitivity analysis, e.g., on the budget parameters. For instance, how is the performance when the budgets for the different clients are different?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studes the problem of online model selection in a federated learning scenario in which the communication and the storage space of the clients are limited. The authors proposed a novel algorithm based on the clustering of the available models and their update according to the losses. They study the bounds on the regret from an adversarial point of view and provide some experiments to validate the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Comments and minor changes:\n\"privately determined by the environment\" it is not clear why\ni.e. -> i.e., same for e.g.\nThe problem formulation lacks of the definition of the objective that algorithms has to optimize.\n(5) -> Equation (5) similarly in the entire paper\nDefine the acronyms\nAdd punctuation to formulas\nsection 4 -> Section 4\n\"bin-packing algorithms such as FFD can be employe\" please provide a reference\nPlease anticipate the definition of the regret, for instance in the problem formulation\nDid you evaluate the errors and accuracies over a test set for each client and then averaged?", "broader_impact_concerns": "I do not foresee any ethical concern being a theoretical work", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oyHk2NFReQ", "reviewer": "Reviewer_CpQM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n - The paper introduces and solves a relevant OFL problem.\n - The motivation of the algorithm design is well supported with a mathematical theorem.\n - The theoretic effectiveness is supported by a thorough regret analysis.\n\nWeaknesses:\n - Some experiment design choices are not motivated.\n - The baseline algorithms are not adapted to the experiment setup in a way that allows fair comparison.\n - The 3rd contribution, server-side client selection is not compared to SoTA client selection in federated learning, and the related works section does not discuss this line of research.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focuses on Online Federated Learning (OFL). The contributions are threefold: firstly, it proposes leveraging Online Model Selection (OMS) to achieve better client-side accuracy in OFL. Secondly, it designs an algorithm to select models in a scenario where the client has limited memory and cannot transfer all models from the server to make OMS locally. Finally, it proposes a method to deal with limited bandwidth on the server side for incoming client model updates.\n\nThe authors support their algorithm design with a detailed regret analysis. Furthermore, they design experiments using classification and regression tasks. They adapt several baseline algorithms to this setting and show their method is competitive compared to them.\n\nI would like to thank the authors for sharing their research as I believe this paper has contributions that are in TMLR's audience's interest.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical:\n\n1. In simulated FL the data distribution is crucial for the model performance. It should be discussed in the main paper, not in the appendix.\n2. What motivates the choice of 1 majority class in the data distribution? 2 majority classes can be also seen in non-IID experiments in the FL literature. Is it typical in OFL?\n3. It is not clear to me in the experiment description: \n    a) does MAB use the same pre-trained model as Fed-OMD, PerFedAvg, and OFMS-FT at the start? \n    b) Does Non-Fed-OMS train the locally stored models?\n4. in case Non-Fed-OMS does not do this, I am missing a baseline where clients and server train $B$ models together, while clients select one of them using OMS locally. This would support the use of more server-stored models.\n5. I am missing a baseline where the server stores the same number of models as OFMS-FT, but the clients select the $B_i$ models randomly. This would support the use of the defined $z$ weights.\n\nIf server-side client selection is in the scope of the paper:\n\n6. Server-side client selection is not compared to any baseline (or not discussed in section 6's last paragraph) Either say it is out of the scope of the paper or support with more experiments.\n7. In the current regression tasks, there are 20 models, 100 clients, clients update $B=5$ models, and the update bandwidth $\\Omega=250$ (\"only half the clients are able to send their updated model to the server\"). Because the clients have very unbalanced datasets, the server might benefit more from seeing all the clients in all rounds resulting in an overall balanced set of data in the training rounds. E.g. this can be achieved if the clients reduce their model memory to half, each client updates fewer models but the server sees all clients (with the current setup it would mean $2.5\" models from each client.\n8. Client selection is missing from the related works See this taxonomy as a reference: [r1]\n9. Server-side client selection should be evaluated compared to SoTA client selections. For example [r2] also works with gradient estimates for unseen clients.\n\nMinor:\n\n10. Section 2. \"Each model...\" sentence defines $\\mathcal{X}$ and $\\mathcal{Y}$ but no part of the paper builds on this sentence, which could be removed for a more clear read.\n11. Section 3.1 PMF acronym never defined.\n12. $\\mathcal{F}$ and $\\mathbb{F}$ font styles are both representing sets, while $\\mathcal{F}$ also represents vector spaces and probabilities. It could be confusing.\n13. The number of model clusters is represented with $m$ (in section 3.1 $m_{i,t}$ for the $i$ client in $t$ round and $m$* for the minimum), $o_{ij,t}$ in the same section a few paragraph later and $v_{i,j}$ for the minimum number of clusters in section 4.\n14. At the end of section 3.1 I would add clarity on the exp() function's behavior: it keeps the weights the same if not updated. Otherwise, the higher the loss the more the weight is reduced.\n15. An experiment where more small models than big ones can fit into the clients might be interesting. With $c_{small}=0.89$ and $B=5$ it is the same 5 models per clients as $c_{big}=1$\n\n\n[r1] Németh, G. D., Lozano, M. A., Quadrianto, N., & Oliver, N. M. (2022). A Snapshot of the Frontiers of Client Selection in Federated Learning. Transactions on Machine Learning Research.\n\n[r2] Chen, T., Giannakis, G., Sun, T., & Yin, W. (2018). LAG: Lazily aggregated gradient for communication-efficient distributed learning. Advances in neural information processing systems, 31.\n\nI think overall the paper has clear contributions and by fixing 1-5 it could be strengthened to an even better level. 6-9 are only critical if the client selection is in the scope of the paper. 10-15 would improve the clarity of the paper in my opinion.", "broader_impact_concerns": "I do not have concerns about Broader Impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers recommended an acceptance. During the discussion period, a major concern regarding the regret measure used in the paper was raised: the server’s regret can be negative since the performance of the best possible single action in hindsight could be outperformed by the performance of actions which are optimised on a per-client basis. The revised manuscript has addressed this critical issue by revising the definition of server regret. The revised manuscript has adequately addressed several questions concerning the experimental setup and client selection.
Decision: Accept (poster)