- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies differentially private covariance estimation under row-sparsity assumptions, improving the best-known upper bound by a factor of \sqrt{k} to match the existing lower bound. The main technical contribution is a multiscale, randomly weighted representation of the clipped empirical covariance matrix, which preserves the underlying sparsity structure without requiring explicit support recovery. This allows the authors to apply matrix concentration directly in operator norm, avoiding the additional error introduced by entrywise analysis.
Critical strengths
The paper presents novel theoretical results, improving upon the state of the art and matching the existing lower bound. While I found the technical analysis somewhat challenging to follow in detail, the proposed approach appears sound and technically interesting. Based on my understanding, the authors successfully achieve the claimed tight bounds, representing a meaningful contribution to the field.
Critical weaknesses
As noted in the strengths, I found the technical analysis difficult to follow in detail, making it challenging to understand how the different components interact and contribute to the final guarantees. I believe the paper would benefit from a clearer presentation of its analysis.
Questions for authors
It would be interesting to discuss the connection between the row-sparsity assumption considered in this paper and the subsamplability assumption studied in [A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input (NeurIPS 2025); Mahpud et al.]. Although these assumptions capture different structural properties, both enable improved private covariance or second-moment estimation. Could the authors clarify the relationship between these assumptions and whether their techniques could be extended to subsamplable inputs?