Estimating Principal Components under Adversarial Perturbations
This work addresses robustness in high-dimensional statistical estimation for applications like low-precision machine learning and adversarial training, providing instance-optimal guarantees for a classical problem.
The paper tackles the problem of estimating the top-r principal subspace of a Gaussian covariance matrix under adversarial perturbations, where each sample can be arbitrarily perturbed up to a specified magnitude. It designs a computationally efficient algorithm that recovers the subspace with error depending on a robustness parameter κ, and proves that this dependence is nearly optimal for every instance, showing that the q→2 operator norm of the subspace characterizes the error.
Robustness is a key requirement for widespread deployment of machine learning algorithms, and has received much attention in both statistics and computer science. We study a natural model of robustness for high-dimensional statistical estimation problems that we call the adversarial perturbation model. An adversary can perturb every sample arbitrarily up to a specified magnitude $δ$ measured in some $\ell_q$ norm, say $\ell_\infty$. Our model is motivated by emerging paradigms such as low precision machine learning and adversarial training. We study the classical problem of estimating the top-$r$ principal subspace of the Gaussian covariance matrix in high dimensions, under the adversarial perturbation model. We design a computationally efficient algorithm that given corrupted data, recovers an estimate of the top-$r$ principal subspace with error that depends on a robustness parameter $κ$ that we identify. This parameter corresponds to the $q \to 2$ operator norm of the projector onto the principal subspace, and generalizes well-studied analytic notions of sparsity. Additionally, in the absence of corruptions, our algorithmic guarantees recover existing bounds for problems such as sparse PCA and its higher rank analogs. We also prove that the above dependence on the parameter $κ$ is almost optimal asymptotically, not just in a minimax sense, but remarkably for every instance of the problem. This instance-optimal guarantee shows that the $q \to 2$ operator norm of the subspace essentially characterizes the estimation error under adversarial perturbations.