Robust Model Evaluation over Large-scale Federated Networks

We thank the reviewer for their time and thoughtful feedback. Below, we address each of the reviewer's comments in detail:

• “Important definitions and assumptions are deferred to the appendix.” Due to space limitations, we had to move some foundational definitions to the appendix to make room for more technical content. We will adjust this in the revised version. Please also refer to our response to Reviewer 9X7d.

• “I don’t know why B^hat is subject in the current form.” Consider the task of estimating the mean of a distribution from a sample set. Typically, one would use the sample (empirical) mean. However, the question here is: what would be the worst-case estimate of the mean if samples come from a different but nearby distribution, in terms of f-divergence? Intuitively, one could reweight the empirical mean by giving larger samples more weight, with weights constrained to remain close to 1. This illustrates the idea behind $\hat{B}$; we mathematically prove that this reweighted estimator is sufficient (achieving a vanishing generalization gap).

• “Why for f-divergence we use QVs with ρ=0?” This is one of our interesting findings. To achieve robust model evaluation under a bounded $f$-divergence shift in the meta-distribution, clients do not need to compute a private adversarial loss (hence, $\rho = 0$, implying the ordinary loss is sufficient). The adversarial aggregation occurs solely on the server side. In contrast, under the Wasserstein distance, clients must compute their adversarial losses according to optimal adversarial budgets, which the server determines. The server finds these optimal budgets in polynomial time, requests adversarial losses from clients, and then aggregates them.

• “The name of Definition 5.1 is ‘meta-distributional f-divergence Ball,’ but equation (4) additionally assumes a Λ-bounded density ratio.” When working with $f$-divergences, assuming bounded density ratios can simplify the analysis. While this assumption can be removed, doing so would introduce additional technical complexity. Furthermore, the bounds become dependent on the choice of the function $f$. For example, without the $\Lambda$-bounded assumption, the bound for the particular case of KL-divergence changes from $\Lambda \cdot K^{-1/2}$ to $\sqrt{\log K / K}$. However, it may slightly change for example if we use chi-square function. We will add references to similar assumptions used in prior work to improve clarity.

• “What exactly are $c_1$ and $c_2$ in Eq (5) since we need to approximate $B^{\hat{}}$?” Constants $c_1$ and $c_2$ result from multiple applications of McDiarmid's inequality and the union bound. Using basic mathematics, both can be shown to be bounded by 32. However, in practice, smaller values (approximately 2) suffice to keep the bounds tight across our experiments. Thus, finding the optimal values for $c_1$ and $c_2$ is left as future work. We will add explanations regarding this in the revised version.

• “For f-divergence, distributions sharing the same support should be explicitly listed as an assumption.” In Definition A.1, we state that $\mu'$ must be absolutely continuous with respect to $\mu$, which basically means the same thing is reviewer suggested.

• “It does not specify how fast $\min n_k$ grows. If $\log K$ outgrows $\min n_k$, then the term does not decrease.” We have already emphasized in line 356 that $(\min n_k) / \log K$ needs to grow. We will also clarify other statements that may be ambiguous on this point.

We would like to thank the reviewer for their careful review and thoughtful feedback. Below, we provide point-by-point responses to each of the reviewer’s concerns:

• “Literature review and comparison with other theoretical works is not enough.”
  In the revised version, we will address this issue. In our initial submission, we had to shorten the introductory sections to accommodate the technical results. In the revision, we will move some of these technical details to the appendix, allowing us to expand the literature review and provide additional explanations and clarifications in the earlier sections.

• “What is the main benefit of knowing $n_k$ for the server?”
  It is not essential for computing the empirical bounds. The values of $n_k$ are only needed if one aims to bound the generalization gap. We can therefore remove the necessity of knowing $n_k$ from our requirements. Thank you for this suggestion!

• “What is the value of the query budget considered for this case in your experiments?”
  In our experiments, we implemented a simple heuristic search algorithm to find robustness radii (specifically, their dual counterparts, the $\gamma$ values) rather than theoretically-guaranteed oracle-based optimization methods. We did not elaborate further on this approach, as we observed that the bounds became tight quickly even with this heuristic search. We will add more detail about this in the revised version.

• “What exactly is the difference between Fig. 1 and Fig. 5?”
  In Fig. 1, we present results for the CIFAR and ImageNet datasets, while Fig. 5 includes additional results from the SVHN and EMNIST datasets. Displaying all four datasets together makes the results more comparable. Both figures correspond to $f$-divergences with different choices of the function $f$ and various values of $\epsilon$, which represents our adversarial budget.

• We also appreciate the reviewer pointing out typographical errors, which we will correct in the revised version.

We hope these responses address the reviewer’s concerns and would be grateful if they could raise their score.

We thank the reviewer for their time and thoughtful feedback. Below, we address each of the reviewer's comments in detail:

1. "The assumption is that the data distribution for the unseen clients is close in f-divergence or Wasserstein distance.": We believe there may be a misunderstanding here. We do not assume that client distributions are close in any sense; indeed, two clients may have very distant data distributions (in f-divergence or Wasserstein distance). In this respect, our setting aligns with that of Scaffold [1], as the reviewer mentions. In our work, we assume that distributions for the source network are sampled from a meta-distribution $\mu$, while those for the target network come from a different meta-distribution $\mu'$. We assume $\mu$ and $\mu'$ are close, but do not impose any closeness between individual distributions sampled from either of them. Otherwise, providing guarantees on the target network based only on source observations is mathematically infeasible. We will add further clarification to the revised version.

2. "The client needs to return a query value with complicated forms; is it feasible to compute? It is a supremum of expectations.": Yes, fortunately, DRO problems of this type are theoretically and practically solvable in polynomial time. The seminal work of Sinha et al. (2017) demonstrates that, in the empirical regime, such problems have a dual form that is concave and solvable in polynomial time. Their work has been extensively used in various robust optimization applications since then. We will emphasize this result more explicitly in the revised version.

3. "It is hard to parse the experiment results. There is no comparison with other methods.": We have two responses: (i) Our CDF bounds are novel, and to the best of our knowledge, there are no previous works providing bounds on the loss CDF. On the other hand, our average loss bounds are already shown to be tight, so we did not include a comparison in that regard. The experiments aim to demonstrate the tightness of our bounds rather than improvements over existing methods. (ii) Our work is mostly theoretical, and our primary goal in the experimental section is to assure readers of the soundness and computability of our bounds.

4. "Is the goal to show the correctness of Theorem 5.5 and Theorem 6.2? But these are asymptotic bounds.": All our theorems, except for Corollary A.4, are non-asymptotic, meaning they hold for all values of $K$ and $n_k$.

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 a data distribution that is close enough to those clients, then we can have some bounds on the model risk on this client.": As mentioned above, we do not assume a single target user with a distribution close to the source distributions; rather, the closeness applies at the level of meta-distributions, not individual user distributions. Federated model evaluation, much like federated model training, is an active research area focused on providing average or tail bounds on model performance using loss values from a limited number of clients without directly accessing their data.

    Attaining the "robust" loss or CDF tail typically requires centralizing heterogeneous datasets on a server to perturb empirical data and estimate adversarial loss, which can compromise privacy. In contrast, our approach shows that robust average loss/loss CDF values can be attained without pooling datasets. Each user can perform a private adversarial risk assessment (based on an adversarial budget set by the server), and the server can then combine these results in a privacy-preserving manner.

    Additionally, the server’s interactions with clients follow policies governed by QV (query value) functions. For shifts in $f$-divergence, the server aggregates the values of QV in an adversarial manner. In the case of Wasserstein distance, the server identifies the optimal adversarial budget for each client in polynomial time, then aggregates the results accordingly.

• "The paper also mentions 'large-scale' in the title. Is it indeed relevant? The evaluation algorithm does not seem to depend on model structure.": The reviewer is correct; in this context, "large-scale" refers to the fact that generalization gaps in our non-asymptotic bounds diminish as network size increases. For a given maximum tolerable generalization gap, the minimum network size can be explicitly determined.

• "Text in Figure 3 is too small to read.": We apologize for this issue. In the revised version, this figure will be presented in full-scale in the Appendix section.

We hope that these responses address the reviewer's concerns and respectfully request that they consider revisiting their score. We believe the current score does not fully reflect the contributions and effort in our work.

We thank the reviewer for their time and thoughtful feedback. Below, we address each of the reviewer's concerns in detail.

1. "The paper studies federated learning under IID distribution": We believe there may be a misunderstanding regarding our data generation setting. Our work explicitly considers a non-IID scenario, where different clients have distinct data distributions. We make no assumptions about the nature or similarity of these distributions. In the federated learning (FL) literature, "non-IID" refers to cases where client distributions differ (as in our setting), not to cases where samples within each client are dependent or from varied distributions.

   Our only assumption is that samples within each client are drawn i.i.d. from its specific distribution (a standard assumption in non-IID FL), and that clients are sampled from a broader meta-distribution. Notably, without this meta-distribution assumption, providing any theoretical guarantees for the target network becomes mathematically infeasible.

2. "The presentation of the paper can be improved": We will improve the presentation to enhance clarity.

3. "The third part of the related work is confusing. The study of the paper is on IID data...": As noted, our study addresses a non-IID setting in which clients possess distinct (and potentially distant) distributions. This issue has been clarified above in response to the first comment.

4. "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.": This result is consistent with robust optimization theory when carefully developed. The generalization gap vanishes as sample or network size grows because the empirical part is adversarially computed, inflating its value. Increasing $\epsilon$ affects the empirical part, not the generalization gap, and this characteristic is highly advantageous for models/distribution pairs with inherent robustness.

5. "The authors claim that $\hat{B}^{*}(\epsilon)$ is asymptotically minimax optimal. But there are no proofs": Our claim is that the bounds are "asymptotically" minimax optimal, meaning they become optimal as $K$ and $\min_k n_k$ approach infinity. The proof, while straightforward, was omitted for brevity: By the strong law of large numbers, our empirical bound converges (almost surely) to the worst-case adversarial loss/CDF computed based on a meta-distribution deviating at most $\epsilon$ from $\mu$. We will add supporting theorems to clarify this claim.

6. "The authors present extensive experimental results, yet they do not provide codes to reproduce them.": The reviewer is correct, and we apologize for the oversight. We will include code for reproducibility in the supplemental material. However, please note that our paper is predominantly theoretical, with experiments intended to demonstrate the practical computability of our bounds.

Questions: We believe these questions are answered within the responses above.

We hope the reviewer finds our responses satisfactory and would appreciate it if they could reconsider their score.