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

Amir Najafi, Samin Mahdizadeh Sani, Farzan Farnia

TL;DR

This paper introduces a framework to provide guaranteed performance bounds for Federated Learning (FL) models when deployed on new, unseen networks of clients. By extending the classic Dvoretzky–Kiefer–Wolfowitz (DKW) inequality to handle "meta-distributional shifts," the authors enable servers to certify a model's worst-case average loss and risk profile without ever accessing private client data.

What Problem Does This Paper Address?

In Federated Learning, a model is trained across a "source network" of clients, each with their own unique, private data distribution. A major headache arises during evaluation: how do we know if this model will actually work when deployed to a completely different "target network" of clients?

Standard evaluation usually just averages performance across the existing clients. However, real-world deployment often involves meta-distributional shifts—for example, an app tested on users in Hong Kong might face different data patterns when released to users in New York.

Illustration of meta-distributional shift between a source network and a target network.

The challenge is twofold:

  1. Heterogeneity: Client data is non-IID (not identically distributed), making simple averaging unreliable.
  2. Privacy: The server cannot peek at the new clients' data to see how well the model is doing; it can only request high-level measurements like local loss values.

Methods

The authors model the problem using meta-distributions ($\mu$), which are essentially "distributions of distributions." Each client's local data distribution is treated as a sample from this broader meta-distribution.

The core technical contribution is the development of Robust Evaluation Guarantees using two main approaches:

  • Robust DKW Inequality: The researchers extended the classic Dvoretzky–Kiefer–Wolfowitz inequality—a tool used to bound the gap between empirical and true cumulative distribution functions (CDFs)—to an adversarial setting. This allows them to certify the "Risk CDF" (the percentage of clients likely to experience a loss above a certain threshold) even if the target meta-distribution $\mu'$ is slightly different from the source $\mu$.
  • Divergence-Based Uncertainty: They consider two types of shifts between the source and target networks:
  • $f$-divergences (e.g., KL-divergence): Captures scenarios where existing client types are reweighted.
  • Wasserstein Distance: Captures more extreme scenarios where entirely new "types" of clients appear in the target network.
Empirical clients sampled from a population and the resulting certified upper bound for the Risk CDF.

The server computes these certificates by solving convex or quasi-convex optimization problems. Crucially, this only requires querying clients for their local loss values (or "adversarial" local losses), preserving data privacy.

Datasets

The authors evaluated their bounds using four standard image classification datasets, modified to simulate federated environments with distribution shifts:

  • CIFAR-10
  • SVHN (Street View House Numbers)
  • EMNIST (Extended MNIST)
  • ImageNet

To create the "meta-shifts," they applied three types of transformations:

  1. Feature Distribution Shifts: Random affine transformations (rotations, shifts) applied to images.
  2. Label Distribution Shifts: Using a Dirichlet distribution to vary the class proportions across different clients.
  3. Resolution/Color Shifts: Specifically for the $f$-divergence tests, they created networks with varying image resolutions and color intensities.

Key Insights and Ideas

  • Uniformity is Key: Unlike standard bounds that might only work for a specific loss value, these bounds are uniform. This means the certificate holds for the entire risk profile (the whole CDF) simultaneously, which is vital for understanding the "tail risk"—the chance that a small group of users will have a terrible experience.
  • Vanishing Generalization Gaps: A common problem with robust certificates is that they can be "loose" or overly conservative. The authors prove that their bounds are asymptotically minimax optimal, meaning the gap between the certificate and the true performance shrinks to zero as the number of clients ($K$) and samples per client ($n_k$) increase.
  • Privacy-First Certification: The framework fits perfectly into the FL paradigm. The server doesn't need raw data, gradients, or model weights from the target clients—just a single scalar value (the loss) per query.

Key Results

  • Tightness: Empirical results on CIFAR-10 and ImageNet show that the certified upper bounds tightly hug the actual performance of the target networks, even under significant distribution shifts.
  • Convergence: The theory holds up—as the number of clients in the source network increases, the certificates become significantly more precise.
  • Efficiency: The certificates are computable in polynomial time. For $f$-divergence shifts, the server can compute the robust bound entirely on its own after receiving standard loss values from clients.

Limitations and Future Work

  • Wasserstein CDFs: While the paper provides a robust CDF bound for $f$-divergence shifts, the Wasserstein section currently focuses on the average risk. The authors note that certifying the full Risk CDF under Wasserstein shifts is mathematically more complex and is deferred to future work.
  • Known Shift Budget: The bounds require the user to specify $\epsilon$ (the maximum allowed shift between networks). In practice, estimating this "budget" for a new network remains a challenge.
  • Computational Overhead: While polynomial, the Wasserstein-based certification requires clients to solve a local optimization problem (finding their own worst-case loss), which is more computationally intensive than a simple loss check.

Summary updated

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
BibTeX
@inproceedings{najafi2025certifiably,
  author = {Amir Najafi and Samin Mahdizadeh Sani and Farzan Farnia},
  title = {{Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=dKfq3JbjnE},
}
Figure