Private graphon estimation via sum-of-squares
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913320724856832 |
|---|---|
| author | Chen, Hongjie Ding, Jingqiu d'Orsi, Tommaso Hua, Yiding Liu, Chih-Hung Steurer, David |
| author_facet | Chen, Hongjie Ding, Jingqiu d'Orsi, Tommaso Hua, Yiding Liu, Chih-Hung Steurer, David |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12213 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Private graphon estimation via sum-of-squares Chen, Hongjie Ding, Jingqiu d'Orsi, Tommaso Hua, Yiding Liu, Chih-Hung Steurer, David Data Structures and Algorithms Computational Complexity Machine Learning 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. |
| title | Private graphon estimation via sum-of-squares |
| topic | Data Structures and Algorithms Computational Complexity Machine Learning |
| url | https://arxiv.org/abs/2403.12213 |