Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private Filtering

Core Methodology§

Differentially private (DP) mechanisms often use noise scaled to the worst-case influence of a single record, which can be unnecessarily large when most data are typical. Propose-Filter-Release (PFR) addresses this by privately filtering out atypical records, then applying a release mechanism that is DP only when the changed record is typical (friendly-DP). The key innovation is a private filtering step that identifies a subset of records that are "friendly" (i.e., fit the data well) without leaking information about individual records.

Formally, let $D$ be a dataset and $f$ a concave friendliness score measuring how well a record $x$ fits $D$. PFR consists of three steps:

1. Propose: Generate a candidate threshold $\tau$ for the friendliness score using a DP mechanism.
2. Filter: Partition $D$ into $D_{\text{friendly}} = \{x \in D : f(x, D) \geq \tau\}$ and the rest. This step must be private.
3. Release: Apply a friendly-DP mechanism $M$ to $D_{\text{friendly}}$.

The filtering step is made private via a novel technique that adds noise to the score evaluations and uses a sparse vector technique to select the threshold. The friendliness score must be concave, which ensures that the filtering step is stable under small changes to the dataset.

Theoretical Guarantees§

For any concave friendliness score $f$ and any friendly-DP mechanism $M$, PFR guarantees $(\epsilon, \delta)$-DP under public conditions on the number of records. Specifically, if the number of records $n$ exceeds a public threshold $n_0$, then PFR is DP. This makes PFR a general privacy primitive comparable to propose-test-release (PTR). In fact, FriendlyCore can be viewed as an implementation of PFR.

Implementation Details§

The private filtering step uses a DP selection algorithm to choose a threshold $\tau$ such that the number of friendly records is sufficiently large. A common approach is to use the exponential mechanism or the sparse vector technique. The release mechanism $M$ can be any mechanism that satisfies friendly-DP, meaning it is DP when the changed record is friendly. For example, for scalar statistics, $M$ could be the Laplace mechanism with noise scaled to the sensitivity over friendly records.

Example: Scalar Mean Estimation§

Consider estimating the mean of a scalar dataset. The friendliness score can be defined as $f(x, D) = -|x - \text{median}(D)|$. PFR would:

1. Propose a threshold $\tau$ (e.g., using the exponential mechanism).
2. Filter records with $f(x, D) \geq \tau$.
3. Release the mean of filtered records with Laplace noise scaled to the sensitivity of the mean over friendly records (which is smaller than the worst-case sensitivity).

Code Snippet§

Below is a simplified Python implementation of PFR for scalar mean estimation.

import numpy as np

def friendliness_score(x, D):
    # Concave score: negative distance to median
    return -np.abs(x - np.median(D))

def private_filter(D, epsilon_filter, tau_candidates):
    # Exponential mechanism to select threshold tau
    scores = [np.sum(friendliness_score(x, D) >= tau) for tau in tau_candidates]
    scores = np.array(scores, dtype=float)
    sensitivities = 1.0  # each record can change count by at most 1
    probabilities = np.exp(epsilon_filter * scores / (2 * sensitivities))
    probabilities /= probabilities.sum()
    return np.random.choice(tau_candidates, p=probabilities)

def pfr_mean(D, epsilon, delta, tau_candidates):
    # Split epsilon budget: half for filtering, half for release
    eps_filter = epsilon / 2
    eps_release = epsilon / 2
    
    tau = private_filter(D, eps_filter, tau_candidates)
    friendly = [x for x in D if friendliness_score(x, D) >= tau]
    
    if len(friendly) == 0:
        return 0.0  # fallback
    
    # Sensitivity of mean over friendly records:
    # each record in [min, max], so sensitivity = (max - min) / len(friendly)
    sensitivity = (max(friendly) - min(friendly)) / len(friendly)
    noise = np.random.laplace(0, sensitivity / eps_release)
    return np.mean(friendly) + noise

Applications§

PFR is illustrated for:

• Scalar statistics: mean, median.
• Principal subspace estimation: PCA with DP.
• KL divergence of user histograms: comparing distributions.
• Effective resistances of a graph: graph analysis.
• Treatment-rule selection: causal inference.

By filtering out atypical records, PFR achieves smaller noise scales and better utility while maintaining rigorous DP guarantees.