Robust Model Evaluation over Large-scale Federated Networks

Authors: Amir Najafi, Samin Mahdizadeh Sani, Farzan Farnia
Primary area: learning theory
Keywords: Distributionally Robust Optimization (DRO), Generalization Bound, Federated Model Evaluation, Glivenko-Cantelli Theorem and DKW Bound

Abstract:
In this paper, we address the challenge of certifying the performance of a machine learning model on an unseen target network. We consider a source network “A” of $K$ clients, each with private data from unique and heterogeneous distributions, assumed to be independent samples from a broader meta-distribution $ \mu $. Our goal is to provide certified guarantees for the model’s performance on a different, unseen target network “B,” governed by another meta-distribution $ \mu' $, assuming the deviation between $\mu$ and $\mu'$ is bounded by either the {\it Wasserstein} distance or an $f$-{\it divergence}. We derive theoretical guarantees for the model’s empirical average loss and provide uniform bounds on the risk CDF, where the latter correspond to novel and adversarially robust versions of the Glivenko-Cantelli theorem and the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality. Our bounds are computable in polynomial time with a polynomial number of queries to the $K$ clients, preserving client privacy by querying only the model’s (potentially adversarial) loss on private data. We also establish non-asymptotic generalization bounds that consistently converge to zero as both $K$ and the minimum client sample size grow. Extensive empirical evaluations validate the robustness and practicality of our bounds across real-world tasks.

Decision: reject
Reviewer scores: 5, 5, 6, 3

Reviews and discussion:
<thread>
creation date:
1730033409733

thread_type:
official_review

<thread_object>
creator: reviewer_odr9

<content>
summary:
This paper considers the problem of certifying a model’s performance over a federated clients drawn from an unseen meta distribution that is close to a set of federated clients drawn from a seen meta distribution. 
The theoretical results for certification are given for Wasserstein distance and f-divergence respectively with the help of Glivenko-Cantelli theorem and the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality. Such certification can be computed within polynomial time.

strengths:
- Having certificates of model’s performance can be important in practice.

weaknesses:
The paper is presented in a way which is very difficult to understand:

- Important definitions and assumptions are deferred to the appendix.
- Theoretical results are given without much explanation. I don’t know why B^hat is subject in the current form and it is hard to tell if the theorems in the paper makes sense or not.
- Why for f-divergence we use QVs with rho=0?
- The name of Definition 5.1 is “meta-distributional f-divergence Ball”,  but the equation (4) additionally assume the Lambda-bounded density ratio which means you don’t actually prove for the entire f-divergence ball. Despite the descriptions above the definition talks about what does Lambda-bounded density ratio do, it is not clear to me is this really necessary or is it just another assumption that makes your proof easier?
- The “Lambda-bounded density ratio” assumption is listed in the appendix without any references. Is this new or already exists in the literature. You need to either cite previous works or justify this assumption is realistic.
- What exactly are c_1 and c_2 in Eq (5) since we need to approximate B^\hat?
- For f-divergence, distributions sharing same support should be explicitly listed as an assumption.
- It is claimed that the term in line 220 decreases with increasing K and \min n_k. However, it does not specify how fast \min n_k grows. If \log K outgrows  \min n_k then the term does not decrease.
- Line 235 “Additionally, any inherent “wellness” or “robustness” of the target model h is directly reflected through a low value for Bb∗(ε)” There is no guarantee that B(\epsilon) and QK is small.
- Certificate of Privacy: I doubt the significance of the claims here. Data recovery attacks are targeting the training where gradients are exchanged in each iteration whereas the task here is to estimate the loss here. Not really fair comparison.

Therefore I don’t think this paper in the current form is ready for publication.

questions:
See above
</content>
</thread_object>

</thread>
<thread>
creation date:
1730584493153

thread_type:
official_review

<thread_object>
creator: reviewer_9x7d

<content>
summary:
This paper provides certified guarantees for the performance of a model, which is trained on a federated learning network, on an unseen network/clients. The data distribution of the clients in the unseen network follow a meta distribution with bounded deviation from the meta distribution of the training network. The deviation is measured in terms of f-divergence and Wasserstein distance. The upper bounds provided for the performance of the model are in terms of empirical average loss (for both the deviation measures above) and CDF of the loss (for f-divergence only). As the main contribution of the work, the generalization gap in the derived bounds vanishes as number of clients and their dataset sizes grow.

strengths:
* Despite being a theoretical paper, it is well-written and it is easy to read.
* The work is theoretically rigorous with helpful and easy-to-read explanations about each part.
* The experimental results clearly support the theoretical derivations in the work.

weaknesses:
There are some weaknesses about the work:
* The existing results in the literature that are closely related to this work are not discussed enough. 

* The authors claim (line 227) that the main advantage of their work is that the generalization gaps in their derived bounds do not have a non-vanishing term, unlike many existing bounds. However, they have not compared their results with at least the best result that exists in the literature. This could be discussed in a separate paragraph after each of the Theorems 5.2, 5.5 and 6.2 (or even deferred to the appendix). Such a discussion would provide a more clear and convincing view of the main contribution and novelty of this work. This could be extended to the experimental results too. 

* There are some experimental results that could improve the draft. I have asked about them in the following questions.

questions:
Other than the weaknesses mentioned above, which are recommended to be addressed, I have some questions as follows:

* In all the three main theorems, the clients are queried by the server about their "expected" non-robust or robust risk values. What is the main benefit of knowing $n_k$ for the server? From the theorems, we see that $n_k$ appears in either the server's queries (in theorem 5.5) or in the generalization gaps (in theorems 5.2 and 6.2) (and not both). Can we eliminate the $n_k$ from the server's queries and replace them with a lower bound for them? This way, the server would just need a lower bound to do its queries without even knowing the clients' dataset sizes, hence providing some extra privacy. Remember that in some FL settings, the aggregation weights for clients are not based on their dataset sizes, but based on their empirical average risk, e.g., in some FL algorithms addressing performance fairness [1]. In such algorithms, the server does not know the clients' dataset sizes.

[1] Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. In International Conference on Learning Representations, 2020.


*  Unlike in theorems 5.2 and 5.5, where the query budget is one for each client, in theorem 6.2, the server queries clients about their robust risk values with "polynomially many" values of $\rho$ (robustness radii). What is the value of query budget considered for this case in your experiments? (e.g., in Fig. 3 right). Also, I am wondering how this would affect the bound computed in your experiments? An ablation study on the query budget, when ranging from 1 (similar to theorems 5.2 and 5.5) to larger values would reveal its behaviour when the "computational complexity/communication budget" changes.


* What exactly is the difference between Fig. 1 and Fig. 5? From what I see they are the same. How exactly the "adversarial budget" changes between the two? 


Minor comments:
* line 063: "both" should be dropped?
* line 093: there are two "the"s
</content>
</thread_object>

</thread>
<thread>
creation date:
1730627265899

thread_type:
official_review

<thread_object>
creator: reviewer_vduy

<content>
summary:
This paper studies the problem of model evaluation on unseen clients. The assumption is that each client is associated with a data distribution, and these distributions are from a meta distribution. The evaluation goes as follows: the server requests the client to evaluate a model on its private dataset, and the client returns an adversarial risk. The goal is to provide an upper bound for the risk of the model. Theoretical bounds are provided with assumption that the unseen clients have close data distribution, characterized by f-divergence or Wasserstein distance. Experiments are conducted to support the theoretical claims.

strengths:
The proof involves multiple advanced results in robust estimation and looks solid.

weaknesses:
- It seems that this paper is purely theoretical and it is not clear if the work has real-world applications. For instance, the assumption is that the data distribution for the unseen clients is close in f-divergence or Wasserstein distance. What does this mean for heterogeneous data distribution? Does this assumption work with non-IID data distribution generation in previous research like [1]? Also, the client needs to return a query value with complicated forms; is it feasible to compute? It is a supremum of expectations. 

- It is hard to parse the experiment results. There is no comparison with other methods, making it difficult to evaluate the novelty of this work. Multiple CDF curves are provided, but it is not clear the meaning of the curves. Is the goal to show the correctness of Theorem 5.5 and Theorem 6.2? But these are asymptotic bounds, and it is not clear to me why you can use experiments to show the correctness.


[1] Karimireddy, Sai Praneeth, et al. "Scaffold: Stochastic controlled averaging for federated learning." International conference on machine learning. PMLR, 2020.

questions:
- Why is this work related to Federated learning? As far as I can see, the main result is saying if we evaluate a model on some clients, and another client has data distribution that is close enough to those clients, then we can have some bounds on the model risk on this client. The model itself can be arbitrary and does not need to be trained with some FL algorithm. Can the authors elaborate a bit more on the connection with federated learning? 
- The paper also mentions "large-scale" in the title. Is it indeed relevant? The evaluation algorithm does not seem to depend on model structure or can be accelerated for large neural networks.
- Text in Figure 3 is too small to read.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730695323513

thread_type:
official_review

<thread_object>
creator: reviewer_w4np

<content>
summary:
This paper studies the generalization capabilities of federated models against unseen clients. Specifically, they aim to provide certified guarantees for the model's performance on a different and unseen target network. Theoretical analysis reveals the importance of the obtained results, where the deviation between different networks is bounded by $f$-divergence or Wasserstein distance.

strengths:
* The topic is important for the real-world deployment of federated learning models.
* The idea is intuitive and enjoys strong guarantees.
* Extensive experiments have been provided.

weaknesses:
* The paper studies federated learning under IID distribution, while the current real-world application leans more toward non-IID clients. In the Introduction, the authors have used many examples to motivate the generalization capabilities of federated learning, which fundamentally stems from non-IID data.
* The presentation of the paper can be improved. For example, the contributions can be listed as bullet points in the Introduction.
* The third part of the related work is confusing. The study of the paper is on IID data, as illustrated in Section 4. Yet, the authors discuss intensively federated learning algorithms under non-IID data. Moreover, the discussion mingles personalized federated learning with non-personalized ones without distinctions. 
* Theorem 5.2 is a strong guarantee in the sense that the generalization gap does not produce a non-vanishing term related to $\epsilon$. However, the authors fail to reason the root cause behind it.
* The authors claim that $\hat{B}^{*}(\epsilon)$ is asymptotically minimax optimal. Yet, Theorem 5.2 is a one-sided bound. To claim it is asymptotically optimal, both lower and upper bounds have to be provided. The same concern goes to Theorem 6.2.
* The authors present extensive experiment results, yet, they do not provide codes to reproduce them.

questions:
* Is it possible to extend the results to non-IID setups? What would be the potential obstacles?
* Can the authors discuss why no non-vanishing term related to $\epsilon$ appears in Theorem 5.2? In addition, what conventional bounds are the authors referring to?
* Can the authors elaborate more on the minimax optimal bounds?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731766181107

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response and Some Major Clarifications

comment:
Dear reviewers,
Thank you for taking the time to review our work.

We believe there may have been some misunderstandings regarding our paper, particularly in the reviews provided by Reviewers w4NP and Vduy. To clarify, we would like to restate the key aspects of our data generation process:

- We have considered a **non-IID** setting where each client in the network possesses a unique and distinct data distribution.
These distributions can vary significantly between clients, and we have not made any assumptions about their similarity or closeness.

- **Within** each client, data samples are i.i.d. with respect to their corresponding data distribution. This is a standard assumption in almost all non-IID federated learning methods.

- Our "only" assumption is that individual client distributions can be treated as independent samples drawn from a broader meta-distribution (a distribution over distributions). Importantly, this does not imply that all clients share the same internal data distribution or that their distributions are close, in any shape or form. Furthermore, we have made no specific assumptions about the characteristics of this meta-distribution.

- $\varepsilon$-proximity in our work applies at the level of meta-distributions which correspond to two different networks, and not the individual data distributions which underlie user samples. For example, consider the city of New York as a meta-distribution and its diverse and various citizens as data distributions which generate data samples (e.g. images) in their cell-phones by taking pictures. Hong Kong can be considered as a different meta-distribution, where its residents can have slightly different habits in taking images or selfies. Therefore, the two meta-distributions are shifted w.r.t. each other. We want to provide performance guarantees on the average and CDF of users in Hong Kong, via only having access to users from New York.

We have also provided detailed, point-by-point responses to each of your comments and concerns.

Thank you in advance for your consideration.
</content>
</thread_object>

</thread>


Metareview:
metareview:
a) Summary

This paper develops theoretical guarantees for evaluating machine learning models on unseen federated networks where client data distributions are heterogeneous and sampled from distinct meta-distributions. It derives robust bounds on the empirical average loss and loss CDF using Wasserstein distance and f-divergence, demonstrating that generalization gaps vanish as the network size and client sample sizes increase. The findings are validated empirically, showcasing the bounds' tightness and practicality, though real-world applicability and comparisons to existing methods are underexplored.

b) Strengths

- Theoretical Contributions: the idea of protecting privacy by adversarially perturbing losses is novel and interesting. So are the adversarially robust extensions of the Glivenko-Cantelli theorem and DKW inequality under meta-distribution shifts. These bounds are proven to be tight, minimax optimal, and non-asymptotic, ensuring vanishing generalization gaps with increasing clients and sample sizes.

- Extensive experimental validation: Extensive experiments are included, though they are primarily illustrative of the theoretical results

c) Weakenesses

- Practical Relevance: The biggest weakness is about the real-world applicability of the theoretical results, particularly under non-IID data setups, as were raised (Vduy, w4NP). Assumptions such as bounded density ratios and the use of f-divergence are perceived as either unclear or overly restrictive.

- Presentation: Some reviewers found the paper challenging to follow, with critical definitions and assumptions deferred to the appendix (oDR9) and difference between meta-distributions and individual client distributions confusing.

- Lack of comparisons and baselines: The paper does not compare its bounds directly with existing works.

d) Reason for **rejection**

The paper presents strong theoretical contributions, including novel bounds for federated model evaluation under meta-distributional shifts, but its real-world applicability is unclear due to restrictive assumptions. Key issues include poor presentation of definitions and assumptions, lack of experimental comparisons to existing methods, and mixed reviewer feedback indicating concerns about clarity and maturity. While promising, the work is not yet ready for publication.