Technical Summary: Differentially Private Nonparametric Modal Learning with Applications to Regression and Clustering

Problem Statement

The estimation of density modes—local maximizers of a probability density function—is a fundamental problem in statistics, offering localized and interpretable summaries of complex, multimodal distributions. Unlike global summaries (e.g., mean or median), modes reveal heterogeneous sub-populations and are critical in applications ranging from clustering and classification to computer vision and nonparametric regression. However, recovering modes is inherently non-regular; small perturbations in density can create or destroy critical points, making estimation sensitive to local smoothness, curvature, and separation.

While significant research exists on differentially private (DP) methods for means, regression, and clustering, private mode estimation remains largely unexplored. Existing approaches, such as the nearest-neighbor based method by Pacchiano et al. (2021), are limited to single-mode settings or lack smoothness-dependent optimality guarantees. This paper addresses the challenge of recovering multiple density modes from sensitive data while providing rigorous $(\varepsilon, \delta)$-differential privacy guarantees.

Methodology: DP-GRAMS

The authors propose DP-GRAMS (Differentially Private GRadient Ascent for Mode Seeking), a multi-stage algorithm that adapts the classical mean-shift procedure to a differentially private setting. The method leverages the equivalence between mean shift and gradient ascent on the log-density (score function).

1. Stabilized Score Estimation

To ensure privacy, the algorithm does not operate directly on the raw log-density gradient $\nabla \log \hat{p}(x)$, which can be highly sensitive to extreme observations. Instead, it employs a stabilized score estimator:
$$\hat{s}_{A, p_{floor}}(x) = \frac{\text{clip}_A(\nabla \hat{p}(x))}{\max\{\hat{p}(x), p_{floor}\}}$$
where $\hat{p}(x)$ is a Kernel Density Estimator (KDE). The numerator is clipped to a level $A$ to bound sensitivity, and the denominator is floored at $p_{floor}$ to prevent division by near-zero values.

2. Three-Stage Pipeline

The algorithm proceeds in three distinct phases:

• Density-Aware Private (DAP) Initialization:
  Finding modes requires good initialization. The authors introduce a DAP scheme that samples initial points from a public grid. It uses the exponential mechanism with a utility function based on local empirical mass (approximating local density). Crucially, it employs a local suppression rule: after selecting an anchor, all grid points within a radius $\rho_{init}$ are removed from the candidate set. This ensures diverse coverage of high-density regions (modal basins) without repeatedly selecting the same neighborhood, achieving high-probability coverage of all true modes with $k \asymp M \log n$ draws.

• Correlated Noisy Gradient Ascent:
  From each initialization, the algorithm performs stochastic gradient ascent on the stabilized score estimator. To satisfy privacy:

  • Gradient Clipping: The score contributions are clipped.
  • Correlated Noise: Since multiple trajectories start from different points but may converge to the same mode, adding independent noise to each trajectory would incur a prohibitive privacy cost. Instead, DP-GRAMS adds correlated Gaussian noise at each iteration. The correlation structure is induced by an exponential kernel based on the spatial proximity of the current iterates. This allows the joint release of multiple trajectories under a single privacy budget.

• Merging:
  The final step merges nearby candidate modes produced by the ascent trajectories. If the number of modes is unknown, a radius-based merge is used; if known, Ward-linkage agglomerative clustering is applied. This post-processing step is deterministic and does not consume additional privacy budget.

3. Extensions

The framework is extended to two downstream tasks:

• DP-PMS: A private modal regression method that updates in the response direction to estimate conditional modes.
• DP-GRAMS-C: A clustering pipeline that releases private modal centers and assigns data points deterministically.

Theoretical Contributions

The paper establishes rigorous statistical and privacy guarantees under the assumption that the true density belongs locally to a Hölder class with smoothness parameter $\beta > 2$.

Privacy Guarantees

The complete DP-GRAMS pipeline satisfies $(\varepsilon, \delta)$-differential privacy. The privacy budget is split between the initialization ($\varepsilon_{init}$) and the ascent stages ($\varepsilon_{modes}$). The use of the exponential mechanism for initialization and the correlated Gaussian mechanism for ascent ensures that the privacy cost scales efficiently with the number of modes and iterations.

Error Rates and Optimality

The authors derive upper bounds on the mean squared error (MSE) for the estimated modes. The error rate takes the form:
$$O\left( \left(\frac{\log n}{n}\right)^{\frac{2(\beta-1)}{d+2\beta}} \right) + O\left( \left(\frac{\text{polylog}(n, \delta)}{n^2 \varepsilon^2}\right)^{\frac{\beta-1}{d+\beta}} \right)$$

• The first term represents the non-private statistical error, matching known minimax rates for mode estimation (e.g., Tsybakov, 1990).
• The second term captures the degradation due to privacy constraints.

Furthermore, the paper derives minimax lower bounds for private mode estimation, showing that the proposed estimators are nearly minimax optimal, up to logarithmic factors in the MSE. This is a significant result, as it demonstrates that the privacy cost does not fundamentally alter the convergence rate's dependence on sample size $n$ and dimension $d$, provided the density is sufficiently smooth.

Experimental Results

Extensive experiments on synthetic and real-world datasets validate the theoretical findings:

• Synthetic Data: On bivariate Gaussian mixtures and heavy-tailed $t$-mixtures, DP-GRAMS successfully recovers multiple modes. The privacy-utility trade-off curves show that the method performs competitively with non-private mean shift, especially as sample size $n$ and privacy budget $\varepsilon$ increase.
• Modal Regression: On sinusoidal and piecewise-constant mixture data, the private modal regression (DP-PMS) successfully tracks multimodal conditional structures that mean-based methods (like LOWESS) fail to capture.
• Clustering: On the MNIST and Cancer RNA-Seq datasets, DP-GRAMS-C demonstrates superior performance in Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI) compared to differentially private $k$-means (DP-k-Means), particularly at moderate privacy budgets. The method effectively preserves cluster geometry in high-dimensional reduced spaces.

Significance and Claims

The paper claims to provide the first comprehensive framework for differentially private nonparametric mode estimation that:

1. Handles Multiple Modes: Unlike prior work focused on single modes or nearest-neighbor approaches, this method is designed to recover a set of separated modes.
2. Achieves Near-Optimality: By utilizing higher-order kernels and leveraging smoothness ($\beta > 2$), the method achieves error rates that are nearly minimax optimal, overcoming the limitations of nearest-neighbor estimators which cannot exploit higher-order smoothness.
3. Practical Privacy Mechanisms: The introduction of the DAP initialization and correlated noise mechanisms offers a practical solution to the tension between the need for granular data distribution (to find modes) and the requirement to protect individual data points.
4. Downstream Utility: The framework naturally extends to modal regression and clustering, providing a unified approach for nonparametric tasks under privacy constraints.

The authors conclude that while the problem of private mode estimation is challenging due to the non-regular nature of critical points, the proposed DP-GRAMS algorithm offers a statistically sound and practically implementable solution with favorable privacy-utility trade-offs.