PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Computation of ROC and PR Curves

Xuefeng Xu, Graham Cormode

arXiv:2510.04979v2cs.LGcs.CR

TL;DR

Federated model evaluation needs ROC and PR curves without centralizing sensitive scores and labels. The paper approximates these curves from quantiles using privacy-preserving aggregation, with error guarantees and communication costs governed by the number of quantiles. Its theoretical AE bounds depend on class imbalance and score-distribution assumptions.

  • Problem

    Federated settings need fuller classification evaluation than accuracy or loss, but exact ROC and PR computation requires access to scores and labels that cannot be centrally shared.

    Source: §1 · p. 1

  • Method

    The method reconstructs ROC and PR curves from compact score-distribution quantiles using O(Q) communication without raw-data sharing, with secure aggregation and distributed differential privacy.

    Source: §1 · p. 2

  • Results

    ROC AE is O(1/Q); PR AE is ~O(1/Q) under mild imbalance and ~O(1/(Qr)) under extreme imbalance.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The number of quantiles Q provides a tunable trade-off between Area Error and communication cost for distributed curve evaluation.

    Source: §8 · p. 12

    The theoretical accuracy analysis uses a well-behaved score-distribution assumption that does not hold universally, although experiments report robustness when it is violated.

    Source: §5.3 · p. 7

Abstract

from arXiv · show

Receiver Operating Characteristic (ROC) and Precision-Recall (PR) curves are fundamental analytical tools for evaluating classification models, providing a comprehensive view of performance across decision thresholds. In modern data management settings, such evaluation must often be performed over data that is distributed across multiple parties and subject to strict privacy constraints. This setting arises naturally in federated learning (FL) and collaborative data platforms, where raw prediction scores and labels cannot be centrally collected. We study the problem of computing ROC and PR curves over distributed data under formal privacy guarantees. The key challenge is that exact computation requires access to all prediction scores and labels, leading to linear communication costs and privacy risks. To address this, we propose a novel framework for approximating ROC and PR curves using quantiles of the score distribution, which can be computed efficiently under secure aggregation and distributed differential privacy. Our approach requires only $O(Q)$ communication, where $Q$ is the number of quantiles, and avoids sharing raw data entirely. We provide theoretical guarantees on the approximation quality by bounding the Area Error (AE) between the true and estimated curves, demonstrating principled trade-offs among approximation accuracy, privacy protection, and communication cost. Our method is robust to data heterogeneity and skew, making it suitable for real-world distributed data management scenarios. Experiments on real-world datasets show that our approach achieves high accuracy with low communication overhead under strong privacy constraints. Overall, this work provides a practical and theoretically grounded solution for privacy-preserving evaluation of classification models over distributed data.

1 INTRODUCTION

The introduction frames full-curve evaluation as an unmet need in privacy-constrained federated settings and proposes quantile-based ROC and PR approximation with accuracy guarantees and tunable communication costs.

1 INTRODUCTION

  • Federated model evaluation needs richer information than accuracy or loss, while exact ROC and PR computation requires sharing scores and labels at linear communication cost.The introduction notes that accuracy can mislead on imbalanced data and that models with lower loss may have worse ROC/PR curves.Source: §1 · p. 1
  • ROC AE is O(1/Q); PR AE is ~O(1/Q) under mild imbalance and ~O(1/(Qr)) under extreme imbalance, with bounds extended to distributed differential privacy.The analysis assumes O(1)-Lipschitz score distributions; the extreme-imbalance bound depends on the class ratio r.Source: §1 · p. 2
  • With Q≈10^2, experiments report ROC AE near 10^-3 and PR AE below 10^-2, remaining low at ε≤1.The authors report low communication and other computational costs in their Flower implementation.Source: §1 · p. 2
  • Quantile-based ECDF approximations reconstruct ROC and PR curves with O(Q) communication, no raw-data sharing, and independence from example count and client heterogeneity.The introduction also describes a privacy-preserving variant whose bounds capture accuracy, privacy, and communication trade-offs.Source: §1 · p. 2
  • The authors describe their ROC/PR materialization protocol as novel despite using standard components, and present Section 5 as the first accuracy guarantee for this problem.The paper situates the problem in federated learning, cross-silo analytics, and collaborative data platforms.Source: §1 · pp. 1–2

2 RELATED WORK

Prior work addresses ROC or AUC through averaging, centralized or distributed differential privacy, and selected-threshold methods, but the cited approaches leave accuracy guarantees or full-curve comparison challenges.

2 RELATED WORK

  • Fawcett's split-data ROC merging heuristics lack formal error guarantees and do not directly recover the global curve under heterogeneous clients; Chen et al.'s centralized DP method also lacks formal error bounds.The authors say adaptation of Chen et al.'s method to a distributed setting is unclear.Source: §2 · p. 2
  • Prior DP AUC methods target a scalar summary, while Sun et al.'s distributed DP AUC approach provides privacy but no result-accuracy bound.The cited Local DP AUC work has large error, motivating a better privacy-accuracy trade-off.Source: §2 · pp. 2–3
  • Barczewski et al. [3] bound squared point error at selected thresholds, so their guarantee is not directly comparable to Area Error; the authors report greater overhead and lower AE for their method in most tested settings.The comparison differs in error metric, evaluation domain, and assumptions.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries define ROC and PR curves and review the privacy, federated quantile, and interpolation techniques used by the approach.

3.1 The ROC and PR Curves

  • ROC plots TPR against FPR, which is invariant to class skew, whereas PR plots precision against recall and is sensitive to imbalance.PR can be more informative when positive instances are rare.Source: §3.1 · p. 3

3.2 Differential Privacy and Federated Quantiles

  • Distributed DP lets clients contribute noise that aggregates to the centralized noise scale, while secure aggregation reveals sums but not individual client inputs.Federated quantile estimation uses aggregated noisy histograms; hierarchical histograms support improved accuracy and consistency enforcement.Source: §3.2 · pp. 3–4

3.3 Monotone Interpolation

  • PCHIP uses piecewise cubics with selected derivatives to preserve monotonicity and avoid overshoot when reconstructing curves from quantiles.The approach also uses linear interpolation, which is simple and efficient but may lack smoothness and fail to capture underlying trends.Source: §3.3 · p. 4

4 FEDERATED ROC AND PR CURVES

The method reconstructs ROC and PR curves from class-specific score ECDFs estimated with quantiles, then estimates those quantiles through federated histograms. It targets compact communication while supporting differential privacy and data distributed across clients.

4.1 Curve Approximation via Quantiles

  • Class-specific score quantiles approximate ECDFs, which are interpolated with PCHIP to derive ROC rates and PR precision and recall at arbitrary thresholds.Figures 1 and 2 illustrate ECDF approximation and the resulting ROC and PR curves.Source: §4.1 · p. 4, Figure 1 · p. 4, Figure 2 · p. 4

4.2 Quantile Estimation via Histograms

  • The aggregated histograms achieve ε-DP, and repeated application T times provides a Tε-DP guarantee.Clients add independent noise to histogram bins under DP before aggregation.Source: §4.2 · p. 4
  • Additively aggregated local score histograms match the centralized global histogram regardless of how data is distributed across clients.The method therefore does not depend on client data heterogeneity for this histogram result.Source: §4.2 · p. 5
  • O(Q) communication suffices when histogram depth is chosen for Q quantiles; with Q=1024, each client sends approximately 213 bins per histogram, totaling around 8K integers.Using secure aggregation increases communication to four rounds or fewer.Source: §4.2 · p. 5

5 ANALYSIS OF AREA ERROR

This section defines Area Error (AE) for ROC and PR curves and bounds it under exact and approximate quantiles in federated settings with privacy noise. It also bounds positive- and negative-class quantile estimation error under distributed differential privacy and propagates those bounds to curve area error, explaining why noisy class-count estimates do not change the overall bound.

5.1 Area Error Definition

  • AE integrates absolute curve differences over the full domain, capturing discrepancies that AUC difference can miss because a small AE implies small AUC error, but not vice versa.Unlike Point Error, it captures discrepancies across the curve rather than only differences at score thresholds.Source: §5.1 · p. 5

5.2 Bounding Area Error Using Exact Quantiles

  • With Q exact quantiles, ROC AE is O(1/Q); threshold-rate errors are bounded by half a quantile interval, and the exact-quantile PR analysis follows a similar outline.The PR analysis is more involved because precision depends nonlinearly on TPR and FPR.Source: §5.2 · pp. 5–6

5.3 Well-Behaved Score Distributions and Lemmas for Approximate Quantiles

  • Lipschitz (“well-behaved”) score distributions let quantile-estimation errors bound TPR/FPR errors; despite local Adult score clustering violating this condition, the method remains empirically robust, and privacy guarantees do not require it.The condition is used for theoretical error bounds and may fail for score distributions with spikes.Source: §5.3 · pp. 6–7

5.4 Bounding the Area Error Using Approximate Quantiles

  • With approximate quantiles and O(1)-well-behaved distributions, ROC AE is O(1/Q); PR AE is ˜O(1/Q) when r ≥ 0.1 and ˜O(1/(Qr)) under extreme class imbalance.Here r = n+/n−; the extreme-imbalance bound requires Q sufficiently large relative to 1/r.Source: §5.4 · pp. 7–9

5.5 Error Analysis in the Federated Setting with Security and Privacy

  • The expected class-specific quantile error is α± = Õ(1/Q + 1/(n±ε)), following hierarchical-histogram traversal with accumulated noise variance O(bh^3/ε^2).Each of h layers splits the privacy budget equally and adds Laplace noise of scale h/ε per bin; for typical settings b = 2 and h = O(log Q).Source: §5.5 · p. 9
  • Under DDP, the ROC and PR curve area-error bounds use a combined quantile error of O(α+ + α−), where α+ and α− are the positive- and negative-class errors.The intermediate bounds are |T(f) − T̂(f)| ≤ O(α+ + α−) and |F(t) − F̂(t)| ≤ O(α+ + α−).Source: §5.5 · p. 9
  • Noisy-histogram class counts have absolute error O(log Q/ε), negligible relative to class counts for typical datasets and ε ≈ 1, and do not change the PR bound.ROC does not require class counts; for PR, the error is dominated by quantile estimation.Source: §5.5 · p. 9

6 EMPIRICAL EVALUATION

The empirical evaluation measures secure-aggregation costs, compares interpolation and privacy settings, tests against a range-query method, and examines PR-curve error under class imbalance.

6 EMPIRICAL EVALUATION

  • The evaluation covers Bank, Adult, and Cover with XGBoost and Logistic Regression, using distributed discrete Laplace noise for privacy by default.The datasets were selected to vary in class imbalance.Source: §6 · p. 9

6.1 Initial Experiments

  • For SecAgg+ histogram aggregation, client-side aggregation takes approximately 1.5 seconds across all tested bin configurations, with communication overhead below 1 MB per client.The evaluation excludes setup and key-sharing phases and reports only histogram-aggregation cost; overall execution time and memory usage are dominated by the underlying secure aggregation protocol.Source: §6.1 · p. 9
  • PCHIP consistently outperforms linear interpolation, while smaller ε raises AE; error remains low at ε≤1, and DP noise can produce an AE plateau as Q increases.The gap between exact quantiles and secure histogram aggregation is more noticeable on Cover, but negligible on Adult and Bank, especially at large Q.Source: §6.1 · p. 10

6.2 Comparison with Prior Work

  • For Q < 100, the range-query method can have lower AE, especially on Cover, but its results are more erratic as Q increases; the difference vanishes at larger Q.The quantile method’s separately estimated positive and negative thresholds may be misaligned at small Q.Source: §6.2 · p. 10

6.3 Experiments on Class-Imbalanced Data

  • As the positive-to-negative ratio r decreases, PR-curve AE usually increases, though a near-flat curve under extreme imbalance can still have low AE.The flat curve reflects classifier performance approaching that of a random classifier.Source: §6.3 · p. 10

7 DISCUSSION

The discussion describes extensions to multi-class classification and related metrics, qualifies the well-behaved-score assumption, and considers local differential privacy and hybrid methods.

7 DISCUSSION

  • For multi-class classification, one-vs-rest or one-vs-one decomposes the task into binary curves, whose area-error bounds carry over to aggregated curves.Examples of aggregation include macro- and weighted-average curves.Source: §7 · pp. 10–11
  • The approach extends to AUC and DET curves; Precision-Recall-Gain curves are proposed as future work.The area error bounds the absolute AUC difference by O(1/Q).Source: §7 · p. 11
  • The O(1)-well-behaved score-distribution condition is sufficient for the theoretical analysis but not necessary for observed robustness; guarantees under weaker assumptions remain open.Score distributions with spikes can violate the condition.Source: §7 · p. 12
  • Under local differential privacy, independent client noise increases total noise; the analysis assumes one example per client, with n clients for n examples.The variance of each bin count is O(n/ε^2).Source: §7 · p. 12
  • At small Q, quantile-based estimates may not outperform range-query methods when aligned thresholds are critical; a hybrid quantile and range-query approach is proposed as a mitigation.The proposed hybrid may give stronger ROC area-error bounds under mild assumptions, but can have high variance at large Q and lacks clear PR area-error bounds.Source: §7 · p. 12

8 CONCLUSION

The paper presents a quantile-based framework for privacy-preserving, communication-efficient computation of ROC and PR curves over distributed data. It reports area-error guarantees and empirical accuracy under strong privacy constraints.

8 CONCLUSION

  • The framework approximates ROC and PR curves from compact distribution summaries, with area error scaling as O(1/Q) or Õ(1/Q) and communication growing linearly with Q.Histogram-based aggregation supports compatibility with secure aggregation and distributed differential privacy.Source: §8 · p. 12

A COMPLETION OF THE PROOF OF THEOREM 5.2

The proof completion considers positive quantiles inserted between negative quantiles and concludes that the total ROC area error remains O(1/Q). The additional discussion addresses score support and storage constraints.

A COMPLETION OF THE PROOF OF THEOREM 5.2

  • Including positive quantiles does not increase the worst-case ROC area-error bound; summing across segments still gives total AE of O(1/Q).The maximum segment bound occurs when the inserted point coincides with its neighboring points.Source: A COMPLETION OF THE PROOF OF THEOREM 5.2 · p. 14

B ADDITIONAL DISCUSSION

  • Scores are assumed to lie in a known bounded interval such as [0, 1], and known discrete support can be used to tailor histogram bins for better estimation accuracy.Source: B ADDITIONAL DISCUSSION · p. 14
  • Quantile sketches such as GK could reduce storage on space-constrained devices, but adapting them requires a privacy-preserving distributed protocol.Differentially private quantile summaries are identified as a possible starting point.Source: B ADDITIONAL DISCUSSION · p. 14

C COMPARISON OF DIFFERENT STRATEGIES FOR PR CURVE

The section compares separate and combined quantile strategies for estimating PR curves, finding that separate estimation produces lower and more stable area error. It attributes this difference to how the strategies handle the precision numerator and denominator.

D PR CURVE EXPERIMENTS WITH XGBOOST

The XGBoost experiments on PR curves examine interpolation methods, the effect of ε, and comparison with a range-query method.

  • Figure 14 compares interpolation methods for the PR curve with XGBoost.Source: Figure 14 · p. 16
  • Figure 15 examines the effect of ε on the PR curve with XGBoost.Source: Figure 15 · p. 16
  • Figure 16 compares the PR-curve approach with a range-query method for XGBoost.Source: Figure 16 · p. 16

E EXPERIMENTS WITH LOGISTIC REGRESSION

The Logistic Regression experiments cover prediction-score distributions and PR- and ROC-curve comparisons across interpolation methods, ε settings, range-query methods, and class imbalance.

Related papers

Loading 2510.04979v2…