Skip to content

Tiered adversarial robustness with a rejection option

Stratified Adversarial Robustness with Rejection

arXiv· arXiv:2305.01139· Jiefeng Chen, Jayaram Raghuram, Jihye Choi, Xi Wu, Yingyu Liang, Somesh JhaDepartment of Computer Sciences, University of Wisconsin at Madison; GoogleIndexed by this site · 23 days ago· Originally publishedDefenses

Quick read

Defenses

Based on the paper PDF (AI-generated); refer to the original

The authors propose the hierarchical rejection setting and the defense CPR, and state that on CIFAR-10 the total robust loss is reduced by at least 7.3% compared with baselines (seen and unseen attacks).

Threat modelDefender's perspective: the attacker applies an l∞ norm-bounded perturbation to the test input; the seen attack budget equals the training budget ε (MNIST 0.3, SVHN/CIFAR-10 8/255), and the unseen attack budget is larger (MNIST 0.4, SVHN/CIFAR-10 16/255); the attack goal is to make the selective classifier misclassify or reject on small perturbations; evaluation uses the adaptive attack ensemble (including BPDA) designed in the paper.

Questions
In adversarially robust classification with rejection, existing studies treat rejecting perturbed inputs as zero-cost, so models may reject a large number of tiny perturbations that could have been correctly classified, whereas in real applications rejection has a cost.
Methods
The authors propose the stratified rejection setting: the rejection loss is monotonically non-increasing with perturbation magnitude; they give a theoretical analysis of total robust loss and robustness curves, and propose the defense CPR—using PGD to check whether predictions within the input neighborhood are consistent, and rejecting if they are not; they also design adaptive attacks for evaluation.
Experiments and results
On MNIST, SVHN, and CIFAR-10, the authors state that CPR has almost always the lowest total robust loss under various rejection losses, with at least a 7.3% reduction under seen and unseen attacks on CIFAR-10; the exception is that under the MNIST ramp loss t=2 seen attack, CPR is worse than some baselines.
Limitations and future work
The authors point out that the rejection loss depends only on perturbation magnitude and does not consider input-dependent losses, and that CPR requires m-step PGD at test time, increasing computational cost; experiments are conducted only on MNIST/SVHN/CIFAR-10 and the l∞ threat model, and each experiment is run only once.
Experimental setupAT+CPR (Ours)、TRADES+CPR (Ours) · MNIST、SVHN et al. · total robust loss、robustness with rejection(robustness curve) et al.
Evaluated models
AT+CPR (Ours)TRADES+CPR (Ours)
Benchmarks
MNISTSVHNCIFAR-10
Metrics
total robust lossrobustness with rejection(robustness curve)robust accuracy with detectionrejection rateF1 score
AI summaryThe researchers propose an adversarial training defense method, CPR, which constructs a robust selective classifier under a tiered rejection setting. The paper points out that existing studies typically set the cost of rejecting perturbed inputs to zero, causing many slightly perturbed inputs that could have been correctly classified to be rejected; the tiered rejection setting models the rejection cost as a loss function that is monotonically non-increasing with perturbation magnitude, and the paper provides a theoretical analysis of it. Experiments on image datasets show that CPR significantly outperforms existing methods under strong adaptive attacks, reducing the total robust loss by at least 7.3% on CIFAR-10 for different rejection losses, holding under both seen and unseen attacks.

The researchers propose an adversarial training defense method, CPR, which constructs a robust selective classifier under a tiered rejection setting. The paper points out that existing studies typically set the cost of rejecting perturbed inputs to zero, causing many slightly perturbed inputs that could have been correctly classified to be rejected; the tiered rejection setting models the rejection cost as a loss function that is monotonically non-increasing with perturbation magnitude, and the paper provides a theoretical analysis of it. Experiments on image datasets show that CPR significantly outperforms existing methods under strong adaptive attacks, reducing the total robust loss by at least 7.3% on CIFAR-10 for different rejection losses, holding under both seen and unseen attacks.

Paper analysis

6 questions; open one to read the full answer

  1. What problem does this paper attempt to solve?

    In adversarially robust classification with rejection, existing work treats rejecting perturbed inputs as zero cost; the authors study a setting where the cost of rejection varies with perturbation magnitude.

    Core question: In adversarially robust classification with rejection (selective classification), how can the real-world constraint that “the cost of rejection varies with perturbation magnitude” be modeled and exploited to learn a robust selective classifier that both misclassifies less and does not excessively reject small perturbations.

    • Problem scenario: The authors take traffic sign recognition in autonomous driving as an example; although abstaining is safer than misclassification, it brings costs of service interruption and human intervention; existing studies (Laidlaw & Feizi 2019, Stutz et al. 2020, Tramèr 2022, etc.) treat rejecting any perturbed input as a legitimate decision that does not count as a robust error.
    • Shortcomings of existing methods: The authors point out that models trained under the zero-cost assumption will reject a large number of tiny perturbations that could have been correctly classified. For example, on MNIST with ε=0.4, CCAT rejects some perturbation of magnitude only 0.02 for 99.30% of test points (main text Section 1).
    • Core observation: Small perturbations can usually still be correctly classified, so rejecting them should incur a large cost; large perturbations are hard to classify, so the cost of rejecting them should be lower. Therefore the rejection loss should be monotonically non-increasing with perturbation magnitude (stratified rejection).
    • Contributions of the paper: Propose the stratified rejection setting and two evaluation tools, total robust loss and robustness curve; give a theoretical analysis (Theorem 1); propose the defense method CPR (Adversarial Training with Consistent Prediction-based Rejection), and design adaptive attacks for evaluation.
    • Threat model (defender's perspective):
      • Attacker's goal: make the selective classifier misclassify perturbed inputs, or trigger rejection on tiny perturbations.
      • Attacker's capability: apply l∞-norm-bounded perturbations to test inputs; the seen attack budget equals the training budget ε, and the unseen attack budget is larger.
      • Victim system: an image classifier with a rejection option (LeNet, ResNet-20 on MNIST/SVHN/CIFAR-10).
      • Evaluation attacks: the paper designs a BPDA-based ensemble of adaptive attacks for CPR and each baseline.
  2. What related research exists?

    Related work falls into three groups: adversarial training and its bottlenecks, (non-adversarial) selective classification, and adversarially robust classification with rejection; the difference of this paper lies in explicitly modeling the cost of rejection.

    Adversarial robustness and adversarial training

    • Madry et al. (2018), Zhang et al. (2019)—adversarial training (AT) and TRADES; the authors state that this is the most effective approach to improving adversarial robustness, but robust error on complex datasets is still unsatisfactory (the paper cites RobustBench: robust test accuracy on CIFAR-10 is hard to exceed 67%).
    • Athalye et al. (2018), Tramèr et al. (2020)—many defenses are broken by strong adaptive attacks; the evaluation in this paper therefore uses adaptive attacks.

    Selective classification (non-adversarial setting)

    • Tax & Duin (2008), Geifman & El-Yaniv (2019), Charoenphakdee et al. (2021), Cortes et al. (2016)—standard classification with a rejection option (selective classification) has been widely studied.
    • Goldwasser et al. (2020)—selective classification with provable guarantees in the transductive setting.

    Adversarially robust classification with rejection

    • Stutz et al. (2020)—CCAT: confidence-calibrated adversarial training using label smoothing and confidence thresholds to generalize to unseen attacks.
    • Sheikholeslami et al. (2021)—RCD: adapts certified defense mechanisms so that the classifier either robustly classifies or detects adversarial examples.
    • Pang et al. (2022)—ATRR: observes that two coupled metrics, prediction confidence and true confidence (T-Con), can distinguish correct from misclassified inputs, and learns corrected confidence (R-Con) for rejection.
    • Laidlaw & Feizi (2019)—CARL: jointly learns a classifier and rejection regions in input space.
    • Balcan et al. (2023)—under a random feature subspace threat model, the authors state that classifiers not allowed to reject are provably vulnerable, and allowing rejection (e.g., thresholded nearest neighbor) can overcome such attacks.

    Baselines and benchmarks: the baselines compared in the experiments are AT+CR, TRADES+CR, CCAT, RCD, ATRR; the datasets are MNIST, SVHN, CIFAR-10.

    Positioning of this paper: the authors point out that existing work treats rejecting perturbed inputs as zero loss and does not explore the cost of rejection; the authors state that they are the first work to study adversarially robust classification with rejection under the stratified-rejection setting. The authors also note that Laidlaw & Feizi (2019) and Tramèr (2022) have proposed the idea of using consistency checks to reject inputs, but the authors state that this paper is the first to systematically implement and evaluate such a defense and design strong adaptive attacks for it.

  3. How does the paper address this problem?

    Proposes the hierarchical rejection setting and two tools, the total robust loss and the robustness curve; after theoretical analysis, gives the defense CPR: reject when neighborhood predictions are inconsistent.

    Overall idea: model the cost of rejection as a rejection loss function that is monotonically non-increasing with perturbation magnitude, and use a robustness curve to uniformly evaluate performance under different rejection losses; theoretically construct a selective classifier fδ that "rejects when close to the decision boundary," and based on this implement the defense CPR (Consistent Prediction-based Rejection).

    Problem setting and formalization

    • Selective classifier f : X → Y ∪ {⊥}, where ⊥ denotes rejection. Rejection loss `rej(r) : [0,∞) → [0,1] is monotonically non-increasing with perturbation magnitude r, and the rejection loss is largest for clean inputs.
    • Two specific rejection losses: step rejection loss rej(r) = 1{r ≤ α0ε}(Eq. 3);ramp rejection loss rej(r) = (1 − r/ε)^t (Eq. 4).
    • Total robust loss (Definition 1): Lϵ(f; ℓrej) = E maxx′ ∈ N(x,ϵ) [1{f(x′) ∉ {y,⊥}} ∨ 1{f(x′)=⊥} ℓrej(d(x,x′))], i.e., the larger of the misclassification loss and the rejection loss.
    • Robustness curve (Definition 2): Rϵrej(f, α) counts both misclassification and rejection as errors within the αε neighborhood, and counts only misclassification as errors within the ε neighborhood; α=1 degenerates to the standard robust error, and α=0 degenerates to the robust error with detection of Tramèr (2022). Lemma 1 gives that the total robust loss can be computed by integrating this curve.

    Theoretical analysis (Section 3)

    • Theorem 1 (binary classification): for any classifier without rejection f* and δ ∈ [0,1], construct fδ that rejects within δε of the decision boundary of f*, whose robust error curve satisfies R_ε^rej(fδ, α) ≤ R_ε'(f*), where ε' = max{(α+δ)ε, (1−δ)ε}, and this bound is tight.
    • Corollary: when α < 1−δ, fδ is no worse than f*; when α ≥ 1−δ it may be worse, but under a monotonically non-increasing rejection loss this part only incurs a lower rejection loss, so the total robust loss can be improved overall. Theorem 3 (Appendix B.4) gives a finer analysis.

    CPR defense (Section 4.1, Algorithm 1)

    • Mechanism: given a base classifier h(x; θ), for a test input x use m-step PGD to find the worst perturbation T(x) within the consistency radius ε̃ (maximizing the cross-entropy with respect to the predicted class); if ŷ(T(x)) ≠ ŷ(x), reject; otherwise accept and output ŷ(x).
    • Hyperparameters: consistency radius ε̃, PGD steps m, step size η. ε̃ is chosen so that the rejection rate on correctly classified clean inputs is approximately the user-specified prej (on MNIST ε̃=0.1, prej=1%, m=20, η=0.01; on SVHN/CIFAR-10 ε̃=0.0055, prej=5%, m=10, η=0.001).
    • The base model can be trained with AT or TRADES; the authors state that this defense is independent of the rejection loss used for evaluation and can generalize to various rejection losses.

    Adaptive attacks (Section 4.2, Appendix E)

    • Inner attack: find a rejected x′ within the αε neighborhood, including LCIA (minimize confidence), CLCIA (simultaneously minimize the confidence of x′ and T(x′)), PDIA (multi-objective, making the target class have high probability on x′ and low probability on T(x′)).
    • Outer attack: find an accepted and misclassified x″ within the ε neighborhood, including CHCMOA (multi-objective, making the target class high-confidence on both x″ and T(x″)) and HCMOA.
    • Attacks that depend on T(x) use BPDA (straight-through estimator) to approximate gradients; the final attack is an ensemble of all inner and outer attacks, and success is counted if any attack succeeds. Solving uses PGD with momentum: 200 iterations, 5 random restarts plus 1 zero initialization, with the step size taking the worst among 3 candidate values.
  4. What experiments did the paper conduct?

    Evaluates the total robust loss and robustness curve on MNIST/SVHN/CIFAR-10; the authors state that CPR is almost always best, with the exception of the seen attack on MNIST ramp loss t=2.

    Experimental Setup

    • Datasets: MNIST, SVHN, CIFAR-10; each test set has 10,000 images, the first 1,000 are used for robustness, the first 9,000 of the middle 9,000 are used for accuracy, and the last 1,000 are used as a validation set for hyperparameter selection (Section 5.1).
    • Models and baselines: LeNet for MNIST, ResNet-20 for SVHN/CIFAR-10; baselines are AT+CR, TRADES+CR, CCAT, RCD, ATRR; CPR variants are AT+CPR, TRADES+CPR.
    • Threat model: l∞ attacks; seen budgets MNIST ε=0.3, SVHN/CIFAR-10 ε=8/255; unseen budgets MNIST 0.4, SVHN/CIFAR-10 16/255.
    • Metrics: total robust loss (step loss α0 ∈ {0, 0.05, 0.1}, ramp loss t ∈ {2, 4}), robustness curve (α ∈ {0, 0.01, 0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.5, 1}), traditional metrics (Table 3).
    • Evaluation method: for each method, take the worst result from the corresponding ensemble of adaptive attacks; all experiments are run once with a fixed random seed (Appendix D).
    • Rejection threshold setting: uniform across all methods, on MNIST only 1% of correctly classified clean validation inputs are rejected, on SVHN/CIFAR-10 it is 5%.

    Main Results

    Total robust loss (lower is better), according to Table 1, listing the two columns step loss α0=0 and ramp loss t=4:

    Swipe horizontally to read the table

    DatasetMethodseen α0=0seen t=4unseen α0=0unseen t=4
    MNISTTRADES+CR0.0600.0651.0001.000
    MNISTCCAT0.1680.8940.2450.914
    MNISTAT+CPR0.0390.0590.0960.116
    MNISTTRADES+CPR0.0420.0580.1330.145
    SVHNTRADES+CR0.4710.4730.8740.874
    SVHNTRADES+CPR0.3800.3810.8130.814
    CIFAR-10TRADES+CR0.5000.5010.8490.849
    CIFAR-10TRADES+CPR0.4290.4300.7810.782

    (Table 1 also contains three rows for AT+CR, RCD, ATRR and the remaining loss columns, omitted here; in the full table CPR is lowest in almost all combinations.)

    • The authors state that CPR has the lowest total robust loss in almost all cases: under unseen attacks it is reduced by at least 60.8% (MNIST), 6.6% (SVHN), 7.3% (CIFAR-10); under seen attacks it is reduced by at least 18.0% (SVHN), 12.8% (CIFAR-10).
    • Exception: under seen attacks with MNIST ramp loss t=2, CPR (AT+CPR 0.133, TRADES+CPR 0.130) is worse than baselines such as TRADES+CR (0.075); the authors explain that on MNIST small perturbations are easy to classify correctly, ramp loss penalizes rejection of large perturbations more, and CPR tends to reject large perturbations.
    • Robustness curve (Figure 2, Appendix Figure 3): the authors state that CPR is clearly higher than baselines at small to medium α, and decreases only at large α; the authors state this is consistent with theoretical predictions.

    Traditional Metric Evaluation (Table 3)

    • What was measured: accuracy on clean inputs, rejection rate, F1, and robust accuracy with detection (seen/unseen).
    • Results: the authors state that CPR is comparable to baselines on clean inputs and clearly higher on robust accuracy with detection. For example, under MNIST unseen attacks AT+CPR is 90.40 and TRADES+CPR is 86.70, while AT+CR, TRADES+CR, RCD, ATRR are all 0.00 and CCAT is 75.50 (%).
    • Under CIFAR-10 unseen attacks TRADES+CPR is 21.90, the highest in the whole table (%).

    Attack Ablation (Table 2)

    • What was measured: the strength of each internal and external attack on CPR (smaller values mean stronger attacks).
    • Results: among external attacks CHCMOA is strongest on all datasets (e.g., MNIST AT+CPR 96.10, versus AutoAttack 97.60, HCMOA 97.80); among internal attacks LCIA is usually strongest, while CLCIA and PDIA are stronger on MNIST (MNIST TRADES+CPR: LCIA 7.60, CLCIA 5.10, PDIA 0.40).
    • The authors emphasize that the final evaluation uses the ensemble of all attacks.

    Other Ablations and Analyses

    • Hyperparameters ε̃ and m (Appendix F.5, Figures 5, 6): larger ε̃ or m improves robustness at α=0 but reduces robustness at large α; the improvement becomes smaller as m increases, and the main experiments use m=10 (MNIST m=20).
    • CPR versus AT without rejection (Appendix F.4, Figure 4): the authors state that AT+CPR is usually better than AT without rejection, more clearly under unseen attacks; under seen attacks AT without rejection is better at large α.
    • CCAT attack strength (Appendix F.7, Table 5): HCMOA is stronger than the PGD-with-backtracking in the original CCAT paper, e.g., under CIFAR-10 unseen attacks robustness with detection drops from 38.20 to 8.80 (%).
    • More rejection losses (Appendix F.3, Table 4): conclusions on step loss α0 ∈ {0.01, 0.15, 0.2} and ramp loss t ∈ {1, 3} are consistent with the main text.
  5. What are some points that can be further explored?

    The authors point out two limitations, the form of the rejection loss and the computational cost at test time, and corresponding directions; experiments are limited to three image datasets and the l∞ threat model.

    Limitations and future directions noted by the authors

    • Rejection loss depends only on perturbation magnitude (Section 6 Limitations & Future Work): this paper only considers rej(r) 形式的损失,未考虑也依赖输入 x 的损失(如 rej(r, x)); the authors state that handling more general rejection losses is an interesting future problem.
    • Increased computation at test time (Section 6): CPR requires m-step PGD to compute T(x) at prediction time, i.e., in addition to two forward passes, m forward and backward passes are needed; the authors state that designing defenses with lower computational cost and better robustness is a future direction.

    Scope of experiments

    • The evaluated models are two architectures, LeNet (MNIST) and ResNet-20 (SVHN, CIFAR-10), and the datasets are three in total: MNIST, SVHN, CIFAR-10 (Section 5.1, Appendix D).
    • The threat model covers only l∞ norm-bounded attacks; the seen budget is the training budget, and the unseen budget is about 1.3–2 times it (MNIST 0.3→0.4, SVHN/CIFAR-10 8/255→16/255) (Section 5.1).
    • The comparison baselines are 5 in total: AT+CR, TRADES+CR, CCAT, RCD, ATRR; CPR is combined only with the two base training methods AT and TRADES (Section 5.1).
    • Robustness is computed on the first 1,000 images of the test set, and all experiments are run only once with a fixed random seed (Appendix D); the paper does not report variance across multiple runs.
    • The theoretical part (Theorem 1, 3) covers only the binary classification case (Section 3, Appendix B).
  6. Summarize the main content of the paper

    Layered rejection setting + total robustness loss and robustness curves + defense CPR; the authors state that CPR is almost always best-performing on three datasets.

    A defense paper on adversarially robust classification with rejection (ICML 2023).

    • Problem: existing work on adversarially robust classification with rejection treats rejecting perturbed inputs as zero cost, causing models to reject many small perturbations that could have been correctly classified; for example, on MNIST with ε=0.4, CCAT rejects some perturbations within 0.02 magnitude for 99.30% of test points.
    • Method: proposes a hierarchical rejection setting in which the rejection loss is monotonically non-increasing with perturbation magnitude; defines the total robust loss and the robustness curve (α=1 degenerates to the standard robust error, α=0 degenerates to robust error with detection); theoretically constructs fδ that rejects near the boundary and gives a tight error bound (Theorem 1); based on this implements CPR—using m-step PGD to check prediction consistency within the input neighborhood, rejecting when inconsistent, which can be applied on top of AT or TRADES bases; evaluation uses a specially designed BPDA adaptive attack ensemble.
    • Main results (Table 1): the authors state that the total robust loss of CPR is the lowest in almost all dataset × rejection loss × attack combinations; under unseen attacks it is reduced by at least 60.8% (MNIST), 6.6% (SVHN), 7.3% (CIFAR-10), and under seen attacks by at least 18.0% (SVHN), 12.8% (CIFAR-10). The exception is the MNIST ramp loss t=2 seen attack, where CPR is worse than baselines such as TRADES+CR.
    • Traditional metrics (Table 3): the authors state that CPR performs comparably to baselines on clean inputs, and robust accuracy with detection is clearly higher, e.g., under MNIST unseen attacks AT+CPR 90.40 versus CCAT 75.50 and the remaining baselines 0.00 (%).
    • Authors' conclusion: in the realistic setting where rejection has a cost, CPR outperforms existing methods under strong adaptive attacks and can be combined with different adversarial training methods; the authors also note that more general forms of rejection loss and the test-time PGD cost are directions for future work.

Related papers

Show 3 more papers
Read originalarxiv.org