Federated Learning under Covariate Shifts with Generalization Guarantees
Authors: Ali Ramezani-Kebrya
Fanghui Liu
Thomas Pethick
Grigorios Chrysos
Volkan Cevher
Venue: Accepted by TMLR ()

Abstract: This paper addresses intra-client and inter-client covariate shifts in federated learning (FL) with a focus on the overall generalization performance. To handle covariate shifts, we formulate a new global model training paradigm and propose  Federated Importance-Weighted Empirical Risk Minimization (FTW-ERM) along with improving density ratio matching methods without requiring perfect knowledge of the supremum over true ratios. We also propose the communication-efficient variant FITW-ERM with the same level of privacy guarantees as those of classical ERM in FL. We theoretically show that FTW-ERM achieves smaller generalization error than classical ERM under certain settings. Experimental results demonstrate the superiority of FTW-ERM over existing FL baselines in challenging imbalanced federated settings in terms of data distribution shifts across clients.

Published in Transactions on Machine Learning Research (06/2023)
Federated Learning under Covariate Shifts with Generalization Guarantees
Ali Ramezani-Kebrya' Deportment of Informatics, University of Oslo and Visual Intelligence Centre
ali
Fanghui Liu"
fanghuui fanghoui.Buuteeee luuteppf.ccc
Laboratory for Information and Inference Systems (LIONS), EPPL
Thomas Pethick"
thomas.pethickklepf..dd
Laboratory for Information and Inference Systems (LIONS), EPFL
Grigorios Chrysos
grigoriasschrrssseeepp
Laboratory for Information and Inference Systems (LIONS), EPFL
Volkan Cevher
wolkan..ccherr@epf..c.
Laboratory for Information and Inference Systems (LIONS), EPFL
Reviewed on OpenReview: https: operreview. net/ forum?? id- iS
Abstract
This paper addresses intra-client and inter-client covariate shifts in federated learning (FL) with focus on the overall generalization performance. To handle covariate shifts, we formulate a new global model training paradigm and propose Federated Importance- Weighted Empirical Risk Minimization (FTW-ERM) along with improving density ratio matching methods without requiring perfect knowledge of the supremum over true ratios. We also propose the communicationn-effcieent variant FITW-ERM with the same level of privacy guarantees as those of classical ERM in FL. We theoretically show that FTW-ERM achieves smaller generalization error than classical ERM under certain settings. Experimental results demonstrate the superiority of FTW-ERM over existing FL basclines challenging imbalanced federated settings terms of data distributiin shifts across clients.
1 Introduction
Federated learning (FL) (Li et al., 2020; Kairouz et al., 2021; Wang et al., 2021) is efficient and powerful paradigm to collaboratively train a 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 minimization (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 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 disease data for training and test a 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 commuiccation costs.
*These authors contributed equally this work. This work was partially done while the first author was LIONS, EPFI.

---

Published in Transactions on Machine Learning Research (06/2023)
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 modily 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 cstimation method under stringent privacy requirements of FL,; 3) are there theoretical guarantees for the modified ERM under the improved density ratio method in FI.?
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; Uchara et al., 2020; Tripuraneni et al., 2021; Zhou & Levine, 2021).* To be specifie, for any client k,
Server
Racaoenly shagiled pool of smisholled test samples
Clients posallel:
Egaaaae importaace ratios
Cumpuic gradiens (FTW-ERM)
Receive agaregated panunciens
trin sample
Shaffle uniabelled sumple Condients/mdddl updres
Giobal model aininizinng orienal
Ommhantiomoid upiaic computsi
appling imporaacee
covariate shift assumes marginal train distributions Pkc (x) and marginal test distributions (x) can be arbitrarily different; while the conditional distribu- tion P (y/x) = pk (y/x) == p(y|ss (x) remains the same, which gives rise to intra-client and inter-client covari- ate shifts. Handling covariate shift is a challenging issue, especially in federated settings (Kairouz al., 2021).
Trap Test
TeaiTrain
Tess
Trai
Traje
Teod
Train samples
Train samples
samples
Clients
Figure 1: An overview of FTW-ERM. Marginal train and test distributions of clients are arbitrarily different leading intra-client and inter-client coveriate shifts. To control privacy leakage, the server randomly shuffles unlabelled test samples and broadcasts to the clients.
To this end, motivated by Sugiyama et al. (2007) under the classical covariate shift setting, we propose
Federated Importance- Weighted Empirical Risk Minimization (FTW-ERM), that considers covariate shifts across multiple clients in FL. We show that the learned global model under intra/inter-cliee covariate shifts is still unbiased in terms of minimizing the overall true risk, i..., FTW-ERM is consistent in FL. To handle covariate shifts accurately, we propose histogram-based density ratio matching method (DRM) under both intra/inter- /erittteerllene distribution shifts. Our method unifies well-known DRMs in FL, which has its own interest in the distribution shift community for ratio est.imation (Zadrozny, 2004; Huang et al., 2006; Sugiyama et al., 2007; Kanamori et al., 2009; Sugiyama et al., 2012; Zhang et al., 2020; Kato & Teshima, 2021). To fully climinate any privacy risks, we introduce another variant of FTW-ERM, termed as Federated Independent Importance- Weeihtte Empirical Risk Minimization (FITW-ERM). 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 baselin federated averaging (FedAvg) (McMahan al., 2017). An overview of FTW-ERM is shown in Fig. 1.
1.1 Technical challenges and contributions
Learning on multiple clients in FL under covariate shifts via importanco-weigheee 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 a key step for non-negative Bregman divergence (nnBD) DRM. Our work handles inter inter/inter-client distribution shifts in FL;
2) It is challenging to obtain per-client bounds on ratio estimation error for a general nnBD DRM with multiple clients and imperfect estimates of the supremum due to intra/inter- /ite/eeeee-llentt couplings in ratios. Note that, even if we have access to perfect estimates of density ratios, it is still unclear whether importance-weighter ERM results in smaller excess risk compared to classical ERM. Our work gives initial attempt by providing an alfirmative answer for ridge regression;
3) While well-established benchmarks for multi-client FL have been used, they are usually designed in a way
'Qr results can be extended to other typical distribution shifts, egg., target shift (Avizasdeneshell, 2022). We provide experimental results on target shift in Section 5.
2

---

Published in Transactions on Machine Learning Research (06/2023)
that each client's test samples are drawn uniformly from 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 (FTW-ERM) along with a privacy- variant (FITW-ERM), and improve nnBD DRM under FL
preserving and communication--efiiiee without requiring perfect knowledge of the supremum over true ratios.
Theoretially establish high-probability guarantees on ratio estimation error 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 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 et al., 2016) on CIFAR10 (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 general setting under intra hitr//inter-llien covariate shifts, provide an in-depth theoretical understanding of learning with FTW-ERM via general DRM, and experimentally validate the utility of the proposed framework. We hope that our work opens the door to a new FL paradigm.
1.2
Related work
In this section, we overview summary of related work. See Appendix B for complete discussion.
Federated learning. The current FL literature largely focuses on minimizing the empirical risk, under the same training/ test data distribution assumption over each client (Li et al., 2020; Kairouz et al., 2021; Wang et al., 2021). Statistical heterogeneity across clients in training-time is handled using heuristics- based personalization methods that typically do not have a statistical learning theoretical support (Smith et al., 2017; Khodak et al., 2019; Li et al., 2021b). In contrast, we focus learning under both intra-client and inter-client covariate shifts. Communicttion-effiienn complementary tochnologies, which can be used along with FTW-ERM to improve FTW-ERM's scalability and security while addressing overall generalization. Our theory focuses on cross-silo FL where a number of trustworthy and available clients under hitra/iinte-client covariate shifts learn a global model collaboratively, and our experiments extend to scenarios with 100 clients and client partial participation.
robust, and secure aggregations
be viewed
Wang et al. (2020) tackle update drifts considering variations in the number of local updates performed by each client in each communication round and focuses on minimizing the empirical risk under the same training/tess data distribution assumption over each client. Li et al. (2021c) propose FedBD to tackle inter-client feature shift by updating Batch Normalization (BN) layers locally and updating non-BN layers using Fed They consider both inter-client covariate shift and concept shift but under the same training/tess data distribution assumption over each client. de Luca et al. (2022) consider Foderated Domain Generalization and propose data augmentation to learn model that generalizes to in-domain datasets of the participating clients and an out-of-domain dataset of a non- non-participating client. They propose to use FedAvg after proper data augmentation, which is orthogonal the algorithmic design, e.g., our work. Gupta al. (2022) propose FL Games, gamo-theoretic framework for learning causal features that are invariant across clients by using ensembles over clients' historical actions and increasing the local computation under the same training/ test. data distribution assumption over each client. Different from these work, we focus on learning and overall generalization performance, i.c., minimizing the average test error over all clients, under both intra/inter-clien covariate shifts.
importancc-weightee ERM and density ratio matching. Shimodaira (2000) introduce covariate shift where the input train and test distributions are different while the conditional distribution of the output.
3

---

Published in Transactions on Machine Learning Research (06/2023)
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 et 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). Sugiyama et al. (2012) propose a BD-based DRM, which unifics various DRMs. Kato & Teshima (2021) propose an unBD-based DRM when using deep neural networks for density ratio ostimation. Our work largely differs from Kato & Teshima (2021) in our problem setting that allows multiple clients, algorithm design to estimate different ratios across clients and relax the requirement to have perfect estimates of the supremum over true ratios while controlling privacy leakage, and theoretical analyses to show the benefit of importance weighting in generalization.
Domain adaptation. Distribution shifts between a source and a target domain have been a prominent problem in machine learning for several decades (Wang & Deng, 2018; Kouw & Loog, 2019). The premise behind such shifts that data is froquently biased, and this results in distribution shifts that can be estimatod 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-based, and b) feature-based methods. In feature-based 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). Sample-based methods aim at minimizing the target risk through data in the source domain. Importance weighting is often used in sample-based methods (Shimodaira, 2000; Jiang & Zhai, 2007; Baktashmotlagh et al., 2014). However, the focus on domain adaptation has been mainly to 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 lopic 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 ct 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 a federated setting and establish generalization guarantees for FTW-ERM, respectively. Rademacher complexity has been used in FL to obtain theoretical guarantees on the centralized model (Mohri et al., 2019) and personalized model (Mansour et al., 2020). These work are different from our setting where we consider multiple test distributions under different training/test data distributions for clients and focus on the overall test error. Bias-variance decomposition is typically studied in two settings, i.e, the fixed and random design setting, which is categorized by whether the (training) data are fixed or random. This technique has been extensively applicd in least squares (Hsu et al., 2012; Diculevent et al., 2017), analysis of SGD (Jain et al., 2018; Zou et al., 2021), and double descent (Adlam & Pennington, 2020).
Notation: We use E|| to denote the expectation and |l 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 {1...., n) for an integer n. We use Z to ignore terms up to constants and logarithmic factors.
2
Covariate shift and FTW-ERM for FL
We first provide the problem setting under intra /atter client covariate shifts, and then describe the proposed FTW-ERM as an unbiased estimate in terms of minimizing the overall true risk?.
2.1 Problem setting
Let X C Rd be a compact metric space, y C IRdx, and K be the number of clients in an FL setting. Let denote the training set of client & with ny samples drawn i.i.d. from an unknown probability distribution yh on X x y.3 The lest data of client k, is drawn from another unknown probability
S =
Notations are provided in Appendix A. For notational simplicity, we use the same notation for probability distributions and density functions.
4

---

Published in Transactions on Machine Learning Research (06/2023)
distribution P on X' x y. Under the covariate shift setting (Sugiyama et al., 2007; Kanamori et al., 2009; Kato & Teshima, 2021; Uehara et al., 2020; Tripuraneni et al., 2021; Zhou & Levine, 2021), the conditional distribution (y/x) = (y(x) := p(y x) is assumed to be the same for all k, while (x) and (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 liw : X + Y, parameterized by w E IR e-g,, weights and biases of a neural network, such that (w(x) (for short h(x)) is good approximation of the label y y corresponding to a new sample x X. Let l: X X V + R__ denote loss function. In our FL setting, the true (expected) risk of client k is given by R& (hwh)) = E ((x.)))p)(xx)) (e(w (x(h)(x),))
2.2 FTW-ERM for FL under covariate shift
We assume that p (x > 0 for k E [K] and all x E X C & with X C Xtx ie., we need a common data domain with strictly positive train density, which is a common assumption (Kanamori et al., 2009; Kato & Teshima, 2021). For a scenario with K clients, we first focus on minimizing Rs (1 E [K]) under intra intra/interr /inter-clientt covariate shifts, i.c., Pk (x) * (x) for all k. We then formulate FTW-ERM to minimize the average test error over clients under covariate shifts by optimizing a global model under our FI. setting.
FTW-ERM for one client. Under (x) + pi (x) Vk, FTW-ERM focusing minimizing R, is given by:
K
min WERd
(lo vf..))
(2.1)
In Appendix C, we elaborate on four special cases of the above scenario, i.e., (x) 4 px*(x) Vk, focusing on one client under various covariate shifts and formulate their FTW-ERM's.
Proposition 1. Let E [K]. FTW-ERM in Eq. (2.1) is consistent. i.c., the learned function converges in probability to the optimal function in terms of minimizing Rs.
See Appendix C for the proof. Proposition 1 implies that, under int intra/inter-client covariate shifts, FTW-ERM outputs an unbiased estimate of true risk minimizer of client I. In Appendix C.1, we show usefulness of importance weighting under no intra-client covariate shifts but inter-client covariate shifts, which is a special and important case of our setting.
Building on Eq. (2.1) that aims to minimize R2, we now formulate FTW-ERM to minimize the average test error over all clients and explain its costs and benefits for federated settings.
FTW-ERM for K clients. Let w be the global model. For K clients under iatra/inner-clinee covariate shifts, FTW-ERM minimizes the average test error over all clients and is formulated as:
K
min P(w) weRd
=
(w)
(FTW-ERM)
where
Fe(w) 1
K Di=1
Pi (xfr.) e(b (x v.
(2.2)
(xP,)
Each client requires an estimate of a ratio in the form of sum of test densities over own train density, e.g., P/e /PL for client k. We emphasize that F&(w) should not be viewed as the local loss function of client k. Our formulation FTW-ERM is meant to minimize the overall test error over all clients given covariate shifts. To solve FTW-ERM, we employ the stochastic gradient descent (SGD) algorithm for T iterations starting from an initial parameter Wo: W++1 w.- ΣK gA (W:) where T3: > 0 is the step size, ge (w,,,) is an unbiased estimate of V (w.,), and wy is the output.
Under no covariate shift, both FTW-ERM with true ratios and classical ERM result in the same solution, which a minimizer of the overall empirical risk. The main difference happens under intra-client and inter- client covariate shifts. In those challenging settings, FTW-ERM's solution is an unbiased estimate of a minimizer of the overall tree risk, while the solution of ERM minimizes the overall empérical risk.
5

---

Published in Transactions on Machine Learning Research (06/2023)
2.3 Privacy, communication, and computation in FL
Privacy and commuicction efficiency are major concerns in FL (Kairouz et al., 2021). We elaborate them and introduce another variant of FTW-ERM with the same guarantees and costs as FedAvg.
Conmunicttion//copptttiioon costs and security benefits. Compared to classical ERM, the communication/ computational overhead of FTW-ERM is negligible.* To solve FTW-ERM, client k should compute an unbiased estimate of the weighted gradient Fw which requires a single backward pass at a single parameter w = wt- Hence, given the ratios, there is no extra computaatioal/commmnini overhead compared to classical ERM. Clients compute the ratios 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 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 quantization, sparsification, and local updating rules, can be used along with FTW-ERM on the fly. More importantly, due to importance weighting, gx (w) can be arbitrarily different from an unbiased stochastic gradient of classical ERM for client k, i.e., 1 E (x yk,,). The formulation FTW-ERM makes it "x
commuiiation//ompuaaaionnn
impossible for an adversary to apply gradient inversion altack and obtain private training data of clients (Zhu et al., 2019). In particular, the attacker cannot formulate the correct optimization problem and reconstruct client k's data unless the attacker has a perfect knowledge the ratio rx(x) = =EK p (x)) (x) that client A applies when computing (stochastic) gradients in Eq. (2.2).
Privacy. Given {rx(x) FTW-ERM efficiently minimizes the overall test error over all clients in a privacy-preserving manner. To estimate those ratios, clients can tolerate some level of privacy leakage, clients send unlabelled samples x for 1 e [K] and j [m**] 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, 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 to minimize the following surrogate objective, which we name Federated Independent Importance-Weighien Weighted Empirical Risk Minimization (FITW-ERM):
K
Th
(xf., (xx.)
min F(w) = wERd
((hw s.
(FITW-ERM)
The formulation FITW-ERM preserves the same level of privacy and same communicatiin costs as those of classical ERM, e.g., FedAvg. Ratios for FITW-ERM are obtained using local data and clients share only gradient information without sharing any data. Clients estimate and apply ratios using their own local data, which essentially modifies their local loss function. This modified local loss for FITW-ERM can be directly substituted in any formal differential privacy results for ERM such as those in (Kairouz al., 2021). However, 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, focus on the original objective in FTW-ERM.
3 Ratio estimation for FL under covariate shift
To solve FTW-ERM, client & should have access to an accurate estimate of this ratio
ΣK (x)
(x()
(3.1)
p (x)
4The analyses of computational/commniict overheads are provided Appendices P and respectively. By estimating ratios locally and absorbing into local losses, FITW-ERM can be viewed as a variant of classical FRM.
6

---

Published in Transactions on Machine Learning Research (06/2023)
Ratio estimation is key step for importance weighting (Sugiyama et al., 2007; 2012). The discrepancy between the true ratio ry for client. l in Eq. (3.1) and the estimated one using our ratio model can be measured by Epy [BD (x)) || [x(x) f leads to BD-based DRMs (Kato & Teshima, 2021; Kiryo et al., 2017):
where the Bregman divergence (BD) associated with a strictly convex
Definition (Bregman 1967). Let By (0,00) be bounded and f B, - .R be striclly conver function with bounded gradient. The BD associated with from ă to is given by BDy (² 2) f(z) - f(z) vf(2)(²-z))
Note that BZ |I 2) is convex function w.r.t. 2; however, it is not necessarily convex w.r.t. 2. The bounded By is standard assumption (Kato & Teshima, 2021), which holds in our problem since the density ralios that are imputs of BD are bounded following the assumption in Section 2.2. We estimate the supremum over truc ratios in Scction 3.2 and provide examples of f commonly used for BD-based methods in Table 4 of Appendix A. Motivated by Kato & Teshima (2021); Kiryo et al. (2017), we propose a new histogram-basse DRM (HDRM) for FI. with multiple clients. HDRM overcomes the over-fitting issue (Kiryo et al., 2017; Kato & Teshima, 2021) while providing an estimate for the upper bound Tk supxxx"" (x),,, which is a key step for non-negative BD (nnBD) DRM. We now extend nnBD DRM to FL settings.
3.1 Extension of nnBD DRM to FL
Let Hr C (r : X' + By} denote a hypothesis class for our ratios Tke e.g., neural networks with a given architecture. Our goal is to estimate rk by minimizing the discrepancy [BD f ( (x) || rx)))) which leads
to BD-based DRM for FL and is formulated in Appendix D.2. Let {x n and {x } denote unlabelled samples drawn ii.d. from distributions PE and p\", respectively, for 1 E [K]. Standard BD-based DRM is nt Jj=1 vf(r((x()) 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.c., min 87 (rx) whore
shown to suffer from an over-fitting issue where - 1
" Σ
nto
(7x) ReLU
1 n
(Tr((xE.))
n Σ
Ck
Σ
(((x(())))) + n
(x(x)x
(3.2)
ReLU(=)= = max max =), 0~ C& < = 7u== (x), f()) - V=))). Intuitively, ReLU is used for non-negativity and < Cs + acts as a regularization parameter. Substituting different I's into Eq. (3.2) leads to different variants of mnBD which covers previous work (Basu et al., 1998; Hastie et al., 2001; Gretton et al., 2009; Nguyen et 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
V[(=)= [(=), and - C(V
f()) = (=-1)² leading to the well-known least-squares importance fitting (LSIF) variant of nnBD for client k.
3.2 Estimation of the upper bound Tk
Estimating F2 = xu (x) is a key step for nnBD DRM. For single train and test distribution, it is shown that overestimating F leads to significant performance degradation (Kato & Teshima, 2021, Section which can be tuned. However, obtaining an efficient estimate of T&k is desirable, in particular when training a deep model. Here we propose a histogram-based method for estimation of Fk-
5). Kato & Teshima (2021) considered 0 < C < 1 as a
Let B C X and assume P and pf are continuous for l E [K]. Since B is connected and babesgue-measuraabe with finite measure, by applying intermediate value theorem (Russ, 1980), there exist x and * such that
Pr(X B} Vol1) and ΣK Pr(X]e E BB) +B)= =K Vol))B where Vol(B) SXEB dx.
We note that supxeB ri (x) V supxem Ex, (x) and ΣX Pi (F"") < supxed Σx, (x)
Σx
To estimate Fk we
infxer (x)
Pe (Btrr)
Infxed Pi (x)
first partition zer into M bins where for each bin Bm, there exists some ttr x,
E Bm, then we define
Fk.m Lis EB
211=1 Dx, EBx))) for m E [M]. Otherwise, Fr,m = 0. Finally, we propose
Pr(XFEB...
RF7 E. 1(x (Bm)
7

---

Published in Transactions on Machine Learning Research (06/2023)
Input:
18 Samples ((x,,)i=)) 1m (((g)) 1at 3 learning rate a, regularization A(r) and regularization
coefficient X.
Output: Ratio model parameters (0,, j for k == to K (in parallel) do Send ne samples to the server;
Server randomly shuffies and broadcasts samples {(x) In 1K fj=
to clients :
for k = to K (in parallel) do
1/n Dnd t Di E81))
Create M bins and compute fk.m
1/nk E 1(x)) EBm)
Estimate C
for t= to T do
for 1: to K (in parallel) do
for =1 1 to N₂ do
if B Di=1 B
(r (x
m),
KC B
Σド= Ei
Bi
then 2 21 (x
g+ Vo. }
E
(
KC2
+
E (r n.
K
else
g: Ve.
B EE 4x KCs B
Σ Σ 4 AA(r))):
B
Update ratio model parameters 0,, 0r ogk:
Algorithm 1: Histogram bassegram-based density ratio matching, Loops are executed in parallel on each client.
to use Ck where P. = max.fr........... Fx.M Convergence of n& to Fk is established in Appendix G. Furthermore, for high-dimensional data, an elficient implementation of HDRM using k-means clustering is provided in Appendix G. We note that the number elementary operations for computing (3.2) and its gradients per step dominates that of running the efficient k-means clustering estimate Cs.
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 C2 's in parallel. Given Cs '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. For client k, we divide unlabelled Bi B and (xte,.)) for n [Nu]. Client B
samples {x
1n. n and {x for I E [K] into N₁ batches (x) KC D.
k first computes I B
D & (rx (rx(x))n,)) Tf it. becomes negative, then apply gradient ascent step to increase this term. We may also opt to apply 1-norm or 2-norm regularizations. The details of the HDRM algorithm are shown in Algorithm 1.
Ee (1 (xF,,,)
BE
4 Theoretical guarantees
To address learning multiple clients in FL, it is essential to obtain per-client generalization bounds for general mnBD DRM with imperfect ostimates of Fy's. Even if we have access to perfect estimates of density ratios, it is still unclear the usefulness of importance weighting. In this section, we firstly study the brobabboyy guarantees on ratio estimation error of nnBD DRM under imperfect estimate of F& in terms of BD risk. We then show the benefit of importance weighting in term of excess risk through a refined biriancrinnce decomposition on ridge regression problem. Theorem Lemma 1, Theorem 2 are proved in Appendix I, Appendix I,, and Appendix M, respectively.
8

---

Published in Transactions on Machine Learning Research (06/2023)
4.1 Ratio estimation error in terms of BD risk
We establish high- probability bound on the ratio estimation error of nnBD DRM with an arbitrary f for client k in terms of BD risk given by
E((rk) (xx)) + 2 (2(x((())))))
(4.1)
where Eg == Bpp C Σ Epp Our bound for client k depends on the Rademacher complexity (Koltchinskii, 2001) of the hypothesis class for density ratio model Hr C fr: X By} w.r.t. client k train distribution P and all client's s test distributions pt for E [K]. Let (H) denotes the Rademacher complexity of function class H w.r.t. distribution p, formally defined as follows:
Definition 2. Let n E④ and p be a distribution, S {xI,..., ,xn] i.i.d. random variables drawn from p. and H be a function class. The Rademacher complezity of H. w.r.t. p given by:
(H) = Es
sup rEA
orlxx)
where {o:) are Rademacher variables uniiformly chosen from 1-1,1}.
We first make the following assumptions on (1(2) Vf(=)=- - and (2(2) = C(VS(=)= f(=))-(())))))))) -Vf(s). Assumption (Basic assumptions on E and f2). We assume 1) supzEB, max [4(=) <o; 2) e is L--ipsshitz and & is Lz-Lipschitz on X:; 3) infrem, [[(((((x(())) > 0 for E [K].
The first. two assumptions are satisfied if in[ E By) for commonly used loss functions, e-g., unnor- malized 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 (Higg--roobabiiiyy ratio estimation error bound for client k). Let ʃ be a strictly corver function with bounded gradient. Denote De supzeB, m1,2 [e((2)), fy arg min Ej (rk) and rh arg min (Ta) where Ê and E, are defined in Eqs. (3.2) and (4.1), respectively. Suppose that e and l satisfy Assumption 1, then for any 8 < 1, with probability at least --6: ô:
Eg(Pk) - Ex &
R
(H,) + Ci Σ n4
Rei Rio (H₂) + Tlog + KC exp
(4.2)
T
where T 23(1/1 CKK/n')).
Remark 1. Theorem 1 provides generalization guarantees for a general mnBD DRM in a federated setting under a strictly convex ff with bounded gradient. We make the following remarks.
1) Typically, the required number of samples to accurately estimate density ratios scales exponentially with the dimensionality of data due to the curse of dimensionality. Theorem 1 bounds estimation error without considering approximation error. The curse of dimensionality avoided when e.g., the ratio model H, is rich enough and contains the true ratio that is smooth enough.
2) Our results are general to cover various ratio models. For example, in Corollary 1 of Appendix J, we consider neural networks with depth and bounded Frobenius norm ||ll & Aw; and establish explicit ratio estimation error bounds for client & in OVV Sw.(1// + KK/ (K/V" + T log KKC,A exp (+)). 3) If the additional error due to estimation of Fx with HDRM Section 3 using M bins considered, it leads to O(K
under mild assumptions. Refer to Appendix K for details. 4) Our error bound increases with K due the structure of BD risk. Note that is in a constant order. Our goal is to show that nnBD DRM is guaranteed to generalize in general federated setting.
M
9

---

Published in Transactions on Machine Learning Research (06/2023)
4.2 Excess risk and benefit of FTW-ERM
In this section, we aim to demonstrate the benefit of importance weighting in term of excess risk through bias-variance decomposition. We consider the classical least squares problem, a good starting point to understand the superiority of FTW-ERM over ERM with gencralization guarantecs. We consider the single client setting K = 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 an unknown probability measure p. The least squares problem is to estimate the true parameter 0., which is assumed to be the unique solution that minimizes the population risk in Hilbert space H: L(O.) minøen L(0) where L(0)= == 2/ (x(x [(y - 0 x²)' Moreover, we have T(O.)= = of corresponding to the noise level. For an estimate A found by a learning algorithm such ridge regression, its performance is measured by the expected eacess risk; R(O) == [0) L(O.), where the expectation is 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_ We assume that E(c] = 0 and [[c2]= o??
We have the following lemma on the bias-variance decomposition of the ridge regression FTW-ERM estimate in the random-design setting.
Lemma 1. Let e Raxd be the training data matria. Let W = srogg(w....... w.) with wi - -x)'(x)) for i E [n]. be the regularized least square estimate with importance weighting: = arg ming E w x; y.)a + 2|101| where À is the regularization porameter. Demote O. be the true estimate, then the excess risk can be decomposed as the bios B and the variance V: E[[(Ø)] - I(O.) = B B with
B: B:=APE 0. Ew E' EW 0.]
E'
v==o.B tr (Iw WXXWWXXWWAL
where Σ= X X WX+ and E = Ex|xx"] J. 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 B and v.
One-hot case. To theoretically prove that FTW-ERM outperforms ERM in non-trivial settings, we start from the onc-hot case, along the lines of Zou et al. (2021), and strictly show that, under which level of covariate shift, the excess risk of FTW-ERM 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 {ei, .g,...,,e, eat according to the data distribution given by Pr(x = e = X₁ where 0 < A S 1 and Σ, x = 1. The class of one- hot least square instances is characterized by the following problem set: {(0.; .1,.... Aa)= 0, E H. Σ 1]. It is not difficult to show that the population second momentum matrix is Σ" = E[x;x;]] diag(Ai....,, for E [n]. Similarly, we assune that each test data follows the same scheme but with different probabilities Pr(x= = e, = X, and hence, we have E = diag(X,, ..). This is relatively simple set setting, which admits covariate shift. Take (1i, da} as the eigenvalues of X x. Since x; can only take on natural basis, the cigenvalue 14 can be understood as the number of training data that equals e, For notational simplicity, we 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.
Theorem 2. Let Ô be the estimate of FTW-ERM, 0" be the classical ERM, and & == xtpi Under the fized-design setting in the one-hot case, label noise assumption, and data correlation assumption, if the ratio w; = 1 (x:)//²² (x..) salisfies
N N
A 1 S w. S E X
(4.3)
then we have R(0) & R(0Y).
10

---

Published in Transactions on Machine Learning Research (06/2023)
Table Fashion MNIST with label shift across five clients, where each client receives different fractions of examples from each class. In this case, FTW-ERM achieves better average accuracy than the baselines.
FTW-ERM
FITW-ERM
FedAvg
Average accuracy
0.8245 + 0.0111
0.7942 = 0.0096
0.5475 + 0.0093
Client 1 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: Average, worst-case, and best-case client accuracies of CTFAR10 target shift. experiment 100 clients
where 5 randomly sampled clients participate in every round of training.
FTW-ERM FedAvg
FedBN
Average client accuracy
0.7658
0.7237
0.4934
Worst client accuracy
0.6163
0.5403
0.1678
Best client accuracy
0.9016
0.8904
0.8233
Remark 3. We have the following remarks:
1) The condition (4.3) equivalent to V (o, 1+ 1++1 which requires the training and test data 2
to behave similarly in terms of eigenvalues, avoiding significant differences under distribution shifts for lcarnability. Other metrics, e.g,, similarity on eigenvectors (Tripuraneni et al., 2021) also coincide with the spirit of our assumption.
2) The ratio matrix W E Raxx However, we only need its top eigenvalue, i.e., the top-d ratios. In particular, the last d ratios have no effect on the final excess risk. This makes our algorithm robust noise and domain shift.
3) For the special case by taking the ratio as w. =
we have
X
10.),.
1(0) (0,),|²>,
B(O) = X
[1:t0 + x]2
#4
x
which implics that the ratio can be regarded as an implicit regularization (Zou et al., 2021).
5 Experimental evaluation
In this section, we illustrate conditions under which FTW-ERM is favored over both Federated Averaging (FedAvg) (McMahan et al., 2017), FedBN (Li et al., 2021c), and FITW-ERM. For MNIST-based experiments we use a LeNet (LeCun ct al., 1989) with cross entropy loss and compute standard deviations over independend executions. For CIFARIO-based experiments we use the larger ResNet-18 network (He al., 2016). Further implementation details can be found in Appendix O.
Target shift. We consider the case of target shift where the label distribution p(y) changes but the conditional distribution p(xly) remains invariant. We split the 10-class Fashion MNIST dataset between 5 clicnts and simulate target shift by including different fractions of examples from each class across the training data and lest data. We further consider the separable case in order to compute the exact ratio for FTW-ERM and FITW-ERM in closed form. The specific distribution and the construction of the ratio can found in Appendix O.1. The results Table illustrate that FITW-ERM can outperform FedAvg on average while preserving the same level of privacy. By relaxing the privacy slightly the proposed FTW-ERR improves Fed Avg uniformly across all clients. Even though the proportions of the classes have been artificially
11

---

Published in Transactions on Machine Learning Research (06/2023)
Table 3: challenging binary classification task on Colored MNIST with covariate shift across two clients. FTW-ERM is close to the idealised baseline that ignores the spurious correlation (Grayscale).
Upper Bound (Grayscale)
FTW-ERM
FITW-ERM
FedAvg
Average accuracy
0.68 + 0.01
0.66 + 0.01
0.63 0.00
0.58 + 0.01
Fashion MNIST
CMNIST
166
Ciient
Client
Client
Client
1.0
1.2
Client
Client
1.0
0.6
0.4
0.4
0.0
0.0
Figure 2:
The squared ratio of eigenvalues ordered in descending order all below 1 thus satisfying V x
(o. 1+ 1+444 in Theorem 2. The sudden increase in the ratio for the lowest eigenvalues most likely due to numerical error occuring when the eigenvalues are close to zero (ef. Figure 3).
created, we believe that this demonstrates a realistic scenario where clients have a 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 O.1 where FTW-ERM is observed improve uniformly over FedAvg.
To model scenario closer to real-world FL, consider setting with 100 clients CIFAR10 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 6 and experimental results can be found in Table 2. We observe that FTW-ERM uniformly improves the test accuracy when compared with FedAvg and FedBN Li et al. (2021c) and that the gap is especially large between the worst-performing clients. The difficulty of FedBN under partial participation is most likely due how the method performs batch normalization. The batch normalization parameters are only maintained locally each client and are consequently only updated when the given client is sampled. For experiments under full participation see Table 7.
Covariate shift. We now focus on covariate shift, where p(x) undergoes a shift while p(ylx) remains unchanged. For this setting, we extend the Colored MNIST dataset in Arjovsky al. (2019) to the multi-client setting. The dataset is constructed by first assigning binary label 0 to digits from 0-4 and label for digits between 5-9. The label is then flipped with probability 0.25 make the dataset non-separable. A spurious correlation is introduced by coloring the digits according to 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.e. provides an upper bound, and referred as Grayscale. FTW-ERM outperforms both basclines in terms of the average accuracy even in two-client setting. FTW-ERM is also close Grayscale upper bound that by construction ignores the spurious correlations.
12

---

Published in Transactions on Machine Learning Research (06/2023)
Verifying assumptions. Consider the two datasets used for the main experiments in Table and Table 3. We verify in Figure 2 that the eigenvalues of the training distribution and test distribution for each client. satisfy
Ni E 1
2 ())
in Theorem 2.
6 Conclusions and future work
In this work, focus on FL under both intra-client and inter-client distribution shifts and propose FTW-ERM to improve the overall generalization performance. We establish high-probability ratio estimation guarantees for general DRM method in federated setting, We further show the benefit of importance weighting in term of excess risk through bias-variance decomposition in a ridge regression problem. Our theoretical guarantees indicate how FTW-ERM can provably solve a learning task under distribution shifts. We experimentally evaluate FTW-ERM under both label shift and covariate shift cases. Our experimental results validate that under certain covariate and larget shifts, the proposed method can learn the task, while baselines such vanilla. federated averaging fails to do We anticipate that methods to be applicable in learning from e.g., medical data, where there might be arbitrary skews the distribution. In addition, believe our study can further encourage the investigation of distribution shifts in FL, as this is critical subject for learning across clients.
Acknowledgments
This work was supported by the Hasler Foundation Program: Hasler Responsible AI (project number 21043) and by the Swiss National Science Foundation (SNSF) under grant number 200021_ 205011.
The work of Ali Ramezani-Kebrya was supported by the Rescarch Council of Norway, through its Centre for Research-based Innovation funding scheme (Visual Intelligence under grant no. 309439), and Consortiun Partners.
References
Ben Adlam and Jeffrey Pennington. Understanding double descent requires fine-grained bias-variance decomposition. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communicttion-fffiicnttt SGD via gradient quantization and encoding. In Advances Neural Information Processing Systems (NeurIPS), 2017.
Martin Arjovsky, Téon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint (XXt::1977002800 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--6 6584, 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. IEFE transactions Information Theory, 44(2):525 536, 1998.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research (JMLR), (.Nov.):463344)) 2002.
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Annals of Statistics, 49771777777 2005.
13

---

Published in Transactions on Machine Learning Research (06/2023)
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-55) 559, 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. In Conference on Computer Vision and Pattern Recognition. (CVPR), pp- 3722-372 -731, 2017.
Olivier Bousquet and André Elisseefft. Stability and generalization. Journal of Machine Learning Research (JMLR), 2:499-526, 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 217, 1967.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: A benchmark for federated settings. In Advances in Newral 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 Kellenborger, Rémi Flamary, Devis Tuia, and Nicolas Courty. DeepJDOT: Deep joint distribution optimal transport for unsupervised domain adaptation. In European Conference on Computer Vision (ECCV), 2018.
Debasmit Das and CS George Lee. Unsupervised domain adaptation using regularized hyper-graph matching. In IEEE International Conference on Image Processing (ICIP), 2018.
Artur Back de Luca, Guojun Zhang, Xi Chen, and Yaoliang Yu. Mitigating data heterogencity in federated learning with data augmentation. arXio preprinl ar arXin:2206. Xii:22000009799, 2022.
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):1305 1511, 2013.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger convergence rales for least-squares regression. Journal of Machine Learning Research, 18(1):3520 3570, 2017.
Jian-Hui Duan, Wenzhong Li, and Sanglu Lu. FedDNA: Federated learning with decoupled normalization-layer aggregation for non-IID data. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2021.
Fartash Faghri, Iman Tabrizian, Mia Markov, Dan Alistarh, Daniel M. Roy, and Ali Hamezani-Kebryee Adaptive gradient quantization for data-parallel SGD. In Advances in Neural Information Processing Systems (NewrIPS), 2020.
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 (NeurIPS), 2020.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. conain-adversarian training of neural networks. Journal of Machine Learning Research (JMLR), 17(1):2000 20000-2000, 2016.
Elnur Gasanov, Ahmed Khaled, Samuel Horváth, and Peter Richtárik. FLIX: A simple and communication- efficient alternative local methods in federated learning. In International Conference on Artificial Intelligence and Statislics (ATSTATS), 2022.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma. Neural compulation, 4(1):1-58; 1992.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Tn Conference On Learning Theory, pp. 297-299, 2018.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Commanications of the ACM, 63(11): 139 109-144,900 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.
Sharut Gupta, Kartik Ahuja, Mohammad Havaei, Niladri Chatterjee, and Yoshua Bengio. FL Games: A federated learning framework for distribution shifts. orXiv preprint ar Xrx::2200. (tt::225511101, 2022.
Hirotaka Hachiya, Masashi Sugiyama, and Naonori Ueda. Importance-weighted least-squares probabilistic classifier for covariate shift. adaptation with application to human activity recognition. Newrocomputing, 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árík. Lower bounds and optimal algorithms for personalized federated learning. In Advances in Neural Information Processing Systems (NewrIPS), 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 Conference on Computer Vision and Pottern Recognition (CVPR), 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 Advonces in Neural Information Processing Systems (NeurIPS), 2006.
Pratock Jain, Sham Kakade, Rahul Kidambi, Pranceth Netrapalli, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: mini-batching, avcraging, and model misspociffcation. Journal of Machine Learning Research, 18, 2018.
Jing Jiang and ChengXiang Zhai. Instance weighting for domain adaptation in NLP. In Annual Meeting of the Association Compulational Linguistics (ACL), 2007.
Suwicha Jirayucharoensak, Setha Pan-Ngum, and Pasin Israsena. BEG-based emotion recognition using deep learning network with principal component based covariate shift adaptation. The Sciendific World Journal, 2014.
P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. 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. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P., M. Mohri, R. Nock, A. Ozgür, R. Pagh, M. Raykova, H. Qi, D. Ramage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, Wang, L. Xiong, Z. Xu, Q Yang, F. X. Yu, H. Yu, and S. Zhao. Advances and open problems in federated learning. Foundations and T in Machine Learning, 14(1-2) 12:1- 2021.
15

---

Published in Transactions on Machine Learning Research (06/2023)
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 homo- geneity test under semiparametric density-ratio models. JEEE Transactions on Information Theory, 58(2): 708-720, 2011.
Masahiro Kato and Takeshi Teshima. Non-negative Bregman divergence minimization for deep direct donsity ratio estimation. In International Conference on Machine Learning (ICML), 2021.
Masahiro Kato, Takeshi Teshima, and Junya Honda. Learning from positive and unlabeled data with a selection bias. In International Conference on Learning Represenlations (TCI.R, 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 in semiparametric two-sample density ratio models. Comptes Rendus Mathématique, 340(12))905-914 -900, 2005.
Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient-based 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 Newral Information Processing Systems (NeurIPS), 2017.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. WILDS: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning (ICML), 2021.
Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Transactions Information Theory, 47(5):1902 1914, 2001.
Wouter Kouw and Marco Loog. A review of domain adaptation without target labels. IEEE Transactions on Pallern Analysis and Machine Intelligence (T-PAMI), 43(3):766 785, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 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, (4):541 551, 1989.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-25)) 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, Amoet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEFE Signal Processing Magazine, 37:50-60, 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, Mcirui 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
16

---

Published in Transactions on Machine Learning Research (06/2023)
Yan Li, Hiroyuki Kambara, Yasuharu Koike, and Masashi Sugiyama. Application of covariate shift adaptation techniques in brain-compute computer interfaces. IEEE Transactions Biomedical Engineering, (7(6):1318-1333) 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 in PCM. IEEE Transactions on Information Theory, 28(2):129 137, 1982.
Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting supervised classification from two unlabeled datasets: A consistent risk correction approach. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications federated learning. arXiv preprint WXXi:2002.10619 2020.
David McAllester. Some PAC-Bayesian theorems. Machine Learning, 37(3)3355 363, 1999.
Colin McDiarmid et al. On the method of bounded differences. Surveys in combinatorics, 141(1):448-188, 1989.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient. learning of deep networks from decentralized data. In International Conference on Arlificial Intelligence and Statistics (AISTATS), 2017.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning (ICML), 2019.
Arkadi Nemirovski. Topics in Non-parumetric Statistics. Ecole E'E de Probabilifes de Saint-Flow XXVIII, 1998.
XuanLong Nguyen, Martin Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Trnssctions on Information Theory, 56(11):5847 5861, 2010.
Jing Qin. Inferences for case-control and semiparametric two-sample density ratio models. Biometrika, 85(3): 619 630, 1998.
Ali Ramezani-Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M. Roy. NUQSGD: Provably communicttion-eliiient data-parallel SGD via nonuniform quantization. Journal of Mochine Learning Research (JMLR), 22(114):1 43, 2021.
Ali Ramezani-Kebrya, Kimon Antonakopoulos, Tgor Krawezuk, Justin Deschemaux, and Volkan Cevher. Distributed extra-gradient with optimal complexity and communication guarantees. In International Conference on Learning Representations (ICLR), 2023.
Sashank Reddi, Barnabas Póczos, and Alex Smola. Doubly robust covariate shift correction. In AAAI Conference on Artíficial Intelligence, 2015.
SB Russ. A translation of Bolzano's paper on the intermediate value theorem. Historia Mathematica, 7(2): 156 185, 1980.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research (JMLR), 11:2635-2613 2670, 2010.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likellodddoo function. Journal of Statistical Planning and Inference, 90(2):227-244 2444, 2000.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S. Talwalkar. Federated multi-task learning. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
17

---

Published in Transactions on Machine Learning Research (06/2023)
Alex Smola, Le Song, and Choon Hui Teo. Relative novelty detection. In International Conference Artificial Intelligence and Statistics (AISTATS), 2009.
Masashi Sugiyama and Klaus- Müller. Input-dependent 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, Takafuni Kanamori, and Manabu Kimura. Least-squares two-sample test. Neural networks, 24(7):735-751, 2011.
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density-ratio matching under the Bregman diver- gence: a unified framework of density-ratio estimation. Annals of the Institute of Statistical Mathematics, 64(5))1009-100 2012.
Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Overparameterrzation improves robustness to covariate shift in high dimensions. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Alexandre B. Tsybakov. Introduction to Nonporametric Estimation. Springer Series in Statistics, 2008.
Masatoshi Uchara, Masahiro Kato, and Shota Yasui. Off-policy evaluation and learning for external validity under a covariate shift. In Advances in Neural Informalion Processing Systems (NeurIPS), 2020.
Vladimir N Vapnik. An overview of statistical learning theory. IEEE Transactions on Neural Networks and Learning Systems (T-NN), 10(5):988-99) 1999.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogencous federated optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Aguera y Arcas, Maruan Al 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 J. Reddi, Peter Richtarik, 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 preprint arXiv:2107.06917 2021.
Mei Wang and Weihong Deng. Deep visual domain adaptation: A survey. Neurocomputing, 312:135 112,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
2017.
Semih Yagli, Alex Dytso, and H Vincent Poor. Information- bounds on the generalization error and privacy leakage federated learning. In International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), 2020.
Makoto Yamada, Masashi Sugiyama, and Tomoko Matsui. Semi-supervised speaker identification under covariate shift. Signal Processing, 90(8):2353-236) 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 (NewrIPS), 2011.
18

---

Published in Transactions on Machine Learning Research (06/2023)
Honglin Yuan, Warren Morningstar, Lin Ning, and Karan Singhal. What do mean by generalization in federated learning? In International Conference. on Learning Representations (ICLR), 2022.
Bianca Zadrozny. Learning and evaluating classifiers under sample selection bias. In Internalional Conference on Machine Learning (ICML), 2004.
Tianyi Zhang, Ikko Yamanc, Nan Lu, and Masashi Sugiyama. A ono-stop approach covariate shift adaptation. In Asian Conference Machine Learning, 2020.
Aurick Zhou and Sergey Levine. Training test data with bayesian adaptation for covariate shift. In Aduances in Newral Information Processing Systems (NeurIPS), 2021.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in Neural Information Processing Systems (NewrIPS), 2019.
Difan Zou, Jingfeng Wu, Quanquan Gu, Dean Foster, Sham Kakade, et al. The benefits of implicit regularization from SGD in least squares problems. In Advances in Neural Information Processing Systems (NewrIPS), 2021.
A Appendix
The appendix is organized as follows:
Examples of f for BD-based DRM provided in Appendix A.
Complete related work is provided in Appendix B.
FTW-ERM with a focus on minmizing Rí are provided in Appendix C.
Details of density ratio estimation are provided in Appendix D.
Communication costs of FTW-ERM and FITW-ERM are analyzed in in Appendix E.
UKL, LR, and PU variants of nnBD are provided in Appendix F.
Convergence of F and k-means clustering for HDRM are provided in Appendix G.
UKT, LR, and PU variants of nnBD for multiple clients are provided in Appendix H.
The proof of the core Theorem exists in Appendix I.
piob-brobayility ratio estimation error bounds for multi-layer perceptron and multiple clients are established in Appendix J.
Additional error due to estimation of Fs with HDRM is analyzed in Appendix K.
Lemma is proved in Appendix L.
Theorem 2 is proved in Appendix M.
counterexample under which FTW-ERM cannot outperform ERM is provided in Appendix N.
Additional experimental details are included in Appendix O.
Computational complexity of Algorithm 1 is analyzed in Appendix P.
The limitations of our work are described in Appendix Q.
19

---

Published in Transactions on Machine Learning Research (06/2023)
Table 4: Examples of for BD-based methods (Sugiyama et 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, PULogLoss = positive and unlabeled learning with log Loss.
Reference
Algorithm
f(z)
Basu et al. (1998)
Robust
g-ll_z a a>0 0
Hastie et al. (2001)
LR (BKL)
log(z))
(z + 1) 1)log(z + 1)
Kanamori et al. (2009)
LSIF
(2-1)²
Gretton et al. (2009)
KMM
(2-1)²
2
Nguyen et al. (2010)
KLIEP
log (2)
Nguyen et al. (2010)
UKL
log (2)
Kato al. (2019)
PULogLoss
C'log(1 2) Cz(log(=) - log(1 -2)), ZE (0
B Complete related work
Federated learning. One well-known method in FL is FedAvg (MeMahan et al., 2017). FedAvg and its variants are extensively studied optimization with a focus on communication efficiency and partial participation of clients while preserving privacy.
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; Faghri et al., 2020; Ramezani- Kebrya et al., 2021; Kairouz et al., 2021; Ramezani-Kebbn aggregation schemnes have been also proposed to provide robustness against training-time attacks launched by an adversary, and to compute aggrogated values without being able to inspoct the clients' local models and data, respectively (Li et al., 2020; Kairouz el al., 2021; Wang el al., 2021).
et al., 2023). Furthermore, robust and secure
Taken together, these work largely focus on minimizing the empirical risk in the optimization objective, under the same training/ taining/test 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 Icarning and overall generalization performance under both intra-client and inter-client distribution shifts. Communication--fficeeel robust, and secure aggregations can be viewed as complementary technologies, which can be used along with our proposed FTW-ERM method to improve the generalization performance. In our setting, clients can also all participate in every training iteration, such 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 FTW-ERM does not require specific assumptions on function F3 's for k E [K] to provide an unbiased estimate of true risk minimizer. Under strong convexity and smoothness assumptions w.r.t. model parameters, similar optimal algorithms to those proposed in (Hanzely et al., 2020; Gasanov et al., 2022) will be optimal for FTW-ERM.
Different from recent FL work by Duan et al. (2021) and Li et al. (2021c), our work introduces new FTW-ERM formulation and shows statistical consistency.
Importance- ERM and density ratio matching. Density ratio estimation is an important step in various machine learning problems such learning under covariate shift, learning under noisy labels, anomaly detection, two-sample testing, causal inference, chango-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 et al., 2011: Kanamori et al., 2011; Sugiyama et al., 2011; Yamada et al., 2011; Reddi al., 2015; Liu Tao, 2015; Kato et al., 2019; Fang et al., 2020; Uchara 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,
20

---

Published in Transactions on Machine Learning Research (06/2023)
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 imput train and test distributions are different while the conditional distribution of the output variable given the input variable remains unchanged. Importance weiihthee-weighteed ERM is widely used to improve generalization 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 et al., 2020; Zhang et al., 2020; Kato & Teshima, 2021). Zhang et al. (2020) proposed a one-step approach that jointly learns the predictive model and the corresponding weights in one optimization problem. Sugiyama et al. (2012) proposed Bregman divergence-basell DRM, which unifies various DRMs. Kato & Teshima (2021) proposed non-negative Bregman ivvergence-bssed DRM to resolve the overfitting issue when using deep neural networks for densily 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 prominent problem in machine learning for several decades (Wang & Deng, 2018; Kouw & Loog, 2019). The premise behind such shifts 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 categories of domain adaptation methods are most closcly related to work: a) sample-based, and b) featuro-basod methods. In feature-based methods, the goal is to find transformation that maps the source samples to target samples (Ganin et al., 2016; Bousmalis et. al., 2017: Das & Lee, 2018; Damodaran et al., 2018). Sample-based methods aim at minimizing the target risk through data in the source domain. Importance weighting is often used in sample-based methods (Shimodaira, 2000; Jiang & Zhai, 2007; Baktashmotlagh et al., 2014). However, the focus on domain adaptation has been mainly to adapt to a single target distribution, not the overall generalization performance on multiple clients, which is addressod 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), bins-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 a federated setting and establish generalization guarantees for FTW-ERM, respectively. Rademacher complexity has been used in FL to obtain theoretical guarantecs on the contralizod model (Mohri et al., 2019) and personalized model (Mansour et al., 2020). Mohri el al. (2019) considered a scenario where a 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 stest 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 a 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 catogorized by whether the (training) data are fixed or random. This technique has been extensively applied in least squares (Hsu el al., 2012; Dieuleveut et al., 2017), analysis of SGD (Jain et al., 2018; Zou et al., 2021), and double descent (Adlam & Pennington, 2020).
informationn-thorettic bounds on the generalization error and privacy leakage in federated settings were established in (Yagli et al., 2020). Under partial participation of clients, Yuan et al. (2022) proposed a framework, which distinguishes performance gaps due to unseen client data from performance gap due to unseen client distributions. Still, these work study FL under the same training/ten test data distribution assumption over each client.
21

---

Published in Transactions on Machine Learning Research (06/2023)
Table Details of scenarios described in Section
Scenarlo
# Cliients Assumptions on Distributions
What client Knows
No-US (C.1)
2
[ (x(x),
p[(x)
# (x)
pi (x)
CS on one (C.2)
2
( # pi (x), P
pi(x)/p (x), (x)x//p
CS both (C.2)
2
pi + pi
(x) P (x)
Pl (x (x), Pi (x)()// (x)
CS multi. in (C.3)
K
P (x) + p for all k
pp (x) ] for all
C FTW-ERM with a focus on minmizing R1
Without loss generality and for simplicity notation, in this section, we set | -= 1. We consider four typical scenarios under various distribution shifts and formulate their FTW-ERM with a focus on minmizing Ri. The details of these scenarios are summarized in Table 5.
Remark 4. Covariance shift (as well as its assumption) is the most commonly used and studied in theory and practice in distribution shifts (Sugiyama al., 2007; Kanamori et al., 2009; Kato & Teshima, 2021; Uehara et al., 2020; Tripuranení et al., 2021; Zhou & Levine, 2021). Handling covariate shift is 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 can be directly extended to multiple clients. This scenario assumes Pk (x) = (x) for
= 2. Client aims to learn hw assuming
(x) is given. We consider the following FTW-ERR that is
(x)
proved to be consistent in terms of minimizing minimizing R₁:
Σ E(hw WERd 11
min
E(h (x (x
(C.1)
2
Covariate shift only for client 1: (CS one) We consider covariate shift only for client 1, i.e,, (x) & (x) and p (x) = pla (x). We consider the following FTW-ERM
ni
min WERd
((h (x
ll (x Y...)
(C.2)
Covariate shift for both clients: (CS on both) We assume px)()) + p1 and (x) + ph (x), i.e., covariate shift for both clients. The corresponding PTTWERM is the same as Eq. (C.2).
Multiple clients: (CS on multi.) Finally, we consider general scenario with K clients. We assume both intra-client and inter-client covariate shifts by the following FTWWERM:
min WERd k=
E() (xt.).
(C.3)
where Σk \ and A 2 O.
Proposition 2. Let E [K]. In above settings, FTW-ERM defined in Egs. (C.1), (C.2), and (C.3) is consistent. i.e., the learned function converges in probobility to the optimal function in terms of minimizing R1.
Proposition 2 implies that, under various settings, FTW-ERM outputs an unbiased estimate of a minimizer of the true risk.
22

---

Published in Transactions on Machine Learning Research (06/2023)
Proof. For the scenario without intra-client covariate shift, FTW-ERM in Eq. (C.1) can be expressed as
(x e(hw (x2,),
22 -00
E (xp((
pf
Elliw (()x(())))))
2
(x
pi Eptyy bc) [e (x), y) pa (x) dx
x p (x)
pi (xx (x)xp(y) (0(h (x), dx
(x) (x) y) dx
(pp) (e (x(hw(x)))))
(hw).
For the scenario with covariate shift only for client 1 or for both clients, FTW-ERM in Eq. (C.2) admits
(x
(x) (x)
((hw (x2,)) v2.))
(x.))
e() (x):
2
P2 (,1)
pf((x)
E Ep(rix) [E (xx) y) Pd (x) dx
P (x)
Pi (x)
dx
Bppr (R(h (x).
(hw)..
We note that (x) (x) (x)
[x] (x) (x) which is the product of ratios due to intra-client covariate shift client
and inter-client covariate shift.
For multiple clients, let [K]. Similarly, we have
(x
(x,,), No -000
Rí (hw)
(x
Then we have
K
nt
E(h (. mf. 000
Rs (Iw)).
The consistency of FTW-ERM, i.e. convergence in probability, is immediately followed the standard arguments in e.g., (Shimodaira, (000)|Section 3) and (Sugiyama et al., 2007)\ 2.2] using the law of large numbers.
Note that to solve Eq. (C.3), client 1 needs to estimate K Remark 5. Scaling Σk= d does not affect the optimal parameters in Eq. (C.3). For rotational simplicity, we set A 1 for k E [K].
(x) for all clients with A (C.3). p (x)
C.1 No intra-client shift
In this section, we consider the important and special case of the setting described in Section 2.1 under no intra-client covariate shifts but inter-client. covariate shifts. For simplicity, consider two clients with
23

---

Published in Transactions on Machine Learning Research (06/2023)
train/test distributions P and Q whose train/test densities are denoted by p and q, respectively. We also suppose that we have a sample ~ P and x' ~ Q to learn with the goal is to find an unbiased estimate of the overall risk with the smallest variance. In this setting, the classical ERM (FedAvg) objective f(z, 0) + {(2', 0) is an unbiased estimate for the overall risk L(0) = Ep([(2, 0)] + Eole(z', 8)1. In this setting, the objective of FTW-ERM, i.e.; [((p(() + (0)) with (p) (1 +1+ p(z) (2, 0) and (0) (1 + p(a' unbiased estimate for the overall risk T(O)-
(()) ((2 0) is an
We now show that the our method (FTW-ERM) has a smaller variance than FedAvg under certain conditions. Let Ep[(((z. [p[((2, 0)]) = o and [g](((2'. 0) Eoll(z', [)]{], =Q.
For FedAvg, the variance is given by
[p -(0)) oo6
For FTW-ERM, the variance is given by
(rol)(((r(0)) + (o)) ((O)² = Vo + Vo
where === --]((((((()) [(0)) and Vo = (0)
- I(O))7]
We now expand each term Vp and Vo. We can show that
- 1
Ep [(1
g(2) ((, Epl((2, 0]] [EQ((((())) of 00
Vp =
p(z)
4
where 0%6 = Epp
(
g(=) p(z)
f(z, 0)+ Eegl((z' 01) + 2E (((2,0) -
-1)2, (p((((,)))) ((,, 0) - EE(((E,, [1]]] Sim-
ilarly, we have
Vo= = 1 Ro (
p(z!)
)((2. Er(((2,0)] Ro(e(2 011) og + 0
((21)
4
where 03 EQ [
p(=)
((2)) ((21, 0) Epl Ep 8)) + 2EQ (e(2200) Eo(((2', 011)
p( ((21 Epl((2. 01)]
((zr)
We note if 03, + o3 S 3 + oZ) then, FTW-ERM will have smaller variance than FedArg, ie., Vp + Vi2 S of + og. The exact condition depends on the loss and densitics. To show a concrcte example, for the more general and practical case with both mntra/inter-client. in Section 4.2, we show that FTW-ERM results in smaller excess risk compared to FedAvg through a refined bias-variance decomposition. Given two distributions, considering the case of no intra-client shift is a special case, where it is true that FedAvg is unbiased estimate of the overall risk. However, this unbiasedness breaks as soon as there is only one client whose test and train distributions are different, which is very common in theory and practice. Please note that FTW-ERMM is an unbiased estimate of the overall risk in a general FL setting without requiring any prior knowledge/assumpe assumptions on the potential covariate shifts.
D Ratio estimation
D.1 nnBD DRM for a single client
For simplicity, we firstly focus on the problem of estimating r(x)
(x(x) and then extend our consideration
(x)(x)
to the estimation of rx (x) in Eq. (3.1). Let r* denote the true density ratio. Our goal is to estimate y* by
optimizing our ratio model r. The discrepancy between r and r" measured by Epr [BDy(r* (x) || rxx))]
We note that Ept, (r))(r*(x) (x) |I r(x)) = Er(r + E,t- (x) where Ey(r)= = E, (Vx((((( f(((x))] Eptc (x)) Note that Ept [f(r is constant w.r.t. r. Let {x"") Jimi and (x), te 1n
1==1 denote unlabelled
For notational simplicity, we overload f(2,0) to denote the loss of model on example
24

---

Published in Transactions on Machine Learning Research (06/2023)
samples drawn ii.d. from distributions p" and p"", respectively. Let H, fr: + BB} denote hypothesis class for our model Using an empirical approximation of (x(r"(x) r(x)), Sugiyama et al. (2012)
formulated BD-based DRM problem min (r) where
t n Σ vf(((}))))
E)(r) 1 nt E Vf(((x())) f(((x+))
-
(D.1)
Sugiyama et al. (2012) showed that BD-based DRM unifics 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 issuc (Kato & Teshima, 2021; Kiryo et al., 2017). In particular, Kato & Teshima (2021) called such issue "train-loss hacking" where nt Ej=1 j-1 Vf(((x])) in (D.1) diverges if there no lower bound on this term. Even when there exists lower bound, the model r tends increase to the largest possible values of its output range at points [xte)>= 13=1- To resolve such issue, Kato & Teshima (2021) proposed to use non-negative BD (nnBD) DRM, Le., minrem, (r) where
C n (r((x))))
1 n
(r)= = ReLU
ntr Σ (r((x)))
nte Σ
ne Σ (2(r(x))))
(D.2)
ReLU(z) = ma, 0 <<C< F su r (x), (1() = vf(z)= f()), and (2(=) = C(V)(=)2
f()) - V=()). Substituting f(z) (z-1)² into (D.2), the least-squares importance fitting (LSIF) variant of mnBD is given by
(r) ReLU
2n Σ
tr
(x
C
Σ
t
(x(3))
1
50
C (r(x) (x)()))
2n
5e
2
In Appendix F, we show explicit expressions for unnormalized Kullback Leibler (UKL), logistic regression (LR), and positive and unlabeled learning (PU) variants of mnBD.
Estimating F= su (x) is a key step for density ratio ostimation. It is shown that underestimating C' leads to significant performance degradation (Kato Teshima, 2021, Section 5). Kato & Teshima (2021) considered C' as hyper- parameerr,eete, which can be tuned. However, obtaining an efficient estimate of is desirable, in particular when training a deep model.
Let B C Xtt. Assume pd and p' are continuous. Since B is connected and Lebesgue-measurabble with finite measure, by applying intermediate value theorem (Russ, 1980), there exist 5² and 4 such that Pr(X E B} = >""("") Vol(B) and PrfXte B} = p p*((e") where Vol(B) = =xeB dx. We note that
SuPxE8 r" (x) infxes (x))
supxem (x")) and ('"("") supxenp"(<) We partition X into M bins where for each bin (Btr (((x)
Ex" 16)))BB.)
for m E [M]. Otherwise, Fm Finally, we propose to use C where max FM). Convergence of f to r is established in Appendix G.
Bm, if there exists some X E Bm, then we define im = Pr( Pr(X"eBm.
Now, suppose there are K clients where each client provides n unlabelled test samples to the pool of samples. Our goal is to estimate F in Eq. (3.1) for k == 1,..., K. The BD-based DRM for client is given by min (rk) where (r(r)) = oo.
E (x,rx(x (f(x))x()))))))) a E ΣK Vf(Tx(x(g))
The mnBD DRM problem for client A is minnEE,, & (Tw) where
K
(7x) = ReLU(SI,
E (rxx(())))
(D.3)
nt
25

---

Published in Transactions on Machine Learning Research (06/2023)
11, = 1 Ei & (1xx((x)))) - C
ni Ej=1 En (1(x(xx))), < Cs < a and Tk = supxex" (x). Sub-
stituting f(z) - لللييا into (D.3), the LSIF variant of nnBD for client given by minr & (Ts) where
(rk) = ReLU(SLSIF) 1
K
C+ (((x)))))
(rx(xtt)
(D.4)
nto
2
and SLSIF 2n Li=1 r k..) 2n Ejm1 Ei (x())) We provide explicit expressions for UKL, LR, and PU variants of nnBD for client & in Appendix H.
(x
Ex (x) (
Our goal to estimate Fs = SuPxex""
For HDRM method, we first partition X into M
Dn P((X)'BBm) Pr(XPEBm]
bins where for each bin Bm, there exists some X E Bm: then we define fk.m
Dn DK (xx) EBm) for m E [M]. Otherwise, Fk.m = 0. Finally, we propose to use C₁ = 1 where
Fg max (FR,1..... F.
D.2 BD-based DRM for FL
Our goal to estimate rk by minimizing the discrepancy B (B)(((()(()))) || [x))), min (Tk) where
which is equivalent
K
(T(rR) = Bpg (xx f(rx(x)) Σ E [Vf(x(x))))
(D.5)
since Bgg: [BD E U((((() and Egg (x(((((( is constant w.r.t. Ta- Let n
(
and {x 1 denote unlabelled samples drawn i.i.d. from distributions p and p/ respectively, for E [K]. A natural way to solve min (rx))) is to substitute empirical averages in Eq. (D.5) (Sugiyama et al., 2012), leading to BD-based DRM for FL: min (r(r where
K
ET(TH)
(m(r - f(rx((H))))
(f(x((()))
nig
E
Communication costs and FITW-ERM
To estimate density ratios for FTW-ERM, clients require to send few unlabelled test samples only once. The server shuffies those samples and broadcasts the shuffled version clients only once. The communication overhead to estimate ratios is negligible compared to the communication costs for sharing high-dinensional stochastic gradients over the course of training.
Consider the example of CIFAR10 consisting of 32 by 32 images with channels represented by 8 bits. one shares 1000 unlabelled images?, the communication amounts to sharing roughly 10 values each with bits, i.e., 25 106 total communication bits or 1.M. 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 10 iterations and aggregations, which amounts to 2.816 x 10 total communicated bits per client, i.e., 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 samples shared for estimating the ratios. To further
A total number 1000 images shown to sufficient learn density ratios CIFARIO (Kato & Teshima, 2021)(10, Section 5.1"
26

---

Published in Transactions on Machine Learning Research (06/2023)
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 FTW-ERM on the fly (Alistarh et al., 2017).
Alternatively, to eliminate any privacy risks, clients may minimize the following surrogate objective, which we name FITW-ERM:
K
min F(w)
= Σ (w)
(E.1)
wERd
k=1
( where Fl(w)= = "/ Pe (xx,))
(low (x v.
We note that privacy risks are eliminated by solving E.1. However, to exploit the entire data distributed among clients and achieve the optimal global model in 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, in this paper, we focus the original objective F(w) in FTW-ERM, which is different from F(w).
F Variants of nnBD
In this scction, we show explicit expressions for unnormalized Kullback-Leible (UKL), logistic regression (LR), and positive and unlabeled learning (PU) variants of nnBD.
Substituting f(z) = z log(2) into Eq. (D.2), we have (z) and (2(2) = 2C log(z), and the UKL variant of nnBD is given by
1 n
C n
(r) = ReLU r(x
Σ
Σ Ø=1
r(x2)0)
1r 1=1
nte
(F.1)
(og(((x)")) Cr(x))))
ne
Substituting f(2) z log(2)) (z 1) log(z + 1) into Eq. (D.2), have (1() log(z + 1) and (2(2)
C'lo((z + 1) + log (*+1), and the LR (BKL) variant of nnBD is given by
C
(r) = ReLU
Σ
log(r(x{") +1)
Σ
log(r(x))) +1))
nt
nte j=1
i=1
(F.2)
n
r(x]²)
log
r(x]=) +1 C Clog(r(x)))
+
ne
j=1
Substituting f(2) = Cllog(1 - Cz(log(2) - log(1 2)) into Eq. (D.2), we have (z)) = - C. log(1 - 2) and
(2()) = -C (lg((2) (2) + (C - (2)- log(o - 2). and the PU variant of nnBD is given by
C n*
log(1 - r(x:)) + C2 nt
(r) = ReLU
log(1 r(x)
n
nte ==1
(F.3)
to
(Clog(r(x}))) (C C2) log(1 r(x)
te
G
Convergence of and k-means clustering
Lemma 2. If nt nle, and M go to infinily with supm Vol(Bm) then Tk-
27

---

Published in Transactions on Machine Learning Research (06/2023)
Proof. Let E X". Note that when ne. n²", and M go to infinity, the numerator and denominator of Fy: become Σ pi (B)) and pt (B))) respectively, where Bm.
Please note that our density ratio in Eq. (3.1) in the form of a sum of test densities over own train density. So even one a 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 but in 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 casy task when data is high dimensional. In practice, one simple method is to cluster train and lest 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, we need a batch of samples from the test distribution of cach client in addition batch of samples from the train distribution for each estimating client. The running time of Lloyd's algorithı with M clusters is O(ndx where n is the total number of samples with dimension dx-
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 & is given by min & (Fk) where
te CF to
EKK, (rw) = ReLU
rx(x))))
(H.1)
50
(log(r((x]))) Carr (xt.))
The LR variant of mnBD for client k is given by min LL (rk) where
ni Σ
C₁
K 1xg(1x(xfg) + 1))
(rk))) = ReLU
log (rx (x + +1
no
(H.2)
K
(x()))))
log
C2 log(ra (x} + +11
te
(x(
+1)
The PU variant of unBD for client given by minl,,e, (rk) where
te
C
(T)) ReLU
log(1 - rx(xx)))
log(1 - (x(())))
nt
(H.3)
K (Ce (og(rx(())))) (Cx C log(1 rx (x(9))))
n
Proof of Theorem
In this section, we prove Theorem 1, which establishes an upper bound on the ratio estimation error of nnBD DRM (HDRM method with an arbitrary f) for client k in terms of BD risk, which holds with high probability along the lines of (Kiryo et al., 2017; Lu et al,, 2020; Kato & Teshima, 2021).
We remind that client k's goal is to estimate this ratio:
ΣK
11=11i1(x (1)
(x(x)
(L.1)
P (x)
28

---

Published in Transactions on Machine Learning Research (06/2023)
For client k, the BD risk is given by
K 8f(rk) (xx))(((((xxx)))
Σ B (+2((r(x)))
(I.2)
Eis (x) xx))
where E2 == Epp Ck Σi E Bp.. CK Fe" Pk suxxxx"
[2(2) Vf(=)= f(z), and
(=)) = C(V/(=(== [())) -(()) We note that the definition of Cs implies in - - Cx > p\ > 0.
We remind that f By + R is a strictly convex function with bounded gradient Vf where B, C [0, 00), and
H4 C fr: + B denotes a hypothesis class for our model
The nnBD DRM problem for client min,, EH, Ef (Tx) where
K
K
(Tx) = ReLU ( - Cx Σ (xx)(((((xx))))) + Σ (2(x((()())))
(I.3)
1nl with Epg is the sample average over {xt and Epg is the sample average over {xt Inte
the following,
we denote E. == Epp - Ck Ei Egge for notational simplicity.
Let AS- == arg min,, EH, E (rk) and r == arg min,, (f(rk)- We first decompose the ratio estimation error into maximal deviation and bias terms:
E,(11) ((()))))())))(((())( =(( E,(ri)
< Ef,) (0) (r())
2 sup
(
(I.4)
ER..
S 2 sup 187 (rx) BBET (rx)]l+ sup TLER
-
(r()
where the second inoquality holds since fx == arg ein 87 (rx). The first term in the RHS of (I.4) the maximal derivation and the second term is the bias.
In the following two lemmas, we find upper bound on the maximal deviation supmEh, (rx) B[ē} (rw)ll and bias SUPrEEH, [ (rw)) E (rx),, respectively.
Lemma 3 (Maximal deviation bound). Denote := =up=eR, maxie(1,2) 14(()), then for any 0 < 8 < the marimal deviation term is upper bounded with probability at least 1 5
sup (Tk) B1ē (rx)]l < 4L, 4L, R" (H,) 4(CxLI + L2) ME
Σ
R (Hr)
(I.5)
K(1+CH Cx)2
+ Deg 2
+
log
1r 1/
ntee
n x te ........, xte x Let S()) be obtained by replacing element of set S₁ by an independent data point taking values from the d 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)) (( ]. If the changed point is sampled from pi then the absolute value of the difference caused in the maximal deviation term is upper bounded by 2dr w.r. If the changed point is sampled from p/e, the the absolute value of the difference caused in the maximal deviation term is upper bounded by (A+(C++1) for 1 1= 1,..., K. Applying McDiarmid's inequality (McDiarmid et al., 1989), with probability at.
Proof. Denote (Sx)) : sup sup, - (rx)] with S₁ = [x
xtr
29

---

Published in Transactions on Machine Learning Research (06/2023)
least 1 - we have
( sup 18 (Tx) ( (rx)]l T.E..
E sup EH,
18
B[ÊT (rx)]1
K(1+ x()2 Cx)2 ne
+ D ArV
2
log 6"
In the following, establish upper bound on the expected maximal deviation Elsup 187 (rk) ElE7 (rx)ll 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 Σ for M E Σ.. Let 9m R + R be a 4n -Lipschitz function. Let Pm.p denote probability distribution over Xr. Suppose that (=m are drawn i.id. from Pm. for p [Nm] and m [M]. Let km.p By + R2 be Lm.p-Lipschitz function and Omp be a constant y m.p. Consider the following stochastic process:
(r(r))
Σ Im
> p=1
where Em.p denotes sample average over {x, 1==1"
In the rest of the proof, we show that
M N
E| sup |R (rx) - -((R((r)) <4 T.E
Lin. 1Cmpp
Imm
Peom. (Hr). Pmmp
(I.6)
To prove (1.6), we consider a continuous extension of ((m.p) defined on the origin. We note that such extension does not change (r(r)) since ((pp) takes values only in By. If By then for any uniformly continuous due Lipschitz continuity. Then (mpp) will be Lm.p-Lipschitz on z E [0, 22). Let
(2) for some 0 S 21 < 22 21], define f(m.p) (2) limz4a, ((m.p) (z) where lim=1z, (m. (2) exists since ((..) is
{x,)==1 1lmu be an independent copy {x)=1r, 12mo Let denote 6 == ElsuprieH. (Rx(rx) E[R& (rx)]l]- Following symmetrization argument (Vapnik, 1999), an upper bound on the symmetrized process can be established by Rademacher complexity:
A E
sup FHE
Σ 9m
Cm Bm Mm - E -8(gm
C Em (mmpmmpmmmmms
Nm
Nm
< BC
sup T M2
9mm
Cm..Bmmpplee (Fx
Compmmpp
m=1
p=1
p=1
Nm
Tigm
Cm. RR
sup EH.
(m. (Tx())) famm
m=1
p=1
(1.7)
Lig
Cm IE
sup Bm (Fx(())))))))) e(m, plmp (0m0)) TH,
M
Nm
4
Lym
1m, E
sup mEE,,
mu=1
p=1
4
Lgm
Ömmp Rlo.. (Hr)
where km. are Rademacher variables uniformly chosen from {-1,1}, È and Ëm.p denote the expectation and sample average data. distribution Pm.p and the independent copy (x:)"=r respectively, the third
30

---

Published in Transactions on Machine Learning Research (06/2023)
inequality holds by the Lipschitz continuous property of Im, and the last inequality is obtained by applying Talagrand's contraction lemma for two-sided Rademacher complexity (Ledoux & Talagrand, 1991; Bartlett & Mendelson, 2002).
Applying (1.6), we can show that
K R (H,, + 4(CxL1 + L2) ni
El sup (xx) E1ē (rx)ll s 4h, R
Σ
Rat (Hr),
T.E..
which completes the proof.
Next find an upper bound on the bias supryen, [BLE] (rw)] Er(rr)
Lemma 4 (Bias bound). Denole De supses, (a [0)())) Assume infreH, [[Bx(li >> 0 for & [K]. Then, an upper bound on the bias term is given by
-2n
sup THHH
- (CW) (LC))) exp
/ + /KC
(I.8)
for some constant T/K > 0.
Proof. Let B2 = E.y - Cs Et= Byg. We first note that
B (nw)] - (rx)] 16E7(r (rx) (r(r))
E ReLU ((x(e((ra(x)))) - (ra()(
< E ReLU (Bx(l((Ta(x)))) - (r(()(a(
E ROLLU (facl((ra(())))) (
ReLU ((xI(I(T((()))) -Bal (r(ee
E 1 ReLU ((x((((ra(x)))) + (x1G((((x))1 =(H)((KKCAA
sup
(ReLU(>) 2)
where the third inequality holds due Jensen's inequality. We note that i2 (fx((())))) s + KC&) implies
sup =(
(ReLU(z) - KC
Due to the assumption infrem, [[xx(1(7x())]]] > 0, there exists an m7 > 0 such that ([Ex(G(rx(x))]]] 2 m for all ry E H,, Then we have
(ReLU (Bule((r((x)))) + (xlle(ra(x)11
Pr [Br supp(ReLLU)
Pr (xx)(((7x() <0)
Pr (xx)l((7x(() <
- -me)
where ReLU(z) ReLU(2) - 2.
Denote ((S)) = Exle, (rx (x)) where Sa fxf....... xtr
x xf......, xte ). Let s be obtained by
replacing element. of set Se by independent data point taking values from the set x We measure
31

---

Published in Transactions on Machine Learning Research (06/2023)
-( If the changed the absolute value of the difference caused by changing one data point in (m(Sz) point is sampled from ph the the absolute value of the difference caused in the maximal deviation term is
upper bounded by Ar. If the changed point is sampled from pl the the absolute value of the difference n
caused in the maximal deviation
is upper bounded by A.C. for I I,..., K. Finally, McDiarmid's inequality (McDiarmid et al., 1989) implies:
-2 Pr < m S eexp A7/n + KKCAA/I
which completes the proof.
Substituting the upper bounds in (I.5) and (I.8) into (I.4), with probability at least 1-6, 6, have
K
- Eg((t) S 8L, R (H,, + V' Ae, nk, + 8(CaL) + L2)
Σ
R
(Hr)
(I.9)
1=1
where V Dry 8 n + K(++C+1)
log + + + KC&) exp A//n COTTTKKKAA//PPP
-2
for some constant 7)s >> 0. A
This completes the proof.
J Ratio estimation error bound for multi-layer perceptron and multiple clients
Our high-probability ratio estimation error bound for client depends on the Rademacher complexity of the hypothesis class for our density ratio model H, C fr: X + By} w.r.t. client k train distribution ph: and all client's test distributions p/e for e [K]. By restricting function class for density ratios and substituting an upper bounds its Rademacher complexity, we can obtain explicit ratio estimation error bounds in terms of nk n in special case. As example, the following corollary establishes ratio estimation error bound for multi-layer perceptron density ratio models in terms of the Frobenius norms of weight matrices.
Example J.1 (Complexity for lulti-layer perceptron class (Golowich et al., 2018)). Assumee that distribution has a bounded support Sp == sUPxesupp()) ||x|| < co. Tet H be the class of real-valued neural networks with depth L over the domain X W; be the network weight matrix i. Suppose that each weight matrix has bounded Frobenius norm || s Aw, for i E [L] and the activation á is 1-Lipschitz, and positive- homogeneous function, i.e., ((az) = a<((), which is applied element-wise. Then we have
R (H) < Sp(v2Llog2 - IIII Aw.
Vn
Remark To control the upper bound Aw; for i E [L], it is natural to employ the sparsity the weights, e.g., (Golowich et al., 2018, Section 4) and (Hanin & Rolnick, 2019). We consider special network architecture where diag(W.)'s almost rank-1. Then ||Wi|FF is upper bounded by 1 for i E [4].
close to 1-sparse unit voctors for i [L], which implics that the matrices W,'s will be
Corollary 1 (Higgh-robabbiity ratio estimation error bound under Example J.1). For Example J.1 and loss functions described in Theorem 1, with probability at least 1 - ò, we have
Ktr
K
Ktc
8f(Pk) - Ex(r))
(6, Ae,nk n'
Th
Vnto
where Ktr = S P LII Aw.),
KTC0
( L1, L2) L2) VI Aw.), and v
Dey 8( K(1+Ca1 log + 2(1 KC2) 1ate
2n KC for some constant T7p > 0.
exp
A
Finally, apply union bound and obtain global ratio estimation error bound that holds for all clients:
32

---

Published in Transactions on Machine Learning Research (06/2023)
Corollary 2 (Higb-probabilityy ratio estimation enror bound for multiple clients). Let 0 < 8n < for & E [K].
Let K" = =]] K For Example J.1 and loss functions described in Theorem 1, with probability at least
_k=1 ÖR, we have
K
K
k
max (E)(fx) - - -E kE[R]
D
n
1=1
(6, A
"h
n)
where V A8V8( 8( n + K(++C) n log 1 2(1 + KC) A exp A//n't KC af/me)
2n
C maxke[K] Ck2 n
min ng 8 = minkelk] ōR, and 17 minke[k] Ti:
The rales match the optimal minimax rates for example for densily estimation problem when the density belongs to the Hölder function class (Tsybakov, 2008)]Section 2] with sufficiently large based on Definition 1.2 of Tsybakov (2008). The ((1/vn) lower bounds are obtained for important problems including nomparametric regression, estimation of functionals, nonparametric testing, and finding a linear combination of M functions to be as close as the target data generating function (Nemirovski, 1998)[Section 5.3].
K Additional error due to estimation of Tk
In this section, we consider practical scenario where we have access only in imperfect estimate of Fk xu (x) to find C in Eq. (3.2). In particular, find additional error when using C2 &x where Fx is obtained by HDRM in Section 3. The mnBD DRM problem for client & using C2 is min &f (rx) where
K
(rx) = ReLU (B,r -
Ox Σ (((r((((()))) + (epr((((
(K.1)
Along the lines of the proof of Lemma 3, we can show that the maximal deviation term using C₁ upper bounded with probability at least 1 d:
K Σ
sup ( - Ł1č (rw)ll < 4L, 4L, E E.
R (H,) + 4(CbL1 + L2) 1=1
pei (Hr)
(K.2)
K(1 x(1+
2 n
+
log
nto
Under perfect estimate of 7k = rx(x with C₁ = 1.1 the mnBD DRM problem for client is mi, (rx)) where
K
(+() = -ReLU
ReLUU(B (BBm Cs
Σ E (((x)((((()))) + +I (2(x(((())))))
(K.3)
Applying triangle inequality, we first decomposse the bias term
sup (rx) -y(r)) sup
(rx) - (rw)l
neW,,
TEE,,
(K.4)
+ sup
[rx]) -
33

---

Published in Transactions on Machine Learning Research (06/2023)
An upper bound on Su, [ (rx)] Ey(rk) is established similar to the proof of Lemma 4:
-21
E + - = (Cx) exp / KC
sup EE
Substituting Eq. (K.1) and Eq. (K.3) into (rx) - * we have
bol, (Tx) - 8 (rx)]l
[[E Ck Be ((1(((()))) - ReLU((EEg Ck Σ Bpp )l (rx(x)))
i=1
which together with (e)U(aa- Re)U(b) la- is used establish the following upper bound:
(T() (T)) s KA.CA Ckl-
(K.5)
Let m² = arg maX Fk.m- We note that by the construction of HDRM, there is constant lower bound on the numerator of Fk. ie., no Ei=1 E [(x] Bm-) 2 E that is achieved when { distributed uniformly across M bins. Let x X and let (x; M) denote a histogram- basaddd-addddd density estimate of PK (x) with M bins. The maximum value of C2 is attained when n ΣØ= Σ [xx],) Bm-) meets its lower bound, which leads to the maximum deviation from Cs < C₁. Assuming pk (x) is Lu-Lipschitz with supxex (x(()) (x) < oc, the mean squared error a histogram- based density estimate with M bins upper bounded by (Wasserman, 2006, Section 6): Eli .) - p (x) = O (LL//M2 + M/n!). Putting together
with a constant lower bound on the numerator of îąK and applying Jensen's inequality, we have:
M n
EJCO2 Call x
L Proof of Lemma 1
We first note that
0 -[L(0)]_((.)) 0 - 0.11
Bias + Variance.
We first find the expression for 9 considering the ridge regression problem assuming (x1(x) is given. FTW-ERM problem with Tikhonov regularization is given by
(x)(x
n
arg min
w. w - 11)² + Blollk
where w; (x.) (x:) and is the regularization parameter. This is a reweighted least squares problem.
The objective function above is strongly convex and differentiable. Applying the fist-order condition, the unique minimum is as follows:
θ
TTyy
Wy
(L.1)
where W = diag w1,.... wn))
Substituting y X0. into (L.1), note that
-= (x WX + +aP) TwxX. + (xT XTTXX X "
" XWe
34

---

Published in Transactions on Machine Learning Research (06/2023)
and
Ex, - Ex (x (XTWX) WTTTXX+N + + Aaa) -1 x Www.
We now characterize the bias B()) and variance v(Ō) terms when the model estimate given by (L.1).
Let |x| := x Ax. Substituting the expression for into R(O), the excess risk can be decomposed into a bias and variance term as follows:
R(θ) = Ex,ex, [1V 0 x) 0')²²
(y - 0. x)
= Ex.xxxel Iv- 0 x + (0. Tx) (y - 0 x
= Ex,,, (10. 0) 0)xx} x
EEx.el10, 0113,00
B -B+V
where the bias is given by
|| (x (XL+ -1 X XWx. 0, 2
B = Ex,
= =Ex
(x (xT 20 1
10.1--]
Aw
with
AWA WX + -
and the variance is given by
(x TWW + ALa) X TWe 2
V Ex.e
= ox |tr (1bv)).
where By = (x WX + Aaa) X w2x (XWXXx WX + >la) -Ta) ''x.. s'
M Proof of Theorem 2
In the one-hot case, it is clear that X x Ex xix and XW = Em wxx,x] are diagonal matrices.
For bias in the one-hot setting, have
B(O) = X2 0. X WX + +T) E ''' (XT o.]
[(0)){12;
(X:(X (XX) 2)²
imm1; 2)2
where the equation holds by the fact that, all matrices diagonal including X X, X WWX and E Accordingly, we have (X WX) XxXXXXXA ()) with i [d]. For the classical ERM, the bias is
d
(0))o
B(0") = x2 Σ
1 x
35

---

Published in Transactions on Machine Learning Research (06/2023)
where A is the cigenvalue of En. To achieve B(θ) & B(0"), have to make some assumptions the relationship between Xi X and wy Our analysis of error bound requires
X law + 2/2
A [os + 2/2
P +
A X
(M.)
which implics
2
1,
(M.2)
A
such that Eq. (M.1) holds where we use the inequality For the vanilla ERM, the variance is
etc & i + 1 for any a, b, > 0. b4c
d
Aipli
v(0")
2
[ + A12
1=1
For FTW-ERM, the variance is
v(O) of XX] WX + AI) - X XXX.XXXXXXXXXXXXXXXXXXXXXXXX
WX WX+ +1) - 1 ''
XXX W
(Ai(X WX) + A)²
-
luww + 212
We note that v(O)= S V(0") can be achieved by
Xa/4: [M + A]2
Napaw?
Iurw + X12
This can be obtained by
P4 +
X
(M.3)
14 + 14
A₂
which implies wa & Ev X
Combining Eqs. (M.2) and (M.3), the proof is complete.
N When FTW-ERM cannot outperform ERM
In this section, we provide a counterexample to show that, under which certain case, FTW-ERM cannot provably outperform ERM.
Proposition 3. Under the same setting of Theorem 2, i.e., the fized- design setting and label noise assumption, under the following condition
X
max - [
Tf the ratio satisfies
X
wx & min
(N.1)
M -1
8
then we have
R(0") R(Ō).
36

---

Published in Transactions on Machine Learning Research (06/2023)
Proof. According to Eq. (M.1), B(0") B(()) holds by
14 +
A
+
A
X
which is equivalent to which is equivalent to
X X
X
X
&
(N.2)
Ma
μ4
According to Eq. (M.3), v(0%) < v(O) holds by
14
X
10
14
A;
W/: S
(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 implics
max 17
A
which is condition in Proposition 3.
X A
X V X 1, have
By checking Eqs. (N.2) and (N.3), in both cases
1 and
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 CIFAR10 (Krizhevsky). MNIST consists of images depicting handwritten digits from 0 to 9. The resolution of each image is 28 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. CIFAR10 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.
Experimental setup: For all experiments we use the cross entropy loss. The stochastic gradient for 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 a LeNet (LeCun et al., 1998), a learning rate of 0.001, no weight decay, and runs for 5, 000 iterations. For CIFA experiments we use the larger ResNet-18 (He et al., 2016). Batch normalization in ResNet-18 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 in Table 7. FedBN Li et al. (2021c) is given a 10 times larger horizon due to slower convergence. The partial client participation experiment in Table 2 uses 200, 000 iterations.
All reported mean and standard deviations are computed over independent runs except for CIFAR1O which uses 3 independent runs. For target shift the randomisation 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 internal cluster using one GPU.
Fashion MNIST provided under the MIT license.
37

---

Published in Transactions on Machine Learning Research (06/2023)
Table 6: CIFAR1O target shift distribution across 100 clients where groups of 10 clients shares the same distribution.
Class
0
3
6
8
9
Train
05/100
5/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
5/9
95/100
$/9
5/9
5/9
5/9
5/9
5/9
5/9
5/9
Client 11-20
Test
6/9
8/9
$/9
6/9
5/9
5/9
5/9
5/9
95/100
5/9
Train
5/9
5/9
95/
5/9
5/9
5/9
5/9
5/9
5/9
5/9
Client 21-30
Test
6/9
6/9
8/9
f/9
5/9
6/9
5/9
95/100
5/9
6/9
Train
5/9
5/9
5/9
95/100
5/9
5/9
3/9
5/9
5/9
5/9
Client 31-40
Test
5/9
6/9
5/9
5/9
5/9
5/9
95/100
5/9
5/9
5/9
Train
5/9
6/9
5/9
5/9
95/100
5/9
3/9
5/9
5/9
5/9
Client 41-50
Test
5/9
5/9
5/9
6/9
5/9
95/100
5/9
5/9
5/9
5/9
Train
6/9
6/9
5/9
6/9
6/9
95/100
5/9
5/9
6/9
5/9
Client 51-60
Test
5/9
5/9
5/9
5/9
95/100
5/9
5/9
5/9
5/9
5/9
Train
6/9
5/9
5/9
6/9
5/9
5/g
95/100
5/9
5/9
5/9
Client 61-70
Test.
5/9
5/9
5/9
95/100
5/9
5/9
5/9
5/9
5/9
5/9
Train
6/9
6/9
6/9
6/9
6/9
6/9
3/9
96/100
6/9
6/9
Client 71-80
Test
5/9
6/9
95/100
5/9
6/9
5/9
3/9
5/9
5/9
5/9
Train
5/9
$/9
$/9
5/9
5/9
5/9
5/9
5/9
95/100
5/9
Client 81-90
Test
6/0
95/100
5/9
6/9
6/9
6/a
5/9
5/9
6/9
6/9
Train
6/9
6/9
$/9
6/9
5/9
5/9
5/9
5/9
6/9
95/100
Client 91-100
Test
95/100
6/9
5/9
5/9
5/9
5/9
5/9
5/9
5/9
5/9
0.1
Target shift
For the target shift experiments Fashion MNIST in Table 1, summarize the different number of data points for each dataset split in Table 9. A similar distribution across clients is used for the additional experiments for FTW-ERM and FedAvg on CIFARIO (Table 8). CIFAR10 differs from Fashion MNIST in the number of examples due to the training set being smaller. The results for CIFAR10 in Table 7 shows that FTW-ERM uniformly improves the accuracy over FedAvg on this difficult target shift instance. We additionally include two-client setting in Table 10 with the associated distribution described in Table 11.
To compute the exact ratio r(x) we will assume that the distributions are separable.
Definition (Separability). A distribution over X y is separable if there erists partition (&) of X such that M()))) = 1 for some E y and all E [m]] We denote the associated deterministic label assignment as g y.
Proposition 4. Assume that the distributions p' y) and (x, y) are both seporable. Then the ratio can be computed based on the associated label y = g(x) as follows,
p'o(y)
r(x) (1)
(0.1)
Proof. Due to separability,
St (y(()) = (y(xx) So
r(x) (x) (1"(x)p''(()
p' y) nd "x (x. y)
(0.2)
(x)
Tt. follows that,
(x v) ('0('))))'e
(0.3)
(x (x1(x))))""
Using the definition of the target shift assumption, pda (xly) p" (xly), the conditional distributions cancel and we obtain the claim.
38

---

Published in Transactions on Machine Learning Research (06/2023)
Table 7: Target shift on CIFAR10 with ResNet-18, Note that FedBN is given a times larger horizon due to slower
convergence.
FTW-ERM
FedAvg
FedBN
Average accuracy
0.6004 + 0.0076
0.4426 + 0.0291
0.5081 0.0520
Client 1 accuracy
0.6714 0.0153
0.3984 + 0.1497
0.6699 0.1283
Client 2 accuracy
0.8196 + 0.0962
0.7307 + 0.1533
0.7213 + 0.0810
Client 3 accuracy
0.5412 + 0.0776
0.3333 + 0.2251
0.1584 = 0.1222
Client 4 accuracy
0.5087 + 0.0827
0.3030 + 0.1106
0.2907 + 0.1859
Client 5 accuracy
0,4610 + 0.0508
0.4476 + 0.3649
0.7003 = 0.0386
Table 8: CIFAR1O larget shift distribution.
Class
2
6
Train
28
28
28
28
28
4885
28
28
28
28
Client
Test,
977
5
5
5
5
5
5
5
Train
28
28
28
28
28
28
4885
28
28
28
Client
Test
977
5
5
Train
28
28
28
28
28
4885
28
28
Client
Test.
977
5
5
5
Train
28
28
28
28
28
28
28
28
4885
28
Client 4
Test
5
5
5
977
5
5
5
5
Train
28
28
28
28
28
28
28
28
28
4885
Client
Test
5
5
5
977
5
5
5
Table Fashion MNTST target shift distribution.
Class
1
2
3
4
6
7
Train
34
34
34
34
34
5862
34
34
34
Client
Test
977
5
5
5
5
Train
34
34
34
34
5862
34
34
Client
Test
977
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 4
Test
5
5
977
5
5
5
5
Train
34
34
34
34
34
34
34
34
5862
Client
Test
5
977
5
Proposition 4 provides a way to compute the ratio r(x) when the labels are available and the shift known.
0.2 Covariate shift
The color flipping probability used to generate cach 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 2.
39

---

Published in Transactions on Machine Learning Research (06/2023)
Table Fashion MNIST with target shift across two clients.
FTW-ERM
FITW-ERM
Fed
Average accuracy
0.82 + 0.00
0.76 + 0.01
0.76 + 0.01
Client 1 accuracy
0.89 + 0.01
0.80 + 0.02
0.94 = 0.00
Client accuracy
0.74 + 0.01
0.71 + 0.02
0.58 + 0.01
Table 11: Two-client Fashion MNIST. The number samples for each class across the different datasets.
Class
2
6
Train
100
100
100
100
100
100
100
100
100
100
Client
Test
9
9
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
P
Computational complexity of Algorithm 1
We note that clients compute the ratios in parallel where cach client needs to estimate one ratio. To estimate density ratios for FTW-ERM, clients require to send few unlabelled test samples only once. The server shuffles those samples and broadcasts the shuffled version to clients only once. Compared to Fed the additional computational cost per client is O(TN2) where T is the number of iterations for Algorithm 1 to converge and N₂ is the number of batches for ratio estimation. Compared to bascline FedAvg, the additional computation of FTW-ERM is negligible but leads to substantial improvements of the overall generalization in settings under challenging distribution shifts.
Q Limitations
In this paper, we focus settings where ratio estimation is required once prior to model training. Handling distribution shifts in complex non-stationary settings where ratio estimation is an ongoing process is an interesting problem for future work.
In addition, various personalization methods have been proposed to improve fairness terms of uniformity of model performance across clients (Li et al., 2021a;b). To meet specific requirements each client, our global model can be combined with a personalized model on each client. Developing new variants of FTW-ERM with a focus on fairness is an interesting problem for future work.
To estimate (r*(x) J= clients need to send unlabelled samples x for I E [K] and j eE [n]]] from their test distributions. We note that instead of their true samples, clients can alternatively send samples generated from a generative model (Goodfellow et al., 2020).
Note that training GANs may be computationally extensive due to required computational resources and availability of representative samples. However, we propose to use GANs as an alternative method with clear caveats, only when 1) clients have sufficient computational resources and 2) they are unwilling share unlabelled data with the server.
Table 12: For covariate shift the datasets for each the client are constructed using different probabilities.
p (x)
pf
(x)
phf (x)
(x)
Probability of flipping color
0.5
0.2
0.2
0.8
40

---

Published in Transactions on Machine Learning Research (06/2023)
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 q" x (/20, 1/20, 1/20, 1/20, 1/2u, 1,1,1,1,1) and 1/20) respectively. The table shows the estimated upper bound the ratio (f) for a range of clustering sizes. A reasonable estimate of the true maximal ratio 20 is obtained for a wide range of clustering sizes. Whereas naively binning the space can be problematic due division by zero, the clustering approach is less prone to this issue as long as # (clusteers < # #ddatppoins)..
g¹ (1, 1,1,1,1, 1,,,, 2/20, 1/2u, 1/20,
# (clusters)
10
20
40
50
100
200
500
10.31
15.48
19.08
27.41
31.47
32.84
206.76
Colored
102
10²
Client 1 (A0)
107
Client 1 (A))
10a-
Client
10
Client 2 (k)
Client 3 (A()
10
Client 4 (A()
Client 4 (A))
10
10
Client 5 (A))
Figure The sudden increase in the eigenvalue ratio observed Figure for larger than 780 and 1300 in Fashion MNIST and CMNIST respectively is most likely due to numerical error. We plot the eigenvalues under the test distributions (X') and under the training distribution (A) and observe that indeed the eigenvalues suddenly drop very close to zero at those exact indices.
41

---

Published in Transactions on Machine Learning Research (06/2023)
As partial mitigation of privacy risks, we introduced FITW-ERM. FITW-ERM does not require any data sharing among clients and does not require any GAN training. In this paper, we focus FTW-ERM since it outputs an unbiased estimate of a minimizer of the overall true risk, and enables us to theoretically show the benefit of importance weighting in gencralization.
One particular challenge in real-world cross-device FL estimate ratios on real-world datasets such 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 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 FTW-ERM and FITW-ERM formulations along with improved ratio estimates will provide reasonable solutions learn an effective global model in world cross-device FL under covariate shifts.
arbitrary test cest/tru traiin
42


Reviews:
[{"review_id": "xExs2MF1Hy", "reviewer": "Reviewer_1yN7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weakness:\n\n1. The concept of adjusting the training loss based on the train/test ratio seems intuitive, and one would expect it to yield a consistent objective a priori.\n2. However, despite being a logical solution for the covariate shift issue, this reweighting approach is not practical because it requires information from the testing dataset during the training phase, which goes against the standard machine learning setup where testing data is not accessible during training.\n3. Additionally, even if the testing data were available, the histogram-based density ratio estimation method could still pose challenges since it may not scale well with the dimensionality of the problem.\n4. The authors assert that the proposed paradigm provides an equivalent level of privacy protection as the standard ERM formulation. However, this statement lacks rigorous analysis, such as a guarantee based on Differential Privacy. Moreover, the density ratio estimation, which is the fundamental aspect of the proposed scheme, seems to introduce additional privacy risks, but there is no analysis of its potential impact.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper address the intra- and inter- client covariate shift in the federated learning by correcting the standard empirical risk minimization formulation with additional importance weights. The required density ratio is obtained via a histogram based estimating scheme. The objective after this reweighting procedure is consistent, i.e. it matches the testing error.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Please address the points raised in the weakness section, especially points 2-4.", "broader_impact_concerns": "Since the proposed paradigm requires test data during the training phase, it does not fit the standard machine learning set up and may requires additional attention if such a framework is implemented in real world system.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NGrzZVqHyc", "reviewer": "Reviewer_hsZ4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. covariate shift is an important problem in FL and in general machine learning. This paper proposes a new method based on importance sampling to address the covariate shift.\n2. The literature survey is quite complete. \n3. This paper shows generalization guarantees of error estimation and gives supporting experiments to show the advantages of FIDEM.\n\nWeaknesses:\n1. Clarity:\n * After Sec 2 the font suddenly becomes italic, which makes it hard to read.\n * Sec 1: Page 1, $p^{\\rm tr}_k$ and $p^{\\rm te}_k$ are not defined.\n * Sec 1.1: BD and DRM are not defined\n* \"Our work is the first step towards ... distribution shifts\": cannot agree on this. There are existing works on it, such as https://arxiv.org/abs/2205.11101, https://arxiv.org/pdf/2206.09979.pdf, https://arxiv.org/abs/2102.07623, etc.\n2. Minor:\n* Page 2: CIFAR10 (Krizhevsky)\n* Page 3: our setting our setting\n* Page 4: i.i.d -> i.i.d.\n* Page 5: sum test over own train: what does it mean?\n* Sec 3.2: what is $C$? \n3. Novelty:\n* The nnBD DRM method seems like a direct application of Kato and Teshima 2021. What is the novel part?\n4. Soundness:\n* Algorithm 1 requires additional communication of samples, which violates privacy constraints more than FedAvg, and it also violates the original design of FL: samples should be kept in local clients. \n* Sec 4.1: the original paper on Rademacher complexity should be Koltchinskii, V. (2001). Rademacher penalties and structural risk minimization. IEEE Transactions on Information Theory, 47(5):1902–1914.\n5. Questions:\n* eq. (2.1): the loss depends on the density ratio estimation. It also requires whenever $p_k^{\\rm tr} = 0$, $p_l^{\\rm te} = 0$. How can this be ensured?\n* Sec 2.3: why is it impossible to apply a gradient inversion attack? It seems possible as long as we can find the gradient.\n* In Theorem 2, could you explain why FIDEM is better than ERM? If we minimize the total loss, it seems that ERM always obtains the optimal solution for the empirical risk. Is it due to the sampling error? \n* In Figure 2, there is a sudden increase and the authors explain it is due to numerical error. However, such an explanation is not quite convincing and it will violate the assumption in Theorem 2.\n* Additional baseline algorithms that address covariate shifts should be compared, such as FedBN, FedNova and the related work mentioned above. Also, FIDEM requires additional samples to be sent to the server, which makes the comparison with FedAvg quite unfair.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new method to solve the covariate shifts in federated learning, called FIDEM. It shows the generalization guarantees of FIDEM and conducts experiments on MNIST, CIFAR-10 and ColoredMNIST. The experiments show advantages over FedAvg.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "I don't have ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HjFaEijPEW", "reviewer": "Reviewer_i3bH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert in privacy theory and in generalization studies, so my review is an educated guess. \n\nStrengths: \n1)This paper has a clear structure, and it is easy to read. The paper has good storytelling and flow. \n2) The introduction part is well-written, and the motivation of the research is clearly stated. \n3) All assumptions, lemmas, and theorems are rigorously described. \n4) Contribution seems to be significant. \n5) Theoretical analysis seems to be correct. However, I might miss something. \n\nWeaknesses: \n1) I think that FIDEM is a good name for the framework. Since this framework is connected to ERM, it must contain ERM in the name. Otherwise, it is confusing for readers. Also, having capitalized letters at the end of the word (weighteD) is questionable. \n2) I do not like that a large part of the text is written in italics. It is suitable for theorems or assumptions, but if the whole section is written in italics, it is hard to follow. \n3) The definition of Bregman divergence for strictly convex function with bounded gradients is not clear. The set should be bounded. Otherwise, strict convexity and bounded gradients will contradict each other. This should be described. \n4) Figure 2 is not clear to readers. The nature of peaks is not explained. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper authors study generalization properties in Federated Learning. They focus on intra-client and inter-client covariate shifts. To overcome the problems caused by the existence of the shifts, authors propose a general framework called Federated Importance-weighteD Empirical risk Minimization. Moreover, the authors propose a communication-efficient variant with the same level of privacy guarantees. At the end of the paper, experimental results are presented. \n\nMore specifically, the authors propose a framework to minimize the average test error for the Federated Learning problem and design a technique to control privacy leakages and also have communication-efficient properties. \n\nThe paper provides a theoretical analysis of high-probability guarantees on ratio estimation error with multiple clients. In this case, the supremum is calculated not exactly. The analysis shows the advantage of importance weighting in terms of excess risk decoupled from density ratio estimation through bias-variance decomposition.\n\nThe authors demonstrate experimental results that show more than 16% overall test accuracy improvement over existing FL baselines for the ResNet-18 model and CIFAR10 dataset. \n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I suggest changing the name of the framework and reducing the percentage of text with italics. \nAlso, I suggest providing more details for Bregman divergence and experiments. ", "broader_impact_concerns": "In this paper, the Broader Impact Statement is not presented. This paper is of theoretical nature, and I do not think that obtained results can lead to ethical issues. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors adapted some existing covariate shift techniques to the federated learning setting, and proposed two algorithms that in theory could accommodate shift in marginal training and test distributions. There is some concern over sending unlabeled test samples to the server, which I agree is one of the limitations of this work. Nevertheless, my hope is that the authors have experimentally shown the advantage of their approach in an ideal setting, and future work could possibly address any remaining limitation. For instance, the authors mentioned in Appendix Q that the clients could train a generative model and send generated samples instead. It is also conceivable that some clients may be willing to estimate and send the test density function, or a nested algorithm can be developed to eliminate the need of sending test samples altogether. Thus, I believe overall this work is interesting and relevant to the FL community, considering especially the ubiquity of domain shift in practical problems. 

In the final revision, please make sure to incorporate the reviewers' comments (if not already done so in the revision), some of which we recall (and add) below: 

-- histogram-based density estimation may not scale well w.r.t. dimension: I believe what the reviewer meant is the sample complexity (not computational complexity that the authors responded to), i.e., how many samples one would need in order to estimate the density (ratio) well. Typically, the dependence on dimension is exponential. It'd be good if the authors add some discussion around this (see also the next comment). 

-- error bound in Theorem 1: note that the bound is about the difference between our estimate and the best estimator from the function class H_k (i.e., left-hand side of Eq (4.2)). To exaggerate a bit, if H_k consists of a single function, we get 0 error trivially. So, the usefulness of Theorem 1 really boils down to how likely H_k contains the true density ratio, which is itself a subtle issue. Perhaps it is worthwhile to add that Theorem 1 is mostly about estimation error, and we do not touch approximation error. Or we simply put our belief on H_k containing the true ratio, which is why one might "skip" the curse of dimensionality as alluded to in the previous point. 

-- Before Section 2.3, "both FTW-ERM and classical ERM result in the same solution, which is a minimizer of the overall empirical risk": this is true in the limit (i.e., when sample size goes to infinity) but not necessarily true in the finite sample setting (e.g., Eq (2.2))

-- FITW-ERM: note that this reduces to the usual FL setting where the local weights are entirely determined by each client (and hence can be abstracted away, e.g., absorbed into the local loss). It is perhaps better to not claim it as new as what the current text implies. 

-- End of page 6: "since the density ratios that are inputs of BD are bounded." This is an assumption, not a fact?
Decision: Accept (poster)