Row-Private Symmetric Cone Programming: Scale-Efficient Algorithm and Lower Bound

We study the row-private approximate feasibility problem for symmetric cone programs (SCPs), a framework that encompasses linear, second-order cone, and semidefinite programming. We focus on high-sensitivity row privacy, where each record is a constraint and changing one record can cause the feasible region to change discontinuously. Since satisfying every private row is generally impossible in this regime, the goal is to remain exactly in the public cone while violating only a small number of private rows under a prescribed additive error $\eta>0$. We give an efficient $(\varepsilon, \delta)$-differentially private SCP solver with violation count $\widetilde{O}\left(k^2/\varepsilon\right)$, and only logarithmic dependence on the scale-to-error ratio $UR/\eta$, where $k$ is the ambient dimension, $R$ is the norm of some feasible point, and $U$ is the size of the problem. This exponentially improves the polynomial dependence on $U$, $R$, and $1/\eta$ in prior work (Song, Xue, and Zhang, NeurIPS 2025). Furthermore, we show that additive error does not remove the intrinsic dimension-dependence barrier. Previous row-private LP lower bounds (Kaplan, Mansour, Moran, Stemmer, and Tur, STOC 2025) established an $\Omega(k/\varepsilon)$ violation count only for exact partial satisfaction; using the padding-and-permuting fingerprinting codes (Peter, Tsfadia, and Ullman, COLT 2024), we prove the same barrier for relaxed satisfaction.