Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming
Organizations: University of California, Berkeley. · New York University. · Massachusetts Institute of Technology.
Abstract
In this paper, we study differentially private mechanisms for functions whose outputs lie in a Euclidean Jordan algebra. Euclidean Jordan algebras capture many important mathematical structures and form the foundation of linear programming, second-order cone programming, and semidefinite programming. Our main contribution is a generic Gaussian mechanism for such functions, with sensitivity measured in , , and norms. Notably, this framework includes the important case where the function outputs are symmetric matrices, and sensitivity is measured in the Frobenius, nuclear, or spectral norm. We further derive private algorithms for solving symmetric cone programs under various settings, using a combination of the multiplicative weights update method and our generic Gaussian mechanism. As an application, we present differentially private algorithms for semidefinite programming, resolving a major open question posed by [Hsu, Roth, Roughgarden, and Ullman, ICALP 2014].
Figures & tables
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Algebra | Rank | Peirce constant | |
| real symmetric matrices | 1 | ||
| complex Hermitian matrices | 2 | ||
| quaternionic Hermitian matrices | 4 | ||
| spin factor , | 2 | ||
| Albert algebra | 3 | 8 | 17 |
Differential Privacy
Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.
See all 309 papers