Estimating Principal Components under Adversarial Perturbations

Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:323-362, 2020.

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 {\em adversarial perturbation model}. An adversary can perturb {\em 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 {\em low precision machine learning} and {\em 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 {\em every} instance of the problem. This {\em instance-optimal} guarantee shows that the $q \to 2$ operator norm of the subspace essentially {\em characterizes} the estimation error under adversarial perturbations.

Cite this Paper


BibTeX
@InProceedings{pmlr-v125-awasthi20a, title = {Estimating Principal Components under Adversarial Perturbations}, author = {Awasthi, Pranjal and Chen, Xue and Vijayaraghavan, Aravindan}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {323--362}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/awasthi20a/awasthi20a.pdf}, url = {https://proceedings.mlr.press/v125/awasthi20a.html}, 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 {\em adversarial perturbation model}. An adversary can perturb {\em 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 {\em low precision machine learning} and {\em 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 {\em every} instance of the problem. This {\em instance-optimal} guarantee shows that the $q \to 2$ operator norm of the subspace essentially {\em characterizes} the estimation error under adversarial perturbations.} }
Endnote
%0 Conference Paper %T Estimating Principal Components under Adversarial Perturbations %A Pranjal Awasthi %A Xue Chen %A Aravindan Vijayaraghavan %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-awasthi20a %I PMLR %P 323--362 %U https://proceedings.mlr.press/v125/awasthi20a.html %V 125 %X 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 {\em adversarial perturbation model}. An adversary can perturb {\em 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 {\em low precision machine learning} and {\em 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 {\em every} instance of the problem. This {\em instance-optimal} guarantee shows that the $q \to 2$ operator norm of the subspace essentially {\em characterizes} the estimation error under adversarial perturbations.
APA
Awasthi, P., Chen, X. & Vijayaraghavan, A.. (2020). Estimating Principal Components under Adversarial Perturbations. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:323-362 Available from https://proceedings.mlr.press/v125/awasthi20a.html.

Related Material