Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)
Jerry Li, Guanghao Ye
Robust covariance estimation is the following, well-studied problem in high dimensional statistics: given N samples from a d-dimensional Gaussian \mathcal{N}(\boldsymbol{0}, \Sigma), but where an \varepsilon-fraction of the samples have been arbitrarily corrupted, output \widehat{\Sigma} minimizing the total variation distance between \mathcal{N}(\boldsymbol{0}, \Sigma) and \mathcal{N}(\boldsymbol{0}, \widehat{\Sigma}). This corresponds to learning \Sigma in a natural affine-invariant variant of the Frobenius norm known as the \emph{Mahalanobis norm}. Previous work of Cheng et al demonstrated an algorithm that, given N = \widetilde{\Omega}(d^2 / \varepsilon^2) samples, achieved a near-optimal error of O(\varepsilon \log 1 / \varepsilon), and moreover, their algorithm ran in time \widetilde{O}(T(N, d) \log \kappa / \mathrm{poly} (\varepsilon)), where T(N, d) is the time it takes to multiply a d \times N matrix by its transpose, and \kappa is the condition number of \Sigma. When \varepsilon is relatively small, their polynomial dependence on 1/\varepsilon in the runtime is prohibitively large. In this paper, we demonstrate a novel algorithm that achieves the same statistical guarantees, but which runs in time \widetilde{O} (T(N, d) \log \kappa). In particular, our runtime has no dependence on \varepsilon. When \Sigma is reasonably conditioned, our runtime matches that of the fastest algorithm for covariance estimation without outliers, up to poly-logarithmic factors, showing that we can get robustness essentially for free.''