Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts

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.

Claims and Evidence

• "Remark 7.3 is not an actual certificate."
  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.

Methods and Evaluation Criteria

• "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."
  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:
  i) The statistical residual, already formulated in Theorem 6.3.
  ii) An algorithmic residual, which can be arbitrarily reduced by (polynomially) increasing the computational effort.
  We will explicitly incorporate this detail into the revised version.

Experimental Design and Analyses and also Questions:

• "How would you explain the gap between the CDFs in Figure 6?"

  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.

  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.

  You can view the updated plots here:
  GitHub Link: https://github.com/annonymous-ICML2025/paper-3310

  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.

We welcome further discussion and, once again, appreciate your time and effort.

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.

We sincerely thank the reviewer for their insightful comments. Below, we provide point-by-point responses to each concern.

Questions

1. "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?"
   Our 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.

2. "It seems that an analysis of complexity to solve the proposed optimization problem, for both the global server and local clients, is missing."
   In 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:

• Server-side:

  • The non-robust case in Theorem 4.1 only requires summing queried loss values, without any optimization.
  • 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).
  • 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).

• Client-side:

  • Theorems 4.1, 5.2, and 5.3 require no client-side optimization; clients only compute their local non-robust loss.
  • 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.

3. "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.

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:
GitHub Link: https://github.com/annonymous-ICML2025/paper-3310
We will also incorporate the necessary graphical details in the revised version of the paper.

We 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.

We sincerely thank the reviewer for their insightful comments. Here, we give point-to-point responses to each concern or question.

Main Comments

The reviewer’s main concerns are:
i) 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.
ii) Missing explicit definitions of notations and assumptions.

Regarding (i):
We 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:
a) 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). b) 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.

Regarding (ii):
We 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.

Questions

1. Addressed above.

2. "How do your results specifically benefit from the federated nature of the data compared to centralized settings?"
   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. In contrast, existing methods either compromise privacy (by accessing raw data) or suffer from non-vanishing assessment gaps.

3. (2, cont'd) "Does evaluation benefit from having more clients, even if each has limited data?"
   Yes! 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.

4. Illustrative Example:
   Consider 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.

We 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.