Robust Model Evaluation over Large-scale Federated Networks
Distributionally Robust Optimization (DRO);Generalization Bound;Federated Model Evaluation;Glivenko-Cantelli Theorem and DKW Bound
Yes
NA
No ethics review needed.
* 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?
* 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.
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.
* 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.
Yes
No ethics review needed.
- 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.
The proof involves multiple advanced results in robust estimation and looks solid.
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.
- 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.
Yes
No ethics review needed.
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
* 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.
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.
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.
Yes
No ethics review needed.
See above
- Having certificates of model’s performance can be important in practice.
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.
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.
@inproceedings{
anonymous2024robust,
title={Robust Model Evaluation over Large-scale Federated Networks},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=eOE2g28eX9},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Distributionally Robust Optimization (DRO) Generalization Bound Federated Model Evaluation Glivenko-Cantelli Theorem and DKW Bound
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/80da84be78c8c197e40b589a9a26b9eaadbc54c6.pdf
learning theory
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Robust Model Evaluation over Large-scale Federated Networks
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission