Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

Zihan Zhang

cs.LGSep 19, 2026

Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

Authors: Zihan Zhang

Organizations: Department of CSE, HKUST

Abstract

We study differentially private covariance estimation in operator norm for mean-zero sub-Gaussian distributions with unknown covariance support and at most $k$ nonzero entries per row. We develop a multiscale random-threshold algorithm with sample complexity $\ot(k^2/α^2+k\sqrt d/(α\varepsilon))$ for $(\varepsilon,δ)$ -differential privacy and error at most $ασ^2$ , where $d$ is the dimension and $σ$ is a known sub-Gaussian scale. The bound improves the privacy-dependent term of the existing $\ot(k^2/α^2+k^{3/2}\sqrt d/(α\varepsilon))$ \citep{kumar2026curse} upper bound by a factor of $\sqrt k$ , and matches the lower bound of $\widetildeΩ(k^2/α^2 + k\sqrt{d}/(α\varepsilon))$ 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. A multiscale allocation of threshold tests balances reconstruction variance against query sensitivity. Together, these ingredients sharpen the trade-off between approximation error and privacy protection, removing the additional $\sqrt{k}$ factor from the privacy-dependent sample complexity.

Explore similar work

Jun 20, 2026cs.LG

On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA

We study high-dimensional differentially private (DP) covariance estimation in the operator norm, and principal component analysis (PCA), under

k

-row-column sparsity (

k

-RCS) of the covariance matrix. In the non-private setting, it is known that

\mathsf{poly}(k, \log d)

samples suffice to solve both of these problems. However, the only comparable result known under DP (Wang et al. 2021) requires

Ω(d)

samples under standard parameterizations of the problem. We investigate when this curse of dimensionality is inherent for sparse covariance estimation tasks under DP. On the upper bound front, we show that a

\mathsf{poly}(k, \log d)

sample complexity for PCA is possible under DP, if we also posit sparsity of the leading eigenvector. We complement this result with

\mathsf{poly}(d)

lower bounds under DP for both sparse covariance estimation and PCA, establishing an exponential gap between the private and non-private variants of these problems when

k = \mathsf{polylog}(d)

. To our knowledge, no such separation has previously been demonstrated for any sparse estimation problems in private high-dimensional statistics. Our techniques are flexible enough that they imply stronger lower bounds even for the well-studied problem of standard DP PCA, without sparsity assumptions.

Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar +1

University of Texas at Austin

Principal Component Analysis Minimax Estimation Differential Privacy Covariance Estimation

Ask PDF

May 22, 2026cs.LG

Private Adaptive Covariance Estimation via Gaussian Graphical Models

We propose PACE-GGM, a data-adaptive differentially private method for covariance estimation that concentrates its privacy budget on the most informative entries of the empirical covariance matrix, rather than perturbing all entries. This applies in the natural setting where the modeler supplies separate bounds for each variable, so that individual entries can be measured with less noise than the full matrix. In each round, our method selects a poorly approximated entry, measures it using the Gaussian mechanism, and then reconstructs a full covariance matrix using a maximum-entropy reconstruction objective, leading to a Gaussian graphical model structure. Experiments on diverse real-world datasets demonstrate consistent improvements in estimation error with respect to the Gaussian mechanism and other baselines, particularly in high-dimensional and low-to-moderate privacy regimes.

Cecilia Ferrando, Miguel Fuentes, Brett Mullins +2

Manning College of Information and Computer Sciences University of Massachusetts Amherst

Differential Privacy Covariance Estimation

Ask PDF

May 27, 2026cs.CR

Privately Estimating Monotone Statistics in Polynomial Time

We study efficient differentially private algorithms for estimating monotone statistics, i.e., statistics that are monotone under the addition of new observations. The starting point for our investigation is subsample-and-aggregate: a classical paradigm that partitions the dataset into blocks, estimates the statistic on each block, and then privately aggregates the estimates. While practical and generically applicable, this approach is quite data-hungry. We improve upon this framework for the class of monotone statistics -- compared to subsample-and-aggregate, our algorithms save a factor of

t

in sample complexity and pay a factor of

e^t

in running time, where

t>0

is a tunable parameter. We complement our results with a query-complexity lower bound, showing that our algorithms are essentially optimal for this task. As an application, we obtain improved results for private eigenvalue estimation, private loss estimation, and privately estimating a single parameter of a high-dimensional model, e.g., in linear regression.

Gavin Brown, Ephraim Linder, Mahbod Majid +1

University of Wisconsin–Madison · Boston University · MIT Mathematics +1

Sample Complexity Differential Privacy

Ask PDF