Estimating Principal Components under Adversarial Perturbations

Abstract

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 $\delta$ 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 $\kappa$ 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 $\kappa$ 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.

arXiv commentIt is to appear at COLT 2020

References in corpus (16)

• Adversarially Robust Generalization Requires More Data
• Robustness May Be at Odds with Accuracy
• Sparse principal component analysis and iterative thresholding
• Learning Adversarially Fair and Transferable Representations
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• A direct formulation for sparse PCA using semidefinite programming
• Rademacher Complexity for Adversarially Robust Generalization
• Adversarial Robustness May Be at Odds With Simplicity
• High-Accuracy Low-Precision Training
• Efficient Algorithms for Outlier-Robust Regression
• Adversarial Risk Bounds via Function Transformation
• Robust Sparse Estimation Tasks in High Dimensions
• Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
• On Robustness to Adversarial Examples and Polynomial Optimization
• Adversarially Robust Low Dimensional Representations
• Squared-Norm Empirical Process in Banach Space