Adversarially Robust Low Dimensional Representations

Abstract

Many machine learning systems are vulnerable to small perturbations made to inputs either at test time or at training time. This has received much recent interest on the empirical front due to applications where reliability and security are critical. However, theoretical understanding of algorithms that are robust to adversarial perturbations is limited. In this work we focus on Principal Component Analysis (PCA), a ubiquitous algorithmic primitive in machine learning. We formulate a natural robust variant of PCA where the goal is to find a low dimensional subspace to represent the given data with minimum projection error, that is in addition robust to small perturbations measured in ${\ell }_q$ norm (say $q=\infty$). Unlike PCA which is solvable in polynomial time, our formulation is computationally intractable to optimize as it captures a variant of the well-studied sparse PCA objective as a special case. We show the following results: -Polynomial time algorithm that is constant factor competitive in the worst-case with respect to the best subspace, in terms of the projection error and the robustness criterion. -We show that our algorithmic techniques can also be made robust to adversarial training-time perturbations, in addition to yielding representations that are robust to adversarial perturbations at test time. Specifically, we design algorithms for a strong notion of training-time perturbations, where every point is adversarially perturbed up to a specified amount. -We illustrate the broad applicability of our algorithmic techniques in addressing robustness to adversarial perturbations, both at training time and test time. In particular, our adversarially robust PCA primitive leads to computationally efficient and robust algorithms for both unsupervised and supervised learning problems such as clustering and learning adversarially robust classifiers.

arXiv comment68 pages including references

References in corpus (22)

• Theoretically Principled Trade-off between Robustness and Accuracy
• Adversarially Robust Generalization Requires More Data
• Robustness May Be at Odds with Accuracy
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Hypercontractivity, Sum-of-Squares Proofs, and their Applications
• Adversarial examples from computational constraints
• Rademacher Complexity for Adversarially Robust Generalization
• Learning mixtures of separated nonspherical Gaussians
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Adversarial Robustness May Be at Odds With Simplicity
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization
• Outlier-robust moment-estimation via sum-of-squares
• Better Agnostic Clustering Via Relaxed Tensor Norms
• PAC-learning in the presence of evasion adversaries
• On Robustness to Adversarial Examples and Polynomial Optimization
• Adversarial Examples from Cryptographic Pseudo-Random Generators
• A Spectral View of Adversarially Robust Features
• Approximation Algorithms for Sparse Principal Component Analysis
• Approximating Operator Norms via Generalized Krivine Rounding
• Squared-Norm Empirical Process in Banach Space

Cited by in corpus (2)

• Adversarial robustness via robust low rank representations
• Estimating Principal Components under Adversarial Perturbations