Near-optimal node-private community estimation in polynomial-time

• URL: http://arxiv.org/abs/2607.09441v1
• Date: Fri, 10 Jul 2026 14:12:03 GMT
• Title: Near-optimal node-private community estimation in polynomial-time
• Abstract summary: We provide a high-probability, node-private algorithm which nearly matches Klopp & Zadik's exponential-time node-private algorithm for exact recovery in block models.<n>We rigorously analyze the privacy, runtime, and utility of our proposed algorithm, showing that even when the number of communities Kilon grows logarithmically with the number of nodes n, we can achieve the minimax rates for exact recovery with the privacy parameter eps growing as log(n)
• Score: 9.8953002257286
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we resolve an open question of Klopp & Zadik (2026) by providing a high-probability polynomial-time, node-private algorithm which nearly matches the performance of their exponential-time node-private algorithm for exact recovery in stochastic block models. Our result involves an explicitly constructed Lipschitz surrogate for the penalized likelihood function, as well as a carefully devised accept-reject algorithm that samples community labels from the corresponding exponential mechanism in polynomial-time. We rigorously analyze the privacy, runtime, and utility of our proposed algorithm, showing that even when the number of communities K grows logarithmically with the number of nodes n, we can achieve the minimax rates for exact recovery with the privacy parameter epsilon growing as log(n), thus matching known lower bounds on the cost of privacy for this setting.

Related papers

• Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds [4.001518483170137]
  We study the classical problem of community recovery in block models with a fixed number of communities.<n>We seek algorithms that are stable with respect to node-wise changes in the graph structure, formally defined as a differential privacy constraint.
  arXiv  Detail & Related papers  (2026-05-15T13:27:24Z)
• Sample-Optimal Private Regression in Polynomial Time [3.3748750222488657]
  We show that any improvement to the sample complexity of our algorithm would violate either statistical-query or information-theoretic lower bounds.<n>Our algorithm is robust to a small fraction of arbitrary outliers and achieves optimal error rates as a function of the fraction of outliers.
  arXiv  Detail & Related papers  (2025-03-31T17:08:12Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications.<n>Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility.<n>We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust [5.037313459134419]
  We give the first-time, differentially node-private, and robust algorithm for estimating the edge density of ErdHos-R'enyi random graphs. We prove information-theoretical lower bounds, showing that the error rate of our algorithm is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2024-05-26T18:59:44Z)
• Private graphon estimation via sum-of-squares [10.00024942014117]
  We develop the first pure node-differentially private algorithms for learning block models and for graphon estimation with constant running time for any number of blocks. The statistical utility guarantees match those of the previous best information-theoretic (expon-time) node-private mechanisms for these problems.
  arXiv  Detail & Related papers  (2024-03-18T19:54:59Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
  This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP) We present confidence intervals (CI) and time-uniform confidence sequences (CS) for $mustar$ when only given access to the privatized data.
  arXiv  Detail & Related papers  (2022-02-17T16:04:49Z)
• No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
  We consider the ubiquitous problem of gaussian process (GP) bandit optimization from the lens of privacy-preserving statistics. We propose a solution for differentially private GP bandit optimization that combines a uniform kernel approximator with random perturbations. Our algorithms maintain differential privacy throughout the optimization procedure and critically do not rely explicitly on the sample path for prediction.
  arXiv  Detail & Related papers  (2021-02-24T18:52:24Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)

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.