🤖 machine learning

Federated and differentially private estimation of KL divergence

This paper introduces FedPriKL, a novel differentially private method for estimating KL divergence in federated settings that achieves unbiased, low-variance accuracy with bounded sensitivity while minimizing communication overhead compared to existing baselines.

Original authors: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

Published 2026-08-24

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern world of data, information is often scattered across millions of individual devices, from smartphones to wearable health trackers. This scattered nature creates a powerful way to learn about the world without ever gathering everyone's data into one central vault. This approach, known as federated learning, allows a central system to build models by asking devices to perform calculations on their own local data and then sharing only the results. However, a critical challenge remains: how do we know if the data being used is changing over time? If the behavior of the people using an app shifts, the models built on old data may become inaccurate or irrelevant. To fix this, analysts need to measure the difference between the current data and a known standard, a task that usually requires seeing the raw data. But in a world where privacy is paramount, revealing the raw data is often impossible. The solution requires a way to measure this difference mathematically without ever exposing the individual details that make up the data.

Researchers at EPFL, the University of Oxford, the University of Warwick, and the Infectious Diseases Data Observatory have developed a new method called FedPriKL to solve this exact problem. Their work focuses on a specific mathematical measure used to compare two sets of data, a tool that tells us how much one group of information has drifted away from a reference point. In this scenario, the reference point is a public standard that everyone agrees on, while the other group is the private, sensitive data held by users on their devices. The goal is to calculate the distance between these two groups without the central server ever seeing the individual records. The researchers created a protocol that allows a central coordinator to ask a small, random selection of devices to check how often certain items appear in their local data. These devices then send back only the counts for those specific items, which are combined securely. To ensure that even these counts cannot be traced back to a single person, the system adds a carefully calculated amount of mathematical noise to the final result.

The team found that their method works with a high degree of accuracy while maintaining strict privacy guarantees. They proved mathematically that their approach produces an unbiased estimate, meaning the result is correct on average, and that the amount of noise required to protect privacy is small enough not to ruin the usefulness of the data. In their experiments, they tested the system using a large dataset of handwritten digits, simulating a real-world scenario where thousands of users contribute data. They discovered that by carefully choosing how many devices to ask and how much noise to add, the system could produce results nearly as accurate as if no privacy protection had been used at all. This is a significant improvement over previous methods where devices tried to hide their data by adding noise before sending it, a technique that often led to inaccurate results. The new method keeps the noise addition to the very end of the process, after the data has been securely combined, which preserves the integrity of the measurement.

The researchers also explored how different settings affect the outcome. They found that the system works well even when only a small fraction of the total users are asked to participate in any given round, and that the amount of data each user needs to send is very small, often less than one kilobyte. This makes the system practical for devices with limited battery and memory. The study showed that the method can accurately distinguish between small changes in data and large ones, which is essential for deciding when a computer model needs to be updated. While the current version of the system relies on a trusted intermediate step to combine the data securely, the researchers demonstrated that this step can be performed using existing secure hardware or advanced cryptographic techniques, ensuring that no single entity ever sees the raw data. The work provides a concrete path forward for monitoring data trends in a way that respects user privacy, allowing organizations to keep their models accurate without compromising the confidentiality of the individuals who generate the data.

Technical Summary: FedPriKL – Federated and Differentially Private Estimation of KL Divergence

Problem Statement

In modern federated learning and analytics, a critical task is monitoring distribution drift to determine when models require retraining or fine-tuning. This requires comparing the empirical distribution of data held by distributed clients ( $P$ ) against a fixed public reference distribution ( $\Pi$ ). However, directly sharing client data or full histograms is often infeasible due to high communication costs and privacy constraints.

Existing approaches face significant hurdles:

Privacy: Centralized collection of samples violates user privacy.
Impossibility Results: The Shift Invariance Theorem [9] implies that estimating the KL divergence between two unknown distributions in a space smaller than the domain size is impossible.
Communication: Transmitting full histograms from clients to a server is bandwidth-prohibitive for large domains.
Bias in Local Perturbation: Standard local differential privacy (LDP) approaches, where clients add noise before aggregation, introduce significant bias when estimating non-linear functions like KL divergence, particularly when handling small probability masses.

The paper addresses the problem of estimating $D_{KL}(\Pi \parallel P)$ in a horizontal federated setting where $P$ is defined by the aggregate data of $n$ clients, and $\Pi$ is a known public benchmark. The goal is to achieve formal example-level differential privacy (DP) while minimizing communication overhead and maintaining estimator accuracy.

Methodology: FedPriKL

The authors propose FedPriKL, a sampling-based protocol that leverages a "trusted aggregator" model to achieve unbiased estimation under DP. The core technical innovation is an unbiased Monte Carlo estimator based on likelihood ratios, combined with secure aggregation and calibrated noise injection.

Key Components:

Unbiased Monte Carlo Estimator:
Instead of computing the full divergence, the method samples $m$ points $x_i$ from the reference distribution $\Pi$ . For each sample, the protocol estimates the likelihood ratio $r(x) = P(x)/\Pi(x)$ .
Using the identity derived in Fact IV.2, the KL divergence is estimated via the function:
$\Phi(r(x), \lambda) = \lambda(r(x) - 1) - \ln(r(x))$
The expectation of this function over samples from $\Pi$ equals $D_{KL}(\Pi \parallel P)$ . The parameter $\lambda$ controls the variance of the estimator.
Protocol Workflow (Algorithm 2):
- Sampling: The server selects disjoint batches of clients ( $C_t$ ) and samples points $x_{i,t}$ from $\Pi$ .
- Secure Aggregation (SecAgg): Clients compute the frequency of sampled points in their local datasets. These frequencies are aggregated using a secure aggregation protocol (e.g., Shamir's secret sharing) to compute the global empirical probability mass $P(x)$ without revealing individual client data.
- Trusted Aggregator Processing: The aggregated probabilities are sent to a trusted aggregator. The aggregator computes the likelihood ratios $r(x)$ , applies the non-linear transformation $\Phi$ , and adds calibrated Gaussian noise ( $\eta_{\epsilon, \delta}$ ) to the result.
- Final Estimation: The noisy transformed values are averaged to produce the final DP estimate.
Privacy Mechanism:
Unlike baseline approaches where clients add noise locally (pre-aggregation), FedPriKL adds noise after secure aggregation but before the non-linear transformation is finalized. This avoids the bias introduced by clipping negative values in local noise (a common issue in LDP). The sensitivity of the estimator is bounded (Theorem IV.4 and IV.5), allowing for precise noise calibration to satisfy $(\epsilon, \delta)$ -DP.
Trust Model:
The protocol assumes a trusted aggregator (or a TEE/SMC realization) that sees only the securely aggregated statistics of the sampled points, not raw client data. The server is "honest-but-curious" and only receives the final noisy estimate.

Key Contributions

Problem Formalization: The paper formalizes the problem of computing KL divergence in a federated setting with formal differential privacy guarantees, specifically addressing the case of a public reference vs. a private empirical distribution.
FedPriKL Algorithm: The authors present the first communication-efficient, sampling-based federated estimator for $D_{KL}(\Pi \parallel P)$ that provides example-level DP.
Theoretical Analysis:
- Unbiasedness: Proven that the estimator is unbiased (Theorem IV.7).
- Sensitivity Bounds: Established bounded sensitivity for the estimator, enabling the derivation of optimal noise scales (Theorems IV.4, IV.5).
- Variance Characterization: Provided a theoretical characterization of the estimator's variance as a function of $\lambda$ , $\epsilon$ , and sample size, and derived the optimal $\lambda$ to minimize variance (Theorem V.1, V.3).
Communication Efficiency: The per-client payload is independent of the domain size. For a domain of $2^{16}$ elements, the payload remains below 1 KB.

Experimental Results

The authors evaluated FedPriKL on the FEMNIST dataset (handwritten digits partitioned by writer), comparing it against a non-private estimator and a baseline LDP approach (Algorithm 1).

Accuracy vs. Privacy: FedPriKL achieves accuracy comparable to the non-private estimator when the privacy budget $\epsilon$ is moderate ( $0.5 \le \epsilon \le 1.0$ ).
Superiority over Baseline: FedPriKL significantly outperforms the baseline (local perturbation) in terms of accuracy and stability. The baseline suffers from bias due to the necessary clipping of negative probability estimates.
Parameter Sensitivity:
- $\lambda$ : The optimal variance parameter $\lambda$ is empirically found to be close to 0.
- Sample Size ( $m$ ): A small number of samples ( $m=10$ ) is sufficient to achieve near-optimal accuracy, keeping client communication lightweight.
- Batch Size: Varying the number of participating clients affects the rate of convergence but does not fundamentally alter the optimal $\lambda$ .
Robustness: The method maintains low absolute error across different divergence magnitudes (from small to large KL values).

Significance and Claims

The paper claims that FedPriKL is the first communication-efficient federated estimator for KL divergence between a public reference and a private population that offers formal example-level differential privacy.

The significance lies in its ability to:

Enable Drift Detection: Provide a privacy-preserving mechanism for platforms to detect distribution shifts and trigger model retraining without exposing sensitive user data.
Overcome Impossibility: By restricting the problem to a known public reference, it sidesteps the impossibility results regarding sketching unknown distributions.
Balance Utility and Privacy: It demonstrates that high utility can be maintained under strict privacy constraints by moving the noise injection step to a post-aggregation phase via a trusted component, thereby avoiding the bias inherent in local perturbation methods.

The authors note that the reliance on a trusted aggregator (or TEE/SMC) is a practical trade-off that can be discharged via secure hardware or multiparty computation, and they identify the removal of this trust assumption as a direction for future work.