Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
Authors: Amir Najafi
Samin Mahdizadeh Sani
Farzan Farnia
Venue: ICML 2025 poster (2025)
Keywords: Distributionally Robust Optimization
Generalization Bound
Glivenko-Cantelli Theorem and DKW Inequality
$f$-divergence and Wasserstein Adversaries
Primary area: theory->learning_theory
TL;DR: In a robust federated model evaluation scenario (A/B Testing), we propose an efficient and private aggragation method that combines local adversarial risks, and prove it achieves minimax-optimal guarantees against global (meta-distributional) shifts.

Abstract: We address the challenge of certifying the performance of a federated learning model on an unseen target network using only measurements from the source network that trained the model. Specifically, consider a source network "A" with $K$ clients, each holding private, non-IID datasets drawn from heterogeneous distributions, modeled as samples from a broader meta-distribution $\mu$. Our goal is to provide certified guarantees for the model’s performance on a different, unseen network "B", governed by an unknown meta-distribution $\mu'$, assuming the deviation between $\mu$ and $\mu'$ is bounded—either in Wasserstein distance or an $f$-divergence. We derive worst-case uniform guarantees for both the model’s average loss and its risk CDF, the latter corresponding to a novel, adversarially robust version of the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality. In addition, we show how the vanilla DKW bound enables principled certification of the model's true performance on unseen clients within the same (source) network. Our bounds are efficiently computable, asymptotically minimax optimal, and preserve clients' privacy.
We also establish non-asymptotic generalization bounds that converge to zero as $K$ grows and the minimum per-client sample size exceeds $\mathcal{O}(\log K)$. Empirical evaluations confirm the practical utility of our bounds across real-world tasks. The project code is available at: github.com/samin-mehdizadeh/Robust-Evaluation-DKW

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
Amir Najafi Samin Mahdizadeh Sani? Farzan Farnia*
Abstract
1. Introduction
We address the challenge of certifying the performance of federated learning model unseen target network using only measurements from the source network that trained the model. Specifically, consider a source network "A" with clients, each holding private, non-IID datasets drawn from heterogeneous distributions, modeled as samples from a broader meta-distribution μ.. Our goal is to provide certified guarantees for the model's performance on different, unseen network "B", governed by an unknown meta-distribution p', assuming the deviation between and μ is coanneddeithen in Wasser- stein distance or an f-divergence. We derive worst-case uniform guarantees for both the model's average loss and its risk CDF, the latter corresponding to novel, adversarially robust version of the Droreryy-Kiefe--Wooffoo (DKW) inequality. In addition, we show how the vanilla DKW bound enables principled certification of the model's true performance on unseen clients within the same (source) network. Our bounds are efficiently computable, asymptotically minimax optimal, and preserve clients' privacy. We also establish non-asymptotic generalization bounds that converge to zero as grows and the minimum per-client sample size exceeds Ollog K). Empirical evaluations confirm the practical utility of our bounds across real-world tasks. The project code is available g git titb..bc. com/ sami n i zadeh/ Robust Bobust-Evaluse Evaluation DKW
The distributed nature of modern learning environments, where local datasets are scattered across clients in a net- work, presents significant challenges for the machine learn- ing community. Federated learning (FL) addresses some of these challenges by enabling clients to collaboratively train a decentralized model through communications with a central server (McMahan et al., 2017; Liu et al., 2024). A major obstacle FL the heterogeneity of data distri- butions among clients. This non-IID nature of client data not only impacts the training stage but also complicates the evaluation of trained models, especially when applied to unseen clients from the same or different networks (Ye et al., 2023; Zawad et al., 2021). In this paper, we focus on the latter problem.
Consider network with K clients, each possessing their own private dataset. For k E [K]. the kth client's dataset is assumed include n& 2 1 samples from unique and unknown distribution Ps. which forms empirical and private estimate Px. Note that the distributions Pı...., .....,Pk: Pk may be highly heterogeneous and distant from one another. In this setting, assume the server wants to assess the perfor- mance of a given machine learning model h on this network. Let the risk function R(h, Pk)) denote the loss of when evaluated over the private data samples of the kth client, i.e., Pg. This quantity can be queried by the server by sending h to client ht and requesting its local loss value, without di- rectly accessing any of the private data samples in client k's dataset. Hence, the server can collect all K loss values and empirically approximate the average performance of over the network, using various metries. One common approach is the average loss: Ek= R(h, Ps), which measures the empirical average performance of the model in the network.
'eparrmennt of Computer Engineering, Sharif University of Technology, Tehran, Iran (Corresponding author) DDeparmentt of Electrical and Computer Engincering, University Tehran, Tehran, Iran DDepartment of Computer Science and Engineering, The Chinese University of Hong Kong (CUHK). Hong Kong. Cor- respondence Amir Najafi <amir.najafi sharif.edu>' Samin Mahdizadeh Sani assaii..aadizza @ @ut.tac ir? Farzan Farnia <famii www.:ecceecccccceceeee
Another approach is the loss CDF, representing the per- centage of clients whose loss exceeds given threshold A: R Σ 1 (R Pa) 2 X), which is useful for estimating the quantiles of the risk (see (Laguel et al., 2021)). For a recent related work on the use of super-quantiles in FL with heterogeneous clients, see (Pillutla et al., 2024). While that study focuses optimization and convergence aspects, our work provides a theoretical treatment of generalization.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributionaal Shifts
A critical challenge arises when certifying the performance of h on different and unseen network with completely different clients. Mathematically, assume a large group of T >> new and unseen clients with corresponding hetero- geneous distributions
Bp (Px)
Qr. which may differ sub- stantially from one another and also from P s. This cor- responds to a beta lesting scenario, where, for instance, a product owner may test a product on a small subset of network before wider deployment (Reisizadeh et al., 2020; Ma et al., 2024). Our goal is to certify the same performance metrics over Qis without accessing them.
Pt
Figure I. A graphical illustration of meta-distributtinal shifts be- tween two client networks governed by μ and μ². Meta-shifts shifts may only denote changes in densities (f-divergence) or can involve support as well (Wasserstein shifts). Each client Pa is a sample from ja, with Pes as its empirical counterpart based on a local datasets. The client distributions Px can vary significantly, such as one having primarily landscape images while another con- tains mostly vehicle images.
Clearly, without a connection between Ps's and Q the certification task is fundamentally infeasible. To address this, we can rely on the following common assumption in many beta testing scenarios: Pi-K and Q1t are all in- dependent samples from the same meta- dettaddittrbbution y (a distribution over distributions), which governs higher-level factors influencing the clients, such as cultural or geographi- cal attributes (Yuan et al., 2021; Ajay et al., 2022; Wu et al., 2024a; Chen et al., 2023; Patel et al., 2022). In this setting, the empirical average risk and empirical risk CDF over Pk 's provide unbiased estimates for those of the unseen clients, i.e., Qi's s.. Still, a natural question would be how large K or either of n. 's need to be such that the mentioned estimates become statistically reliable?
Again, without this assumption certifying the performance of h under μ¹ is mathematically impossible. The degree of deviation (E) between and μı' can be quantified us- ing metrics such as Kullback-Leibler (KL) divergence or Wasserstein distance, both interpreted in the context of meta- distributions. KI., or more generally, an f-divergence cap- tures situations where client types in one meta-distribution are reweighted in another (Mehta et al., 2024), whereas Wasserstein distance accounts for the emergence of entirely new client types, representing novel regions of the meta- distribution's 's support (Wang et al., 2022; Kuhn et al., 2019). For example, smartphone users in a coastal area may often take pictures of the sea, whereas residents mountainous regions cannot do so unless they travel. See Figure/ I for more details. We are not aware of any prior theoretical bounds for meta-distributionally robust evaluation (or beta testing) in federated settings. In any case, a review of prior works on similar scenarios of non-III federated learning and model evaluation is provided in Section A.
In this work, we propose a novel approach by leveraging the (DKW) inequality (Dvoret- zky et al., 1956) that uniformly bounds the CDF estimation error from empirical observed samples. Note that in our setting, the CDF is considered for the performance metric of clients drawn from meta distribution μ.. Therefore, the observed clients' performance values lead to proxy empir- ical CDF, and we want to provide an upper-bound on the true CDF to provide a performance guarantee for an unseen client Q; ~ j.. Our approach is to extend the DKW inequal- ity to bound the gap between the empirical and population (true) CDFs. Figure 2 illustrates our DKW inequality- -based approach and how it can provide certified upper-bound on the true CDF of unseen clients' performance.
D
Our Contribution: Our problem, formally defined in Sec- tion 3, is to address the robust evaluation of any given h un- der the menee-ment scenario. Section 4 presents some initial results for the non-robust evaluation when μ = n², i.e., standard beta testing. Theorem 4.1 proves non-asymptotic concentration bounds for both the empirical average and CDF of the risk, with exponential convergence as both K and ming Ti increase. Notably, our convergence results for the loss CDF are uniform over thresholds X, meaning they hold for all X E R simultaneously, via utilizing clas- sical tools in statistics, including the DKW inequality and Glivenko- Cantelli theorem (Dvoretzky et al., 1956).
On the other hand, in real-world applications, target clients can belong to distinct populations with considerable cultural or behavioral differences compared to those observed in the evaluation phase. For example, an app developer might be limited to test mobile application on users from Hong Kong, but ultimately hopes to release it for users from New York. This scenario corresponds to meta- distibiistibu robust evaluation, where the objective is to evaluate the per- formance of h under worst-case shifts from jl to μ'. Here, I and yí represent unknown meta-distributionss, with K empirical samples from μ corresponding to Pi...., PK. Unfortunately, I' is completely unseen, however, it is as- sumed to deviate at most from μ. for some known E > O.
Next, we provide robust bounds on the average loss and/or risk CDF when target network is adversarially shifted from the source. We extend the concept of distributional robust-
2

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
Empirical clients
(Unilormly sumpled from the netwock)
Empinical CDP (ohserved)
Popolation CDF (unohserved)
Population set of clients
Certified upper hound (computed from abserved clients)
Cumulative Probability
0.8
0.2
0.0
0.2
0.4
0.6
0.8
1.0
Accurncy
Figure 2.
Our theoretical bounds are estimated from a set of seen users in federated network governed by meta-distribution μ.. We extend the application of DKW inequality provide certified upper-bound the true CDF of the performance of umseen clients following the same meta-distribution p.
meta-disttibuttinnal robustness, considering both f- divergences and Wasserstein-type adversaries, respectively in Sections 5 and 6, to provide worst-case guarantees.
2. Notations and Preliminaries
For K E N, [K] denotes the set {1, 21, K}. Consider two measurable spaces X' and V, referred as the fea- ture and label spaces, respectively. Typically, we assume X' C Rd for some d N, while may be {=1} for binary classification tasks or R in regression problems. However, we make no extra assumptions regarding X' and V. We de- fine the joint feature- space as 2 & X x y. Let M M( denote the set of all probability measures supported on Z. Each ((2) corresponds a joint measure over ran- dom feature vector X E X and its associated random label y V. The expectation operator with respect measure P is denoted by Ep, We refer to μ meta meta-distribution over 2, expressed as p. M (Z) e M (M (2)), where each sample from is itself a probability measure over Z. In other words, a meta mntaa-isttrbution is a distribution over distributions supported on 2. In our work, μ models the heterogeneity and non-IID-nee of the clients, since indepen- dent samples from μ represent different data distributions shifted from one another.
The majority of existing robust evaluation schemes require aggregating all private datasets in a central server for a collective adversarial manipulation of all the samples (Liu al., 2024; Reisizadeh al., 2020; Sinha al., 2018), which severely violates privacy. Another category of approaches simply compute the average ordinary risk of h in the source network, but are then forced to add a non- vanishing (e-dependent) generalization gap that does not go to zero even when K, 11:K grow to infinity (see Section and also (Rahimian and Mehrotra, 2019; Zeng and Lam, 2022)). The latter approaches fail to take into account the possible inherent wellness or robustness of h, thus usually result into excessively inflated risk certificates.
We prove that globally robust evaluations under both f- divergence and Wasserstein regimes can be done in fed- erated manner as long as: i) server can query the local ordinary or adversarial (only for Wasserstein attacks) loss of h from each client, and ii) server can repeat such queries with potentially various attack budgets for polynomially many times. Note that do not need to directly access client's ss data. Our evaluation guarantees are asymptotically minimax optimal, and have vanishing generalization gaps which converge to zero as both K and (ming n&)/ log K grow. Our robust and uniform bounds on risk CDF in Sec- tion are based on novel extension of DKW inequality adversarial scenarios, which is extensively detailed in Section B. The numerical results standard datasets in Section 8 validate the tightness of our bounds.
For simplicity, we abbreviate M(Z) as M. For any two measures P, Q.Q& E M, let D(P, Q) E R2 denote any given distance or divergence between the two distributions such as KL or Wasserstein distance. In this context, let B3, denote an p-distributional ambiguity ball for p 2 Mathematically, for any measure P E M:
(I) which represents the set of distributions within dis- tance/divergence from according to D. Similarly, meta- distributional ambiguity balls (e( are defined as the set of meta-distributions over M within an distance
B,(P) E D(P.Q) < pp)
3

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributionaal Shifts
from base meta-distribution jr. Mathematically, we have Ge (u) A {u' E M² D [²) S s) Here, the deviation D can be any properly defined f-divergence or a Wasserstein metric between the distadiitributions in M In particular, the transportation cost in the Wasserstein distance can itself be a Wasserstein metric on M in its ordinary sense.
Let Pk denote the empirical version of Ps based on the private samples in PE. which are known only client k.
The server can query each of the K clients by sending a model h and a robustness radius N 0 to client k E [K]. In response, the client returns the adversarial loss of h around Pa:
Server-Client Query Policy:
Let h : : + )' represent hypothesis (e.g., a classifier) that maps the feature space X' onto the label space y ! Additionally, assume a fixed loss function é (y, F). which assigns a loss value to each pair of actual and predicted labels, y and G. respectively. The expected loss, or Risk, of hypothesis h w.r.t. data distribution P E .M is defined as R(h, P) A Ep {e (y, )( Here, P could be the true distribution or an empirical approximation obtained from a dataset, usually denoted by P. The adversarial risk of h w.r.t. a base measure P (or empirical P) and a robustness radius= E 20000 O, is formulated as (Sinha et al., 2018):
QV (h, p) A sup
[((((,,(())))
(5)
QEB,(P.)
The type of distributional ball B,(-) can be defined using any user-defined divergence or metric over MM. When the robustness radius is unspecified, the client assumes is zero, and returns the non-robust loss, i.e. (h) = QV (4, 0). We later show that the local adversarial loss (when p > 0) is not needed for f-divergence-bait based guarantees and only appears in Section which focuses on Wasserstein shifts. Each client k accepts a maximum number of queries. referred to the query budget.
Re-adv P) e
sup EQ [((y,h(X)) (P)
Assume the server sends model h to the clients and requests a number of robust or non- robust loss values for several arbitrary robustness radii. Server's ultimate goal is to use these values to provide a meta- vitaadistributtionally robust upper bound for the average or CDF of the loss of h. Mathematically speaking, the objective is to efficiently compute empirical values (x) and E2 A) such that the following bounds hold with high probability over the sampling of clients and datasets:
Our Problem Setup:
and denotes the worst risk over all distributions in a E- neighborhood of P according to D. Similarly, the meta- distributionally robust loss of with respect base meta- distribution j is defined as:
sup Epene [Er [K(v, ((I)I] (M)
(3)
The geometry of the ball G3 in M2 can be determined us- ing various application -spcciiic divergences or metrics over M In Section 5, we deal with f-divergence balls, while Wasserstein meta-distributional balls (using the ordinary Wasserstein metric as their transportation cost) are utilized in Section 6. We also discuss how to practically implement such loss values in Section 7 and Appendix F.
sup Ep TEple(O (( & Ei(E)+ + (6)
# (E)
sup p (w)
X) S (c,
The generalization gaps Ç, S' should vanish as both K and ming n& increase asymptotically. Also, the second high- probability bound needs to hold for all threshold values X, simultaneously (or uniformly). We consider both f- divergence and Wasserstein metrics to specify the geometry of the meta- -ittrdiittiba ambiguity ball G. (w).
3. Problem Definition
This section formally defines our problem. First, we outline the data generation process, privacy constraints, and spec- ify the query policy that governs communication between clients and the server
From an algorithmic perspective, Σ1.2 must be computable using only the private server-client query policy QV (h, p) for various robustness radii p. Server decides the number of queries for each client, as well as the value of for each query. However, the computational cost of evaluating each query at the client side, and the total number of queries per client should increase at most polynomially with parame- ters.
Consider K e N clients connected to a central server, where client k E [K] has a unique data distribution P& E M(Z). We assume PI, .......PP PK are heterogeneous samples of an unknown meta-distribution f over Z. No one knows P&s, however, client & has access to a dataset D2 of size 7 2 1, which contains independent samples from PR. i.e.,
Data Generation:
Dx A
(x(1)) (k)
))) i E [ma]}
(4)
4. Non-Robust (Ordinary) Guarantees
It should be noted that our work goes beyond this limitation and can he applied to any supervised unsupervised machine learning task.
In this section, we solve the problem setting of section in the non-robust regime, i.c., when μí = yu or equiva- lently & = This scenario corresponds to the standard
4

---

Certifiably Robust Model Evaluation in Federated Learning under Meta--Distributional Shifts
beta testing, which has been extensively applied in practice (Chen et al., 2024). Simple statistical bounds can establish the high-probability concentration of the empirical average 1 Ek= R(h. Pk) around its true mean w.r.t. μ, as long as K
our work. Before that, Sections 5 and 6 extend Theorem 4.1 to the robust setting, where jí' can be adversarially per- turbed from μ by either an f-divergence or Wasserstein adversary.
the loss function f(.) is measurable and bounded (e.g., let be 1-bounded such as the 0-1 loss). However, the same argument does not directly extend to the loss CDE, as the bounds must hold uniformly for all threshold values À 2 O. Without uniformity, such guarantees significantly weak- ened. By "uniform," " we mean that, with high probability over the sampling of the K users, the worst-case deviation between the empirical and true tail probabilities is consis- tently bounded. This challenge is resolved using a classic result on the convergence of empirical CDFs, specifically the wwvreezy--Kiefee-Wollvww (DKW) inequality and the Clivenko-Cantelli theorem (see Section B, and in particular Lemma B.1). The following theorem summarizes our main findings in the non-robust setting.
5. --iverrgee
Shifts
In this section, we provably bound the mett-diittibuttionally robust performance of h, in terms of the average risk and risk CDF.
Definition 5.1. Consider two meta-distributions pt, p² E
M where μr' is absolutely continuous with respect to p. Let
f : [0, oo) + [-oc, oo] be a convex function such that fx) is finite for all x > O, f(1) = O, and f(0) = limm- f(t) (which could be infinite). The f f-divergence between p and p is defined as:
Dy(n'llu)= J S
dd'(P)
du(P).
(9)
JPEM du(PP)
Theorem 4.1. Let μ be a meta- distrriistiiution, and assume F.....,Pr Pk be K independent instances of u. while Ps for K E [K] represent their empirical counterparts, formed using nu independent private samplex from the k-th client. Let h: X --y be any model and E be any measurable and 1 I-bounded loss function. Then, for any 8 > O, the following holds with probability at least 1 1 8:
Pi....,
Also, for 2 O, the f-divergence ball G is defined as {u' Dy(u'llu) S {), which describes neighborhood around where the divergence does not exceed E.
Our goal is to provide a theoretical guarantce for the loss of h under the worst-case meta-distribution μt E f (u). us- ing only the query values from client samples in the source network governed by Jr. Since clients generated by p' may follow different densities compared to μ,, it is natural to reweight the robust loss to achieve a robust upper bound. The following theorem formalizes this idea by reweighting the query values using coefficients Okk, h E [K]. and opti- mizing for the worst-case weights, provided they remain close to uniform weights. This approach yields a minimax- optimal bound with vanishing generalization gap.
K
1 K
Eμ EE (e (y. h (X)))
<
Qv
(h)+
(7)
K
Vlog (K6
1
1
n
1/2
VK
K
For the loss CDF, the following bound holds with probability at least - 8 uniformly for all X E R;
Ep [e (y, h (X)) 21 (x)
(8)
Theorem 5.2. Assume unknown meta veta-distributtinss μ M let 0, and consider f(-) to be as in Definition 5.I. Let h x y be any model and E be any measurable and 1-bounded loss function. Assume Pı,..., Px represent K independent and unknown sample distributions from μ. Accordingly, let Ps for l E [K] represent their empirical counterparts, formed using ny independent private samples from the k-tth client. Let A & 1 KE. Define B as:
K KL 1=1
log (K+1)
2(K +1) log
1 QVa(h)2 V 2n
8
2K
The proof is given in Appendix C. By ignoring poly- logarithmic terms, the empirical means over both the K users and the n& samples from each client k converge rate of (min (K, ming n log -))- In both inequal- ities, the left-hand sides represent strong statistical quan- tities, while the right-hand sides consist of: i) vanishing generalization gaps, plus ii) empirical values that can be fully evaluated based on users' private datasets and using the private query policy described earlier (i.e., the (h) values). Additionally, each client needs to be queried only once.
K
BC A
sup
Σ km
ag Qv (h)
(10)
SEaaa..axs SA
K
K
1
subject to
1
< c1
log (8 (8-1)/K,
K
k=1
1
f(au)
S + c2v log (6 (6-1)/K,
K
In Section 7. we discuss the computational complexity, cer- tificates of privacy, and tightness of the all the bounds in
where constants K, C1, 02 2 0 are known and depend on
f()) Then, for any > O the following bound holds with
5

---

Certifiably Robust Model Evaluation in Federated Learning under Meta--iistributional Shifts
probability at least -: 6:
À R, similar to the original DKW inequality. Again, the empirical value J (e, A) is the solution a server-side convex and thus efficient program. More details will be given in Section 7.
sup MED! div (1)
E E
[Rp (v, h (X)]] <
(e)
B
(11)
K
+ log (Kō-1)O
1 VK
+
1
-
1/2
K k=1
6. Wasserstein Meta-Distributional Shifts
This section addresses the case of Wasserstein meta-shifts from μ to p². Such shifts present significant challenges, as the model h may encounter entirely unseen regions of the meta meta-distributional support. In practical terms, users may exhibit data distributions that are entirely novel compared to p&s of the evaluation phase in the source network. To miti- gate this effect, as we will show later this section, server needs to query out-of-domain loss values from each of the K clients. Here, we provide theoretical guarantees for the average risk, but not for the entire risk CDF. Addressing the full risk CDF requires a more advanced methodology, which falls beyond the scope of the current paper and is defered to future work. We begin by introducing both standard and meta-distributien
The proof including the formulations for K, C1, are pro- vided in Appendix D. This theorem establishes a robust bound on the expected loss under meta-shifts using B= (s), along with a vanishing generalization gap with a decay rate of Ô (min{{ K, ] -1/2). The empirical quantity (e) is derived from a convex optimization problem performed server-side. In Section 7, we discuss all of aspects of com- puting this quantity. Also, it worth noting that as both E, K tend to zero, the bound becomes increasingly similar to the non-robust case of Theorem 4. which should be expected. As discussed before, a key advantage of our result is that the generalization gap lacks any non- non-vanishing e-dependent term. Next, we present our main result for robust CDF estimation of the loss under KL meta-shifts:
Wasserstein metrics, and then present our main result, an analog of Theorem 5.2 for Wasserstein- type shifts.
Theorem 5.3. Assume the setting of Theorem 5.2. For any X E R. let us define the empirical value Jd (a, X) as
Definition 6.1. For any two measures P, E M M (2) and
a lower semi-continuous function c Z x Z + Rz0, we define the Wasserstein distance between P and Q as
K
log 0
sup SSA
Ean'
1
QV (h)
21-1
KL
2n
k=
We (P, - inf Biz,z)~~ (c ( Z'),, (13) vEC(P..)
1 K
subject to
Σ
1 ag - -15 < K
log (Kō-1),
K
where C (P, Q) denotes the set of all couplings between and Q i... all joint probability measures in .M x Z) that have fixed P and Q as their respective marginals (Kuhn et al., 2019).
k=l
1 log (K8-1),
Σ (ox) S e 22V
K
K
Then, with probability at least 1 - 8, the following bound holds uniformly over all X E I::
The function e called the transportation cost and is user- defined. For example, c cZZ Z') ---'Xll, + oc 11 (y # s/) corresponds
typical feature-shifi scenario in robust ML. We (P, Q) (which is a metric over M) measures the minimum cost of transforming P into Q or vice versa ac- cording to the cost characterized by c. Unlike f-divergence, Wasserstein distance can stay bounded under support shifts. In fact, is a powerful tool to model slight support changes between distributions and due to this property is widely used in adversarial robustness research.
N/ ((
sup # plegf (m)
(12)
(e,, + 100)++++OKK/o
(VK-1log (K6-1))
Proof is in Appendix D, and extends the classical results from Slivenko-Cantelly theorem and DKW bound into an adversarial setting. We have detailed our new theoretical findings in Section B. The bound in Theorem 5.3 exhibits the following properties: i) is forward-shifted with respect to the true CDF, meaning it exhibits delayed reaction to increasing \ compared to the true CDF. The maximum delay is on the order of ((TTog K //ming rix). ii) The value of the CDF estimator also deviates from the true estimator by the amount O(ylog K/K). Consequently, as K and (ming n4)/ log K tend to infinity, the generalization gap becomes zero. iii The bound holds uniformly over all
In a similar fashion, one can define the Wasserstein distance between any two meta- distribistissss p, pL E MM² (Z) with respect to any valid transportation cost over the space of measures M (Z), such as the ordinary Wasserstein distance.
Definition 6.2 (Wasserstein metric over M For any two meta-distributions μ, μí' E M² (Z), assume a distributional transportation cost such as ordinary Wasserstein distance We (.-)). where c is a bounded and proper (according to Definition 6.2) transportation cost on 2 x 2. In this regard,
6

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Disstriuutional Shifts
Bpx (Pk)
distributionally robust loss of h around pe:
Bpg (P)
Epen (Ep le (y. (X)))) S {0(())) (E)
sup ('
( 1 K
log ((KKK)1)))) 1
K K
1 1kk
K
o
log
E6
f
The proof is provided in Appendix E. Similar to Theorem 5.2, Theorem 6.3 offers a robust bound on the expected loss under Wasserstein meta-distributional shifts using Ü (z). Once again, the generalization gap decreases asymptoti- cally as both K and (minke]j] ns.) log K increase with
Figure 3. A graphical illustration of the core idea behind Theorem 6.3. Each tuple pı.K that satisfies the constraints corresponds to one possibility for n', via extending the local risk of P&s to their worst-case out-of-distribution values in B., (Px). Therefore, we maximize over all such Pi:K to account for the worst p².
rate O (Vlg K/K + maxke[K] Ay log( (nx)). It is important to note that the inherent robustness of against Wasserstein-type distributional shifts, if it exists, would be reflected in (')(s,, thereby reducing the bound.
let us define
| - 1 llw.
inf B(P.))= (W (P,Q)) (14) rEC(pa))
A notable contribution of our work in this section is that we show robust evaluation against Wasserstein adversarial attacks to μ is possible using only QV, (h, p) values. In other words, it is not needed to move data points into a central server to perform collective attacks, and each client can independently assess the performance of h under local attacks. However, the budget values Pk for each client need be carefully selected. In Section 7, we show this is possible the server-side in polynomial time. Figure gives graphical illustration of the procedure in Theorem 6.3.
as the Wasserstein distance between μ and according to transportation cost We.
Here, C (u,,() is the set of all couplings (joint measures in M (Z) x M (2)) with a and μ' as their respec- tive marginals. Accordingly, for & 2 0 and P E M, we define the Wasserstein ball of radius e around P M as B. (P) A [Q] We (P,Q) S E}, where the trans- portation cost is hidden from formulation for the sake of simplicity. Similarly, one can define the Wasserstein ball around meta-distribution μ E .M with radius s as Ge (w) A {n'l || - v'w I =}} which is the set of mistadisttibuttons with a mittatiistrbbutiona) Wasserstein distance of most E from p.
7. Asymptotic Minimax Optimality, Privacy, and Computational Efficiency
In this section, we address the computational complexity of our proposed empirical upper-bounds in Theorems 4.1, 5.2, 5.3 and 6.3 both the server and client sides. We also discuss their privacy w.r.t. local user data. Finally, we prove their asymptotic minimax optimality.
We now present our main result of this section: quasi- convex (and thus polynomial-time optimization problem that provides empirical meta- ditt-iiittiuuionlllyy robust evalua- tion guarantees against Wasserstein shifts, with a asymptoti- cally vanishing generalization gap.
Remark 7.1 (Server-side Computational Complexity). The server-side optimization problems in Theorems 5.2 and 5.3 are convex and efficiently (in polynomial totomiill-tmeeeee w.r.t. K) solvable. Fach client queried only once for their non- robust (ordinary) loss value (px 0). Robust local losses are not required for f-divergence shifts, since the reweight- ing attack can be carried out entirely at the server-side. On the other hand, the bound in Theorem 6.3, i.e., Ū+ (c), is the solution to quasi-convex program, where a standard bisection method (c.g.. Algorithm 1 in Appendix F), can approximate Ü* (e) within an arbitrary error margin A > O, in polynomial time w.r.t. K and 1- The total query budget per client in this case is also polynomial with respect to both K and log x
Theorem 6.3 (Empirical Evaluation with Wasserstein Ro-
bustness), Consider the same setting as in Theorem 5.2. Let be bounded and proper (according Definition 6.2) transportation cost on Z x Z. For any given 5, > 0, consider the following constrained optimization problem:
1
Ú
(E)
sup
QU (k.
(15)
K
PLUMPK
E/K
k=1
K
1 K
log K+2
subject to
Pk S 8
1
+ +Ci
K
1=1
where C1 is a universal constant. Then, the following bound holds with probability at least for the meta-
Remark 7.2 (Client-side Computational Complexity). For the case of f-divergence shifts in Theorems 5.2 and 5.3,
7

---

Certifiably Robust Model Evaluation in Federated Learning under Meta- Meta-Distributional Shifts
clients only return the ordinary loss values which can be computed in time O (mx) at client k. In Theorem 6.3, as- sume the transportation cost e is convex with respect to its second argument and is differentiable. Then, the client- side optimization problem to determine QV (h, p) in equa- tion 15, for any given h and p. is convex (Sinha et al., 2018). A standard stochastic gradient descent algorithm can approx- imate QV (h, p) within an arbitrary error margin A 0, with polynomial time complexity relative to A
cifar10 feature
eifart0 label
1.0
0.8
0.8-
0.6
0.6
0.4
014
0.2
02-
0.0
0.0
1D
72
96
10)
66
10
maagenettteature
imagenett-lae -acne-----ee
1.0-
1.0
0.6
0.6
0.6-
0.6
Proofs of Remarks 7.1 and 7.2, as well as the bisection method in Algorithm can be found in Appendix F. Remark 7.3 (Privacy). All empirical bounds in this work only use the local ordinary or adversarial loss values, with- out direct access to local private samples or model gradients. In particular, the empirical value (E) in equation 15 re- lies solely on the Wasserstein adversarial loss of clients, i.e., (h, p) for polynomially many values of To the best of our knowledge, there are no well-known privacy attacks capable of effectively recovering private data from this procedure. It should be noted that providing Differential Privacy (DP) certificates goes beyond the scope of our work.
6.4-
0.4-
0.0
24
5B
90
04
70
Accuraty
Accurasy
Figure 4. Non-robust Risk CDF bounds for unseen clients. Here. "Meta" refers to the main population with 1000 nodes. DKW- robust bounds are depicted only for tightness comparison.
Notably, working on novel attacks or providing information- theoretic analysis for the recover-ability of private data from multiple local adversarial loss values can be a proper future research direction. Finally, the following remark (proved in Appendix F) provides tightness guarantees for our bounds. Remark 7.4 7.4 (Asymptotic Minimax Optimality). All em- pirical upper-bounds in Theorems 4,1,5.2, 5.2, 5.3 and 6.3 are asymptotically minimax optimal, which means they can be achieved by a worst-case shift when K and all ng/ log K grow toward infinity. This means our bounds are tight and cannot be improved, at least when network and local dataset sizes become sufficiently large.
Figure 5. Meta-distributional shifts based on resolutions (left) and colors (right). (a) Sample images from each resolution/color. (h) Average number of samples per resolution/color within each net- work selected from the meta distributions. (c) Histogram of model accuracy densities for the two meta distributions.
Feature Distribution Shift: Each sample x (k) in the dataset is manipulated via transformation chosen randomly for each node. Specifically, each user is assigned a unique matrix (4) and shift vector 8(k), and the data is modi- fied as X (kk) are respectively random matrices and vectors with i.i.d. zero-mean Gaussian entries. The standard deviation varies based on the dataset: 0.05 for CIFAR-10 and SVHN, 0.1 for EMNIST, and 0.01 for ImageNet.
8. Experimental Results
Our work is mainly theoretical; In any case, we present a series of experiments on real-world datasets to show tight- ness and computability of our bounds in practice. First, we outline our client generation model and present number of non-robust risk CDF guarantees. A more complete set of experiments with complementary explanations can be found in Appendix G. We simulated a federated learning scenario with n = 1000 nodes, where each node contains 1000 local samples. The experiments were conducted using four different datasets: CIFAR-10 (Krizhevsky al., 2009), SVHN (Netzer al., 2011). EMNIST (Cohen al., 2017), and ImageNet (Russakovsky et al., 2015). To create each user's data within the network, we applied three types of affine distribution shifts across users: This assumption is generally not restrictive, as any norm ex- hibits this property
(I + A x()) + -(R), where AA) and
Label Distribution Shift: Here, we assume that each meta- distribution is characterized by a specific a coefficient. To generate each user's data under this shift, the number of samples per class is determined by Dirichlet distribution with parameter a. In experiments, we
0.4.
This shift combines both the feature and label distribution shifts described above to create a new distribution for each user.
Feature & Label Distribution Shift:
Figure 4 illustrates our bounds on the risk CDF of unseen
8

---

Certifiably Robust Model Evaluation in Federated Learning under Meta- Cetta-iitributtinall Shifts
Culor
cifar10-trature
cifar10-lsbel
EmaneeSerpet Cal-iquar Dotoart C627
Comolalte Probeshit
1.0
1.0
Jegirt
Sourcs
0.8
day
0.6
0.4
0.6
Dhraar 0.34
0.0
50
00
03
70
0.0
60
70
90
Imagenet featurre
Imagenet label
Conulative Probaliity
1.0
1.0
0.6
0.6
12
0.4
02
Wiliio
0.3
Wasiggo
Meta
Meta
0.0
0.0
50
GG
69
36
60
66
70
Figure 6. f-divergence certificates for two meta detaadistributions based on resolutions (Left) and colors (Right).
Accuracy
Acturacy
Figure 7. Wasserstein- certificates for unseen clients. "Meta" refers to the main population with 1000 nodes. Dotted curves are based on 500 networks within the population.
clients with no shifts. We selected 500 nodes from the popu- lation and considered 500 other nodes as unseen clients. We then plotted the CDFs based on 500 samples and confirmed that our bounds hold for the real population as well. Due to the standard DKW inequality, the empirical CDF a good estimate for the test-time non-robust risk CDF.
in (Sinha et al., 2018). More detailed experiments with vari- ous levels of tightness are shown in Figure 10 in Appendix G. Although our theoretical findings in Section 6 focus on the average risk and not the risk CDF, extended the same framework to the CDF in this experiment to explore whether the theory might also apply. The results were positive, sug- gesting potential for extending our theoretical findings in this area.
8.1. f DDivergennce Meta- Dettr-iistibutionall Shifts
We assumed users belong to two distinct deta-distributions:: the source and the target. CNN-based model is initially trained on network of clients sampled from the source. The resulting risk values are then fed into the optimization problems in Section 5 to obtain robust CDF bounds, consid- ering both the Chi-Square and KL divergence as potential choices for f. Finally, we empirically estimate the risk CDF for users from the target meta-distribution and validate our bounds. Specifically, we tested our certificates in two dis- tinct settings using the CIFAR-10 dataset (see Figure 5). We generated various image categories with differing res- olutions or color schemes, and then sampled from these categories to create different distributions. More details of this procedure can be found in Section G.
9. Conclusion
This work introduces new polynomial-time computable per- formance bounds to guarantee the performance of a model h on an unseen network B, using only data and queries from network A. The key assumption is that the meta-distributions behind user data in the two networks are E-close, measured by d-divergencc or Wasserstein shifts, which address diverse practical scenarios. The bounds, backed by rigorous proofs, achieve vanishing generalization gaps network size K and normalized samples grow. Novel contributions include a robust GC theorem and DKW bound for f-divergence shifts. Experiments confirm the bounds' tightness and efficiency.
Figure 6 verifies our CDF certificates based on both chi- square and KL--divergence (dotted curves) for the target meta distribution (orange curve). As can be seen, bounds have tightly captured the behavior of risk CDF in the target network. More detailed experiments are shown in Figure 9 in Appendix G.
Impact Statement
This paper proposes a certifiably robust evaluation frame- work for federated learning under meta- meta-distributional shifts, providing theoretical guarantees on performance under de- ployment shifts. The proposed approach may benefit real- world federated systems by improving reliability and trust in evaluation across diverse clients. However, if misapplied without properly validating the assumptions on shift struc- ture, the certificates may give false sense of robustness. Care should be taken to ensure the theoretical assumptions hold approximately in practice, and to transparently com- municate the limitations of the guarantees.
We then used the above-mentioned affine distribution shifts to create new domains according to a Wasserstein metric. Figure summarizes our numerical results in this scenario. To generate different networks within the dictrdiittiiutiion, we applied the affine distribution shifts described in Section G.I. Once again, the results validate our certificates, this time for Wasserstein-tyy shifts. It is important to note that the bounds presented here remain tight, particularly under adversarial attacks as defined by a distributional adversary

---

Certifiably Robust Model Evaluation in Federated Learning under Metaa-Distributional Shifts
Acknowledgments
Theo Diamandis, Yonina Eldar, Alireza Fallah, Farzan Far- nia, and Asuman Ozdaglar. A wasserstein minimax frame- work for mixed linear regression. In International Con- ference on Machine Learning, pages 2697-2706. PMLR, 2021.
The work of Farzan Farnia is partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China, Project 14209920, and is partially supported by CUHK Direct Research Grants with CUHK Project No. 60 and 4937054.
Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribu- tion function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.
References
Anurag Ajay, Abhishek Gupta, Dibya Ghosh, Sergey Levine, and Pulkit Agrawal. Distributionally adaptive meta reinforcement learning, Advances in Neural Infor- mation Processing Systems, 35:25856 25869, 2022.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Per- sonalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
Hassan Ashtiani, Shai Ben-David, Nicholas Harvey, Christo- pher Liaw, Abbas Mehrabian, and Yaniv Plan. Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes. Advances in Neural Information Processing Systems, 31, 2018.
Farzan Farnia, Amirhossein Reisizadeh, Ramtin Pedarsani, and Ali Jadbabaie. An optimal transport approach to per- sonalized federated learning. IEEE Journal on Selected Areas in Information Theory, 3(2):122-71,, 2022.
Adnan Ben Mansour, Gaia Carenini, Alexandre Duplessis, and David Naccache. Federated learning aggregation: New robust algorithms with guarantees. arXiv preprint arXiv:2205. 10864, 2022.
Ruize Gao, Feng Liu, Jingfeng Zhang, Bo Han, Tongliang Liu, Gang Niu, and Masashi Sugiyama. Maximum mean discrepancy test is aware of adversarial attacks. In Inter- national Conference on Machine Learning, pages 3564- 3575. PMLR, 2021.
Jose Blanchet and Karthyek Murthy. Quantifying distribu- tional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-600, 2019.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM journal on optimization, 2344):234,-2368, 2013.
Stephen Boyd. Convex optimization. Cambridge UP, 2004.
Wei-Ning Chen, Graham Cormode, Akash Bharadwaj. Peter Romov, and Ayfer Ozgur. Federated experiment design under distributed differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 2458- 2288-246..16 PMLR, 2024.
Peter W Glynn and Donald L Iglehart. Importance sampling for stochastic simulations. Management science, 35(11) l): 1367-1392, 1989.
Kai Hu, Yaogen Li, Shuai Zhang, Jiasheng Wu, Sheng Gong, Shanshan Jiang, and Liguo Weng. Fedmmd: A federated weighting algorithm considering non-iid and local model deviation. Expert Systems with Applications, 237:121463, 2024.
Yiqiang Chen, Wang Lu, Xin Qin, Jindong Wang, and Xing Xie. Metafed: Federated learning among federations with cyclic knowledge distillation for personalized healthcare. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Yongzhe Jia, Xuyun Zhang, Amin Beheshti, and Wanchun Dou. Fedips: Heterogeneous federated learning for mul- tiple tasks with local parameter sharing. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), 2024.
Shu-Ling Cheng. Chin- Yuan Ych, Ting-An Chen, Eliana Pastor, and Ming-Syan Chen. Fedger: Achieving perfor- mance and faimess for federated learning with distinct client types via group customization and reweighting. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), 2024.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 international joint conference on neural networks (IJCNN), pages 2921-2922 IEEF, 2017.
Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Haafiezzadeh-baadee Wasser- stein distributionally robust optimization: Theory and applications in machine learning. In Operations research
10

---

Certifiably Robust Model Evaluation in Federated Learning under Metaa-Distributionall Shifts
& management science in the age of analytics, pages 130-166. Informs, 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bis- sacco, Baolin Wu, Andrew Y Ng. al. Reading digits in natural images with unsupervised feature learning. In NIPS workshop on deep learning and unsupervised fea- ture learning, volume 2011, page 4. Granada, 2011.
Yassine Laguel, Krishna Pillutla, Jéröme Malick, and Zaid Harchaoui. Superquantiles at work: Machine learning applications and efficient subgradient computation. Set- Valued and Variational Analysis, 29(4):967-996, 2021.
Kumar Kshitij Patel, Lingxiao Wang. Blake E Woodworth, Brian Bullins, and Nati Srebro. Towards optimal com- munication complexity in distributed non-convex opti- mization. Advances in Neural Information Processing Systems, 35:13316 2022.
Haoyu Lei, Shizhan Gong, Qi Dou, and Farzan Farnia. pfedfair: Towards optimal group fairness-accuracy trade- off in heterogeneous federated learning. arXiv preprint arXiv:2503. 14925, 2025.
Krishna Pillutla. Yassine Laguel, Jérôme Malick, and Zaid Harchaoui. Federated learning with superquantile aggre- gation for heterogeneous data. Machine Learning, 113 (5):2955-3022, 2024.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning with matched averaging. In Proceedings of the 34th Conference on Neural Informa- tion Processing Systems (NeurIPS), 2020.
Hamed Rahimian and Sanjay Mehrotra. Distribution- ally robust optimization: A review. arXiv preprint arXiv: arXiv:/908.055 2019.
Bingyan Liu, Nuoyan Lv, Yuanchun Guo, and Yawen Li. Recent advances federated learning: A systematic survey, Neurocomputing, page 128019, 2024.
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. Advances in Neural Information Processing Systems, 04-21554-21666 2020.
Mi Luo, Fei Chen, Dapeng Hu, Yifan Zhang, Jian Liang, and Jiashi Feng. No fear of heterogeneity: Classifier calibration for federated learning with non-iid data. In Advances in Neural Information Processing Systems 34 (NeurIPS), 2021.
Olga Russakovsky. Jia Deng, Hao Su, Jonathan Krause, San- jeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpa- thy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 11::211-255 2015.
Mengmeng Ma, Tang Li, and Xi Peng. Beyond the fed- eration: Topology-ave federated learning for gener- alization to unseen clients. In Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages -3890. PMLR, 21-27 Jul 2024.
Seyed Amir Hossein Saberi, Amir Najafi, Abolfazl Mota- hari, and Babak Khalaj. Sample complexity bounds for learning high-dimensional simplices in noisy regimes. In International Conference on Machine Learning, pages 29541.. PMLR, 2023.
Sarah Matta, Mathieu Lamard, Laurent Borderie, Alexandre Le Guilcher, Pascale Massin, Bernadd Rottier, Beat- ricé Cochener, and Gwenolé Quellec. Domain generaliza- tion for multi-diseass, detection in fundus photographs. In 2024 46th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), pages 1-4. IEEE, 2024.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certi- fying some distributional robustness with principled ad- versarial training. In International Conference on Learn- ing Representations, 2018
Behnaz Soltani, Yipeng Zhou, Venus Haghighi, and John Lui. A survey of federated evaluation in federated learn- ing, arXiv preprint 2305::::3000000700 2023.
Colin McDiarmid et al. On the method of bounded differ- ences. Surveys in combinatorics, 141(1):148-188) 1989.
Michel Talagrand. The glivenko-cantelli problem. The Annals of Probability, pages 837-870, 1987.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273- 1282. PMLR, 2017.
Yue Tan, Guodong Long, Lu Liu, Tianyi Zhou, Qinghua Lu, Jing Jiang, and Chengqi Zhang. Fedproto: Feder- ated prototype learning across heterogeneous clients. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022.
Ronak Mehta, Vincent Roulet, Krishna Pillutla, and Zaid Harchaoui. Distributionally robust optimization with bias and variance reduction. In The Twelfth International Conference on Learning Representations (ICLR), 2024.
Zhenyi Wang, Xiaoyang Wang, Li Shen, Qiuling Suo, Kaiqiang Song, Dong Yu, Yan Shen, and Mingchen

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
Gao. Meta-learning without data via wasserstein
distributiionally-robbt model fusion. In Uncertainty in Artificial Intelligence, pages 2045-2055. PMLR, 2022.
Jun Wu, Jingrui He, and Hanghang Tong. Distributional network of networks for modeling data heterogeneity. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 3379- 3390, 2024a.
Xinghao Wu, Xuefeng Liu, Jianwei Niu, Haolin Wang, Shaojie Tang, and Guogang Zhu. Fedlora: When per- sonalized federated learning meets low-rank adaptation. In International Conference on Learning Representations (ICLR), 2024b.
Mang Ye, Xiuwen Fang. Bo Du, Pong C Yuen, and Dacheng Tao. Heterogeneous federated learning: State-of-the-art and research challenges. ACM Computing Surveys, 56(3):
1-44, 2023.
Honglin Yuan, Warren Morningstar, Lin Ning, and Karan Singhal. What do mean by generalization in federated learning? arXiv preprint I 10. 14216, 2021.
Syed Zawad, Absan Ali, Pin- Pin-Yu Chen, Ali Anwar, Yi Zhou, Nathalie Baracaldo, Yuan Tian, and Feng Yan. Curse or redemption? how data heterogeneity affects the robust- ness of federated learning. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 10807-10814, 2021.
Yan Zeng, Yuankai Mu, Junfeng Yuan, Siyuan Teng, Jilin Zhang, Jian Wan, Yongjian Ren, and Yunquan Zhang Adaptive federated learning with non-iid data. The Com- puter Journal, 66(1 1):27)8-2772, 2023.
Yibo Zeng and Henry Lam. Generalization bounds with minimal dependency hypothesis class via distribution- ally robust optimization. Advances in Neural Information Processing Systems, 35:27576-27599 2022.
Jie Zhang, Bo Li, Chen Chen, Lingjuan Lyu, Shuang Wu, Shouhong Ding, and Chao Wu. Delving into the adver- sarial robustness of federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
Luhao Zhang, Jincheng Yang, and Rui Gao. A short and gen- eral duality proof for wasserstein distributionally robust optimization. Operations Research, 2024.
Yao Zhou, Jun Wu, Haixun Wang, and Jingrui He. Adver- sarial robustness through bias variance decomposition: A new perspective for federated learning. arXiv preprint arXiv:2009.09026, 2022.
12

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
Sampled Histograms
Sampled Histograms
clioet
cllest
Wobundiy
Spnce of All Distributions
400
clinel
0.5
Source Meta Distribution
Tirget Meta
Discibution
clinet
8.00
cdinsr
020
Inttahity
6:5
676
Figure A graphical illustration of meta-distributional shifts between two different networks (or societies) of clients/users. Heterogeneous user data distributions be considered as i.i.d. samples from meta-distribution. In this example, clients from meta meta-distribution primarily have vehicle images, while those from another meta-distribution mostly have animal images.
A. Complementary Review of Previous works
In this section, review several related works in federated training and evaluation of models with non-IlD clients. We then review a series of known (mostly theoretical) results regrading generalization gaps and shortcomings of current methodologies related to our problem set in this paper, i.c., beta testing in FL scenarios.
A.1. Generalization in FL.
The challenge of generalizing FL models to unseen clients and distributions has been studied in several related works. Li et al. (2020) introduce method to address the heterogeneity of client data, focusing improving the generalization of FL models. Similarly, Ma et al. (2024) propose a appology-aware federated learning approach that leverages client relationships to enhance model robustness against out-of-federation data. Also, Zeng et al. (2023) explore adaptive federated learning techniques to dynamically adjust model parameters based on client data distributions. The robustness of FL models against distribution shifts and adversarial attacks has been the focus of several related references. Reisizadeh et (2020) propose robust federated learning framework handle affine distribution shifts across clients' data. Their proposed framework incorporates
distribution shift model to account for device-dependent data perturbations. Also, Zhang et al. (2023) conduct comprehensive evaluations on the adversarial robustness of FL models, proposing the decision boundary- -based FL Training algorithm to enhance the the trained model's robustness. Zhou et al. (2022) gain insight from the variance decomposition to improve adversarial robustness in FL. Also, Ben Mansour et al. (2022) propose a robust aggregation method to reduce the effect of adversarial clients.
A.2. Non-lID Federated Learning
The heterogeneous nature FL, where clients have different data distributions has been a topic of great interest in the literature. In particular, modeling the heterogeneity of local data distributioonsdaaaasts via assuming a higher-level meta-distribution has been the center of several researches.
13

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
See, for example, Wu et al. (2024a); Chen al. (2023); Patel et al. (2022); Matta et al. (2024). Please refer to Figures 1, and 8 for more illustrative definition of meta-distribution over local statistical empirical distributions in a heterogeneous and non-IID network. In this regard, Fallah et al. (2020) introduce a personalized federated learning framework based on model-agnostec meta- meta-learning, which provides performance guarantees by optimizing for data distribution heterogeneity. Farnia et al. (2022) propose an optimal transport approach to personalized federated learning by learning and inverting the optimal transport map between the distribution of clients, which has been further extended to fairnss--awaee personalized federated learning in (Lei et al., 2025). Diamandis et al. (2021) propose a Wasserstein- framework to federated learning under the non-IlD scenario by training a mixed linear regression model capturing the non-IID-ness of the clients' data, Luo et al. (2021) propose a classifier calibration method that adjusts for bias in heterogeneous data, offering improved performance guarantees in non-IID settings. Tan et al. (2022) develop FedProto, a framework that leverages prototype learning to improve convergence and robustness under non-convex objectives. Moreover, Wu et al. (2024b) propose FedLoRA, which adapts low-rank parameter sharing techniques to mitigate the effects of heterogeneity in personalized federated learning. Also, Cheng et al. (2024) and Jia et al. (2024) introduce group- croup-based customization and local parameter sharing strategies, respectively, to provide fairnsss and efficiency guarantees for heterogeneous client types and multiple tasks in FL. A recent work on using super-quantiles in FL with heterogeneous clients is (Pillutla et al., 2024), which focuses on optimization and convergence aspects of the this problem.
A.3. Theory of Federated Model Evaluation
Evaluating models over networks of clients, also known as beta testing, or alpha/beta testing, or A/B testing, involves evaluating the performance of model or application on a small, randomly selected sample of potential users before wider deployment (Soltani et al., 2023). Specifically, this process assumes that central server has access to a limited subset of K clients from large network and can request these clients to evaluate a given machine learning model la on their local data. The clients then report the results to the server. The objective is to estimate the average performance of the model across the entire network based on this limited sample (Liu et al., 2024).
Several critical challenges emerge in beta testing scenarios: i) Data Privacy: Can we reliably assess the average performance without direct access to clients' local data? ii) Sample Efficiency: How many randomly selected clients are necessary to achieve a reliable performance assessment? iii) Meta--istributionnl Robustness: How can we guarantee a minimum level of performance for the model if the underlying considerations include the computational efficiency of server-side and client-side algorithms required for such evaluations.
governing the clients/users changes slightly? Other
Questions (i) and (ii) above are relatively well-addressed in the literature, either through federated evaluation frameworks (see Sections A. and A.2), or via conventional concentration inequalities (see, for example, our Theorem 4.1). However, the challenge of Distibbitrib Robust Assessment (M-DRA) remains underexplored. This problem addresses the robustness of model evaluation when the meta-distribution governing client data (μ) shifts slightly to new distribution (p'). A straightforward yet naive approach tackle this problem is to use the concept of Maximum Mean Discrepancy (MMD) (see Hu et al. (2024) or Gao et al. (2021)) in order to provide a bound on the performance of h on the target meta-distribe distriibiti ,', based on its performance on the source meta- dittriiittbbttinnn μ (Sinha et al., 2018). Mathematically, for any meta-distribution u' which is in an e-vicinity of μ. we have:
Ep [Ep (1 (1,,((()))) Eppn [Ep (1 (y, (x + Ex [Ep (2 (y, (w, (X)))
S Epnn (Er (2 (y, h ( sup Ep--p [E (v. h (X)))
hEи
Eppn [Ep (1 (y, h (X))) + MMD (n, (M)),
(16)
where H. is a class of functions that h belongs to, and Epr-p (-) is defined as Ey (-) - Ey (-). This way, closeness of y' to (e-vicinity) is reflected into the MMD value, i.e., MMD is proportional to e. Also, note that the first term, i.e., Eyep [E (E (y. h (X))) can be estimated according to any unbiased averaging over the sample distributions Pt...., Pk of y (and not p²), or their empirical counterparts Pi:k-
While MMD offers promising starting point, however, the gap term MMD (n, μ (H) does not shrink as K or either of n&s increase asymptotically. It is an e-dependent and non-vanishing error term that inflates the adversarial loss of h regardless of any possible inherent robustness in h around μ. To the best of our knowledge, there are no prior works that have already addressed this issue in federated beta testing (or model evaluation in general).
14

---

Certifiably Robust Model Evaluation in Federated Learning under Neta-Distribbutinaal Shifts
B. Uniform Convergence of Empirical CDFs from Adversarial Samples: GC Theory Revisited
Assume we are given n i.i.d, samples distribution P. denoted by XI...., Xn E R and we aim to estimate the true cumulative distribution function (CDF) of X P based on these empirical observations. The Glivenko- Cantelli theorem provides strong guarantees on the asymptotic behavior of the worst-case error when estimating a CDF from a finite number of i..d. samples (Talagrand, 1987). The theorem states that the - -nomm of the difference between the true CDF of X P. denoted by F, and its empirical version based on n i.idd. samples, denoted by F., which can be formulated as
Cdivenko-Cantelli
P (x) A Σ 1(x
Ve E.,
almost surely converges to zero as n approaches infinity. Mathematically, this is expressed as:
lim
F
Fr
2 0.
(17)
Furthermore, the well-known Evoretzky-Keifers Wolfowit (DKW) theorem provides non-asymptotic bounds for this asymptotic behavior.
Lemma B.1 (DKW Inequality (Dvoretzky et al., 1956)). Let X be a measurable subset of and let P be any probability measure supported on X. Let XI,-.., X, R be n iid. samples from P. Then, the following bound holds for the noo-norm of the difference between the empirical and true CDF of P:
log 3
IP
sup XER
P(X2M)
Σ X)
S
- 8,
(18)
n
2n
iE|m
for any 5 >
The proof of this lemma can be found in the reference. This result allows us to provide uniform convergence guarantees on the tail probability of the loss of h, i.e., IP( (y, h (X)) 2 X) for any À E, based on K i.id. observations of the loss across the network. By "uniform." " between the empirical and statistical tail probability is consistently bounded.
that, with high probability over the sampling of the K users, the worst deviation
For the case of f f-divergence robustness, we show that it is also possible to derive an asymptotically consistent and uniform bound for the risk distribution (CDF) over the target network, which estimates
n' (Ep [e (y, 2 X)
for all À E R. simultaneously. Here, pí represents the unknown target distribitti, which assumed be within an E-proximity of the source meta-distribution μ. Note that μ is also unknown, and our access is through K independent empirical realizations Pı,.... ... Px. where each P& is known only to client & via a private sample of size n&- To achieve this, we first derive robust version of the uniform convergence bound on empirical CDFs, i.e., the robust Dvoretzky- Wolfowitz (DKW) inequality:
Lemma B.2 (Robust Version of DKW Inequality). Let μ and p' be two probability measures T where j¹' is absolutely continuous w.r.t μ.. Assume X1,..., Xn for NN to be i.i.d. samples drawn from Suppose we have Dj (1(ll S for some 2 0 and proper convex function f()). For 8 > O, let us define the set An (E,5) 5) as
1 n
n log (
a Σ ((a) t2 n 1ea/n-1oop log )1)
An An (E, A a
a4
S cap
(19)
where constants C1 and depend only on f(-). Then, there exists a E An (E, 8) such that the following uniform bound holds with probability at least 1 --b. d:
so <o(vn-1oo log (7)
sup XER
1' (X
Σ a; (X, A
(20)
15

---

Certifiably Robust Model Evaluation in Federated Learning under Meta- Meta-Distributional Shifts
Proof of Lemma B.2. The proof for most of its initial parts follows the same path in the proof of Theorem 5.2. In particular, use Lemmas D.I and D.2 from the proof of Theorem 5.2 (see Section D) to show that the following events occur separately with probability at least
& for any d > 0:
3.
1
(x,) du((x))
log 1
S c1
(21)
n
m
SE(n]
Dy (Nl (1'llx)
1
E f vE(m)
(u'( du((;))
S
021
log X n1
(22)
where C1. C2 > 0 are constants depending on f()). These probabilities are with respect to the randomness in drawing i.i.d.
samples XI,..., X ~ p. This is equivalent to the following statement:
(x du(X.)
28
E An
2 1
(23)
2E(N]
3
Next, define (A) for as
(A(A) & w(X) S A),
(24)
where the weight function wXX) 2 is the unknown (bounded) density ratio between p' and jr, i.e.
(x)
(XX)
(25)
dx(X)
Since w() is non-negative, Fx (A) is non-decreasing in X, starting at when X = oC and not exceeding an upper-bound A +00 (due to absolute continuity property) X + co.
Consider the probability measure p². For 2 2, define Ai, Ai...... Ar such that (i) X3 = -o and X co, and (ii) I'(X < {;) = i/m for E [m - -1]. These X;, i E [m] U {0) represent the m-quantiles of μ². For any X E RR let i i= i(A) E [m] be such that x E A;). Then, the following chain of inequalities holds almost surely for all À E IR:
PA(A) (X < A) = P.00)) - (X s FA(AT) n' S xi) m²
- & A) = >
(26)
m
Thus, the following bound holds for all X E R:
F - n1xx < 1/1
= sup AER
Fa(A) - 11 S
- x;) + 1
K
max ie mm)....
(27)
m
On the other hand, for any fixed À E R, we have the following relation for the expectation of FA):
Σ w (Xx)I(XX A
E. En((P((A)] = Ey
Ry (X,) [\
n
1
dx'((X
1(X < A)dμ(x)
n du(x)
(X < A).
(28)
16

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
Given that the weight functions w (X;) for i [x]] are bounded, and I1.) {0, 1}, McDiarmid's inequality states that for any 0,
PP ((P.(2)) (X S X7) > >)) s 2e (0==))))=)
(29)
Therefore, using the union bound over all i 0, 1, ......... m, obtain:
Fx(A p¹ (X s 25) >E) >))])=))=+ = =2mm + 1)e (0=22((ne).
IP
max (E...
(30)
Equivalently, for any 8 > O, the following bound holds with probability least 1 1-8/3:
Pa(4))- - s xt) so = log
66(m + 1)
D18X
(31)
iE (0. (....
Using the preceding inequalities, in particular relations in equation 23, equation 27 and equation 31, we can say there exists Or E An such that the following bounds for Fa hold with probability at least 6:
Fv 1 S <
FT(A7) 10(x S 13) +
max m!.........
76(m + 1)
+ 1
1)
0
inf mENza
(2n) -log log
m
<
11 n log
(3)
(32)
8
Thus, the proof is complete.
A direct corollary of Lemma B.2 is the following robust (again with respect f-divergence adversaries) of the well-known Gilivenko-Cane Cantelll theorem:
Corollary B.3 (Robust Version of Glivenko-Cantelll Theorem). Let μ and yl be probability measures TR and let J - {X be an i..dd sequence drawn from μ. Assume μ. and pl are absolutely continuous with respect to each other. Additionally, suppose D, (p/(lp) S for some 2 O and a proper convex function [().. Then, there exists a non-negative sequence {a that can depend on L, has the following properties:
lim n-o
1 0a=1 =0=1 and
lim Σ (as) Se, n-00
(33)
n
1=1
1=1
and also satisfies the
the following condition:
lim sup n- XER
p (X A
n Σ
1
a1 (X, s a
(34)
-
Corollary B.3 follows directly from Lemma B.2.
C. Proofs of the Statements in Section
Proof of Theorem 4.1. The proof for the average risk is straightforward and combines several applications of McDiarmid's inequality (or, more simply in this case, Hoeffding's 's inequality). For any instance of distributions P. ~ μ. let us define the random variable Ç = CPP) as follows:
C(P) 2 ( (v,h(x)) P(dZ).
(35)
17

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Diistributional Shifts
where & denotes the loss function, and 2 is the space of possible outcomes. We omit the detailed proof that P being random variable implies C(P) is also random variable, as this follows from standard measurability arguments.
Now, for any 8 > O, we apply McDiarmid's inequality to obtain:
log K+1
IP
c c- F S
(36)
2K
K +
where the bound holds due to the one-sided version of McDiarmid's inequality, and the fact that E [0, 1] almost surely. Next, for each E [ we similarly have:
log K+1
L (1 (xx+))) Ep, [e (
P
(37)
T
2nk
K +
This follows from Hoeffding's inequality, given that the data points in the local dataset of the k-th client are i..d By the union bound, the above K + inequalities hold simultaneously with probability least 1 6. Finally, combining these inequalities gives us the desired bound in the theorem, thus completing the proof.
For the bound concerning the empirical CDF, the proof follows more or less the same path. Let us define the statistical query value of the kth client as QV,(h), i.e.,
QV (h) & Ep. (y. h (x))
(38)
where PE: is the true (unknown) data generating distribution which is assigned to client k E [K]. In this regard, according to Lemma B.I, for any 5 > 0 we have
1 E KE[K]
log 2(K+1)
8
P
sup XER
/r
Ep [e ((),
(QV 2 A)
S
2
2K
+1
Also, applying the McDiarmid's inequality for K times (once, with respect to each client & [K], the following bounds also hold:
n
(k) Vi h (x (x(1)) Ep, (x, V
log K+1
8
2
(39)
TIJ
2n1
K +
which show the boundedness of the deviation between the empirical query values QV (h) and statistical ones (h). This similar to the previous part of the proof. Again, applying union bound and combining all the inequalities mentioned so far in the proof, the final bound in the statement of the theorem holds with probability at least 8 and proof complete.
D. Proofs of the Statements in Section
Proof of Theorem 5.2. For each is E [K]. let us define the event (k) follows:
Σ (v) (x!") (x + log (
[++ (<"
(k) Ep. (y
(K)
(40)
Ték vE[Ma]
2n1
where, since E(-) is assumed to be a 1-bounded loss function and the samples are drawn independently, McDiarmid's R²3 (McDiarmid et al., 1989). For the rest the proof, we assume the density ratio
inequality tells us that IP (A) of the meta-distributions p. μ are bounded, i.e., we have
dyl de
(P)
SA, VP E (u),
(41)
18

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
for some positive A. We call this property the N-boundedness of density ratio. At the end of the proof, show that in problem have A & 1 ke. We now state and prove two essential lemmas which will be used in the subsequent arguments.
Lemma D.1. Consider two meta vetaadistribuutions μ. p' E M2 which are absolutely continuous with respect to each other and have a A-bounded density ratio for some A 2 1. For K E M, assume P Pk E M to be i.i.d sample distributions sampled from y. Then, for all e > O, the following concentration bound holds:
1
Σ KE[K]
(Pk)
2 S exp
2K
(42)
dp(Pt)
Ao 2-2
Proof of Lemma D.I. Due to the assumed mutual absolute continuity, μ and μ' share the same support. Therefore, for P ~ μ., define the scalar random variable
dp'(P)
<-<(P)
(43)
dp(P))
This variable is bounded by A-1 a.e. 0.5.
5 S A. Regarding the expected value of have:
(P)
J.a.
dP) du(P)= =1
E [C] Bp-n
(44)
dp(P)
dp(P)
Let 5s ((P)). Since ((P1), ................................ ((Pk) .(P(k) represent i.i.d. instances of s. McDiarmid's inequality states that:
2K
P
Σ KE[K]
CK
E
[c]
26
S exp
(45)
K
(A- A-12-1)2
which completes the proof.
Lemma D.2. For A Z 1, assume two meta-distributions pL E M are absolutely continuous with respect to each other and have a A-bounded density ratio. Let f be a convex function that satisfies the conditions described in Definition 5.1. For K N, assume P1 PI,..., E M to ii.d. sample distributions sampled from μ. Then, the following concentration
bound holds:
(D. (H'llH)
1
du' (Pk) di
-2Ke
Σ
2E Sexp
(46)
BW (f())
kE(K)
where BW (ʃ () is defined as:
BW ()
sup A-TGuESA
f(u)- f(v).
(47)
Proof of Lemma D.2. The proof follows similarly that of Lemma D.1. For P μl, let us define the random variable
<(P) - (du' dd'(P) (P)
du'
(48)
du (P)
Then, having defined ÇA = (Ph), we know that Si...., SK represent i.i.d. instances of Ç. Moreover, the expected value of Ç is the f-divergence between pL and
(
(du'(P) (
E(l = Epnn
D, (1'llA).
(49)
Finally, since pt and y have the b-buunded density ratio property, the following bounds hold almost surely:
G.S.
a.s.
Ç 5
sup
f(u)
2
inf SeSA
f(v),
(50)
A
SSSA
19

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
which means the range of is almost surely equal to BW (/ () A). Hence, again using McDiarmid's inequality, get the bound:
-2K BW ())
Σ kE[K]
CE - [[] 26 S exp
(51)
and this completes the proof.
With the lemmas established, let define additional events &2 and Es based on the concentration bounds:
& K Σ (Pk) dp((P)
S 1/2
(52)
KE[K]
= * &
(du(PP) du(PP))
/ Dy (4Cll + 1/2-
(53)
KEIK]
where C1, C2 are constants which only depend on and f()), according to Lemmas D.I and D.2. Based on the above arguments and the results the mentioned lemmas, we have P (P 2 K+3- Using the central idea for importance sampling (Glynn and Iglchart, 1989), the following equations hold for all p. p. and h:
( (du'(P)
-
du'(P)
E Epwp
Ep [e hy, du(P)
Ep (x), da(P)
du(P)
P [Ep [e (v, h (X))]]-
(54)
At this point, and similar to the idea of Lemma D.1, define &a as the event of the empirical loss meta-distribution p concentrates (with high probability) around its expected value, i.e.,
=
(
(d)(PP)
Epan
Er Ep (v. 5
1
dy' (Pa)
log ( (K+3)
Ep.. [e (y, (X)) AAV
(55)
K
du(Pk)
2K
kE[K]
Again, since
Ep L (y. h (X)) 2.. 0 S dp(Pk)
(Px)
3 A,
McDiarmid's inequality states that the probability bound PP (E.) > ススं holds. Our final definition in this proof is random set of meta-distributions & C MM2 which represents an empirical candidate for the neighbors of μ. Mathematically speaking, let us define:
G
M²
1
Σ kE(R]
du(Pt) du(Pk)
$ 111CK-11/2
K
1 Σ f
dv (Pa) du (Pt) (du
S SE+ C2K-111
(56)
K
KE[K]
which depends on and has a random (empirical) nature since also depends on sample distributions PI...., Px- Based on prior discussions and lemmas, we have yı' E G as long as the events ε2 and & hold, simultaneously. By further assuming
20

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
that events & and 5iahs s for & E [K] also hold, we can finally write the following chain of inequalities:
E Prpp
[Ep (y, (X))ll
(57)
dp'
log K+a
E
Ep, (y, (X))) + AV
K
(p{(Pt)
2K
kE|K]
(Pk) (pt(Pt)
log (K+3)
K+3) log
E.p. h AV
K
2K
K
2n1
kE[K]
kE[K]
a.e. 1
dv(Pk) du((P Pk)
K +
A
sup VEG
Pr ( +
log
K
2K
K
2mp
KE[K]
kE[K]
It should be noted that the condition v G can be interpreted as introducing
du(P))
Ak [K],
0rk
dp(Px)'
and force 01 Ok to satisfy the constraints in the definition of B²( Hence, this gives the high probability bound
claimed inside the statement of theorem. The only remaining part of the proof is to show events 51 ,5,, Es and & for all E [K] hold, simultaneously, with a probability at least 6.
For any event ç, let & denote its complement. Then, we already have
IP (<(()) P .ES... ......... (Ei)
5
Wk E [K].
K+3
In this regard, one can simply use the union bound and obtain the following chain of inequalities:
(U
P
stth (e)
US
Σ
P
P(())
K8
+
6
6.
(58)
K +
K K+3
kE(K]
kE(K]
This means the bound in the statement of theorem holds with probability at least and thus completes the proof. Finally, let derive upper-bound for A, a.k.a., the density ratio bound. According to the definition of f-divergence, we have:
[ {5(()) (dpd du (P)
]
Dy (4' (R) = Epnn
SE.
(59)
Assume there exists a region in the distributional space S (Z). where for all P EEE S the density ratio du' /du(P) is at least A, for some A 2 1. Then, we have D, (H' (()) 2 (S) f (A). Setting μ (S) equal to 8 (our high-probabiliyg error margin this problem), we get
(A) < E/8,
which means A < f (e/6). On the other hand, we already know that f is convex function (see Definition 5.1) which means f-1 must be concave. Additionally, we must have f(1) = 0. Therefore, the following inequality holds:
A f (E/0) 51+ (5-1 (0)) 1
(60)
where & does not depend on E.
Proof of Theorem 5.3. Similar the proof of Theorem 5.2, we begin by noting that, due to McDiarmid's inequality, for any
8 > with probability at least K6 the following set of inequalities holds simultaneously for all l e [K]: K+2
K+2 log
QV (M) (h) +
(61)
2nk
21

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributionall Shifts
Next, it can be readily verified that:
log (Kgg)
1 2
QV (h) A
Ak E [K].
(62)
2m
,
Additionally, note that:
EPP (QV (h) 2 A)] = μ (QV (h) 2 A).
(63)
The remainder of the proof simply involves applying the result of Lemma B.2 with maximum error probability of This concludes the proof.
26
K+2
E. Proofs of the Statements in Section 6
Proof of Theorem 6.3. Proof consists of two parts:
Proving the statement of theorem for the statistical case, where minke(K] ngg -> oo and thus we have (h, QV p) for all h E H. p 2 0 and & [K].
Replacing the statistically exact adversarial loss QV, p) which is based on the unknown distribution sample P'c with its empirically calculated counterpart (h,, p) which is computed based on the known (yet private) distribution Ps for all & E [K]. This part of the proof requires establishing uniform convergence bound over all values of p 2 0.
Part I The core mathematical tool used throughout the proof is the following duality result from (Sinha et al., 2018) (originally derived in (Blanchet and Murthy, 2019)) which works for general Wassersteinnconsttriie optimization problems:
Lemma E.1 (Proposition of Sinha al. (2018)). Let P be a probability measure defined over a measurable space D ((-) :: S + R be any loss function, e denote proper and lower semi-continuous transportation cost on Q x Q and assume
2 0. Then, the following equality holds for the Wasserstein- DRO around P:
sup Beaace (P)
Eq [e))] = inf 720
7 + Ep
sup E(Z') - 70 2) Z
(64)
Proof can found inside the reference. Also, (Blanchet and Murthy, 2019) and (Zhang et al., 2024) along with several other papers have theoretically analyzed alternative proofs. Based on the duality formulation in Lemma E. and considering the fact that meta-distribution μ is also "distribution" over the measurable space M,, one can rewrite the original Wasserstein-constrainee MDRO in the statement of the theorem in its dual form:
sup BPw [Ep [e (1) (X)]] n n'EG. (M)
inf 720
75 + E E sup EQ E[(((,,)(())
inf 200
Ey sup Eq (1, (0w
(65)
The main advantage achieved by this reformulation is the substitution of μ with the fixed meta-distribution μ inside the expectation operators. Therefore, the optimization no longer has to be carried out in the M² space. For the sake of simplicity in the proof, assume supreme value in equation 65 is attainable. This assumption is not necessary, and can be relaxed by using more detailed mathematical analysis which is replacing the optimal distribution Q" with Cauchy series of distributions and proceed with similar arguments. However, we have decided to avoid this scenario in order to simplify the proof. In this regard, let us define:
Q" (P, 2) A arg max Eo (v, (X))) - (P.Q) -)), VP E supp
(66)
Q
22

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributionaal Shifts
Then, the following relation holds:
Pp [Ep [e (y, (X))lI inf (En (x E'EG.
sup
720
inf (BpnH (B 1 (v. h (x))i]
720
BBp~ We (P. Q" (P:7)) - -e}-
(67)
which, can be simply rewritten as:
sup Epow [Ep ((),,(()))) inf By (EQ.(P.)) 1e (y, h (X))I 720
(m)
subject to Ep-μ DW. Q", (P,
Se. se.
(68)
Using a similar argument as before, let us assume the inf,20 in equation 68 also attainable and denote the optimal value by 7" y (J4, e). Once again, this assumption is not necessary and can be relaxed at the expense introducing more mathematical details and making the proof less readable. In this regard, we have:
sup Ep [Ep [e (y, h (x))]] Ex (BQ 16 (y, h (x))I]
(69)
# (n)
where it has been already guaranteed that the optimal parameter 7" 2 and optimal distribution Q" (P,7"), the following constraint holds:
E EPEN We (P.Q" (P,7")) Se.
(70)
For any supp (1) S M,, let define the following optimal robustness radius function
p" (P; A W. (P,Q* (P,7"))-
(71)
Therefore, the original MDRO objective in the statement of the theorem can be readily upper-bounded using the following distributionally robust formulation:
sup Epop h (x))ll = Epan (EQ (v. (X)]]
(M)
< Epnn
sup (P
Eq [e (x))(
(72)
Using the upper-bound equation 72 and the inequality condition on optimal Wasserstein radius functions p" (P) described in equation 70, we can proceed to the empirical stage of the proof. At this stage, the true expectation operators should be replaced by their empirical counterparts which are based i.i.d. realizations of meta-distribution μ., i... unknown distributions PI....,PA Pk and their known yet private empirical realizations, i.e., P: for é E [K].
For P ~ je, let us define the following new and real-valued random variables v (P) and C(P) as follows:
(PP) A sup
Eq l8 (x)))
QEB (P)
C(P) (P;
(73)
It should be noted that (P) is readily known to be (almost surely) bounded by 1, since E(-) is assumed to be 1-bounded. Additionally, the boundedness for C(P) directly results from the assumption that c is bounded transportation cost.
Lemma E.2. There exists R < too such that We have p² (P: << foror P ~ p.
Proof. The proof straightforward and directly results from the definition of Wasserstein distance:
C(P) e 0" (PPe,,)) W. (P.Q (P,r))
inf E, |c (Z, Z')l
"EC(P.Q"))
sup
clZ z') < +00,
(74)
Z.
which concludes the proof.
23

---

Certifiably Robust Model Evaluation in Federated Learning under Metaa-Distributional Shifts
Using similar series of arguments the ones explained in Lemmas D.1 and D.2 (proof of Theorem 5.2), together with the fact that (Pt)s )s all bounded by one can directly apply the McDiarmid's inequality and show that the following bound holds with probability at least 1
5 for any 8 >>> 0:
K42
Eq le (x)) + log K+2)
E PM
sup QEB
Ee Eele(y,h (P(
sup QEBwase
(75)
K kE(K)
(P.) (Pt)
(Pt)
2K
On the other hand, by using the boundedness property for ((P) proved in Lemma E.2 and applying McDiarmid's inequality once again, the following bound holds with probability 1 K+2 (for any > 0) for the empirical mean of ((P) over true sample distributions PI....,PP:
log K+2
log K+2
Σ ((P)) [c(P)) + V KE[K]
Setal
(76)
K
K
K
where 6j is known universal constant depending only on the bound on transportation cost Here, the last inequality is direct consequence of the property shown in equation 70.
Let S C I 20 be defined as the following subset:
S
(SI (GI..... (K) E R
Ca 2 0,
Ak
1 [K],
Σ
La setor
log K+2
(77)
K
K
kc(K)
So far, we have shown that
P ( (Pt) 5) 2
5
(78)
K 2
In a similar procedure to the one used in the proof of Theorem 5.2, union bound ensures that the bound in equation 75 and the mathematical statement of { (Px))EE E S simultaneously hold with probability at least following chain of bounds also hold with the same probability w.r.t. drawing of Pı,..., Px from pc:
26
Then the
K+2
sup Eprn' EP [8 (y, (X)II S Epap a (EGG(u)
sup QEB
Eq le (3, h (X))
log (Kt2)
sup QeBwan kE]K] (P))
Eq (1,hh
K
2K
log K+2
$ sup pES K
Σ
sup
Eo le (v. (X)))
kE(K]
QEB
QEBmam (Px)
2K
1
log K+2
sup PES K
Σ K)
QV (h. +
(79)
2K
For reasons that become clear in the final stages of the proof, we need to replace the set S with new one denoted by S' which should be defined as:
S' a (G...... (K) (G.....CK)
RK
CA Z
Vk [K].
1 K
E kE(K]
c4 Se 1+ 1) K
01
log K+2
K
2K
Evidently, replacing S' with S in the maximization step of equation 79, i.e., sup pup'' gives an upper bound for the original formulation of suppes. since each member of S' can be formed by taking member from S and add all radius values by constant e/ K. Obviously, this procedure only makes the adversarial loss value larger and hence all the bounds still apply.
24

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Diittributional Shifts
Part II So far, we have managed (partially) prove the proposed bound in the statement of the theorem in scenarios where ming ne and thus we have Pj 0.5. Ps for all l E [K]. At this stage of the proof we focus replacing
Q (h, =
sup QEB PM
Eq le (v. h (X)).:
(PL)
for any & E [K] and arbitrary 2 O, with its empirical version QV (h, p). Let us reiterate that we do not have any knowledge regarding Pk. and only client & has access to its empirical version Pa which is based on Th i.i.d. samples. Therefore. QV (h,p) p) is computable via the querying policy described in Section 3, while the true query value QV p) is always unknown.
To this aim, similar to (Sinha et al., 2018) first let us define the following Φ. (Z) function for y 2 0 and 2 E 2:
Φy (Z)
A sup
l (Z') - 70 (Z', Z) Z'EZ
(80)
where -(-,-) is the original transportation cost and é (Z) abbreviates é (y, h (X)) where we have omitted h for simplicity in notation. First, it can readily verified that if l is bounded between O and 1, so does oy for any y 2 0. Second, note that from Lemma E.1 we have the following duality formulation for QVn and QV for any Pk: 2 0:
QV (h, pk))
A
sup QEB (Pt)
Eq le (x)) inf tYpk + Ep b (Z)}}. 720
(81)
QV (h, Pk)
sup
EQ le (v. h (x)] = inf 720
PPk + Th xE(mx)
Σ
Φn (2
Duaa (Ft)
In the following, first we show that dy (Z), for any Z E Z is a Lipschitz function with respect to 7y where the Lipschitz constant only depends on the way the transportation cost e is bounded, i.c., the inherent boundedness of c or the compactness of Z. Additionally, we show that the optimal 7 2 0 in both minimization problems on the right-hand sides of equation 81 is bounded by a known constant. The latter result is deduced from the fact that all robustness radii Pr: k E [K] in the statement of theorem has known margin from zero Finally, we show the above-mentions properties can guarantee that E,, [ (Z)] uniformly converges to its true expected value Ep, ( (Z)) for all relevant value of y 2 0. Hence, the empirical and statistical query values are always within controlled and asymptotically small deviation from each other
regardless of the robustness radius value Pk-
In this regard, the following lemma shows that Φ, (Z) for any Z E Z is a Lipschitz function with respect to 7 2 0:
Lemma E.3. There exists a constant R 2 0 which only depends on transportation cost e such that function Φ., (Z) is R-Lipschite with respect to y 2 0, for all Z E Z.
Proof. For any two distinct values 7 2 O, let Z; and Z denote the optimal values for which the sup in equation 80 is attained. Similar to several previous arguments, attainability of the sup in this case is not necessary again, and thus this assumption is made for the sake of simplifying the proof.
Then, for any Z E Z we have:
by (Z) sup 8 {Zz) nc 2 (((z)) 70 (Z 2),
Z'EZ
by (Z) E (Zip) 9'0 (Zi,Z)) 2).
which directly gives us the following bound:
7/) o (Z) Φ (2) 2 -7 -7--7) (Z
(82)
Through a set of similar arguments and replacing and y. the following complementary bound can be achieved as well:
oy (Z) Φy (z) < - (r (00
(83)
25

---

always lower-bounded by zero which makes the whole objective to become larger than On the other hand, setting 7 Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
Therefore, the following inequality can be established according the boundedness of e (or alternatively, compactness of
)):
1 (Z) Φ, (Z) - h - 71 max {e(Z,, 2)} rE(o.)3
- h 71
sup cZ
Z'EZ
- Rh 7
(84)
which proves the Lipschitz-ness of d, with respect to ?.
The following lemma shows that optimal values of y in the right-hand side minimization of equation 81 (or the infimum-
achieving sequence case the infimum not attainable) is bounded by a known constant:
Lemma E.4. In both minimization problems on the right-hand side of equation 81, the optimal & value denoted by Yf (if
attained), or the tail of its sequence in case the inf is not attainable, satisfies 0 S - PE
Proof. Proof directly results from the fact that ((-) is bounded between and 1. Therefore, looking at the dual optimization problem equation 81, increasing 7 beyond 1/pk results in 7/4 > while the second term (i.e., the adversarial loss)
would (at worst) results in the objective be 1. Therefore, the optimizer inf,20 should not choose a ry value that is larger than 1/pp-
At this point, we can state the main lemma in the second part of the proof, which theoretically shows that empirical query values, i.e.. QV,,h,, p) for any fixed h e H and uniformly all p 2 0 converge to their true statistical expected values with a high probability.
Lemma E.5 (Uniform Convergence of Empirical Queries). For k E [K], assume the unknown sample distribution Pk (k) (k)) }} for i E [na] denote ny E N i.i.d. feature-label pairs drawn from Pk. The kth dataset is only known to client k. Then, for any fixed classifier h and any > 0, the following bound holds with probability at least 1 6/(KK+ 2):
and let ( (k) = [x!
QV (h.p) QV (h. so (1115 log
(K (K+2)) 22
sup P2#/K
(85)
=d
Proof. Using the dual formulation of Lemma 1, we can rewrite the main objective of the theorem as follows:
@V (h, p) QV p)
sup P2:/K
sup PE2:/K
inf 1920
TPP Ep. (0g (Z)]
inf hype + Ep, [Ø,, (2)1 420
(86)
Again, for the sake of simplicity in the proof let us assume both optimal values 7 and 7" in the minimization problems on the right-hand side of equation 86 are attainable. It should be noted that this assumption is not necessary and can be relaxed by adding more mathematical work. Then, from Lemma E.4 we already know
K
05
Pk
Let us partition the feasible search set of 7 2 0, i.e. [0, K/E) into L & small constant which should to be determined later in the proof. For each interval, let us choose representative (for example, the value at the beginning of the interval) denoted by % with = 1, L. Then, based on Lemma E.3, for any Ps E le/ K, 2Ke), any corresponding 7 E 1/p)) and all Z E 2 we have
[
R equal intervals, where 0 is 22
K
A
A
| (Z) 2r. (Z) S R|7 7p S R
(87)
3
K2R
K'
26

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributionall Shifts
where i* arg se(4] 17 7al- On the other hand, from the maximization problem that defines (*) in equation 15, have that
( KE+
K +
Pk I o
V / log
Ak E [K],
(88)
where we have omitted constants for the sake readability. Therefore, the above discussions directly lead to the following bound the statistical sense (i.e., with respect to Pt):
inf hyps + Ep. 10, (Z)ll min hripk + Ep, 10 (2) (E
720
min 1 7il (R + sup pk) xE(L]
K
E
(K + 2)
O
R+ KE
K Kog
&
K2R
1
log
R42 o
$ 0
(89)
K
Through a similar procedure, the following bound also holds for the empirical case (i.e., Pk). but this time almost surely:
inf 720
FPpk
+ PR, [dg [Z)]
min
Taps
Ep, 1 (Z)]
iE L)
a.e. S
1
1
log
K+2
A O
(90)
Therefore, according to the fact that Ps is an empirical estimate Ps based on ny i..d. samples, we have:
QV (h, QU (h. a.s.
1
1
log
K+2
sup pz:/K K
<
A
+
+
K
R
R
K
max RE[L]
Bj,
(oby (Z)]
Ep 10 (2)
(91)
Since ty for each [L] is a non-negative and 1-bounded (adversarial) loss function, simply applying McDiarmid's inequality and the union bound over all L values of yss would give us the following bound which holds with probability at least 1 5/(K + 2) for any
log
LIK K2)
max
E
(dg. (Z) - -Ep, (dy (2)
S
5
(92)
2n
which gives us the following bound for sup D2/// QU (h. (h. QVx (ha p)
with the same high probability:
RK- +2)
log
sup P26/K
QV (h, QV (h, (h. 5
inf A
AC(K,,,0)+
(93)
72.
where function ((.) is defined as
2 1
K+2 log
((K,E,8)
+
5
K
R
K
27

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
It should be noted that R is constant that does not depend other parameters. Also, we have minimized over A since the bound holds irrespective of A. Exact solution of the minimization problem in equation 93 is not needed, since choosing
A = O ( nk n=112 ! gives us the following bound:
log
sup P2c/K
QV (h, QV (h, 0o
(94)
T2k
and completes the proof.
By using the uniform convergence result from Lemma E.5 and applying it to all K clients simultaneously, see that (via a union bound argument) with probability at least K6/(K + 2) the empirical and statistical queries QV (h, pk) and Q (h, pk) are asymptotically close for all & E [K]. and uniformly for all robustness radii
E O KE+ K
(O(KE)
log((K +2)/6)
Pk
which considered for the maximization problem of equation 15. Finally, using another union bound argument incorporate the bounds from equation 75 and equation 78 in addition to the previous K events, say that with probability at least 1 5 the following bound holds:
sup Ep [E [e (v, h (X)) (a)
(K (K+2)mm
log
log K+2
S sup PES'
Σ
sup QEB
EQ (y (X))) + C2
K
Yh
2K
kE[K]
log
(K+2))m2
log ( K++2
sup PES'
Σ kE[K]
QV (h, Pk) Px) +
(95)
K
12k
2K
where is constant that only depends on either the transportation cost or the compactness of sample space Z. This completes the proof.
F. Proofs of Remarks in Section 7
Proof of Remark 7.1. We begin by discussing the server-side programs in Section 5, which address f-divergence meta- robustness, followed by the analysis in Section 6, which focuses on Wasserstein meta-robustness.
Server-side Programs in Theorems 5.2 and 5.3 optimization variables on...., Furthermore, the constraints define convex feasible set:
The objective function in both programs is a linear function of the
The constraint
1 K
ap 1 SC
for any positive constant C, is equivalent to the intersection of the two constraints: 1 ΣK S 1 C' and E 0g 2 C. These correspond to band region bounded by two hyperplanes in R. K forming a convex set.
The other constraint,
1 K
Σ f(ax) SE+C',
K Am
28

---

Certifiably Robust Model Evaluation in Federated Learning under Metaa-iistributional Shifts
Algorithm 1 Server-side Bisection Algorithm
Require: E,
input h, A > 0, and poly (K, log }) query budget for QV for all k E [K]
1: Initialize a +- min E(-) (or 0), +- max e(-) (or 1)
2: while a >
3: f (a + b)/2
4: Solve convex feasibility problem:
5: Find PI.....PK s/K such that
6:
R
EkE[K] PE se + R)) +av
K
7:
* EvE[K] @V, Pk) 2
8:
if problem is feasible then
9:
a a+
10: else
11: b
end if
13:
end while
output upper-bound b
K for constant C", represents the (s + -')-suelevel set of the convex function 7 Σ k=1 M(xx). The convexity of this function follows directly from the convexity of f(-), as stated in Definition 5.1. Consequently. this constraint also defines convex set.
Therefore, both programs feature linear objectives and feasible sets that are intersections of convex sets in RK implying that both programs are convex and can be solved efficiently (Boyd, 2004; Ghadimi and Lan, 2013). This completes the proof.
Server-side Program Theorem 6.3 The query functions (V p), for any fixed h E H, are non-decreasing with respect p 0. Therefore, the following function:
(PI.....PP .K)
1
Σ RE(K
QV (h.
(96)
K
a summation of K non-decreasing functions, where each function depends only on one of the P values. This function, c(p...... .P............. ), a quasi-concave function. Although quasi-concave functions are not generally concave, they do possess concave superlevel sets. Specifically, for each E R, the following sets are convex R.A
S, A (on....px) PK)
E
1 K
Σ RE[A]
Q (h, 21
(97)
As result, the original optimization problem in equation 15 can be decomposed into a sequence of convex optimization problems. Each sub-problem is essentially feasibility problem that checks whether the set S, is feasible for given E R. Given that the original objective function is bounded between 0 and 1, binary search can be employed to iteratively approximate the maximum attainable value of the objective within any desired error margin A > 0. This process is detailed in Algorithm 1, which implements bisection algorithm.
important to note that each feasibility check boob-prollm Algorithm I convex problem, and therefore can be solved in polynomial time with polynomial evaluations of the constraint functions, i.c., the QV₁ functionss Consequently. both the computational complexity and the required query budget remain polynomial. In particular, for a given > 0, the maximum the objective in equation 96 can be approximated with an error of at most A, requiring at most log iterations (feasibility checks) in Algorithm (Boyd, 2004).
29

---

Certifiably Robust Model Evaluation in Federated Learning under Meta- Meta-Distribuutinall Shifts
Proof of Remark 7.2. We turn to client-side optimizations for this theorem, which take the form:
sup (E
EQ [e (Z)),
where the notation & E h (X)) has been simplified to l (Z) (for Z = ()) for clarity and ease of notation. For a client k E [K], the local distribution P corresponds Ps. which is derived from ny samples drawn from an arbitrary distribution Pk- This optimization program is initially defined within restricted distributional space, B and may appear intractable at first glance. However, by leveraging Lemma E.1 (see Appendix E), which relies on a core mathematical tool from the seminal works of (Sinha et al., 2018) (originally derived in (Blanchet and Murthy, 2019)), this formulation can be rewritten in its dual form. This dual reformulation is subsequently shown to be implementable in polynomial time (Sinha et al., 2018). The rest of the proof of Remark 7.2 is the summary of the method proposed and subsequently used in the above mentined reference (not our work).
Let P be probability measure defined over a measurable space S2 {(.) : R be any loss function, denote proper and lower Wassersteinn-onstraiine DRO centered around P:
transportation cost on f2 x Ω2 and assume 0. Then, the following equality holds for the
sup e - (Z' .2. 21
sup QE By (P)
EgQ [e (Z) = inf 720
7p + Ep
(98)
The optimization over 7 is one-dimensional. On the other hand, the term EP (sup Z' E EI (Z) (Z', 2) is non- increasing for y 2 0, while the other term, np, is affine. In fact, 7/ and P are dual counterparts, where increasing p decreases the optimal y value and vice versa. Therefore, the outer minimization inf,20 can be handled in polynomial time as long as the inner expected maximization can be numerically solved efficiently (in polynomial time).
For the inner maximization, we have
Ep.
sup Z'ER
(ZZ) 70 (Z', 2)
1
Σ
sup ((Z)) - 70 Zi),
Z'ER
(E(ma]
(*) (x(x -3; - which follows from the fact that Pr. is an atomic empirical measure. We follow the same procedure
for Z, =
as in (Sinha al., 2018):
Assume E is twice differentiable with a founded-from-beet (but potentially negative) curvature, i.e., the Hessian matrix satisfies V t -3I for some bounded | 2 O.
Assume e is I-strongly convex in its first argument (same as Assumption A in Sinha et al. (2018)).
These assumptions are not overly restrictive, most candidates for the loss function e (-), such as cross-entree rross-entropy loss coupled with a deep neural network architecture for h, directly correspond to analytic and twice- diieediiferrentialle functions with bounded curvature from below. Note that we do not assume convexity for f, thus maintaining the generality of the problem. On the other hand, most choices for the transportation cost e are convex in their first argument (e.g., any valid norm).
Based on the above-mentionel two assumptions, straightforward to see that the term é (Z') ye (Z', Z.) is concave as long as y B (i.e.,& is not excessively large). According to standard convergence theorems in convex optimization theory (see, for example, Ghadimi and Lan (2013) or Boyd (2004)), any vanilla local first-order optimization algorithm with oracle access to gradients, such as stochastic gradient descent (SGD), can achieve an O (T 1/2) approximation of
Obj (Zi...,, Znzit) A
Σ iE(ne)
sup L 7c (Z), Zi),
Z'En
after T 2 iterations. This completes the proof.
Proof of Remark 7.4. As K, ming na - the bounds presented in Theorems 4.1, 5.2, 5.3, and 6.3 achieve minimax optimality, referred to as Asymptotic Minimax Optimality (AMO). Mathematically, this implies that the proposed empirical bounds on the right-hand sides become attainable by an adversary, rendering them unimprovable. This particular approach in demonstrating the tightness of such bounds is a standard practice in nearly all theoretical works within this field and related areas (see Sinha et al. (2018); Ashtiani et al. (2018); Saberi et al. (2023); etc.).
30

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distriiuutional Shifts
This theorem provides non-robust guarantees and thus there adversaries involved. Therefore, the proof for this part is straightforward since only need show the right-hand side of the inequalities equal the left-hand sides in the asymptotic regime. In this regard, we have
AMO for Theorem 4.1
k
K
lim
1 K
Q (h) = lim
lim t00
Σ 1=1
h (x!") (x(()))
K
+00
K-000
K
Tek
k=1
K
0.5.
lim
Ep, [e (y
k=
Epan (Er, [e (v, h (x))))
(99)
The first almost sure equality follows from the fact that that dataset { (x .u
consists of i.idd samples from Ps ) "
for each & E [K]. The second one is result of Pl...., Px being i..d. samples of μ. In both cases we have used the strong law of large numbers.
In a similar fashion, for the loss CDF and all subsequent values of À E R, the following almost sure equalities hold:
[K+1) log 6
K
log (K+1)
1
lim K.ncK
@Va(k) 2 A
lim
lim QV
K
2n1
K
100
21L
k=1
R=
log (K-1)
lim
lim @V+(h) + lim
2 1
K000
K
ne m20000
2nx
R=1
0.5. lim
1 (Er, ((),, 21
K
K
Ep-n [1 (Ep [e (y. (x)) A)
= μ (Ep ( (X)) 2 A).
(100)
Again, the almost sure equalities are the result of applying law of large numbers both distributional and meta-distributional levels. Therefore, the proof for this part is complete.
AMO for Theorems 5.2 and 5.3 Assume two arbitrary meta-distributions μ' and and only assume Dy [p)) S (note that for E < co, this assumption automatically enforces relative continuity as well), and let Pı, P2.... be an infinite i..d. sequence from j.. The only extra restriction over μ' is that it represents probability measure. Combining all these natural restrictions we get
Non-negativity of μ², which means for any S C (2) we have μ (S) 2 O.
Normalization condition of probability measures which mathematically translates into the following equalities:
1 (M(2)) = SPEN // (dP) = Eppp
(1' [d()
K dy
lim K00
(Px).
(dP))
K
K kml
du
Boundedness of f-divergence, which can be written as follows:
2 (1/1))) Epnn
f dp' du
(P))
0.
lim
Σn A=
dp'
(Ps)
K
du
In all the above statements, the almost sure equality holds with respect to the randomness of drawing the i.i.d. sequence of distributions P,, Pz.... from i and utilizes the application of the law of large numbers. Based on the above discussions, any measure defined on Borel o-fildd over M (Z) that satisfies the above conditions is a potential candidate for the worst-case yl in the statement of theorem.
31

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts
On the other hand, the proposed bound in the right-hand side of the main result in Theorem 5.2 is computed via the following optimization problem:
(e)
A
sup
ag QV (h)
(101)
K
K
subject to
Σ
ak
1
S c1 (og
K
k=1
K
1
f(ax)
S log (5-1)/K.
K
k=1
Since, for all d >> 0 we have
lim log (0-1)/K 0, and lim + c2V (6-1)/K =,, x0000
(102)
in the asymptotic regime of K + oo the vector (an...., ak) converges to the sequence (asliEN with the following properties:
K -a=1 and
0₁ 2 O, ViEN,
lim +00 K
lim K-+00
Σ f(a,) Se.
(103)
K
Therefore, it can be deduced that any fashee that satisfies such conditions corresponds an achievable density ratio, i.c ag = dp' /dp (Px), & E N. for some μ E M² (Z). In other words, the sup value is achievable. The same set of arguments hold for Theorem 5.3, and the proof for this part is complete.
AMO for Theorem 6.3 The proof relies heavily on the theory developed in the proof of Theorem 6.3 (see Section E), and we adopt the same procedure and notations. Recall the bound proposed in Theorem 6.3: For any e, 8 >> 0, consider the following constrained optimization problem:
K V (h,
Ü (E) A
sup
(104)
P 2 e/K
K
k=1
1
K
1 K
log (++2)
subject to
K
Pk
E
1
+ ta1
K
k=1
In the asymptotic regime (i.e., K, ming nr + oo), we have
lim QV pk) ny 400
sup QEB,,
Eq ( (X))),
(105)
where P1, Pa.... is an infinite (but countable) i.i.d. sequence from the meta-distribution μ.. The almost sure convergence follows from the law of large numbers. Define Mz 14.. In the asymptotic regime (K - oo), the constraint becomes:
Ep-p 10 (P)] a.s. lim
Pk
K oo
K
1
log $
S lim E
1
K400
K
K
=
(106)
Thus, the optimization problem defining 0+ when K, ny + oo (almost surely) reduces to:
Ú (s) a.S.
sup p:M
Ep-n sup QEB (Pt) le (e (x)))(
subject to Ep (P)) Se.
(107)
32

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributionall Shifts
Introducing a Lagrange multiplier 7 2 0, and using strong duality, this problem becomes:
inf 720
sup (:M
sup (EBxp))(P)
I (v, (o (Bp~a [p[P] (p())) -))
inf
sup (2.
EPnp sup (EB,AP)(P))
(v, -x -e) -
720
inf
7/ +
sup (M
E E
sup (P))
(u ~00
(108)
720
The combined effect of the two supremum operators (supp. and supQEB yields the following min-max problem:
Eq (x)) -
inf
yE
E Bp
sup QEMx
(109)
720
By Lemma 1.1, this is equal
sup Epop ( M'E (1))
(110)
Thus, the proposed bound Ü+ converges to the above expression as K, ming ny oc, which is exactly equal to the statistical quantity that was supposed to upper-bound. This completes the proof.
G. Complementary Experimental Results
In this section, we present a complementary series of experiments on real-world datasets to demonstrate: (i) the validity and tightness of our bounds, and (ii) that our bounds are not only theoretically sound but also practical to compute. For clarity and readability, we repeat key explanations from Section 8 to maintain a cohesive narrative.
G.1. Client Generation and Risk CDF Certificates for Unseen Clients
In the first part of our experiments, we outline our client generation model and present a number of risk CDF guarantees. We simulated a federated learning scenario with = 1000 nodes, where each node contains 1000 local samples. The experiments were conducted using four different datasets: CIFAR-10 (Krizhevsky al., 2009), SVHN (Netzer et al., 201 I), EMNIST (Cohen al., 2017), and ImageNet (Russakovsky et al., 2015). To create each user's data within the network, applied three types of affine distribution shifts across users:
Feature Distribution Shift: Each sample x in the dataset is manipulated via transformation chosen randomly for each node. Specifically, each user is assigned unique matrix (k) and shift vector ((k), and the data is modified as follows:
(+) = (I + A
+ (())
(111)
In our experiments, A (k) and (k) are respectively random matrices and vectors with i.i.d. zero-mean Gaussian entries. The standard deviation varies based on the dataset: 0.05 for CIFAR-10 10 and SVHN, 0.1 for EMNIST, and 0.01 for ImageNet.
Here, we assume that each meta-distrin meta-distribution is characterized by a specific a coefficient. To generate each user's data under this shift, the number of samples per class is determined by a Dirichlet distribution with parameter a. In our experiments, we use a 0.4.
Label Distribution Shift:
Feature Label Distribution Shift: As the name suggests, this shift combines both the feature and label distribution shifts described above create new distribution for each user.
Figure 4 illustrates our performance certificates (i.c., bounds on the risk CDF) for unseen clients when there are no shifts. We selected 100 nodes from the population and considered 400 other nodes as unseen clients. We then plotted the CDFs based on 100 samples and confirmed that our bounds hold for the real population as well. Due to the standard DKW inequality, the empirical CDF a good estimate for the test-time non-robust risk CDF.
33

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributtinaal Shifts
G.2. Certificates for f-Divergence Meta-Distributtonall Shifts
fefaturee
cifar10-
cifar O-feature&labbll
1.0
1.0
Curnclative Prabability
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
doy
0.2
del 0.2
del 0.2
0.2
adV
adv
adv
0.2
0.2
de 0.2
72
74
60
85
70
75
svhn-feature
svhn-label
svhn-feature&labbl
1.0
1.0
1.0
0.8-
0.8
0.8
0.6
0.6
Cumulativa
0.4
0.4
d 0.2
dal 0.2
des
0.2
adv
0.2
adv
adv
dy
Mata
Mata
emnist- feature
emnist-label
emaist-featured feature&label
1.0
1.0
1.0
Cumulative Probabiitty
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
dev 0.2
day 0.2
day - 0.2
adv
edv
0.2
adv
dy
du
Meta
Meta
Mata
86
85
95
Imagenet-fcature
imagenet-label
imagenettfoatureklia
1.0
1.0
1.0
Probahiltty
0.8
d,y
das
du =
0.2
0.2
Meta
Mata
Meta
0.0
56
58
G0
62
64
66
68
70
50
52
54
53
60
62
Accuracy
Accuracy
Accuracy
Figure 9. Extension of previous experiments to broader range of adversarial budgets for f-divergence attacks. DKW-based certificates for unseen clients in our four examined datasets, Meta refers to the main population with 1 1000 nodes.
In this section, we examined scenarios where users belong to two distinct neta-distribbution:: the source and the target. A ONNN-ased model is initially trained on network of clients sampled from the source. The resulting risk values are then fed into the optimization problems introduced in Section 5 to obtain robust CDF bounds, considering both the Chi-Square and KI. divergence as potential choices for f. Finally, we empirically estimate the risk CDF for users from the target
34

---

Certifiably Robust Model Evaluation in Federated Learning under Metta-Distributionall Shifts
cifar10-featur
cifarl O-label
cifar10-eettur<(label
1.0
1.0
1.0
Cumulative Probability
0.8
0.8
0.6
0.1
0.1
0.4
0.2
Wass;00
0.11
0.2
WasSsoo 0.1
0.2
Wasssoo = 0.11
Meta
Meta
Meta
55
60
70
75
80
40
60
80
svhn feature
Syhn-feature&label
1.0
Cumulative Probabiity
0.8
0.6
0.6
0.6
0.4
0.4
0.4
Wassspo
0.08
Was$s0o
0.07
Wassspo
0.08
Meta
Meta
Meta
0.0
0.0
0.0
75
80
85
90
75
80
85
90
95
70
75
80
85
90
emnist-feature
emnist-label
emnist-feature&label
1.0
Cumulative Probabiity
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
Wasssoo
0.03
0.2
Wasssco
0.04
Was5s0o
0.03
Meta
Meta
Meta
0.0
0.0
82
84
86
88
90
70
80
90
70
75
80
85
90
95
imagenet-feature
imagenet-label
llageeeeteestuur&elleell
1.0
1.0
Cumulative Probablity
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
WasS;0o
0.12
WasSspo 0.11
0.2
WasS30o
0.12
Meta
Meta
Meta
0.0
0.0
0.0
50
55
60
55
60
65
70
45
50
55
60
Accuracy
Accuracy
Accuracy
Figure 10. Wasserstein distance-based certificates for unseen clients in our four examined datasets. Meta refers to the main population with 1000 nodes. Dotted curves are based on 500 networks within the population.
meta-distri and validate our bounds. Specifically, tested certificates in distinct settings using the CIFAR-10 dataset (see Figure 5). We generated various image categories with differing resolutions or color schemes, and then sampled from these categories to create different distributions:
Resolutions: Images cropped and resized create eight different resolutions. The Dirichlet coefficients for the first (source) meta-distribution range from 0.4 to 0.7 for the four lower resolutions and from 0.7 to for the four higher resolutions, For the second (target) meta deta-distribution, the ranges are reversed: 0.7 to 1 for the lower resolutions and 0.4 to 0.7 for the higher resolutions. The number of samples per resolution for each user determined using Dirichlet distribution, with coefficients randomly selected from the specified range for the meta-distribution. As a result, users sampled from source will have more high-resolution images, while users from the target will have more low-resolution
35

---

Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributionaal Shifts
samples.
The color intensity of the images varies from 0.00 (gray-scale) to 1.00 (fully colored). For the source meta-distribution, the a coefficients range from O to 0.5 for images with color intensity below 0.5, and from 0.5 to 1 for images above 0.5. As with the resolution setting. the ranges are reversed for the target, and the number of samples per color intensity for each user calculated similarly. Therefore, users sampled from source will have more colorful images, while those from the target will have more gray-scale images.
Colors:
Figure 6 (left) verifies our CDF certificates based on both chi- chi-square and KL-divergence (dotted curves) for the target meta distribution (orange curve). As can be seen, bounds have tightly captured the behavior of risk CDF in the target network. More detailed experiments are shown in Figure 9 in Appendix G.
G.3. Certificates for Wasserstein-
Meta-Distributional Shifts
In this experiment, as previously mentioned, we used affine distribution shifts to create new domains. Figure (right) summarizes our numerical results in this scenario. To generate different networks within the meta-distribution, we applied the affine distribution shifts described in Section G.I. Once again, the results validate our certificates, this time for Wasserstein-type shifts. The blue curve, representing the real population, consistently falls within or beneath the blue shaded Regarding tightness, it is important note that the bounds presented here remain tight, particularly under adversarial attacks as defined by distributional adversary in (Sinha et al., 2018). More detailed experiments with various levels of tightness are shown in Figure 10 in Appendix G.
Although our theoretical findings in Section 6 focus solely on the average risk and not the risk CDF, we extended the same framework to the CDF this experiment to explore whether the theory might also apply. The results were positive, suggesting potential for extending our theoretical findings in this area. A more detailed series of simulation results are presented via Figures and 10, respectively.
Figure illustrates complementary results for f f-divergence bounds risk CDF, which are robust extensions of the DKW bound. Simulations have been repeated for several different values of e, where both KL. and x2 (Chi-Square) divergences have been considered.
Figure 10 shows the robust CDF bounds for Wasserstein shifts. Again, different values of for Wasserstein distance have been considered which have resulted in several bounds with various levels of tightness. should be noted that all bounds are asymptotically minimax optimal, meaning that an adversary can choose distribution to perform exactly as bad the bounds, least in the asymptotic regime where both K and ming ng tend infinity.
36


Reviews:
[{"review_id": "QevB2VrZLT", "reviewer": "Reviewer_nqsu", "summary": "The paper provides an analysis of model evaluation under tighter risk assessment conditions compared to previous works on federated evaluation. The main contribution includes a novel extension of the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality adapted for federated data distributions. The authors claim improved evaluation procedures leveraging the federated nature of data, emphasizing the impact of meta-distribution similarity on evaluation quality.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their insightful comments.  Here, we give point-to-point responses to each concern or question.\n\n---------------------------------\n\n**Main Comments**  \n\nThe reviewer’s main concerns are:  \ni) Justifications for our claim that previous methods either ignore the inherent robustness or wellness of the evaluated model or are suboptimal due to restrictive assumptions.  \nii) Missing explicit definitions of notations and assumptions.  \n\n**Regarding (i):**  \nWe have provided a detailed explanation in Section A of the Appendix due to page limitations. However, as requested, we can move it to the main body. In Section A, we categorize existing methods into two approaches:  \na) They collect all client samples on a central server, approximate the meta-distribution (e.g., via histograms), and design collective (meta-)distributional attacks to assess adversarial loss. This approach obviously violates privacy in federated learning (FL) and is impractical for real-world model evaluation, making it primarily useful only for research purposes (See Reisizadeh et al., 2020; Ma et al., 2024 for more details).\nb) They introduce a \"model-independent\" additive term, often using Maximum Mean Discrepancy (MMD) (e.g., in Sinha et al (2017), Pillutla et al. (2024), etc.), to inflate the loss. This approach is suboptimal because it disregards the model's inherent robustness. Consequently, the generalization gap does not vanish as the sample size increases, meaning a constant, non-vanishing term must always be added to the evaluation network's loss to certify robustness for the target network.\n\n**Regarding (ii):**  \nWe have included as many definitions as space allows, but we can reorganize them into a dedicated section for clarity, as suggested by the reviewer. Regarding assumptions, we make none beyond assuming that local distributions are independent samples from a meta-distribution. All other aspects are kept as general as possible. If the reviewer has specific assumptions in mind, please let us know.  \n\n------------------------------------\n\n**Questions**  \n\n1) Addressed above.  \n\n2) **\"How do your results specifically benefit from the federated nature of the data compared to centralized settings?\"**  \nOur bounds are computable solely using Query Value (QV) functions (defined in Section 3), meaning we do not require access to clients' private data or even their local sample sizes. In contrast, existing methods either compromise privacy (by accessing raw data) or suffer from non-vanishing assessment gaps.  \n\n2) (2, cont'd) **\"Does evaluation benefit from having more clients, even if each has limited data?\"**  \nYes! A larger number of clients $K$ provides more information about the underlying meta-distribution $\\mu$, even when their data remains private. Consequently, even if each client has limited data, (at least) parts of our bounds asymptotically improve as $K$ increases. This has been theoretically shown in our results in Theorems 4.1, 5.2, 5.3 and 6.3. We will emphasize this in the revised version.  \n\n3) **Illustrative Example:**  \nConsider a company planning to launch an app for a target customer base in New York. Before full deployment, they might conduct a pilot test in a smaller, controlled community (e.g., New Jersey) to evaluate user experience, infrastructure capabilities, etc. A key challenge is ensuring that insights from New Jersey generalize to New York, given possible differences in user lifestyles and preferences between the two cities. Our work addresses this by providing privately and efficiently computable bounds that extend beyond the evaluation network to unseen (but similar) target networks. How to choose $\\varepsilon$ in practice? This highly depends on the application. However, the main point is usually to see how fast the performance of $h$ \"degrades\" as $\\varepsilon$ grows, which is a sign of the sensitivity of the model. This does not need the exact knowledge of $\\varepsilon$ in practice.\n\n----------------------------\n\nWe welcome further discussion and, once again, appreciate your time and effort. If our responses have been satisfactory, we would greatly appreciate it if you increase your score.", "claims_and_evidence": "Most claims are supported by rigorous theoretical proofs and experimental validation. However, some claims about the inherent wellness or robustness of risk analysis compared to prior work need clearer justification. In particular, the paper does not adequately explain why previous methods ignored inherent robustness or whether their analysis was suboptimal due to different assumptions or scenarios.", "methods_and_evaluation_criteria": "The evaluation makes sense in the context that the main contribution of this work is theoretical.", "theoretical_claims": "I have reviewed the theoretical claims, and they appear to be correct.", "experimental_designs_or_analyses": "See Methods And Evaluation Criteria.", "relation_to_broader_scientific_literature": "The paper situates itself well within the broader context of federated learning and risk analysis, extending prior results with more refined statistical bounds. However, the authors could strengthen this section by explicitly contrasting their contributions against key previous works on robustness and risk evaluation in federated learning.", "essential_references_not_discussed": "I am not aware of any missing references, although, I am not very familiar with all the relevant literature.", "other_strengths_and_weaknesses": "The primary strength of the paper lies in its theoretical innovation and careful extension of known statistical bounds (DKW inequality) into federated learning contexts. However, the clarity of presentation suffers at points due to missing explicit definitions of notations and assumptions, making parts of the paper challenging to follow.", "other_comments_or_suggestions": "1. Improve the clarity by explicitly defining all notations and assumptions in a dedicated section.\n\n2. Enhance discussions around practical implications, especially regarding meta-distribution similarity handling.", "questions_for_authors": "1. Could you clarify precisely why previous methods did not sufficiently address inherent wellness or robustness of risk? Are there scenarios they overlooked, or did their approaches inherently limit their analysis?\n\n2. Can you explicitly demonstrate or discuss how your results benefit specifically from the federated nature of the data compared to centralized settings? In particular, does evaluation benefit from having more clients, although with limited data? \n\n3. Could you elaborate more on the practical implications and handling of meta-distribution similarity in real-world scenarios? How would practitioners estimate or manage this similarity effectively?", "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": "", "extra_scores": {}}, {"review_id": "GAjjQZnws2", "reviewer": "Reviewer_6ciV", "summary": "This paper introduces a robust optimization framework for evaluating machine learning models in federated settings with non-IID client data, where the data distributions are governed by an unknown meta-distribution. The goal is to assess model performance not only on a given client network (standard A/B testing) but also on unseen networks with similar distributions, measured using f-divergence or Wasserstein distance. The framework enables private server-side aggregation of local adversarial risks, ensuring robust global model evaluation with polynomial time and query complexity. Theoretical results establish minimax-optimal risk bounds with vanishing generalization gaps as the network size increases. Empirical evaluations confirm the framework’s effectiveness in real-world tasks.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their insightful comments. Below, we provide point-by-point responses to each concern.  \n\n-----------------------------\n\n**Questions**  \n\n1) **\"The theorems analyze bounds under different distributions. Can the authors please highlight the key challenges of this analysis in federated learning compared to non-federated learning?\"**  \nOur analysis evaluates model performance under different (meta-)distributional shifts. The key challenge in federated learning (FL) is that data is decentralized and private, unlike centralized settings where full data access is available. Our bounds are computable solely using Query Value (QV) functions (defined in Section 3), meaning we do not require access to clients' private data or even their local sample sizes. This makes our method particularly suited for federated model evaluation. In contrast, existing methods either compromise privacy (by accessing raw data) or suffer from non-vanishing assessment gaps. For further details, please refer to our response to Reviewer nqsu.  \n\n2) **\"It seems that an analysis of complexity to solve the proposed optimization problem, for both the global server and local clients, is missing.\"**  \nIn most parts of Section 7, and almost all of Appendix F (proofs), we have provided a thorough **computational complexity analysis** for both server-side and client-side optimizations. In particular, Remark 7.1 discusses server-side complexity, while Remark 7.2 covers client-side computational aspects. Below, we summarize the key results:  \n\n- **Server-side:**  \n  - The non-robust case in Theorem 4.1 only requires summing queried loss values, without any optimization.  \n  - The optimization problems in Theorems 5.2 and 5.3 are convex, featuring linear objectives with either linear or linearly separable convex constraints. Such problems are solvable in polynomial time with at least a linear convergence rate (see the proof of Remark 7.1 in Appendix F).  \n  - The optimization problem in Theorem 6.3 is quasi-convex. It is solved using the bisection algorithm in Algorithm 1 (Appendix F), which finds the global optimum in logarithmic time. Each step of this algorithm involves solving a convex program with at least a linear convergence rate (again, see the proof of Remark 7.1 in Appendix F). \n\n- **Client-side:**  \n  - Theorems 4.1, 5.2, and 5.3 require no client-side optimization; clients only compute their local non-robust loss.  \n  - Theorem 6.3 involves a local optimization at the client side to assess adversarial loss. This problem has been well studied (see proof in Remark 7.2, based on Sinha et al. (2017)), and under the given assumptions, it is convex with at least a linear convergence rate.  \n\n3) \"**The writing could be improved by more discussion of the motivation and intuition of the proposed optimization framework.**\": This issue has already been addressed in our response to Reviewer nqsu. Please refer to our response to Question 4 (illustrative example).  We make sure to highlight such examples in the revised version.\n\n**4) \"**The experiments can hardly demonstrate that the bounds are tight.**\":** Thank you for pointing this out. The bounds are indeed tight, but the figures required an additional detail to illustrate this more clearly. We have addressed this in our response to Reviewer SPhP, who raised a similar concern. Please refer to that discussion for further details. To clarify, the figures in the paper compare the source non-adversarial setting with one specific adversary (modifying image coloring and resolution), while the bounds hold for the **worst-case** scenario. To better demonstrate the claimed tightness, we have added an extra curve to the plots, representing **an achievable** adversarial example based on the source network. This addition makes the tightness more apparent. You can view the updated figures here:  \n[GitHub Link: https://github.com/annonymous-ICML2025/paper-3310](https://github.com/annonymous-ICML2025/paper-3310)  \nWe will also incorporate the necessary graphical details in the revised version of the paper.  \n\n------------------------\n\nWe welcome further discussion and, once again, appreciate your time and effort. If our responses have been satisfactory, we would greatly appreciate it if you reconsider your score.", "claims_and_evidence": "The motivation and intuition of the proposed methods are not adequately discussed.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No, I did not.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "Related to federated leanring.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength: \n\nAnalyzed the bound of generalization in evaluating models in federated learning. Different distribution shifts have been considered such as f-divergence and Wasserstein distributional shift. An optimization framework was developed to get a generalization bound for model evaluation in federated learning.\n\nWeakness: \n\n1. The theorems analyze bounds under different distributions. Can the authors please highlight the key challenges of these analysis in federated learning compared to non-federated learning?\n\n2. It seems that it lacks an analysis of complexity to solve the proposed optimization problem, for both the global server and local clients. \n\n3. The writing could be improved by more discussion of the motivation and intuition of the proposed optimization framework. \n\n4. The experiments can hardly demonstrate that the bounds are tight. It is questionable whether it could provide an effective evaluation in reality.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "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": "", "extra_scores": {}}, {"review_id": "MKfk66yEHv", "reviewer": "Reviewer_K26v", "summary": "The paper proposes algorithms to robustly estimate a model performance under a ball of f-divergence or Wasserstain distance, and provide the generalization bounds of the proposed methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their insightful and positive comments on our paper. Please let us know if you have any further questions or concerns—we would be happy to address them and clarify any points that might help you further increase your score.", "claims_and_evidence": "The paper claims the proposed methods can estimate model performance robustly, though it is mainly a theory work, the claim is supported by some experiments.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The main claims are the derived risk and CDF of the proposed estimators, showing their convergence rate to the true value as the number of clients and samples grows. I did not check proofs in the appendix.", "experimental_designs_or_analyses": "The experiments are using simulated data with datasets CIFAR-10, SVHN, EMNIST, and ImageNet. For each dataset a client-dependent transformation is applied to create heterogeneous data distribution. Then proposed methods are used to estimate CDF for model evaluation and it is compared with empirical CDF. The proposed methods can capture shape and trends of the true CDF.", "relation_to_broader_scientific_literature": "It tackles the problem of robustly estimating model performance in a federated environment where some clients may be out of the network during evaluation. It is a relevant setting in federated learning.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "", "extra_scores": {}}, {"review_id": "uXjhFKU2SN", "reviewer": "Reviewer_SPhP", "summary": "The paper tackles the problem of robust federated evaluation, in which a server aims to evaluate a model $h$ on the private federated data while taking into account the scenario in which the model could be used on a different distribution in deployment. The paper provides theoretical bounds to characterize the federated empirical evaluation of the model while using only a reasonable number of queries from the server to the clients. Two main Meta-Distributional Shifts were analyzed: f-divergence and Wasserstein distance shifts. Experimental results were provided to show the tightness of the provided bounds.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their careful analysis and insightful comments on our paper. Below, we provide point-by-point responses to each concern.  \n\n--------------------------\n\n**Claims and Evidence**  \n\n- **\"Remark 7.3 is not an actual certificate.\"**  \n  The reviewer is absolutely correct. We will remove the term \"certificate\" from Remark 7.3 and adopt a more precise phrasing. Our work does not focus on privacy analysis from a differential privacy (DP) perspective. Instead, Remark 7.3 simply states that, to the best of our knowledge, no known model inversion attack can reconstruct samples solely from a series of adversarial loss values computed at different radii.  \n\n----------\n\n**Methods and Evaluation Criteria**  \n\n- **\"The paper does not clarify how an imprecise solution to this optimization problem, with error $\\Delta$, can be used on the server side. In other words, it is assumed that the clients can compute $\\widehat{\\mathsf{QV}}(h,\\rho)$ precisely, which is not always possible.\"**  \n  Thank you for pointing this out. The reviewer is correct that an imprecise computation of $\\widehat{\\mathsf{QV}}(h,\\rho)$ introduces an additional error term. However, since the empirical bound in Theorem 6.3 is based on an average of QVs, an approximation error of at most $\\Delta$ per QV results in a total additional error of at most $\\Delta$. Thus, the generalization gap should include two components:  \n  i) The **statistical residual**, already formulated in Theorem 6.3.  \n  ii) An **algorithmic residual**, which can be arbitrarily reduced by (polynomially) increasing the computational effort.  \n  We will explicitly incorporate this detail into the revised version.  \n\n------------------\n\n**Experimental Design and Analyses**  and also **Questions**:\n\n- **\"How would you explain the gap between the CDFs in Figure 6?\"**\n\n  Thank you for bringing this to our attention. As the reviewer correctly noted, the gap depends on how \"tightness\" is interpreted. The current gap shown in the paper should not vanish because the difference between the CDFs of evaluation and target clients remains nonzero for any strictly positive $\\varepsilon$. However, by \"tightness,\" we specifically refer to the **generalization gap** approaching zero.  \n\n  In Figure 6, we currently show our bounds alongside the empirical CDF of loss over evaluation clients (without adversarial attacks) and compare them to one specific attack (modifying image coloring and resolution). However, our bounds hold for **the worst-case** scenario. To better illustrate this, we have added an extra curve representing **an achievable, but more general** adversarial performance. This curve aligns more closely with the theoretical bounds, making the tightness clearer.  \n\n  You can view the updated plots here:  \n  [GitHub Link: https://github.com/annonymous-ICML2025/paper-3310](https://github.com/annonymous-ICML2025/paper-3310)  \n\n  This will show that our bounds closely match these worst-case adversarial shifts, with any remaining gap diminishing as $K$ and $\\min_k n_k$ increase. We will update the plots accordingly in the revised version.  \n\n-------------------\n\nWe welcome further discussion and, once again, appreciate your time and effort.", "claims_and_evidence": "Most of the claims are backed with clear evidence, with the exception of the following :\n\n- In Remark 7.3, the authors claim as a certificate of privacy the absence of current attacks capable of recovering private data from the loss queries. This is not a certificate, contrary to information theoretical privacy certifications such as differential privacy.  For instance, for the computation in Equation 15, given that the number of queries from the server to the clients can be large, it is more than likely that the privacy of local data can be compromised.", "methods_and_evaluation_criteria": "The server solves constrained convex (or quasi-convex) optimization problems to compute the desired empirical quantities. For Wasserstein Meta-distributional shifts, the client is also required to solve a convex optimization problem. However, the paper does not clarify how an imprecise solution to this optimization problem, with error $\\Delta$, can be used on the server side. In other words, it is assumed that the clients can compute $\\widehat{QV_k}(h, \\rho_k)$ precisely, which is not always possible.", "theoretical_claims": "I did not check the correctness of the proofs.", "experimental_designs_or_analyses": "The authors provide experiments covering non-robust as well as the two Meta-Distributional Shifts. Settings not covered by the theory are also included. However, it is not clear what the authors mean by tightness in the interpretation of the results. Indeed, Figure 6, for instance, shows quite a large difference between the CDFs.", "relation_to_broader_scientific_literature": "The contributions of this paper seem novel and relevant to the emerging field of federated evaluation.", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "I included the key strengths and weaknesses in the previous paragraphs.", "other_comments_or_suggestions": "Small typo:\n- 297 (left) two meta-distributions µ, µ’ \n\nThe paper should also include an impact statement, as required by the ICML 2025 guidelines.", "questions_for_authors": "How would you explain the gap between the CDFs in Figure 6 ?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a robust optimization framework for evaluating machine learning models in federated settings where client data is non-IID and drawn from an unknown meta-distribution. Unlike standard evaluation approaches that consider only the current client network, the proposed method aims to generalize model evaluation to unseen but distributionally similar client networks. This is achieved through private server-side aggregation of local adversarial risks, incorporating f-divergence and Wasserstein distance measures for robustness. Theoretical contributions include asymptotically minimax-optimal bounds for risk and CDF estimation, with provable vanishing generalization gaps as the number of clients and sample sizes increase. The framework is designed to be computationally efficient and privacy-conscious, with empirical results showing its effectiveness across multiple real-world datasets.

Reviewers generally acknowledged the paper’s strong theoretical foundation, with particular appreciation for its novel application of the DKW inequality in the federated learning context and its careful treatment of meta-distributional shifts. Multiple reviewers highlighted the contribution’s relevance to federated evaluation and its potential to advance understanding of generalization under distributional shifts. However, some concerns were raised about the presentation and the lack of detailed intuition behind the proposed optimization framework. Several reviewers also noted missing complexity analysis especially given the number of server queries involved. Most of the reviewers' concerns are addressed by the authors' responses. However, some of the reviewers are still not convinced by the practicality of the derived bounds since the nature of the bounds are min-max and might be pessimistic in practice.
Decision: Accept (poster)