Differentially Private Nonparametric Modal Learning with Applications to Regression and Clustering

• URL: http://arxiv.org/abs/2607.29675v1
• Date: Fri, 31 Jul 2026 17:55:02 GMT
• Title: Differentially Private Nonparametric Modal Learning with Applications to Regression and Clustering
• Abstract summary: DP-GRAMS is a mean-shift inspired method that performs noisy ascent on a differentially private score estimator.<n>We prove that all population modes are recovered with high probability and establish error rates of the form $O!left(tfraclog nn)frac2,-1)d+2right.<n>We present two natural extensions: DP-PMS, a private modal-regression method, and DP-GRAMS-C, a clustering pipeline.
• Score: 2.685668802278155
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Density modes provide a localized and interpretable summary of multimodal distributions, but their estimation under rigorous differential privacy constraints remains largely unexplored. We study differentially private recovery of density modes for multivariate distributions under local smoothness, curvature, and separation conditions. We propose DP-GRAMS, a mean-shift inspired method that performs noisy ascent on a differentially private score estimator. Assuming the density belongs locally to a Hölder class with smoothness parameter $β> 2$, our score estimator uses bias-reducing higher-order kernels, and then enforces privacy in the gradient ascent steps via gradient clipping and calibrated Gaussian noise. A private initialization scheme combines a density-aware utility with a suppression rule and, with $k\asymp M\log n$ draws over a public $h_{\mathrm{DAP}}$-grid and suppression radius $ρ_{\mathrm{init}}\asymp (\log n)^{-1/d}$, achieves high-probability coverage of the modal basins by successively suppressing selected local neighborhoods in competitive regions, while correlated noise across multiple starts enables joint release under a single $(\varepsilon,δ)$-differential privacy guarantee. We prove that all population modes are recovered with high probability and establish asymptotic error rates of the form $O\!\left((\tfrac{\log n}{n})^{\frac{2(β-1)}{d+2β}}\right) + O\!\left((\tfrac{\mathrm{polylog}(n,δ)}{n^2\varepsilon^2})^{\frac{β-1}{d+β}}\right)$. We also provide minimax lower bounds for private mode estimation, and show that our estimators are nearly optimal, up to a logarithmic factor in the MSE. We present two natural extensions: DP-PMS, a private modal-regression method, and DP-GRAMS-C, a clustering pipeline. Extensive experiments on synthetic and real data demonstrate favorable privacy-utility trade-offs relative to common baselines.

Related papers

• Faster Learning under Relaxed Local Differential Privacy [1.1470070927586014]
  We show that adding independent noise with a convenient symmetrized Gamma distribution attains the $$-TV-LDP.<n>We illustrate the benefits of this simple privacy mechanism by implementing a neural network estimator.
  arXiv  Detail & Related papers  (2026-09-04T11:55:35Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD [7.787109481104569]
  We analyze Differentially Private Gradient Descent (DP-SGD) in the $f$differential privacy framework.<n>We prove that enforcing a small separation imposes a strict lower bound on the noise multiplier $$, which directly limits the achievable utility.<n>Our experiments confirm that the noise levels implied by this bound leads to significant accuracy degradation at realistic training settings.
  arXiv  Detail & Related papers  (2026-01-15T09:50:36Z)
• Optimal Best Arm Identification under Differential Privacy [8.321992395325912]
  Best Arm Identification (BAI) algorithms are deployed in data-sensitive applications, such as adaptive clinical trials or user studies.<n>We study the problem of fixed-confidence BAI under global Differential Privacy (DP) for Bernoulli distributions.<n>Our algorithm outperforms existing $delta$correct and $epsilon$-global DP BAI algorithms for different values of $epsilon$.
  arXiv  Detail & Related papers  (2025-10-20T09:46:09Z)
• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  Federated learning enables machine learning models with privacy of participants.<n>There is no differentially private distributed method for training, non-feedback problems.<n>We introduce a new distributed algorithm $alpha$-$sf NormEC$ with provable convergence guarantees.
  arXiv  Detail & Related papers  (2025-02-19T07:10:32Z)
• Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
  Under privacy constraints, the complexity of private linear regression is emphnot captured by the usual covariance matrix.<n>We introduce an Information-Weighted Regression method that attains the optimal rates.<n> Notably, our results demonstrate that joint privacy comes at almost no additional cost.
  arXiv  Detail & Related papers  (2025-02-18T18:35:24Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  We study person-level differentially private mean estimation in the case where each person holds multiple samples. We give computationally efficient algorithms under approximate-DP and computationally inefficient algorithms under pure DP, and our nearly matching lower bounds hold for the most permissive case of approximate DP.
  arXiv  Detail & Related papers  (2024-05-30T18:20:35Z)
• PrivSGP-VR: Differentially Private Variance-Reduced Stochastic Gradient Push with Tight Utility Bounds [9.47030623916154]
  We propose a differentially private decentralized learning method (termed PrivSGPVR) which employs gradient push with variance reduction and guarantees privacy for each node. Our theoretical analysis shows that, under DP noise with constant variance, PrivGPS-VR achieves a sub-linear convergence rate of $mathcalO (1/sqrtnK)$.
  arXiv  Detail & Related papers  (2024-05-04T11:22:53Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
  We show that noisy gradient descent (SGD) algorithms attain the optimal excess risk in low-dimensional regimes. Our work draws upon concepts from the geometry of normed spaces, such as the notions of regularity, uniform convexity, and uniform smoothness.
  arXiv  Detail & Related papers  (2021-03-01T19:48:44Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.