Calibrated Surrogate Losses for Adversarially Robust Classification
arXiv:2005.13748
Abstract
Adversarially robust classification seeks a classifier that is insensitive to adversarial perturbations of test patterns. This problem is often formulated via a minimax objective, where the target loss is the worst-case value of the 0-1 loss subject to a bound on the size of perturbation. Recent work has proposed convex surrogates for the adversarial 0-1 loss, in an effort to make optimization more tractable. A primary question is that of consistency, that is, whether minimization of the surrogate risk implies minimization of the adversarial 0-1 risk. In this work, we analyze this question through the lens of calibration, which is a pointwise notion of consistency. We show that no convex surrogate loss is calibrated with respect to the adversarial 0-1 loss when restricted to the class of linear models. We further introduce a class of nonconvex losses and offer necessary and sufficient conditions for losses in this class to be calibrated. We also show that if the underlying distribution satisfies Massart's noise condition, convex losses can also be calibrated in the adversarial setting.
arXiv commentCorrigendum to the published version in COLT2020 (http://proceedings.mlr.press/v125/bao20a.html)
References in corpus (32)
- Theoretically Principled Trade-off between Robustness and Accuracy
- Provable defenses against adversarial examples via the convex outer adversarial polytope
- Towards Deep Neural Network Architectures Robust to Adversarial Examples
- Certified Adversarial Robustness via Randomized Smoothing
- Certified Defenses against Adversarial Examples
- Domain Adaptation: Learning Bounds and Algorithms
- Understanding Adversarial Training: Increasing Local Stability of Neural Nets through Robust Optimization
- Robustness and Regularization of Support Vector Machines
- Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation
- Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
- Risk bounds for statistical learning
- Bridging Theory and Algorithm for Domain Adaptation
- Making Risk Minimization Tolerant to Label Noise
- Semidefinite relaxations for certifying robustness to adversarial examples
- Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks
- Composite Binary Losses
- Adversarial examples from computational constraints
- Does Distributionally Robust Supervised Learning Give Robust Classifiers?
- On Symmetric Losses for Learning from Corrupted Labels
- A Minimax Approach to Supervised Learning
- Loss factorization, weakly supervised learning and label noise robustness
- Theoretical evidence for adversarial robustness through randomization
- Adversarial Risk Bounds via Function Transformation
- Convex Calibration Dimension for Multiclass Loss Matrices
- Multiclass Classification Calibration Functions
- Monge blunts Bayes: Hardness Results for Adversarial Training
- Calibrated Surrogate Losses for Adversarially Robust Classification
- On Structured Prediction Theory with Calibrated Convex Surrogate Losses
- Structured Prediction with Projection Oracles
- Calibration and Consistency of Adversarial Surrogate Losses
- A Finer Calibration Analysis for Adversarial Robustness
- Classification using margin pursuit