4
[2403.12213] Private graphon estimation via sum-of-squares
source link: https://arxiv.org/abs/2403.12213
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 18 Mar 2024]
Private graphon estimation via sum-of-squares
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 mechanism 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 optimization over arbitrary polytopes, and (3) a general approach to perform Lipschitz extensions of score functions as part of the sum-of-squares algorithmic paradigm.
| Comments: | 70 pages, accepted to STOC 2024 |
| Subjects: | Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2403.12213 [cs.DS] |
| (or arXiv:2403.12213v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2403.12213 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK