Introduction
Linear regression serves as a foundational tool in data science, utilized not only for its predictive power but for its capacity to provide interpretable explanations. By examining regression coefficients ($\beta$), practitioners determine feature importance and the directional relationship between variables and outcomes. However, this reliance on interpretability introduces a specific security vulnerability: the interpretability attack.
While traditional adversarial machine learning research focuses on degrading model accuracy, this paper explores how an adversary can strategically manipulate data to alter the perceived significance of specific features. By framing these attacks as optimization problems, the authors demonstrate that even a single poisoned data point or a minor rank-one modification to the feature matrix can fundamentally change the "story" a model tells.
Adversarial Scenarios and Methodology
The research investigates three distinct attack vectors, each increasing in complexity and scope. The common thread is the assumption of a limited "energy budget," constraining the magnitude of the adversary's changes to ensure the attack remains subtle.
1. Single-Point Attack on a Specific Coefficient
In this scenario, the attacker seeks to maximize or minimize a single coefficient $\beta_i$ by injecting one new data point $\{y_0, x_0\}$ into the training set. This is initially a complex bi-level optimization problem. However, the authors utilize the Sherman-Morrison formula to transform the objective into a ratio of quadratic functions. They prove that this problem possesses a "hidden convex" structure, allowing for a globally optimal closed-form solution derived via Karush-Kuhn-Tucker (KKT) conditions.
2. Targeted Attack with Minimal Collateral Damage
Beyond simply changing one coefficient, an attacker may wish to isolate the impact—altering a specific $\beta_i$ while keeping all other coefficients as stable as possible. This prevents the attack from being detected through broad shifts in model behavior. The authors formulate this as a multivariate polynomial optimization problem. To solve it, they employ Lasserre’s relaxation method (a Sum of Squares approach), which converts the non-convex problem into a sequence of solvable semidefinite programs.
3. Rank-One Feature Matrix Modification
This broader attack involves modifying the existing feature matrix $X$ by adding a rank-one matrix $\Delta = cd^\top$. This framework is highly versatile, as it can model scenarios such as modifying a single feature across all samples or effectively deleting a specific data point. To find the optimal $c$ and $d$, the authors propose an alternating optimization algorithm. This method iteratively updates the vectors to converge toward a critical point, providing a robust alternative to standard gradient-based methods.
Experimental Evaluation
The proposed methods were evaluated using the Istanbul Stock Exchange (ISE) dataset, which contains 536 daily returns of the Istanbul Stock Exchange alongside seven international market indexes (e.g., S&P 500, Nikkei 225). The goal was to predict Istanbul returns based on international performance.
Key Findings
- Fragility of Interpretability: The experiments confirmed that a single, optimized data point could reduce a statistically significant coefficient to near zero, effectively "silencing" a feature's perceived impact.
- Optimization vs. Heuristics: The optimization-based attacks significantly outperformed random poisoning. While random noise might slightly shift coefficients, the proposed methods reached specific target values with high precision.
- Global Optimality in Practice: For targeted attacks, the authors found that low-order Lasserre relaxations (order 2 or 3) were sufficient to identify global optima, making the approach computationally feasible.
- Superiority over PGD: In rank-one modification tests, the alternating optimization algorithm proved faster and more stable than Projected Gradient Descent (PGD), which often struggled with local minima and sensitive hyperparameter tuning.
Discussion and Implications
The research highlights a critical tension between model utility and security. Because many adversarial problems in linear regression appear non-convex, they were previously thought to be computationally difficult for an attacker. By identifying "hidden convexity" and applying advanced relaxation techniques, this paper shows that optimal attacks are often efficiently obtainable.
The rank-one modification framework is particularly significant because it serves as a "universal bound" for various data tampering strategies. Since many common edits—such as changing a column or row—are rank-one operations, this analysis provides a worst-case scenario for data integrity.
Conclusion and Future Work
This work demonstrates that linear regression is highly susceptible to targeted manipulation of its interpretability. Future research directions include extending these optimization frameworks to multi-point injection attacks and exploring similar vulnerabilities in more complex models beyond the linear case. Additionally, the development of robust regression techniques that can detect or mitigate these optimal feature manipulations remains a vital area for defensive security research.
Summary updated