TY - JOUR

T1 - Estimating principal components under adversarial perturbations

AU - Awasthi, Pranjal

AU - Chen, Xue

AU - Vijayaraghavan, Aravindan

N1 - Publisher Copyright:
Copyright © 2020, The Authors. All rights reserved.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/5/31

Y1 - 2020/5/31

N2 - 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 ℓq norm, say ℓ∞. 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 → 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 → 2 operator norm of the subspace essentially characterizes the estimation error under adversarial perturbations.

AB - 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 ℓq norm, say ℓ∞. 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 → 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 → 2 operator norm of the subspace essentially characterizes the estimation error under adversarial perturbations.

UR - http://www.scopus.com/inward/record.url?scp=85095064770&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85095064770&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85095064770

JO - Free Radical Biology and Medicine

JF - Free Radical Biology and Medicine

SN - 0891-5849

ER -