Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
We give the first polynomial-time, differentially node-private, and robust algorithm for estimating the edge density of Erd\H{o}s-R\'enyi random graphs and their generalization, inhomogeneous random graphs. We further prove information-theoretical lower bounds, showing that the error rate of our algorithm is optimal up to logarithmic factors. Previous algorithms incur either exponential running time or suboptimal error rates. Two key ingredients of our algorithm are (1) a new sum-of-squares algorithm for robust edge density estimation, and (2) the reduction from privacy to robustness based on sum-of-squares exponential mechanisms due to Hopkins et al. (STOC 2023).
Code (0)
등록된 구현이 없습니다.
Tasks
Density EstimationSimilar Papers 제목 키워드 기반
Fast Private Kernel Density Estimation via Locality Sensitive Quantization
We study efficient mechanisms for differentially private kernel density estimation (DP-KDE). Prior work for the Gaussian kernel described algorithms that run in time exponential in the number of dimensions $d$. This pape…
Density EstimationQuantizationUniversal Approximation of Edge Density in Large Graphs
In this paper, we present a novel way to summarize the structure of large graphs, based on non-parametric estimation of edge density in directed multigraphs. Following coclustering approach, we use a clustering of the ve…
ClusteringDensity EstimationModel SelectionvalidAgnostic Private Density Estimation for GMMs via List Global Stability
We consider the problem of private density estimation for mixtures of unrestricted high dimensional Gaussians in the agnostic setting. We prove the first upper bound on the sample complexity of this problem. Previously, …
Density EstimationA One-Pass Private Sketch for Most Machine Learning Tasks
Differential privacy (DP) is a compelling privacy definition that explains the privacy-utility tradeoff via formal, provable guarantees. Inspired by recent progress toward general-purpose data release algorithms, we prop…
BIG-bench Machine LearningDensity EstimationScalable Mutual Information Estimation using Dependence Graphs
The Mutual Information (MI) is an often used measure of dependency between two random variables utilized in information theory, statistics and machine learning. Recently several MI estimators have been proposed that can …
Information PlaneMutual Information Estimation