Differentially Private Nonparametric Modal Learning with Applications to Regression and Clustering

Overview§

This paper tackles the problem of estimating density modes (local maxima) under differential privacy (DP). Modes are a natural summary for multimodal distributions, but their estimation in the private setting is largely unstudied. The authors propose DP-GRAMS, a mean-shift style algorithm that performs noisy gradient ascent on a privately estimated score function. The key contributions include: (1) a bias-reducing score estimator using higher-order kernels (for Hölder smooth densities with $\beta > 2$), (2) gradient clipping + Gaussian noise for privacy, (3) a private initialization scheme that covers modal basins via a density-aware grid and suppression, and (4) minimax lower bounds showing near-optimality.

Problem Setup and Score Estimation§

Given $n$ i.i.d. samples from a density $f$ on $\mathbb{R}^d$, the goal is to recover all local maxima (modes) of $f$ under $\varepsilon$ (or $(\varepsilon, \delta)$) differential privacy. The population mode satisfies $\nabla f = 0$ and $\nabla^2 f \prec 0$. The mean-shift update uses the score function $s(x) = \nabla \log f(x) = \nabla f(x)/f(x)$. The authors estimate $s(x)$ via kernel density derivative estimators.

To achieve better bias for $\beta > 2$, they use higher-order kernels $K$ of order $\kappa$ such that $\int K(u) du = 1$, and moments up to order $\kappa - 1$ vanish. This leads to a score estimator with bias $O(h^\beta)$ and variance $O(1/(n h^{d+2}))$ (roughly). The private score estimator is obtained by clipping the (approximate) score contributions and adding Gaussian noise to the aggregated gradient:

$$ \hat{s}_{\text{priv}}(x) = \frac{1}{n} \sum_i \text{clip}_C\left( \nabla K_h(x - X_i) \right) + \mathcal{N}\left(0, \sigma^2 I_d\right), $$

where clipping enforces bounded sensitivity and $\sigma^2$ is set according to the Gaussian mechanism.

DP-GRAMS Algorithm§

The algorithm proceeds in two stages:

1. Private initialization: A density-aware utility function is evaluated on a public grid of size $h_{\mathrm{DAP}}$. A suppression radius $\rho_{\mathrm{init}} \asymp (\log n)^{-1/d}$ is used to ensure that selected starting points cover distinct modal basins. The grid has $k \asymp M \log n$ starts, and the selection step uses the exponential mechanism to choose points that are both likely near modes and separated. Correlated noise across multiple starts enables simultaneous release under a single $(\varepsilon, \delta)$ budget.

1. Private mean-shift ascent: From each starting point, the algorithm iteratively updates

$$ x^{(t+1)} = x^{(t)} + \eta \cdot \hat{s}_{\text{priv}}(x^{(t)}), $$

with step size $\eta > 0$, clip threshold $C$, and added Gaussian noise. The number of iterations per start is limited to $T = O(\log n)$ to control accumulated privacy loss via the composition theorem.

Theory and Optimality§

The main result states that, with high probability, all population modes are recovered, and the estimation error for each mode is

$$ O\left(\left(\frac{\log n}{n}\right)^{\frac{2(\beta-1)}{d+2\beta}}\right) + O\left(\left(\frac{\operatorname{polylog}(n,\delta)}{n^2 \varepsilon^2}\right)^{\frac{\beta-1}{d+\beta}}\right). $$

The first term matches the non-private minimax rate for mode estimation under Hölder smoothness. The second term is the privacy cost. The authors prove minimax lower bounds for private mode estimation, showing that DP-GRAMS is optimal up to logarithmic factors in mean squared error.

Extensions§

• DP-PMS: private modal regression, where conditional density modes are estimated as functions of the covariate.
• DP-GRAMS-C: a clustering pipeline that assigns points to recovered modes using a private thresholding rule, achieving cluster centers with distortion guarantees.

Illustrative PyTorch Snippet§

The following code sketches the privatized score ascent used in DP-GRAMS. In practice, kernels are evaluated in batch and the privacy accountant is integrated.

import torch

def private_score_estimator(X, x, h, C, sigma, beta=4):
    """
    X: (n, d) data tensor
    x: (d,) current point
    h: bandwidth
    C: clip bound
    sigma: noise std
    beta: order of the kernel (must be even)
    """
    n = X.shape[0]
    # Higher-order kernel: combination of Gaussian derivatives. For beta=4:
    coeffs = torch.tensor([0.5, -0.5], dtype=x.dtype)  # example coefficients
    diff = (X - x) / h
    # Compute kernel weighting: sum_j coeff_j * (-1)^j * d^j/dx^j Gaussian(diff)
    # Simplified: use Gaussian derivative of order 2 and 4
    gauss = torch.exp(-0.5 * diff.pow(2).sum(dim=1))
    # Approximate derivative kernel: diff * gauss for beta=2; for beta=4 use (diff^3 - 3 diff)*gauss
    kernel_deriv = (diff.pow(3) - 3 * diff) * gauss  # d/dx of 4th-order kernel
    # Clip per-sample contributions to L2 norm C
    clipped = kernel_deriv / torch.clamp(kernel_deriv.norm(dim=1, keepdim=True), min=C) * C
    score = clipped.mean(dim=0) / h
    # Add Gaussian noise for DP
    score += torch.randn_like(score) * sigma
    return score

def dp_grams(X, starts, h, C, sigma, eta, T):
    modes = []
    for start in starts:
        x = start.clone()
        for _ in range(T):
            score = private_score_estimator(X, x, h, C, sigma)
            x = x + eta * score
        modes.append(x)
    return torch.stack(modes)

Conclusion§

DP-GRAMS is a principled, privacy-preserving approach to multivariate mode estimation with strong theoretical guarantees. Its separation of initialization and ascent, combined with careful kernel design and noise calibration, yields practical algorithms for regression and clustering under DP.