Paper Overview
Field: Machine Learning Authors: Moshe Shenfeld, Eliad Tsfadia, Katrina Ligett Released: 2025-10-28 arXiv: 2510.25919
Abstract (Full Translation)
An estimator can be accurate and stable on typical data, yet sensitive to a few possible records. Differentially private mechanisms commonly scale their noise to the worst-case influence of a single record, which lets these records dictate the noise even when the remaining data would allow far less. Removing them first would restore the smaller scale, but the removal must itself be private.
We introduce propose-filter-release (PFR), which, by privately filtering its input, turns a mechanism that protects the addition or removal of a typical record — one that fits the remaining data — into one that is differentially private in the standard sense, on every input. Using our novel filtering step, PFR requires only a concave friendliness score, which measures how well a record fits a dataset, and a friendly differentially private release mechanism (one that is private when the changed record fits the remaining data). For every such score and release mechanism, it guarantees differential privacy under public conditions on the number of records, making it a general privacy primitive comparable to propose-test-release, with FriendlyCore viewable as one of its implementations. We demonstrate the versatility of PFR by instantiating it for scalar statistics, principal subspace estimation, KL divergence of user histograms, effective resistance of graphs, and stable ranking.
Why It Matters
- Outlier problem: Worst-case sensitivity lets a few atypical records inflate privacy noise for everyone, degrading utility on typical data.
- Private filtering: PFR removes outliers privately, so the reduced sensitivity of the remaining data can be safely exploited.
- Generality: Any concave friendliness score plus a friendly-DP release mechanism suffices — the framework unifies prior approaches like propose-test-release and FriendlyCore.