acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Algorithms for Packing and Covering Semidefinite Programs

Abstract

We provide differentially private algorithms for solving packing and covering semidefinite programs (SDPs) under the privacy model where neighboring inputs differ by a single constraint. We give efficient polynomial-time algorithms for both packing and covering SDPs that achieve better utility than the state-of-the-art exponential-time algorithm of Song-Xue-Zhang (NeurIPS 2025), which is designed solely for covering SDPs. Our approach builds upon a variant of the dense Multiplicative Weights Update (MWU) framework, and leverages an oracle which computes approximate largest/smallest eigenvectors. The oracle is implemented via a differentially private power iteration, and may be of independent interest.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
packing and covering semidefinite programs, differential privacy

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_5qJgOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This submission studies how to approximately solve packing and coving semidefinite programs under differential privacy. The key idea is to use dense multiplicative weights updates to maintain a distribution over constraints and construct a weighted average of their matrices. A private spectral oracle then finds approximate largest/smallest eigenvectors of this matrix to construct a solution that approximately satisfies most constraints. The proposed method achieves polynomial runtime and improves the stated constraint-violation bound over prior work. Its main technical contribution is a private power method with an eigengap-independent guarantee.

Critical strengths
  1. The paper addresses an important and relatively underexplored problem in the differential privacy literature.
  2. The algorithmic framework is clean and intuitive.
Critical weaknesses
  1. Some notation and definitions remain unclear, making the algorithms difficult to understand. For example, the public target UU seems to play a pivotal role in the proposed approaches, but its role and underlying intuition are not clearly explained. Moreover, the threshold UU in the truncated softmax and softmin functions seems important to the algorithm’s performance, but its influence is not made explicit in the stated lemmas and theorems.
  2. The lack of numerical experiments leaves the practical benefits suggested by the theoretical findings unverified. Experiments are needed to determine whether the proposed algorithms truly improve over existing methods and to assess their computational burden.
Questions for authors
  1. Several mathematical and pseudocode inconsistencies need correction. Claim G.1 states QT≥1/64Q_T\geq 1/64, whereas its proof establishes QT≥1/(64d)Q_T\geq 1/(64d). Eq.(3) seems omit an η\eta term?
  2. How can the public target (V) be obtained while preserving privacy? Remark 1.1 suggests searching over candidate values and applying the exponential mechanism. Could the authors provide more explanations?
2 comments

We thank the reviewer for the valuable feedback

Regarding the threshold UU. The threshold UU is used in the truncated softmax and softmin functions, which is part of the Dense MWU framework. This threshold is not only for the algorithm’s performance but is critical to guarantee the privacy of the algorithm. Intuitively, we want to guarantee constraint-privacy of the SDP, which is the case when a constraint of the SDP can change arbitrarily; therefore we need to guarantee that no constraint has very large weight during the MWU algorithm. This threshold UU and the truncated softmax and softmin functions are to guarantee this condition.

Regarding the experiment: Our paper is mainly theoretical, aiming at the theoretically understanding of the cost of privacy when imposed on packing and covering SDPs. We would like to mention that there is no existing implementation of algorithms private SDPs for comparison; notably the prior algorithm by Song et al. even has exponential runtime. Developing a practical differentially private algorithm would require substantial thought to ensure solution quality and efficiency while guaranteeing privacy. We leave that implementation and experimental study to future work.

We would also like to refer the reviewer to our response to Reviewer X4yZ for the memory and runtime of the algorithm in comparison with the baselines.

Question 1: Thank you for pointing out the typos. Indeed we miss an η\eta is Eq (3). In Claim G1: the revised statement is as follows: For constant cc sufficiently small, with probability at least 51/16051/160, we have QT≥164dQ_{T}\ge\frac{1}{64d}. The lower bound is 164d\frac{1}{64d} instead of 1/641/64. We have made these revisions in the paper.

Question 2: We discuss this assumption in the paper in Remark 1.1 and in our response to Reviewer X4yZ. The algorithm is private for any fixed target VV. The assumption on VV approximating OPTOPT is only for the utility guarantee. To lift this assumption, we assume a known public bound BB on the optimum value of the SDP, and use grid search. We provide the complete algorithm and detailed utility guarantee in our response to Reviewer X4yZ and in the revised paper.

I thank the authors for detailed responses to my concerns. After reading these responses, as well as other reviewer's reports and the responses to them, I believe my concerns have been sufficiently addressed. I am rising my score from 2 to 3.

Reviewer_8RfUOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors give an efficient polynomial algorithm for computing differentially private solutions to packing and covering semidefinite programs. The privacy model is altering a single constraint and they aim to satisfy all but a small number of constraints. This achieves better utility as well as time complexity of the state of the art Song et al which only works for covering SDPs.

Critical strengths
  1. The paper is generally understandable. The structure if very natural in setting up the Multiplicative Weights Update framework and fitting the problem in that setup.

  2. The differentially private power iteration I believe is quite cool and although it is just a means to prove the improvements on these SDP satisfying algorithms, it is worth highlighting.

  3. The algorithmic improvements are significant (exponential to polynomial).

Critical weaknesses
  1. This is a minor one: but I would have appreciated some more description on use cases for when covering or packing SDPs naturally arise where the constraints are differentially private (i.e. maybe 2 sentence example describing a private packing or covering problem).

  2. I think one could argue that this is a niche area and solution that a minority would be interested in. I could go either way on this claim because I think it is significant but not too many people in the privacy community are focused on solving linear programs (although it is a known area of research).

Questions for authors
  1. Are there any experiments or metrics that can support the presented theory on test data? Both from the utility and the speed guarantees? It would be nice to have an example of the SDP set up from private data and compared with Song et al.

  2. What other use cases are there for the differentially private power iteration method?

2 comments

We thank the reviewer for the valuable feedback.

Regarding the applications of packing and covering SDPs and general SDPs with privacy. We provide below a few use cases:

Kernel and metric learning [1, 2, 3]. Clinicians may confidentially annotate pairs of patient cases as similar or dissimilar. A packing SDP learns a metric that keeps similar pairs within a prescribed distance, while a covering SDP learns a metric that keeps dissimilar pairs at least a prescribed distance apart. Each annotation contributes one constraint, so constraint-level differential privacy limits what the released metric reveals about whether any particular annotation was used.

Matrix factorization [4]. A recommender can use an SDP to learn user and item factors from ratings. Rating-level privacy limits what someone can infer about that rating from the released model.

Robust statistics [5, 6]. An SDP can estimate a population mean from clinical measurements even when some measurements are corrupted. The estimate may be shared publicly, while each patient’s participation and measurement are sensitive.

Robust optimization [7]. A planner can use an SDP to design a system that operates across confidential failure scenarios. If each scenario contributes one constraint, constraint-level privacy can limit what the published design reveals about a specific vulnerability.

Regarding the applications of differentially private power iteration method: One application is in differentially private principal component analysis. There is a long line of work that use private power iteration for estimating the top eigenvector and top eigen-subspace [8,9,10,11].

Regarding the experiment: Our paper is mainly theoretical, aiming at theoretically understanding of the cost of privacy when imposed on packing and covering SDPs. Most works in this direction only explore the question. Developing a practical differentially private algorithm would require substantial thought to ensure solution quality and efficiency while guaranteeing privacy. We leave that implementation and experimental study to future work.

References

[1] Lanckriet et al. Learning the Kernel Matrix with Semidefinite Programming. JMLR, 2004.

[2] Xing et al. Distance Metric Learning with Application to Clustering with Side-Information. NeurIPS, 2002.

[3] Weinberger and Saul. Distance Metric Learning for Large Margin Nearest Neighbor Classification. JMLR, 2009.

[4] Srebro, Rennie, and Jaakkola. Maximum-Margin Matrix Factorization. NeurIPS, 2004.

[5] Hopkins and Li. Mixture Models, Robustness, and Sum of Squares Proofs. STOC, 2018.

[6] Cheng, Diakonikolas, and Ge. High-Dimensional Robust Mean Estimation in Nearly-Linear Time. SODA, 2019.

[7] Ben-Tal and Nemirovski. Robust Convex Optimization. Mathematics of Operations Research, 1998.

[8] Moritz Hardt and Aaron Roth. “Beyond Worst-Case Analysis in Private Singular Vector Computation.” STOC, 2013.

[9] Moritz Hardt and Eric Price. “The Noisy Power Method: A Meta Algorithm with Applications.” NeurIPS, 2014.

[10] Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, and Adams Wei Yu. “An Improved Gap-Dependency Analysis of the Noisy Power Method.” COLT, 2016.

[11] Julien Nicolas, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar, and Mark Coates. “Differentially Private and Decentralized Randomized Power Method.” arXiv preprint, 2024.

Reviewer_8RfUOpenReview ↗

Response

Dear Authors,

Thank you for your response, in particular the applications information. These use cases should make their way into the paper beyond the current list of citations in the introduction. I think an applications section in related work is appropriate.

I still maintain a score of 3 because I still have concerns of significance that I mentioned in Critical Weaknesses 2. I do like the result and I am closer to a score of 4 than I was before. I'll keep an open mind to changing my score during the Reviewer-AC discussion period. Best of luck.

-Reviewer 8RfU

Reviewer_K3osOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies differentially private packing and covering semidefinite programs (SDPs). The authors propose efficient polynomial-time algorithms that improve upon the utility guarantees of previous work, which only addressed covering SDPs and required exponential time. Their approach is based on a dense Multiplicative Weights Update (MWU) framework combined with a differentially private power iteration for approximating the largest and smallest eigenvectors.

Critical strengths

The paper is well written, and the proposed techniques are clearly explained and easy to follow. Moreover, the authors establish new state-of-the-art results for the problem, improving upon existing utility guarantees while providing efficient polynomial-time algorithms.

Critical weaknesses

Theorem 1.1 assumes a public target V that approximates OPT, but the motivation and role of this parameter are not sufficiently explained before the theorem. Although this becomes clearer in the technical sections, I believe a brief explanation before would improve readability.

Questions for authors

As a note, the sentence describing the noise parameter in the private power method, particularly the phrase "now can be upper bounded in the spectral norm of the sensitivity of the matrix A" in line 145, is unclear and appears to contain a typo (?).

2 comments

We thank the reviewer for the positive feedback.

Regarding the assumption on the public target VV: We have revised the paper to address this concern by the reviewer. First, we would like to note that our algorithm is private for any fixed target VV. We made this assumption for the simplicity of the paper and to align with private work in this area. This assumption can be lifted as we detailed in our revised paper and also in our response to Reviewer X4yZ.

Question: Indeed, we will clarify the sentence the reviewer pointed out. The noise is calibrated to the Euclidean sensitivity of the matrix–vector query. Since the current iterate has unit norm, this sensitivity is bounded by the spectral-norm sensitivity of the rescaled matrix.

Thank you for the clarifications and revisions. The authors have adequately addressed my concerns and questions, and I have no further comments.

Reviewer_X4yZOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies packing and covering semidefinite programs under constraint-level differential privacy, where neighboring datasets differ by one constraint matrix. Since satisfying every constraint is generally incompatible with privacy, the algorithms allow a bounded number of constraint violations. The authors extend Dense MWU to SDPs and introduce a gap-independent private power-iteration oracle. The resulting algorithms run in polynomial time and improve the dimension dependence of the exception bound from √d, while also improving its dependence on problem width.

Critical strengths

1.The paper improves both runtime and utility guarantees while handling both packing and covering SDPs. This is meaningful progress over the prior exponential-time result for covering alone. 2.The private power method targets Rayleigh-quotient accuracy rather than recovery of a specific eigenvector, avoiding an eigengap assumption. This guarantee fits the adaptive oracle requirements of the outer MWU framework. 3.The method perturbs matrix–vector products rather than the entire matrix. This exploits spectral-norm sensitivity and avoids the additional dimension loss from converting to Frobenius-norm sensitivity. 4.The paper separates the Dense MWU utility analysis from the private spectral-oracle implementation. The Gaussian baseline also helps isolate the contribution of the new oracle.

Critical weaknesses

The algorithm treats N as public, while add/delete adjacency changes the actual number of constraints. The iteration count, privacy allocation, and exception budget depend on N. Although Lemma 4.1 compares instances with N and N−1 constraints, the paper does not fully explain how the complete algorithm uses consistent public parameters across neighbors. It should clarify whether N is the actual size or a fixed public upper bound. The utility guarantee assumes a public value V approximating the private optimum within 1±α/20. This is a strong auxiliary-information assumption. The proposed guessing-and-selection workaround lacks a complete specification of the search range, score sensitivity, and additional privacy and utility costs.

Questions for authors
  1. Is N the actual constraint count or a public capacity bound? How are the iteration count and privacy parameters kept consistent when one constraint is added or removed?
  2. Could you provide a complete algorithm without the accurate public target V, including its additional privacy cost, exception budget, and runtime?
  3. Please clarify whether Theorem H.2 should have √d dependence, and state the correct lower bound and success probability in Claim G.1.
  4. What are the total matrix–vector multiplication count, memory cost, and numerical-precision requirements? How much additional computation is needed for the utility improvement over the Gaussian baseline?
1 comment

We thank the reviewer for the valuable feedback. We answer your questions below.1.

  1. Regarding NN: we use NN as the fixed and publicly known number of constraints. To avoid confusion over this quantity, we have revised the paper so that neighboring inputs differ by the replacement of one constraint (instead of addition or deletion of one constraint), so neighboring inputs have the same constraint count. NN is treated as a public quantity in all prior works.

  2. The complete algorithm without the accurate public target is as follows: We added the complete algorithm to the appendix of the paper. The idea of the algorithm is following. We assume that there is a public upperbound BB on the optimum of the SDP and the known public bound Λmax⁡\Lambda_{\max} for the spectrum (the algorithm is always private for all instances while can guarantee the utility on instances satisfying these public bounds). Define K=1+ln⁡Λmax⁡Bln⁡(1+α/20)K=1+\ln\frac{\Lambda_{\max}B}{\ln\left(1+\alpha/20\right)} and Vj=(1+α/20)j/Λmax⁡V_{j}=\left(1+\alpha/20\right)^{j}/\Lambda_{\max}. For each VjV_{j} we run the algorithm for fixed target in the paper with parameters ϵg=ϵ42Kln⁡(2/δ),δg=δ2K\epsilon_{g}=\frac{\epsilon}{4\sqrt{2K\ln(2/\delta)}},\delta_{g}=\frac{\delta}{2K} and βg=β2\beta_{g}=\frac{\beta}{2}. Then we select among these outputs by the number of violated constraints. Let CjC_{j} be the actual number of violated constraints for target VjV_{j} and sj=min⁡{N,s0(Vj)}s_{j}=\min\left\{ N,s_{0}\left(V_{j}\right)\right\} is the target number of violated constraints. We can scan the output in the increasing order of VjV_{j} for covering and decreasing order for packing. Run AboveThreshold algorithm with privacy budget ϵs=ϵ2\epsilon_{s}=\frac{\epsilon}{2} and return the first candidate satisfying Cj+vj≤sj+2a+ξC_{j}+v_{j}\le s_{j}+2a+\xi where vj∼Lap(4/ϵs),ξ∼Lap(2/ϵs)v_{j}\sim Lap(4/\epsilon_{s}), \xi\sim Lap(2/\epsilon_{s}) and a=4ϵsln⁡2(K+1)βa=\frac{4}{\epsilon_{s}}\ln\frac{2(K+1)}{\beta}. The final guarantee is $s\le \min\left\{ N,\widetilde{O}\left(\frac{\sqrt{Kd} \left(\Lambda_{\max}Z\right)^{3/2}\sqrt{\log N}}{\alpha^{2}\epsilon}+\frac{1}{\epsilon}\ln\frac{K}{\beta}\right)\right\} $, where Z=OPTZ=OPT for covering and Z=BZ=B for packing. The complete algorithm only changes the bound given in the paper and runtime of the algorithm by log factors. Regarding the runtime of the algorithm in the paper, we answer in Q4.

  3. Typos: There is a typo in Theorem H.2. The dependence on dd is linear, ie, s\le\min\left\\{ N,\widetilde{O}\left(\frac{d\,W^{3/2}\sqrt{\log N}}{\alpha^{2}\epsilon}\right)\right\\}, worse than our algorithm by a factor d\sqrt{d}. This is where our algorithm improves. Claim G1. Thank you for spotting the typo. The revised statement is as follows: For constant c sufficiently small, with probability at least 51/160, we have QT≥164dQ_{T}\ge\frac{1}{64d}.

  4. Comparison between private power iteration and Gaussian oracle. The algorithm using two sided private power iteration as written uses (Λmax⁡V)2log⁡Nα3\frac{\left(\Lambda_{\max}V\right)^{2}\log N}{\alpha^{3}} matrix–vector products.

Total runtime:

Gaussian: O(Λmax⁡Vlog⁡Nα2d3)O\left(\frac{\Lambda_{\max}V\log N}{\alpha^{2}}d^{3}\right)

Private power iteration: ((Λmax⁡V)2log⁡Nα3d2)\left(\frac{\left(\Lambda_{\max}V\right)^{2}\log N}{\alpha^{3}}d^{2}\right)

Memory: Apart from the input, both uses O(d2+N),O(d2)O\left(d^{2}+N\right), O\left(d^{2}\right) for the d2d^{2} entries of the iterate matrices and NN weights for the constraints.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.