Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback
Authors: Boxin Zhao
Ziqi Liu
Chaochao Chen
mladen kolar
Zhiqiang Zhang
JUN ZHOU
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Client Sampling
Optimization

Abstract: Due to the high cost of communication, federated learning (FL) systems need to sample a subset of clients that are involved in each round of training. As a result, client sampling plays an important role in FL systems as it affects the convergence rate of optimization algorithms used to train machine learning models. Despite its importance, there is limited work on how to sample clients effectively. In this paper, we cast client sampling as an online learning task with bandit feedback, which we solve with an online stochastic mirror descent (OSMD) algorithm designed to minimize the sampling variance. We then theoretically show how our sampling method can improve the convergence speed of optimization algorithms. To handle the tuning parameters in OSMD that depend on the unknown problem parameters, we use the online ensemble method and doubling trick. We prove a dynamic regret bound relative to any sampling sequence. The regret bound depends on the total variation of the comparator sequence, which naturally captures the intrinsic difficulty of the problem. To the best of our knowledge, these theoretical contributions are new and the proof technique is of independent interest. Through both synthetic and real data experiments, we illustrate advantages of the proposed client sampling algorithm over the widely used uniform sampling and existing online learning based sampling strategies. The proposed adaptive sampling procedure is applicable beyond the FL problem studied here and can be used to improve the performance of stochastic optimization procedures such as stochastic gradient descent and stochastic coordinate descent.

Under review as a conference paper at ICLR 2023
ADAPTIVE CLIENT SAMPLING IN FEDERATED LEARN- ING VIA ONLINE LEARNING WITH BANDIT FEEDBACK
Anonymous authors Paper under double-blind review
ABSTRACT
Due to the high cost of communication, federated learning (FL) systems need sample subset of clients that involved in each round of training. As result, client sampling plays an important role in FL systems as affects the convergence rate of optimization algorithms used train machine learning models. Despite its importance, there limited work on how to sample clients effectively. In this pa- per, cast client sampling as an online learning task with bandit feedback, which we solve with an online stochastic mirror descent (OSMD) algorithm designed to minimize the sampling variance. We then theoretically show how our sampling method can improve the convergence speed of optimization algorithms. To handle the tuming parameters in OSMD that depend on the unknown problem parameters. we use the online ensemble method and doubling trick. We prove dynamic regret bound relative to any sampling sequence. The regret bound depends on the total variation of the comparator sequence, which naturally captures the intrinsic diffi- culty the problem. To the best of our knowledge, these theoretical contributions new and the proof technique is of independent interest. Through both syn- thetic and real data experiments, we illustrate advantages the proposed client sampling algorithm over the widely used uniform sampling and existing online learning based sampling strategies. The proposed adaptive sampling procedure is applicable beyond the FL problem studied here and be used to improve the performance of stochastic optimization procedures such as stochastic gradient descent and stochastic coordinate descent.
INTRODUCTION
Modern edge devices, such as personal mobile phones, wearable devices, and sensor systems in vehicles, collect large amounts of data that valuable for training of machine learning models. If each device only uses its local data to train a model, the resulting generalization performance will be limited due the number of available samples on each device. Traditional approaches where data are transferred to a central server, which trains a model based on all available data, have fallen of fashion due to privacy concerns and high communication costs. Federated Learning (FL) has emerged as paradigm that allows for collaboration between different devices (clients) to train global model while keeping data locally and only exchanging model updates (McMahan et al.) 2017).
In a typical FL process, we have clients that contain data and a central server that orchestrates the training process (Kairouz et al. 2021). The following process is repeated until the model is trained: (i) the server selects a subset of available clients; (ii) the server broadcasts the current model parameters and sometimes also training program (e.g.. Tensorflow graph (Abadi et al. 2016);; (iii) the selected clients make updates to the model parameters based on their local data; (iv) the local model updates uploaded to the server; (v) the server aggregates the local updates and makes a global update of the shared model. In this paper, we focus on the first step and develop a practical strategy for selecting clients with provable guarantees.

---

Under review as a conference paper at ICLR 2023
To train machine learning model in FL setting with M clients, we would like to minimize the following objective
min F(w)= = Σ
Am (w; Dm),
(I)
mE[M]
where o(w; pm) is the loss function used to assess the quality of a machine learning model param- eterized by the vector w based on the local data Dm on the client m E [M.) The parameter Am denotes the weight for client m. Typically, we have Am = Rmm/n n. where 7m = [Dm is the number M Em=1 Rmm- At the beginning
of samples on the client m, and the total number of samples is
of the t-th communication round, the server uses the sampling distribution p (pi..... .......M)' to choose K clients by sampling with replacement from [M] Let S S [MM] denote the set of chosen clients with | = K. The server transmits the current model parameter vector w² to each client m E St. The client computes the local update 9'n and sends it back to the server After receiving local updates from clients in S", the server constructs a stochastic estimate of the global gradient as
1 g = K
Σ MEST
Am
Im.
Pin
and makes the global update of the parameter w² using g¹. For example, w = w² Heg.. . if the server is using stochastic gradient descent (SGD) with the stepsize sequence {pe (Bottou al. 2018). However, the global update can be obtained using other procedures as well.
The sampling distribution in FL is typically uniform over clients, p' = = (1/M T/.
However, nonuniform sampling (also called importance sampling) can lead to faster convergence, both in theory and practice, as has been illustrated in stochastic optimization (Zhao & Zhang 2015] Needell et al. 2016). While the sampling distribution can be designed based on prior knowledge (Zhao & Zhang 2015: Johnson & Guestrin 2018, Needell al., 2016 Stich al. 2017), we cast the problem of choosing the sampling distribution as an online learning task and need no prior
knowledge about equation [
Existing approaches to designing a sampling distribution using online learning focus on estimation of the best sampling distribution under the assumption that it does not change during the training process. However, the best sampling distribution changes with iterations during the training process, and the target stationary distribution does not capture the best sampling distribution in each round. In the existing literature, the best fixed distribution in hindsight is used as the comparator to measure the performance of the algorithm used to design the sampling distribution. Here, we focus on mea- suring the performance of the proposed algorithm against the best dynamic sampling distribution. We use an online stochastic mirror descent (OSMD) algorithm to generate a sequence of sampling distributions and prove regret bound relative to any dynamic comparators that involve total vari- ation term that characterizes the intrinsic difficulty of the problem. To the best of our knowledge, this is the first bound the dynamic regret with intrinsic difficulty characterization in importance sampling. Moreover, we theoretically show how our sampling method improves the convergence guarantee of optimization method by reducing the dependency on the heterogeneity of the problem.
1.1 CONTRIBUTIONS
We develop an algorithm based on OSMD that generates a sequence of sampling distributions {p' 1p' based on the partial feedback available to the server from the sampled clients. We prove a bound on regret relative to the any dynamic comparators, which allows us to consider the best se- quence of sampling distributions as they change over iterations. The bound includes a total variation
We use [M] to denote the set (1....M)..
"In this paper, assume that all clients available in each round and the purpose of client sampling to reduce the communication cost, which is also the case considered by some previous research (Chen et al. 2020). However, in practice, it is possible that only a subset of clients are available at the beginning of each round due to physical constraint. In Appendix H.2 we discuss how to extend our proposed methods to deal with such situations. Analyzing such extension highly non-trivial and we leave for further study. See detailed discussion in Appendix [H.2
'Throughout the paper we do not discuss how gfn is obtained. One possibility that the reader could keep in mind for concreteness is the LocalUpdate algorithm Charles & Konečny 22000) which covers well-known
algorithms such as mini-hatch SGD and FedAvg (McMahan et al. 2017).
2

---

Under review as a conference paper at ICLR 2023
term that characterizes the intrinsic difficulty of the problem by capturing the difficulty of following the best sequence of distributions. Such a characterization of problem difficulty is novel. Besides, theoretical result can recover the results in previous research special cases and is thus strictly more general. Moreover, we theoretically improve the convergence guarantee of optimization al- gorithm by using sampling scheme over uniform sampling. We show that adaptive sampling can help reduce the dependency on the heterogeneity level of the problem. We also mkae contribu- tions in experiments and practical parameter tuning strategy. See Appendix A.] for more detailed discussion of our contributions.
1.2 RELATED WORK
Our paper related client sampling in FL. importance sampling in stochastic optimization, and online convex optimization. We summarize only the most relevant literature, without attempting to provide an extensive survey. Due to space limit, we only summarize the first direction here, and leave the discussion about importance sampling in stochastic optimization and online convex optimization in Appendix B
For client sampling, Chen et al. 2020) proposed to use the theoretically optimal sampling distribu- tion to choose clients. However, their method requires all clients to compute local updates in each round, which is impractical due to stragglers. Ribbroo & Vikalo (2020) modelled the parameters of the model during training by an Ornstein-Uhlenbect process, which was then used to derive an optimal sampling distribution. [Cho et al. (2020b) developed a biased client selection strategy and analyzed its convergence property. As result, the algorithm has a non-vanishing bias and is not guaranteed converge to optimum. Moreover, needs involve more clients than our method and is thus communication and computational more expensive. Kim et al. (2020); : Cho et al. (2200);; Yang al. (2020) considered client sampling as a multi-armen bandit problem. but provided only limited theoretical results. Wang et al. (2020) used reinforcement learning for client sampling with the objective of maximizing accuracy, while minimizing the number of communication rounds.
1.3 NOTATION
Let R = [0, )M) and R (0, oc) For M E N+, let PM-1 PM- RM E 2, 1}
be the (M - 11)- -dimensioonl probability simplex. We p (p1, (p1...., PM to denote sampling distribution with support on [M] == {1, {1..... M). We use y1: to denote a sequence of sampling distributions {r') Let +-
R be differentiable convex funetion defined D, where D is convex open set, and we use D to denote the closure of D. The Bregman divergence
R
between any x, y D with respect to the function is given as D& (x (1 (xx) p
(V x - y). The unnormalized negative entropy is denoted as (x(x) = -m==1 Im log Im Em=1 Zm.
(II
D RVW. with 0 log 0 defined as O. We use Ilp denote
the L,- norm for S p S 0c. For E R", we have ||æ/|p- = (Ei= x 1/p when < p < oo, ||=||| Σ |r;] and | maxigign | Given any norm ||, we define its dual norm as ||2||, = sup f x: ||||| 1).
For two sequences } and [bn]. we use an = O(b.)) or on S bn if there exists C > 0 such that lan/bal < C for all n large enough; on @(bb)) if an O(bn) and bn O(a,) simultaneously. Similarly, an Ö(b,) if a, Ob, log bn) for some k > 0: a, ((b,)) if an Ö(b,) and bn = Ō(a,) simultaneously.
1.4 ORGANIZATION OF THE PAPER
We motivate importance sampling in FL, introduce adaptive client sampling algorithm, and tablish bound on the dynamic regret in Section 2 We derive optimization guarantee of mini-batch SGD using sampling scheme in Section
Due to space limit, we leave additional contents in appendix. More specifically, we give additional related work summary in Appendix In Appendix C.3dixx C.3)and Appendix C.4 .,4 we design two extensions
to the sampling algorithm that make it adaptive to the unknown problem parameters. We leave
detailed algorithm descriptions and theoretical properties of adaptive methods in Appendix C We
3

---

Under review as a conference paper at ICLR 2023
provide the experimental results synthetic data in Appendix F and real-world data in Appendix G
Sampling without replacement is discussed in Appendix C.5 and Appendix F.4
Finally, we give
conclusions and discussions about future directions in Appendix
ADAPTIVE CLIENT SAMPLING
We show how to cast the client sampling problem as an online learning task. Subsequently, we solve the online learning problem using OSMD algorithm and provide a regret analysis for it.
2.1 CLIENT SAMPLING AN ONLINE LEARNING PROBLEM
Recall that at the beginning of the t-th communication round, the server uses sampling distribution p' to choose set of clients S by sampling with replacement K clients from [M.] to update the
parameter vector w For chosen client E St. the local update denoted g For example, the
local update 9'n = ; ;m,) may the full gradient; when mini-batch SGD/FedSGD is used,
then Im (L/B) E V where gt i.1dd Dm and B is the batch size; when FedAvg
is used, then I'm = (w"n w²'/ //haalal where w = w mmbb-1 Mooca V
(mmb-1 Si.iiiimni)))
b E [B], w/m = w', Sm.6 1..dd Dm, and Moocl is the local stepsize. We define the aggregated oracle update at the 1-th communication round as
J
Ama'n
The oracle update is constructed only for theoretical purposes and is not computed in practice.
The stochastic estimate g", defined in equation?? 2 is an unbiased estimate of J that is, Eg: [g"] = J Note that we only consider the randomness of St and treat I'm as given The variance of g is
1 K
M
I 12 - || P'm
(3)
Our goal design the sampling distribution p¹, used to sample St, so minimize the variance in equation 3 In doing so, we can ignore the second term as it is independent of p'.
Let
X
gtt 12..
For any sampling distribution q (g...... qas) the variance reduction
loss is defined as
5
d
le(g)
4m
Given sequence of sampling distributions 1:T, the cumulative variance reduction loss is defined ITq = DT,44000 le(4).. When the choice of q 1:T is random, the expected cumulative variance reduction loss is defined as I(y E (:T):))) )
The variance reduction loss appears in the bound on the sub-optimality of stochastic optimization algorithm. As motivating example, suppose F(-) in equation is o-strongly convex. Furthermore, suppose the local update 9' Vo(w"; Dm, is the full gradient of the local loss and the global update is made by SGD with stepsize be 2/(ot). Theorem 3 of Salehi et al. (2017) then states that for any T 2 1:
2 ] F(w*)= oT(T 1)
E
F
2
Σ w²
I(p
T(T +1)
'The randomness comes from two sampling processes. The first sampling happens clients level, and the second sampling happens locally when choosing samples. To ease the understanding, one may treat of, full local gradient.
'The variance reduction loss 4()) should be distinguished from the training loss (l.). While the former is always convex, o6-) be non-convex.
4

---

Then the Under review as a conference paper at ICLR 2023
where w* is the minimizer of the objective in equation| I Therefore, by choosing the sequence of sampling distributions p!. to make the L(pl:T) small, one can achieve faster convergence. This observation holds in other stochastic optimization problems as well. We develop algorithm that creates a sequence of sampling distributions p²: to minimize [pp::T) using only the norm of local updates, and without imposing assumptions the loss functions or how the local and global updates are made. As result, the algorithm can be applied to design sampling distributions for essentially any stochastic optimization procedure. In Section 3 the upper bound of mini-batch SGD of non-convex objectives.
we show how our sampling method improves
Suppose that the beginning of the t-th communication round we know all { optimal sampling distribution
JM
p-_ (1-,11-... (V',I......P..MM)) arg min l(p)
PEPM-11
obtained as pi.m Vann /EM /at.). Computing the distribution pz, is impractical as requires local updates of all clients, which eradicates the need for client sampling. From the form of p². we observe that clients with large am are more "important" and should have a higher probability will need explore the environment to learn about the importance of clients before we can exploit the best strategy. Finally, we note that the relative importance of clients will change over time, which makes the environment dynamic and challenging.
of being selected. Since do not know { JM
Based on the above discussion, we cast the problem of creating sequence of sampling distribu- tions as an online learning task with bandit feedback, where game is played between the server and environment. Let p be the initial sampling distribution. At the beginning of iteration I, the server samples with replacement K clients from [M], denoted St, using p². The environment re- veals (am hmss to the server, where a = A2 I The environment also computes 4<p"); however, this loss is not revealed to the server. The server then updates pf+ based on the feed- back { {aam me )-=1 and sampling distributions (p" I-")-=1- Note that in this game, the server only gets information about the chosen clients and, based on this partial information, or bandit feedback, needs to update the sampling distribution. On the other hand, we would like to be competitive with an oracle that can calculate the cumulative variance reduction loss. We will design y' in way that is agnostic to the generation mechanism of {al h22), and will treat the environment as deterministic, with randomness coming only from {S* J121. We describe an OSMD-based approach to solve this online learning problem.
2.2 OSMD SAMPI.ER
The variance-reduction loss function 4 is a convex function on PM-1 and
Vi((g) V4(())= -
a (0))2 (aM)²
a'v
R- for all g = (q....., TM) e RM
Since we do not observe at, we cannot compute 1c(.) or V4(-). Instead, we can construct unbiased estimates of them. For any E PM-11 let le(g:p'' p²) be an estimate of lg()) defined as
a' N fm E s7
E 4( = K m=1 qmp
(6)
and vi((pp')) E R has the mith entry defined as
vi( = K2
1
N (mmest) P
a
(7)
The set St is sampled with replacement from [M] using p' and N {m E 5*) denote the number of times that a client m is chosen in St. Thus. 0 < N {m E S < K. Given and pt. ((::p') and vig(g p²) are random variables in IR and R.M that satisfy
Es [i(g:p') |p 4(9).
Esa
Vhla.p")
I p v4(9).
5

---

Under review as a conference paper at ICLR 2023
Algorithm OSMD Sampler
1: Input: A sequence of learning rates (11321 parameter a PMr-aaaaMMo/ number of iterations T.
2: Output: p!.T.
3: Initialize: 6¹ 3'ppumi
pumif
4: for = 1, T,2,,..,"--1.....
5: Sample 5" by p'.
6: Compute (1'('';')) via equation 7
7: 1 arg min (e,, Vi. (') Do (vll)).
PEA
8:
end for
When S and p' E R are given, k(q::p)) convex function with respect to q on R and satisfies - ((d'p')) s (Vi(q:p") d'), for q, E R The constructed estimates (g:pp) and V') are crucial for designing updates to the sampling distribution. To the best of our knowledge, while similar estimators as p') in equation 6 was used in previous litera- ture (Borsos et al. 2018), we are the first one to propose (i, in equation 7 and use it for updating sampling distribution.
OSMD Sampler is online stochastic mirror descent algorithm for updating the sampling dis- tribution, detailed in Algorithm [ The sampling distribution is restricted to lie in the space A = PM n Ia/M, oc) E (0, 1], prevent the server from assigning small probabilities to devices. Let 1 with A C D. The learning rates (#:)22 are positive and nonincreasing
RM +
continuously differentiable convex function defined on D,
F] Line 7 of Algorithm provides an update to the sampling distribution using the mirror descent update. The available feed- back is used to construct estimate of the loss, while the Bregman divergence between the current and next sampling distribution is used as regularizer, ensuring that the updated sampling distribu- tion does not change too much. The update only uses the most recent information, while forgetting the history. which results in nonstationarity of the sequence of sampling distributions. In Line 5 of Algorithm we choose S by sampling with replacement. Section C.5 the results to sampling without replacement.
we discuss how to extend
The mirror descent update Line 7 is not available in closed form in general and an iterative solver may be needed. However, when (b()) is chosen as the negative entropy (-) (we use this as our default choice), a closed-form efficient solution can be obtained. An efficient implementation is shown in Algorithm in Appendix C.I The main cost comes from sorting the sequence [ MM Jm=1- which can be done with the computational complexity of O(M log M). However, note that we only update few entries of p' to get g+ and p' is sorted. Therefore, most entries of p are also sorted. Using this observation, we can usually achieve a much faster running time, for example, by using adaptive sorting algorithm (Fstivill-Castro & Wood 1992). Next, provide bound the dynamic regret for OSMD Sampler.
2.3 DYNAMIC REGRET OF OSMD SAMPLER
We first describe the dynamic regret used to measure the performance an online algorithm that generates sequence of sampling distributions {5)x2 i in non-stationary environment. Given any comparator sequence / E ph the dynamic regret is defined
D-Regrety (TT)) L (p' (q
(8)
In contrast, the static regret measures the performance of an algorithm relative to the best fixed sampling distribution, that restricts g²
q" (Namkoong al. 2017 Salchi al. 2017 Borsos et al. 2018 2019). When using a fixed comparator q D-Regret, q): besides, write D-Regret, denote D-Regret, (g):
g. we write the regret
WWe use the term learning rate when discussing online algorithm that leamss sampling distribution, while the stepsize used in the context of optimization algorithm.

---

Under review as a conference paper at ICLR 2023
The following quantity describes the dynamic complexity of comparator sequence and will appear in the regret bound below.
Definition 2.1 (Total Variation), The total variation of a comparator sequence q' T: with respect to the norm || on RM is TV (q! ET= ll - g"ll-
The total variation measures how variable sequence is. The larger the total variation TV the more variable y²22 is, and such comparator sequence is harder to match. To give an upper bound on the dynamic regret of OSMD Sampler, we need the following assumptions.
Assumption 1. The function (()) is p-strongly convex, > O with respect to ||-
(xx) 2 (yy + (V - -y- + 6 || - ull.. E.y
Assumption 2. There exist positive functions H a). (0l(M,a)he)) and Dmax (M, a)) such that [|)l( I H(M, a), (p: I Q,(M,a) almost surely, and D punif) s D Dmax (M, a)) for all P.
These assumptions are standard in the literature (Hall & Willett 2015). When we choose + D and = ||. these assumptions hold (See Appendix D.3). Under Assumption [ we have Do (x () (p² /2) - yll². simplify the notation, we will omit M and a from HT (Q:)
and D Dmax. We also need the following quantities that quantify how far qf is from A. Given PM-1 and a E (0, 1]. let
aa) =
Σ T
M
a
1 {
< a M).
a()',a)) =
M a
Im
1
{ M 1
M
> mm
(g'n
a
a
M
M
w(1 a))
0lg a) = w( a)) (1 N1
(9)
We will use these quantities to characterize the projection error in the following theorem, which is the main result of this section.
Theorem 1. Suppose Assumptions hold and we use ]| 11= 11- to define the total variation. Assume that (1 is nonincreasing sequence. Let fir be a sequence generated by Algorithm ! For any comparator sequence q=:T", where of is allowed to be deterministic or random, we have
D Dmax
2H E TV 1T)
2 Σ
D-Regrety (q
+
M.
[Q]]]
?/1
1/T
Intrinsic Regret
8
E (
11
Pmojectin Error
Proof. The major challenge of the proof to construct a projection of the comparator sequence q q-T onto AT and bound the projection error. To the best of our knowledge, this bound on the projection error of dynamic sequence is novel. Another challenge to deal with the dynamic compara- tor, which requires us connect the cumulative regret with the total variation of the comparator sequence. See Appendix for more details.
From Theorem we see that the bound on the dynamic regret consists of two parts. The first part the intrinsic regret, quantifying the difficulty of tracking a comparator sequence in AA"' the second part is the projection error, arising from projecting the comparator sequence onto AA. Note that the intrinsic regret depends on through Daxx H, and (Q1h21- As shown in Appendix D.2 we have w(q', dr) < for a E [0, 1], which implies that "'g", a.) S M/a. Furthermore, (1a ai) S EM (a/M)1 4gtn < (a/M)} < a. Therefore, the projection error can be upper bounded by (8Ho))/nt+ (M/a) Dt-44('' 4.4)). More importantly, when dfn E A, we have ('4', a) = w(g',a)
7

---

Under review as a conference paper at ICLR 2023
a)) 0. Thus, when the comparator sequence belongs to A",, , the projection error vanishes and we only have the intrinsic regret. As a decreases from one to zero, the intrinsic regret gets larger (it often tends to infinity shown in Corollary 3), while
allowing larger class of comparator sequences; on the other hand, the projection error decreases to zero, since the gap between A and PM-1 vanishes with An optimal choice of a balances the two sources of regret.
When || = || Il and + is the unnormalized negative entropy, the Step 7 of Algorithm | has a closed-form solution (see Proposition By Pinsker's 's inequality, the unnormalized negative entropy (x(x)) is 1-strongly convex on PM-1 with respect to || - ||i. When g²=2 is deterministic sequence,
we have E [TV (q (g"T)) = TV (q (T))
With Theorem 1 we have the following corollary.
Corollary 1. Suppose conditions of Thhoorem 1 hold and let p²uT be the sequence generated by Algorithm For any comparator sequence q we choose a such that q' E for all t [T]. Let
K2a
log M + log [
7) = M V
(10)
2 2 T
(
Then
2/2M3
T
D-Regret (1
[log M 2log ETV
>
E (at)
K2a
where a' MMX X 1l
maxismgM for all [T].
for
Proof. The proof follows directly from Corollary 3 Appendix D.3
Note that as the training proceeds, the norms of local updates are decreasing, thus {ā (ā-)7_ is typ- ically decreasing sequence. Thus, naive upper bound is ET [[ =TT). However, in Appendix F.6. we empirically show that ā' decreases fast and the cumulative square sum of this sequence will converge to constant, that is, ET- E{ plies that the static regret with respect to the best fixed sampling distribution in hindsight (where [V (+7) 0) is empirically O(1), which is much better than the rates in previous research (Salehi et al. 2017 Borsos et al. 2018). Besides, our regret analysis also allows for sampling distributions that change over time (where (V)) 0), and thus is more general than previous results.
(1). This result further im-
The choice of learning rate in equation 10 depends on unknown quantities prior to training, and is thus impractical. In Appendix C.3 and Appendix C.44 we introduce practical automatic parameter tuning strategies with the help of online ensemble method and doubling trick.
3 CONVERGENCE ANALYSIS OF MINI-BATCH SGD WITH OSMD SAMPLER
We illustrate how OSMD Sampler can be used to provably improve the convergence rate of the mini- batch SGD. The detailed algorithm given in Algorithm in Appendix C.2 We use mini-batch SGD as a motivating example to show how adaptive sampling improves the convergence guarantee of an optimization algorithm. The analysis in this section can be extended to other optimization algorithms well.
To simplify the notation, we denote Fm (w) == d (w; Dm) and let Am = 1/M for all m E [M]. We assume that E W C Rd, where W is compact set. Besides, we assume that client objectives are differentiable and L-smooth functions.
Assumption 3. For all m E [M], F., (-) is differentiable and L-smooth, that is,
VV (z) (.) s -||x-18 for all x, W.
Note that allow F, (-) to be non-convex. We also assume that the objective function F(-) is that is, we assume that F = inf F(w) > -c. In addition, we make the following assumption about the local stochastic gradient.
8

---

Under review as a conference paper at ICLR 2023
Assumption 4. For all w E W and m [M], we have Be.D... [Vo(w;)) BE-D,.. [IV((w;)) (w))ll) s
V (w) and
Next, we introduce quantities that characterize heterogeneity of the optimization problem. Specifi- cally, heterogeneity characterizes how objective functions of different clients differ from each other. In federated learning problem, heterogeneity can be large and it important to understand its effect on the convergence of algorithms. The following three quantities characterize the heterogeneity:
M
M Σ m=1
S = sup
1
Σ m=1
V (w) [F(W]]
sup wEW
[ [VF(2))]
NEW M
M
M
G = min
[F - |F((w]]
sup WEW
PEPM
M
Pm
M Σ m=1
2
2 = sup NEW
(VFm(w))
M
By Jensen's 's inequality we have that Ço 2 (1 2 C2 and we assume that Ço < oc. The quantity Ço has been commonly used quantify first-order heterogeneity (Karimireddy et al.] 22200a b), while Çi and (2 are variants of So corresponding to different sampling schemes. More specifically, when we use q² and p. to sample clients, we will have the heterogeneity level be Çi and (2 respectively, where q" = arg minppeP.. supwew Em=1( (1/Pm) [| Fm (w)ll² is the best fixed sampling distri- bution. Finally, the following quantities are useful in stating the convergence guarantee. Recall that B is the local batch size in Algorithm and K |S Let DF = F(w") F*,
DEL OVDEL Ro
SO
VTK DFL OVDEL GVDFL
VTKB
VD LO (-Regrtty(g"))
R =
T
VTKBa VTK
T
R6 DEL
OVDEL
S&VDEL
VDFT D-Regret, (p):T)
VTKBa
VTK
We are now ready to give the convergence guarantee of Algorithm
Theorem 2. Assume Assumption 3 and Assumption 4 hold. Let ut 14, [T], where u is given in equatiion 33 in Appendix. Let {w² (w"...., w" - be the sequence of iterates generated by Algorithm Band let th denote an element of that sequence chosen uniformly at random. When g" E
A, we have [|VF
S RR; when p'. E A.for all & E [T], we have E [[]FF("))] Ro;
when 9" E A pt. E A both hold, we have IE [[F((())) S min R1, R2).
See proof in Appendix D.6 We derive different convergence rates R1 and R2 in Theorem 2 by choosing different comparators. More specifically, Rí is derived by comparing against g and Rs derived by comparing against p!-T. The different notions of heterogeneity reveal the fact that different sampling schemes can change the convergence speed of optimization algorithms through the change of heterogeneity level.
Note that Ro is the rate of mini-batch SGD under uniform sampling (Ghadimi & Lan 2013). OSMD Sampler can obtain tighter rates than uniform sampling when R2 or Rs are smaller than Rg. To have R1 Ro, we need (a/vKB) Va - 1) + /D- DeReerety--(g )/T S (L/VK)(G - G.). By Corollary we have a worst-case upper bound of D-R Regret,(("") as O(VT) empirical evidence in Appendix F.6 suggests tighter rates (1)). With either rates, we always have (eRegret,
o(1). Thus, to have Rj S Ro, we only need (a (I 1) < Co - Ç1 asymptotically. That is, want the gap between the heterogeneity under best fixed sampling distribution and uniform sampling to be large, compared to (a (B)(1//) 1), which is always true when use full local gradient, i.e., when = 0. Similar arguments apply to when Rg 5 Ry- See a more detailed discussion in Appendix A.2 A.2

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Gre- gory S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, lan J. Good- fellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangging Jia, Rafal Józefowiez, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg. Dan Mané, Rajat Monga, Sherry Moore, Derek Gor- don Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul A. Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda B. Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. CoRR, abs/1603.04467, 2016.
Zalan Borsos, Andreas Krause, and Klir Levy. Online variance reduction for stochastic opti- mization. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pp. 324-357. PMLR, 2018
Zalán Borsos, Sebastian Curi, Kfrr Yehuda Levy, and Andreas Krause. Online variance reduction with mixtures. In Kamalika Chaudhuri and Ruslan Salakhudinnvv (eds.), Proceedings of the 36th International Conference on Machine Learning, ICMI, 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 705-714, PMLR, 2019.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-33 311, 2018.
Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: benchmark for federated settings. CoRR, abs/1812.01097, 2018.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Zachary Charles and Jakub Konečný. On the outsized importance of learning rates in local update methods. CoRR, abs/2007.0083 00078, 2020.
Wenlin Chen, Samuel Horvath, and Peter Richtárik. Optimal client sampling for federated learning- CoRR, abs/2010.13722, 2020.
Yae Jee Cho, Samarth Gupta, Gauri Joshi, and Osman Yagan. Bandit-based communication-effiiiennn client selection strategies for federated learning. In Michael B. Matthews (ed.), 54th Asilomar Conference Signals, Systems, and Computers, ACSCC 2020, Pacific Grove, CA, USA, Novem- ber 1-4, 2020, pp. 1066-1063 1069. IEEE, 2020a. doi:
9443523.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection federated learning: Convergence analysis and pfwer-of-choice selection strategies. CoRR, abs/2010.01243, 2020b.
Tarin Clanuwat, Mikel Bober- Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature. CoRR, abs/1812.011188, 2018. URL http:
7/arxiv. v... www. abt//baa//11111 01718
Dominik Csiba and Peter Richtárik. Importance sampling for minibatches. J. Mach. Learn. Res., 19:27:1-27:21, 2018.
Amit Daniely, Alon Gonen, and Shai Shwartz. Strongly adaptive online learning. In Fran- cis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference Ma- chine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1405-1411. JML.R JM.R.org, 2015.
10

---

Under review as a conference paper at ICLR 2023
Cynthia Dwork. Differential privacy: A survey of results. In Manindra Agrawal, Ding-Zhu Du, Zhenhua Duan, and Angsheng Li (eds.), Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi an, China, April 25-29, 2008. Proceedings, vol- ume 4978 of Lecture Notes in Computer Science, pp. 1-19. Springer, 2008. doi: 10.1007/ httpsstts://// org 1 1 /77777777787 3-00--922---------------
978-3-540-79228-44
Vladimir Estivill-Castro and Derick Wood. A survey of adaptive sorting algorithms. ACM Comput. 24(,,44(4):4 476, 1992.
Saeed Ghadimi and Guanghui Lan, Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim., 2344)2334-22368 2013. doi: 10. 10.11177120880811. URL httpt:ttt/...o..//// org/ 10. 1137/1208888811
Siddharth Gopal. Adaptive sampling for SGD by exploiting side information. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.). Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 364-372. org, 2016.
Eric C. Hall and Rebecca M. Willett. Online convex optimization in dynamic environments. IEEE Sel. Top. Signal Process., 9(4):447-662, 2015. doi: 10. 100//STSP.2015.44447777
Ayoub El Hanchi and David Stephens. Adaptive importance sampling for finite- unite--um sum optimization and sampling with decreasing step-sizes. In Hugo Larochelle, Marc Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Process- ing Systems 33: Anmual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Filip Hanzely, Boxin Zhao, and Mladen Kolar. Personalized federated learning: A unified frame- work and universal optimization techniques. arXiv preprint arXiv:2102.09743, 2021.
Elad Hazan. Introduction to online convex optimization. Found. Trends Optim., 2(3-4):157-3255 2016. doi: 10.1561/2400000013.
Tyler B. Johnson and Carlos Guestrin. Training deep models faster with robust, approximate impor- tance sampling. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicold Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31; Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 7276-7286, 2018
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Olveiia. Hubert Eichner, Salim El Rouayheb, David Evans. Josh Gardner, Zachary Gar- rett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons. Marco Gruteser, Zaïd Harchaoui, Chaoyang He. Lie He. Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh. Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao Advances and open problems in federated learning. Found. Trends Mach. Learn., 14(1-2):112) 2021. doi: 10.1561/22000000
AyferOzgür,
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebas- tian U. Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. CoRR, 2as/2008.036066 2020a. URL https:// https:///axiv... org/ abs/
2008 03606)
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD; stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 5132 5143. PMLR. 2020b. URL http:://proceeee http::///ccceeeeeggseeee mlr www.:/tww...p.....ee....e sesesss/vlllg kar htt.1//9///aimiiedyya000a0
html

---

Under review as a conference paper at ICLR 2023
Tachyeon Kim, Sangmin Bae, too Lee, and Seyoung Yun. Accurate and fast federated learning via combinatorial multi- aelti-armed bandits. CoRR, abs/2012.03270, 2020.
Viraj Kulkarni, Milind Kulkarni, and Aniruddha Pant. Survey of personalization techniques for federated learning. In 2020 Fourth World Conference on Smart Trends in Systems, Security and Sustainability (World54), pp. 794-797. IEEE, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. CoRR, 2010.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-fffiienn learning of deep networks from decentralized data. In Aarti Singh and Xiaojin (Jerry) Zhu (eds.). Proceedings of the 20th International Conference on Artificial Intelli- gence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282. PMLR, 2017.
Hongseok Namkoong, Aman Sinha, Steve Yadlowsky, and John C. Duchi. Adaptive sampling prob- abilities for non-smooth optimization. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 2574-2583 PMLR, 2017.
Deanna Needell, Nathan Srebro, and Rachel Ward. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Math. Program., 155(1-2):549-57, 2016. doi: 10. 1007/5
Yurii E. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim., 22(2):341-362 2012. doi: 10.1 177/0000000000
Dmytro Perekrestenko, Volkan Cevher, and Martin Jaggi. Faster coordinate descent via adaptive importance sampling. In Aarti Singh and Xiaojin (Jerry) Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pp. 869-877. PMLR, 2017.
Aravind Rajeswaran, Chelsea Finn, Sham M. Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- tems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 113-124, 2019.
Mónica Ribero and Haris Vikalo. Communication-efficin federated learning via optimal client sampling. CoRR, abs/2007.15199 2020.
Farnood Salehi, L Elisa Celis, and Patrick Thiran. Stochastic optimization with bandit sampling. 02544, 2017.
arXiv preprint
Farnood Salehi, Patrick Thiran, and L. Elisa Celis. Coordinate descent with bandit sampling. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Con- ference Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 9267-92777 2018
Sebastian U. Stich, Anant Raj, and Martin Jaggi. Safe adaptive importance sampling. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vish- wanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 4381 13911, 2017.
Tim van Erven and Wouter M. Koolen. Metagrad: Multiple learning rates in online learning, In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Gamett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference Neural Information Processing Systems 2016, December 5-10. 2016, Barcelona, Spain, pp. 3666-3674, 2016.
12

---

Under review as a conference paper at ICLR 2023
Martin J Wainwright. High-dimensional statistics: A non-asymppotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Hao Wang, Zakhary Kaplan, Di Niu, and Baochun Li. Optimizing federated learning on non-iid data with reinforcement learning. 39th IEEE Conference Computer Communications, INFOCOM 2020, Toronto, ON, Canada, July 6-9, 2020, pp. 1698-1707. IEEE, 2020. doi:
10.1109/IFFC0MM41044.. .020.9949.299954499
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. CoRR, 000/17080077777 2017. URL http:://rxii..rrrtttt/
abs/1708.077
Miao Yang, Akitanoshou Wong, Hongbin Zhu, Haifeng Wang, and Hua Qian. Federated learning with class imbalance reduction. CoRR, abs/201 1266, 2020.
Tianbao Yang. Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Op- timal dynamic regret of online learning with true and noisy gradient. In Maria-Florina Balcan and Kilian Q Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning. ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 449-457. JMLR.org. 2016.
Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou Adaptive online learning in dynamic environments. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 1330-1340, 2018.
Boxin Zhao, Boxiang Lyu, and Mladen Kolar. L-svrg and I-katyusha with adaptive sampling. arXiv preprint arXiv:2201.13383 2022.
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1-9. JMLR.org. 2015.
Zeyuan Allen Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1110-1119 JMLR.org, 2016.
13

---

Under review as a conference paper at ICLR 2023
A
MORE DISCUSSIONS
In this section, we include additional discussions that is omitted from the main text due to space limit.
A. DETAILED DISCUSSION ABOUT CONTRIBUTIONS
We develop an algorithm based on OSMD that generates a sequence of sampling distributions {p' J121 based on the partial feedback available to the server from the sampled clients. We prove bound on regret relative to the any dynamic comparators, which allows us to consider the best se- quence of sampling distributions as they change over iterations. The bound includes total variation term that characterizes the intrinsic difficulty of the problem by capturing the difficulty of following the best sequence of distributions. Such characterization of problem difficulty is novel. Besides, our theoretical result can recover the results in previous research as special cases and is thus strictly more general. Moreover, we theoretically improve the convergence guarantee of optimization algo- rithm by using our sampling scheme over uniform sampling. We show that adaptive sampling can help reduce the dependency the heterogeneity level of the problem.
We demonstrate the empirical superiority of the proposed algorithm through synthetic and real data experiments. In addition to client sampling in FL, our proposed algorithm will have a broad impact on stochastic optimization. Adapting our algorithm to any stochastic optimization procedure that chooses samples, such as SGD, or coordinates, such as Stochastic Coordinate Descent, may improve their performance. For example, Zhao et al. (2022) illustrated the practical benefits of our algorithm to speed up L.-VRRG and L-tauuush..
The learning rate of the proposed algorithm depends on the total variation of the comparator se- quence, which is generally unknown. Furthermore, it also depends on the total number of iterations that can also be unknown. In appendix, nical challenges. In particular, we adapt the bollow-the-rggularize----- trick to automatically choose the learning rate that performs well as the best learning rate asymp- totically.
make the algorithm practical by addressing few tech-
algorithm and doubling
A.2 DETAILED DISCUSSION ABOUT THEOREM
We derive different convergence rates Rj and R2 in Theorem 2 by choosing different comparators, which rates can be applied shall depend on the tuning parameter a (or equivalently the space A). More specifically, R₁ derived by comparing against q¹ and R₂ is derived by comparing against P. The different notions of heterogeneity reveals the fact that different sampling schemes can change the convergence speed of optimization algorithms through the change of heterogeneity level.
It is worth noting that one can always choose other comparator sequences besides these two and derived new upper bounds. When choosing a more flexible comparator, one can obtain a smaller heterogeneity, but risk requiring higher regret and larger space A (which will require smaller a). A good choice of comparator should keep a trade-off between these two concerns. We leave how to choose the optimal comparator sequence as a future research direction.
Note that Rg is the rate of mini-batch SGD under uniform sampling (Ghadimi & Lan 2013). To see when OSMD Sampler can obtain tighter rates than uniform sampling, we only need R₁ or Rg to be smaller than Rg.
When will R₁ < Ro- To have Rg S Ro. we need (o/V/B)(L/V/a-l)) +)+ / DeRerttt, (g") S
(1/VK)(Go (.) By Corollary we have a worst-case upper bound of D-Regret, (9") as O(VT);
empirical evidence in Appendix F.6 suggests tighter rates O(1). With either rates, we always have
D-Regret,(q")/T o(1). Thus, to have Rí S Ro. we only need (o/vB)
1) <
Sa asymptotically. That is, we want the gap between the heterogeneity under best fixed sampling
distribution and uniform sampling be large, compared to (a/VB)(1/Vá - 1). When o = 0, that is, if we use full local gradient, then this is always true.
When will R2 Ro. Similarly, to have Rg < Ro, we need (o/VKB)(I/V +
/ DD-Regret, (pt)/T x (I/VR)(G (2) A worst-case upper bound of (p!:T))
14

---

Under review as a conference paper at ICLR 2023
based Corollary is O(T); however, shown in Appendix F.6. the empirical evidence sug- gests that we may have (p to be O(VT) or even O(1), which then implies that D-Regret, (P.:)) o(1). Given this is true, to have R1 2 Rg. we need (a (tr/B))(1//// - 1) < Su Si asymptotically. That is, we want the gap between the heterogeneity under best dynamic sam- pling distribution and uniform sampling be large, compared to v///B)(1/// - 1). When = O, that is, if we use full local gradient, then this is always true.
New characterization of heterogeneity. Let AC; Co C; for i = 1.2. Based on the previous analysis, we see that AC., 1.2, can also help measure the dissimilarity of the different clients. Compared with So. the new characterization reflects how much gain we can have by using non- uniform sampling, where AG measures the advantage gained by fixed sampling distribution, and ACe measures the advantage gained by dynamic sampling distribution.
B MORE RELATED WORK
Our paper is also closely related to importance sampling in stochastic optimization. Zhao & Zhang (2015); Needell et al. (2016) illustrated that by sampling observations from a nonuniform distribu- tion when using gradient-based stochastic optimization method, one achieve faster conver- gence. They designed a fixed sampling distribution using prior knowledge on the upper bounds of gradient norms. Csiba & Richtárik (2018) extended the importance sampling to mini-batches. Stich (016) developed adaptive sampling strategies that allow the sampling distribution to change over time. Nesterov (2012): |Perekrestenko et al. (2017) ;
et al. (017)sJJonsoo & Guestrin (018); Gopal
Zhu et al. (2016); Salchi et al. (2018) discussed importance sampling in stochastic coordinate de- scent methods. Namkoong et al. (2017): Salehi al. (2017); Borsos et al. (2018) 2019); |Hanch & Stephens (2020) illustrated how to design the sampling distribution by solving an online learning task with bandit feedback. [amkoong et al. (2017); Salchi et al. (2017) designed the sampling distri- bution by solving multi-armed bandit problem with the EXP3 algorithm (Lattimore & Szepesvári, 2020 Chapter 11). [Borsos et al. (2018) used the follow-the- www.ltterrgulariied--eeeede
algorithm (Lattimore & Szepesvári 2020 Chapter 28) to solve an online convex optimization problem and make updates to the sampling distribution. [Borsos et al. (2019) restricted the sampling distribution to be a linear combination of distributions in predefined set and used an online Newton step make updates to the mixture weights. The above approaches estimate a stationary distribution, while the best distribution is changing with iterations and, therefore, intrinsically dynamic. In addition hav- ing suboptimal empirical performance, these papers provide theoretical results that only establish regret relative to fixed sampling distribution hindsight. To address this problem, |Hanch & Stephens (2020) took a non-stationary approach where the most recent information for each client was kept. A decreasing stepsize sequence is required establish regret bound. Furthermore, the regret bound does not capture the intrinsic difficulty of the problem. In comparison, we establish a regret bound relative to dynamic comparator-4 sequence of sampling distributtons- imposing assumptions the stepsize sequence, and this bound includes the dependence on the total variation term characterizing the intrinsic difficulty of the problem.
Our paper also contributes to the literature on online convex optimization. We cast the client sam- pling problem as an online learning problem (Hazan 2016) and adapt algorithms from the dynamic online convex optimization literature to solve it Hall & Willett (201)); Yang et al. (2016); Daniely et al. (2015) proposed methods that achieve sublinear dynamic regret relative to dynamic compara- sequences. In particular, Hall & Willeu (2015) used dynamic mirror descent algorithm to achieve sublinear dynamic regret with total variation characterizing the intrinsic difficulty of the environment. However, the optimal tuning parameters depend on the unknown total variation. On the other hand, van Erven & Koolen (2016); Zhang et al. (0188) proposed different online ensemble approaches to automatically choose the tuning parameters for online gradient descent. Compared with the problem settings in the above studies, there are two key new challenges that we need to address. First, we only have partial information--aane about the loss functions. Second, the loss functions in our case are unbounded, which violates the common boundedness assumption in the online learning literature. To overcome the first difficulty, construct an unbiased estimator of the loss function and its gradient, which are then used to make an update to the sampling distribution. We address the second challenge by first bounding the regret of our algorithm when the sampling distributions in the comparator sequence lie in a region of the
feedback-instead of the full information
15

---

Under review as a conference paper at ICLR 2023
simplex for which the loss is bounded, and subsequently analyze the additional regret introduced by projecting the elements of the comparator sequence to this region.
C ADDITIONAL ALGORITHMS
C.I ALGORITIM TO SOLVE STEP OF I WIIEN & IS UNNORMALIZED NEGATIVE ENTROPY
When (()) is chosen the negative entropy ④b((), closed-form efficient solution can be obtained as shown Proposition [
Proposition 1. Suppose 4 = Le is the unnormalized negative entropy in Algorithm 7 Let
p P'm exp (N {m S*} mam (K2 (v/m)*)}
E [M]
Let [M] [M] be a permutation such that smallest integer m such that
PT(1)
++1
S
s++ P (2)
... S
Pa(My Let mt, be the
st+1
M
S++1 Pa(m)
1
m
a
a++ PT))
M
M
Then
fa/M (11- ((m), - 11)3M))))))))
if < <m,,
ptt
/E pa(s)
otherwise.
Proof. See Appendix D.I
An efficient implementation is shown in Algorithm 2
Algorithm Solver of Step of Algorithm [ when unnormalized negative entropy
1: Input: , St. { mese, and A = PM-1 1 (a),
2: Output: p
3: Let ptt = p'm exp {N {m E / (p (pm)))) }²) for m E [M].
4: Sort [Dt-1jaf Jm=1 in non-decreasing order: (1) < F S ... S P
5: Let um = Pa(m) (1 m--1a a) for m [M].
1++
6: Let um 37 2j=m Px() for E [M].
MM -+1
7: Find the smallest m such that Um >> Um. denoted as m
aa/M
Tf < m otherwise.
8: Let p
((1 ((m, - 1) / (I Pr(i))
C.2 MIN-BATCH SGD WITH OSMD SAMPLER
In this section, we describe the Min-batch SGD with OSMD Sampler in Algorithm Compared to classical min-batch SGD, the key ingredient of Algorithm is Line 13 where the server updates the sampling distribution by OSMD Sampler, and Line 5 where the server samples the local mini-batch from non-uniform sampling distribution.
C.3 ADAPTIVE-OSMI SAMPLER
The choice the sequence of learning rates (n. hes has a large effect on the performance of OSMD Sampler. Similar to Corollary have the following Corollary.
16

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Min-batch SGD with OSMD Sampler
1: Input: Number of communication rounds T, number of clients chosen in each round K, local batch size B, initial model parameter w", stepsize {we)
2: Output: The final model parameter w..
3: Initialize: 500 p quiif
4: for t = 0, ,, -- do
5: Sample 5" with replacement from [M] with probability 3 such that |S*| K.
6: for m E S do
7: Download the current model parameter wt.
8:
Locally sample mini-batch B = (5 (5m.1 Sm, i.i.d. uniformly random from [Mm)]
9:
Locally compute and upload g"T. (1/B) Volw"; (m,,)) to the server.
10: end for
11:
Server computes a = Amll 12 for m E St and
Am
Im.
Dim
MESt
12:
Server makes update of the model parameter w +- w² Mag Server obtains updated sampling distribution p++11 by Algorithm end for
14:
Corollary 2. Suppose conditions of Theorem 7 hold and let pi: be the sequence generated by Algorithm
We choose a such that pt, E for all E [T]. Let
k2
log M 2 log M / (p!:T)
1 = M M E
(11)
12
2T
Then
D-Regres,(v! 1:T) 2V2M E (a
[log M + 2 log (M/a) (TV (p!:))
(12)
K203
where a' = MAXISmEM a MMX 19
The choice in equation 11 still depends unknown quantities such as E[a*), E[TV(p)")) and T. To get E. we can add a pre-training phase where we broadeast the initial model parameter w to all devices before the start of the training, and collect the returned 1 from all responsive devices, which we denote as Sa. Then ât == maxme Am 2| On the other hand, E and T are hard to estimate in advance of the training. We discuss how use online ensemble method to choose the learning rate without the knowledge of (p! ]. and how to get rid of the dependence on T using the doubling trick.
The main idea is to run a set of expert algorithms, each with a different learning rate for Algo- rithm [1] We then algorithm More specifically, we define the set of expert learning rates as
prediction seetfictionwwth-exxppeeee with-expert-addvee algorithm track the best performing expert
K²aa
log M
=
2
e = 1, ................................ BB
(13)
M3
2T
where
4 log((M M/aa) (T - 11) +1
E = loga
1 log M
(14)
Then for each de E, Adaptive-OSMD Sampler algorithm runs expert algorithm to gener- ate a sequence of sampling distributions p!.T. Mcanwhile, it also runs meta-algorithm that uses
We refer the reader to Chapter 2 of Cesa-Bianchi & Lugosi 2006) for overview of prediction-with- expert-advice algorithms.
17

---

Under review as a conference paper at ICLR 2023
Algorithm 4 Adaptive-OSMD Sampler
1: Input: Meta learning rate y the set of expert learning rates & fm S n2 .... S ngt with
E [8|: parameter a E (0, 1]. A = Pas-1 n |a/M, oo)MM; number of iterations T; initial
distribution p!mit
2: Output: 1 p2.r
Set 0- = (1+ (1+1//)/(eel
1)) and P. pimit e [g].
4: for t = 1,2,,,,... 1.2....,T''
do
5: Compute p² > O..
6: Sample S by p².
7:
do for .......
8: Compute ; p²) via equation and V4((t;p") via equation 7
9: Solve o arg min le (p, (i Dz (v ae)) via Algorithm 2
10: end for
Update the weight of each expert:
0 exp { -b:tt:
g++1
e e [E)
Ye 0 exp
12:
end for
strategy to aggregate {p! (i1:TLE achieves performance close to the best expert.
Je=1 into a single output p which
Algorithm 4 details Adaptive-OSMD Sampler. Note that since
compute ( it and
(i. p directly, there is no need use surrogate loss as in van Erven & Koolen 2016 and Zhang et al. 2018).
From the computational perspective, the major cost comes from solving step of Algorithm which needs to be run for total number of T llog TJ times. Compared with Algorithm the computational complexity only increases by a log(T) factor. We have the following result on Algorithm
l| to define total variation. Let a be small enough such that p', E for all [T]. Let pxrr be the output of Algorithm with 7 M TE
Theorem 3. Let th = T. and we use
|1- =
pinit puuit and E as in equation 13 Then
3/2M3 / E 2
D-Regrety <
T [log M + 2 log (M/a) E [TV (p!-))]
K2a3
M
TE @
(1 + 2 log E).
8K
Proof. See Appendix D.4
Since the additional regret term is ((MM))( which is no larger than the first term asymp- totically, the bound the regret is of the same order in equation 12 However, do not need to know the total variation E (x)V(p to set the learning rate.
Based on Theorem 3 the choice of relies prior knowledge about {pt, Jr21 Specifically, we need a to be small enough so that pl E .A for all t E [T]. While this prior knowledge is not generally available, in Section FS we experimentally show that the proposed algorithm is robust to the choice
of a. As long as the chosen a is not too small or too large, we obtain a reasonable solution. We always set 0.4 in experiments.
18

---

Under review as a conference paper at ICLR 2023
C.4 ADAPTIVE-OSMI SAMPLER WITH DOUBLING TRICK
Algorithm 4 requires the total number of iterations T as input, which is not always available in practice. In those cases, we use doubling trick (Cesa-Bianchi & Lugosi 2006 Section 2.3) avoid this requirement. The basic idea to restart Adaptive-OSMD Sampler at exponentially increasing time points T. 22222_10 2 The learning rates of experts in Algorithm 4 are reset at the beginning of each time interval, and the meta-algorithm learning rate y is chosen optimally for the interval length. We set Th at the beginning of each time interval using the maximum environment feedback from the previous interval.
More specifically, the time point To, we let
K²a
log M Ma
e 1,,,, Eb )
20
9-1
(15)
where
4 loog (M/a)
Eg
log2
1+
(2 (24-1-11 -1) 11)
11
(16)
2
log M
practical implementation, at the time point 1 = To. instead of initializing all expert algorithms using uniform distribution, we can initialize them with the output of the meta-algorithm for / T3 1. To get get the server pre-training phase where the initial model parameter wo is broadcast to all devices before the start of the training. Subsequently. the server collects the returned lls II from all responsive devices. which are denoted as 5 Then ã' == max 0% where a% = Am 1 Sampler is detailed in Algorithm
and 76 M 2 tab. b 2 1. We set aTh max -1 Th 1 To-1
SK
From the computational perspective, by the proof of Theorem Algorithm needs to run Step Algorithm 4 for total number of O [ T) times. Therefore, the computational complexity of Dlaative-Doubling-OSS OSMD Sampler, while it increases by only log(T)) factor compared to OSMD Sampler. The following theorem provides bound on the dynamic regret for Adaptive-Doubling OSMi Sampler.
Sampler is asymptotically the same as that of Adaptive-
Theorem 4. Let Φ- = De and we use ||- = 11-111 11 to define the total variation. Let a be small enough constant so that p_ 1:: A and the training stopped after T iterations. Suppose that there exists a constant C >> 1 such that TTo < Cā for all b = fi.TT be the output of Algorithm where p unii is used Step
B, where B = [log2(T + 1) Let Then
D- R-ggeret
2 +1]
(2C + 11++))M2@// (a!)
log M + 2lo (M/a) E +
22
k²a3
M
E
(C + 2og LT)
8K
Proof. See Appendix D.5
From Theorem we observe that the asymptotic regret bound has the same order that of OSMD Sampler and AdaD Sampler. However, Adaptive-Duubing-OSMMD Sampler does not need know (V))) T in advance.
C.5 ADAPTIVE SAMPLING WITHOUT REPLACEMENT
In the discussion so far, we have assumed that the set St is obtained by sampling with replacement from p¹. However, when K is relatively large compared to M and pt is far from uniform distribution, sampling without replacement can be more efficient than sampling with replacement. However, when sampling without replacement using p', the variance reduction loss does not have a clean form as in equation 4 As result, online design of the sampling distribution is more challenging. In Sampler
this section, we discuss how to use the sampling distribution obtained by Adaptive-OSS sample clients without replacement, following the approach taken in Hanchi & Stephens (2020).
19

---

Under review as a conference paper at ICLR 2023
Algorithm 5 Adaptive-OSMD Sampler with Doubling Trick (Adapiiv-DDublinn-OSSD)
1: Input: Paramter
2: Output: p' for fort=
3: Use w" to get {a mes5, where S is the set of responsive clients in the pre-training phase.
4: Initialize â maxmes" en and 1.
5: while True do
6: Set E, as equation 15
7: Let 7o = M 25-1a5
8: Obtain [ st=2-1 from Algorithm 4 with parameters: 7b. E6, as the number of iterations
2b-1, and the initial distribution puuif pa"m'=3 (when b > 1).
9:
if Training Process Converged then
10:
Break. end if
11:
12:
Let b + b+1.
13: Let ab = max Tb
end while
Algorithm Adaptive sampling without replacement
1: Input: w and p¹
2: for t = 1,2, 2, 2.......
do
3: Let P(1)
p³ and sample m from [M] by P(ay-
4: for k = 2, ..... K do
5:
Design sampling distribution for sampling the k-th client in the 1-th round Construct P(,) by letting
6:
{{
1 -1- k-1 (1- pini) ) p. m E [M]]mq..... m
Ple) =
0
otherwise.
7:
** Sample the k-th client */
8:
Sample m from [M] [m].......................... mp-1) by Playy
9:
end for
10: Let S = fmf.....
))
11: The server broadcasts the model parameter w' to clients in St.
12: The clients in St compute and upload the set of local gradients ( Imng }
13:
1* Construct global gradient estimate #/
14:
Let Φ(1) X Xm I'm /f(()..
for k 2.... do
16:
Let g(x) = Nong Iin; /B(K),
+ kk-1 N Xing
17:
end for
18:
Let g'
KK 9/k)
19:
1* Update the model weight based on the global gradient estimate #/
20:
Obtain the updated model parameter w=+ using w' and g
21:
1* Update sampling distribution */
Let arn, ll 2 for m E St.
23:
Input {ar bes: into OdDD Sampler to get g
end for
The detailed sampling procedure is described in Algorithm We still use Adaptive-OSMD Sampler to update the sampling distribution. However, we use the designed sampling distribution a way that no client is chosen twice. Furthermore, I8 Algorithm with the following properties.
fonndhmmmooosstuu constructs the gradient estimate
20

---

Under review as a conference paper at ICLR 2023
Proposition 2 (Proposition 3 of Hanchi & Stephens (2020)). Let p' =pand let g' be in Step 18
of Algorithm Note that O' (p) depends p. Recall that J Em AmFrm We have Est [ J
and
arg
min Est [llg' [1 arg min 4(p), PEPM-
PEPM-
where (x) is defined in equation and the expectation is taken over St.
From Proposition 2 we see that ÿ' is an unbiased stochastic gradient. Furthermore, the variance of g' is minimized by the same sampling distribution that minimizes the variance reduction loss in equation 4 Therefore, it is reasonable to use the sampling distribution generated by Adaptive- OSMD Sampler design g².
D TECHNICAL PROOFS
D.1 PROOF OF PROPOSITION
First, we show that the solution pt+1 in Step of Algorithm can be found as
5 arg min ni (D, vi((o';')) + De. (p (p))"'),
PED
-+ arg min Do. (pl1 PEA
The optimality condition for +1 implies that
T vi (p. Vp' 0.
(17)
By Lemma the optimality condition for g implies that +t VΦ, ( ( (p+ }} 2
for all p A.
Combining the last two displays, we have
ip pーーー -0
vi :D) + v - (F)) for all E A.
By Lemma this is the optimality condition for + to be the solution in Step 7 of Algorithm
Note that equation 17
implies that
Tp
of N {m e St) +lg((ttt)) log((tm) 0,
m [M].
K2
(
Therefore,
K2 (pt ) 3 (mEst).
p'm = P'm exp
[M],
and the final result follows from Lemma
D.2 PROOF OF THEOREM
We first state a proposition that will be used to prove Theorem The key difference between Theorem [ and Proposition 3 is that in Proposition 3 the comparator sequence lies in A, and, as result, there no projection error.
Proposition 3. Suppose the conditions of Theorem 1 hold. For any comparator sequence 1:T with y E A, E [T], we have
2H D-Regret, (T Dinax + TV (q 1:T
T
+
E
[Q?
Proof. By Lemma and the definition of g in Step 7 of Algorithm 1 we have
1 vi(0'':'') < (v ( 1t g¹)
(18)
21

---

Under review as a conference paper at ICLR 2023
By the convexity of (');''), we have
4p': -''a'''"";'' - ( - 9²)
(VL((( - -
Then, by equation 18 we further have
" u('''''))'' - - - - + ('' -1+
T
From the definition DD we have
Dæ (21 || x2)
D& (23 || 22) Do (ooo) - 21).
22, E D.
Then
1
- - D (d'11"") - Do (1'11p - Dx (0++)1159] + (Vi(('' - -1
7/e
1
D (4'11 - Do (q [+++))+++]]] 1 7/2
D (1*+))))**) Do (9'11x++1)
178
1 DD Dz "13²) + (Vie D'), - 11
(19)
7/t
We bound the second term in equation 19 as
D&
(1 Da (4 (1+))
5(g (1( ((g") - (V 1+1 9¹)
(V0() - v get - 9¹)
1n
(1((t+t) - 1|1111 q'll
2H -
(20)
where (a) follows from the convexity of ((-). (b) follows from the definition of the dual norm, and
(c) follows from the definition of H. Since ((-) is p-strongly convex, we can bound the third and fourth term in equation as
Do 11'") + (vi((':))) ('),'' p S
P 11 10 (i.('''''''1111 - 11
27
Since ab < a² (26) + 12 a, b, > further have
Do D 11p') + (o' 11+1 S
-
2n
2T. Qt. (21)
<
p
Combining equation 19 equation 21
we have
Do (g'llp")
Do
11 - 9ill
2
T(p':pp 1 -(('';p))
2H
7
n
n
p
This implies that
T
Σ :''::0))
Σ p))
Do (g*1)
Do (4++1104*))
T
l
T
-2H
+
Q
71
1/+11
T/t
t=1
D& (111)
2H
T
2 T
11 - 9'll +
n
TfT
0 [=1
1=1
D D
2H
2 T
+
TV (g (:T+)
Σ
Q
m
(22)
171
Tpr
p t=1
22

---

Under review as a conference paper at ICLR 2023
since P1 is the uniform distribution. Finally, note that
T
E
Σ 1=1
: - Eulo:
Σ
E
Egt
Ess [c( :t))
t=1
t=1
Σ
E
[Le(0') le(4")]
1=1
D-Regrety (g )
The conclusion follows by taking expectation both sides of equation 22
We are now ready to prove Theorem I
Proof of Theorem 7 For any comparator sequence g²22" with oe E PM-11 t [T], we have
T
T
T
T
D-Regrety (q ) E
Σ
h(0')
Σ
(( + Σ 4(
Σ
k(lg))
(23)
t=1
t=1
1=1
1=1
By Proposition
we further have that
E
40')) Σ u(a))
1=1
T + 2 Σ R [
Dmax
2H
2H 1T
TV (q [
+
-VV
(24)
WT
P t=1
Therefore, to prove Theorem we design a suitable sequence q qI.T, where q' E A, and bound the terms 2:114(()) - Σ t=1 4((gt) and TV (21:3)) TV (T).
We define 7¹ as
Sa/M d'n d' - w a) (atn )
if dm a/M, if qh 2 a/M,
(25)
where w(g', a:) is defined in equation 9
We now show that q' E A, t E [T]. by showing that
ot 2 a/M, [M]) and E EmeLM &. 1. For m E [M] such that o < a/M, we have
from equation 25 that of = a/M. For m E [M] such that dfn 2 a/M, by equation 25 we have Ii - a/M
w(q't a)) (gin a/M). Thus, we proceed to show that w(q", a) s I. Since
=
Σ m=1
am
9m
Σ m=1
4m
am
M
M
{ sm
Σ
{ dm
M
<
M
M
M
a,
we have
M
M
Σ
d'm
a
[ am
>
a
> Σ
a
din
{
a.
<
a
M
M
M
M
m=1
m=1
23

---

Under review as a conference paper at ICLR 2023
Therefore, 0 S ,(g', a) 1. Furthermore, w(g', 0) 1 and w(q', 1. Finally, show that
Em=1 Im By equation 25 and the definition of w''", a.) in equation we have
M
M
M
M
1m
+
Im
4m 2
a M
}
M
M
m=1
m=1
m=1
w(d' (.)
fm
I
4m
2
a
M
M
m=1
4m
4m
4m
Σ
Um
{
4m
M
M
M
M
M
Am
am
2
Σ
4m
<
M
M
m=1
Therefore, de A for any E [T].
We now bound E le(T") - Et= k.d"). When dm < <a/M, then 1/ - 1/4 < O; and when
d' a/M, then
1 w(g',a) (1- Mig
1
q'n
Iin
1 w a) (1- Mi
I'm 1 w(a' a) (1 M9
Since
w(g',a) aa) (1- Mgg. )
a( and 1 aa)(d',a) (1-
w(1
2 21- wlg' a))
M atn
M
tm S 1, we have
1 a(
(l
Zm
d'n
w(g', a) (1
a
4
M
Thus,
M
4(d")
Σ 4(4")
am
om
T
M
a
m
Iim
>
M
f
m==1
M
809 a)
9m
>
a
dh
M
m=1
6lg". a))((9))
(26)
1=1
24

---

Under review as a conference paper at ICLR 2023
Next, we bound TV (q - TV (q (T)
Note that
T =
(T
- 7
11
2=
Σ
1/"h q
9 q
+
-
t=
T Σ
1 1111
1 q
9
9-
9
'11
T Σ 1=1
S TV (
11 -
We now upper bound by equation 25 we have Im Um wil" a) (gm R) Therefore, recalling the definition of (4'"", a.) in equation 9
Σ of
1 - 9 11- If < < M, then 7Tm - -a/ If 2 a/M,
we have
M Σ
amn M E(
|
q¹ 1
M
Im
t 1
4m
M f
a
w(g', a) +
M
a
1
4m
M
a
m=1
m=1
= Σ
Im
1 am
}
M
M
m=1
20' a)
and
T <
TV
( a..
(27)
Combining equation 23 equation sides, obtain the result.
24 equation 26 and equation 27 and taking expectation on both
D.3 COROLLARY AND ITS PROOF
Corollary 3. Suppose conditions of Theorem 7 hold and + De. Then for any comparator
quence (T. we have
}.
log M
(log(M/a) 7r
2M
D-Regrety (TT:))
<
TV (TT))
+
(at)2
K4a
m
[=1
8H
Σ
V a) Σ a)d'g))
WT
where a² = maxismaM an = maxismsi X2 11gh
Proof. When + = d. we have
1 from Pinsker's inequality. Furthermore, || 11. =
11.. (p) (log Pr.g...... ... logPM) T_ and 1i A PM-1 n [a/M, co) E [T'. Then Q. Maat/(K2 aK2 and H = log( M/a) follows by checking the definition. Finally, to show that
Do (q unif) log M for all q A, note that Do (4 || uniff
log M Idd Zm log 4m S
log M.
D.4 PROOF OF THEOREM 3
The proof proceeds in two steps. First, we show that there exists an expert learning rate n, E such that the regret bound for g1:T is close equation 12 That is, show that there exists ne E & such
25

---

Under review as a conference paper at ICLR 2023
that
T Σ (( - Euols S
3/2M3 (2-)2
E
- t=1
T [log M + log (M/a) E TTV (p! ]]]
K203
(28)
Note that 5t p.. Second, we show that the output of meta-algorithm track the best expert with small regret. That is, we show that
M
TE [a_) (1 2og E),
E
Σ
E
Σ D")
E
(29)
8K
The theorem follows by combining equation
28
and equation 29
We first prove equation 28
Since 0 - E[TV
(p!")) S 2(T - 1), we have
k²a
log M
K²aa
log M + 4log(M/a)(T I max E,
min
M
V
21
S
"
M
27
where v)* is defined as in equation 11 the proof of equation 22 and proof of Corollary 3] we show that
Thus, there exists Bee E,, such that Me 211" I 2% Repeating
Σ L(p':'))
Σ (((is)) s
log M +
2log( M//o)
TV (p-7))
Σ (a') Kta6
ne
ne
which then implies that
log M
2 Plog(M/or
E
Σ (G's''
E
TV (p!-7)
nee
2n M 6
2 E (at)² 27
T
k&a a
Since /2 S 37", we further have
T Σ (')
E
1=1
2 log M
4log(M/a)
TV (p!:T)]
+ 2n M T
Σ
(aa)²
11¹
17"
Kda 1=1
2 log M
+
4 4log(M/a)
TV (p.:T)
2n¹ MT
E. (at)2]
11pt
17t
kda
3
EE (2
Dlo M 2og (M/a)
TV (D)
K2
Now, equation 28 follows, since
E
EE
Est [((pi:b)
Σ
We prove equation
29 next. Let
i (#2:0))
e e (E) [T].
Recall the update for 0g in Step
of Alg
We have
0 exp
8
t= T...
Σ Σe Oz exp
(-7Li_1)
26

---

Under review as a conference paper at ICLR 2023
Let ,₂ Eb=1 0g exp { { Then
Σ 0g exp { (--it)
log 1 = llg
and, for 1. 2 2,
Σ og exp -716 exp { -7b:
+
log
log
---1
Eb 0f exp {
E
of exp (1b008:0)))
= log
b=1
We have
O2
log θT
log 1 +
log
Oc-1
1=1
of exp { (-11(66:00))
log
7²
(fi:((h:p') + 8Ka?
(Lemma 3
b=1
22 ET= @²
"pp::p" +
(Jensen's inequality)
8Ka²
and
log (Or) = -log
Σ b=1
0g exp
(-114]
log
max 0 exp ISbEE
{ (-r24.)) - min
L log
1
ISbSE
?
0
Combining the last two displays, we have
T2M² (I a²
min ISbSE
1 + log
Σ
p'p::0") +
0g
8Ka²
which implics that
YM2
ET= ( at
ΣiG:E)- - in
1
log
1
log ØT:
1
E [P].
8Ka²
01
8Ka2
Taking expectation on both sides, we then have
M22TB
E
f
log 0!
8Ka²
Since 0 2
ga. log 1/0 < 2og E. Lety= = / ET to minimize the right hand
1.
side of the above inequality with log 1 1/0 substituted by 1. Then
T
T
E
i5 = E
(
:²))
M
TE a
(1+ + 2 E), aE [E].
α
8K
27

---

Under review as a conference paper at ICLR 2023
D.5 PROOF OF THEOREM 4
Recall that Ti = -b and 1²h is reinitialized as the uniform distribution. Let
Tb
Tb11-1
D-Regret, = E
Σ
4(0')
Σ
u(pl))
T=Tb
T=To
Similar to the proof of equation 28 and equation 29
we have
D-Regret,
(2C + 1)VM
log M + 2lg (M/a) E TV pp+ (
]]
(To+1 Tb)
K2a²
+ M
(Tb+1 T, [at)]
(C + 2 Eb)
a
8K
(2C + 1) 1)v22 2M
E (2
[log M 2log (M/a) TV TV
(1!)7)((V2)--1
kaa3
M
E SK
(C log E) (V2)
where E' is defined in equation 14 Since B = [log, (T + 1) we have 73 < S TB+1 - 1, which
implies that < T TB + T+1 TB 2 Thus, we can similarly obtain
E
Σ 4('')
Σ 1(Pl)
L T
t= Te
(2C + 1) 2 / E [a
<
[log M + 2lo (M/a) (p! (VV
k
M
E a
+ a
(C + 2lg E) (V2)
8K
The result follows combing the last two displays.
D.6 PROOF OF THEOREM 2
Our proof follows the similar technique used in the proof of Theorem 2.1 of Ghadimi & Lan 2013). Our key novel technique is the construction of ghost subset that drawn from [M] from the comparator sampling distribution. The ghost subset is only constructed for theoretical purpose and does not need be computed in practice. We only show the proof of R1, Ro and R2 can be then derived in a similar fashion.
Let 8' =g¹
VF VF(w)) Under Assumption 3 by (1.6) of Ghadimi Lan 2013), have
I
F (11 < F (w²)
F (w"). m11 w²)
|
L
= F F - 1 VF (w')) , + 2
||0"||
= Fww)) - 11 -F|/FF (n0") 11 (VF ,0)))
+ " 1 ||VF (w*) 2 + /V (w*) 56) + [|1011]]]
L
= F Fww) - (1 ) || (w))) || (n- - ( (VF 88) +
L
2 22
10911
(30)
Note that E [g w = VF(w"), thus we have E [0t w', 101 = 0. and
E [VF (w") [")]), = [ (VF (w'). , 5*) w0' [07] 0.
(31)
28

---

Under review as a conference paper at ICLR 2023
On the other hand, we assume that there is a ghost subset of clients S with |S*| K, which is drawn from [M] with sampling distribution q. Besides, we let
Im
g'
MK
Im
TR
Then we have
||00|12
wt, 0²)
Es 11g J + J VF(w")| w', pp)
Es
E.s |l9s J- w .'' + +I|+ VF(w))]
= 1e (6') || || VF(W'')12
= l4 (v-) - | + || - -VF(w))] + le (f²) - 4 (1-)
Eg. |100 | VF w', [0] + (f') 4, (g.).
Since
E
|
FF(w")1
wt .p'
2 VF(w*)
Din
E
wo Dr
MK
Iin
mc
S 2E
1
Σ
Iin
Σ
VF (w*)
MK
Um
MK
Iin
mESt
mESt
/12
Vin( Um
+ 2E
VF((0")
1/, Dr
MK
mEgt
2
Σ
VEn (1")
w/ 15t
M
(ghh))
Sr
2
M
V (2")
-I (w
+
K
M2
Zi
m=1
20
M
1
2C7
20
2
<
M
K
KBa
K
m==1
where the penultimate line follows that E |1ohn and the last line follows that Iún 2 a/M. Thus, have
(mm(())) S o² / B and the definition of G1,
2a²
2t
E
|11001 2
w² :50
+
+4 (B¹) - 14 (g-),
KBa
K
which implies that
2To²
2TC2
T-1
T-1
E ||0-11] <
+
+ E
Σ 4 (Ø')
Σ l (q+)
KBa
K
1=0
1=
2To²
2TÇ2
+
+ D-Regrety
(32)
KBa
K
29

---

Under review as a conference paper at ICLR 2023
Combine equation 30 equation
31 and equation 32 have
L u1 11
Σ
E
[
2
+ L
2To²
2TÇी
I F(w')) F(w*)
D-RRegret
KBa
s D L /²² KBa
12To²
+ 2T
+ +-Reegret,(4"))
K
Since S 1/L, thus (p - L 22² = p(l
1) 2 2/2, thus
T-1 Σ
2DF
20² KBa
26
D-Regretz(4"))
VF (n=))| $
+ Lp
Tμ
K
T
Finally, let
min 1/L, (1/0) (1/o0) DE DFKBa/(LT) DF / DE (LDD-RRerre (g*))
(33)
then have
VF (1²)
1=
DF
LT
TL
(D-Regretr(9"))
max LooV DFK
SiV
DFK
DF
OVDFL SVDDEL
VDF LILLLLDDRREE D-Regrety
VTKBa
VTK
DF
LT
TL +GI DFK
LD- (g*))
L+ DFK
T
DE
OVDFT.
+ SIDDET. + VD LV D-Regrety
VTKBa
VTR
T
DLL OVD'L
VTKBa + SVD'L VDF LA D-Regrety (9*))
VTK
E USEFUL LEMMAS
Lemma 1. Suppose that f is differentiable convex function defined on domf, and X C domf is closed convex set. Then is the minimizer of f on X if and only if
Vs(x) (y (y- (yxx)((xxx)) x)
for all y E X.
Proof. See Section 4.2.3 of Boyd al. 2004).
Lemma 2. For q E PM-1 we have Da(a 11 umitt < log M, where to is the unnormalized negative entroyy.
Proof.
Since ((g) = Em Im (log 9m 1) < 0, (mp = - -log M, and
1
(Du(puii ) pumil) Σ
(qm
log
0.
M
M
have (g [1)) < log M.
30

---

Under review as a conference paper at ICLR 2023
Lemma 3 (Hoeffding's Inequality). Let X be random variable with S X S b for a. E R. Then for all s E R. we have
log E [e**] I sB[X] + ((b-a) a)-
8
Proof. See Section 2 of Wainwright 2019).
Lemma 4 (Based on Exercise 26.12 of Lattimore & Szepesvári (2020). Let a E [0. A
PM-1 0 MMM, D [0, oc) M and + = De is the unnormalised entropy on D. For (0))) M, let arg minveA Do (vlly)) Suppose yn S 1/2 S ... S yas. Let m be the smallest
value such that
ym (1
(1-"*
m
a
Σ
M
a
Ym.
M
M
TE
Then
a M
if < m
Fm
(1
alym
otherwise.
S Un.
Proof. Consider the following constrained optimization problem:
Umm
min we uE(0,.0)MM
Uy
log
4/m
m=1
M
s.t.
Σ
Um
1,
172m
Um
m [M].
M
Since x is the solution to this problem, by the optimality condition, there exists X, V1, such that
PM E R
log
2m
+
1
-
Um = 0,
m E [M],
(34)
Vm
M
Fm = 1,
(35)
m=1
2m
M 2 0,
m E [M],
(36)
Vm 2 0,
m E [M],
(37)
Um
4m
a
= 0,
m E [M]-
(38)
M
By equation 34
have F' Um exp(- (1 + À + vm)) By equation 37 and equation 38 when
Im a/M, we have Fi = ym exp( (11 + + pm)) ) 2 Vm exp( -1 A): when 2n > a a/M, we have Im ym exp(-I1 A). Assume that Φ
Fm -1 a/M Fm S ... S MM Then
M
M Σ
=
Σ
Zm = (m* 1) a
exp(p11+ A)-
Vm
M
m=1
m=m
which implies that
exp(-1+X) 1 (m" 1) M
(39)
Σ m=m
Thus, have
(m"
1) a
Em Om exp(-1 X) ymm
M
ΣM Um
M
31

---

Under review as a conference paper at ICLR 2023
which implies that
Vm (1
(1- m²
CK
Σ
M
ym.
(40)
M
M
To complete the proof, we then only need to show that
M
ymm 1 m
a
Σ
Vm
(41)
M
M
for all 1 S m' S m - 1. The result then follows from equation 40 and equation 41 To provee-
quation 41 recall that for any 1 I m' I m we have a/M Ym exp(-1
X + Vnn and
because y1 .... S yM, we have
1m This way, we have
m m
m Σ
(m" m')
Σ
ym exp (-1+ S exp (-1+ Vmm)
ym
(42)
m=
On the other hand, by equation 39 we have
M
(m* 1) exp(-1++)
Σ
Vm S exp (-1+ Vmm)
Σ
ym
(43)
m==
Combining equation 42 and equation 43 we have
1 1 (m' 1) aM
1-(m" 1) M + (m* - mmmmm M
Σ Emmm' Vm
Σm=r Um
exp (-1+ X + Vmn)
Sm Um + Mmmm- Dm
Emam Vmn
-ep (-1+ A Vm))
ym
which then implies equation 41
F SYNTHETIC EXPERIMENTS
In this section,
synthetic data to demonstrate the performance of AdDD Sampler. We compare our method against uniform sampling in Section F.I and compare against other ban- dit feedback online learning samplers in Section F.2 In addition, we examine the robustness of
Adaptive-OSMi Sampler to the choice of a in Section F33 while in Section [:4, we compare it with
the sampling without replacement variant discussed in Section C.5 Finally, in Section we show some empirical observation for regret analysis.
We generate data as follows. We set the number of clients M 100, and each client has 100 samples, m [M]. Samples on each client are generated as
Vm.i (w+ Rm..) N(0, 0.1
i E [nam]:
(44)
where the coefficient vector W. Rd has elements generated i.idd N(10, 3), and the feature vector Zm.i E Rdd is generated as Xmmi ~ E,,, where E.m = 8m Σ, a diagonal matrix with Σj = x(-1)/(d-1)-1 and k > 0 is the condition number of Σ. We generate {sm {M L..d. from ((),a² and rescale them 8mn (sm. maxme[[] 8m) x 10 so that 8.. 10 for all m E [M]. In this setting, controls the difficulty of each problem when solved separately, while a controls the level of heterogeneity across clients. In all experiments, we fix k = 25, which corresponds to a hard problem, and change to simulate different heterogeneity levels. We expect that uniform sampling suffers when the heterogeneity level is high. The dimension d of the problem set as d = 10. The results averaged over 10 independent runs.
32

---

Under review as a conference paper at ICLR 2023
We use the mean squared error loss defined
M Σ Lm(w),
1
L(w)
where
Lm(w)
(ym,,i (w*, xmm,))
2mem
We use the stochastic gradient descent to make global updates. each round f. we choose subset of K = 5 clients, denoted as S For each client m E S", we choose a mini-bat mini-batch of samples, B of size B 10, and compute the mini-batch stochastic gradient. The parameter w is updated as
w++1 wt
JSGD MKB
Σ
(ym, (w., Im,,)) Em,i
Pm iEB
mESt
where MSGD is the learning rate, set as MSGD 0.1 in simulations.
Adaptive- OSMnD Sampler as 0.4. The tuning parameters for MABS, VRB and Avare are set as in their original papers.
In all experiments, we
Computational resources and amount of compute. All the computation was done on a personal laptop. The synthetic data experiments are computed by CPU (Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz 2.59 GHz). Each run of experiments in this section took less than 10 minutes.
F.1 ADAPTIVE-OSMI SAMPLER VS UNIFORM SAMPLING
0=0.0
10.0
lagllas))
0
0
250
500
750
1000
250
500
750
1000
250
500
750
1000
logrrggett
12
12
10
10
250
500
750
1000
250
750
1000
250
500
750
1000
Optimal
The training loss (top row) and the cumulative regret (bottom row) of Adaptive-OSMD Sampler Uniform vs Optimal with 1.0, a 3.0, and 10.0. The solid line denotes the mean and the shaded region covers mean + standard deviation across independent runs.
Figure 1:
The results of the training process and the cumulative regret are shown in Figure I For the training loss, we see that when the heterogeneity level is low (o 1.0), the uniform sampling performs as well as Adaptive-OShl OSMii Sampler and theoretically optimal sampling: however, as the heterogeneity level increases, the performance of uniform sampling gradually suffers; when a = 10.0, uniform sampling performs poorly. On the other hand, Adaptive-OSMI) Sampler performs well across all levels of heterogeneity and is very close to the theoretically optimal sampling. Similarly, for the cumulative regret, when the heterogeneity level is low, the cumulative regret of uniform sampling is close to Adaptive-OSMD Sampler; however, when the heterogeneity level increases, the cumulative regret of uniform sampling gets much larger than Edaptive-OSMII Sampler. Based on the above results, we can conclude that while the widely used choice of uniform sampling may be reason- able when heterogeneity is low, our proposed sampling strategy robust across different levels of heterogeneity, and thus should be considered as the default option.
F.2 ADAPTIVE-OSMI SAMPLER VS MABS VS VRB VS AVARE
We compare Adaptive OSMD Sampler to other bandit feedback online learning samplers: MABS (Salehi al. 2017), VRB (Borsos et al. 2018) and Avare (Hanchi & Stephens 2020
33

---

Under review as a conference paper at ICLR 2023
1.0
3.0
10.0
-2.5
-2
-2
250
500
1000
250
500
1000
250
1000
16
14
14
14
10
250
500
750
1000
0
250
500
750
1000
250
500
750
1000
Optimal
Figure 2: The training loss (top row) and the cumulative regret (bottom row) of Adaptive-OSMD Sampler MABS VRB Avare with 1.0, a 3.0 and 10.0. The solid line denotes the mean and the shaded region covers mean + standard deviation across independent runs.
Training loss and cumulative regret are shown in Figure 2 form better when the heterogeneity level is low and MABS performs better when the heterogeneity level is high, Adaptive-SSMB Sampler always achieves the best in both training loss and cumula- tive regret across all different levels of heterogeneity. Thus, we conclude that Adaptive is better choice than other online learning samplers.
We see that while VRB and Avare per-
F.3 ROBUSTNESS OF ADAPTIVE-OSMD SAMPLER TO THE CHOICE OF a
We examine the robustness of Adaptive-OMMD Sampler to the choice of a. We run Adaptive- OSMD Sampler separately for each E {0.01, 0.1, 0.4, 0.7, 0.9, 1.0]. Note that when a 1.0, the Adaptive-OSMD Sampler outputs uniform distribution. Training loss and cumulative regret are shown in Figure 3 We observe that Adaptive-OSMDD Sampler is robust to the choice of a, and performs well as long is not too close to zero or too close one.
F.4 EXPERIMENTS ON SAMPLING WITH REPLACEMENT VS WITHOUT REPLACEMENT
We compare sampling with replacement and sampling without replacement when used together with Slaptive-OSMD sampler. Sampling without replacement is described in Section C.5 Training loss and cumulative regret are shown in Figure We observe that using sampling with replacement results in slightly smaller cumulative regret and slightly better training loss. However, these differences are not significant.
F.5 DYNAMIC SAMPLING DISTRIBUTION V.S. FIXED SAMPLING DISTRIBUTION
In this paper, we allow both our sampling distribution and competitor sampling distribution to change over time, while previous studies either use fixed sampling distribution (Zhao & Zhang 2015 Needell et al. 2016) or they compare against fixed sampling distribution (Namkoong al., 2017 Salehi et al. 2017 Borsos et al.] 2018 2019). In this section, we show that under certain settings, dynamic sampling distribution can achieve significant advantage over fixed sampling dis- tribution. More specifically, compare Adaptive-OSMD Sampler with the Lipschitz constant based importance sampling distribution proposed by Zhao Zhang (2015): Needell et al. (0166), which we denote SS
We still use the same model as in equation to generate data. but we generate w, and Im,i differently. Motivated by Zhao al. (2022) for each E [M], choose uniformly random one dimension among " denoted as supp m. E [d]. as the support of rm. for all [n while the remaining dimensions of Fm j
be zero. The nonzero dimension of Fm, is generated
34

---

Under review as a conference paper at ICLR 2023
0=10.0
log(loss]
0
-2
0
250
500
750
1000
250
500
750
1000
0
250
500
750
1000
12
14
logiregret)
12
15
10
9
0
250
500
750
1000
250
500
750
1000
250
500
750
1000
0.01
0.1
0.4
a 0.7.
0.9
1.0
Optimal
Figure 3: The training loss (top row) and the cumulative regret (bottom row) of Adaptive-OSMD Sampler with different choices a under a 1.0, a 3.0 and = 10.0. The solid line denotes the mean and the shaded region covers mean + standard deviation across independent runs.
1.0
3.0
10.0
4
4
log[loss]
2
2
2
0
-2
0
250
500
750
1000
0
250
500
750
1000
0
250
500
750
1000
11-
log(regret)
10
10
8
250
500
750
1000
250
500
750
1000
250
500
750
1000
t
t
t
Ada-OSMD with a 0.4
Ada-OSM Mad-OSMD--oRRpplaee with a= 0.4
Optimal
Figure 4: The training loss (top row) and the cumulative regret (bottom row) of Adaptive-OSMD
Sampler with replacement without replacement across 1.0, 3.0 and 10.0. The solid line denotes the mean and the shaded region covers mean + standard deviation across independent
runs.
35

---

Under review as a conference paper at ICLR 2023
1.0
10
log(loss)
30
-2
-5
0
250
500
750
1000
0
250
500
750
1000
0
250
500
750
1000
50
20.0
logiregret)
48
15.0
46
12.5
44
10.0
250
500 t
750
1000
250
500
750
1000
250
500
750
1000
t
t
Ada-OSMD
IS
Figure 5: The training loss (top row) and the cumulative regret (bottom row) of Adaptive-OSMD Sampler vs p across 1.0, 3.0 and 10.0. The solid line denotes the mean and the shaded region covers mean + standard deviation across independent runs.
from (1.0, 0.13). The entries of w. are generated i.idd from e (0,,") Therefore, & controls the variance entries of w..
Besides, we choose the optimal stepsize from the set 0.1, 0.05, 0.01} for each method separately. The final result shown in Figure 5 We see that Adaptive OSMD Sampler performs better than p across all levels of v. Note that in practice, in order to implement p we need prior information about Lipschitz constants Lm (-)'s, while Adaptive-OSMD Sampler does not need prior information. This way, our proposed method does not only have better practical performance, but also requires less prior information.
F.6 EMPIRICAL OBSERVATION REGRET
In Corollary we see that the upper bound for the regret of OSMD sampler with respect any comparator sequence q²:ı depends section, we first empirically show how a' and "iii(aaa) grow with in practice. Then, we use 1: as the comparator and show how TV(p2=1) grow with empirically. Finally, we also empirically show how the regret (p. grows. The experimental setting of this section is the same as Section
important quantities: Et (at)² and TV In this
In Figure
6 plot both a' and Ea") over t. We see that a' drops to zero fastly. As result EL (a converges constant - This way, we empirically have Σ (a²)² 0(1). In Figure 7 show how TV(p!*) grows with t. We that TV(p!=t
O(t) empirically, which is consistent with the worst-case upper bound. Based on this result, the best upper bound of D-Regret,-(12e (x):²) we can hope in practice is O(VT). However, as shown in Figure 8 in practice, we have (p! converge to constant. This observation indicates that the upper bound we obtained might still be loose compared practical result.
G REAL DATA EXPERIMENT
We compare Adaptive-OMMD Sampler with uniform sampling and other online learning samplers including MABS (Salchi et al, 2017). VRB (Borsos et al. 2018) and Avare (Hanchi & Stephens, 2020) real data. We use three commonly used computer vision data sets: MNIST (LeCun &
36

---

Under review as a conference paper at ICLR 2023
1.0
o 3.0
dh 10.0
80
200
150
100
50
400
600
1000
700
400
1000
200
400
800
1600
300000
70000
250000
50000
150000
40090
100000
20000
10000
Figure 6: Plots of how and Σ (a grow with f.
20
300
200
T00p
150
200
0
200
460
600
800
1000
200
400
500
800
1000
200
430
630
830
1000
Figure 7: Plots of how TV grows with t.
==
0=0.0
== 10.0
120000
60000
100000
50000
80000
150000
60000
100000
30000
40000
50000
20000
1006
Figure 8: Plots of how (p! I.T) grows with
37

---

Under review as a conference paper at ICLR 2023
Cortes, 2010 R
KMINIST (Clanuwat et al. 2018 and FMINST (Xiao et al. 2017 10
We set
the number of devices to be M = 500. To better simulate the situation where our method brings significant convergence speed improvement,
create highly skewed sample size distribution of the training set among clients: 65% of clients have only one training sample, 20% of clients have 5 training samples, 10% of clients have 30 training samples, and 5% of clients have 100 training samples. This setting tries to illustrate real-life situation where most of the data come from a small fraction of users, while most of the users have only small number of samples. The skewed sample size distribution is common in other FL data sets, such as LEAF (Caldas et al. 2018). The sample addition, each client has 10 validation
size distribution the training set is shown Figure ? samples used to measure the prediction accuracy of the model over the training process.
We use a multi-class logistic regression model. For a given gray scale picture with the label y E (1, ..... C), we unroll its pixel matrix into vector x E R². Given parameter matrix W E R the training loss function defined in equation
@ sr, v) = ICE
where :R) + RC the softmax function defined as
exp(x;;
[s(z], = ΣØ exp(x,))
for all x ERC
and (<E(<; = 1 1 log R (I,..., is the cross-entropy function.
We use the same algorithms and tuning parameters as Section Learning rate SGD set to 0.075 for MNIST and KMNIST, and is set to 0.03 for FMNIST. The total number of communication rounds is to 1, 000. In each round of communication, we choose K = 10 clients to participate (2% of total number of clients). For chosen client m, compute its local mini-batch gradient with the batch size equal to min (5, n. where nm is the training sample size on the client m.
Figure 10 shows both the training loss and validation accuracy. Each figure shows the average per- formance over independent runs. We use the same random seed for both Adaptive- Sampler and competitors, and change random seeds across different runs. The main focus on minimizing the training loss, and the validation accuracy only included for completeness. We observe that Hlaptive-OSMD Sampler performs better than uniform sampling and other online learning plers across all data sets. Given the cheap computational cost and the significant practical advantage, recommend using Adaptive-OSMa OSMD Sampler the default option in practice. Besides, for the completeness of the paper, we also include the results under homogeneous setting where the sample sizes are balanced across different clients. The result shown in Figure [1] where we see that all methods perform similarly.
Computational resources and amount of compute. All the computation was done on a personal laptop. The real data experiments are computed by GPU (NVIDIA GeForce RTX 2070 with Max-Q Design). Each run of all experiments in this section took less than 15 minutes.
H DISCUSSION
We studied the client sampling problem in FL. We proposed an online learning with bandit feedback approach to tackle client sampling. We used online stochastic mirror descent to solve the online learning problem and applied the online ensemble method with doubling trick to choose the tuning parameters. We established an upper bound on the dynamic regret relative to the theoretically opti- mal sequence of sampling distributions. The total variation of the comparator is explicitly included in the upper bound as a measure of the difficulty of the problem. Extensive numerical experiments
$ Yann LeCun Corinna Cortes hold the copyright of MNIST dataset, which a derivative work from original NIST datasets. MNIST dataset is made available under the terms of Creative Commons Attribution- Share Alike 3.0 license.
"KNNIST dataset is licensed under permissive CC BY-SA 4.0 license, except where specified within some henchmark scripts.
10MNNIST dataset is under The MIT License (MIT) https//tech.raland.ccom
Copyright
[2017] Zalando SE,
38

---

Under review as a conference paper at ICLR 2023
Sample size distribution
300
number of users
200
100
0
20
40
60
80
100
number of samples
Figure 9: The sample size distribution in the training set across clients.
Unifsmm
Ad-O5MD
MARS
Figure 10: Comparison between Adaptive- OSMpi Sampler, uniform sampler and other online learn- ing samplers real data in terms of training loss (top row) and validation accuracy (bottom row). Different columns correspond to different data sets. The solid line represents the mean and the shadow area represents mean 0.5 standard error. Adaptive-OSMD Sampler is both faster and more stable. The result is the average performance over independent runs.
39

---

Under review as a conference paper at ICLR 2023
Un Form
Adw-CSMD
MABS
VRB
Arar
MNIST
KMNIST
FMNIST
-1.50
-1.60
-1.60
-1.75
-1.80
2000
2.25
-2.00
Log(oss)
2.20
2.20
-2.75
-2400
-3.00
-2.60
2.60
-3.25
-2.00
-2.80
3.50
300
750
1000
1.00
1,00
Aocuray
Aucuracy
Accuracy
0.50
0.50
0.50
0.25
0.25
0.25
0.00
250
500
750
1003
0.00
250
500
750
1000
0.00
0
253
300
750
1000
Communication Rounds
Communication Rounds
Communication Rounds
Figure 11: Comparison between Adaptive- OSMD Sampler, uniform sampler and other online learn- ing samplers real data in terms of training loss (top row) and validation accuracy (bottom row) under balanced samples size. Different columns correspond to different data sets. We see that all methods perform similarly.
demonstrated the benefits of our approach over both widely used uniform sampling and other com- petitors.
In this paper. we have focused on sampling with replacement. However, sampling without replace- ment would ideally be a more efficient approach. In Section C.5 we discussed natural extension of AdSD Sampler to setting where sampling without replacement is used. However, this approach does not directly minimize the variance of the gradient g". When sampling without placement is used, the variance function becomes more complicated and the design of an algorithm to directly minimize the variance is an interesting future direction.
Besides, in federated learning, privacy is major concern. In this paper, the non-uniform sampling distribution may make the protection of clients' privacy more challenging than uniform sampling. One possible solution is to add noise to the gradient feedback and protect the clients' privacy un- der the Differential Privacy (DP) concept (Dwork) 2008). However, the added noise may hurt the performance of our sampling design and increase the regret. Studying the trade-off between pri- vacy protection and regret is an important direction for addressing societal concerns in real-world application.
Other fruitful future directions include the design of sampling algorithms for minimizing personal- ized FL. objectives and sampling with physical constraint in FL system, which discuss next.
40

---

Under review as a conference paper at ICLR 2023
H.1 CLIENT SAMPLING WITH PERSONALIZED FL OBJECTIVE
Data distributions across clients are often heterogeneous. Personalized FL has emerged as one effective way to handle such heterogeneity (Kulkarni et al. 2020). Hanzely et al. (2021) illustrated how many existing approaches to personalization can be studied through a unified framework, and, in this section, we discuss natural extension of Adaptive-OSMM Sampler to this personalized objective. Specifically, we study the following optimization problem
M
min F(,, w.,3
=
Σ m==1
Amo(w, Bmi Dm),
(45)
where w E Ie corresponds to the shared parameter and 3 = (31, (31...., Bxr) with 8m E Rd
corresponds to the local parameters. The objective equation (45iioon455ooor equation[4] coves federated learning problems (Hanzely et al. (021). We further generalize the approach and study the following bilevel optimization problem:
wide range of personalized
min h(w)
Σ Am Fmn Fu, (m)) Σ Am Amo(w, Bml(w): Dan))
(46)
subject to Bm(w) = arg min mig
Gm (w, 3m) = Φlw, Bm: Dmm)
recovers equation 45 When D' F D Dm, we then optimize the shared and local parameters different datasets, which may prevent overfitting. The formulation in equation i closely related to the implicit MAML (Rajeswaran et al. 2019).
When D.. = Dm, then equation 46
In the following, we V.. denote partial derivative with respect w with 3. fixed, V A.. to denote partial derivative with respect to 8m with w fixed, and V to denote a derivative with respect w where By, (w) is treated function of w. Let V 3.m Gm Pm) Rd Rdm be the Hessian matrix of Gm. with respect to B. where w is fixed, and V w0mm Gm(w, 8m) E Rox be the Hessian matrix of Gm with respect to w and Bm. that is,
8Gm (w, 3m) imm a0m (w, Bm)
V Pem. (w, B.))
for all i 1,2, ....... d.
V We (uc, Pm))
for all 1,2, do. -1,2.....
By the implicit function theorem, we have
M
M
Vh(ww= = M
Am V Fm, (w)) + M
Σ Am 2 (m)))) m=1
(47)
m
Vih(w)
Vah(w)
where
V Fm (w, Bm (w)) V a Fm (w, (w)):
V2Fm (w. Bm == mB Fm (w. Bm (w))
V2 V Bm Fm(w, Am (w))
V
Ban. (w, Bm (w)).
There are two parts to Vh(w") and, therefore, instead of choosing a single subset of clients for computing both parts, decouple St into two subsets S and S S S U U.S. We use clients in Sf to compute local updates of the first part, and clients in St to compute the local updates of the second part. To get an estimate of Vh(w). then combine. Assume that gi.m an estimate of V, Fm (w, Am (w)) and 98.m. an estimate of 22 (w, (w)), we can then construct estimates of Vih(w) and V2h(w)
can estimate V Vih(w) and V2h(wr separably and
Lim
oi K
Xm
g2
Σ
Am
Pi...
K2
P²,m
MESt
MESt
where K; [G and K₂ | Then g oi + o is estimate of Vh(w).
41

---

Under review as a conference paper at ICLR 2023
We design pi and på to choose Si and S2 by minimizing the variance of the gradients. Note that
min E1 pi
Ey ||li Vih(w") min E2
Est
|1 V2h(w'))1
P2
min
s
||lst
Vih(w")
gb [an(w"))]]
so that the decomposition allows us to better minimize the variance. We term this approach as doubly variance reduction for personalized Federated Learning. The first part minimizes the variance of updates to the shared global parameter, when the best local parameters are fixed; and the second part minimizes the variance of updates to local parameters, when the global part is fixed. While these two parts are related, any given machine will have different contributions to these two tasks.
Adaptive-O OSMDe---MDDDD Sampler be used minimize the variance for both parts of the gradient. We note that this is a heuristic approach to solving the client sampling problem when minimizing a personalized FL objective. Personalized FL objectíves have additional structures that should be used to design more efficient sampling strategies. Furthermore, designing sampling strategies that improve the statistical performance of trained models, rather than improving computational speed, is important in the heterogeneous setting. Addressing these questions is an important area for future research.
H.2 SAMPLING WITH PHYSICAL CONSTRAINT IN FL SYSTEM
In this paper, assume that all clients available in each round. However, in practical FL applications, a subset of the clients may be inactive due to physical constraints, thus we have to assign zero probabilities them. In this section, we propose simple extension of proposed sampling method to such case.
Specifically, denote the subset of clients that are active at the beginning of round t as H' C [M]. If we have |=| < K, we can then use all clients in I' to make updates in round f; otherwise, we would like choose smaller subset St S Ie to participate. This can be achieved by rescaling the output sampling distribution of any of our proposed methods, which we denote as p². We let Pt. /E p))) and P for all m & It. We can then use Pt, choose St from I'.
However, analyzing such method in terms of convergence and regret guarantee is highly non- trivial. Typically, for general active clients sequence [t=) the optimization algorithms are not guaranteed to converge even if we involve all clients in 7 in each round. This can happen, for ex- ample, if client is active for only once in the whole training process. Thus, to ensure convergence, need additional assumptions about { Moreover, deriving regret bound is also very chal- lenging, as assigning zero probability to any client will make the variance-reduction loss unbounded and thus the regret be arbitrarily large. To achieve such theoretical result, one may need to ap- propriately redefine the regret concept. Such an analysis is beyond the scope of this paper and we leave it for future research.
42


Reviews:
[{"review_id": "wf6tEUfdOR", "reviewer": "Reviewer_ZCkp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work examines adaptive client sampling in federated learning. The paper's major contribution is to treat client sampling as an online learning problem and to create an algorithm employing a novel sampler (OSMD) with a nice theoretical guarantee.", "summary_of_the_review": "This paper established the first regret bound of applying online learning technique on the client sampling in federated sampling. But in my opinion, the presentation could be further improved. Furthermore, it appears to me that a related sampler has already been described in Borsos et al., 2018, so it would be better if the author(s) could describe the technical challenges involved in establishing the necessary bound. Overall I suggest weak accept.", "strength_and_weaknesses": "Strength\n* This study establishes the regret upper bound for the first time.\n* Numerous tests are performed to validate the suggested algorithm.\n\nWeaknesses\n* The presentation of this paper could be improved. It could be preferable if the author(s) included Section 3, which applies the suggested OSMD sampler to MINI-BATCH SGD, in the appendix rather of the main paper and included the experiments there instead. Additionally, there is no concluding paragraph.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "irEnyYZgN5", "reviewer": "Reviewer_Hgfz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Stochastic optimization algorithms typically work by estimating the gradient of the cost function on the fly, and thus, their convergence rate depends on the cumulative variance of the gradient estimation. Therefore, proper selection of the sampling probability on the data points (that are used to compute the gradient) can help reduce this variance. \nSimilarly, under the federated/distributed setting, the server estimates the gradient by sampling a subset of clients, and this paper proposed an online stochastic mirror descent algorithm to decide the sampling probabiilty on the clients. As the optimal sampling probability changes in every round, the author proved the dynamic regret of online stochastic mirror descent algorithm.", "summary_of_the_review": "This paper is technically sound, and the idea of using OSMD for client sampling is natural and well-motivated. Therefore, I recommend accept.", "strength_and_weaknesses": "Strength:\n1. Although I didn't check all the proof, the results in this paper look intuitive and technically sound.\n2. This paper is well-motivated, and the proposed OSMD method is of interests to federated learning and stochastic optimization.\n\nWeakness & Questions:\n1.  There lacks enough discussions and comparison with federated learning algorithms, e.g. a table summarizing the settings and theoretical results may be helpful. Currently, the discussions in this paper is more about variance reduction for gradient estimation in stochastic optimization algorithm. It is a bit unclear to me the contribution/improvement compared with existing federated learning algrithms. I would appreciate it if the authors could provide more explanations. For example, can the proposed method help attain linear convergence to the global optimum for strongly convex and smooth functions, as in (Mitra et. al. 2021)?\n\nMitra, A., Jaafar, R., Pappas, G.J. and Hassani, H., 2021. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34, pp.14606-14619.\n\n2. I am curious, in Algorithm 3, is it possible to apply OSMD to learn the sampling probabilities of mini-batch SGD in line 8, and will it be helpful?\n\n3. At the end of section 2.1, the authors mentioned \"will treat the environment as deterministic\". Can the authors elaborate more on this? What is our assumption on the sequence of variance reduction loss function, can it be generated by an adaptive adversary?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_ArRDuCrcB", "reviewer": "Reviewer_dGNg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies adaptive client sampling in federated optimization and formulates it as the problem of online sampling variance minimization with bandit feedback. To address this problem, the authors propose an online stochastic mirror descent (OSMD) algorithm and establish dynamic regret bound. Moreover, the convergence rate of federated optimization with the proposed OSMD sampler is also established.", "summary_of_the_review": "By considering the issue of insufficient experiments, I tend to reject this paper.", "strength_and_weaknesses": "#Strength\n1) Previous studies about online sampling variance minimization with bandit feedback focus on static regret. By contrast, this paper considers dynamic regret. To achieve a dynamic regret bound, the authors propose the online stochastic mirror descent (OSMD) algorithm, which is the main contribution of this paper and is new to me.\n2) The combination of the OSMD sampler with federated optimization seems to be reasonable and the convergence rate has also been proved.\n\n#Weakness\n1) The organization of this paper is a little strange. In the main paper, the authors do not provide experimental results, which seems to be important for studies on federated learning. Moreover, it would be better if the complete related work is introduced in the main paper.\n2) The experimental results provided in the appendix are not sufficient to verify the advantage of the proposed method. First, from Figures 2 and 10, the performance of the existing MABS method is close to that of the proposed method in terms of loss. Second, the authors do not provide experiments to show the necessity of dynamic regret, which is the main novelty of the paper. \n3) I agree that the proposed OSMD is applicable beyond federated learning. Therefore, it is a little strange why the authors do not directly study the larger problem, namely stochastic optimization. Moreover, it seems that federated learning does not bring an essential challenge compared with stochastic optimization.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UvgPsllDAE", "reviewer": "Reviewer_cLap", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies client selection in federated learning. The authors cast this problem as an online learning task with bandit feedback. They proposed to adopt online stochastic mirror descent (OSMD) to minimize the sampling variance. ", "summary_of_the_review": "This work is technically sound and solves an interesting problem of adaptive client selection in federated learning. The solution has solid theoretical foundation. It would be great if the weakness aspects can be resolved.", "strength_and_weaknesses": "+ Formulating the client selection problem as an online learning one with bandit feedback is an interesting idea, which allows the use of dynamic regret to measure the performance.\n+ Both convergence and regret are analyzed.\n\nWeakness:\n- The empirical performance of the proposed adaptive client selection is not well presented. The authors are suggested to report experimental results with standard FL tasks for both IID and non-IID clients on (FE)MNIST, CIFAR, and Shakespeare datasets.\n- From a pure theoretical point of view, there is limited novelty of this work (especially from the online learning aspect). The theoretical results and their derivations are fairly standard. The gradient in (7) follows the same idea as the unbiased estimate of $l_t(q)$, i.e., the expectation of number of times client $m$ is selected equals $Kp_m^t$, and I do not understand why this is novel.\n- I'm wondering why the authors did not choose adversarial learning as the tool to study this FL client selection problem.\n- Sampling with replacement is used in the main paper. It is unclear how this is relevant in practice -- it would lead to potentially selecting the same client multiple times in one round of FL, which is unrealistic.\n\n\n----\nPost-rebuttal comment:\nI thank the authors for their responses, in particular providing new simulation results for FL. I would encourage the authors to carefully consider the organization of this paper -- if the theoretical results of online learning are not the main contributions, maybe the authors can consider moving the theoretical part to appendix, while moving the experimental results to the main paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject