# A Theoretical Study of The Effects of Adversarial Attacks on Sparse Regression

arXiv: https://arxiv.org/abs/2212.11209 · HTML: https://mlsanity.com/paper/2212.11209/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 42 references that are in the map.
- First posted on arXiv 21 Dec 2022.

## Builds on (most cited first, 23 of 23)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Adversarial examples in the physical world](https://mlsanity.com/paper/1607.02533/) (2016)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Unlabeled Data Improves Adversarial Robustness](https://mlsanity.com/paper/1905.13736/) (2019)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Adversarial Examples Are a Natural Consequence of Test Error in Noise](https://mlsanity.com/paper/1901.10513/) (2019)
- [Precise Tradeoffs in Adversarial Training for Linear Regression](https://mlsanity.com/paper/2002.10477/) (2020)
- [Adversarially Robust Generalization Just Requires More Unlabeled Data](https://mlsanity.com/paper/1906.00555/) (2019)
- [Model Compression with Adversarial Robustness: A Unified Optimization Framework](https://mlsanity.com/paper/1902.03538/) (2019)
- [Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks](https://mlsanity.com/paper/2004.13617/) (2020)
- [Random Noise Defense Against Query-Based Black-Box Attacks](https://mlsanity.com/paper/2104.11470/) (2021)
- [On the Generalization Properties of Adversarial Training](https://mlsanity.com/paper/2008.06631/) (2020)
- [Adversarially Robust Estimate and Risk Analysis in Linear Regression](https://mlsanity.com/paper/2012.10278/) (2020)
- [Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm](https://mlsanity.com/paper/1405.2936/) (2014)
- [Adversarial regression training for visualizing the progression of chronic obstructive pulmonary disease with chest x-rays](https://mlsanity.com/paper/1908.10468/) (2019)
- [Adversarial Regression with Multiple Learners](https://mlsanity.com/paper/1806.02256/) (2018)
- [Provable Computational and Statistical Guarantees for Efficient Learning of Continuous-Action Graphical Games](https://mlsanity.com/paper/1911.04225/) (2019)

## Built on by (most cited first, 1 of 1)

- [Admissibility of Stein Shrinkage for Batch Normalization in the Presence of Adversarial Attacks](https://mlsanity.com/paper/2507.08261/) (2025)

## Abstract (arXiv)

This paper analyzes ℓ1 regularized linear regression under the challenging scenario of having only adversarially corrupted data for training. We use the primal-dual witness paradigm to provide provable performance guarantees for the support of the estimated regression parameter vector to match the actual parameter. Our theoretical analysis shows the counter-intuitive result that an adversary can influence sample complexity by corrupting the irrelevant features, i.e., those corresponding to zero coefficients of the regression parameter vector, which, consequently, do not affect the dependent variable. As any adversarially robust algorithm has its limitations, our theoretical analysis identifies the regimes under which the learning algorithm and adversary can dominate over each other. It helps us to analyze these fundamental limits and address critical scientific questions of which parameters (like mutual incoherence, the maximum and minimum eigenvalue of the covariance matrix, and the budget of adversarial perturbation) play a role in the high or low probability of success of the LASSO algorithm. Also, the derived sample complexity is logarithmic with respect to the size of the regression parameter vector, and our theoretical claims are validated by empirical analysis on synthetic and real-world datasets.