Handling Covariate Shifts in Federated Learning  with Generalization Guarantees
Authors: Ali Ramezani-Kebrya
Fanghui Liu
Thomas Pethick
Grigorios Chrysos
Volkan Cevher
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federate Learning
Generalization
Covariate Shift
Importance Weighting

Abstract: Covariate shift across clients is a major challenge for federated learning (FL). This work studies the generalization properties of FL under intra-client and inter-client covariate shifts. To this end, we propose Federated Importance-weighteD Empirical risk Minimization (FIDEM) to optimize a global FL model, along with new variants of density ratio matching methods, aiming to handle covariate shifts. These methods trade off some level of privacy for improving the overall generalization performance. We theoretically show that FIDEM achieves smaller generalization error than classical empirical risk minimization under some certain settings. Experimental results demonstrate the superiority of FIDEM over federated averaging (McMahan et al., 2017)  and other baselines, which would open the door to study FL under distribution shifts more systematically.


Under review as a conference paper at ICLR 2023
HANDLING COVARIATE SHIFTS IN FEDERATED LEARNING WITH GENERALIZATION GUARANTEES
Anonymous authors Paper under double-blind review
ABSTRACT
Covariate shift across clients is a major challenge for federated learning (FL). This work studies the generalization properties of FI. under intra-client and inter- client covariate shifts. To this end, we propose Federated importance-weigheee Empirical risk Minimization (FIDEM) to optimize global FL model, along with new variants of density ratio matching methods, aiming to handle covariate shifts. These methods trade off some level of privacy for improving the overall generalization performance. We theoretically show that FIDEM achieves smaller generalization eтrоr than classical empirical risk minimization under some certain settings. Experimental results demonstrate the superiority of FIDEM over federated averaging (McMahan et al., 2017) and other baselines, which would open the door to study FL under distribution shifts more systematically.
INTRODUCTION
Federated learning (FL) (Li al., 2020; Kairouz et al., 2021; Wang et al., 2021) an efficient and powerful paradigm to collaboratively train shared machine learning model among multiple clients, such as hospitals and cellphones, without sharing local data.
Existing FL literature mainly focuses on training a model under the classical empirical risk min- imization (ERM) paradigm learning theory, with implicitly assuming that the training and test data distributions of each client are the same. However, this stylized setup overlooks the specific requirements of each client. Statistical heterogeneity is a major challenge for FL, which has been mainly studied in terms of non-identical data distributions across clients, i.e., inter-client distribution shifts (Li et al., 2020; Kairouz et al., 2021; Wang et al., 2021). Even for a single client, the distribution shift between training and test data, i.e., intra-client distribution shift, has been a major challenge for decades ( (Wang & Deng 2018; Kouw & Loog 2019, and references therein). For instance, scarce dis- ease data for training and test local hospital can be different. To adequately address the statistical heterogeneity challenge in FL, we need to handle both intra-client and inter-client distribution shifts under stringent requirements in terms of privacy and communication costs.
We focus on the overall generalization performance on multiple clients by considering both intra- client and inter-client distribution shifts. There exist three major challenges to tackle this problem: 1) how to modify the classical ERM to obtain an unbiased estimate of an overall true risk minimizer under intra-client and inter-client distribution shifts; 2) how to develop an efficient density ratio estimation method under stringent privacy requirements of FL; 3) are there theoretical guarantees for the modified ERM under the improved density ratio method FL?
We aim to address the above challenges in our new paradigm for FL.. For description simplicity, in our problem setting, we focus on covariate shift, which is the most commonly used and studied in theory and practice in distribution shifts (Sugiyama et al., 2007; Kanamori et al., 2009; Kato & Teshima, 2021; Uehara et al., 2020; Tripuraneni et al., 2021; Zhou & Levine, 2021). To be specific, for any client k covariate shift assumes the conditional distribution Ph (ylx) = pk (ylx) == p(ylx) remains the same; while marginal distributions p (x) and pf((x) (x) can be arbitrarily different, which gives rise intra-client and inter-client covariate shifts. Handling covariate shift is challenging issue,
especially in federated settings (Kairouz et al., 2021).
'Our results can he extended to other typical distribution shifts, e.g., target shift (Azirzadenesheli, 2022). We provide experimental results target shift in Section 5.

---

Under review as a conference paper at ICLR 2023
To this end, motivated by Sugiyama al. (2007)
Server
under the classical covariate shift setting, we propose Federated Inportance-weighheD Empir- ical risk Minimization (FIDEM), that considers covariate shifts across multiple clients in FL., We show that the learned global model under intra/inter-client covariate shifts still unbiased in terms of minimizing the overall true risk, i.e., FIDEM consistent FL. To handle covariate shifts accurately, we propose histogram- -based density ratio matching method (DRM) under both intra/inter-client distribution shifts. Our method unifies well-known DRMs in FL, which has its own interest in the distribution shift community for ratio estimation (Zadrozny, 2004; Huang et al., 2006; Sugiyama et al., 2007; Kanamori
selabhilee
Runslenly shaffled pfol
CO
Estieayy lepectzce salos
Corppr (PIDEM)
Clera En Expesliet
ginins ding devaal batcher
Crudkenoreci cohiecrrpee sferapiatu inporizor
Clients
Figure 1: An overview of FIDEM. Marginal train and test. distributions clients are arbitrarily different lead- ing to intra-client and inter-client covariate shifts. To control privacy leakage, the server randomly shuffles unlabelled test samples and broadcasts the clients.
et al., 2009; Sugiyama et al., 2012; Zhang et al., 2020; Kato & Teshima, 2021). To fully eliminate any privacy risks, we introduce another variant of FIDEM, termed Federated Independent Importance- weighteD Empirical risk Minimization (FIIDEM), It does not require any form of data sharing among clients and preserves the same level of privacy and same communication costs as those of baseline federated averaging (FedAvg) (McMahan et al., 2017). An overview of FIDEM is shown in Fig. 1.
1.1 TECHNICAL CHALLENGES AND CONTRIBUTIONS
Learning on multiple clients in FL under covariate shifts via seportance-weightee ERM is challenging due to multiple data owners with own learning objectives, multiple potential but unpredictable train/test shift scenarios, privacy, and communication costs (Kairouz et al., 2021). To be specific, 1) It is non-trivial to control privacy leakage to other clients while estimating ratios and relax the requirement to have perfect estimates of the supremum over true ratios, which is key step for non- negative BD (nnBD) DRM. Our work is the first step towards handling inter/inter-client distribution shifts in FL;
2) It is challenging to obtain per-elient generalization bounds for general nnBD DRM with multiple clients and imperfect estimates of the supremum due to intra/inter-cliee couplings in ratios. Note that, even we have access to perfect estimates of density ratios, it still unclear whether importance- weighted ERM results in smaller excess risk compared to classical ERM. Our work gives an initial attempt by providing an affirmative answer for ridge regression;
3) While well-established benchmarks for multi-client FL have been used, they usually designed in a way that each client's test samples are drawn uniformly from a set of classes. However, we believe this might not be the case in real-world applications and then design realistic experimental settings in our work.
To address those technical challenges, we
Algorithmically propose an intuitive framework to minimize average test error in FL, design efficient mechanisms to control privacy leakage while estimating ratios (FIDEM) along with a privacy-preserving and communication-effiiie variant (FIIDEM), and improve nnBD) DRM under FL without requiring perfect knowledge of the supremum over true ratios.
Theoretically establish generalization guarantees for general nnBD DRM with multiple clients under imperfect estimates of the supremum, which unifies a number of DRMs, and show benefits of importance weighting in terms of excess risk decoupled from density ratio estimation through bias-variance decomposition.
Experimentally demonstrate more than 16% overall test accuracy improvement over existing FL baselines when training ResNet-18 (He al., 2016) on CIFARIO (Krizhevsky) in challenging imbalanced federated settings in terms of data distribution shifts across clients.
In conclusion, we expand the concept and application scope of FL to a general setting under intra/inter- client covariate shifts, provide an in-depth theoretical understanding of learning with FIDEM via general DRM, and experimentally validate the utility of the proposed framework. We hope that our work opens the door to new FL. paradigm.
2

---

Under review as a conference paper at ICLR 2023
1.2 RELATED WORK
In this section, we overview a summary of related work. See Appendix B for complete discussion.
The current FL. literature largely focuses on minimizing the empirical risk, under the same train- ing/test data distribution assumption over each client (Li et al., 2020; Kairouz et al., 2021; Wang al., 2021). In contrast, we focus on learning under both intra-client and inter-client covariate shifts. Communication--fficee -eftiiinnfffiient,, robust, and secure aggregations can be viewed as complementary technologies, which can be used along with FIDEM to improve FIDEM's scalability and security while addressing overall generalization. Shimodaira (2000) introduced covariate shift where the input train and test distributions are different while the conditional distribution of the output variable given the input variable remains unchanged. Importance- ization performance under covariate shift (Zadrozny, 2004; Sugiyama & Müller, 2005; Huang et al., 2006; Sugiyama et al., 2007; Kanamori et al., 2009; Sugiyama et al., 2012: Fang al., 2020; Zhang et al., 2020; Kato & Teshima, 2021). Sugiyama et al. (2012) proposed a Bregman divergence- based DRM, which unifies various DRMs. Kato & Teshima (2021) proposed non-negative Bregman divergence- based DRM when using deep neural networks for density ratio estimation. Our work largely differs from Kato & Teshima (2021) in problem setting that allows multiple clients, algorithm design to estimate different ratios across clients while controlling privacy leakage, and theoretical analyses show the benefit of importance weighting in generalization.
ERM is widely used to improve general-
COVARIATE SHIFT AND FIDEM FOR FL
We first provide the problem setting under intra/inter client covariate shifts, and then describe the proposed FIDEM as an unbiased estimate in terms of minimizing the overall true risk?.
2.1 PROBLEM SETTING
Let X S Rd be a compact metric space, y S Rdd,, and K be the number of clients in an FL setting. Let S₂ ((x,,,), ) denote the training set of client k with n samples drawn i.id from an unknown probability distribution p on X' y.² The test data of client k drawn from another unknown probability distribution PE on X' x y. Under the covariate shift setting (Sugiyama et al., 2007; Kanamori et al., 2009; Kato & Teshima, 2021; Uchara et al., 2020; Tripuraneni et al., 2021; Zhou & Levine, 2021), the conditional distribution ( x) p (y(x) := p(y /x) is assumed to be the same for all k while pl (x) and pk (x) can be arbitrarily different, which gives rise to intra-client and inter-client covariate shifts. We consider supervised learning where the goal is to find a hypothesis hw : X' + y, parameterized by w E Rd e.g., weights and biases of a neural network, such that (x) (for short h (x)) is good approximation of the label y E y corresponding to new sample x E X. Let E X x y 1 denote a loss function. In our FI. setting, the true (expected) risk of client is given by R& (hw) E( [e y))
2.2 FIDEM FOR FL UNDER COVARIATE SHIFT
For scenario with K clients, we first focus on minimizing R₁ (1 [K] under intra/inter-client covariate shifts, i.e., p (x) F ple (x) for all k. We then formulate FIDEM to minimize the average test error over K clients under covariate shifts by optimizing a global model under our FL setting.
FIDEM for one client. by:
Under p [ + pt (x) Ak, FIDEM focusing minimizing R₁ is given
min wERd
E(h (x)
(2.1)
(xx(.)
In Appendix C, we elaborate four special cases of the above scenario, i.e., px((() # pl (x) Vk. focusing on one client under various covariate shifts and formulate their FIDEM's.
(x)
NNotations are provided in Appendix A. For notational simplicity, we use the notation for probability distributions and density functions.
3

---

Under review as a conference paper at ICLR 2023
[K]. FIDEM in Eq. (2.1) is consistent. i.e., the learned function converges in probability to the optimal function finctiion in terms of minimizing Rd.
Proposition 1. Let l
See Appendix C for the proof. Proposition implies that, under intra/inter-client covariate shifts, FIDEM outputs an unbiased estimate of a Irue risk minimizer of client l. In Appendix C.I, we show usefulness of importance weighting under no intra-client covariate shifts but inter-client covariate shifts, which is special and important case of our setting.
Building on Eq. (2.1) that aims minimize R₁, we now formulate FIDEM to minimize the average test eπrоr over all clients and explain its costs and benefits for federated settings.
FIDEM for K clients. Let w be the global model. For K clients under intra/inter-cline covariate shifts, FIDEM minimizes the average test error over all clients and is formulated as:
K
min F(w) = WER
Fl(w),
(FIDEM)
where
Σ 1== (xW.e) pk (x
Fk(w) tE
(x
(2.2)
Each client requires an estimate of a ratio in the form of sum test over own train. We emphasize that (w(w) should not be viewed as the local loss function of client k. Our formulation FIDEM is meant to minimize the overall test eπror over all clients given intra/inter-client covariate shifts. To solve FIDEM, we employ the stochastic gradient descent (SGD) algorithm for T iterations starting from an initial parameter Wo: Wt+1 = W; Σx= gA (W:) where T): > 0 is the step size, g& (w,) an unbiased estimate Fi (w.,) and WT is the output.
Under no covariate shift, both FIDEM and classical ERM result in the same solution, which is minimizer of the overall empirical risk. The main difference happens under intra-client and inter- client covariate shifts. In those challenging settings, FIDEM'ss solution is an unbiased estimate of a minimizer of the overall true risk, while the solution of ERM minimizes the overall empirical risk.
2.3 PRIVACY, COMMUNICATION AND COMPUTATION IN FL
Privacy and communication efficiency are major concerns in FL (Kairouz et al., 2021). We elaborate on them and introduce another variant of FIDEM with the same guarantees and costs as FedAvg.
Communicationcomppttainnaa costs and security benefits. Compared classical ERM, the communication/compplatiiooo overhead of FIDEM is negligible." 4 To solve FIDEM, client k should compute an unbiased estimate of the weighted gradient Vw (w,). which requires single back- ward pass at a single parameter w = W.. Hence, given the ratios, there is no extra computa- tional/communication overhead compared classical ERM. Clients compute the ratios in parallel. In Appendix E, we provide a concrete example and show that the number of communication bits needed during training in standard FL is usually many orders of magnitudles larger than the size of samples shared for estimating the ratios. To further reduce communication costs of density ratio estimation and gradient aggregation, compression methods such as quantization, sparsification, and local updating rules, can be used along with FIDEM the fly. More importantly, due to importance weighting, gA (w) can be arbitrarily different from an unbiased stochastic gradient of classical ERM
for client k;, i.e., n Σ (w (xI,)) yK,)) The formulation FIDEM makes it impossible for an adversary to apply gradient inversion attack and obtain private training data of clients (Zhu et al., 2019). In partieular, the attacker cannot find the vanilla (stochastic) gradients and reconstructs data
unless the attacker has a perfect knowledge of the ratio F% (x) = Σ pl (x)((((//)/)))) (x)x///[(x)
Privacy. Given (rx()) FIDEM efficiently minimizes the overall test error over all clients in privacy- manner. To estimate those ratios, if clients can tolerate some level of privacy
"The analyses of computationallcommnnittooo overheads are provided in Appendices P and E, respectively.
4

---

Under review as a conference paper at ICLR 2023
leakage, clients send unlabelled samples x for I [K] and [n=*] from their test distributions. To control privacy leakage to other clients, we propose that the server randomly shuffles these unlabelled samples before broadcasting to clients. In Appendix Q, we discuss alternative method instead of sending original unlabelled samples and discuss its limitations.
To fully eliminate any privacy risks compared to classical ERM, clients may opt minimize the following surrogate objective, which we name Federated Independent Importance-weightee) Empirical risk Minimization (FIIDEM):
(x R. Elhw (...).
min F (w) w
(FIIDEM)
(x
The formulation FIIDEM preserves the same level of privacy and same communication costs as those of classical ERM, e.g., FedAvg. However, to exploit the entire data distributed among all clients and achieve the optimal global model in terms of overall test error, clients need to compromise some level of privacy and share unlabelled test samples with the server. Hence, in this paper, we focus on the original objective in FIDEM.
3 RATIO ESTIMATION FOR FL UNDER COVARIATE SHIFT
To solve FIDEM, client & should have access to an accurate estimate of this ratio
E/= (x)
Tx (x)
(3.1)
(x)
Ratio estimation is a key step for importance weighting (Sugiyama et al., 2007: 2012). The discrep- ancy between the true ratio r for client in Eq. (3.1) and the estimated one rı using our ratio model T (x)) where the Bregman divergence (BD) associated with
can be measured by p [D, ( a strictly convex f leads to BD-based DRMs (Kato & Teshima, 2021; Kiryo et al., 2017):
Definition (Bregman 1967). Let B C [0, oo) and f B, - be a strictly convex function with bounded gradient. The BD associated with f from ā to z is given by BD 2) = f(ž) f(z) ff(z) 2)).
Note that BD, || 2)) is convex function w.r.t. ē; however, it is not necessarily convex w.r..
Motivated by Kato Teshima (2021); Kiryo et al. (2017), we propose a new histogram- DRM (HDRM) for FL with multiple clients. HDRM overcomes the over-fitting issue (Kiryo al., 2017; Kato & Teshima, 2021) while providing an estimate for the upper bound T% = supx r (x), which is key step for non-negative BD (nnBD) DRM. We now extend nnBD DRM to FL settings.
3.1 EXTENSION OF NNBD DRM TO FL
We assume that Pk common data domain with strictly positive train density, which is a common assumption (Kanamori et al., 2009; Kato & Teshima, 2021). Let H, C (r: X' + B denote hypothesis class for our ratios rks e.g., neural networks with a given architecture. Our goal to estimate T by minimizing the discrepancy p [BD,(r
tr (x"*) > 0 for & E [K] and all x"* E L C X' with X C A i.e., we need a
Th (x)),, which leads to BD-based DRM for FL. and is formulated in Int
n and [x({]]" denote unlabelled samples drawn i.i.d from distributions pk and pp", respectively, for E [K]. Standard BD-based DRM is shown to suffer from an over- wet-ifiting
Appendix D.2. Let (xt,)
issue where - - mn Vf(r (xt;)) diverges if there is no lower bound on this term (Kiryo et al., 2017; Kato & Teshima, 2021). To resolve this issue in FL, we consider non-negative BD (nnBD) DRM for client k. i.e., min,,eH. & (rx) where
Ck nle
nt K
(rs) ReLU
& (1(x(xx
n1 ΣΣ (((x((x)))) +
ΣΣ 1250
(r(xx(x)))). (3.2)
1=1
1=1
ReLU(z) = max(0, 2), 0 < C < F Tk = supxexu (x)), (x) = vf(z)) - f(z), and
(2(=) = C(V](=)) (()]))))=(())))-->)))))))))))>)) -/()) Intuitively, ReL. is used for non-negativity and 0 Ct < #
5

---

Under review as a conference paper at ICLR 2023
acts regularization parameter. Substituting different f's into Eq. (3.2) leads different variants of nnBD, which covers previous work (Basu et al., 1998; Hastie et al., 2001; Gretton et al., 2009; Nguyen al., 2010; Kato et al., 2019). We provide explicit expressions of those variants for client k in Appendix H. In this work, we focus on f(z) (=-1)² leading to the well-known least-squares importance fitting (LSIF) variant of nnBD for client k.
3.2 ESTIMATION OF THE UPPER BOUND Fk
Estimating F1: = x r (x) is a key step for nnBD DRM. For single train and test distribution, shown that overestimating 7 leads to significant performance degradation (Kato Teshima, 2021, Section 5). Kato & Teshima (2021) considered C as hyper-parameter, which can be tuned. However, obtaining am efficient estimate of F is desirable, in particular when training a deep model. Here propose a histogram based method for estimation of Tk.
Let B C. X and assume p and pi are continuous for E [K]. Since is connected and Lebesgue-mease measurable with finite measure, by applying intermediate value theorem (Russ, 1980), there exist x and x such that Pr[ E B} pk Vol(B) and Σ Pr[X E B}
ΣE P1 (x**) where Vol(B) = SxeB dx. We note that supxes (x) S sup.cB Σ (x) and ΣK (1 (1()")
intxes PT
S SuPxEB El (x)(x) To estimate Tk we first partition X into M bins where P
for each bin Bm. if there exists some x E Bmd then we define Fk.m ΣK PB
Pr(
ato In El=, (BB) for m E [M]. Otherwise, Pr.m = O. Finally, we propose to use C₁
2.'4 1(x) EBm)
"
where ix max F. Convergence of i4 to Fx is established in Appendix G. Furthermore, for high-dimensional data, efficient implementation of HDRM using k-means clustering is provided in Appendix G.
Fk
In HDRM, K clients estimate their ratios in parallel. To be specific, clients first share unlabelled test samples with the server. The server returns the randomly shuffled pool of samples to all clients. Then clients find Cx 's in parallel. Given C 's, clients estimate their corresponding ratios in parallel. To handle high-dimensional data samples and deep ratio estimation models, we adopt a variant of SGD.
1a for E [K] into Ng batches For client k we divide unlabelled samples {xE,)) and {x(g))=1 B
[mnjj=== for E [Na]. Client k first computes Bur (x and {xte
Btt
B (1T6(x))
Σja E (1(x(xtt,,))) If it becomes negative, then we apply gradient ascent step to increase this term We may also opt to apply 1-norm 2-norm regularizations. The details of the HDRM algorithm are shown in Algorithm I in Appendix A.
KCC B
4 THEORETICAL GUARANTEES
To address learning on multiple clients in FL, it is essential to obtain per-client generalization bounds for general nnBD DRM with imperfect estimates 7f Even if we have access perfect estimates of density ratios, it is still unclear the usefulness of importance weighting. In this section, we firstly study the bigh-brobability generalization guarantees of nnBD DRM under imperfect estimate of 7x in terms of BD risk. We then show the benefit of importance weighting in term of excess risk through a refined hias-variance decomposition on ridge regression problem. Theorem 1, Lemma 1, Theorem are proved in Appendix I, Appendix L,, and Appendix M, respectively.
4.1 GENERALIZATION ERROR IN TERMS OF BD RISK
We establish a high-prohee bigh-probability bound on the generalization error of nnBD DRM with an arbitrary f for client & in terms of BD risk given by
(rw) = (x(x)]((((xxx)) + Σ Epp- (x)))
(4.1)

---

Under review as a conference paper at ICLR 2023
i-= where E5 Epp Cs Ei=1 Byge. Our bound for client i depends the Rademacher com-
plexity (Shalev-Shwartz & Ben-David, 2014) of the hypothesis class for our density ratio model H, C fr :x + ] w.r.t client k train distribution pk and all client's test distributions pf" for
I e [K]. Let R (H) denotes the Rademacher complexity of function class H. w.r.t distribution p.
formally defined in Appendix A. We first make the following assumptions on (2) = Vf(=)== - f())
and (2(2) = C(Vf(z)2 f(2)) vf(=).
Assumption 1 (Basic assumptions & and (2). We assume 1) suPzEB, (1 [k1(z)] oc; 2) l is Li-Liscchizz and &g is Ly-Lipschitz on X:; 3) infreN, [x(e((rx(x))] > 0 for k E [K].
The first two assumptions are satisfied if [=|= E B > 0 for commonly used loss functions, c.g., unnormalized Kullback- Leibler and logistic regression. The third assumption is mild, commonly used in DRM literature (Kiryo et al., 2017; Lu et al., 2020; Kato & Teshima, 2021).
Theorem 1 (Generalization error bound for client k). Let f be a strictly convex function with bounded gradient. Denote De == supseB, max [=]],,, f& == arg min, EJ (rx) and r := arg minm.en (T(r where E and E are defined in Eqs. (3.2) and (4.1), respectively. Suppose that 1 and &g satisfy Assumption 1, then for any 0 8 < 1, with probability at least 8:
Ef(F - Ex(r S (H.) + C Σ
R my
1ot (H.) + r llg z KKx,,,epp
(4.2)
where T r= A2(1// C2K/n'))
Remark 1. Theorem 1 provides generalization guarantees for a general nnBD DRM in a federated setting under a strictly convex f with bounded gradient. We make the following remarks.
1) Our results are general to cover various ratio models. For example, in Corollary 1 of Appendix J, we consider neural networks with depth L and bounded Frobenius norm || I Aw, and tr establish explicit generalization error bounds for client & in OVT Aw, (1/v " + K/Vn'))
/ T log + &C exp (7)).
2) If the additional error due to estimation of Fs with HDRM in Section 3 using M bins is considered, leads to (
M under mild assumptions. Refer to Appendix K for details.
3) Our error bound increases with K due to the structure of BD risk. Note that K is in a constant order. Our goal is to show that nnBD DRM is guaranteed to generalize in a general federated setting.
4.2 EXCESS RISK AND BENEFIT OF FIDEM
In this section, we aim to demonstrate the benefit of importance weighting in term of excess risk through biri-variance decomposition. We consider the classical least squares problem, good starting point to understand the superiority of FIDEM over ERM with generalization guarantees. We consider the single client setting K 1 for the ease of description, and our results can be extended to the multiple clients setting.
Let (x, y) denote the (test) data sampled from unknown probability measure p. The least squares problem is to estimate the true parameter 0., which assumed to be the unique solution that minimizes the population risk in Hilbert space H: L(O.) = minøen L(O) where L( 2 |E(x,))<I(y - 0 x))?. Moreover, we have L(0.) = a² corresponding to the noise level. For an estimate θ found by learning algorithm such ridge regression, its performance is measured by the expected excess risk, (() I(OO). where the expectation over the random noise, randomness of the algorithm, and training data. In the following, we consider two settings: random-design setting and fixed-design settings where the training data matrix is random and given, respectively.
Bias variance decomposition. We need the following noise assumption for our proof.
Assumption 2 (Dhillon et al. 2013; Zou et al. 2021, bounded variance). Let := y 0._ x. We assume that E[c] = 0 and E[e?| = o.
We have the following lemma on the bias-variance decomposition of the ridge regression FIDEM estimate in the random-design setting.
7

---

Under review as a conference paper at ICLR 2023
Lemma 1. Let X Raxd be the training data matrix. Let W diag(wi; "...., W,) with wi pd (xi)/p" (x:) for i [n]. 0 be the regularized least square estimate with importance weighting: = arg ming Ei= wi(O x; y1)² + 2|10| where is the regularization parameter. Denote O. be the Irue extimate, then the excess risk can be decomposed as the bias B and the variance V: [[) - ((0)) = +B+ V, with
B = A O. w. S.
V:=o²BB tr [ (W W W.X
where Σw == X WX+XL XL, and E = Ex(xxx] Note that the expectation is taken over the randomness of the training data matrix X and label noise.
Remark 2. Our results in Lemma 1 hold under the fixed-design setting where the training data are given (Dhillon et al., 2013; Hsu et al., 2012), by omitting the expectations from and V.
One-hot case. To theoretically prove that FIDEM outperforms ERM in non-trivial settings, we start from the one-hot case, along the lines of Zou al. (2021), and strictly show that, under which level of covariate shift, the excess risk of FIDEM is always smaller than the classical ERM.
To be specific, in the one-hot case, every training data x is sampled from the set of natural basis fer, C2 ................................ ) according to the data distribution given by Pr(x e.} = X where ( < X; S 1 and E, 2 1. The class one-hot least square instances is characterized by the following problem set: (0.;; AI...., Aa): 0. E H. E = 1} It is not difficult to show that the population second momentum matrix E E x ] = diag (i..... .h....,Ad, Ag) for E [n]. Similarly, we assume that each test data follows the scheme but with different probabilities Pr(x e: XT. and hence, have t =
(,)....,))).. This is a relatively simple setting, which admits covariate shift. Take {11, (22, ( as the eigenvalues of X X. Since x; can only take on natural basis, the eigenvalue 14 be understood the number of training data that equals e;- For notational simplicity, rearrange the order of the training data following the decreasing order of the ratio, such that the i-th sample x, corresponds to the ratio w, as the exact i-th largest value.
X_ Under the Theorem 2. Let Ô be the estimate of FIDEM, O" be the classical ERM, and & == Xtp fixed-design setting in the one-hot case, label noise assumption, and data correlation assumption, if the ratio w; := (xx(x))))))))))))) (x,) satisfies
A
1 ux E1
(4.3)
X
then have R(O) & R(O").
Remark We have the following remarks:
1) The condition (4.3) is equivalent to / E (0, ( + which requires the training and test data to behave similarly in terms of eigenvalues, avoiding significant differences under distribution shifts for learnability. Other metrics, e.g., similarity on eigenvectors (Tripuraneni et al., 2021) also coincide with the spirit of our assumption.
2) The ratio matrix is W E R=x", However, we only need its top d eigenvalue, i.e., the top-d ratios. In particular, the last n d ratios have no effect on the final excess risk. This makes our algorithm robust to noise and domain shift.
3) For the special case by taking the ratio as w;
we have
X
[0.),,33
10.),122
B(O) X2
X
[m:0 + xj²
2
which implies that the ratio can be regarded as implicit regularization (Zou al., 2021).
5 EXPERIMENTAL EVALUATION
In this section we illustrate conditions under which FIDEM is favored over both Federated Averaging without ratio estimation (FedAvg) (McMahan al., 2017) and FIIDEM. In all experiments, use LeNet (LeCun et al., 1989) with cross entropy loss and compute standard deviations over independent executions. Due to the page limit, the implementation details are in Appendix O.
8

---

Under review as a conference paper at ICLR 2023
Table 1: Fashion MNIST with label shift across two clients, where each client receives different fractions of examples from each class. In this case, FIDEM achieves a better average accuracy than the baselines.
FIDEM
FIIDEM
FedAvg
Average accuracy
0,8245 = 0.0111
0.7942 + 0.0096
0.5475 + 0.0093
Client I accuracy
0.8627 + 0.0175
0.8336 + 0.0066
0.3978 + 0.0215
Client 2 accuracy
0.9308 + 0.0057
0.8896 + 0.0124
0.9143 + 0.0048
Client 3 accuracy
0.7742 + 0.0618
0.7275 + 0.0261
0.3677 + 0.0297
Client 4 accuracy
0.7933 + 0.0598
0.8204 + 0.0152
0.6566 + 0.0447
Client 5 "accuracy
0.7616 = 0.0593
0.6998 + 0.0649
0,4009 + 0.0642
Table 2: A challenging binary classification task on Colored MNIST with covariate shift across two clients. FIDEM is close the idealised haseline that ignores the spurious correlation (Grayscale).
Upper Bound (Grayscale)
FIDEM
FLIDEM
FedAvg
Average accuracy
0.68 + 0.01
0.66 + 0.01
0.63 + 0.00
0.58 + 0.01
Target shift. We consider the case of target shift where the label distribution p(v) changes but the conditional distribution p( p(xly) remains invariant. We split the 10-class Fashion MNIST dataset between 5 clients and simulate a target shift by including different fractions of examples from each class across the training data and test data. We further consider the separable case in order to compute the exact ratio for FIDEM and FIIDEM in closed form. The specific distribution and the construction of the ratio can be found in Appendix O.1. The results in Table 1 illustrate that FIIDMM can outperform FedAvg on average while preserving the same level of privacy. By relaxing the privacy slightly the proposed FIDEM improves on FedAvg uniformly across all clients. Even though the proportions of the classes have been artificially created, believe that this demonstrates realistic scenario where clients have different fraction of samples per class. Additional experiments using larger models on the CIFARIO dataset under a challenging target shift setting can be found in Appendix 0.1 where FIDEM is observed to improve uniformly over FedAvg.
Covariate shift. We now focus covariate shift, where p(x) undergoes shift while p(y[x)
remains unchanged. For this setting, we extend the Colored MNIST dataset in Arjovsky et al. (2019) to the multi-client setting. The dataset is constructed by first assigning binary label to digits from 0-4 and label for digits between 5-9. The label is then flipped with probability 0.25 to make the dataset separabae. A spurious correlation is introduced by coloring the digits according their assigned labels and then flipping the colors according to a different probability for each distribution (see Appendix O.2). For this experimental setup, we introduce an idealized scheme, which ignores the color and thus the spurious correlation. i.c., provides an upper bound, and is referred to as Grayscale. FIDEM outperforms both baselines terms of the average accuracy even two-client setting. FIDEM is also close to Grayscale upper bound that by construction ignores the spurious correlations.
CONCLUSIONS AND FUTURE WORK
In this work, we focus on FL under both intra-client and inter-client distribution shifts and propose FIDEM to improve the overall generalization performance. We establish high-probability general- ization guarantees for a general DRM method in federated setting. We further show the benefit of importance weighting in term of excess risk through varsinar decomposition in a ridge regression problem. Our theoretical guarantees indicate how FIDEM can provably solve a learning task under distribution shifts. We experimentally evaluate FIDEM under both label shift and covariate shift cases. Our experimental results validate that under certain covariate and target shifts, the proposed method can learn the task, while baselines such as vanilla federated averaging fails to do so. We anticipate that our methods to be applicable in learning from e.g., medical data, where there might be arbitrary skews on the distribution. In addition, we believe our study can further encourage the investigation of distribution shifts in FL., this is critical subject for learning across clients.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ben Adlam and Jeffrey Pennington. Understanding double descent requires a fine-grained bias-
variance decomposition. Advances Neural Information Processing Systems, 33, 2020.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2017.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprini urXiv:197.0028:0 2019.
Kamyar Azizzadenesheli. Importance weight estimation and generalization in domain adaptation under label shift. IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), 44 (10):6578-658) 2022.
Mahsa Baktashmotlagh, Mehrtash T Harandi, Brian C Lovell, and Mathieu Salzmann. Domain adaptation on the statistical manifold. In Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2481-2488 2014.
Peter L Bartlett.
The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions on Information Theory, 44(2):525-336 1998.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research (JMLR), 3(Nov.):463-482, 2002.
Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Annals of Statistics, 199--377977 2005.
Ayanendranath Basu, Ian R Harris, Nils L Hjort, and MC Jones. Robust and efficient estimation by minimising a density power divergence. Biometrika, 85(3):549-555 1998.
Steffen Bickel and Tobias Scheffer. Dirichlet-enhanced spam filtering based on biased samples. In Advances in Neural Information Processing Systems (NeurIPS), 2007.
Konstantinos Bousmalis, Nathan Silberman, David Dohan, Dumitru Erhan, and Dilip Krishnan. Unsupervised pixel-level domain adaptation with generative adversarial networks. Conference Computer Vision and Pattern Recognition (CVPR), pp. 3722-3731, 2017.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research (JMLR), 2:499-526, 020999556,444 2002.
Lev M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-2177 1967.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. LEAF: A benchmark for federated settings. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Kuang Fu Cheng and Chih-Kang Chu. Semiparametric density estimation under a two-sample density ratio model. Bernoulli, 10(4):583-604, 2004.
Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty, Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation. pp. 447-463, 2018.
Debasmit Das and CS George Lec. Unsupervised domain adaptation using regularized hyper-graph matching. In 2018 25th IEEE International Conference on Image Processing (ICIP), pp. 3758- 3762. IEEE, 2018.
Paramveer S. Dhillon, Dean P. Foster, Sham M. Kakade, and Lyle H. Ungar. A risk comparison of ordinary least squares vs ridge regression. Journal of Machine Learning Research, 14(1): 1505-1511, 2013.
10

---

Under review as a conference paper at ICLR 2023
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger conver- gence rates for least-squares regression. Journal of Machine Learning Research, 18(1):3520-3570, 2017.
lian-Hui Duan, Wenzhong Li, and Sanglu Lu. FedDNA: Federated learning with decoupled normalization-layer aggregation for non-llD data. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, 2021.
Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. In Advances in Neural Information Processing Systems (NeurlPS), 2020.
Yaroslav Ganin, Bvgeniya Ustinova, Hana Ajakan, Paseal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Dowaii-adversarial training of neural networks. The journal of machine learning research, 17(1):209-2030, 2016.
Elnur Gasanov, Ahmed Khaled, Samuel Horváth, and Peter Richtárik. FLII: A simple and communication-efficin alternative to local methods in federated learning, In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma. Neural computation, 4(1):1-58, 1992.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Conference On Learning Theory, pp. 297-299, 2018.
Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11):139 2020.
Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Covariate shift by kernel mean matching. Dataset shift in machine learning, 3(4):5, 2009.
Hirotaka Hachiya, Masashi Sugiyama, and Naonori Ueda. Importance-weightee least- probabilistic classifier for covariate shift adaptation with application to human activity recognition. Neurocomputing, 80:93-101, 2012.
Boris Hanin and David Rolnick. Deep ReLU networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik. Lower bounds and optimal algorithms for personalized federated learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference and prediction. Springer, 2001.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Shohei Hido, Yuta Tsuboi, Hisashi Kashima, Masashi Sugiyama, and Takafumi Kanamori. Statistical outlier detection using direct density ratio estimation. Knowledge and Information Systems, 26(2): 309-336, 2011.
Daniel Hsu, Sham M. Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference on Learning Theory, 2012.
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. Correcting sample selection bias by unlabeled data. In Advances in Neural Information Processing Systems (NeurIPS), 2006.
11

---

Under review as a conference paper at ICLR 2023
Prateck Jain, Sham Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: niti-batching, averaging, and model misspecification. Journal of Machine Learning Research, 18, 2018.
Jing Jiang and ChengXiang Zhai. Instance weighting for domain adaptation in nlp. Proceedings of the 45th annual meeting of the association of computational linguistics, pp. 264-271, 2007.
Suwicha Jirayucharoensak, Setha Pan-Ngum, and Pasin Israsena. EEG-based emotion recognition using deep learning network with principal component based covariate shift adaptation. The Scientific World Journal, 2014, 2014.
Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. D'Oliveira, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchin- son, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Liu, P., M. Mohri, R. Nock, A. Özgür, R. Pagh, M. Raykova, H. Qi, D. Ra- mage, R. Raskar, D. Song, W. Song, S. U. Stich, 7. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao. Advances and open problems in federated learning. Foundations and Trends R0 in Machine Learning, 14(1-2):1-210, 2021.
Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama. A least-squares approach to direct importance estimation. Journal of Machine Learning Research, 10:1391-1445, 2009.
Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama. f-divergence estimation and two-sample homogeneity test under semiparametric density-rabee rrato models. IEEE Transactions on Information Theory, 58(2):708-724 2011.
Masahiro Kato and Takeshi Teshima. Non-negative Bregman divergence minimization for deep direct density ratio estimation. In International Conference Machine Learning (ICMI., 2021.
Masahiro Kato, Takeshi Teshima, and Junya Honda. Learning from positive and unlabeled data with selection bias. In International Conference on Learning Representations (ICLR), 2019.
Yoshinobu Kawahara and Masashi Sugiyama. Change-point detection time-series data by direct density-ratio estimation. In Proceedings of the SIAM international conference on data mining, 2009.
Amor Keziou and Samuela Leoni-Aubin. Test of homogeneity semiparametric two-sample density ratio models. Comptes Rendus Mathématique, 340(12):905-910 2005.
Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient- meta-learning methods. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Ryuichi Kiryo, Gang Niu, Marthinus C. du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. WILDS: A benchmark in-the-wild distribution shifts. In International Conference on Machine Learning (ICML), 2021.
Wouter M Kouw and Marco Loog. A review of domain adaptation without target labels. IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), 43(3):766-785, 2019.
A. Krizhevsky, Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009,
Yann LeCun, Bernhard Boser, John S. Denker, Donnie Henderson, Richard E. Howard, Wayne Hubbard, and Lawrence D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, 1(4):541-551, 1989.
12

---

Under review as a conference paper at ICLR 2023
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, al. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-235 23244, 1998.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes, volume 23, Springer Science & Business Media, 1991.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37:50-60, 2020.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. In International Conference on Learning Representations (ICLR), 2021a.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated
learning through personalization. In International Conference on Machine Learning (ICML), 2021b.
Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. FedBN: Federated learning on non-IID features via local batch normalization. In International Conference on Learning Representations (ICLR), 2021c
Yan Li, Hiroyuki Kambara, Yasuharu Koike, and Masashi Sugiyama. Application of covariate shift adaptation techniques in train-computer interfaces. IEEE Transactions on Biomedical Engineering, 1316))1118-1324 2010.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting, IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), 38(3):447-461, 2015.
Stuart Lloyd. Least squares quantization PCM. IEEE Transactions on Information Theory, 28(2): 129- 1982.
Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction approach. In International Conference on Artificial Intelligence and Statisties (AISTATS), 2020.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning, arXiv preprint 2001:20002.1069, 2020.
David A McAllester. Some pac-bayesian theorems. Machine Learning, 37(3):355-363 1999.
Colin McDiarmid et al. On the method of bounded differences. Surveys combinatorics, 141(1): 148-188, 1989.
H. B. McMahan, Moore, D. Ramage, S. Hampson, and B. A. Arcas. Communication--ffiiieeee learning of deep networks from decentralized data. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- lional Conference on Machine Learning, pp. 4615-4625. PMLR, 2019.
Arkadi Nemirovski. Topics in Non-parametric Statistics. Ecole d'Eíe de Probabilifes de Saint-Flou XXVIII, 1998.
XuanLong Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56 56(11):5847-5811 2010.
Jing Qin. Inferences for case-control and semiparametric two-sample density ratio models. Biometrika, 85(3):619-630, 1998.
Sashank Reddi, Barnabas Péczos, and Alex Smola. Doubly robust covariate shift correction. In AAAI Conference on Artificial Intelligence, 2015.
SB Russ. A translation of Bolzano's paper on the intermediate value theorem. Historia Mathematica, 7(2): 15- 1980.
13

---

Under review as a conference paper at ICLR 2023
Shai Chalev-Swwarde and Shai Ben-Davie Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Shai Shalev- Shaltv-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research (JMLR), 11:2635-2670, 2010.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of Statistical Planning and Inference, 90(2):227-244, 2000.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S. Talwalkar. Federated multi-task learning. Advances in Neural Information Processing Systems (NeurIPS), 2017.
Alex Smola, Le Song, and Choon Hui Teo. Relative novelty detection. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2009.
Masashi Sugiyama and Klaus-Robert Müller. nependee estimation of generalization error under covariate shift. Statistics & Decisions, 2005.
Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert Müller. Covariate shift adaptation by
importance weighted cross validation. Journal of Machine Learning Research, 8(5), 2007.
Masashi Sugiyama, Taiji Suzuki, Yuta Itoh, Takafumi Kanamori, and Manabu Kimura. Least-squares two-sample test. Neural networks, 24(7):735-751, 2011.
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density- matching under the Bregman divergence: a unified framework of density-ratio estimation. Annals of the Institute of Statistical Mathematics, 64(5): 100911400,
2012. 2012
Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Overparamettrizaation improves robustness to covariate shift in high dimensions. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Alexandre Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statisties, 2008.
Masatoshi Uchara, Masahiro Kato, and Shota Yasui. Off-policy evaluation and learning for external validity under a covariate shift. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Vladimir N Vapnik. An overview of statistical learning theory. IEEE Transactions Neural Networks and Learming Systems (T-NN), 10(5):988-999, 1999.
Jianyu Wang, Zachary Charles. Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Aguera y Arcas, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data. Suhas Diggavi, Hubert Eichner, Advait Gadhikar, Zachary Garrett, Antonious M. Girgis, Filip Hanzely, Andrew Hard, Chaoyang He, Samuel Horvath, Zhouyuan Huo, Alex Ingerman, Martin Jaggi, Tara Javidi, Peter Kairouz, Satyen Kale, Sai Praneeth Karimireddy, Jakub Konecny, Sanmi Koyejo, Tian Li, Luyang Liu, Mehryar Mohri, Hang Qi. Sashank Reddi, Peter Richtarík. Karan Singhal, Virginia Smith, Mahdi Soltanolkotabi. Weikang Song, Ananda Theertha Suresh, Sebastian U. Stich, Ameet Talwalkar, Hongyi Wang, Blake Woodworth, Shanshan Wu, Felix X. Yu, Honglin Yuan, Manzil Zaheer, Mi Zhang, Tong Zhang, Chunxiang Zheng, Chen Zhu, and Wennan Zhu. A field guide to federated optimization. arXiv preprini arXiv: 107.:2207.00611 2021.
Mei Wang and Weihong Deng. Deep visual domain adaptation: A survey. Neurocomputing, 312: 135-153, 2018.
Larry Wasserman. All of nonparametric statistics. Springer Science & Business Media, 2006.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.0774: 2017.
Semih Yagli, Alex Dytso, and H Vincent Poor. ietommttion-heorettie bounds the generalization error and privacy leakage federated learning. In International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), 2020.
14

---

Under review as a conference paper at ICLR 2023
Makoto Yamada, Masashi Sugiyama, and Tomoko Matsui. Semi-supervised speaker identification under covariate shift. Signal Processing, 90(8):2353-2366 2010.
Makoto Yamada, Taiji Suzuki, Takafumi Kanamori, Hirotaka Hachiya, and Masashi Sugiyama. Relative density-ratio estimation for robust distribution comparison. In Advances in Neural Information Processing Systems (NeurIPS), 2011.
Honglin Yuan, Warren Morningstar, Lin Ning. and Karan Singhal. What do we mean by generalization in federated learning? arXiv preprint arXiv:2110. 14216, 2021.
Bianca Zadrozny. Learning and evaluating classifiers under sample selection bias. In International Conference Machine Learning (ICML), 2004.
Tianyi Zhang, Ikko Yamane, Nan Lu, and Masashi Sugiyama. A one-step approach covariate shift adaptation. In Asian Conference on Machine Learning. 2020.
Aurick Zhou and Sergey Levine. Training on test data with bayesian adaptation for covariate shift. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems (NeurlPS), 2019.
Difan Zou, Jingfeng Wu, Quanquan Gu, Dean P Foster, Sham Kakade, al. The benefits of implicit regularization from SGD in least squares problems. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
A CONTENT OF THE APPENDIX
Notation: We use B[-] to denote the expectation and || to represent the Euclidean norm of a vector. We use lower-case bold font to denote vectors. Sets and scalars are represented by calligraphic and standard fonts, respectively. We use [n] to denote (I.".,,)) for an integer We use S to ignore terms up to constants and logarithmic factors.
The appendix is organized follows:
Definition of Rademacher complexity, examples of f for BD-based DRM, and the steps of HDRM in Algorithm are provided in Appendix A.
Complete related work is provided in Appendix B.
FIDEM with focus minmizing R₁ are provided in Appendix C.
Details of density ratio estimation are provided in Appendix D.
Communication costs of FIDEM and FIDDEM are analyzed in Appendix E.
UKL,, LR, and variants of nnBD are provided Appendix
Convergence of 5 and k-means clustering for HDRM are provided in Appendix
UKL, LR, and PU variants of nnBD for multiple clients provided in Appendix H.
The proof of the core Theorem exists in Appendix I.
Generalization bounds for multi-layer perceptron and multiple clients are established in Ap- pendix
Additional error due estimation of with HDRM is analyzed in Appendix K.
Lemma is proved in Appendix L.
Theorem 2 is proved in Appendix M.
A counterexample under which FIDEM cannot outperform ERM is provided in Appendix N.
Additional experimental details are included in Appendix O.
Computational complexity of Algorithm is analyzed in Appendix
The limitations of our work described in Appendix Q
15

---

Under review as a conference paper at ICLR 2023
Table Examples of for BD-based methods (Sugiyama al.. 2012: Kato & Teshima, 2021). LSIF least-squares importance fitting, LR logistic regression, BKL binary Kullback Leibler. UKL unnormalized Kullback- Leibler, KLIEP Kullback- Leibler importance estimation procedure, KMM kernel mean matching LosL positive and unlaheled learning with log Loss.
Reference
Algorithm
f(z)
Basu et al. (1998)
Robust
za-l-z
0
0
Hastie et al. (2001)
LR (BKL)
log(z) - (2+ log(z + +1
Kanamori et al. (2009)
LSIF
(2-1)²
2
Gretton et al. (2009)
KMM
(3-1)²
2
Nguyen et al. (2010)
KLIEP
log(2)) 2
Nguyen et al. (2010)
UKL
z =log(z)= -
Kato et al. (2019)
PULogLoss
Cllo((1 2) Cz(log(=) log(1 =)), =E (0,1),
Input: Samples (fx), fi k=1- {(x]] 1-=1 1=11 learning rate a, regularization A(r) and
regularization coefficient A.
Output: Ratio model parameters {0r, J
for k = to K (in parallel) do
Send n² samples to the server;
Server randomly shuffles and broadcasts samples {(x).) In 1/ clients; j=1
for ic 1 to K (in parallel) do
Create M bins and compute Fk.m 1/n" E; Ei EBm))
1/n E EB,,)
Estimate C2
max FF,, 3
for do
for k = 1 to K (in parallel) do
for n to Ng do
if
BY Ei=l Bt
(rx (m,,)))
KC B
Σj= e (r
2 then
Br
gk = Vo. B Σt
l (rx k,m,,))
KC
Ee= e (1x(( +
By
K Σ b (2( (x ( )) A(T)))
else
B & (x kn),))) - KC2 B 2 E (Fa((x), + + A(x))
Bk = Vo.
B
14
Update ratio model parameters 6r, = 0r, + ags;
Algorithm 1: Histogram- bassed density ratio matching. Loops executed in parallel on each client.
Definition 2. Let Σ4 and be distribution. S = (xi,... Xn) } be i.i.d. random variables drawn from p. and be a function class. The Rademacher complexity of w.r.. p is given by:
Rº
EsE,
sup rEh
Σ 0 i=1
where {o are Rademacher variables uniformly chosen.from { 1,,1
B RELATED WORK
Federated learning. One well-known method in FL is FedAvg (McMahan et al., 2017). FedAvg and its variants are extensively studied in optimization with a focus on communication efficiency and partial participation of clients while preserving privacy.
16

---

Under review as a conference paper at ICLR 2023
Indeed, host of techniques, such gradient quantization, sparsification, and local updating rules, have been proposed to improve communication efficiency in FL (Alistarh et al., 2017). Furthermore, robust and secure aggregation schemes have been also proposed to provide robustness against training- time attacks launched by an adversary, and to compute aggregated values without being able to inspect the clients' local models and data, respectively (Li et al., 2020; Kairouz al., 2021; Wang et al., 2021).
Taken together, these work largely focus on minimizing the empirical risk in the optimization objectíve, under the same training/test data distribution assumption over each client. Differences across clients are handled using personalization methods based on heuristics and currently do not have a statistical learning theoretical support (Smith et al., 2017; Khodak et al., 2019; Li et al., 2021b).
In contrast, we focus on learning and overall generalization performance under both intra-client and inter-client distribution shifts. communication-effiiiee robust, and secure aggregations can be viewed as complementary technologies, which can be used along with our proposed FIDEM method to improve the generalization performance. In our setting, clients can also all participate in every training iteration, such as cross-silo FL.
We note that (Hanzely et al., 2020; Gasanov et al., 2022) focus on minimizing the empirical risk, under the same training/test data distribution assumption over each client. Our formulation in FIDEM does not require specific assumptions on function F&'s 's for k E [K] to provide an unbiased estimate of true risk minimizer. Under strong convexity and smoothness assumptions w.r.. model parameters, similar optimal algorithms to those proposed in (Hanzely et al., 2020; Gasanov al., 2022) will be optimal for FIDEM.
Different from recent FL work by Duan al. (2021) and Li et al. (2021c), our work introduces new FIDEM formulation and shows statistical consistency.
Importance-weighted ERM and density ratio matching. Density ratio estimation is an important step in various machine learning problems such as learning under covariate shift, learning under noisy labels, anomaly detection, two-sample testing, causal inference, change-pint detection, and classification from positive and unlabelled data (Qin, 1998; Shimodaira, 2000; Cheng & Chu, 2004; Keziou & Leoni-Aubin 2005; Sugiyama et al., 2007; Kawahara & Sugiyama, 2009; Smola et al., 2009; Hido al., 2011; Kanamori al., 201 1: Sugiyama et al., 2011: Yamada al., 2011; Reddi et al., 2015; Liu & Tao, 2015; Kato et al., 2019; Fang et al., 2020; Uehara et al., 2020; Zhang et al., 2020; Kato & Teshima, 2021). In particular, covariate shift has been observed in real-world applications including brain-computer interfacing, emotion recognition, human activity recognition, spam filtering, and speaker identification (Bickel & Scheffer, 2007: Li et al., 2010; Yamada et al., 2010; Hachiya et al., 2012; Jirayucharoensak et al., 2014). Shimodaira (2000) introduced covariate shift where the input train and test distributions are different while the conditional distribution the output variable given the input variable remains unchanged. Importance weighted ERM is widely used to improve generalization performance under covariate shift (Zadrozny. 2004; Sugiyama & Müller, 2005; Huang al., 2006; Sugiyama et al., 2007; Kanamori et al., 2009; Sugiyama et al., 2012; Fang et al., 2020; Zhang et al., 2020; Kato & Teshima, 2021). Zhang et al. (2020) proposed one-step approach that jointly learns the predictive model and the corresponding weights in one optimization problem. Sugiyama et al. (2012) proposed a Bregman divergence-basee DRM, which unifies various DRMs. Kato & Teshima (2021) proposed a non-negative Bregman divergence-basee DRM to resolve the overfitting issue when using deep neural networks for density ratio estimation. While this line of work focuses on DRM with a single train and test distributions, we consider a federated setting with multiple clients in this paper.
Domain adaptation. Distribution shifts between a source and a target domain have been promi- nent problem in machine learning for several decades (Kouw Loog, 2019; Wang & Deng. 2018). The premise behind such shifts is that data is frequently biased, and this results in distribution shifts that can be estimated by assuming some (unlabelled) knowledge of the target distribution. The following two categories of domain adaptation methods are most closely related to our work: a) sample-basse and b) feature- based methods. In feature-based methods, the goal is to find a transformation that maps the source samples to target samples (Ganin et al.. 2016; Bousmalis et al., 2017: Das & Lee, 2018: Damodaran et al., 2018). Contrary to feature-based methods, sample-based methods aim at minimizing the target risk through data in the source domain. Importance weighting
17

---

Under review as a conference paper at ICLR 2023
Table 4: Details of scenarios described in Section 2.
Scenario
#Clients
Assumptions on Distributions
What client Knows
No-CS in (C.1)
pi = (x), (x)
* pi (x)
p (x)
CS on one in (C.2)
2
pi (x) # Pi (x),
(x) pa (x) pi (x) (x), (1)(x)/pp (x)
CS on both in (C.2)
2
Pi px((x) + pi (x), pi (x) + p2 (x) p (x)
(p) (x). (x) (x)
CS multi. in (C.3)
K
Pi (x) pi (x) for
(x) (x) for all &
is often used in sample-based methods (Shimodaira, 2000; Jiang & Zhai, 2007; Baktashmotlagh al., 2014). However, the focus on domain adaptation has been mainly adapt to a single target distribution, not the overall generalization performance on multiple clients, which is addressed in this paper.
Statistical generalization and excess risk bounds. Understanding generalization performance of learning algorithms is one essential topic in modern machine learning. Typical techniques to establish generalization guarantees include uniform convergence by Rademacher complexity (Bartlett, 1998), and its variants (Bartlett et al., 2005), bias-variance decomposition (Geman et al., 1992; Adlam & Pennington, 2020), PAC-Bayes (McAllester, 1999), and stability-based analysis (Bousquet & Elisseeff, 2002; Shalev- Shwartz et al., 2010). Our work employs the first two techniques to analyze our density ratio estimation method in federated setting and establish generalization guarantees for FIDEM, respectively. Rademacher complexity has been used in FL. to obtain theoretical guarantees on the centralized model (Mohri et al., 2019) and personalized model (Mansour al., 2020). Mohri et al. (2019) considered a scenario where single target distribution is modeled as an unknown mixture of multiple domain distributions and obtained a global modal by minimizing the worst-case loss. This is different from our setting where we consider multiple test distributions for clients and focus on the overall test error. Mansour et al. (2020) studied personalization under the same training/test data distribution assumption over each client, which is different from our setting. Bias- variance decomposition provides a relatively refined characterization of generalization error (or excess risk), where a large bias indicates that model is not flexible enough to learn from the data and a high variance indicates that the model performs unstably. Bias-variance decomposition is typically studied in two settings, i.c., the fixed and random design setting, which is categorized by whether the (training) data are fixed or random. This technique has been extensively applied in least squares (Hsu et al., 2012; Dieuleveut al., 2017), analysis of SGD (Jain et al., 2018; Zou et al., 2021), and double descent (Adlam & Pennington, 2020).
Information- thhorreticct bounds the generalization error and privacy leakage in federated settings were established in (Yagli er al., 2020). Under partial participation of clients, Yuan et al. (2021) proposed framework, which distinguishes performance gaps due unseen client data from perfor- mance gap due to unseen client distributions. Still, these work study FL under the same training/test data distribution assumption over each client.
C FIDEM WITH A FOCUS ON MINMIZING R1
Without loss of generality and for simplicity of notation, in this section, set ( - 1. We consider four typical scenarios under various distribution shifts and formulate their FIDEM with a focus on minmizing Rg. The details of these scenarios are summarized in Table 4.
Remark 4. Covariance shift (as well as its assumption) is the most commonty used and studied in theory and practice in distribution shifts (Sugiyama et al., 2007; Kanamori et al., 2009; Kato & Teshima, 2021; Uehara al., 2020; Tripuraneni et al., 2021; Zhou & Levine, 2021). Handling covariate shift a challenging issue, especially in federated settings (Kairouz et al., 2021).
No intra-client covariate shift: (No-CS) For description simplicity, we assume that there are only 2 clients but our results be directly extended to multiple clients. This scenario assumes tr (x) = pk (x) for l: = 2. Client aims to learn Ah assuming p5
(x) is given. We consider the following FIDEM that is proved to be consistent in terms of minimizing minimizing R1:
Pk
min We2d TE
(xl.) vI.
80h (x2,), y2.1)
(C.1)
p
(x),))
18

---

Under review as a conference paper at ICLR 2023
Covariate shift only for client 1: (CS on one) We now consider covariate shift only for client 1, i.e. pf (xx # (x) and (x) = pl (x). We consider the following FIDEM
pl (xt.)) (x),)
22
tr ((hw (...).y..).
min WER T1
((hw
(C.2)
Covariate shift for both clients: (CS on both) We assume pi (x) + pl (x) and p (x) + ph px()), Le., covariate shift for both clients. The corresponding FIDEM is the same as Eq. (C.2).
Multiple clients: (CS on multi.) Finally, consider general scenario with K clients. We assume both intra-client and inter-client covariate shifts by the following FIDEM:
pi
(xf.)) (x
min WER-
E(hw d.
(C.3)
where E dE = and AR 2 0.
Proposition 2. Let E [K]. In above settings, FIDEM defined in Eqs. (C.1), (C.2), and (C.3) is consistent. i.e., the learned function converges in probability to the optimal function in terms of minimizing R1.
Proposition implies that, under various settings, FIDEM outputs an unbiased estimate of minimizer of the true risk.
Proof. For the scenario without intra-client covariate shift, FIDEM in Eq. (C.1) can be expressed as ((hw (x),)()))))
p (x2,))
p (x)
E(hw 2
22,)
22
Enp (x.3)
722
P2 (2,
(x)
pf (xx)
Ep(r)x
elb (((ow(x))) v)) (x) dx
x p (x)
= -Ep(s(x)
p (x) (x),y) dx
x
= -E(()())
p (x)) (x), dx
(xP)))))
(x)h((x))))
= R((hw):
For the scenario with covariate shift only for client 1 or for both clients, FIDEM in Eq. (C.2) admits
(x(5,)
p (x)
(how (x(2,) 22,))
n +000
(xp()
e( ((w((x)))))
T22
(x
po (x)
V
pia (x()
= Ep(x)x)
e(Tiw y)), dx
x pbl (x)
= -Ep(ybe)
pl (x) (x), dx
= (xp(( (((h((x),)))
= R1
We note that pi (x)
(x) (x) p [x) which is the product ratios due to intra-client covariate shift on client I and client covariate shift.
For multiple clients, let k E [K]. Similarly, we have
1
p (x(E)) E(h (x
2 +00
Rí (lw)..
P (x
19

---

Under review as a conference paper at ICLR 2023
Then we have
Pi (x))
ll (lw (2().)) yk,)) of mb
R1 (kww).
Pk (x,,2)
A=1
The consistency of FIDEM, i.e., convergence in probability, is immediately followed the standard arguments in e.g., (Shimodaira, 2000][Section 3] and (Sugiyama et al., 2007)[Section 2.2] using the law of large numbers.
Note that to solve Eq. (C.3), client needs to estimate
e (x) for all clients & with 2 > 0 (C.3). [x]
1 A does not affect the optimal parameters in Eq. (C.3). For rotational simplicity, we set 0 1 for k E [K].
Remark 5. Scaling Σx=
C.I. No INTRA-CLIENT CLIENT SHIFT
In this section, we consider the important and special case of the setting described Section 2.1 under no intra-client covariate shifts but inter-client covariate shifts. For simplicity, we consider a two clients with train/test distributions P and Q whose train/test densities are denoted by p and q, respectively. We also suppose that we have sample ~ P and z' ~ Q to learn with the goal to find an unbiased estimate of the overall risk with the smallest variance.
this setting, the classical ERM (FedAvg) objective {(z, 0) + {(2', 0) is an unbiased estimate for the overall risk L(0)= Ep ((, [=(((= 0)}². In this setting, the objective of FIDEM, i.e., ((.((0) + (Q)) with (0) (1 + ((a) overall risk (().
p(=) f(z, 0) and (Q) (1 + p(=') ((z', 0) is an unbiased estimate for the (())
We now show that the our method (FIDEM) has a smaller variance than FedAvg under certain conditions. Let [p[((((, 0) - Ep( ()) = oi and Egl(!(=', 0) Eo(e(=', 0)) o².
For FedAvg, the variance is given by
Er (e(2, + () - - +
For FIDEM, the variance is given by
Er ( (f-((0) (r + (0)) ((())) Vr Vo
where Vp = 4Ep(((((())) - [ and Vo- = = ((())) L(O))?)
We now expand each term Vp and Vq- We can show that
- Ep
(
g(2)
(((2, 0) Ep(((2, 0)] - 011) 21 9
of + +
1
p(z)
4
where 0% = Ep
( plte) [(e))) 0) - E .01) 9 + 2EE [1(2,,0) - Epl((z 011)
(((e) ((2, 0)
(()))
Boll(s', .0)] Similarly, we have
Vqa = 1 Ro [(1
p(2') ((('' -Ep((,((, []] Eo(((=200))) og ((21)
008
4
where 03- = =Bol
((()))
((=', 0) =r]((z,01) " + 2Ee (((2 (ioe()))Eo((((,00))) (01(
( ((2'00000
((37)
Epl((z, [0]]]
We note if 03 + 03 S 3 + +z3) then, FIDEM will have smaller variance than FedAvg, i.e.,
Vp + Ve 2 o7 + oz. The exact condition depends on the loss and densitics. To show a concrete
'For notational simplicity, we overload E(z,0) 0) to denote the loss of model 0 example
20

---

Under review as a conference paper at ICLR 2023
example, for the more general and practical case with both intra/inter-client in Section 4.2, show that FIDEM results smaller excess risk compared to FedAvg through a refined varrinae decomposition. Given two distributions, considering the case of no intra-client shift is special case, where it is true that AvdAvg is an unbiased estimate of the overall risk. However, this unbiasedness breaks soon there is only one client whose test and train distributions different, which is very common in theory and practice. Please note that FIDEM is an unbiased estimate of the overall risk in general FL setting without requiring any prior knowledge/assumptinss on the potential covariate shifts.
D RATIO ESTIMATION
D.I NNBD DRM FOR A SINGLE CLIENT
For simplicity, we firstly focus on the problem of estimating r(x) = px((x)
(x) and then extend our
consideration the estimation of (x) in Eq. (3.1). Let denote the true density ratio. Our goal is to estimate r" by optimizing our ratio model r. The discrepancy between r and r" is measured by
Eppr [BD (r (x) r(x))] We note that E 2p== BD,(r" (x) r(x)) Er(r) E B,p (rr=([(("(())) where ()(r) tpt= [V/((x)))(() - [(((x)) - E.t [V)(( Note that [p (f(((()) is constant fj=1
Let (x(")=
li=1 and { denote unlabelled samples drawn i.idd from distributions pd and
p' respectively. Let H.r C (r: X - B denote hypothesis class for our model r. Using an empirical approximation of E (x) r(x),, Sugiyama et al. (2012) formulated BD-based DRM
problem minYEH, (r) where
E,(r)=
= ntr
f(r()))) - nle vf(((x))))
(D.I)
Sugiyama et al. (2012) showed that BD-based DRM unifies well-known density ratio estimation methods by substituting an appropriate f in (D.1). However, it is shown that solving BD-based DRM with highly flexible models such as neural networks typically leads to an over-fitting issue (Kato & Teshima, 2021; Kiryo et al., 2017). In particular, Kato & Teshima (2021) called such issue "train-loss hacking" where 1/ म Σ/ (r((x)))) in (D.1) diverges if there is no lower bound on this term. Even when there exists lower bound, the model tends to increase the largest possible values of { )= To resolve such issue, Kato & Teshima (2021) proposed to use non-negative BD (nnBD) DRM, i.e., min,eH, (r) where
its output range at points {xx] 1z=1-
(7() ReLU 1 n n fr
RD ne Σ ((((x()))
1 to
C
Σ (r(xx))
ne Σ
(r((x)))),
(D.2)
ReLU(>> = max(0, 0 < C F supxxxu rx),, (1( vf(z)z f(z), and (z(2)
C(Vf(z)= -(())) Vf(=). Substituting f(z) = (x-1)² into (D.2), the least-squares importance
fitting (LSIF) variant of nnBD is given by
1
C
n
&TSTT (r) = ReLU
(r(x)o)
2 (x))))
2n
2n
te
2
j=1
In Appendix F, we show explicit expressions for unnormalized Kullback-Leible (UKL), logistic regression (LR), and positive and unlabeled learning (PU) variants of nnBD.
Estimating F su rxx is key step for density ratio estimation. It is shown that underes- timating Icads to significant performance degradation (Kato & Teshima, 2021, Section 5). Kato & Teshima (2021) considered C
syper-parameter, which can be tuned. However, obtaining efficient estimate of is desirable, in particular when training a deep model.
Let B C F Assume pd and pd are continuous. Since B is connected and Lebesgue-measurable measurable with finite measure, by applying intermediate value theorem (Russ, 1980), there exist in and f such that Pr(Xtr B) = (3*()*+Vol(( and Pr( te E B} p (ol())) where Vol(B)
21

---

Under review as a conference paper at ICLR 2023
SXEB dx. We note that supxes r" (x) v
supxem (x)
infxer (l) and plo(ale) pir(
I intxer (lr(x) We partition
supxem Daeeepp"(e (x)
X into M bins where for each bin Bm if there exists some x E Bms then define f.
EB( + Σi= (x5" for m E [M]. Otherwise, F. = O. Finally, we propose to use F.a)) C $ where F = ma, (f.) Convergence of i to F is established in Appendix G.
Pr(X"EBm) ni E. EB))
Now, suppose there are K clients where each client provides n unlabelled test samples to the pool of samples. Our goal is to estimate Th Eq. (3.1) for k is given by min (rx) where Ey (rx) (r(()(x())) The nnBD DRM problem for client k is minr, E7 (ra) where
1,..,,, The BD-based DRM for client Σ n i=1 (VS(rx(EE)))) ( (xE, f(rr ((rx((x
K
87 ( ReLU(S),
noo Σ
(r(r(())))),
(D.3)
Si,4 + E (r(x(xx)))) nie
Ej= j= Et=l ( (1(T((x)))) 0 < C. A.2 and Fk =
su (x). Substituting f(z) (=-1)² into (D.3), the LSIF variant of nnBD for client is given by min, &isip (Tx) where
Th (xx()))) Ch (x()))
(isi(nn) ReLU(SLSIT ne
(D.4)
and SLSIP 2n UKI., L.R and PU variants of nnBD for client ls in Appendix H.
E (
Co.
j=1 E
rx(x)))) We provide explicit expressions for
t0
(x For HDRM method, we first partition X
Our goal is to estimate rk sU ((())
into M bins where for each bin B., if there exists some X E Bm. then we define fr.m
EEs StSt"t PB(X(EBB..)
Σj= DE, EBm) for [M]. Otherwise, Pk.m Finally, we "/ Σ. EB,,)
propose to use Cg = 1 where Fx = max (Fx,1. ,
D.2 BD-BASED DRM FOR FL
Our goal is to estimate T3 by minimizing the discrepancy Egg (BD)(rī(x)) || [x(x))), which is equivalent to min,,eH, {r() where
(T(rk) Epg -
f(rx(x))] Σ E [V)(r((x)),,
(D.5)
since Epy (rD)(rī(x) rx(x))] = + (((t(()) and Exp (x)] constant w.r.t. rk. Let (x) ". and {x/ respectively, for / E [K]. A natural way to solve ming, (rx) is to substitute empirical averages in Eq. (D.5) (Sugiyama al., 2012), leading to BD-based DRM for FL: min (r(r)) where
+ 1yn denote unlabelled samples drawn i.i.d from distributions ph and p!a,
ni Vf(rn(xx)) - f(rx(x);))) n
te
K
(r(r
vf (f(x(x)))))
tc
1=1
E COMMUNICATION COSTS AND FIIDEM
To estimate density ratios for FIDEM. clients require to send a few unlabelled test samples only once. The server shuffles those samples and broacassts the shuffled version to clients only once. The
22

---

Under review as a conference paper at ICLR 2023
communication overhead estimate ratios is negligible compared to the communication costs for sharing sigh-dimensional stochastic gradients over the course of training.
Consider the example of CIFARIO consisting of 32 by 32 images with 3 channels represented by bits. If one shares 1000 unlabelled images", the communication amounts to sharing roughly 3 x 10 values each with 8 bits, i.e., 25 10 total communication bits 3.1MB. In contrast, during training, the network size alone easily surpasses this size (e.g. the common ResNet-18 has 11 million parameters, each represented by 32-bit floating point), Standard training of ResNet-18 requires 8 x 10a iterations and aggregations, which amounts to 2.816 x 10 total communicated bits per client, i..,, 3.5TB during training.
In other words, the number of communication bits needed during training in standard federated learning is usually many orders of magnitudes larger than the size of samples shared for estimating the ratios. To further reduce communication costs of density ratio estimation and gradient aggregation, compression methods such as quantization, sparsification, and local updating rules, can used along with FIDEM on the fly (Alistarh et al., 2017).
Alternatively, eliminate any privacy risks, clients may minimize the following surrogate objective, which we name FIIDEM:
K
min F(w) Σ Fw(w)
(E.1)
where (w)
"i PE (xt.) 2 Pt (x
((h (x
We note that privacy risks are eliminated by solving E.I. However, to exploit the entire data distributed among all clients and achieve the optimal global model terms of overall test error, clients need to compromise some level of privacy and share unlabelled samples generated from their test distribution with the server. Hence, this paper, we focus on the original objective F(w) FIDEM, which is different from F(w).
F VARIANTS OF NNBD.
In this section, we show explicit expressions for unnormalized Kullback-Leibler (UKL), logistic regression (LR), and positive and unlabeled learning (PU) variants of nnBD.
Substituting f(z) = 2 log(2) - into Eq. (D.2), we have {1 = z and l2(2) = 2C - -log(z). and the UKL variant of nnBD is given by
tm
(r) ReLU
ntr Σ
(x-))
C
Σ
r(x)o)
to
==1
(F.1)
log(r(x)0)) Cr(x}9))
te 5=1
Substituting f(2) 2 log(2) (2 + 1) log(z + 1) into Eq. (D.2), we have (2) = log(z + 1) and (2(=) C Coo((= + 1) log [=+] and the LR (BKL.) variant of nnBD is given by
n
te Σ
(r) = ReLU
log(r(x)) tr + (x)
log(r(x))) +1))
cr 1=1
nte
1=1
(F2)
r(x+()
C Clog(r(x))) + +
log
to
r(xcj)) +1
'A total number of 1000 images are shown to be sufficient to learn density ratios on CIFAR10 (Kato & Teshima, 2001){10, Section 5.1].
23

---

Under review as a conference paper at ICLR 2023
Substituting f(2) = C'log(1 - 2) + C2(log(2) - log(1 2)) into Eq. (D.2), have (2(2)
-C'log(1 2) and (2(z) = (2) 2)++ + (C - -C) log 1 2). and the PU variant of nnBD is given
by
n
C n
(r( ReLU
log( r(xxt))
Σ
log(L r(x)
71
n
(F33
log r(x) -(
ne
G CONVERGENCE OF F AND K-MEANS CLUSTERING.
Lemma 2. n n'e, and M go to infinity with supm Vol(Bm) + 0, then ng + Tg-
Proof. Letx E X Note that when na n² and M go to infinity, the numerator and denominator of 75 become Df Vol) and p (x) respectively, where x E Bm.
Please note that our density ratio in Eq. (3.1) is in the form of a sum of test densities over own train density. So even if one or few number of ratios are poorly estimated, it will not impact the entire ratio in Eq. (3.1) nested estimation errors. The error does not propagate in multiplicative manner an additive way.
k-means clustering for HDRM. We note that partitioning the space and counting the number of samples in each bin is not necessarily an easy task when data is high dimensional. practice, one simple method is to cluster train and test samples using an efficient implementation of k-means clustering with M clusters and count the number of train and test samples in each cluster (Lloyd, 1982). To estimate the ratios, in addition to a batch of samples from the train distribution for each estimating client. The running time of Lloyd's algorithm with M clusters is ((d where is the total number of samples with dimension dx-
need batch of samples from the test distribution of cach client
H UKL, LR, AND PU VARIANTS OF NNBD FOR MULTIPLE CLIENTS.
In this section, we provide explicit expressions for UKL, LR, and PU variants of nnBD for client k.
The UKL variant of nnBD for client k is given by min ETKI (rw) where
C
12
K
é+ (rk) = ReLU
rx
Tx(()))
no
(H.I)
K
(log(T> - CArA (x(x())))))))
te
The LR variant of nnBD for client & is given by min E (rk) where
E+ (tt)
ReLU
n
log (ru (x
+
Ck
n
te
k
log(rx(x +1)
no
#=1
(H.2)
re(x19)
log
Ct log(rx +1)
77
rx(x))))
+1
24

---

Under review as a conference paper at ICLR 2023
The PU variant of nnBD for client & is given by min & (TA)
where
Rk
CF
k
(rx( = ReLU
log(1 (x(xx +
log(1 - -x((()))))
n2
(H.3)
K
(Ca (og((((((())))) (Ox 0 log(1 - r -xx(x(,))
I PROOF OF THEOREM 1
In this section, we prove Theorem 1, which establishes an upper bound on the generalization error of nnBD DRM (HDRM method with an arbitrary f) for client & in terms of BD risk, which holds with high probability along the lines of (Kiryo al., 2017; Lu et al., 2020; Kato & Teshima, 2021).
We remind that client k's goal is to estimate this ratio:
Σ
pi (x)
Tx(x)
(L.I)
Pkc (x)
For client k; the BD risk given by
K Σ 1=1
Ep(rk) = [xx(x)((((((xx)]]] +
1 (rxx(()
(1.2)
where E. = Eptt - Ck E E Eppe < Ck < Fo Tk supxEx"
(x)
(z) =
Vf(=)= f(2). and (2(2) = C(Vf(2)2 f(2) Vf(z). We note that the definition C2 implies
PA - C& Σ pl > O. We remind that f B - TR is strictly convex function with bounded
gradient Vf where By [0, 20), and H, C (r X + By} denotes a hypothesis class for our model
The nnBD DRM problem for client k EH, & (rx) where
K
(Tx) ReLU ((pp: Ck Σ ) [[1 + Σ (22((((
(1.3)
with Epye the sample average over {x and Enye the sample average over {xt 1n In the following, we denote E, := EB, C₁ Σk En for notational simplicity.
Let f arg min & (rk) and r arg miney EH, E, (rx). We first decompose the general- ization eтror into maximal deviation and bias terms:
(fx)) -7 (7)) E,(r()
2 2 sup
(8y(r)) (())
(I.4)
2 sup 187 (rx) - -BL) (rx)]]+ sup EER
ELLT -1,))
where the second inequality holds since A == arg min, 8 (rx). The first term the RHS of (I.4) is the maximal derivation and the second term is the bias.
In the following two lemmas, we find an upper bound on the maximal deviation supricH. (8t(r)) (rz) BLÊ (rx)] and bias sup B (rx) E (rx)), respectively.
25

---

Under review as a conference paper at ICLR 2023
Lemma 3 (Maximal deviation bound). Denote De su maxic (1.2) [e((2)), then for any
0 < 8 < 1, the maximal deviation term is upper bounded with probability at least 1 ò
K Σ
sup (r)( ( (rx))l 4L, (H.) + 4(CxL1 + L2) nEtH,
RPi 250
(Hr)
1=1
(1.5)
K(1+ + C2)2
De
+
log
tr
nte
Proof. Denote (Sk)
sup suPT (rx)
(ra)
EJē (rx)]l with S₁
{xt ( Xi,1." knn Let 5. be obtained by replacing element of set Sk by an independent data point taking values from the set A We now measure the absolute value of the difference caused by changing one data point in the maximal deviation term (I.5), i.e., ($x) 2 ( II
If the changed point is sampled from pk then the absolute value of the difference caused in the maximal deviation term is upper bounded by 24, If the changed point is sampled from "t
pt the the absolute value of the difference caused in the maximal deviation term is upper bounded +11(Ce+1] for I 1, ..... K. Applying McDiarmid's inequality (McDiarmid al., 1989), with by 25th
probability at least 1 - ö, we have
(Tx) (1(x) (rx)) & E sup r EHH (rk) - ( (rx)ll
sup E.
K(1 + ((1+C,)² log 1
V n n
In the following, we establish an upper bound on the expected maximal deviation Elsup,, &f(()) E(ê by generalization the symmetrization argument in (Kiryo et al., 2017; Lu et al., 2020) followed by applying Talagrand's contraction lemma for two-sided Rademacher complexity.
Let m E [M] and Nm E Z, for M E Z.. Let 9m R - be a Ly... Lipschitz function. Let Pm.p mmm.p denote a probability distribution over X Suppose that {x are drawn i.i.d. from Pm.p for E [Nm]] and m E [M]. Let fm.p By + IR,, be a Lmpp-Lipshitz function and Öm.p be a constant m, p. Consider the following stochastic process:
(x(T
Σ Im
p=1
where Rm, denotes sample average over (mr. In the rest of the proof, we show that
M N
E sup ra EH
jie (r(alr)))ll <
Lgnn 1Cm,pp Lem D.Pr.p (Hr))
(l.6)
To prove (I.6), we consider a continuous extension of (mpp) defined on the origin. We note that such extension does not change Rig (rk) since ((m.p) takes values only in By. If By = {(21, 22)) for some 0 21 22, then for any z E [0, 21). we define ((m.p)) (z) limm ((mmp) (2) where limzja, ((m.p) (=) exists since (mm is uniformly continuous due Lipschitz continuity. Then (m. "om.p will be Lips-hip on 2 E [0, 2g]. Let )mm be an independent copy of {x))mm> Let denote 6 := E[supr, (rx)
Following a symmetrization argument ( (Vapnik, 1999), an upper bound on the symmetrized process can be established by Rademacher complexity:
26

---

Under review as a conference paper at ICLR 2023
Nm
8g S E
sup
gm
Cm. Cm. (l (Fx))(() -B(gm
>
p=1
p=1
M
N
< EE
sup
Σ
goL
Cm.p Em. (im.
Σ
Bm (rx(
F4E m=l
M
No
Bm.pl (mmp)))) E.. (m (Ta
L
sup TEE
m=
9m
C Cm IBE|
sup TEH
[m (mmp)) - (im (0)) Em, ((mss((((x)) ( (0)]]
pm1
M
Nm
Lim
1mmpp
sup TEE,,
(lmp (Fx( (m. (011
M
N
L 9m
1mmpp Rhtuup (Hr))
10
(I.7)
where om.p are Rademacher variables uniformly chosen from {-1,1}, and Empp denote the Tmppp
expectation and sample average over data distribution Pm.p and the independent copy {x4 )= respectively, the third inequality holds by the Lipschitz continuous property of Im. and the last in- equality is obtained by applying Talagrand's contraction lemma for two-sided Rademacher complexity (Ledoux Talagrand, 1991; Bartlett Mendelson, 2002).
Applying (I.6), we can show that
K
E| sup (rx) BIE, (rx)ll < 4L, R (H4) + + L2) EE
Σ 1=1
pel (Hr),
which completes the proof.
Next we find an upper bound on the bias suprieH, [B( (rx) - E Ey(rx)
Lemma (Bias bound). Denote Ae supzEB, maxie(1.2) (6(())
Assume
infren, E[EA (rx((()))] 0 for lo E [K]. Then, upper bound the bias term is given by
-
sup T.,
((1 KKK))AA exp A//n + K.C.
(1.8)
for some constant 774 0.
Proof. Let Bx = Ep TEL - Eg(rk)]
Cs ΣK Bpy- We first note that
BEÊT (rk) E((r))
= E RoLU (rx()(x) - t (e((((
E |CLLU (Bulli(rx(x))) - (x(e((r(x)))]
E 1 ReLU (Eall((Tx(x)))) (r(e
ReLU
(EN(((((((>))) (x(()(x(x))))
I RReLU (Ball((Ta(x))))) # (
sup
(ReLU(=) - -2) 2)
=
27

---

Under review as a conference paper at ICLR 2023
where the third inequality holds due to Jensen's 's inequality.
We note that (x((((rx(x)] - (1 + AC implies
sup ==55((4
(ReLU(2) - -) (1 Ac.
Due to the assumption in,, (((x((((( > 0, there exists an T
0 such that
([Ex)G((n(x))]]] 2 ?) for all rh Hr. Then we have
E 1 { ReLU (Bxl(161((x11)) + Balls(r((x)1]]] Pr suppp(e
Pr -r(((al((rr(())) <0}
Pr (r((((((((xx)))) < (Tr))(( - mp
where (eLU(2) ReLU(z) - 2.
Kn Let 5% be obtained by replacing element of set Sy by an independent data point taking values from the set x We now measure the absolute value the difference caused by changing one data point in (Sx) ( I. If the changed point is sampled from p the the absolute value of the difference caused in the maximal deviation term is upper bounded by n If the changed point is sampled from pl the the absolute value of the difference caused in the maximal deviation term is upper bounded by A.C for 1 = .,. K. Finally, McDiarmid's inequality (McDiarmid et al., 1989) implies:
Denote (Sk) := (r(()((x()))) where Sg {xx .1 x1 1,1
-2 A /2/nk/ + KC
Pr (Rxll < E mh) S exx
which completes the proof.
Substituting the upper bounds in (I.5) and (I.8) into (I.4), with probability at least 6, we have
K
: - < 8L, (Hr) + (6,, De, ir n²²) + 8(CbL1 + L2)
Σ 1=1
Re nic (H,)
(I.9)
where V Ae//8(22 K(++CN1) log + 2(1 KCx)A, exp (xting KO(AS/ ni
2n
for some
constant > O. This completes the proof.
J GENERALIZATION BOUND FOR MULTI-LAYER PERCEPTRON AND MULTIPLE CLIENTS
Our generalization error bound for client is depends on the Rademacher complexity of the hypothesis class for our density ratio model H, C {r X' + B w.r.t. client & train distribution p and all client's test distributions p/a for 1 [K]. By restricting function class for density ratios and substituting an upper bounds on its Rademacher complexity, we can obtain explicit generalization error bounds terms of n ne a special case. As an example, the following corollary establishes generalization bound for multi-layer perceptron density ratio models in terms of the Frobenius norms of weight matrices.
Example J.1 (Complexity for layer perceptron class (Golowich et al., 2018)). Assume that distribution has bounded support S, := supxesupr(p) ||x|| < co. Let H be the class of real-valued neural networks with depth I over the domain ter W; be the network weight matrix i. Suppose that
28

---

Under review as a conference paper at ICLR 2023
each weight matrix has bounded Frobenius norm |Wil|s 1 Aw; for E [L] and the activation is I-Lipschitz, and pesitive-homogeneon function, i.e, Φ(az) = (z((2), which applied clement-wise. Then we have
R (H) < Sp(v2L 2 + 1) Il Aw.
Vn
Remark To control the upper bound Aw, for i [L], is natural to employ the sparsity of the weights, e.g., (Golowich et al., 2018 8, Section 4) and (Hanin & Rolnick, 2019). We consider a special network architecture where diag( W;)'s are close to 1-sparse unit vectors for E [Z.]. which implies that the matrices W,'s will be almost rank-1. Then |W& is upper bounded by 1 for i e [L].
Corollary (Generalization error bound under Example J.1). For Example J.1 and loss functions described in Theorem 1, with probability at least 1 5, we have
Ky k
K
KT
(f({k) - E,(r1) -
Σ
+ (666 De, Ae nn
Vn
1=1
where KT O K(+C n
PK VLII Aw.). KI
O(max L1, L2)S p VLIIi Aw.), and v
A
log 1/ +2(1+ K exp
-20
some for some constant > 0.
Finally, apply union bound and obtain a global generalization error bound that holds for all clients: Corollary 2 (Generalization error bound for multiple clients). Let 0 8g for k E [K]. Let
K" [ Kg. For Example J.I and loss functions described in Theorem 1, with probability
at least -kki 8R, we have
K
K
Ktc
max
- - <
kE[K]
n
Vn
1=1
T7 (5, De, 12" nea)
2n where 8( K(1+0) log + 2(1 + KC) Ae exp A2/2" A3/m
C
ni
maX Ck. n²' minke[K] n 5 = minke[K] 66, and = min MKk-
The rates match the optimal minimax rates for example for density estimation problem when the density belongs the Hölder function class (Tsybakov, [008)[Section) 2] with sufficiently large based on Definition 1.2 of Tsybakov (2008). The 12(1/ /n) lower bounds are obtained for important problems including nonparametric regression, estimation of functionals, nonparametric testing, and finding linear combination of M functions to be as close the target data generating function (Nemirovski, (998)[Section 5.3].
K ADDITIONAL ERROR DUE TO ESTIMATION OF Tк
In this section, consider practical scenario where have access only in imperfect estimate of F = supxex" (x) to find C3 in Eq. (3.2). In particular, we find additional error when using Č₁ Fi where Ps is obtained by HDRM in Section 3. The nnBD DRM problem for client & using C₁ is min & (rk) where
(7x)) ReLU
(Rpp Čr Ee ([r))(()))))))) + p
(K.1)
I=1
Along the lines of the proof of Lemma 3, we can show that the maximal deviation term using C% is upper bounded with probability at least 5:
K Σ
sup (rx) B1 (ra))l < 4h, R R. (HL)) + 4(CaL: I + L2) E....
Rej
(Hr)
1=1
(K.2)
K(1 + 0x)3
1 log
+ A 2
12
no
29

---

Under review as a conference paper at ICLR 2023
Under perfect estimate of Fvx supxext (x) with Cs 7/2 the nnBD DRM problem for client A: is min 87 (rx) where
(Tu) ReLU ((8 Cs Σ ) 1e (Tx((()))) + Σ E (r(x()))))))))
(K.3)
Applying triangle inequality, we first decompose the bias term
- sup ne
(Tx) (rw)ll (mw))
sup rE
(K.4)
sup rEM,
(1ef+((x))) E)(ra)
An upper bound on supr
| (rx)] - (rx) is established similar to the proof of Lemma
-2n
EE|E (rx) Ey - (1 KC exp
sup
Ai/n KKG
ELEH,
Substituting Eq. (K.1) and Eq. (K.3) into Biē (rx) + (rx))l we have
[R(E) (rx) - 87 (r=)]
K
= -|((ReLU((Bp) C2 Σ (r1x - ReLU((É, - Cs (((x)(()))))
Σ 1=1
i=1
which together with ReLU((a) Re)U(b) la bl is used to establish the following upper bound:
[m())())) - (ra) = KA-L - Ckl.
(K.5)
Let m = arg [MX fR,m- We note that by the construction of HDRM, there is a constant
lower bound on the numerator of 7k. i.e., पक Σ}= tH Σ (x E Bm-) 2 C, that is achieved In when {x( f==1 are distributed uniformly across M bins. Let x E X and let p (x: M) denote a histogram-based density estimate of p (x) with M bins. The maximum value of C₁ is attained when En E 1xx), E Bm.) meets its lower bound, which leads to the maximum deviation from CA S. Ck. Assuming p (x) is L with supxex Pk (x) < oc, the mean squared error of a histogram-based density estimate with M bins upper bounded by (Wasserman, Seetion 6]: Ex M)- p (x) = OLL /M2 2 + M M/ Putting together with a constant lower bound on the numerator of ny and applying Jensen's 's inequality, we have:
M
EJJč2 C+ S
M
L PROOF OF LEMMA
We first note that
(() - L(O.) =E 1. Bias + Variance.
We first find the expression for Ô considering the ridge regression problem assuming p (x FIDEM problem with Tikhonov regularization is given by
is given.
(x(x
arg min
w x; v2)² + 1110
30

---

Under review as a conference paper at ICLR 2023
(x)) and is the regularization parameter. This is reweighted least squares problem. (xx)
where uz
The objective function above is strongly convex and differentiable. Applying the fist-order condition, the unique minimum is as follows:
0 [X WX AL) AL)) x Wy
(L.1)
where W dia ... w.
Substituting y = X0, + E into (L.I), we note that
(x WX + Ala) x WXe. + (X TRX + AL)) "x We
WW
and
Ex,c cc (0) - Ex (x [X-
WX + ALd) x x WWX.]
We now characterize the bias B(0) and variance v(0) terms when the model estimate is given by (L.1).
Let ||x == x Ax. Substituting the expression for 0 into R(O), the excess risk can be decomposed
into a bias and variance term as follows:
R(0)- = Ex,ex, [Vy 0T x)² (y - 0. }
= Ex,xx. (y- 0_ x + (0. - 00)xxx xx) (y 0_. x
= Ex,xx (10. (0) 0) x
27
-EE,eell0- - 0
= B +
where the bias is given by
(XT + ALA) -1 "WxXX - 0. 1
B = Ex,e
= =Ex
||
(X AI2)
10
I
= Ex/,Ex/AAW: E Aw,
with
AW. = Tx T
and the variance is given by
[X (xTxxxX> + AL2) -'x x TWe] E
V = Ex,e
= =,2'x |tr (dv))..
where Φy = -xx" T WX + Ala)
-1 x x (X WX + Ala) -1 '
-'...
M PROOF OF THEOREM? 2
In the one-hot case, is clear that X En x and X WX = En w;x,x] are diagonal matrices.
For bias in the hot setting, we have
B(0) = 2 0. ( T + L (x (XTWx)))" '00
10)))
X2
(X1(X WX) 2)
X3
Maym + 2\2
31

---

Under review as a conference paper at ICLR 2023
where the equation holds by the fact that, all matrices diagonal including X, X WX, and E Accordingly, we have (x WX) = XxxX ( with E [d]. For the classical ERM, the bias is
d
(O.):13
B(0)) X2 Σ
144 X]2
where A; is the eigenvalue of E.. To achieve B(0) & B(0"), we have to make some assumptions on the relationship between Xi X; and ws. Our analysis of error bound requires
X
A
P4 +
A
(M.1)
[1,0, + 212
J +
M
X
which implies
X
Wi >
-
(M.2)
A
such that Eq. (M.1) holds where the inequality b+c For the vanilla ERM, the variance is
< + for any a. 0.
d
Aspli
v(0")
2
[4 + 2]2
For FIDEM, the variance is
v(0) = of (X WX + AI) - X W (X WX X1) -1 - '
XA
(I(XTWX) + x)²
Xyuw?
Juwn + Aj3
We note that v(θ) S v(0") can be achieved by
Aspls
2
[M4: + x12
[mww + 212
This can be obtained by
14 +
A
X
(M.3)
H4
+
#4
A
which implies w; < E
Combining Eqs. (M.2) and (M.3), the proof is complete.
N WHEN FIDEM CANNOT OUTPERFORM ERM
In this section, provide counterexample to show that, under which certain case. FIDEM cannot provably outperform ERM.
Proposition 3. Under the same setting of Theorem 2, i.e. the fixed-desige setting and label noise assumption, under the following condition
max [)
If the ratio satisfies
w. & min
(N.1)
p4
then we have
R(0")
R(O).
32

---

Under review as a conference paper at ICLR 2023
Proof. According to Eq. (M.1), B(0") < <B(0) holds by which is equivalent to
14 +
A
14
+ A
X
X V
(N.2)
A
According to Eq. (M.3), v(0*) < v(O) holds by
#4 + wy
X
14 + X
A
which is equivalent to
1/
(N.3)
Combining Eqs. (N.2) and (N.3), the proof is complete. To validate the condition in Eq. (N.1), we require each term in the RHS to be nonnegative. That implies
max 1-)
which is our condition in Proposition 3.
V 2 and / N
By checking Eqs. (N.2) and (N.3), in both cases
< 1, we have
Wi & 1.
O EXPERIMENTAL DETAILS AND ADDITIONAL EXPERIMENTS
Datasets: We make use of three datasets in the experiments: MNIST (LeCun et al., 1998), Fashion M (Xiao et al., 2017), and CIFARIO (Krizhevsky et al., 2009). MNIST consists of images depicting handwritten digits from 0 to The resolution of each image is x 28. The dataset includes 60, 000 images for training. Similarly Fashion MNIST includes grayscale images of clothing of resolution 28 x 28. The training set consists of 60, 000 examples, and the test set of 10, 000 examples. CIFARIO consists of colored images with resolution of 32 x 32. The training set contains 50, 000 examples while the test set contains 10, 000 examples.
For all experiments each of the clients are computed with a batch size of 64 and aggregated on the server, which uses the Adam optimizer. Experiments on MNIST and Fashion MNIST uses LeNet (LeCun et al., 1998), learning rate of 0.001, no weight decay, and runs for 5, 000 iterations. For CIFARIO experiments we use the larger ResNet-18 (He al., 2016). Batch normalization in ResNet-18 is treated by averaging the statistics on the server and subsequently broadcasting to the workers. A learning rate of 0.0001 and weight decay of 0.0001 are used. We report the best iterate in terms of average test accuracy after 20, 000 iterations. All reported mean and standard deviations are computed over 5 independent runs except for CIFAR10 which uses independent runs. For target shift the randomisation is also over the realization of the class distributions to ensure that the conclusions are not due to the particularities of the sub-sampled images. All experiments are carried out on an internal cluster using one GPU.
Experimental setup:
the cross entropy loss. The stochastic gradient for
Fashion MNIST is provided under the MIT license.
33

---

Under review as a conference paper at ICLR 2023
Table CIFARIO target shift distribution across 100 clients where groups of 10 clients shares the same distribution.
Class
0
2
3
5
6
8
Train
95/100
$/9
5/9
5/9
5/9
5/9
5/9
5/9
5/9
5/9
Client 1-10
Test
6/9
6/9
6/9
6/9
6/9
6/9
5/9
6/9
6/9
95/100
Train
6/9
96/10 100
%/9
6/9
6/9
6/9
5/9
%/9
8/9
6/9
Client 11-20
Test
5/9
5/9
5/9
5/9
5/9
5/9
5/9
5/9
95/100
5/9
Train
6/9
3/9
95/100
5/9
5/9
5/9
5/9
5/9
3/9
5/9
Client 21-30
Test
5/9
5/9
5/9
5/9
5/9
5/9
5/9
95/100
5/9
5/9
Train
6/9
5/9
5/9
95/100
$/9
5/9
5/9
5/9
5/9
Client 31-40
Test
5/9
5/9
5/9
5/9
5/9
5/9
95/100
5/9
5/9
5/9
Train
6/9
5/9
6/9
6/9
95/100
6/9
5/9
6/9
5/9
5/9
Client 41-50
Test
6/9
5/9
6/9
6/9
5/0
95/100
6/9
6/9
6/9
5/9
Train
5/9
5/9
5/9
5/9
5/0
95/100
5/9
5/9
5/9
5/9
Client 51-60
Test
6/9
5/9
5/9
6/9
95/100
5/9
5/9
5/9
5/2
5/9
Train
6/9
5/9
6/9
6/9
1/9
6/9
W5/100
6/9
5/9
5/9
Client 61-70
Test
6/9
5/9
5/9
95/100
5/9
5/9
5/9
5/9
5/9
5/9
Train
6/9
$/9
%/9
%/9
$/9
6/9
$/9
96/100
5/9
5/9
Client 71-80
Test
6/9
3/9
95/100
5/9
5/9
5/9
3/9
5/9
5/9
5/9
Train
6/9
$/9
5/9
6/9
5/g
5/9
5/9
5/9
95/100
5/9
Client 81-90
Test
5/9
95/100
100
5/9
5/9
5/9
5/9
5/9
5/9
5/9
5/9
Train
5/9
5/9
5/9
5/9
5/9
5/9
5/9
5/9
5/9
95/100
Client 91-100
Test
95/100
5/9
6/9
6/9
6/9
6/9
5/9
6/9
6/9
1/99
Table 6: Average, worst-case, and best-case client accuracies of CIFARIO target shift experiment across 100 clients where 5 randomly sampled clients participate in every round of training.
FIDEM
FedAvg
Average client accuracy
0.7658
0.7237
Worst client accuracy
0.6163
0.5403
Best client accuracy
0.9016
0.8904
0.1 TARGET SHIFT
For the target shift experiments on Fashion MNIST in Table 1, we summarize the different number of data points for each dataset split Table 9. similar distribution across clients is used for the additional experiments for FIDEM and FedAvg on CIFARIO (Table 8). CIFARIO differs from Fashion MNIST in the number of examples due the training set being smaller. The results for CIFARIO in Table 7 shows that FIDEM uniformly improves the accuracy over FedAvg on this difficult target shift instance. We additionally include a two-client setting in Table 10 with the associated distribution described in Table 1I.
To model scenario closer to real-world FL, we consider a setting with 100 clients on CIFARIO under challenging distribution shifts and partial participation of clients, which is requirement for cross- device FL (Kairouz et al., 2021; Wang et al., 2021). We sub-sample 5 clients uniformly at random at every round for 200, 000 iterations. The target distribution is described in Table and experimental results can be found in Table 6. We observe that FIDEM uniformly improves the test accuracy when compared with FedAvg and that the gap is especially large between the worst-performing clients.
To compute the exact ratio r(x) we will assume that the distributions are separable.
Definition 3 (Separability). A distribution over X x y is separable if there exists partition (X)) of X such that p(y Xx) for some ys and all E [m)). We denote the associated deterministic label assignment as X - v.
34

---

Under review as a conference paper at ICLR 2023
Table 7: Target shift CIFARIO with ResNet-18.
FIDEM
FedAvg
Average accuracy
0.6004
0.0076
0.4426 + 0.0291
Client accuracy
0.6714
0.0153
0.3984 = 0.1497
Client accuracy
0.8196 0.0962
0.7307 + 0.1533
Client accuracy
0.5412 0.0776
0.3333 + 0.2251
Client accuracy
0.5087 0.0827
0.3030 + 0.1106
Client accuracy
0,4610 0.0508
0.4476 + 0.3649
Table 8: CIFARIO target shift distribution.
Class
0
2
3
4
5
6
8
9
Train
28
28
28
28
28
4885
28
28
28
28
Client
Test
977
5
5
5
5
5
5
Train
28
28
28
28
28
28
4885
28
28
28
Client
Test
5
977
5
5
5
5
5
5
Train
28
28
28
28
28
28
28
4885
28
28
Client
Test
5
977
5
5
5
5
5
5
Train
28
28
28
28
28
28
4885
28
Client
Test
5
5
5
977
5
5
5
5
5
Train
28
28
28
28
28
28
28
4885
Client 5
Test
5
5
5
5
977
5
5
5
5
5
Proposition 4. Assume that the distributions yd (x, y) and p" y) are both separable. Then the ratio can be computed based on the associated label == g(x) as follows,
100pppaar p²a(y) r(x)
(0.1)
(x)
Proof. Due separability, p¹ p²*(y(x) = pr' (g/x). So
(x)
(x) v) (x)) (x 8)  (x (v) (x
(x))x"(()lx))
r(x)
(0.2)
p(r(x)
follows that,
(x v)
(0.3)
nd (x,y)
Using the definition of the target shift assumption, pd 1xx((( y) = pd (xly), the conditional distributions cancel and we obtain the claim.
Proposition 4 provides way compute the ratio r(x) when the labels available and the shift is known.
O.2 COVARIATE SHIFT
The color flipping probability used to generate each of the colored MNIST datasets for the covariate shift experiment can be found in Table 12. We consider an asymmetric client setup where client in addition has 40 times less training examples than client
O.3 VERIFYING ASSUMPTIONS
Consider the two datasets used for the main experiments in Table I and Table 2. We verify in Figure that the eigenvalues of the training distribution and test distribution each client satisfy
E (0,
I+vT+45 in Theorem 2.
x
2
35

---

Under review as a conference paper at ICLR 2023
Table 9: Fashion MNIST target shift distribution.
Class
0
3
5
8
9
Train
34
34
34
34
5862
34
34
Client
Test
977
5
5
5
5
5
5
Train
34
34
34
34
34
34
5862
34
34
34
Client
Test
5
977
5
5
5
5
5
Train
34
34
34
34
34
34
34
5862
34
34
Client
Test
5
977
5
5
5
5
5
Train
34
34
34
34
34
34
34
34
5862
34
Client
Test
5
977
5
5
Train
34
34
34
34
34
34
34
34
34
5862
Client
Test
5
5
977
5
5
5
Table 10: Fashion MNIST with target shift across two clients.
FIDEM
FIIDEM
FedAvg
Average accuracy
0.82 + 0.00
0.76 + 0.01
0.76 + 0.01
Client accuracy
0.89 + 0.01
0.80 0.02
0.94 0.00
Client 2 accuracy
0.74 + 0.01
0.71 + 0.02
0.58 + 0.01
P COMPUTATIONAL COMPLEXITY OF ALGORITHM
We note that clients compute the ratios in parallel where each client needs to estimate one ratio. To estimate density ratios for FIDEM, clients require send few unlabelled test samples only once. The server shuffles those samples and broadcasts the shuffled version to clients only once. Compared FedAvg, the additional computational cost per client O(TNx) where T is the number of iterations for Algorithm to converge and N₃ is the number of batches for ratio estimation. Compared baseline FedAvg, the additional computation FIDEM is negligible but leads to substantial improvements of the overall generalization in settings under challenging distribution shifts.
Q LIMITATIONS
In this paper, focus settings where ratio estimation is required prior to model training. Handling distribution shifts in complex non-stationary settings where ratio estimation is an ongoing process is interesting problem for future work.
In addition, various personalization methods have been proposed to improve fairness in terms of uniformity of model performance across clients (Li al., 2021a;b). To meet specific requirements of each client, our global model can be combined with personalized model on each client. Developing new variants of FIDEM with a focus on fairness is interesting problem for future work.
Table 11: Two-client Fashion MNIST. The number of samples for each class the different datasets.
Class 5
0
3
8
9
Train
100
100
100
100
100
100
100
100
100
100
Client
Test
9
9
9
990
990
990
990
990
Train
39
39
39
39
39
3986
3986
3986
3986
3986
Client
Test
990
990
990
990
990
9
9
9
36

---

Under review as a conference paper at ICLR 2023
Table 12: For covariate shift the datasets for each of the client are constructed using di diffeeent probabilities.
pf
(x)
pl
(x)
p2
(x)
P2 (2"())
Probability of flipping color
0.5
0.2
0.2
0.8
1.6
Clent
12-
Giant 1
Clent
Glant2
Cient
1.2
Clent
Clent
3.0
0.6
0.6
0.4
0.0
100
200
300
400
500
600
700
800
500
5000
1500
2000
A
Figure The squared ratio of eigenvalues ordered in descending order are all below thus satisfying
X,
(o. -
1444
in Theorem 2. The sudden increase ratio lowest eigenvalues are most likely numerical emror.
Table 13: Estimating ratio upper bound with k-means clustering. We consider the target shift setup, such that
tight upper bound is known, and construct single client variant for simplicity. We specifically consider MNIST with a label distribution during training and testing to be 9" (2/20, 3/20, 1/20, 3/20, 1/20, 1, 1, 1)1)) and 97 x (1, 1, 1, 1, 1/20, 1/20, 1/20, 1/20, 1/20) respectively. The table shows the estimated upper bound on the ratio (7) for range of clustering sizes. A reasonable estimate of the true maximal ratio of 20 is obtained for wide range of clustering sizes. Whereas naively binning the space be problematic due division by zero, the clustering approach is less prone this issue as long as # (clusters) < # (datapoints).
# (clusters)
10
20
40
50
100
200
500
10.31
15.48
19.08
27.41
31.47
32.84
206.76
37

---

Under review as a conference paper at ICLR 2023
To estimate frx (x)(x)]<= clients need to send unlabelled samples xi,j for 1 E [K] and E [n**] from their test distributions. We note that instead of their true samples, clients can alternatively send samples generated from generative model (Goodfellow al., 2020).
Note that training GANs may be computationally extensive due to required computational resources and availability of representative samples. However, we propose use GANs as an alternative method with clear caveats, only when 1) clients have sufficient computational resources and 2) they unwilling share unlabelled data with the server.
As partial mitigation of privacy risks, we introduced FIDDEM. FIDDEM does not require any data sharing among clients and does not require any GAN training. In this paper, focus FIDEM since it outputs an unbiased estimate of minimizer of the overall true risk, and enables us to theoretically show the benefit of importance weighting in generalization.
One particular challenge in real-world cross-device FL is to estimate ratios on real-world datasets such as WILDS (Koh et al., 2021) and LEAF (Caldas et al., 2019). WILDS has been mostly used for domain generalization, where the setting is not similar to ours. We still have to decide on an arbitrary test/train split. LEAF mainly captures inter-client distribution shifts and settings where different clients have different numbers of examples over thousands of clients. This work is not about scalability to thousands of clients experimentally using our single GPU simulated setup. While we anticipate efficient ratio estimation will improve over time, our FIDEM and FIIDEM formulations along with improved ratio estimates will provide reasonable solutions to learn an effective global model in real-world cross-device FL under covariate shifts.
38


Reviews:
[{"review_id": "xLIiUSTd0SB", "reviewer": "Reviewer_S6qR", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 focuses on the covariate shift in the federated learning framework. In sec 2.2, they formulate FIDEM and show that it is consistent. Also, they briefly discuss its modifications in terms of privacy. The modified objective function is named as FIIDEM. In Sec 3, they discuss the estimation of the ratio $r_k(x)$ in Eq. (3.1). The detailed estimation procedure is discussed in Sec. 3.1 and Sec. 3.2. The theoretical guarantee is in Sec. 4. In Sec 4.1, they study the estimation of $\\hat{r}_k$ and put the result in Theorem 1. In Sec 4.2, they consider the ridge regression as an illustrative example to show FIDEM outperforms the classical ERM in reducing the regret. In Sec. 5, they present the numerical results and draw the conclusions iin Sec. 6.", "summary_of_the_review": "Although this paper is well written, it contains serious problem such as using the testing information during training. \nAlso, certain claims are not accurate (see my comments above). ", "strength_and_weaknesses": "Strength: \nFirst, this paper consider a very interesting issue. Also, it is well written and can convey its basic ideas to the readers. \n\nWeakness:\n1. The biggest concern is that FIDEM contains the probability $p^{\\textup{te}}_{\\ell}$ (c.f. Eq. (2.1)). This information is w.r.t. the testing data and should not be used in training. \n\n2. Certain statement is not correct. In Prop. 1, they claim FIDEM __converges in probability to the optimal solution__. Notice that __converge in probability__ has a specific meaning in probability. It is used to distinguish with the concepts __converge in distribution__, __almost sure converge__, and $\\ell_p$ converge. After checking their proof, I think the authors actually mean __convergence in distribution__. Also, their proof is not complete. They should also prove that they can switch the order of $\\min$ and $\\lim$. \n\n3. The notation is a little messy. In Thm.2, the regularization coefficient $\\lambda$ is not stated explicitly and it is in a very similar form of the $\\lambda_i$ (the probability).\n\n4. Also, the indexing is not consistent between the main context and supplementary material. For example, Proposition 1 in the main context is denoted as Proposition 2 in the supplementary material.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "VRnOdX4S0r", "reviewer": "Reviewer_Vgm5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an important sampling approach to handle inter and intra client distribution shifts in the federated learning setting. To this end, the authors propose Federated Importance-weighteD Empirical risk Minimization (FIDEM) algorithm to optimize a global FL model, along with new variants of density ratio matching methods, in particular \na histogram-based density ratio matching method. Then, we introduce another variant dubbed as FIIDEM) that  does not require any form of data sharing among clients and enjoys the same level of privacy and same communication costs as FedAvg.\n", "summary_of_the_review": "Overall, the paper studies an interesting question in learning from multiple heterogeneous data sources, but I did not find the theoretical results and proposed algorithm novel/exciting enough due to issues discussed above. Also, I have concern about the applicability of algorithms to FL as advertised by authors which makes me lean toward rejection.\n", "strength_and_weaknesses": "The proposed density ratio matching method is a natural generalization of existing methods to federated settings with a binning technique to achieve this goal which can be implemented in parallel in a simple way: clients first share unlabelled test samples with the server. The server returns the randomly shuffled pool of samples to all clients. On the theoretical side, the authors provide bounds on the error of estimating ratios, and generalization of  FIDEM. I have a few concerns about the results:\n\n- Consider a simple setting where there are $n$ users, $n/2$ with data sampled from distribution $\\mathcal{D}$ (e.g., covariance $\\Sigma$) and the rest from $-\\mathcal{D}$ ($-\\Sigma$). In this case, understanding it is an extreme case, if we shuffle the data, with high probability no client can make informative ratio estimates due to discrepancy among distributions. But I was not able to infer this from the derived bound.\n\n- I appreciate authors who honestly mention that  clients need to compromise some level of privacy and share unlabelled test samples with the server, but this is too restrictive in FL. Moreover, in an FL setting, usually the number of clients is assumed to be extremely large (at least in cross-silo) each with possession of a small data set. Since the error of standard empirical discrepancy estimation methods between pair of data sources $i$ and $j$, which also applies to ratio estimation, is bounded by $O\\left(1/\\sqrt{n_i} + 1/\\sqrt{n_j}\\right)$ where $n_i$ and $n_j$ are number of samples in data sources, I am not sure how these methods can be applied to cross-device FL (would be more suitable to cross-silo setting with no privacy concern).\n \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OXX6hxE6caL", "reviewer": "Reviewer_rE23", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose FIDEM, a framework (i.e., modeling choice) to compute a parameter which minimizes the average population risk over all clients. Their proposal is essentially sample average approximation with use of importance reweighting. They identify a quantity which is useful in this computation: the sum of density of the test distributions over the train distribution of a given client (see eqn. 3.1). They then propose DRM for estimating this ratio. ", "summary_of_the_review": "I currently recommend that this paper is rejected. The methodology is relatively standard (importance reweighting). While the authors do propose some new HDRM estimator for the likelihood ratio, the formulation in the case of only inter-client shift (but no intra-client shift), as well motivated by recent surveys (e.g. Kairouz et al) on FL, is highly problematic, as it introduces greater variance (e.g. from estimating a likelihood ratio). \n\n", "strength_and_weaknesses": "My main concern with this paper is that the formulation is problematic in the case of no intra covariate shift. In particular, imagine that you have K clients, all of which have no internal shift (i.e., their train and test distributions are the same), yet their covariate laws are different. In the notation of this paper you have $p_i := p^{\\rm tr}_i = p^{\\rm te}_i$ for all i, but $p_i \\neq p_j$ for distinct $i,j \\in [K]$. \n\nIn the setting described above, FIDEM is attempting to minimize the average risks across all the clients, but still employs likelihood-reweighting, which will lead to greater variance but with no gain in de-biasing. This is not necessary. In this case, one can simply minimize the average empirical risks (i.e., minimize the sum of the client loss over all the network only reweighting by the number of samples on each client) --- and this will be an unbiased approximation of the average empirical risk. The authors need to justify why this formulation is beneficial in this (important) setting. For instance, look at equation (C.1). The approach suggested here amounts to debiasing the estimate for R_1 and R_2, even though this does not matter from the perspective of minimizing the sum of the two risks. \n\nOtherwise, my concern is that this paper is not very original. The main contribution of this paper (from a technical perspective) is the identification of the quantity r_k(x) as given in equation (3.1). This is very straightforward, and is essentially moving one sum inside another. Not only that, the authors themselves cite papers of Sugiyama et al, which has proposed reweighting ERM. This is not at all a new observation beyond moving a sum inside another for $K > 2$ (typically prior work on IW-ERM uses just a two client setting, but this is a very minor technical detail.)\n\nFinally, the authors' assumptions regarding their likelihood ratio estimation procedure are very strong. Their condition assumes that all the train and test distributions are mutually absolutely continuous with respect to one another. This for instance, precludes the possibility that the train and/or test distributions of different clients have any difference in their supports. We know this is not necessary, for instance, in the setting of a well-specified linear model, in which case, the only requirement to learn under covariate shift is that the distributions all place some mass in all subspaces (but note that is is possible to have different supports). \n\nI would also point out that the experimental evaluation is lacking greatly. The majority of the paper studies covariate shift, yet only one example is given and the result is quite similar to FIIDEM. Finally, the authors should provide more evaluations on e.g. image tasks, as have been proposed by others in the community (e.g. the WILDS datasets, LEAF datasets, etc.)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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": "5Q9vNt7aZS", "reviewer": "Reviewer_Yvya", "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 focuses on federated learning under covariate shift using direct density ratio estimation. This work establishes high-probability generalization guarantees and the benefit of importance weighting in terms of excess risk through bias-variance decomposition in a ridge regression problem. The experimental results of the proposed method is significantly better than the vanilla federated averaging in Fashion-mnist and C-mnist datasets.", "summary_of_the_review": "This paper will benefit from a significant restructure and rewriting to make the theoretical results more connected with each other and expand the experiments. How federated learning imposes new challenges to the analysis and methodology should also be emphasized. ", "strength_and_weaknesses": "Strength:\n\nEven though the theory is built on a set of previous works, the results under the federated setting is new.\n\nThe empirical results are impressive.\n\nThe result also covers cases when the covariate shift correction is working better than ERM.\n\nWeakness:\nThe experiments are not relevant to the theory. For example, for theorem 2, it would be nice to have it validated in the experiments.\n\nThe new federated learning setting is similar to the covariate shift to me. Most of the analysis under vanilla covariate shift can be easily applied to the federated learning setting. I may be wrong, but at least it is not that clear in the paper what is the hard part of generalizing analysis on the nnBD to federated learning.\n\nThe analysis on nnBD is general while the analysis for the excess risk is for rigid regression and also for one-hot cases. They are not that connected, so we do not know how to think about the whole federated learning in an end-to-end fashion. From the literature, it seems the two analyses are rooted in different lines of previous research. It would be nice to build a more natural connection between them.\n\nThe experiments are limited that more real federated learning settings should support the proposed method. \n\nTarget shift is a slightly different setting than covariate shift even though important weighting is still an effective method there. However, in target shift, you do not need nnBD methods for density ratio estimation. So I am not sure why it is included in the experiments.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject