On Achieving Optimal Adversarial Test Error
This addresses the challenge of robust generalization in adversarial machine learning, providing a foundational theoretical guarantee for broad applicability.
The paper tackles the problem of achieving optimal adversarial test error for general data distributions and perturbation sets, proving that adversarial training on shallow networks with early stopping and an idealized optimal adversary can achieve this optimal error, whereas prior work was limited to specialized distributions or training error guarantees.
We first elucidate various fundamental properties of optimal adversarial predictors: the structure of optimal adversarial convex predictors in terms of optimal adversarial zero-one predictors, bounds relating the adversarial convex loss to the adversarial zero-one loss, and the fact that continuous predictors can get arbitrarily close to the optimal adversarial error for both convex and zero-one losses. Applying these results along with new Rademacher complexity bounds for adversarial training near initialization, we prove that for general data distributions and perturbation sets, adversarial training on shallow networks with early stopping and an idealized optimal adversary is able to achieve optimal adversarial test error. By contrast, prior theoretical work either considered specialized data distributions or only provided training error guarantees.