Robustness Cannot be Reduced to Regularization: Studying Adversarial Training Beyond the Linear Case
For ML practitioners seeking efficient adversarial defenses, this work shows that computational shortcuts based on regularization equivalence are fundamentally limited to linear models.
The paper proves that adversarial training cannot be reduced to a simpler regularized risk minimization for two-layer neural networks, contradicting prior results for linear models. Empirical evidence on Wide-ResNets suggests the impossibility extends to deeper architectures.
The vulnerability of ML models to adversarial examples has recently emerged as a major concern. While adversarial training is one of the most effective countermeasures to this issue, its high computational cost remains an obstacle to practical deployment. Recent progress in reducing this cost has relied, in the case of linear models, on a formal equivalence between the adversarial risk and a simpler form of regularized risk. This enabled significantly more efficient training procedures, which naturally raises the question of whether such an equivalence can be extended beyond linear models. In this work, we formally show that no such equivalence is possible for two-layer networks. Our proofs proceed via a reduction to key properties that fundamentally separate the adversarial risk from any simple regularized risk which would only exhibit a weak form of data dependence. Beyond this setting, we provide empirical evidence on Wide-ResNets indicating that the same type of impossibility persists in deeper and more expressive architectures.