Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming

We appreciate your valuable comments. We are happy to address your concerns and questions.

Q: Many readers know SDP but not EJA; it would be better if the authors could explain the technical results using examples from Euclidean space.
A: We agree and will include examples in terms of real symmetric matrices and semidefinite programming (SDP) when explaining the technical results in the revision.

Q: Could the Gaussian mechanism be adapted for DP algorithms that currently rely on SDP? What are some future works that could benefit from the results developed in this paper?
A: We believe our Gaussian mechanism and SDP framework is general enough to address problems that can be “privatized” via solving an SDP privately. For example, robust mean estimation [CDG19] and robust covariance estimation [CDGW19] both require solving a positive SDP; our results can already provide private solutions to these programs, achieving roughly $r/\epsilon$ violated constraints, where the constraint matrix has size $r \times r$ with $r = N + d$ ($N$ is the sample size and $d$ is the dimension), and $\epsilon$ is the privacy parameter. For future work, we see two main directions: (1) improving the generic Gaussian mechanism to match the Laplace mechanism for $\ell_1$ norm, or proving that the Gaussian mechanism is in fact optimal in the EJA setting; (2) applying our private SCP solvers to more problems, such as support vector machines (SVM), which can be formulated as a quadratic program, or matrix completion, which admits a natural SDP convex relaxation.

Q: The high-sensitivity solvers rely on an oracle to an exponential size $\gamma$-net. Could this be replaced by some random sampling or sketching?
A: This is a very interesting question. We believe it is possible to replace the explicit net by the following sampling procedure: for SDP, recall that we require an oracle to the net of the ball $B = \\{u \in \mathbb{R}^r : \\|u\\|\_2^2 \leq {\rm OPT}\\}$. Without loss of generality, assume ${\rm OPT}=1$; then, one can generate a random $u \in B$ by first sampling from a spherical Gaussian and then randomly choosing a radius. Finally, to obtain a point on the net, we could round the sampled point to the nearest point on the net.

References

[CDG19] Chen, Diakonikolas, and Ge. High-dimensional robust mean estimation in nearly-linear time. SODA, 2019.
[CDGW19] Chen, Diakonikolas, Ge, and Woodruff. Faster algorithms for high-dimensional robust covariance estimation. COLT, 2019.

We appreciate your insightful and encouraging comments. We are more than happy to address your concerns and answer your questions. In particular, we thank you for highlighting that the use of Jordan algebras provides conceptual clarity, as it offers a clean framework for analyzing parameters: for example, in the case of SDP, we work with collections of $r \times r$ symmetric matrices, and the Jordan algebra framework makes explicit whether parameters should depend on the rank $r$ or on the dimension $k = \frac{r(r+1)}{2}$.

Q: The Gaussian mechanisms utilize sensitivity parameters which may not be easy to compute or bound a priori in all cases.
A: We agree that computing the sensitivity parameters in advance may not always be straightforward. However, in some cases, we can bound them: for example, in SDP, if the added constraint has bounded spectral or Frobenius norm, or if the perturbation is bounded, then the sensitivity can be controlled.

Q: Optimality of the noise added to achieve privacy is also a concern.
A: We agree that, in this work, we did not prove the optimality of the noise mechanisms. We leave proving optimality of the mechanisms as an important direction for future work. Our main purpose is to initiate the study of DP for SDP, and more generally, for SCP and Jordan algebras. In particular, we wish to highlight a main challenge in this broader setting, namely, the discrepancy between rank $r$ and dimension $k$. This distinction does not arise in the classical vector setting where $r = k$.

Q: Random matrix theory may be a source of additional improvements on the DP guarantees for SDP solvers.
A: Yes, we agree that random matrix theory (RMT) can provide improved bounds when working with symmetric matrices, as noted from Line 256 to 261. In particular, standard results from RMT show that the spectral norm of a random Gaussian matrix scales with $\sqrt{r}$, rather than $\sqrt{k}$, which can improve bounds in the low-sensitivity constraint privacy regime for SDP. We will include a more explicit discussion of this improvement for SDP in the revision.

Q: Besides SDP, are there any straightforward generalizations to second-order cone programming?
A: For second-order cone programming (SOCP), the $(n+1)$-dimensional second-order cone can be viewed as the cone of squares of an $(n+1)$-dimensional spin factor, where the Gaussian element is an $(n+1)$-dimensional standard Gaussian vector. Notably, the spin factor has constant rank $r=2$ and division algebra dimension $d=n-1$, so $n=O(rd)$. Therefore, when applying our SCP results to SOCP, the suboptimality parameter scales with $n$, which matches the scaling for LP.

Q: Can the more recent existing LP results be recovered easily from the Jordan algebra framework?
A: Yes, to recover LP, we observe that for $n$-dimensional LP, there is a unique Jordan frame (the standard basis), and the rank $r$ equals the dimension $k$ equals $n$. Thus, all LP results can be recovered using our machinery, except that for private covering LP, one no longer needs to use a net argument to discretize the space of primitive idempotents (there are exactly $n$), so we obtain the $n^{1/4}$ scaling in the suboptimality parameter as in prior work [HRRU14].

Q: Line 260: why is the $\ell_\infty$ norm of a Gaussian element a major open question?
A: We appreciate your observation. In retrospect, the $\ell_\infty$ norm of a Gaussian element is in fact known and depends on the structure of the Jordan algebra. Every Euclidean Jordan algebra is the direct sum of five simple Jordan algebras: real symmetric matrices, complex Hermitian matrices, quaternionic Hermitian matrices, spin factors, and the exceptional $3\times3$ quaternionic Hermitian matrices. The first three cases have been well studied in RMT, where the $\ell_\infty$ norm scales as $O(\sqrt{r})$. For spin factors (of dimension $k=n+1$), an element can be written as $x' = (x_0, x)$ for $x = (x_1, ..., x_n)$, and the $\ell_\infty$ norm is $|x_0| + \\|x\\|\_2$, so it scales as $O(\sqrt{k})$. As the $\ell_\infty$ norm is the maximum over all components of the direct sum, it is $O(\sqrt{r_{\max}})$ if none of the components are spin factors (where $r_{\max}$ is the largest rank), and $O(\sqrt{r_{\max}} + \sqrt{k_{\max}})$ if there is at least one spin factor. We will include this clarification in the revision.

References

[HRRU14] Hsu, Roth, Roughgarden and Ullman. Privately solving linear programs. ICALP, 2014.

We thank you for your thoughtful and detailed comments, and for your clear assessment of our paper's technical soundness. We especially appreciate your insights regarding the framing of our work, and your recognition of the value in our treatment of noisy oracles for Symmetric Cone Programs (SCPs) and the Multiplicative Weights Update (MWU) algorithm in this context. We believe your feedback offers a clear path to significantly improve the manuscript. Below, we address your main concerns and questions.

Motivation and Contribution: Our primary motivation is to answer the open problem in [HRRU14]: can we design a differentially private (DP) solver for semidefinite programming (SDP)? We demonstrate that it is possible to develop DP solvers, in the spirit of [HRRU14], for SDP and more generally for Euclidean Jordan Algebras (EJAs) and SCPs. While noisy SCPs and their MWU algorithms are independently interesting, the DP framework is not merely decorative: differential privacy provides a principled and structured reason to introduce and analyze noise in these algebraic settings. The DP perspective allows us to formalize sensitivity analyses, composition, and utility guarantees in a systematic way that guides the general study of noise in optimization.

Our framework goes beyond the case-by-case approaches in prior work by providing a generic method for DP in EJA/SCP settings, which helps clarify the scaling with rank $r$ and dimension $k$ for particular applications. This, in turn, “unlocks” a range of downstream private algorithms and improved privacy guarantees for problems such as:

• Private SVMs via SOCP,
• Private matrix completion, robust mean/covariance estimation, and sparse PCA via SDP relaxations,
• Any other task that can be formulated as an SDP or SOCP where privacy of constraints or data is a concern.

On the Role of the EJA Structure and Isometry: We appreciate your careful consideration of our use of isomorphisms between EJAs and $\mathbb{R}^k$. While any EJA of dimension $k$ admits such an isomorphism, directly reducing to $\mathbb{R}^k$ would obscure crucial algebraic structure. Critically, not all norms in $\mathcal{J}$ correspond to standard norms in $\mathbb{R}^k$. For instance, sensitivities and utility parameters would often scale with the full dimension $k$, rather than with the rank $r$ which is usually much smaller (e.g., for real symmetric matrices, $k=O(r^2)$). Furthermore, as highlighted by an insightful comment from another reviewer, we also observed that the $\ell_\infty$ norm of Gaussian elements in EJAs scales as $O(\sqrt{r})$ for most simple EJAs, which would not be apparent by treating everything as $\mathbb{R}^k$. Thus, the EJA framework enables sharper, problem-specific bounds and a more precise understanding of the underlying privacy costs.

On Presentation and DP Background: We appreciate your point about the proportion of the manuscript devoted to DP background. Our intention was to ensure accessibility for the optimization and algebra communities, who may not be familiar with differential privacy. In the revision, we will streamline standard DP background, moving technical details to the appendix where possible, and sharpen the exposition to focus more directly on the novel technical contributions in noisy optimization and SCP.

On Privacy Accounting and Mechanism Optimality: We thank you for highlighting the importance of more advanced privacy accounting techniques (such as [BW19], moments accountant, and RDP) that may yield tighter bounds. While we fully agree on their value, our current work is focused on establishing the foundational differentially private framework for EJA/SCP. Incorporating these advanced accounting methods would introduce significant additional technical complexity and analysis, and we believe this goes beyond the scope of this initial theoretical contribution which is already quite dense. We therefore consider developing tighter, optimal bounds using these techniques, and proving the optimality of the mechanisms, to be a critical and exciting direction for future work.

On Specific Technical Points:

• $\sigma$ parameter and dependence on $\epsilon,\delta$: We will update the manuscript per your suggestion and cite [BW19].
• Noisy oracle and MWU for SCP: We agree this contribution is of independent interest and will expand the manuscript to give it more self-contained exposition.
• Improving generic utility beyond the exponential mechanism: This is a fascinating and important question. While our current framework provides generic utility guarantees applicable across the EJA setting, exploring methods to exploit specific EJA structures for tighter utility bounds is a promising avenue for future research, and we are actively considering this.
• Existence of the dual oracle: The dual oracle checks for the constraint that (approximately) violates its condition most, so its existence can be guaranteed by simply checking all constraints.
• Unit-norm requirement in Theorem C.12: You are correct that this is not without loss of generality. As explained in Remark C.13, the isomorphism $\phi$ only preserves the $\ell_2$ norm. We believe this requirement could indeed be replaced with the standard $\ell_1$ norm one, and exploring a generalized analysis without this assumption is an important and promising direction for future work.

We are confident that these clarifications and the planned revisions will significantly strengthen the manuscript, making its valuable contributions clearer and more impactful for the NeurIPS audience. Thank you again for your constructive and detailed feedback.

References

[HRRU14] Hsu, Roth, Roughgarden and Ullman. Privately solving linear programs. ICALP, 2014.

[BW19] Balle and Wang. Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising. ICML, 2019.

We thank the reviewer for highlighting the value of empirical evaluation. We fully agree that experimental results can provide important insights into the practical utility-privacy tradeoffs of differential privacy mechanisms for SCPs. In this work, our primary focus is on establishing a rigorous theoretical foundation for differential privacy in the setting of Euclidean Jordan algebras, which represents a significant generalization beyond prior work in vector spaces. Given the mathematical novelty and generality of our results, as well as the broad range of potential SCP applications, we felt it was important to first lay down the theoretical groundwork and analyze sensitivity in this new setting.

We view empirical evaluation as a natural and promising direction for future work. Extending our theoretical results to practical implementations and benchmarking them on real or synthetic SCP instances, as suggested, would be a valuable addition to the literature, and we appreciate the reference to [MMSVV21] as a guiding example.

References

[MMSVV21] Medina, Muñoz, Syed, Vassilvitskii, and Viterick. Private optimization without constraint violations. AISTATS, 2021.