A Fast Algorithm for Adaptive Private Mean Estimation

A Google TechTalk, presented by John Duchi, 2023-02-08 Privacy ML series. 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 ||⋅||Σ. Paper: https://arxiv.org/abs/2301.07078