Private Matrix Approximation and Geometry of Unitary Orbits

Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Thakurta, Nisheeth K. Vishnoi
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3547-3588, 2022.

Abstract

Consider the following optimization problem: Given $n \times n$ matrices $A$ and $\Lambda$, maximize $⟨A, U\Lambda U^*⟩$ where $U$ varies over the unitary group $\mathrm{U}(n)$. This problem seeks to approximate $A$ by a matrix whose spectrum is the same as $\Lambda$ and, by setting $\Lambda$ to be appropriate diagonal matrices, one can recover matrix approximation problems such as PCA and rank-$k$ approximation. We study the problem of designing differentially private algorithms for this optimization problem in settings where the matrix $A$ is constructed using users’ private data. We give efficient and private algorithms that come with upper and lower bounds on the approximation error. Our results unify and improve upon several prior works on private matrix approximation problems. They rely on extensions of packing/covering number bounds for Grassmannians to unitary orbits which should be of independent interest.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-mangoubi22a, title = {Private Matrix Approximation and Geometry of Unitary Orbits}, author = {Mangoubi, Oren and Wu, Yikai and Kale, Satyen and Thakurta, Abhradeep and Vishnoi, Nisheeth K.}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {3547--3588}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/mangoubi22a/mangoubi22a.pdf}, url = {https://proceedings.mlr.press/v178/mangoubi22a.html}, abstract = {Consider the following optimization problem: Given $n \times n$ matrices $A$ and $\Lambda$, maximize $⟨A, U\Lambda U^*⟩$ where $U$ varies over the unitary group $\mathrm{U}(n)$. This problem seeks to approximate $A$ by a matrix whose spectrum is the same as $\Lambda$ and, by setting $\Lambda$ to be appropriate diagonal matrices, one can recover matrix approximation problems such as PCA and rank-$k$ approximation. We study the problem of designing differentially private algorithms for this optimization problem in settings where the matrix $A$ is constructed using users’ private data. We give efficient and private algorithms that come with upper and lower bounds on the approximation error. Our results unify and improve upon several prior works on private matrix approximation problems. They rely on extensions of packing/covering number bounds for Grassmannians to unitary orbits which should be of independent interest.} }
Endnote
%0 Conference Paper %T Private Matrix Approximation and Geometry of Unitary Orbits %A Oren Mangoubi %A Yikai Wu %A Satyen Kale %A Abhradeep Thakurta %A Nisheeth K. Vishnoi %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-mangoubi22a %I PMLR %P 3547--3588 %U https://proceedings.mlr.press/v178/mangoubi22a.html %V 178 %X Consider the following optimization problem: Given $n \times n$ matrices $A$ and $\Lambda$, maximize $⟨A, U\Lambda U^*⟩$ where $U$ varies over the unitary group $\mathrm{U}(n)$. This problem seeks to approximate $A$ by a matrix whose spectrum is the same as $\Lambda$ and, by setting $\Lambda$ to be appropriate diagonal matrices, one can recover matrix approximation problems such as PCA and rank-$k$ approximation. We study the problem of designing differentially private algorithms for this optimization problem in settings where the matrix $A$ is constructed using users’ private data. We give efficient and private algorithms that come with upper and lower bounds on the approximation error. Our results unify and improve upon several prior works on private matrix approximation problems. They rely on extensions of packing/covering number bounds for Grassmannians to unitary orbits which should be of independent interest.
APA
Mangoubi, O., Wu, Y., Kale, S., Thakurta, A. & Vishnoi, N.K.. (2022). Private Matrix Approximation and Geometry of Unitary Orbits. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:3547-3588 Available from https://proceedings.mlr.press/v178/mangoubi22a.html.

Related Material