Federated Computation of ROC and PR Curves

arXiv:2510.04979 · cs.LG, cs.CR · Submitted 2025-10-06 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Federated Computation of ROC and PR Curves".

Jane: Receiver Operating Characteristic (ROC) and Precision-Recall (PR) curves are fundamental tools for evaluating machine learning classifiers, offering detailed insights into the trade-offs between true positive rate vs.

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So, wrapping up our discussion on "Federated Computation of ROC and PR Curves," the authors, Xuefeng Xu and Graham Cormode, have presented a method that provides a way to approximate those important ROC and PR curves in Federated Learning by estimating quantiles from the prediction score distribution under distributed differential privacy.

Jane: What this means for us is that we can finally get a more reliable picture of model performance in distributed settings without needing access to raw data or sacrificing our privacy too much, provided we are willing to accept an approximation error bounded by terms related to the number of quantiles and the privacy budget.

Lu: The implication here is significant because it gives researchers a robust tool to assess classification performance in federated environments that accounts for practical limitations like communication overhead and privacy constraints simultaneously.

Meng: From a practical standpoint, this suggests that we can move towards deploying more complex AI models across decentralized networks knowing we have a mathematically defined way to quantify their trade-offs between accuracy and the necessary privacy safeguards.

Lalam: The cultural impact of this paper is that it builds trust in distributed AI systems; it provides a standard way to measure performance that respects user privacy and system constraints, which is essential for deploying AI in sensitive areas.

Tom: It really does give us a better lens through which to view model evaluation in FL, moving beyond just accuracy metrics to get a more holistic understanding of where the model actually struggles across different operational thresholds.

Jane: So, in short, this paper offers a concrete mechanism for estimating the ROC and PR curves under distributed differential privacy in an FL setting, giving us quantified bounds on how accurate that approximation is based on the number of quantiles we choose.

Lu: This work lays a strong foundation for extending these ideas to other metrics like AUC or even detection error trade-off curves, suggesting a broader applicability beyond just ROC and PR.

Meng: I'm optimistic that as the community adopts these theoretical guarantees, we'll see FL models become much more trustworthy because we will have better tools to verify their performance in complex, real-world distributed scenarios.

Lalam: Indeed, having these verifiable metrics under strict privacy rules is what will enable the next generation of widely deployed and trusted AI applications.

Conclusion: Tom: So we’ve been diving into how this paper tackles approximating ROC and PR curves in federated learning by estimating quantiles from prediction scores under distributed differential privacy, and now it's time to talk about the core of what they did with "Federated Computation of ROC and PR Curves."

Jane: Right, Tom. They essentially figured out a way for AI models trained across many devices to get a reliable picture of how well those models are actually performing when we look at different classification thresholds.

Lu: I think it’s fascinating because it solves that big problem where we can’t just look at accuracy and feel like we know if the model is good, especially when the data stays locked away on individual clients.

Meng: From an engineering standpoint, what I find compelling is how they manage the communication cost; if it scales linearly with the number of bins instead of exponentially with data size, that makes it actually feasible for real-world deployment.

Lalam: For me, this work suggests a path toward building AI systems that are not just accurate but also transparent in their performance evaluations, which really helps build public trust in these distributed environments.

Tom: Exactly! And looking at the authors, Xuefeng Xu and Graham Cormode—they’ve put together a method that provides mathematical guarantees on the error of those curve approximations, which is huge because it gives us confidence in what we're seeing.

Jane: That’s right, Tom. They didn't just throw out some simple hacks; they provided formal bounds on the Area Error under both secure aggregation and distributed differential privacy settings.

Lu: The theoretical guarantees are what really excite me; the complexity of those error bounds, like O(one/Q or one/√nε), shows how carefully they’ve balanced privacy noise against estimation precision.

Meng: I'm looking at the practical impact, and honestly, being able to measure performance without needing raw data access means we can deploy these models in highly sensitive areas where data sharing is absolutely forbidden.

Lalam: Precisely. This advance opens up new possibilities for AI deployment in healthcare or finance where privacy regulations are strict; we can prove the model's reliability without ever seeing the patient records or transaction histories.

Tom: It really puts a powerful framework into our hands for evaluating distributed AI, and it sets a high bar for how we measure performance beyond simple accuracy metrics.

Jane: It’s clear that this paper isn't just about math; it’s about giving us a more complete and honest scorecard for AI deployed in decentralized settings.

Lu: So the next big question is how we can best integrate these quantile estimation methods into larger, more complex federated workflows efficiently.

University of Warwick

cs.LG, cs.CR

Submitted: 2025-10-06

Updated: 2026-09-27

Comments: VLDB 2027. 19 pages, 26 figures, 1 table. Project page see http://xuefeng-xu.github.io/fedcurve.html

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 89/100

The gist: Receiver Operating Characteristic (ROC) and Precision-Recall (PR) curves are fundamental tools for evaluating machine learning classifiers, offering detailed insights into the trade-offs between true

Key concepts

Receiver Operating Characteristic (ROC): A tool used to evaluate classifier performance by plotting the True Positive Rate against the False Positive Rate across different classification thresholds. It shows how well a model can distinguish between positive and negative classes.
Precision-Recall (PR) Curve: Similar to ROC, this curve plots Precision against Recall. Precision measures the accuracy of positive predictions, while Recall measures how many actual positives were found. It is particularly useful for imbalanced datasets where accuracy alone can be misleading.
Empirical Cumulative Distribution Function (ECDF): The ECDF estimates the distribution of prediction scores based on observed data points. The method uses this function to approximate the true ROC and PR curves by calculating quantiles from these estimated distributions without needing raw data access.
Area Error (AE): This metric quantifies how far the approximated curve is from the true curve by measuring the integral of their absolute differences over the entire range. Theoretical bounds are established for this error under different privacy conditions.

Terminology

Area Error — 102× in this paper
Accuracy — 26× in this paper · explained in 1 episode
Differential Privacy — 25× in this paper · explained in 4 episodes
AUC — 16× in this paper · explained in 2 episodes
Aggregation — 15× in this paper · explained in 1 episode
Differentially Private — 11× in this paper · explained in 3 episodes
Federated Learning — 10× in this paper · explained in 14 episodes
Area Error (AE) — 8× in this paper · explained in 1 episode
Exact Quantiles — 8× in this paper
Data Heterogeneity — 7× in this paper · explained in 3 episodes
Under Distributed Differential Privacy — 7× in this paper
Theoretical Guarantees — 6× in this paper · explained in 2 episodes
Consistency — 4× in this paper · explained in 3 episodes
False Positive Rate — 4× in this paper
Federated Learning (FL) — 4× in this paper · explained in 7 episodes
True Positive Rate — 4× in this paper
Under Secure Aggregation — 4× in this paper
Communication Overhead — 3× in this paper · explained in 2 episodes
Receiver Operating Characteristic — 3× in this paper
Detection Error Tradeoff — 2× in this paper
Robustness — 2× in this paper · explained in 5 episodes
Alignment — 1× in this paper · explained in 1 episode
Area Under the Curve — 1× in this paper
Area Under the Curve (AUC) — 1× in this paper · explained in 1 episode
Calibration — 1× in this paper · explained in 7 episodes
Core — 1× in this paper · explained in 2 episodes
Differential Privacy (DP) — 1× in this paper · explained in 7 episodes
False Negative Rate — 1× in this paper
Score Function — 1× in this paper · explained in 4 episodes

Summary

Receiver Operating Characteristic (ROC) and Precision-Recall (PR) curves are fundamental tools for evaluating machine learning classifiers, offering detailed insights into the trade-offs between true positive rate vs. false positive rate (ROC) or precision vs. recall (PR). However, in Federated Learning (FL) scenarios, where data is distributed across multiple clients, computing these curves is challenging due to privacy and communication constraints.

The gist: This paper proposes a novel method for approximating ROC and PR curves in a federated setting by estimating quantiles of the prediction score distribution under distributed differential privacy.

Motivation

Current FL evaluation tools often rely on simple metrics like accuracy and loss, which provide an incomplete picture of model performance, especially on imbalanced datasets where accuracy can be misleading. ROC and PR curves offer a comprehensive view of model performance across all classification thresholds, but their exact computation requires access to raw prediction scores and labels, violating privacy principles in FL. Furthermore, naively aggregating this information incurs significant communication cost that scales linearly with dataset size. Prior work has shown that even the ROC curve can reveal information about class labels.

Methodology for Curve Approximation

The proposed method approximates ROC and PR curves by estimating the empirical cumulative distribution function (ECDF) of prediction scores using quantiles, computed separately for positive and negative classes, without accessing raw data. The process involves:

Constructing hierarchical histograms where clients locally bin prediction scores with evenly spaced boundaries across the score range.
Sending these histograms to the server, which aggregates them to estimate global quantiles from which approximate ECDFs are constructed using monotone interpolation (PCHIP interpolation is recommended).

The curve points are then derived using the estimated ECDFs:

((

F(s) = 1 − Φ−(s), where F is FPR and Φ− is the ECDF of negative scores.

((

T(s) = 1 − Φ+(s), where T is TPR/Recall and Φ+ is the ECDF of positive scores.

((

P(s) = T(s)n+ / (T(s)n+ + F(s)n−), where P is Precision.

Theoretical Guarantees on Area Error

The approximation quality is quantified by the Area Error (AE), defined as the integral of the absolute difference between the true and estimated curves over [0, 1]. The paper provides theoretical bounds on this error:

Under Secure Aggregation (SA), it proves a worst-case AE bound of O(1/Q) for the ROC curve and O˜(1/Q) for the PR curve, where Q is the number of quantiles used.
Under Distributed Differential Privacy (DDP), the error bound is extended to O˜(1/Q + 1/√nε) for both ROC and PR curves, where ε is the standard privacy budget and n is the total number of examples.

Privacy and Communication Trade-offs

The method achieves an efficient trade-off between accuracy, privacy, and communication cost. The communication cost scales linearly with the number of leaf bins in the histogram structure. To ensure accurate quantile estimation, a height parameter h is set as h = ⌈logb Q⌉ + c. This keeps the total communication cost at O(Q), which is much smaller than the dataset size. Furthermore, when DDP is applied, each client adds independent noise to their local histograms before sending them to the server.

Empirical Validation and Findings

Empirical results on real-world datasets (Bank, Adult, Cover) demonstrate high approximation accuracy with minimal communication and strong privacy guarantees. Key findings include:

: The PCHIP interpolation method consistently outperforms linear interpolation for both ROC and PR curves. Under DDP, the Area Error exhibits a plateau as Q increases, consistent with the theoretical analysis. 21

: The separate strategy for computing the PR curve (estimating quantiles for positive and negative examples separately) consistently yields lower and more stable area error compared to combining quantiles. 17

: The method remains robust under strong privacy settings (e.g., ε ≤ 1), with low area errors achieved even on larger datasets like Cover due to the error bound scaling with 1/√nε. 22

Extensions and Future Work

The proposed approach is extensible to multi-class classification by decomposing the problem into multiple binary tasks (e.g., one-vs-rest). It also naturally extends to derived metrics such as AUC, where the area error directly bounds the AUC difference by O(1/Q). The method can be adapted for other metrics like the Detection Error Tradeoff (DET) curve. Future work includes integrating these techniques into popular FL frameworks and studying how to control the impact of malicious clients attempting to poison data collection.

Improvements for AI systems

Based on the provided scientific paper, here are specific improvements that an AI system could implement by leveraging its findings:

Improve model evaluation in Federated Learning (FL) environments by replacing simple metrics like accuracy and loss with ROC and PR curve analysis.
Enable informed deployment decisions by assessing model performance across all classification thresholds, which is crucial for imbalanced datasets where accuracy is misleading.
Ensure privacy-preserving evaluation by computing these curves without sharing raw prediction scores or class labels, instead using only quantiles of the prediction score distribution under Differential Privacy (DP).
Reduce communication overhead in FL by utilizing a federated quantile estimation method based on histogram aggregation, leading to a communication complexity of only O(Q) rather than scaling with the full dataset size.
Achieve provable performance guarantees for these evaluations by providing theoretical bounds on the Area Error (AE), such as O(1/Q) under Secure Aggregation (SA) and O˜(1/Q + 1/nε) under Distributed Differential Privacy (DDP).
Adapt evaluation strategies to handle data heterogeneity and skew robustly, as the quantile estimation method is agnostic to these factors because it aggregates counts additively.
Optimize the trade-off between privacy and accuracy by tuning the number of quantiles (Q), allowing practitioners to select an optimal Q based on their required approximation accuracy level while maintaining a specific privacy budget (ε).
Implement advanced interpolation techniques, such as Piecewise Cubic Hermite Interpolation (PCHIP), for reconstructing the ROC and PR curves from estimated quantiles to ensure smoother, more accurate curve approximations compared to linear interpolation.
Provide robust handling of class imbalance by allowing the evaluation of PR curves with formal error bounds that explicitly depend on the class ratio (r), distinguishing between mild and extreme imbalance scenarios.
Integrate the method into existing FL frameworks like Flower for practical, privacy-preserving model evaluation pipelines.

In summary, an AI system utilizing this paper can perform a comprehensive, privacy-guaranteed assessment of machine learning classifiers trained in distributed environments, providing a nuanced view of model efficacy across all operational thresholds with minimal communication overhead.