Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy
This addresses the fundamental privacy-accuracy trade-off in high-dimensional statistical estimation for data analysts and privacy researchers, representing a strong theoretical advance rather than an incremental improvement.
This paper tackles the problem of estimating high-dimensional bandable covariance matrices under differential privacy constraints, proposing a novel differentially private blockwise tridiagonal estimator that achieves minimax-optimal convergence rates under operator and Frobenius norms, with privacy-induced error showing polynomial dependence on dimension. It also introduces an adaptive estimator that attains near-optimal rates without prior knowledge of decay parameters.
The covariance matrix plays a fundamental role in the analysis of high-dimensional data. This paper studies minimax and adaptive estimation of high-dimensional bandable covariance matrices under differential privacy constraints. We propose a novel differentially private blockwise tridiagonal estimator that achieves minimax-optimal convergence rates under both the operator norm and the Frobenius norm. In contrast to the non-private setting, the privacy-induced error exhibits a polynomial dependence on the ambient dimension, revealing a substantial additional cost of privacy. To establish optimality, we develop a new differentially private van Trees inequality and construct carefully designed prior distributions to obtain matching minimax lower bounds. The proposed private van Trees inequality applies more broadly to general private estimation problems and is of independent interest. We further introduce an adaptive estimator that attains the optimal rate up to a logarithmic factor without prior knowledge of the decay parameter, based on a novel hierarchical tridiagonal approach. Numerical experiments corroborate the theoretical results and illustrate the fundamental privacy-accuracy trade-off.