acceptodds
Withdrawn from ICLR 2027

Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We study differentially private covariance estimation in operator norm for mean-zero sub-Gaussian distributions with unknown covariance support and at most nonzero entries per row. We develop a multiscale random-threshold algorithm with sample complexity for -differential privacy and error at most , where is the dimension and is a known sub-Gaussian scale. The bound improves the privacy-dependent term of the existing kumar2026curse upper bound by a factor of , and matches the lower bound of in its applicable parameter regime. Our key technical ingredient is a direct operator-norm bound on the centered fluctuations of an ideal reconstruction, exploiting conditional independence rather than accumulating entrywise errors across each row. Combined with a multiscale test allocation that balances reconstruction variance against query sensitivity, this bound removes the additional factor from the privacy-dependent sample complexity.

Primary area:
learning theory
Keywords:
Differential privacy, optimal sample complexity, sparse covariance estimation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_JsC6OpenReview ↗
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?

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

This paper studies differentially private (DP) covariance estimation under row/column sparsity constraints. In other words, they assume at most kk non-zero entries per row/column of the covariance. They match a lower bound of Kumar et al. (2026) for a specific parameter regime by removing a multiplicative factor of kk from the sample complexity. Their techniques are built upon those of the said prior work, and the results here are pretty much theoretical.

Critical strengths
  1. Matching the lower bound. albeit in specific parameter regimes, that was previously provided by Kumar at al. (2026).
Critical weaknesses
  1. The problem seems a bit too niche. As in, we see a lot of DP covariance estimation papers, and I'm sure their setting has some applications, but they didn't motivate the work enough, except for saying that we just close a gap of some problem. In that sense, the results seem incremental, especially given that the lower bound only exists for a specific parameter regime. I'm having a hard time determining the strengths of this work (besides what I already wrote) because the authors are not really talking about the significance or the impact of their work on the vast DP literature.
  2. The writing is very below-par -- to the extent that I am mostly recommending a reject because of that. Understanding the algorithm was really hard, and I have been working in DP for several years at this point. I would strongly recommend a rewrite of this work because as of now, it looks like the authors have not made much effort to improve the exposition beyond an LLM provided. This comment is purely about the writing quality, and I'm in no way questioning the authors' efforts in terms of the scientific development. I could be wrong about what I said about the writing, as well, in which case, I apologise. However, I still stand by the fact that this paper is very hard to follow, and I don't think it's just because the technical ideas are super complicated. I am writing my feedback/questions regarding the writing below; please, note that I'm not writing all of my concerns about the specifics of the writing because I can only do so much.
Questions for authors

I'm using this for both questions and comments.

  1. Please, use [DMNS'06] as the citation for DP.
  2. Intro, technical ingredients. What do you mean by "randomized reconstruction"? This term has not been defined anywhere yet. This entire paragraph is very confusing and unclear. A lot is being said in here just as plain statements, without any intuitive explanation behind these things. E.g., "whose contributions vanish outside the support of Σ\Sigma" -- this has no meaning because the reason and significance of this is not being conveyed. I would strongly recommend rewriting this paragraph. I would not assume that the reader knows or understands the prior works that you might be building on. The notations are also not defined anywhere before, for example, the "max" operator is defined in the prelims. Point (ii): What "position" are we talking about?
  3. The second paragraph of Section 3. This explanation makes no sense if I don't already know the prior work of Kumar et al. (2026). Please, rewrite to make it comprehensible. This is not really adding anything because you're explaining things later anyway.
  4. Section 3. Pre-processing. You're using the word "threshold" a lot in different contexts. It is getting quite confusing. Here, do you just mean the clipping parameter RR?
  5. Section 3. Stage 1. What are "scale" and "repetition index"?
Reviewer_bgbtOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This work investigates sparse covariance estimation under approximate central differential privacy. Given nn iid samples from a σ\sigma-sub-Gaussian distribution PP with mean zero and kk-row-column sparse covariance Σ\Sigma, the authors seek to estimate Σ\Sigma up to error ασ2\alpha \sigma^2 w.h.p. while satisfying (ϵ,δ)(\epsilon, \delta) differential privacy.

The authors give an algorithm which solves this problem given O~(k2α2+kdαϵ)\tilde{O}\left(\frac{k^2}{\alpha^2} + \frac{k \sqrt{d}}{\alpha \epsilon}\right) samples. This bound matches the lower bound for the problem and improves the privacy-dependent term of existing upper bounds by a factor of k\sqrt{k} (Kumar et al, 2026).

The algorithm first clips the datapoints to a set threshold, then computes the empirical covariance matrix of the clipped dataset. It then selects entries from the empirical covariance, along with weights for these entries, using a series of threshold tests. Finally, it outputs a noisy weighted sum of the selected entries.

Critical strengths
  • The authors develop a novel private algorithm and prove that its guarantees match the lower bound of differentially private sparse covariance estimation. This is a tight result and improves upon the best known upper bound by a factor of k\sqrt{k} in the privacy-dependent term. This establishes the significance of their result.
Critical weaknesses
  • The paper is written in such a way that is very difficult to understand. It introduces new terms without enough context (ex: saying "private selection" without saying what is being selected) and new variables that may not be necessary (ex: Σˉe(S)\bar{\Sigma}_e(S) represents E[Σeid∣S]E[\Sigma_e^{id} \mid S]). Further, while the paper explains the different steps of the algorithm and the proofs, it does not do a great job of explaining the intuition behind them. For example, it would be helpful to explain how the "privatization" steps of the algorithm relate to standard DP mechanisms like randomized response. This lack of clarity is the main reason for my score.
  • While the paper does close a gap between upper and lower bounds, the significance of this gap is unclear. The improvement is only in terms of kk, the sparsity parameter, which may be <<d<< d in some cases, and therefore relatively unimportant in the bound. Additionally, the paper's bound introduces additional logarithmic dependencies with on kk and large constants, which may further undermine the significance of the improved asymptotic bound.
Questions for authors

Please comment on the significance of improving the upper bound by a factor of k\sqrt{k}. When is kk not much smaller than dd?

The authors mention that their results do not impose an eigengap condition. Does (Kumar et al, 2026), or other related works, make an eigengap assumption? Given a brief read of the paper, it seems like their eigengap assumption is only needed for sparse PCA.

What is the runtime of this algorithm and how does it compare to prior works?

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

Related papers

Discussion (0)

Sign in to comment.