- 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
- The paper addresses an important and relatively underexplored problem in the differential privacy literature.
- The algorithmic framework is clean and intuitive.
Critical weaknesses
- Some notation and definitions remain unclear, making the algorithms difficult to understand. For example, the public target seems to play a pivotal role in the proposed approaches, but its role and underlying intuition are not clearly explained. Moreover, the threshold 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.
- 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
- Several mathematical and pseudocode inconsistencies need correction. Claim G.1 states , whereas its proof establishes . Eq.(3) seems omit an term?
- 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
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.
We thank the reviewer for the valuable feedback
Regarding the threshold U. The threshold U 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 U 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 η is Eq (3). In Claim G1: the revised statement is as follows: For constant c sufficiently small, with probability at least 51/160, we have QT≥64d1. The lower bound is 64d1 instead of 1/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 V. The assumption on V approximating OPT is only for the utility guarantee. To lift this assumption, we assume a known public bound B 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.