[edit]
A Pretty Fast Algorithm for Adaptive Private Mean Estimation
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2511-2551, 2023.
Abstract
We design an (ε,δ)-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 ||⋅||Σ, takes time ˜O(nd2) 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=Ω(d3/2) to achieve non-trivial error with respect to the norm ||⋅||Σ.