Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming
This work addresses privacy concerns in optimization for applications like machine learning and operations research, offering a foundational extension of differential privacy to symmetric cone programming.
The paper tackles the problem of designing differentially private mechanisms for functions with outputs in Euclidean Jordan algebras, which underpin key optimization problems like semidefinite programming, by introducing a generic Gaussian mechanism and deriving private algorithms for symmetric cone programs. It resolves an open question from 2014 by providing differentially private algorithms for semidefinite programming.
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 $\ell_2$, $\ell_1$, and $\ell_\infty$ 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].