The accuracy of many machine learning estimators depends on the quality and representativeness of training data. In practice, an model can perform well on the majority of records while remaining vulnerable to a small subset of outlying or influential entries. Differential privacy (DP) mechanisms typically add noise scaled to the worst-case influence of a single record. This approach ensures privacy guarantees even when one record deviates arbitrarily, but it comes at a cost: the noise magnitude is dictated by the most extreme case, even when the bulk of the data would support a much tighter calibration.
Removing outlying records before applying a private mechanism would reduce the required noise scale, but the removal step itself must preserve privacy. Naively dropping records that appear anomalous can itself violate the privacy budget or introduce bias. The core tension is how to identify and filter records without compromising the differential privacy guarantee.
The propose-filter-release framework
Propose-filter-release (PFR) addresses this tension by inserting a private filtering step between the data and the release mechanism. The framework takes as input a dataset, privately removes records that are judged to be unfriendly, and then applies a base mechanism that was designed to protect the addition or removal of a typical record. After filtering, the mechanism is differentially private in the standard sense on every input.
PFR does not require a specific distance metric or outlier detection method. Instead, it relies on two components:
- A concave friendliness score that quantifies how well a given record fits the remaining dataset. The score is concave, meaning diminishing returns as fit improves, which enables compositional guarantees.
- A friendly-DP release mechanism that is private when the changed record fits the remaining data. If the record is unfriendly, the mechanism withholds output or applies a fallback that does not violate the privacy definition.
Together, these components allow PFR to scale noise to the typical sensitivity of the data rather than the worst-case. The guarantee holds under public conditions on the number of records, making PFR a general-purpose privacy primitive comparable to propose-test-release (PTR).
Friendliness scoring and private filtering
The friendliness score assigns a value to each record indicating its compatibility with the rest of the dataset. Concavity ensures that the score does not grow arbitrarily with small improvements in fit, which is essential for the privacy analysis. The score is not a binary classifier; it provides a continuous measure that the filtering step can use to decide which records to remove while preserving the overall privacy budget.
The filtering step operates as follows: for each record, compute the friendliness score assuming that record is removed. If the score falls below a public threshold, the record is deemed unfriendly and is filtered out. The threshold is chosen based on the desired privacy parameters and the number of records, but it is not itself secret. After filtering, the remaining dataset is passed to the release mechanism.
Because the filtering is private, the mechanism that follows must be friendly-DP. A friendly-DP mechanism is one that satisfies the differential privacy definition when the record that was added or removed is friendly (i.e., fits the data well). When the record is unfriendly, the mechanism may output a default value or abstain, and this behavior is allowed under the privacy definition as long as it does not leak information about friendly records.
Instantiation for scalar statistics
For scalar statistics, the friendliness score can be based on the residual of a record relative to the mean or median of the remaining data. A record with a large residual relative to the scale of the other points receives a low friendliness score, indicating it is unfriendly. The release mechanism can be the standard Laplace or Gaussian mechanism applied to the sum or mean of the filtered dataset. Because the friendliness score is concave in the residual, the privacy analysis carries over directly.
In this instantiation, PFR effectively reduces the sensitivity from the range of the entire dataset to the typical spread of the data after removing outlying records. The number of records must satisfy a public condition such as n > c ċ d for some constant c and dimension d, which is a common condition in DP analyses of scalar statistics.
Instantiation for principal subspace estimation
Principal subspace estimation seeks a low-dimensional representation of high-dimensional data. The sensitivity of the subspace depends on the directions in which the data varies most. A record that lies far outside the main cluster of points can dominate the estimated subspace, causing the noise scale to inflate.
In the PFR instantiation, the friendliness score measures how well a record aligns with the principal components of the remaining data. A record that is nearly orthogonal to the top eigenvectors receives a low score. The release mechanism adds noise to the subspace estimate, with the noise scale determined by the typical rather than worst-case sensitivity. The concavity of the score in the alignment measure ensures the privacy guarantee.
Instantiation for KL divergence of user histograms
When users report histograms, the KL divergence between a user's histogram and the population histogram can be sensitive to a single outlying category. PFR provides a way to compute a private estimate of the average KL divergence while scaling noise to the typical sensitivity.
The friendliness score for a histogram record can be based on the ratio of the user's category counts to the expected counts under the population distribution. Records where this ratio is extreme receive low friendliness. The release mechanism answers with a noisy version of the average KL divergence over the filtered histograms. The concavity of the score in the count ratio ensures the analysis holds.
Instantiation for effective resistances of a graph
Effective resistances measure the voltage experienced at a node when a unit current is injected at another node, grounded at a reference. They are used in graph algorithms for sampling, sparsification, and optimization. A single edge with very high resistance can inflate the sensitivity of estimates based on effective resistances.
In the PFR instantiation, the friendliness score evaluates how much a given edge contributes to the overall effective resistance profile. Edges whose removal would drastically change the resistance profile receive low friendliness. The release mechanism perturb the effective resistance estimates with noise scaled to the typical profile after filtering. The concavity of the score in the resistance change ensures the privacy guarantee.
Instantiation for treatment-rule selection
In causal or policy evaluation, treatment-rule selection chooses which action to take given an observed state. The sensitivity of the selected rule can be dominated by a few states that visit rarely or have extreme outcomes. PFR can be used to release a private policy that selects treatment rules while scaling noise to the typical state-action distribution.
The friendliness score for a state can be based on the visitation frequency or the magnitude of the outcome. States with low visitation or high outcome variance receive low friendliness. The release mechanism outputs a private policy that selects rules based on the filtered dataset. The concavity of the score in the visitation-outcome product enables the overall privacy analysis.
Relation to prior work and FriendlyCore
The propose-filter-release framework generalizes propose-test-release (PTR), which first proposes a function, tests it for sensitivity, and then releases the result. PTR relies on a test that must itself be private; PFR replaces the test with a private filtering step that requires only a concave friendliness score and a friendly-DP release mechanism. This makes PFR applicable to a broader range of settings where a test is not available or is too coarse.
FriendlyCore, a prior work on core sets for differential privacy, can be viewed as one implementation of the PFR framework. FriendlyCore identifies a subset of records that preserves the statistical properties of the full dataset, and the PFR framework provides the general privacy analysis that underlies that construction. The friendship of a record in FriendlyCore corresponds to the friendliness score in PFR, and the release mechanism in FriendlyCore corresponds to the friendly-DP release.
Limitations and trade-offs
The friendliness score must be concave, which restricts the class of scores that can be used. Not all natural measures of fit are concave, and designing a suitable score may require effort. The threshold for filtering is public, which means an adversary knows which records were removed; this may be a concern in settings where the very fact of removal leaks information. Additionally, the public condition on the number of records n may limit applicability in very small datasets, though the condition is typically satisfied in machine learning workloads.
The framework also assumes the release mechanism is friendly-DP, which is a non-trivial design requirement. Not every existing private mechanism satisfies this property, and adapting a mechanism to be friendly-DP may require modifications.
Practical implications
For practitioners, PFR offers a way to obtain tighter privacy budgets when the data contain outlying records. By privately filtering before release, the noise scale can be reduced without sacrificing the standard differential privacy guarantee. The framework is modular: any concave friendliness score and any friendly-DP release mechanism can be combined, which means existing work on either component can be leveraged.
The instantiations demonstrate that PFR is not a niche technique; it applies to statistics, subspace estimation, divergence estimation, graph analysis, and policy selection. Each instantiation follows the same pattern: define a concave friendliness score, ensure the release mechanism is friendly-DP, and apply the filtering step. The resulting mechanism satisfies differential privacy on every input while adding noise proportional to the typical sensitivity of the data.
Future work could explore automatic methods for designing friendliness scores for new domains, or extending the framework to other privacy notions such as local differential privacy or Rényi differential privacy. The connection to FriendlyCore suggests that core-set constructions can be framed within the PFR paradigm, opening a path for further integration.