A Fast Algorithm for Adaptive Private Mean Estimation
This work addresses the challenge of efficient and adaptive private mean estimation for data analysis, offering significant improvements over prior methods that required exponential computation or higher sample complexity.
The paper tackles the problem of estimating the mean of a multivariate distribution with unknown covariance under differential privacy constraints, achieving optimal convergence rates with near-linear sample complexity and efficient computation time, while allowing for degenerate or low-rank covariance and extending beyond sub-Gaussian distributions.
We design an $(\varepsilon, δ)$-differentially private algorithm to estimate the mean of a $d$-variate distribution, with unknown covariance $Σ$, that is adaptive to $Σ$. To within polylogarithmic factors, the estimator achieves optimal rates of convergence with respect to the induced Mahalanobis norm $||\cdot||_Σ$, takes time $\tilde{O}(n d^2)$ to compute, has near linear sample complexity for sub-Gaussian distributions, allows $Σ$ to be degenerate or low rank, and adaptively extends beyond sub-Gaussianity. Prior to this work, other methods required exponential computation time or the superlinear scaling $n = Ω(d^{3/2})$ to achieve non-trivial error with respect to the norm $||\cdot||_Σ$.