Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy

T. Tony Cai; Yicheng Li

math.STMar 20, 2026

Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy

Authors: T. Tony Cai, Yicheng Li

Organizations: Department of Statistics and Data Science, The Wharton School, University of Pennsylvania · KLATASDS-MOE, School of Statistics, East China Normal University

Abstract

Estimating covariance matrices is fundamental to a wide range of statistical applications. This paper studies minimax and adaptive estimation of high-dimensional covariance matrices under $ρ$ -zero-concentrated differential privacy ( $ρ$ -zCDP) over three nested classes: the pointwise-decay class $\mathcal{H}_α$ , the row-tail class $\mathcal{G}_α$ , and the separated-block class $\mathcal{F}_α$ . We consider both squared operator norm loss and normalized squared Frobenius norm loss. For $\mathcal{H}_α$ and $\mathcal{G}_α$ , we develop center--outer dyadic estimators tailored to the refined geometry of the two classes, while for $\mathcal{F}_α$ , we develop a blockwise tridiagonal estimator. The resulting minimax-optimal rates reveal a nontrivial interplay among the smoothness $α$ , the loss, the geometry of the covariance class, and the privacy constraint. In contrast to the non-private setting, privacy distinguishes covariance classes that share the same leading non-private rate and induces a polynomial dependence on the ambient dimension. We further develop procedures that adapt to the unknown decay parameter over all three covariance classes under both losses, at the cost of at most polylogarithmic factors. To establish minimax lower bounds, we develop a novel differentially private van Trees inequality that connects Fisher information with the $ρ$ -zCDP constraint and may be useful for other private estimation problems. We also construct carefully designed prior distributions to obtain matching minimax lower bounds.

Figures & tables

	Non-private rate		Cost of privacy
Class	Operator	Frobenius	Operator	Frobenius
$\mathcal{F}_{\alpha}$	$n^{-\frac{2\alpha}{2\alpha+1}}$	$n^{-\frac{2\alpha}{2\alpha+1}}$	$x^{\frac{\alpha}{\alpha+1}}$	$x^{\frac{\alpha}{\alpha+1}}$
$\mathcal{G}_{\alpha}$	$n^{-\frac{2\alpha}{2\alpha+1}}$	$n^{-\frac{2\alpha+1}{2\alpha+2}}$	$\displaystyle x^{\frac{2\alpha}{2\alpha+1}}\vee x^{\frac{2\alpha+1}{2\alpha+3}}$ (log)	$x^{\frac{2\alpha+1}{2\alpha+3}}$ (log)
$\mathcal{H}_{\alpha}$	$n^{-\frac{2\alpha}{2\alpha+1}}$	$n^{-\frac{2\alpha+1}{2\alpha+2}}$	$\displaystyle x^{\frac{2\alpha}{2\alpha+1}}\vee x^{\frac{2\alpha+1}{2\alpha+3}}$ (log)	$x^{\frac{2\alpha+1}{2\alpha+3}}$

Table 1: Leading algebraic terms under squared operator and normalized squared Frobenius losses in the high-dimensional regime. Logarithmic factors suppressed. Denote

x=d/(\rho n^{2})

. The marker “(log)” indicates a fixed polylogarithmic gap between the current upper and lower bounds.

Figure 1: Dyadic block structure at bandwidths

k

and

2k

Panel of Figure 2 — Figure 2: Multiscale block construction and local release modules.

s_{t}(X,H)=\frac{1}{n}\sum_{i=1}^{n}\chi_{L}\left(\xi(u^{\top}X_{i,I})(v^{\top}X_{i,J})\right)-\langle B_{t-1},H\rangle_{F}.

Algorithm 4 Greedy Rank-One Block Estimator

\widehat{j}_{k}=\max\left\{j:\max_{B\in\mathcal{B}_{k}}\left\lVert{Z_{B,k,j}-Z_{B,k,i}}\right\rVert_{\star}\leq D_{k,j}+D_{k,i}\text{ for every }i<j\right\}.

Algorithm 8 DP Adaptive Multiscale Block Estimator

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Partitioning overlapping blocks into groups with disjoint blocks.

Figure 4: An illustration of the blockwise prior distribution.

Figure 5: Comparison of the true covariance matrix and the estimators.

Figure 6: Squared operator norm errors of the DP blockwise tridiagonal estimator under different privacy budgets.

Panel of Figure 7 — Figure 7: Log squared operator norm errors under two asymptotic regimes; the upper row uses the estimator with the true decay parameter, the lower row the adaptive estimator, and the left and right columns correspond to the regimes dominated by statistical error and privacy error, respectively. Error bars show the empirical standard deviation on the log scale.

Panel of Figure 8 — Figure 8: Squared operator norm errors for the adaptive estimator and estimators using fixed decay parameters.

Covariance Estimation

Covariance estimation develops methods for learning dependence and uncertainty structure from noisy, incomplete, or high-dimensional data.

See all 60 papers

May 22, 2026

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

Sep 19, 2026

Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

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.

Zihan Zhang

Department of CSE, HKUST

Covariance Estimation Differential Privacy

Ask PDF

Jun 20, 2026

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

Abstract

Covariance Estimation

Explore similar work

Private Adaptive Covariance Estimation via Gaussian Graphical Models

Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

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