On the Adversarial Robustness of Subspace Learning

Fuwei Li, Lifeng Lai, Shuguang Cui

Abstract

Principal Component Analysis (PCA) is a cornerstone of high-dimensional data analysis, yet its vulnerability to targeted adversarial manipulation remains underexplored compared to traditional outlier-robust methods. This paper investigates the fundamental limits of subspace learning robustness by characterizing optimal adversarial attacks. We model the adversary as a malicious actor with full data knowledge and a constrained energy budget seeking to maximize the Asimov distance between the original and poisoned subspaces. Our analysis provides closed-form solutions for both rank-one and general optimal attacks, revealing that the vulnerability of a subspace is primarily determined by the gap between its $k$-th and $(k+1)$-th singular values. We demonstrate that beyond a specific energy threshold, an adversary can render the learned subspace completely orthogonal to the original.

Introduction

Subspace learning, particularly PCA, is essential for dimensionality reduction in fields ranging from medical imaging to recommendation systems. While "Robust PCA" has long addressed unintentional data corruption like sparse outliers or Gaussian noise, it does not account for adversarial scenarios where a malicious actor strategically modifies data. This research shifts the focus to adversarial robustness, exploring how a powerful adversary can tilt the coordinate system of a dataset to degrade downstream performance.

Problem Formulation

The authors consider an adversary who observes a data matrix $X$ and introduces a modification matrix $\Delta X$ to create a poisoned version $\hat{X} = X + \Delta X$. The adversary's objective is to maximize the Asimov distance (the largest principal angle $\theta$) between the $k$-dimensional subspace of $X$ and that of $\hat{X}$, subject to an energy constraint $\|\Delta X\|_F \leq \eta$. This setup represents a worst-case security scenario for safety-critical systems.

Methodology

The attack is formulated as a non-convex optimization problem. The authors derive solutions through a hierarchical approach:

  1. Rank-One Attacks: Analyzing modifications where $\Delta X = ab^\top$, representing the addition of a single malicious sample or feature modification.
  2. General Attacks: Removing rank constraints to find the global optimum.
  3. Dimensionality Reduction: A significant technical finding is that the optimal attack matrix is sparse when represented in the basis of the original principal components, specifically targeting the interaction between the $k$-th and $(k+1)$-th components.
  4. Closed-Form Solutions: By transforming the non-convex problem into a ratio of quadratic functions, the authors provide analytical solutions based on the data's singular values and the budget $\eta$.

Experimental Results

The theoretical findings were validated using synthetic data and the Gasoline Spectral Dataset. The results confirm that the "optimal" strategies significantly outperform random noise and existing baselines like "ad-pca."

Comparison of subspace distance $\theta^*$ under different attack strategies as a function of the normalized energy budget $\eta/\sigma_k$.

As shown in the figure above, the general optimal attack (wr-opt) reaches the maximum possible distance of $\pi/2$ (90 degrees) much faster than other methods. This $\pi/2$ threshold occurs when the energy budget $\eta \geq (\sigma_k - \sigma_{k+1})/\sqrt{2}$. Beyond this point, the poisoned subspace is entirely orthogonal to the ground truth.

On real-world data, the authors demonstrated that these attacks cause a catastrophic failure in Principal Component Regression (PCR). For the gasoline dataset, the predictive power ($R^2$) plummeted to zero exactly at the predicted theoretical threshold, effectively neutralizing the model's utility.

Key Insights

  • The Singular Value Gap: The ease of "tilting" a subspace is inversely proportional to the gap between the $k$-th and $(k+1)$-th singular values. A small gap indicates a highly vulnerable subspace.
  • Strategic Sparsity: Even with the ability to modify the entire matrix, the most effective attack is highly targeted, focusing on "confusing" the boundary between the included and excluded principal components.
  • Attack Potency: General attacks consistently outperform rank-one attacks for the same energy budget, particularly in datasets that are not strictly low-rank.

Conclusion

This work establishes the theoretical boundaries of PCA's adversarial robustness. By identifying the specific conditions under which subspace learning fails, it highlights a critical security gap in standard dimensionality reduction techniques. While the current study assumes a white-box adversary and does not propose defenses, it provides the necessary mathematical foundation for developing future robust subspace learning algorithms, potentially through game-theoretic frameworks or adversarial training.

Reference: Li, F., Lai, L., & Cui, S. (2019). On the Adversarial Robustness of Subspace Learning. arXiv:1908.06210v1.

Summary updated

BibTeX
@inproceedings{li2019adversarial,
  author = {Fuwei Li and Lifeng Lai and Shuguang Cui},
  title = {{On the Adversarial Robustness of Subspace Learning}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2019},
  doi = {10.1109/icassp.2019.8683270},
}
Figure