  We design an $(\varepsilon, \delta)$-differentially private algorithm to
estimate the mean of a $d$-variate distribution, with unknown covariance
$\Sigma$, that is adaptive to $\Sigma$. To within polylogarithmic factors, the
estimator achieves optimal rates of convergence with respect to the induced
Mahalanobis norm $||\cdot||_\Sigma$, takes time $\tilde{O}(n d^2)$ to compute,
has near linear sample complexity for sub-Gaussian distributions, allows
$\Sigma$ 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 = \Omega(d^{3/2})$ to achieve
non-trivial error with respect to the norm $||\cdot||_\Sigma$.

Machine Learning;Cryptography and Security;Data Structures and Algorithms;Machine Learning