Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming
Authors: Zhao Song
Jianfei Xue
Lichen Zhang
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
euclidean jordan algebra
symmetric cone programming
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We develop private mechanisms for Euclidean Jordan algebras and private algorithms for symmetric cone programming, this leads to private algorithms for semidefinite programming.

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 $\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].

Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming
Zhao Song University California, Berkeley magic. 1iw..kdeexxddmii........ com
Jianfei Xue New York University jx8986nyu.ed edu
Lichen Zhang MIT CSAIL
lichenz@csail wttp::/sssaaa.ii......mmmm..ma.e .mi. edu
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 con- tribution generic Gaussian mechanism for such functions, with sensitivity measured in fg. L1, and fx norms. Notably, this framework includes the important case where the function outputs are symmetric matrices, and sensitivity is measured in the Frobenius, nuclear, 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 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].
Introduction
As modern machine learning leverages increasingly large models and ever-growing datasets, protect- ing the privacy of data has become a paramount concern. Differential privacy [DMNS06, DKM+06] has emerged the gold standard for data privacy, owing its simplicity, practicality, and strong theoretical guarantees. Designing machine learning algorithms with differential privacy (DP) particularly valuable, as enables protection of both user data and model parame- ters [BIK 17, GKN17, MRTZI8, TLC 20, ATMR21, NBD22, FHL+24J. However, most dif- ferentially private algorithms for machine learning are developed in case-by-case manner tailored specifically to individual problems to ensure good privacy and utility trade-offs. More generic approaches, such as making stochastic gradient descent (SGD) differentially pri- vate IXLW12, BST14, ACG* 16], have gained significant traction. Since SGD is core subrou- tine many training algorithms, this line of work provides automatic privacy guarantees across wide range of models. Following this direction, we develop differentially private algorithms for solving symmetric cone programs (SCP), broad class of convex optimization problems that includes linear programs (LP), second-order (SDP). These convex formulations arise in many machine lcarning applications, including sup- port vector machines [BGV92, CV95, MMR 01, Joa06, CL11, SSSSC1 GSZ25), matrix comple- tion [CT10, Recl1, CR12, JNS 13, ZWL15, GLZ17, + GSYZ24, SYYZ25], robust mean and covariance estimation [CDG19, CDGW 19], experimental design [vAG19, AZLSW20), and sparse PCA [dEGJL04, ZHT06, dBEGO8, ZdEG10, VCLR13).
programs (SOCP), and semidefinite programs
Symmetric cone programming (SCP) has been extensively studied from an algorithmic per- spective, with both first-order methods [CLPV23, ZVTL224 and second-order methods [Fay97a, Fay97b, SA03, Per23] developed, as they provide valuable insights for solving semidefinite
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

programs, However, algorithms for SCP with differential privacy (DP) guarantees have re- ceived little attention, largely due the abstract nature of the problem class. In fact, to the best of our knowledge, the only known DP algorithms in this family are for linear pro- grams [HRRU14, DF MMSVV21, BBDH24, BBDH25], and designing DP algorithms for SDPs was posed as major open question in [HRRU14]. In this paper, we take a significant step forward by designing DP mechanisms not only for SDPs, but for the broader class of SCPs - a much richer and more general family of convex optimization problems. Our main contributions are two-fold: (1) We begin by examining Euclidean Jordan algebras (EJAs), a class of real inner product spaces that includes RR and the space of real or complex symmetric matrices of size xr. We develop a generic Gaussian mechanism over EJAs that provides (c, 8)ddifferential privacy guarantees when sensitivity is measured in the L,, fz, or & norms. In the case of symmetric matrices, this corresponds to nuclear, Frobenius, and spectral norms, respectively. This stands in contrast to the well-known matrix mechanism [LHR+ 10, HTO9], which aggregates multiple linear queries into matrix and measures sensitivity column-wise in vector norms. Our framework instead captures the geometric structure of matrices by modeling perturbations to their spectrum. (2) We then design suite of private first-order algorithms for solving SCPs under various neighboring data settings. Specifically, given two neighboring databases D and D', we consider the following cases: (i) D' has one additional linear constraint compared to D (high sensitivity constraint privacy), (ii) D and D' differ in one entry of the scalar vector b (low sensitivity scalar privacy), (iii) the constraint sets differ in fox norm (low sensitivity constraint privacy), and (iv) the objective elements differ (low sensitivity objective privacy). For the high sensitivity constraint setting, we show that the multiplicative weights update algorithm over constraints from [HRU13, HRRU14] naturally extends to SCP. For the remaining cases, we develop a novel variant of the multiplicative weights algorithm that operates over the primal variable space, guided by an approximate oracle that identifies the most violated constraint. This is combined with the Gaussian mechanism we previously designed for the EJA structure. As a byproduct, we design multiplicative weights algorithm that could utilize noisy oracle to for solving SCPs, which we believe could lead to applications beyond differential privacy.
Roadmap. In Section 2, we survey related work on both differential privacy and symmetric cone programming. In Section 3, we provide preliminary background on differential privacy and Euclidean Jordan algebras. Section 4 introduces a generic Gaussian mechanism for Euclidean Jordan algebras and establishes privacy guarantees under ε E2, and fox sensitivities. present algorithms for private symmetric cone programming, covering both high sensitivity and low sensitivity constraint privacy settings. For the high-sensitiving case, we give algorithms for solving covering semidefinite programs and covering symmetric cone programs. Section 6 concludes with a discussion of open problems and limitations of our work. Appendix A provides additional preliminaries, particularly on Euclidean Jordan algebras and regret bounds for symmetric cone multiplicative weights updates. Appendix B presents the full details, analysis. and applications for the high sensitivity constraint privacy setting. In Appendix C, we describe algorithms for the low sensitivity setting, including scalar privacy, constraint privacy, and objective privacy.
Section 5, we
2 Related Work
Differential Privacy. Since its introduction in [DMNS06]. differential privacy has become the standard notion for providing rigorous privacy guarantees in algorithm design. It has found widespread applications across general machine learning [CM08, WM10, JE19, TF20], deep neural networks [ACG+ 16, BPS19], computer vision [ZYCW20, LWAL21, TZXL19],, natural language processing [YDW+21, WK18), federated learning [BIK+17, 23, SWY723] and adaptive data structures [HKM** + 22, BKM + 22, ACSS23, 23, SYYZ23, FFL+25), 25]. The line of work most relevant to ours concerns differentially private algorithms for convex programming, particularly linear programming. The work of [HRU13] was among the first to study private algorithms for zero-sum games, special case of linear programming. Subsequently, [HRRU14] systematically examined private linear programs under various notions of sensitivity, including constraint, scalar, and objective perturbations. Their algorithms typically produce solutions that may violate constraints slightly due to privacy noise. To address this, [MMSVV2I] considered the case where only the scalar vector is private, and showed that constraint satisfaction can be maintained by explicitly perturbing the scalar vector. An alternative approach was proposed in [DFVH+ 20], which reformulates the private problem as a stochastic Bbance-constrainee program, whose solution satisfies the original constraints
2

---

with high probability. Building on these ideas, [BBDH24] extended the framework of [MMSVV21] to handle private constraints, and [BBDH25] further demonstrated that it possible to privatize all components of línear program while still satisfying the constraints. Our work is most closely related to [HRRU14], as the other approaches heavily rely on the specific structure of linear programs and extensively use the Laplace mechanism. In contrast, we show that extending these ideas to symmetric cone programming poses significantly greater challenges, both technically and algorithmically.
Euclidean Jordan Algebras and Symmetric Cone Programming. Euclidean Jordan algebras form the algebraic foundation of symmetric cone programming. It is well known that any EJA can be decomposed into a direct sum of simple Jordan algebras, and up to isomorphism, there are exactly five types of simple EJAs: real symmetric matrices, complex Hermitian matrices, quaternionic Hermitian matrices, spin factors, and the Albert algebra [FK94]. Among these, real symmetric matrices underlie semidefinite programming, while spin factors correspond to second-order cone programming, EJAs are commutative but non-associative algebras, and this structure provides key insights into the geometry and algorithmic design of semidefinite programming. As symmetric cone programming generalizes both SOCP and SDP, interior point methods have been extensively developed for this broader setting [Fay97a, Fay97b, SA03, Vie07], with significant effort devoted to abstracting and extending classical SDP techniques. In particular, [Per23] proposes novel interior point method for symmetric cone programs using geodesic updates on the Riemannian manifold defined by the interior of the symmetric cone. Our work builds heavily on the multiplicative weights update framework introduced in [CLPV23] for online linear optimization over symmetric cones, and extended in [ZVTL.24] to general symmetric cone programming. This framework is especially well suited for designing differentially private algorithms, as the oracle component required by multiplicative weights can be implemented via the exponential mechanism.
3 Preliminaries
In this section, we provide some preliminary knowledge on Euclidean Jordan algebras, symmetric cone programming and differential privacy.
3.1 Notations
We use Ö( to denote OJ poly log For two real vectors x, y E R2 we use (I, to denote x y. We use |ı>]|,, ||0||2,, ||= to denote the vector f,, la and for norms. For two real symmetric matrices X, Y E R we use (X, Y) to denote Tr(X YY), where Tr(-) is the trace of the matrix. We use || || and || to denote the matrix nuclear, Frobenius and spectral norms. We use X > Y to denote X - Y is positive semidefinite matrix. We N Σ) denote the multivariate Gaussian distribution with μ and covariance matrix Σ.
3.2 Euclidean Jordan Algebras and Symmetric Cone Programming
We will exclusively work with Euclidean Jordan algebras, which, will later, generalize many important spaces, including R$ and the set of all r x r real symmetric matrices.
Definition 3.1 (Euclidean Jordan algebra (EJA)), An Euclidean Jordan algebra (EJA) is a finite- dimensional vector space I equipped with:
a bilinear product x² (x o y) = x a (x² o y);
I I + I that satisfies, for all x,y J. x xoy = y and
an inner product (.-)) I x J + R that satisfies. for all x. U. E J, (1) = =2, 0);
identity element that satisfies. for all J, coz zoe=
As an example, if I is the set of all r x r real symmetric matrices, then the Jordan product is defined by o y 2 (ay + yæ), where- denotes standard matrix multiplication. Fuclidean Jordan algebras induce a geometric structure known as a symmetric cone, which can be characterized as follows:
Definition 3.2 (Symmetric cone, [Vie07]). A symmetric cone is a closed convex cone in a finite- dimensional inner product space J that satisfies the following properties
K. is self- i.e., K := ty E J x) 2 VI K} = K.
3

---

K. is homogeneous, for any u. U. E int(KC), there exists an invertible linear transformation L J + I such that L(u) and =(K)=
K can be characterized as the cone of squares of an EJA, specifically, there exists an EJA with K. = =x²= x E } where x² x for x E J.
There rank.
key parameters associated with Euclidean Jordan algebra (EJA) J: its dimension and
Definition 3.3 (Dimension and isomorphism), Let I be an EJA. Then there exists a positive integer k such that I is isomorphic to RR. This integer & is called the dimension of J. denoted by dim(J) Moreover, there exists linear isomorphism & : I - IR* such that for all x. E J. we have (x, v) (0(x), ((y),, Le., & is an isometry with respect to the inner product.
As an example, consider the set of X r real symmetric matrices. The dimension of this space is r(r+1) since one can map these matrices to vectors of the same dimension. To define the rank, we first introduce suitable spectral decomposition for any element J.
Definition 3.4 (Jordan frame). Let Q1:.... 9r E I be elements satisfying idempotency (4 q)) and primitiveness (4, + 0 and cannot be written as a sum of two nonzero idempotents). We say fq..... g-P } is a Jordan frame if (1) 9: 9 0 for i + j: (2) Ei=1 9: =
The rank of EJA is defined as the size of Jordan frame used to form spectral decomposition. Definition 3.5 (Spectral decomposition). For any I E J. there exists set of unique real numbers λ1, .h....,.. Ay and Jordan frame (q....., 9r such that x Di=1 Xeq-- The minimal such r is called the rank of I (denoted by rank(J] r). We use Tr(x) We define the exponentiation function exp J - I exp (Ei X.))) = Σ exp(). (x:()))):
X to denote the trace of the element
Returning to the example of the set of r r real symmetric matrices, we observe that the spectral decomposition coincides with the standard matrix spectral decomposition. Therefore, the rank of this space is r. Note the quadratic gap between the rank and the dimension for this example. The final concept we introduce here is the trace-based inner product and the associated family of norms.
Definition 3.6 (Inner product and norm). Given v, y E J, we define their inner product as (r.u) Tr(x y). For any p E [1, o0), the lp norm of x is defined as ||>||p (E (> and for p oc, the Ex norm is defined as ||rll = m [x=())]
Standard inequalities related to the inner product, such Cauchy-Schwarr and Hölder's inequality, continue to hold in this setting; we defer their proofs to Appendix A. We are now ready to define symmetric cone programming.
Definition 3.7 (Symmetric cone programming). Given collection of elements 01. am, C E I and b Tm the symmetric cone program (SCP) is defined as
max (c,z)
S.t. (a,, x) S bi: x >x 0,
Vi [m],
where žx denotes the generalized cone inequality, i.e., łx y means x y K.
3.3 Differential Privacy
Differential privacy is a strong and rigorous notion of privacy, first introduced in [DMNS06). We state its formal definition below.
Definition 3.8 (Differential privacy, [DMNS06]). A randomized mechanism M : :D - R is said to provide (e, d-diifeernttil privacy if. for every pair of neighboring databases D, D' E D (differing in
exactly one record) and every meusurable subset S C R.
Pr[M(D) e S) < e Pr(M(D') E S
Here > 0 and 0 < 6 1 are privacy parameters. The special case å 0 is referred to as c-differential privacy.
We will make use of the standard Gaussian mechanism.

---

We also make use of the exponential mechanism [MT07]. a tool for achieving privacy when the output lies in a discrete or non-numeric domain. This mechanism relies on a quality score, a realev function that evaluates the utility of pairing a database with a candidate output. Given database, the way, element whose quality score is Definition 3,9 (Gaussian mechanism [DKM* 06]). Let e, > O. A mapping f : D - R has
se-siiiitivity D2 for all neighboring databases D, D' differing one record, (f(D)
- f(D))ll S
22. The Gaussian mechanism releases M(D) = S(D) + where v (0, o² [x) and a
A2y / (1.g(1125/ This mechanism satisfies (c, 8) -differrett privacy. privacy.
We note that [BW18] has improved the parameters of Gaussian mechanism, in particular the depen- dence on e, for a. They further extend the analysis to work for all ranges of In this work, we focus on providing a preliminary privacy analysis of EJA, thus we adopt the more traditional and simple bound for Gaussian mechanisms.
To analyze the utility of the Gaussian mechanism, it is convenient to recall standard tail bound for Gaussian random vectors.
Lemma 3.10 (Laurent and Massart [LM00]. Let Z X be chi chi-squared random variable with ls degrees of freedom. Suppose each component has zero mean and variance o². Then:
Pr[Z koo 2 (2V 2t)o² S exp(-t),
Pr|ko² - 22 2v kto? < exp(-t) -t).
exponential mechanism then selects, in a close to the maximum achievable value.
Definition 3.11 (Exponential mechanism, [MT07]). For database D and range R. the exponential mechanism chooses R with probability proportional to exp 22 ((r D)). Here Q R x D - R a quality score function, and A denotes its sensitivity with respect to neighboring databases. This mechanism is e-differential privacy.
The exponential mechanism satisfies the following utility guarantee.
Lemma 3.12 (Accuracy guarantee for exponential mechanism, [KPRU14])- Given B (0,1) and database D. let OPT denote the maximum value of the quality score Q can attain on database D. Then, with an e-private exponential mechanism with quality score on database D and outputs satisfies
that, with probability at least - B, Qrr, D) 2 OPT
2A log
[R]
Finally, we recall a standard composition tool to combine private mechanisms.
Lemma 3.13 ([DRV10), Let 8 E (0, 1), and M1,...,M4, be é' c'-private, adaptively chosen mecha- nisms, then the composition M1 o... o Ma is (c, 5)-iivaee,,, provided that c' 88k 1og(1/)
We remark that while adaptive composition has been improved via moment accountant [ACG* + 16] and Rényi DP [Mir17, WBK19], use the simpler adaptive composition for illustrating the main idea.
4 A DP Framework for Euclidean Jordan Algebras
In this section, introduce differential privacy (DP) framework for Fuclidean Jordan algebras (EJA), based on the Gaussian mechanism. We begin with a motivating example. Let S" denote the set of all r r real symmetric matrices. Suppose we are designing private recommendation system, where each client record is represented by an r-dimensional feature vector u. The goal is to privately release the covariance matrix of the dataset. In this setting, two neighboring databases D, D' differ in exactly one feature vector, and the function data. It is then natural to define sensitivity using the matrix Schatten-p norms rather than entrywise norms. For instance, the foo sensitivity corresponds to the spectral norm (D) f(D))l, while the l sensitivity corresponds to the nuclear norm (D) /(D') These spectrum-aware notions of sensitivity highlight the inadequacy of mechanisms like the Laplace mechanism, which adds noise entrywise, and motivate the need for more principled approach. This leads us to consider general formulation of differential privacy in the context of EJAs, which we refer as DP-EJA.
'D + S" outputs the covariance matrix of the
5

---

Definition 4.1. Let DD be the universe of databases, and let f : - J. For neighboring databases D, D', we define:
f has l sensitivity A1 ifllf(D) - S Ai
f has l2 sensitivity 2₂ ( - S(D' S A
f has lo sensitivity A. if (f(()) - l( s A..
Perhaps the first question one might ask for DP-FJA how do we define an additive noise mecha- nism? It is not immediately clear what constitutes "Gaussian element" in an EJA J. Thus our first order business is to develop a Gaussian mechanism for EJAs.
Lemma 4.2 (Generic Gaussian mechanism). Let J be EJA with dim(J) equipped with an isometry 6 J R. Let e, > 0 and let f D I be a function with E sensitivity D Consider the following mechanism:
Set 2lg21og(1255/5
Generate Gaussian noise vector ((0,o²
Set = (v).
The mechanism releases J(D) and is (c, (diffferneellll private.
Proof. The proof is straightforward. Since & is isometry, we have that for any T, E J, (ő(x), (y)) = (x. y). which implies that || = [[(x))]22 Therefore, the & sensitivity of f satisfies [I][ I(D')l2 = I[)[(()) (()())) By Definition 3.9, the Gaussian mechanism (D) +v (c, (c, -ifferr-iffe private. Since ø is also an isometry, we have & o (( (D) = fD) + ( f(D) + 2, which implies that the release fD) + is (c, d) d)-piivtte.
O
Lemma 4.2 provides a simple method for constructing a Gaussian element in J: choose an isometry 6, generate Gaussian vector in I and then apply o -. Such an isometry always exists, one can construct it using an orthonormal basis for J. As an example, consider J = S", , the space of r(r-1) and the isometry é maps symmetric
r X real symmetric matrices. Then dim( k 2 matrix to vector with the entries from its upper triangular part. Lemma 4.2 in this case corresponds to generating a Gaussian vector in R and then applying x to obtain a symmetric matrix with the upper triangular part filled by the Gaussian vector. The E norm on S corresponds to the Frobenius norm, so it is easy to see that Lemma 4.2 recovers the standard Gaussian mechanism for matrix-valued functions under Frobenius norm sensitivity. As a consequence, we obtain private mechanisms for l and Ex sensitivity via norm inequalities:
Corollary 4.3. Let I be an EJA with dim(J) = k, equipped with an isometry à I + RR.. Let 6, > O, and let J D I have l sensitivity D1. Then, the generic Gaussian mechanism (Lemma 4.2) with sensitivity parameter A is (e, dddifferrrel private.
Corollary 4.4. Let J be an EJA with dim((T) = k, equipped with an isometry 6 : J + R.. Let 6, O, and let f + I have for sensitivity Aos. Then, the generic Gaussian mechanism (Lemma 4.2) with sensitivity parameter vrA is (c, -differrentll private.
One might wonder whether is possible perturb only the eigenvalues instead of all & dimensions. This idea is particularly tempting for S", since k = =O(r² while the rank is only r. A naïve approach would be first compute a spectral decomposition fDD E X then inject scalar Gaussian noise to each eigenvalue, yielding E (A:++1)) This approach also appears attractive for handling & sensitivity by injecting Laplace noise to each eigenvalue. Unfortunately, this method fails to ensure differential privacy. is not sufficient to perturb only the eigenvalues the Jordan frame must also be randomized. This can sometimes be achieved by sampling a random Jordan frame (Pi....,P; and outputting Σ (A, p/)p; However, this raises challenges in bounding the l norm of the result, as one must account for differences between Jordan frames. In the special case R. this issue disappears since there is unique Jordan frame fei...., ex } and rank coincides with dimension. For e sensitivity, one might wish to obtain a pure e-private mechanism using the Laplace mechanism: namely, sample Laplace noise vector in R& with suitable parameters and map it into J via Φ Unfortunately, this also fails: the l norm in IR does not, general, correspond the norm J (except when J f In essence, the isometry á only preserves the inner product and hence

---

the lg norm - but not other norms. For this reason, our mechanisms for l and &o sensitivity are derived from the generic Gaussian mechanism.
We also note that the utility guarantee for the generic Gaussian mechanism follows from the isometry property of d: the lg norm of the noise element I equals the l2 norm of the Gaussian vector RR which scales as v due Lemma 3.10. This implies a weaker bound when translating to so norm. For S standard results in random matrix theory state that || O(VF) [Wig58]. For general EJAs, it is well-known that they are direct sums of five simple EJAs [FK94], and if it does not has spin factor as its component, then || O (T where mmax is the largest rank among its
components, and is O(Vknax + /mrmax) ) if it has spin factor as its component and kimax is the largest dimension. To unify the discussion, we conservatively adopt the weaker OVVi)) bound in this work.
5 Private Symmetric Cone Programming
In this section, develop differentially private algorithms for solving symmetric cone programs. As an application, we obtain private algorithms for semidefinite programming, resolving a major open question posed in [HRRU14]. Following the framework of [HRRU14] for linear programming, we study private algorithms under several settings: (1) High sensifivity constraint privacy, where neighboring databases may differ by one entire constraint; (2) Low sensirivity constraint privacy, where all databases have the same number of constraints, and neighboring databases differ in the foc norm of those constraints; (3) Scalar privacy, where neighboring databases differ in the right-hand side vector b, again measured in fxc norm; (4) Objective privacy, where neighboring instances differ in the objective element e under for norm. Our algorithm for the high sensitivity constraint setting is a generalization of the dense multiplicative weights update (MWU) method used in [HRRU 14 44] for linear programs. For the other three settings, we adopt the MWU framework for symmetric cone programming introduced in [CLPV23, ZVTL24], but propose novel scheme in which the update direction is determined by identifying the most violated constraint.
5.1 High Sensitivity Constraint Privacy
In this setting, the SCP instances for two neighboring databases share the same objective element J but differ by one constraint and its corresponding scalar value: they have the same first m constraints, while D' contains an additional constraint and scalar value b' Note that this additional constraint can be arbitrary. As first observed in [HRRU14] 4], it is generally impossible to design private algorithm that satisfies all constraints, as a new constraint can significantly alter the optimal solution of the original program. The key idea in [HRRU14] is to run an MWU procedure over restricted set of constraints, so that the output solution satisfies most of the constraints while preserving privacy. This is achieved by applying Bregman projection [HW01] and performing MWU over projected dense distribution over the constraints. While [HRRU14] analyzes this method in the context of linear programming, we show that it extends naturally to symmetric cone programming, since the algorithm operates over constraints. As consequence, we obtain private algorithms for covering semidefinite programs that are especially useful in regimes where the number of constraints m is much larger than the matrix dimension r. Specifically, consider the following covering SDP:
min Tr(X) X
s.t. (A, X) 1,
Vi [m)]
where AI...., A. 2 0 and max || S 1. All matrices are of size r x r. Covering SDPs have a wide range of applications in machine learning, including robust mean estimation [CDG19], robust covariance estimation [CDGW 19], and E-optimal experimental design [vAG19].
Theorem 5.1 (Informal version of Theorem B.)0). Let > 0, (0, 1) be the DP parameters, and let 3 E (0, 1) be the failure probability. Given a covering SDP with m constraints over r x matrices, there exists an algorithm (Algorithm 3) that finds X* > 0 such that (A, 2 1 a for all but constraints, with probability at least 1 - B. and a satisfy
==
= 22 (Flog log (1/8) log(1/8) logm). a= O(OTT)
Moreover, the algorithm is e-differentially private with respect high sensitivity constraint privacy.
7

---

The core idea behind Theorem 5.1 is to use the dense MWU framework described above, paired with a private oracle that performs a simple linear minimization. To ensure privacy, the oracle is implemented using the exponential mechanism. A major technical challenge is that, even when the optimal value of the program is fixed to OPT, the number of feasible solutions infinite, as they correspond to extreme rays of the positive semidefinite cone intersected with hyperplane. A naive application of Lemma 3.12 would yield a vacuous bound due to [R| = Do. To overcome this, we use 7-net argument to discretize the space of feasible solutions. By carefully choosing 7, we ensure the size the net is exp(r), which allows us to apply Lemma 3.12 with a penalty factor r. This contrasts with the private covering LP algorithm in [HRRU14], where the feasible solutions simply scaled standard basis vectors in I,, and hence [R] = r, resulting in no such dependence on r.
Inspired by our private algorithm for covering SDP, we further extend the framework to any covering symmetric cone program over a simple Euclidean Jordan algebra:
min Tr(x) aEK
s.t. (), 21, Vi [m].
It is well-known that, up to isomorphism, there five types of simple Jordan algebras: X real symmetric matrices, r X r complex Hermitian matrices, r x r quaternionic Hermitian matrices, r-dimensional spin factors, and the exceptional Albert algebra [FK94]. In particular, the cone of squares for r-dimensional spin factors corresponds to the r-dimensional second-order cone. To apply the machinery developed for private covering SDP general SCP, we observe that the oracle's optimal solutions are (scaled) primitive idempotents in J. Therefore, a q-net argument requires bounding the dimension of the set of primitive idempotents. For all simple Jordan algebras, this dimension is O(r) [FK94], which mirrors the dimension in the SDP case where I = S To the best of our knowledge, this is the first attempt to quantize the rays of primitive idempotents via nett, and we hope this approach enables further applications and tighter bounds in future work.
Theorem 5.2 (Informal version of Theorem B.13). Let J be a simple EJA of rank r. Let c > O, 5 E (0, 1) be the DP parameters, and let B E (0, 1) be the failure probability Given a covering SCP with m linear constraints, there exists an algorithm (Algorithm 3) that outputs a point x² E K. such that (at, x²) > 1 or for all but s constraints, with probability least 1 B. The parameters s and satisfy
log(1/8) 8 = ( (o) logm). a O(PT).
Moreover, the algorithm is e-differentially private with respect to high sensitivity constraint privacy.
5.2 Low Sensitivity Constraint Privacy
In the low sensitivity setting, two neighboring databases have the same number of constraints and differ in the Eo norm. Specifically, let A(D), A(D") be the constraint sets corresponding to neighboring databases D and D', respectively. We assume that max (D, As observed in [HRRU14] for the LP setting, it is possible to approximately satisfy all constraints by applying MWU over the variables. In particular, the oracle in this setting is given the constraint set A E J scalar vector b E RT and point æ E K, and it must return an approximately most violated constraint a; such that (at, b, 2 maxje(m] (a). - bj
A...
with high probability. We refer to such an oracle an (a, 7ddual oracle, which achieves additive approximation and fails with probability at most 7. This oracle is particularly well-suited to privatization via the exponential mechanism: the score function (i) (a,, x)) b, leads to both privacy and accuracy guarantees. It remains to show that one can indeed solve the SCP in a first-order fashion using such an oracle. In the case of linear programming, this is already established by the classical work of [PST95]. Our first result shows that an approximate most violated constraint oracle can likewise be used to solve SCPs over symmetric cones in a first-order manner. Before stating the result, we define the width of the constraint set as p = ma ||ai]boo-
Theorem 5.3 (Informal version of Theorem C.2). Given an SCP with m linear constraints, suppose there exists a feasible point x K. with Tr(x:) 1, and access an (a/22, 7 oracle. Then, there exists an algorithm (Algorithm 5) that finds a distribution element x²' E K. such that (ai, x") & b, +
for all i E [m]) with probability at least T7 where T O log
8

---

The assumption on the existence of I with Tr(x) = 1 is without loss of generality, as it can always be satisfied by scaling down any optimal solution by its { norm. Previous MWU algorithms for symmetric cone programming have relied on primal oracle, where the input is point with Tr(x) 1, and the output vector y R satisfying (E; U:0i - C, x:) 2 and bb S
K.
[ZVTT.244. Our proof instead builds on the regret bound for MWU over EJAs as established in (CLPV23J.
Algorithm 1 Constraint private SCP solver.
1: procedure CONSTRAINTTRRAATESCCHC.
J " R")
2: x' c/r
3: Let (t, be the parameters for the oracle, á be the parameters for DP
4: Let ORACLE be (duua oracle
5: T 144 log a²
TT/ool(1/)) 11 12p
6:
for t = - T do
f A \ (o
7:
8:
p¹ ORACLE(A,
9:
V¹ o2)
2 + (p')
i apetz'
x1 + exp(- E1 18
12:
Tr(exp(- Eim 781))
13:
end for
14: return Et=r
15:
end procedure
We observe that the private data A is accessed both during the oracle step and the loss computation. To ensure privacy in the oracle step, we use the exponential mechanism; for the loss computation, we apply the generic Gaussian mechanism developed Section injecting Gaussian noise into the constraint returned by the oracle.
Theorem 5.4 (Informal version Theorem C.7 and C.9). Let A Im satisfy X(a.) [[,1, for all E [m]. and let b E R"" Let 3,e > O and ê E (0,1). Then Algorithm using the exponential mechanism to implement dual oracle returns distributional element x" such that with probability at least 1 - B, (a;, I + for all i E [m]. where
1/2 1/2, 1/4
polylog(r, 1/B,,11)
1/2
Moreover, the algorithm is (c, --private with respect low sensitivity constraint privacy.
Compared the low sensitivity constraint privacy LP result of [HRRU14], our bound incurs an additional 1/4 factor in a. This arises because the sensitivity is measured in the fxo norm, yet the noise added is k-dimennional Gaussian vector. By standard concentration bounds on the norm of Gaussian vectors (see Lemma 3.),), the l2 norm of the Gaussian vector and consequently, the corresponding Gaussian element entrywise Laplace noise, and the magnitude of any single perturbation is at most A /e with high probability. As discussed in Section 4, our framework does not permit injecting noise directly into the eigenvalues of the EJA elements, since this would require sampling random Jordan frame as well posing additional complexity and potential distortion. We also develop algorithms for the setting where the scalar vector b E RT or the objective element c E J is private under low sensitivity. These follow as variants of the MWU algorithm developed for low sensitivity constraint privacy SCP. We defer the details to Appendix C.
scales with VV. In contrast, [HRRU14] adds independent
Remark 5.5. We interpret Algorithm as an approximate multiplicative weights update (MWU) scheme with noisy oracles. Instead of applying the MWU rule directly to the primal variables. the algorithm first perturbs the oracle output with Gaussian noise and then uses the perturbed value for the updute. Theorem 5.4 can thus be viewed quantifying how the injected noise influences constraint violations. More broudly, by altering the noise distribution, one can adapt the noisy MWU framework other settings that require different types of error guarantees.

---

6 Conclusion
We study differentially private algorithms for convex programming, with a particular focus on symmetric cone programming. To this end, we develop a generic Gaussian mechanism for Euclidean Jordan algebras that provides differential privacy guarantees under é,, f,, and toe norms. We incorporate this mechanism into private solvers for symmetric cone programs under both high and low sensitivity settings. For the high sensitivity regime, we generalize the analysis of [HRRU14] beyond linear programming and apply it to covering semidefinite programs and covering symmetric cone programs. In the low sensitivity setting, we design a private solver based on an approximately most violated constraint oracle, in conjunction with our generic Gaussian mechanism. As direct consequence, we obtain a family of differentially private algorithms for semidefinite programming a longstanding open problem originally posed by [HRRU14] that also encompass wide range of applications in machine learning.
There are several limitations of our work, which leave as directions for future research. (1) The differential privacy mechanisms we employ are relatively basic; recent advances in moment accounting and Rényi DP [ACG* + 16, Mir17, WBK19] could yield stronger trade-offs between privacy and utility. (2) Although our private solvers provide meaningful guarantees, they only approximately satisfy the constraints. In high sensitivity settings, this manifests as small number of constraint violations. A central open question is whether it is possible to design private algorithms that satisfy all constraints exactly. For linear programming. [MMSVV21, BBDH24, BBDH25] develop techniques to preserve feasibility under privacy. Extending these methods to the broader setting of symmetric cone programming (and even SDPs) is considerably more challenging, since one must contend with privacy-presenve perturbations to the spectrum of matrices rather than to entries of vector.
Acknowledgment
We thank anonymous NeurIPS reviewers for their constructive comments. Lichen Zhang is supported by Mathworks Fellowship and Simons Dissertation Fellowship in Mathematics.
References
[ACG+16 16] Martín Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security (CCS), pages 308-318. ACM, 2016.
[ACSS23] Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adver- sarial streaming via differential privacy and difference estimators. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPlcs), pages 8:1-8:19. Schloss Dagstuhl- - Leibniz-7entrum für Informatik, 2023.
[ATMR21] Galen Andrew, Om Thakkar, H. Brendan McMahan, and Swaroop Ramaswamy. Dif- ferentially private learning with adaptive clipping. In Advances in Neural Information Processing Systems, volume 34, pages 17455- 17466, 2021.
[AZLSW20] Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Programming, pages 1-40, 2020.
[BBDH24] Alexander Benvenuti, Brendan Bialy, Miriam Dennis, and Matthew Hale. Guaranteed feasibility in differentially private linearly constrained convex optimization. IEEE Control Systems Letters, 8:2745-2750, 2024.
[BBDH25] Alexander Benvenuti, Brendan Bialy, Miriam Dennis, and Matthew Hale. Differen- tially private linear programming: Reduced sub-optimality and guaranteed constraint satisfaction. arXiv preprint arXiv:2501.19315, 2025.
10

---

[BGV92] Bernhard E. Boser, Isabelle M. Guyon, and Vladimir N. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, 1992.
[BIK* 17] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for preeaccpreeeeviiggg machine learning. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1175-1191. ACM, 2017.
[Bir46] George D. Birkhoff. Tres observaciones sobre el álgebra lineal. Revista A de la Universidad Nacional de Tucumán, Serie A, pages 147-151, 1946.
IBKM+22 22] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranu- rak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1671-1684, 2022.
[BPS19] Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in Neural Information Processing Systems (NeurIPS), 32: 12:1549--55488 2019.
[BST14] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimiza- tion: Efficient algorithms and tight error bounds. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 464-473. IEEE, 2014.
[BW18] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Proceedings of the 35th In- ternational Conference on Machine Learning (ICML 2018), volume 80 of Proceedings of Machine Learning Research, pages 403 412. PMLR, 2018.
[CDG19] Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly-linear time. In Proceedings of the Thirtieth Annual ACM-SIAN Symposium on Discrete Algorithms (SODA), pages 2755-2771. SIAM, 2019.
[CDGW19] Yu Cheng, Ilias Diakonikolas, Rong Ge, and David P. Woodruff. Faster algorithms for nigh-dimensional robust covariance estimation. In Proceedings of the 32nd Confer- ence on Learning Theory (COLT), volume 99 of Proceedings of Machine Learning Research, pages 1-31. PMLR, 2019.
[CL11] Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM Trans. Intell. Syst. Technol., may 2011.
[CLPV23] Ilayda Canyakmaz. Wayne Lin, Georgios Piliouras, and Antonios Varvitsiotis. Multi- plicative updates for online convex optimization over symmetric cones, 2023.
[CM08] Kamalika Chaudhuri and Claire Monteleoni. In NIPS, volume 8, pages 289-296. Citeseer, 2008
logistic regression.
[CR12] Emmanuel Candès and Benjamin Recht. Exact matrix completion via convex opti- mization. Commun. ACM, 2012.
[CSW+23] Yeshwanth Cherapanamjeri, Sandeep Silwal, David Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou, Robust algorithms on adaptive inputs from bounded adversaries. In The Eleventh International Conference on Learning Representations, 2023.
[CT10] Emmanuel J. Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inf. Theor, 2010.
[CV95] Corinna Cortes and Vladimir Vapnik. Support-vector networks, Mach. Learn., 1995.

---

[dBEGO8] Alexandre d' Aspremont, Francis Bach, and Laurent El Ghaoui Optimal solutions for sparse principal component analysis. Journal of Machine Learning Research, 9: 9:1269-1294 2008
[dEGJL04] Alexandre d' Asspemonn,, Laurent El Ghaoui, Michael I. Jordan, and Gert R. G. Lanck- riet. A direct formulation for sparse pea using semidefinite programming. In Advances in Neural Information Processing Systems, volume 17, pages 4 1-448. MIT Press, 2004,
[DVH 20] Vladimir Dvorkin, Ferdinando Fioretto, Pascal Van Hentenryck, Jalal Kazempour, and Pierre Pinson. Differentially private convex optimization with feasibility guarantees. arXiv preprint arXiv:2006. 12338, 2020.
[DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, volume 4004 of Lecture Notes in Computer Science, pages 486 186-503. Springer, 2006.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[DRV10] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51 annual symposium on foundations of computer science, pages 51-60. IEEE, 2010.
[Fay97a] Leonid Faybusovich. Euclidean jordan algebras and interior-point algorithms. Positiv- ity, 1(4):331-357 1997.
[Fay97b] Leonid Faybusovich. Linear systems in jordan algebras and primal-dual interior-point algorithms. Journal of Computational and Applied Mathematics, 86(1):149-175, 1997.
[F]L+25] Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, and Lichen Zhang. On differential privacy for adaptively solving search problems via sketching. In International Conference on Machine Learning (ICML). PMLR, 2025.
[4] Jie Fu, Yuan Hong, Xinpeng Ling, Leixia Wang, Xun Ran, Zhiyu Sun, Wendy Hui Wang, Zhili Chen, and Yang Cao. Differentially private federated learning: A system- atic review. arXiv preprint arXiv:2405.08200 2024.
[FK94] Jacques Faraut and Adam Korányi. Analysis on Symmetric Cones. Oxford Mathemati- cal Monographs. Clarendon Press, Oxford University Press, 1994.
[GKN17] Robin C. Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv:1712.0755 2017.
[GLZ17] David Gamarnik, Quan Li, and Hongyi Zhang. Matrix completion from O(n) samples in linear time. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 940 1100-947.110 PMLR, 07-10 Jul 2017.
[GSY724] Yuzhou Gu, Zhao Song, Junze Yin, and Lichen Zhang. Low rank matrix completion via robust alternating minimization in nearly linear time, In The Twelfth International Conference on Learning Representations (ICLR), 2024.
[GS725] Yuzhou Gu, Zhao Song, and Lichen Zhang. Faster algorithms for structured linear and kernel support vector machines. In The Thirteenth International Conference on Learning Representations (ICLR), 2025.
[HKM+22) 22] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. J. ACM, 69(6), 2022.
12

---

[HRRU14]
Justin Hsu, Aaron Roth, Tim Roughgarden, and Jonathan Ullman. Privately solving linear programs. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), volume 8572 of Lecture Notes in Computer Science, pages 612-624. Springer, 2014.
[HRU13] Justin Hsu, Aaron Roth, and Jonathan Ullman. Differential privacy for the analyst via private equilibrium computation. Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 341-350, 2013.
[HT09) Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceed- ings of the s Annual ACM Symposium on Theory of Computing (STOC), pages 705-714. ACM, 2009.
[HW01] Mark Herbster and Manfred K Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research, (281-309):00-116,, 2001.
[JE19] Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th USENIX Security Symposium (USENIX Security 19), pages 1895- 1912, 2019.
[JNS13] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix comple- tion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 665-674, 2013.
[Joa06]
Thorsten Joachims. Training linear svms in linear time. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. pages 217-226, 2006.
[KLL+23] Jonathan Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian. Matrix comple- tion in of Computer Science, FOCS'23, 2023.
time. In 2023 IEEE 64th Annual Symposium on Foundations
[KPRU14] Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 403-410, 2014.
[LHR* 10] Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the 29th ACM SIGMOD-SIGACT-SSGAAAT Symposium on Principles of Databuse Systems (PODS), pages 123-134. ACM, 2010.
[LM00] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
[LT91] Michel Ledoux and Michel Talagrand. Probubility in Banach Spaces: Isoperimetry and Processes. Classics in Mathematics. Springer, 1991.
[LWAL21] Zelun Luo, Daniel Wu, Ehsan Adeli, and Fei-Fei Li. Scalable differential privacy with sparse network finetuning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 5059-5068, 2021.
[Mir17] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[MMR 01] K.-R. Muller, S. Mika, G. Ratsch, K. Tsuda, and B. Scholkopf. An introduction to kernel-based learning algorithms. IEEE Transactions on Neural Networks, 12, 2001.
[MSSVV1] Andrés Muñoz Medina, Umar Syed, Sergei Vassilvitskii, and Ellen Vitercik. Private optimization without constraint violations. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2557-2565. PMLR, 13-15 Apr 2021.
13

---

[MRTZ18] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. 6th International Conference on Learning Representations (ICIR), 2018.
[MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium Foundations of Computer Science (FOCS), pages 94-103, IEEE, 2007.
[NBD22] Maxence Noble, Aurélien Bellet, and Aymeric Dieuleveut. Differentially private federated learning on heterogeneous data. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 10110-10145, PMLR, 28 38-3 Mar 2022.
[Per23] Frank Permenter. A geodesic interior-point method for linear optimization over symmetric cones. SIAM Journal on Optimization, 33(1):1-25, 2023.
[PST95] Serge A Plotkin, David B Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20(2):257-301, 1995.
[Rec11] Benjamin Recht. simpler approach matrix completion. Mach. Learn. Res., 12:3413-3430, dec 2011.
[SA03] S. Schmieta and F. Alizadeh. Extension of primal-cual interior point algorithms to symmetric cones. Mathematical Programming, 96(3):409-43 2003.
[SSSSC11] Shai Shalev-Shwartz, Yoram Singer. Nathan Srebro, and Andrew Cotter. Pegasos: primal estimated sub-gradient solver for svm. Math. Program., 127, 2011.
[SWYZ23] Zhao Song. Yitan Wang. Zheng Yu, and Lichen Zhang. Sketching for first order method: efficient algorithm for low-bandwidth channel and vulnerability, In Inter- national Conference on Machine Learning (ICML), pages 32365-32417. PMLR, 2023.
[3] Jiankai Sun, Xin Yang, Yuanshun Yao, Junyuan Xie, Di Wu, and Chong Wang. Dpaue: differentially private auc computation federated learning. Proceedings of the Shirtt-Seventh AAAI Conference on Artificial Intelligence and Thirly-Fisth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence, Press, 2023.
AAAI
[SYY723] Zhao Song, Xin Yang, Yuanyuan Yang, and Lichen Zhang. Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance. In International Conference on Machine Learning (ICML), pages 32418-32462. PMLR, 2023.
[SYYZ25] Zhao Song, Mingquan Ye, Junze Yin, and Lichen Zhang. Efficient alternating mini- mization with applications weighted low rank approximation. The Thirteenth Internation Conference on Learning Representations (ICLR), 2025.
[TF20] Aleksei Triastcyn and Boi Faltings. Bayesian differential privacy for machine learning. PMLR, 2020.
In International Conference on Machine Learning, pages
[TLC+20] Stacey Truex, Ling Liu, Ka-Ho Chow, Mehmet Emre Gursoy, and Wenqi Wei. Ldp-fed: Federated learning with local differential privacy. In Proceedings of the 3rd ACM International Workshop on Edge Systems, Analytics and Networking (EdgeSys '20), pages 61-66. ACM, 2020.
[TWK22] Jiyuan Tao, GQ Wang, and L. Kong. The araki-lieb-thirinne inequality and the golden- thompson inequality euclidean jordan algebras. Linear and Multilinear Algebra, 70<19):4228-49 42088,4443444400 2022.
14

---

[TZXL19] Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, and Ping Li. On efficient retrieval of top similarity vectors. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP)IJCNIPP) pages 9239-5244, 2019.
[vAG19] Joran van Apeldoorn and András Gilyén. Improvements in quantum sdp-solving with applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPlcs), pages 99:1- 99:1-99:15 Schloss Dagstuhl-Leibniz-Zzan matik, 2019.
für Infor-
[VCLR13] Vincent Q. Vu, Juhee Cho, Jing Lei, and Karl Rohe. Fantope projection and selection: near-optimal convex relaxation of sparse pea. In Advances in Neural Information Processing Systems 26 (NeurlPS), pages
2013.
[Ver18] Roman Vershynin. High DiggenDimessional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[Vie07] MVC Vieira. Jordan algebraic approach to symmetric optimization. PhD thesis, 2007.
[WBK19] Yu- Yu-Xiang Wang. Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1226-1235. PMLR, 2019.
[Wig58] Eugene P. Wigner. On the distribution of the roots of certain symmetrie matrices. Annals of Mathematics, 67(2):325-327, 1958.
[WK18] Benjamin Weggenmann and Florian Kerschbaum. Syntf: Synthetic and differentially private term frequency vectors for privacy-preserving text mining. In The 41st Interna- tional ACM SIGIR Conference on Research & Development in Information Retrieval, pages 305-314, 2018.
[WM10] Oliver Williams and Frank McSherry. Probabilistic inference and differential privacy. Advances in Neural Information Processing Systems (NeurIPS), 15:2451-24557 2010.
[XLW12] L. Xie, K. Li, and H. Wang. Stochastic gradient descent with differential privacy. In 2012 IEEE International Conference on Intelligent Control and Information Process- ing. pages 47-52. IEEE, 2012.
[YDW+21] Xiang Yue, Minxin Du, Tianhao Wang, Yaliang Li, Huan Sun, and Sherman S. M. Chow. Differential privacy for text analytics via natural text sanitization. In Findings, ACL-IJCNLP 2021, 2021.
[7dRG10) Youwei Zhang, Alexandre d' Aspremont, and Laurent El Ghaoui. Sparse pea: Convex relaxations, algorithms and applications. In Daniel Palomar and Yonina Eldar, editors, Convex Optimization in Signal Processing and Communications, pages 331-352. Springer, 2010.
[ZHT06] Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of Computational and Graphical Statistics, 15(2):265 226-28,, 2006.
[ZVTL24] Jiaqi Zheng, Antonios Varvitsiotis, Tiow-Seng Tan, and Wayne Lin. A primal-dual framework for symmetric cone programming. arXiv preprint arXiv:2405.09/55, 2024.
[ZWL15] Tuo Zhao, Zhaoran Wang, and Han Liu. A nonconvex optimization framework for low rank matrix estimation. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[ZYCW20] Yuqing Zhu, Xiang Yu, Manmohan Chandraker, and Yu-Xiang Wang. Private-knn: Practical differential privacy for computer vision. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 11 11854-11862, 2020.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main contributions of this paper include a generic Gaussian mechanism for Euclidean Jordan algebra and private algorithms for symmetric cone programming. They are clearly reflected in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper clearly discusses the limitations in the second paragraph Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer: [Yes]
Justification: All assumptions and proofs are provided, specifically, see Section 4 for the privacy proof of the generic Gaussian mechanism, Appendix В for the settings and proofs for high sensitivity constraint privacy with applications, and Appendix C for a slew of results in the low sensitivity setting.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper is theoretical in nature and does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
17

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper is theoretical and does not contain data and code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.
seggiidde///dduuuiissss wrriiissssoooolioi onnooiccy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips.
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is theoretical hence contains no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is theoretical hence contains no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
18

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper is theoretical hence contains no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that NeurIPS Code of Ethics https http://::///uruseeceeae httpssscccppupcbpceeeeeeeeeeecee cetooliieethiisuueellll...
didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: Authors have reviewed and ensured the paper adheres to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Broader societal impacts have been discussed in Appendix D.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
19

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper is theoretical in nature, therefore does not contain data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper is theoretical in nature, therefore does not use any assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswi wwwode.hhoe...c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
20

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper is theoretical in nature, therefore does not create any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooeemmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper is theoretical in nature, therefore does have any crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper theoretical in nature, therefore does require and IRB approvals.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
21

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM only used for word editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy (https / http:////oo/eeeeee//////0/0/ for what should or should not be described.
22

---

Appendix
A More Preliminaries
In this section, we provide more preliminaries on standard inequalities for EJA and multiplicative weights update for SCP.
Cauchy-Schwarz inequality is automatically satisfies given an proper inner product, we record it here.
Definition A.1 (Cauchy-Schwanl inequality for EJA). Let x; y E J, then we have the following standard Cauchy-Schwarz inequality:
Kr, w>1 S || 11y/12.
While -Shhwarz inequality only requires an inner product space, Hölder's inequality requires dual norms and pairing. Nevertheless, we prove the Hölder's 's inequality for EJA.
Lemma A.2 (Hölder's inequality for EJA). Let p. E [1, oo) satisfy 1/p + 1/9 1. let E J. then have
Ke, M\l S ||=11p 111/lg-
Proof. The idea is write v, y in their spectral decomposition and apply the standard vector Hölder's inequality. Let æ = Ex λ;u; y = Ei μ4ú; be their respective spectral decomposition. Note that given a primitive idempotent element u, we have that Tr(c) = ||c|] because its rank-1. Then
(xz, x> = Tr(x u1)l
Tr
Σ M.xi
Σ Aspl Tr(us v,)1
Ael- luyl (ui, my),
consider the matrix pt.j (ut, Uz), note that P is doubly stochastic matrix: since all u,'s, vj are primitive idempotent, it must be that (ui, U/) 2 O. Moreover, it's easy to verify that we fix i, then
(us 05)) (ui: (5)
1=1
-usse) e) Tr(us)
=1
and the same argument holds for rows. By Birkhoff-von Neumann theorem [Bir46], P can be written convex combination of permutation matrices :P = "E=n c:lT; where e;'s form convex combination, so suffices to work with any permutation matrix IT and its corresponding permutation function σ [r] [r]. set [A], [pl be the vector with entries in | [pyl. then
Σ AAdl 1
|pyl
11g = 1111
Σ Del Iottl--
(1)
Thus, we can conclude that
Σ
Pal |psl (ui, = |^| Plu]
23

---

GillAllellall
= || Iplla/la
where we use vector Hölder's inequality in the third step. This completes the proof.
[TWK22] proves generalized Golden-Thompsee Thompson inequality for EJA, follows.
Lemma A.3 (Generalized Golden- Golden-Thompson inequality, (TWK22]). Let (J,o) be an EJA and y,y J, the generalized Golden- Thooeson inequality holds:
Tr(exp(# + y)) I Tr(exp(æ) exp(u)).
We now describe the online linear optimization framework over symmetric cones.
Definition A.4 (Online linear optimization (OLO) framework using symmetric cone multiplicative weights update (SCMWU), [CLPV23]). At each time I, the algorithm needs to pick distributional element p' such that Tr(p²) and p' K. Once the element is picked, a linear loss function (p) = (m', ,P) where m E J. The SCMWU computes the next iterate as
exp(-1) Et=1 m²)
Tr(exp( -1 E==1m²)
where p² e/ Tr(e)) is the uniform distribution K.
The main idea of SCMWU is to incur cumulative losses comparable to the losses of the best set of actions that an algorithm can make in hindsight. The discrepancy between the cumulative losses of our algorithm and the optimal algorithm is usually referred to as the regret as function of time t. We recall the regret bound of SCMWU proved [CLPV23].
Theorem A.5 (Theorem 5.1 of [CLPV23]), Let (I, o) be EJA of rank K. be its cone squares. For any y & (0, 1] and any sequence of loss vectors (e....., (T)) satisfy [1@' lloo S 1, the iterates A generated by Algorithm satisfy
Σ CC B) + Inr
where any point K. satisfying Tr(B) =.
B High Sensitivity Constraint Private SCP
In this section, we study algorithms for SCP in the high sensitivity constraint privacy setting. We generalize the algorithm and analysis of [HRRU14] in the LP setting.
B.1 Solving SCP with Dense Multiplicative Weights Update
Let us begin by considering constraint private SCPs over a symmmetric cone K. in an EJA J. with the general form
max (c, x) ZEJ s.t. (aj, x) S by, Vj E [m]
r E K,
24

---

where c, a........00..................... 4m E JJ.......b E R a J.
Let Kort = Kn far J (c,z) OPT}. We reduce the SCP to the feasibility program
find KOPT s.t. (aj, S bb, Vj E [m],
then binary search the value OPT. Hence, it suffices to solve the feasibility program. As KOPT is convex, we write K. for KOPT for simplicity.
Let A {(1,.--.,00 ,00m E Im be collection of constraints. A database D defines an SCP as a tuple (c(D), (.D)) A(D), ((D), where c(D) is the objective element, A(D) is the set of constraints and b(D) is the right hand vector. In a constraint private SCP, we have that c(D) c(D', the only differing parts are the constraints A(D),((D") and their associated scalar value. In particular, IA(D) n A(D')l m, [A(D) = m, IA(D')I m +,, A(D), A(D") coincide with all m but one constraint. The scalars for the coinciding constraints are the same, except the scalar value for the differing constraint. We define the adjacency as differing by exactly one constraint.
Definition B.1 (High sensitivity constraint privacy). Given m N. vector b RT" and a constraint set A E Tm, a randomized mechanism M that outputs a vector in I is (e, (e,8)-high sensitivity constraint private for any A, A' such that A' = AU {am+tl. and b, such that b' [b; bm+1]
Pr[M((,, b, A) E S] S e Pr[M(m + 1,b,, E S
for any subset J.
Next, we introduce the dense MWU framework. Let J. denote the universe of actions, F be the measures on the set of actions F F + [0, 1]. and F be the respective probability distribution, defined as F TFT where |F| EJEr Py density of F. A key concept we will be relying on is the Bregman projection.
Definition B.2 (Bregman projection). Let F be measure with F| for some 0, we define I I,&F F as the Bregman projection of F' onto the set of L/s-dense distributions:
1 _ min(11 YSEF, P.Ff = 8
where e 2 O is the value satisfying = Efer min(1,
Algorithm 2 Dense multiplicative weights update, [HW01].
1: procedure DENSEMWU(F.n)
2:
Fl t- the uniform distribution on F
F E
3: for 11=------ do
4:
B' F,
5: Receive loss vector do
b E
6: for f F++1 F++1+ - -
7:
8: end for
9: end for
return FT
11:
end procedure
The following lemma due to [HW01] gives the regret bound for Algorithm Lemma B.3 ([HWOI). Let F2 denote the uniform distribution over F (so that [Fal = 1). Consider the sequence of projected distributions TT= produced by Algorithm 2 under an arbitrary loss sequence {Et TT= with ||e*1| < 1 and step size S 1/2. Define B* as the uniform distribution
supported on some subset S C F of size s. Then,
T
CC B') + + log F
Σ
B
S T
T
25

---

As standard for any MWU algorithm, we define the width of an SCP, denoted as p:
P 2 max max max (a,(D), (D)),,
ZER sE[m]
MWU algorithm usually assumes oracle that can efficiently perform "simpler" minimization problem, and our case, it corresponds to minimize over a simple linear function.
Definition B.4 ((ox, -ppprooxie, p-hounded oracle). Given distribution y E R and set = {a1..... aml J E J an (a,, apprrxxmmaee, p-bounded oracle returns x² E K. with probability
at least B such that
Yoa x²) min yaa x) + and
max sc/m
(a,, x²) b, S P.
To solve symmetric cone programs, employ the dense symmetric cone multiplicative weights update algorithm, which maintains distribution over the constraints and, at each iteration, selects a point æ E IC that approximately minimizes the weighted violation of those constraints. Intuitively, losses increase the weight assigned to violated constraints, thereby steering subsequent iterates toward improved feasibility. Averaging the points x' across all iterations then produces approximately feasible solution. The full procedure is described in Algorithm 3.
Algorithm 3 SCP feasibility via DENSESCMWU.
1: procedure SCPDENSEMWU(A,
2: y +- 1m/m
3:
Let p 2 maxp max max4e[m] (D,) b.(D)) be the width of the SCP, E N be
the density parameter, a > O be the desired accuracy
4:
Let ORACLE be (a, -accurate, p-bounded oracle
5:
17
k / (log mT/mm/TTTT. T + 36a -2 2p² log m
6:
for / = 1
do
7:
x² <- ORACLEEU A)
8:
et < (1/2p) (b; (a),x")) + 1/2
9: Update 7 from T and l' via dense multiplicative weights with density
10: end for
11: return T + (1/T)
12: end procedure
Algorithm differs significantly from other MWU algorithms for solving SCP such as [CLPV23, ZVTL24), where the algorithm updates the variable E K. instead of distribution constraints, In the following, we show that Algorithm 3 provides utility guarantee for solving the program. The proof is similar to [HRRU14), the analysis focuses the constraint, which does not exploit the structure of EIA J.
the
Lemma B.5 (Approximate SCP feasibility via SCPDENSEMWU, Let A fai,...... am E T and b E Rmm be the width of the SCP. Let a E [0,9p), 3 E (0,1) and Suppose the SCP feasible, then Algorithm with density that utilizes an (a 8 -appoxiiiix p-bounded oracle can output x² in K. such that, with probability at least 1 - B, there exists subset of constraints S S [m] with S < s and x*) b, + a for all S.
36a 36a-2pp log m.
Proof. We will condition on the event that the oracle succeeds on all steps, note that this could be achieved via a union bound over T steps obtain a success probability of least 1-3. 3.
Let KG = ty RT (1m,3) y) = 1, | I 1/s} be the set of 1/s-dense distribution. The oracle finds xf with = yi (a;, x²) < Li=1 yib; + a//3. Define the i-th item in the loss vector is e = (b; - (a;, xf)) 1/2. Then we have
(e' = Σ A
1=1
m
1 |bvl Ib
= -112pp)
Σ
(b:
(as,
1=1
26

---

2 (1/2p)
Σ vi4 v/bb) -a/3) + |1lll
i=1
a
6p
if a 9p, then (0,0") 1. To prove an upper bound, we recall that the oracle is p-bounded:
(e.5))
(1/2p)
Σ (b. (as, af)) + 2 llvll
m
1
lb: (ai,
2 +
2p
Σ
1/4 +
2
1=1
1,
therefore, apply Lemma B.3 for the following bound, let K.g, then
1
((.p) p) + + log m
2
6p
T
n/
1=1
1
1 2 + 1 (b, (a, x²))+
log 1/
Σ
Ps
T
2p
rearranging gives
m
log m n/T
(b: (a;, x²)) + n
Pi
6p
2p
x² the above bound could further be written recall that we set the final output I = 1/T t=
m
2plog m
Σ
ps (ai, S
Σ
p4 by + 2pm +
+
1T
t=1
picking 1) log m and T
100p" log gives
a²
Σ pt (a. x) S Σ
b - a.
1=1
As the above bound holds for any p E K,,, it must the case that J satisfies all but at most constraints with additive error a. Suppose otherwise, there are constraints violate the a-additive error condition, then we could set p as the uniform distribution over these s constraints and this implies that these constraints satisfy the a-additive error condition, contradiction.
B.2 Privacy Guarantee of Dense Multiplicative Weights Update
Next, we prove that Algorithm 3 is private long the oracle is private. The algorithm only utilizes the private data via the oracle minimization, hence, as long as the oracle is privately minimizes over K. at each step E [T]. the final output will automatically be private as K. is convex. To do so, recall a lemma first proved in [HRU13], showing that for two neighboring databases that differ by one action, then their projected distributions ÿ and y satisfy |1 7 S 2/s.
Lemma B.6 ([HRU131). Let F: F + [0, 1] and F" FU(f} + [0, 1] be two measures their respective set of actions. Let density parameter s E N and it satisfies that (1) [F', [F"| S s. (2) F1 = FjJ for every f E F. Let F, F' be the corresponding Bregman projections onto the set of 1/ 1/s-dense distributions, then we have
FF-FIl 2/3
27

---

Now we are able to present our main theorem for high sensitivity constraint privacy:
Theorem B.7 (Privacy guarantee). Let e, > O. Consider symmetric cone program with constraint mairix A Imm, vector E IR',, and width p. Fix parameters a E 10,9pl, 3 (0, 1), and 3 logm Given access to an (ax33, B/TT)-ppprximmate p-bounded oracle that is also For any neighboring instances, the oracle inputs satisfy
e'private where e'= VSTlog(1/6)
1x 2
Then Algorithm run with density parameter (e, 8)-high sensitivity constraint private.
Proof. Since the oracle is e' e'-private, the overall (c, connstrrii private is achieved via adaptive composition (Lemmaa 3.13). When adding or removing a constraint, we note that A and are identical except for one additional constraint. Since project the distribution onto Kg, it must be the case Ilul |17 || S 1/s, and i - 7 S 2/s follows from Lemma B.6. Thus, since two distributions are identical except for the probability associated with the additional constraint, we have completed the proof.
B.3 Application I: Private Solver for Covering SDP
As application, show how to develop private solver for covering semidefinite programming:
min XEReXr
Tr(X)
s.t. (A, X) 2 Vi E [m]
0 0
where A
Am 2 O. We without loss of generality assume maXie[m] ||Ad|| < 1, note that this can be done via scaling all the A,'s. Again, we consider the convex set KOPT = (X > 0: Tr(X)= оPT) and will assume OPT is known, as otherwise it could be found by binary search. Thus, we can consider the feasibility problem
find X E KOPT
s.t. (4, X) 2 1, Vi [m].
It is natural to study high sensitivity constraint privacy in this setting, as one could view A; as the positive semidefinite constraint matrix associated with each individual data point as in the case of robust mean estimation [CDG19], robust covariance estimation [CDGW19] and E-optimal experimental design [vAG19].
We need to design an oracle to solve the minimization problem
O = arg min X XEKOPT
Ar X);
this is linear minimization problem, and KorT is the intersection of hyperplane and the positive semidefinite cone, and the solutions to the linear minimization are the extreme rays of the cone:
x"
where ||0||3 = OPT. To implement a private oracle, it is tempting to use exponential mechanism directly, but note that there infinitely many r-dimensional vectors u satisfying ||ui| OPT, so the accuracy guarantee of Lemma 3.12 12 because meaningless as | = co. To address this issue, we use y-net argument quantize the ball B {u E R' ||ul[3 < OPT} into finitely many points.
Lemma B.8 (IL191, Ver18)). Let B (u R ||u]|2 < RJ, there exists finite collection of points N < TR"" such that for any u B, there exists u E N such that I|u vl12 S 7 yor 7 > Moreover: |N| = ((BRn)"))
Our private oracle will then be the exponential mechanism, over the net N.
Lemma B.9. Let OPT, E > 0, 3 E (0, 1), s E N, and define B {u E Rr ||ul S OPT).
Assume neighboring inputs y. 3 E 1 satisfy l| < L. ll I 1 and yy //11 - 2 Let N be
28

---

/OPTT 22n of B (Lemma B.8), and let Ovy) denote the e-private exponential mechanism on N with quality score
Qu, E Y: uu ) 1.
Then O(y) is ( aapprxxiiae p-bounded oracle with
6r OPT
log(1/3),
P S 30P--1
Proof. We first need to prove the width of the oracle. For any point a E N, we know that there exists point v B with ||u - ul[2 S 7, therefore
(Ai, uu T) 1 = u A -
< |1u12 -1
- 21|u112 + 21|u 2 -1
- 2(PT +
For accuracy guarantée, we first need to compute the sensitivity of the quality score. To do so, note that for the first m entries, we have E 1y 2/l - 2/s and D' might have one more constraint, therefore the extra entry of y has its magnitude being at most 1/s. We let y. v/ E IR++1 and set 9m++1 = 0, the sensitivity is
Σ Uo A
Σ
E Ul un T> 1u T ② YA Σ s(A.))ul
-iiu v.Ju Acul
max :
lu T "A,ul: 11 - y
max || 11 -3/s
3ОPT
To obtain the final bound, we need handle on |N. Pick Lemma 3.12, we can choose a as
OPT then N S exp(r) and by
6PPT a: 8.6.
log( N\
6r OPT
log(1/3).
8
this ensures a success probability of at least 1 - B. We hence complete the proof.
We in position state the final privacy and utility guarantee of algorithm for high sensitivity constraint privacy.
Theorem B.10 (Formal version of Theorem 5.1). Let 8,8 E (0,1), > 0. Algorithm 3 with the oracle Ogy) as in Lemma B.9 solves a covering SDP with m constraints by outputting X > 0 such
that with probability at least we have (A,, X*) 2 1 a for all but constraints where
s s Ω ( l/ log(1/8) log m
and a = OOPTT) Moreover, Algorithm e-private with respect to high sensitivity constraint privacy.
Proof. To apply Theorem B.7, we require a S 9p, and need to use an 3//3.//T) 11388//T)apprrxiimat aaprroximate plug in these choices into
oracle with e'-private. As T 36a 36a-2 -2p"
log and é (ng
Lemma B.9:
18r OPT
log (T\
8 el
29

---

54r OPT . (og())))))) log(T/3)
r. OPT VT
log log(1/))ogg(1/1))
T.OPT-P v log log(1/8)
0
8.6.0
solve for a, we get
r. OPT P log (1/0)looogg'' 1og
a=C.
and the requirement < 9p forces that
OPT
log (111)) m C'p,
8
rearranging gives
r. OPT
V8 2
log m -log' 1/2 (1/8) 1og(1/3) log m
log (1/8)
C
p.c
OPT
8 Ω
P.c
Ω __ log" /2 (1/0) log(1 (13)) logm) m
This completes the proof.
B.4 Application II: Private Solver for Covering SCP
More generally, consider the covering symmetric cone programming:
min NEJ
Tr(x)
s.t. (a;, x) 2 1, Vi E [m]
x E K,
where aiy..., Um K. We can again without loss of generality assume max4emi ||a:/oo 1. Set
KoPT {r K. Tr(x)) OPT), reduce the optimization to feasibility:
find x E KOPT s.t. (a,,z) 2 e [m].
Recall that we need to design an oracle to solve
O arg min zEKOrT
y:og x).
in the case of SDP, we noted that the optimal solutions to a linear minimization over the positive semidefinite cone are the extreme rays of the cone, i.e., rank-1 positive semidefinite matrices. For SCP, we consider the case where J is simple Jordan algebra, which covers the interesting cases including real symmetric matrices, Hermitian symmetric matrices and spin factors (the algebra whose cone of the squares the second-order cone). In this scenario, it's easy to see that the optimal solutions are the primitive idempotent y with Igll3 = OPT. To use 7-net argument, we need to understand the dimension all the primitive idempotents in J. These primitive idempotents form connected and compact manifold, whose dimension can be characterized follows:
Lemma B.11 ([FK94]). Let I be simple Jordan algebra with runk and Peirce constant d. Let Q (q I q is a primitive idempotent), }, then dim((Q = d(r-1). Let = (c:q: e E R2 E Q). then (C) d(r 1) +1.
30

---

Algebra J
Rank
Peirce constant
X r real symmetric matrices
r x r' complex Hermitian matrices
r
2
r quaternionic Hermitian matrices
4
7-dimensional spin factors
2
Albert Algebra
3
8
Table I: Five types of simple Jordan algebras, their rank and Peirce constant.
Peirce constant is a parameter related to the Pierce decomposition a Jordan frame. We list r and for all the simple Jordan algebras.
We note that r-dimensional spin factors are (r + 1) -immeensional vectors whose cone the square is the second-order cone. We can hence conclude that for all simple Jordan algebras, the dimension of is at most 4r. We could then use exactly the same argument for Lemma B.9 and B.10 for covering SCP.
Lemma B.12. Let OPT, > O, 3 E (0, s E N, let COFT = fc 9 & < OPT, Q}. Assuming neighboring inputs y, R satisfying oo lly' S 1/s, 1yy 11 S 2/s. Let N be a / OPTT /2-net of COPT and let Oyy) denote the e-private exponential mechanism with quality score
Q(p,y) 9)
yıa,, p)
Then, Oγy is an (a, apprrxxiiae, p-bounded oracle with
a 24r OPT
log(1/3), P PS D33PT-1
8 6
Theorem B.13 (Formal version of Theorem 5.2). Let B,8 E (0,1), 0. Algorithm 3 with the
oracle O as in Lemma B. solves a covering SCP with constraints by outputting x² E K. such that with probability at least 33 we have (a,, x²) 2 o for all but constraints where
St ( log (1(0) log(1/8) log m
and O(PPT). Moreover, Algorithm is e-private with respect high sensitivity constraint privacy.
C Low Sensitivity SCPs
For low sensitivity SCPs, the divergence between neighboring inputs diminishes the database size increases, We continue to study the feasibility program in the following form:
find K.
s.t. (a,, x) I by, Vi E [m].
We further without loss of generality normalize the constraints that the feasible solutions distributions over J. The reduction is simple, if the optimal solution has trace L,, then consider
find E K. s.t. (ai, x) S bb/LL,v [m]
has distribution solution. Once computing solution x². the unscaled program. The only downside is that if the constraints are only approximately satisfied: (a,, x²) b, L + for all i [m], by setting a' LL, then (a,, Lx*) b; + a'.
scale back obtain solution for
C.1 Solving SCPs with Multiplicative Weights
For convenience, we present standard algorithm framework for multiplicative weights update. We note Algorithm 4 is quite different from the standard multiplicative weights update, which would
31

---

take the form
F exp(-nE))
F++1
Tr(Ft exp (xp()))(t))
however, this turns out to be insufficient since exp(A) A) exp( B) * exp( + B) in general unless A and B commute, see [CLPV23] for more details. The regret bound of Algorithm 4 has been recorded in Lemma B.3.
Algorithm 4 Multiplicative weights update algorithm.
1: procedure MWU(F, 71)
2: F the uniform distribution on FF
3: for t= 1 + T - do
4: Receive loss E E J (may depend on F1, ........" F*)
exp(-n -i-1- 5: p++1 Tr(exp(-1) -ia
6: end for
7: return FT
8: end procedure
Our MWU algorithm for solving SCP is somewhat different from the variants introduced in [ZVTL24].
it relies on dual oracle that returns approximately most violated constraint. This should be treated as a generalization of the dual oracle for LP introduced in [HRRU14).
Definition C.1 (Dual oracle). For 7 O, (a, --daaal oracle, given A {ai, (.,,..., am) } Jm. b E TRm and x E K as imput, returns an index i E [m] such that
(at, x) b, 2 max (Laj, σ) - by) a. jE[m]
with probability at least 1 % provided that
max ((ax((a; bb) 0. jE(m)
The full algorithm is given in 5.
Algorithm 5 Solving SCP feasibility via MWU over primal variables.
1: procedure SCPMWUPRIMALAA E J E Rm)
2: xx f e/r
3: Let p = max axlloo be the width of the SCP, a >> be the desired accuracy
4: Let ORACLE be a (a, dual oracle.
4 T +- 16,² logr
5:
"
6:
for
t= 0 0 do
7:
p' + ORACLE(A, b, b.
8:
L p app
exp( Di ne*) 1+1 + Tr(expl Ei N(1)))
9:
10:
end for
11: return .
(1/T))+ x
12:
end procedure
Our MWU framework is based on SCP variant introduced in [CLPV23, ZVTL24), hence its proof dif- fers significantly from [PST95] as the update is different. Moreover, the SCP solver due to [ZVTL24] utilizes primal oracle. Henee, prove convergence theorem for the dual oracle.
Theorem C.2 (Formal version of Theorem 5.3). Suppose the SCP admits a distributional feasible solution E IC with Tr(x) = Then Algorithm 5, when equipped with (a/2, 7) -dual oracle, returns & E K. such that
(as, x) < by +
ei [m],
with probability at least 1 Thy
32

---

Proof. Our proof will be applying Theorem A.5, to do so, we first need to verify that the sequence of loss satisfy that ||e S 1. As we set p to be the max infinity norm over all constraints, it's easy to see that || S 1. Next, we assume the oracle is exact, i.e., it returns maxje(m) (aj. by. Then we show how to generalize the argument to approximate oracles. By Theorem A.5, we have that
T Σ
(0 ..) + n/ + hr
(e,
for any probability distribution y E K. Set = (aps, x²) - byr, we can explicitly compute the LHS:
Σ (0
x²)
(ppt
p
1 T
(bpe r²),
meanwhile since we can choose any distribution y K., we choose a feasible y so that for any i [m]] (a., v) S b;, thus
Σ (,,y)
1
Σ
apt
v)
t=1
1
$
bpr
P t=1
combining these inequalities yields
hr
S nT
+
P
multiplying both sides by & gives
p plu
T
r
np
1/T
setting 17 2/ and T lor the above bound simplifies to
1 T
Σ nE
to obtain final bound for any constraint, fix i E [m]. we note that for any t E [2]. it must be the case that (a,, w²) bi S (apt, x²) bpr, and if we average it gives
1
Σ aas x²) b, (ai, b;
T
T
Ft
S 6,
as desired. Now recall in our algorithm we are using approximate dual oracle, and we slightly modify the analysis by setting e = a/ 2,, and note that the only place we are using the most violated constraint is to prove all constraints, where using ( ddull oracle would blow up the final error by a factor of a/2. Together with the choice of e, we conclude that for any E [m], (as, x)) b. S a holds with probability at least - Try (via umion bound).
33

---

C.2 Scalar Private SCPs
We first consider the "simpler" case of scalar private SCPs. This is when the objective and constraints are public data, and only the scalar vector b is private. A private database D is mapped to a tuple (A(D),<(D) b(D)). For neighboring databases D, D', the mappings satisty
dD) = c(D))
A(D) = A(D"),
Le., both the objective vector and the constraint matrix A are independent of the data. Moreover, the right-hand side vectors differ only by bounded amount:
[b(D) b(D')ll < A...
Note that since R", here the infinity norm is the standard vector for norm. We again focus on the feasibility SCP. Formally:
Definition C.3. Given a vector IR"", and a constraint set E Jmh, a randomized mechanism M that outputs vector in I is (e, 6)-low sensitivity scalar private for any b, b' with b|b 1l S Aoc.
Pr[M(b, A) E S) Pr[MMB', A) E E] +
for any subset S S
To achieve privacy, will implement private dual oracle via exponential mechanism, henceforce privatize Algorithm 5.
Lemma C.4. Let > and y E (0, 1). Suppose that on neighboring instances the vector changes by at most Doc in lx norm. Then, the e-private exponential mechanism with quality score
bii (aa, x) b;
an (a, duual oracle, where
2A oc log(
Proof. Note that our oracle will be following the procedure:
Given A, x, b, computing Q(i, b) for all e [m];
Sample constraint with probability exp( شيك (i),
This procedure is automatically e-private following the definition of exponential mechanism (Def. 3.11), so it remains to prove the procedure indeed implements an (a, -dual oracle. By Lemma 3.12, this is true
2 log( which completes the proof.
We are now the position to provide privacy and accuracy guarantees for scalar private SCPs. Theorem C.5. Let
8, e (0,1), 1), and define p max4e[m] |as]]oc- Then Algorithm is (c, -low sensitivity scalar private with sensitivity A... and with probability least B outputs x² E K. such that (ai,x") > E b, + a for all E [m], where
1/2
e//2 log
"logo // (1g))) log
Proof. Let (8Tlog(1/8)
exponential mechanism to implement an e'-private dual oracle,
and by adaptive composition (Lemma 3.13), this gives a final (c, (erivatr algorithm. For success probability, we set 7 = B/T. By Lemma C.4, we have
a 2Ax
log mf
2Ax / 8T (188)
mF
log(
B
34

---

8D Sooplogg 2202 "llo"//(11/) -loo(
16mpp² log
a²²
solving for a gives
11/2 1/2 log 1/4 rlogg rlog2/4(1/0)) (1/8) (1/ 10
el/2
as desired. This completes the proof.
C.3 Low Sensitivity Constraint Private SCPs
Given the feasibility program
find E KC
s.t. (a,, x) S bi, Vi,i E [m],
and neighboring instance would perturb some constraints by small amounts. More specifically, for two set of constraints A, A' E J define the global infinity norm as
|| A'l max
|aa d'lloo>
ic im(m]
and we assume for two neighboring instances, their distance in global infinity norm is at most A...
Similarly to the scalar private setting, private database mapped tuple (A(D), For every pair of neighboring databases D, D', the mappings satisfy
cD) c(D))
b(D) b(D),,
ie., both the objective vector and the scalar b are independent of the data. Moreover, the constraints differ by a bounded amount
|A(D) A( A.x.
Formally:
Definition C.6. Given a vector E R", and a constraint set A E JTh randomized mechanism M that outputs vector in I is (e,6)-low sensitivity constraint private for any A, A' such that || - Al S Aocr
Pr[M(b,A) $ e Pr[M(b,, E S
for any subset J.
We without loss of generality normalize the constraints so that the spectrum of each lies in [-1, 1]. Our algorithm will again be implementing the dual oracle with exponential mechanism. However, as the oracle returns a constraint and it will be used to compute the loss, we have to add one more layer of privacy via the generic Gaussian mechanism.
Theorem C.7 (Privacy guarantee of Theorem 5.4), Let and A.c be as defined in Algorithm 1, and suppose the algorithm employs an e' c'-private dual oracle. Then Algorithm is (c, 6) -low sensitivity constraint private with sensitivity A.c.
Proof. We note the privacy comes from two sources: the Gaussian mechanism and the oracle operation. For Gaussian mechanism, by Lemma 4.2, we know that each operation is / (ff')/r-'iivttee and each oracle is c' c'-private. By an adaptive composition over 2T operations, we see that the algorithm is (c, ppivvate.
We prove that the exponential mechanism is private dual oracle under this setting of neighboring. Lemma C.8. Let > 0 and E (0, 1). Suppose that on neighboring instances the constraint set A changes at most Arc in lxx norm. Let K. be any distributional element. Then, the e-private exponential mechanism with quality score
Q A) (a;, x)) b
is an (a, dual oracle,
24
m
log
35

---

Proof. Since x is distribution, the quality score Q changes by at most A. on neighboring inputs, and hence is -enssiive. The claimed accuracy bound then follows directly from the accuracy guarantee of the exponential mechanism (Lemma 3.12).
To prove the convergence, we need to slightly change the original argument, as we have to perturb each constraint by Gaussian noise element. We give customized proof based on standard regret bound.
Theorem C.9 (Utility guarantee of Theorem 5.4). Let A E Tth satisfy Ma.) S [-1, for all i E [mn], and let b E Rm.. Fix 8, > 0 and E (0, 1). Let r denote the rank of I and l. its dimension. Algorithm I, when run with the exponential mechanism
Then, with probability least dual oracle (Lemma C.8), returns a distribution x² such that
(0,, Sb
[m],
where
Am 1/2 1/44//11//4
a Ō
poly log(r, 1/B,1/8)
e//2
Proof. Let be as in Theorem C.7, T be the number iterations in Algorithm 1, and set = (2T).
By Lemma C.8, with probability at least 1 7 the oracle returns p' such that for all constraints E [m].
(() (lap x²) bbt) S
24
log(
m
Here p' is chosen as the constraint that is nearly the most violated, up to an additive factor of a. Define the vanilla loss 8 azt. Note that the left-hand side of (3) is exactly ((,,,") bb) ((f', x²) - b,z). Applying a union bound over the T oracle calls, inequality (3) holds simultancously for all t E [T] with probability at least 3/2. We henceforth condition on this event.
We next need to bound the norm of the noise element 2. Again, we utilize the isometric between J and I& in & norm: recall that (62") (2') is Gaussian vector sampled from (0, o² I²I,), by Lemma 3.10, with probability at least - (2T).
2T
| l (Vk+ + log(
3
A. ( 2og (T/)) + 2r (og( log(1/7))
union bound over T' noise elements, it succeeds with probability least 1 B/2, condition on this event happen. Note that the bound on || (Eq, (4)) subsumes the error introduced by the oracle (Eq. (3)).
We proceed by assuming the norm of Gaussian noise is small, in particular,
Do v 2rk (T/8) + /2r (T)6 log(1/7))
(5)
since a < this implies that the norm of the noise is at most 1/6. Hence,
||e* oc
||
||2 1bo
e 00
+ ||
2
1.
We can then apply Theorem A.5: pick y E K. be feasible distribution element, then
1
S
1
Σ
C vi
+
log
T
T
nT
36

---

set r = (
(x
+
we compute
2
2
1
bpt
Σ
x²)
T
T
2
1=1
t=1
bpt
logr
Σ
T
+ 17 +
1/T
Fix any constraint a,, since we assume the error of the exponential mechanism at most 2 log( m
7
by Eq. (5) and x' is distribution, it must be the case that
(0;, x²)
b;
(2 _0
T
2
T t=1
b
logr r
$
+
nf 6'
where the first step is by Eq. (3). Recall that we also have shown that the norm of Gaussian noise is small and we could bound the term introduced by
(22 20 1 S | 11a ||
I //
where the first step is by Hölder's inequality (Lemma A.2) and the second step is by Eq. (5). Thus, we have
1 Σ aq x²) b t=1
2 2log
Σ 2(p v) bp + 2m +
T
T 1=1
nf
remains to examine therefore
2(2,, y) bic, since is feasible, it must be that for any i, (a v) b, S 0,
2 v) - byt = (apt,)) v) + (z', v) bp.
< (x",1)
< |wlla ||
S a/6,
put things together, we have
(ai, v²) b; (at, bi
T
20
2 log r
21 +
n/
S ax
where the last step is by the choice of n and T. remains to provide value of a that satisfies Eq. (5), and we can take
6d (v 2rk log (T/5) + (orlog(T/0) (og(1)))
e'
24 VTT (VK + Vlo((1/7)) log(T/0)
288A /Flor (Vk+ + Vlog(T/3) log (T/8)
ae
rearranging gives
12A 1/2 ,/, 2/ (10gr)//44
288 log 1/4 (log
288 log r 1/2
(log
e/2
3
8
This completes the proof.
37

---

Remark C.10. Our algorithm differs significantly from the row private LP algorithm of [HRRU14], where they ensure the constraints are private by injecting Laplace noises to each entry. This comes from the fact that for 3 TR." the only Jordan frame is the standard basis, hence to develop differential private mechanism, is enough to perturb the eigenvalues. For other J, this no longer the case. Consider I to be the set of all r X real symmettic matrices, then a Jordan frame can be formed by taking any set of orthonormal vectors Ujy..., Up E R' and computing u U| :.... U4 u, This large degree of freedom means that private mechanism must also perturb the Jordan frame to ensure the basis information is preserved. We achieve so by implicitly resorting to the isomorphism between I and R. such a random Gaussian element would possess both random eigenvalues and Jordan frame. frame. Note that we choose Gaussian mechanism instead of Laplace mechanism, as we will only provide either lg & norm guarantee instead of ea and l2 norm only distorts & by factor of / instead of k that is given by the & norm.
C.4 Objective Private SCPs
Finally, we consider objective private SCP, where instead solving a feasibility problem, we try to solve the optimization version. In contrast to [HRRU14), we again consider two neighboring objectives differ in foe norm.
max (c, ZEJ
s.t. (a;, x) S bi, Vi E [m]]
K.
Given two neighboring databases D, D', we have A(D) = A(D'), = b(D') and |c((D) o() Aoo. Formally,
Definition C.11. Given a vector b E R", c CE K and a constraint set A Jmm a randomized mechanism M that outputs a vector in I is (e, 8l-wow sensitivity objective private if for any e, d such that ||c d'll dl S Ax.
A)
A)
for any subset S J.
Next, we present a simple algorithm, based similarly on the Gaussian mechanism introduced in Lemma 4.2, but applied to the objective element. We further assume somewhat unusual but necessary condition on the SCP: there exists an optimal solution with unit Eg norm.
Theorem C.12. Let the objective private SCP has optimal value OPT and the optimal solution has unit E2 norm. Suppose dim(J)= k and Φ J - R is an isomorphism between J and R Consider the following mechanism:
Set Am 2r log(1/6)
Generate Gaussian noise vector (2
Set (v).
Then, let ē= c c and the perturbed SCP
max (2, 2:) #E.7
8.f. (ai, < bi, Vi E [m]
||0||| =1
E K.
is released. Then, the algorithm is (e, -lo sensitivity objective private with sensitivity A With probability 1 3, solving the perturbed SCP non-privately produces such that (ai,x" bi, Vi [m] and (c, xx) 2 OPT a, where
4A 00 log (1))) + [lg(1/3)
38

---

Proof. Recall that ||e||2 S vr. V/-l|cloo. by Corollary 4.4, indeed the mechanism is (c, --rivatee For accuracy, by Lemma 3.10, with probability least 1 3.
|| - (Vk + vlog(1/3))
x 2rk log (100 v 2r (og(1/0) log(1) (13))
Suppose that
25ol22rklogh +
a
2
Let x be the optimal solution to the perturbed SCP, and let x be the optimal solution to the original SCP. Note that if
(c, (, < OPT
then
(C,"" = (c+ (2),
< OPT a + (6- 3*)
S OPT a + 11 (z)1l2 |
= ОPT - a/2,
where use & is an isometry (can be achieved by picking an isomorphism with respect to an orthonormal basis), Bouchy-Schwarr inequality and the definition of a/22. Meanwhile, note that
(²,x") OPT +
2 OPT - ||2||2 ||00||a 112
OPT - a/2,
contradicts the definition of x². Thus, it must be the case that (c, ;*) > OPT a, and 3 is feasible since it's feasible solution to the perturbed SCP, and the perturbation does not change feasibility. This completes the proof.
Remark C.13. In [HRRU14), they impose much standard assumption that ||>||| = 1. This again comes from the fact that for J = IR*, the isomorphism is just the identity map, and in addition to the isometry in lo norm [|o(2)][2 = 1212. all norms are preserved. This is particularly important when applying Hölder's inequality: when ||]|| = L, we could upper or lower bound the inner product by the Ex norm of the noise z. This no longer true for J + RR. as o(.) only preserves the & norm, translating between different norms would incur blowup or shrinkage factors dependent on Of course, imposing an &g norm constraint makes the constraint set no longer an affine subspace, which would require solvers that could handle quadratic constraints.
D Impact Statement
Our work concerns the privacy of symmetric cone programming, we believe its development would help protect the data and model privacy for various machine learning tasks. At its current stage, work is theoretical, so does not lead to any direct negative societal consequences.
39


Reviews:
[{"review_id": "S0IXqyF30D", "reviewer": "Reviewer_KhAJ", "summary": "This paper introduces differential privacy mechanisms for functions with outputs in Euclidean Jordan algebras (EJAs) and applies them to symmetric cone programming (SCP). The main contributions are: (1) a generic Gaussian mechanism for EJAs with $l_1, l_2$, and $l_{\\infty}$ sensitivity, and (2) private algorithms for SCP under various sensitivity settings using multiplicative weights updates.", "questions": "A weakness of this work is the absence of experimental validation. if possible, Could the authors provide empirical evaluation on some synthetic and real-world symmetric cone programming instances? For example, Medina et al. (2020) demonstrated their private optimization algorithm's effectiveness through experiments showing utility-privacy tradeoffs and comparing against baselines. \n\n[1] Medina, Andrés Muñoz, Umar Syed, Sergei Vassilvitskii, and Ellen Vitercik. \"Private optimization without constraint violations.\" arXiv preprint arXiv:2007.01181 (2020).", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The paper extends differential privacy beyond vector spaces to the more general setting of Euclidean Jordan algebras, which is mathematically non-trivial.\n- It addresses the longstanding question of private semidefinite programming posed by Hsu et al. (2014).\n- The paper covers multiple sensitivity notions, including high/low sensitivity for constraints, scalars, and objectives.\n\n## Weaknesses\nWhile the theoretical contributions are mathematically sound, the paper lacks empirical evidence demonstrating actual performance of DP mechanisms on real-world symmetric cone programming instances.", "was_revised": true, "final_justification": "Authors addressed my questions, and I tend to maintain my score.", "rebuttal": "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.\n\nWe 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.\n\n**References**\n\n[MMSVV21] Medina, Muñoz, Syed, Vassilvitskii, and Viterick. Private optimization without constraint violations. AISTATS, 2021."}, {"review_id": "1EOfFz2spC", "reviewer": "Reviewer_5Ady", "summary": "This paper proposes a theoretical framework for applying differential privacy (DP) in more complex algebraic spaces using the framework of Euclidean Jordan Algebras (EJA). From a DP perspective, the Gaussian mechanism can be applied when there exists an isometry from the EJA to $\\mathbb{R}^k$ by adding Gaussian noise in $\\mathbb{R}^k$ and inverting the isometry. The claimed benefit of the more general framework is a unified approach to a variety of problems, including semidefinite programming problems. \n\nOf note is that this paper is a purely theoretical/algorithmic contribution and does not rely on experimental evidence. I think this is fine, but I wish to forestall criticisms from others about the lack of experiments: it is a reasonable choice by the authors' choice to not do an empirical study.", "questions": "I can appreciate that the authors are in a bind when writing this paper. Will a NeurIPS reviewer know what an EJA is? Will they know what DP is? Will they have seen SCPs? Will they know only a subset? Therefore they have opted to submit a manuscript which is dominated by basic definitions. I am writing this review as someone who has familiarity (at varying levels) for all 3 (more on DP, textbook-level on the SCPs and JAs).\n\nThis paper is basically about noisy SCPs: the noise is Gaussian (no other distributions are investigated). This makes the differential privacy interpretation almost \"window-dressing\" around the actually interesting part of the paper.\n\n**Issue 1: What is the actual DP contribution?** By the author's own admission, \"the utility guarantee for the generic Gaussian mechanism follows from the isometry property of $\\phi$\" so why is the privacy story so important?\n\n* If we can assume there is an isometry $\\phi \\colon \\mathcal{J} \\to \\mathbb{R}^k$ why not just work with $\\mathbb{R}^k$ if the mechanism is effectively $\\phi^{-1}( f(D) + z )$? That seems to be the workhorse of the privacy guarantees: since we are working with $\\ell_2$-sensitivity the sensitivity bound is preserved by the isometry so there's basically no difference from thinking of a mechanism $g \\colon \\mathcal{D} \\to \\mathbb{R}^k$ and using post-processing invariance to apply $\\phi^{-1}$. That would avoid the need to rebuild any differential privacy definition \"from scratch.\" Am I missing something deeper here? \n* The setting of $\\sigma$ in terms of $\\epsilon$ and $\\delta$ is \"old fashioned\" and does not hold for all $\\epsilon$: see Balle and Wang (ICML 2019). \n* In general, working with $(\\epsilon,\\delta)$ and advanced composition is far behind with respect to the privacy accounting literature: just look in [Google Scholar for \"privacy accounting\"](https://scholar.google.com/scholar?hl=en&q=privacy+accounting). Why use the \"advanced composition\" and not modern methods like the moments accountant, RDP, etc.? These have been around for well over 5 years.\n* From a purely motivational standpoint, what applications for which privacy is important does the EJA framework \"unlock\" with respect to prior work?\n\n**Issue 2: Is the main technical contribution in showing that MWU can be extended to symmetric cone programming?** The paper really gets going in Section 5 and beyond, where they delve into some interesting issues around using MWU in SCPs.\n\n* Spending more time in the actual paper on covering SDPs and noisy optimization (or noisy oracles) would broaden the scope of the paper.\n* Is there a way to exploit the specific structure of this problem setting to improving over the \"generic\" utility guarantees from the exponential mechanism?\n* What is the justification for the dual oracle? That is, why should such an oracle exist (the argument that it is useful to have one is there in the paper already).\n* Is the unit-norm solution requirement in Theorem C.12 without loss of generality? It seems not.", "limitations": "Yes.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "For the author's benefit, in the language of journal submissions this is to me a \"reject with recommendation to resubmit\": the technical results are sound but the presentation is not reflective of the actual contribution.\n\n**Strengths:**\n\n* The EJA framework is a nice general frame for thinking about DP methods in non-vector settings.\n* While using the multiplicative weights (MWU) approach is by now \"classic\", the authors do a nice job of looking at its instantiation in an important class of problems.\n\n**Weaknesses:**\n\nThe main weakness of the paper (to me) is that the authors saddle themselves with the baggage of differential privacy and accounting for completely unnecessary reasons: understanding SCPs with noisy oracles is, in and of itself, an interesting problem. This has led to a manuscript which obscures, rather than highlights, the main technical contribution. Differential privacy is simply an *application* or *example* of what is really going on. There could be other reasons why the oracle is noisy/approximate.\n\n* It is hard to identify new conceptual ideas on privacy side from the EJA formulation given the requirement of an isomorphism to Euclidean space.\n* Far too much space in the main manuscript is devoted to a rehash of DP, making the contribution to symmetric cone programming a bit telegraphic.\n\nI am recommending reject based on the manuscript presented for review. This is not a judgment on the merits of the results but rather on whether the paper is a good contribution to the literature.", "was_revised": true, "final_justification": "I find this reporting requirement overly burdensome given the reviewing load. My responses to the authors are there in the record.", "rebuttal": "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.\n\n**Motivation and Contribution:**\nOur 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.\n\nOur 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:\n- Private SVMs via SOCP,\n- Private matrix completion, robust mean/covariance estimation, and sparse PCA via SDP relaxations,\n- Any other task that can be formulated as an SDP or SOCP where privacy of constraints or data is a concern.\n\n**On the Role of the EJA Structure and Isometry:**\nWe 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.\n\n**On Presentation and DP Background:**\nWe 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.\n\n**On Privacy Accounting and Mechanism Optimality:**\nWe 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**.\n\n**On Specific Technical Points:**\n- $\\sigma$ parameter and dependence on $\\epsilon,\\delta$: We will update the manuscript per your suggestion and cite [BW19].\n- 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.\n- 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.\n- 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.\n- 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.\n\nWe 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.\n\n**References**\n\n[HRRU14] Hsu, Roth, Roughgarden and Ullman. Privately solving linear programs. ICALP, 2014.\n\n[BW19] Balle and Wang. Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising. ICML, 2019."}, {"review_id": "12RPoLS5de", "reviewer": "Reviewer_HiLA", "summary": "The paper provides differentially private SDP solving algorithms where the privacy guarantee is measured by the sensitivity to perturbation in nuclear, spectral or Frobenius norms of the output positive semidefinite matrix. The SDP solvers use multiplicative weights and solve the SDPs approximately in the sense that a fraction of the constraints may be violated. The techniques used to achieve these differentially private solvers are the design and analysis of MMW style algorithms so that DP guarantees can be reduced to ensuring that the oracle is implemented in a ‘privacy preserving’ manner. The private oracles are then implemented using a combination of Gaussian and exponential mechanisms for covariance matrices (some developed in the present work) and epsilon net arguments, that are described using the formalism of Euclidean Jordan Algebras, \n\nWhile there has been much work of DP for linear programs, there are not many references on DP for SDP solving. This paper takes important steps on DP mechanisms for SDPs and ‘approximately’ solves the DP for 4 different formulations for the closeness of databases. The algorithms do not seem to be optimal in all settings and possibly could be improved by future work.", "questions": "-Random matrix theory may be a source of additional improvements on the DP guarantees for SDP solvers. RMT answers questions on the precise change in the spectrum when the entries of the matrix are perturbed by adding additive noise, as in the Gaussian mechanism proposed here. \n\n- Besides the SDP case, are there any straightforward generalizations to private mechanisms for second order cone programming? Also, can the more recent existing LP results be recovered easily from the Jordan algebra framework? \n\n- Line 260: Why is an l-infty estimate for the norm of a Gaussian element a major open question?", "limitations": "Discussed in paper.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- The paper uses a principled approach to developing differential private mechanisms for SDPs developing first a Gaussian mechanism. It then considering separately 4 different notions of database closeness that may arise and separately solving each using a tailored MMW type algorithm and Gaussian, exponential and \nEpsilon net type arguments. \n\n- It could be argued that the Jordan algebra is not really needed and results could be proved using more standard notation. However the use of Jordan algebras provides conceptual clarity for definitions of the Gaussian mechanism and in the construction of the gamma-net in one of the proposed mechanisms for covering SDPs. \n\n- A weakness is that the Gaussian mechanisms utilize the sensitivity parameter which may not be easy to compute or bound apriori in all cases. For the SDP case this parameter is a bound on change in spectral/Frobenius norm of the solution when a single constraint is added or perturbed. \n\n- Optimality of the noise added to achieve privacy is also a concern as the quality solution degrades with the extra noise added. Not much is said in the paper on whether this noise rate can be reduced or is optimal under some conditions. \n\nOverall assessment: Assessment: A good paper that carries out a detailed investigation of DP for SDPs in different settings using MMW type algorithms.", "was_revised": true, "final_justification": "The comments and clarifications addressed sufficiently my remaining questions regarding this paper. I would like to maintain my score of 5.", "rebuttal": "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}$.\n\n**Q: The Gaussian mechanisms utilize sensitivity parameters which may not be easy to compute or bound a priori in all cases.**  \nA: 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.\n\n**Q: Optimality of the noise added to achieve privacy is also a concern.**  \nA: 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$.\n\n**Q: Random matrix theory may be a source of additional improvements on the DP guarantees for SDP solvers.**  \nA: 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.\n\n**Q: Besides SDP, are there any straightforward generalizations to second-order cone programming?**  \nA: 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.\n\n**Q: Can the more recent existing LP results be recovered easily from the Jordan algebra framework?**  \nA: 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].\n\n**Q: Line 260: why is the $\\ell_\\infty$ norm of a Gaussian element a major open question?**  \nA: 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.\n\n**References**\n\n[HRRU14] Hsu, Roth, Roughgarden and Ullman. Privately solving linear programs. ICALP, 2014."}, {"review_id": "GACzcrPPZG", "reviewer": "Reviewer_kBdT", "summary": "This paper studies differentially private symmetric cone programming (SCP). Prior works used private multiplicative-weights for linear programs (LP). But optimization on richer cones such as Lorentz and PSD cones are still open. Because Gaussian mechanisms calibrated in  Euclidean norm either introduce dimension-dependent noise or break cone feasibility, no polynomial time algorithm with meaningful utility guarantees existed for constraint-private semidefinite programs (SDP), where a single individual’s data can alter an entire constraint. Using Euclidean Jordan algebras, this paper introduces a cone-aware Gaussian mechanism that matches operator-norm sensitivity and embeds into a rank-sensitive multiplicative-weights framework. \n\nThis gets us the first solver for private covering SDP that also extends to all symmetric cones defined in SCP. The main theorem (theorem 5.1 )guarantees approximate feasibility while violating only $s=\\mathcal{O}\\left(\\frac{r}{\\varepsilon}\\right)$ constraints, matching the linear-program rate when cone rank $r$ equals dimension. The mechanism therefore closes the open problem of high-sensitivity, constraint-private optimization beyond linear settings, extending differential privacy guarantees to symmetric cones while retaining polynomial runtime and tight accuracy.", "questions": "1. Could the cone-aware Gaussian mechanism be adapted for DP algorithms that currently rely on SDP, such as private sparse PCA or robust mean/variance estimation? What are some potential future works that could benefit from the generic gaussian mechanism and the private SCP?\n\n2. The high-sensitivity solver relies on an exponential-size $\\gamma$-net oracle. Can this be replaced by some random sampling, or sketching technique?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: I haven't read the proof but this paper feels very solid. The contribution is mainly from the generic gaussian mechanism that removes the dimension dependence and unlocks the private SCP. I feel like this advancement could have broader implications, potentially benefiting areas like private learning, private sparse PCA, private robust mean/variance estimation, etc.\n\nWeaknesses: Many readers know SDP but not EJA, it would be better if the authors could explain the technical results using examples from Euclidean space.", "was_revised": true, "final_justification": "After rebuttal, my questions are all resolved. I also share Reviewer 5Ady's concern about the positioning of the paper. Overall, I think thi is a good private optimization paper with a focus more on the optimization side.", "rebuttal": "We appreciate your valuable comments. We are happy to address your concerns and questions.\n\n**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.**  \nA: We agree and will include examples in terms of real symmetric matrices and semidefinite programming (SDP) when explaining the technical results in the revision.\n\n**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?**  \nA: 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.\n\n**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?**  \nA: 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.\n\n**References**\n\n[CDG19] Chen, Diakonikolas, and Ge. High-dimensional robust mean estimation in nearly-linear time. SODA, 2019.  \n[CDGW19] Chen, Diakonikolas, Ge, and Woodruff. Faster algorithms for high-dimensional robust covariance estimation. COLT, 2019."}]

Author rebuttal:

Meta-review: The submission provides a framework for perturbation and optimization algorithms in Euclidean Jordan Algebras (EJA). The main application of this idea is in the context of privately solving certain classes of conic programs, far beyond linear optimization. This problem is important, and not enough research has dived into these questions. The work provides an elegant framework for perturbation mechanisms, leveraging structural properties of EJA, in particular certain isometries with the standard Euclidean space. 

This work obtains novel algorithms for privately solving SDPs, a question raised over 10 years ago in a work by Hsu et al. 

There is major agreement on all reviewers that the contributions are significant, and therefore warrant publication in NeurIPS.
Decision: Accept (poster)