Private Graphon Estimation via Sum-of-Squares
METADATA ONLY
Loading...
Author / Producer
Date
2024-06
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We develop the first pure node-differentially-private algorithms for learning stochastic block models and for graphon estimation with polynomial running time for any constant number of blocks. The statistical utility guarantees match those of the previous best information-theoretic (exponential-time) node-private mechanisms for these problems. The algorithm is based on an exponential mech- anism for a score function defined in terms of a sum-of-squares relaxation whose level depends on the number of blocks. The key ingredients of our results are (1) a characterization of the distance between the block graphons in terms of a quadratic optimization over the polytope of doubly stochastic matrices, (2) a general sum-of-squares convergence result for polynomial op- timization over arbitrary polytopes, and (3) a general approach to perform Lipschitz extensions of score functions as part of the sum-of-squares algorithmic paradigm.
Permanent link
Publication status
published
External links
Editor
Book title
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing
Journal / series
Volume
Pages / Article No.
172 - 182
Publisher
Association for Computing Machinery
Event
56th Annual ACM Symposium on Theory of Computing (STOC 2024)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
graphon estimation; differential privacy; sum-of-squares hierarchy
Organisational unit
09622 - Steurer, David / Steurer, David
Notes
Conference lecture held on June 24, 2024.
Funding
815464 - Unified Theory of Efficient Optimization and Estimation (EC)