Small Interval Boxes as a Single-Step Cure for Catastrophic Overfitting

Making an image classifier robust to small, deliberately chosen input perturbations usually means paying twice. Adversarial training, which retrains the model on worst-case perturbed inputs, costs roughly ten times a normal training run because each update needs a multi-step attack. Certified training, which proves that no perturbation inside a small ball can flip the prediction, costs clean accuracy because its bounds grow loose with depth and over-constrain the network. The cheap fix for the first problem is a single-step attack, but it suffers catastrophic overfitting: partway through training, the model suddenly looks robust to the one-step attack it trains on while becoming fully breakable by stronger multi-step attacks.

This note argues that the tool built for the second problem can fix the first. Interval bound propagation (IBP) pushes a box of possible inputs through the network layer by layer and returns guaranteed lower and upper bounds on the outputs. If we place a small IBP box around a single-step adversarial point and train on the worst case inside that box, the loss bound punishes exactly the sharp, localized bends in the decision boundary that cause catastrophic overfitting. The bound also stays tight enough to preserve clean accuracy, and the whole update costs about three network passes instead of eleven. The proposal tests whether this one ingredient gives fast training, adaptive-attack robustness that holds up, and nontrivial certificates together.

Core Claim

Catastrophic overfitting is a geometric failure. Understanding Catastrophic Overfitting in Single-step Adversarial Training shows that the model learns a sharp distortion of its decision boundary exactly at the training radius $\epsilon$. Inputs at interior distances $k\epsilon$ ($k<1$) are left vulnerable, and the onset of this failure is marked by input-gradient norms growing up to 35×. Current fixes either add noise or enforce local linearity of the loss by sampling.

Towards fast and effective single-step adversarial training (N-FGSM) adds large unclipped noise around the clean input. Efficient local linearity regularization to overcome catastrophic overfitting (ELLE) penalizes nonlinearity of the loss along random line segments, which costs three extra forward passes.

An interval bound over a box is a deterministic, worst-case version of that same penalty. If the upper bound on the loss over the box is small, no point inside the box, including any sharply bent pocket, can have high loss. Certified Training: Small Boxes are All You Need (SABR) supplies the observation that makes this affordable. Interval error grows super-linearly with box radius, so a box of radius $\tau=\lambda\epsilon$ with $\lambda$ around 0.05 is tight enough not to collapse clean accuracy.

SABR, however, places its box around a multi-step PGD adversary (projected gradient descent, the standard iterative attack). It therefore inherits the full cost of adversarial training. Our claim is that the multi-step search is unnecessary once the box is there. A single noisy gradient step finds a good enough anchor, and the box itself prevents the overfitting that would otherwise make a single-step anchor fail.

Concretely, for clean input $x$ with label $y$, we draw uniform noise $\eta \in [-2\epsilon, 2\epsilon]$ and take one signed-gradient step of size $\alpha$ to get an anchor $x'$, clipped so the box stays inside the $\epsilon$-ball. We then minimize

$$ \mathcal{L}(\theta) = \mathcal{L}_{\mathrm{CE}}\big(\overline{f}_\theta(B_\tau(x')),\, y\big), \qquad x' = \Pi_{\epsilon-\tau}\big(x + \eta + \alpha\,\mathrm{sign}\,\nabla_x \mathcal{L}_{\mathrm{CE}}(f_\theta(x+\eta), y)\big). $$

Here $\overline{f}_\theta(B_\tau(x'))$ is the worst-case logit vector that IBP computes over the box of radius $\tau$ centered at $x'$, and $\Pi_{\epsilon-\tau}$ projects onto the shrunken ball around $x$. The cost per update is one forward and one backward pass for the step, plus one IBP forward and backward pass, which is roughly 2–3× a forward pass by the file's estimate. Total cost lands near ELLE and well below PGD-10 or SABR.

Research Program

The work has three parts.

Build the training rule and its one adaptive piece. The box radius $\tau$ is the knob between adversarial training ($\tau=0$) and full certified training. SABR tunes it by hand per setting. Our hypothesis is that catastrophic overfitting and over-regularization can both be read off the bound itself. We will track the ratio between the IBP width of the box and the empirical loss range found by a cheap two-point probe inside it. If the ratio spikes, the network is bending sharply inside the box, and the box should grow. If the ratio is near 1, the box is near tight and can shrink to recover accuracy. This uses the propagation-tightness quantity of Understanding Certified Training with Interval Bound Propagation as a live control signal rather than a post-hoc diagnostic. It is cheaper than the per-sample root finding of Adaptive Certified Training (ACERT), which runs about 3.3× slower than fast IBP.

Test the mechanism, not just the numbers. We will measure three things through training:

  • input-gradient norms;
  • loss along the adversarial direction at $\epsilon/3$, $2\epsilon/3$ and $\epsilon$, following the probe from the catastrophic-overfitting paper;
  • the fraction of inactive ReLU units, which Fast Certified Robust Training with Short Warmup links to capacity loss.

The claim predicts that the box term suppresses the gradient-norm explosion before multi-step accuracy collapses. Plain single-step training should show the explosion. Full IBP should suppress it, but only by killing neurons.

Evaluate against attacks built for this defense. Our model sees one box per example around one single-step anchor. The natural worry is that pockets of the $\epsilon$-ball far from the anchor direction are never trained. SABR never checked this for its own boxes. We will run AutoAttack plus a defense-aware attack. That attack starts many PGD restarts from points deliberately far from the training anchor, for example opposite-sign corners of the ball, and searches specifically at interior radii, where catastrophic overfitting is known to hide.

Certificates are reported with a complete or incomplete verifier, in the way Connecting Certified and Adversarial Training (TAPS) evaluates its unsoundly trained models. Deterministic certificates are sound within $\epsilon$, so the ghost-certificate spoofing of Certified but Fooled! cannot apply to certified points inside the threat model. We will say so plainly rather than claim spoofing resistance as a result. Adaptive attacks matter here for the uncertified points and for verifying that empirical robustness is real.

Baselines

The naive reference point is plain single-step adversarial training with a random start. It is the method whose collapse we claim to cure. It should show catastrophic overfitting at large $\epsilon$; the catastrophic-overfitting paper reports standard FGSM collapsing to 0.1% PGD-50 accuracy on CIFAR-10.

The strongest fast empirical competitors are N-FGSM and ELLE-A, run from the authors' code in LIONS-EPFL/ELLE, which also provides the PGD-50-10 and AutoAttack evaluation scripts we will use for every model. ELLE-A reports 44.32% AutoAttack accuracy on CIFAR-10 (Efficient local linearity regularization to overcome catastrophic overfitting). For N-FGSM the file's numbers cover ImageNet only: 17.12% PGD-50-10 at $\epsilon=6/255$. We found no reported CIFAR-10 number for N-FGSM on Lacuna, so we will rerun it. Beating these baselines means matching or exceeding their AutoAttack accuracy at equal wall-clock time while also producing nonzero verified accuracy, which neither provides.

The strongest certified competitor is SABR with its original multi-step PGD anchor. It reports 79.24% clean and 62.84% certified accuracy at $\epsilon=2/255$, and 52.38% clean and 35.13% certified at $\epsilon=8/255$, on CIFAR-10 (Certified Training: Small Boxes are All You Need). The cheap certified reference is fast IBP, at 65.03% verified error ($\epsilon=8/255$, 160 epochs) (Fast Certified Robust Training with Short Warmup).

Rethinking Evaluation Paradigms in IBP-based Certified Training showed that single-point comparisons mislead and that SABR gains over 1% when retuned. We will therefore give SABR, fast IBP and our method the same hyperparameter search budget, the same architecture as the SABR paper, and the same verifier. We will compare clean-versus-certified fronts at matched GPU-hours rather than single points. Beating SABR means reaching its front within about one point of certified accuracy at a third or less of its training time. Strictly dominating it is not required.

Two ablations isolate the key ingredient:

  • Multi-step SABR versus single-step SABR without the noise term. This is the most dangerous alternative; see below.
  • Our method with a fixed $\tau$ versus the bound-driven $\tau$. This tests whether the adaptive piece earns its place.

Why not just…?

Why not just run SABR with a single PGD step? This is the real threat. If one-step SABR with no noise matches our method, then N-FGSM-style noise adds nothing, and the contribution shrinks to "SABR's inner attack is overkill." That would still be useful but is narrower. The ablation above settles it. Our prediction rests on the catastrophic-overfitting mechanism: a clipped single step without noise produces anchors that cluster at the ball's boundary, where the sharp distortion forms. Single-step SABR should therefore overfit at large $\epsilon$ (8/255 and 16/255) even if it survives at 2/255. If it does not overfit there, we report that and drop the noise from the method.

Why not just use N-FGSM or ELLE, which already avoid catastrophic overfitting cheaply? They give empirical robustness only, and the file records that the bounds of ELLE models remain unverified and loose. Our method should cost about the same as ELLE, which also needs extra passes. If it matches their AutoAttack accuracy and additionally certifies a meaningful fraction of inputs, it dominates them. If it costs AutoAttack accuracy, the front plot will show the price of the certificate, and practitioners can choose.

Why not just use fast IBP, which is already cheap? Fast IBP trains on the full $\epsilon$-box. By the propagation-invariance analysis in Understanding Certified Training with Interval Bound Propagation, that forces cross-layer weight-sign alignment and costs clean accuracy; SABR's 52.38% versus IBP's 48.94% clean at $\epsilon=8/255$ illustrates the gap. Our method is not meant to beat fast IBP on raw speed. It should reach a better clean-certified front at comparable cost, and the dead-neuron measurements will show whether the mechanism is the one claimed.

Why not just tune existing methods better? We adopt that discipline rather than argue against it: every baseline gets the same tuning budget. The file reports that at $\epsilon=8/255$ all well-tuned certified methods converge near 35% certified accuracy. We therefore do not claim to break that barrier. Our claim concerns cost and the empirical-certified combination at that barrier.

Proposed Experiments

Settings. The main study is CIFAR-10 at $\epsilon \in \{2/255, 8/255\}$ for certified comparison, and at $8/255$ and $16/255$ for the catastrophic-overfitting regime. TinyImageNet at $\epsilon=1/255$ tests scale; there the reference points are TAPS's reported 22% certified accuracy and the gains SABR reports.

Metrics. We report clean accuracy, AutoAttack accuracy, PGD-50-10 accuracy, the defense-aware far-restart attack, and verified accuracy. Each is paired with wall-clock GPU-hours and peak memory. We use three seeds, because catastrophic overfitting is seed-sensitive.

Decisive checks. There are three, and any one can falsify the claim:

  • Overfitting at large radius. At $\epsilon=16/255$, our method must show no collapse of multi-step accuracy across all seeds, while plain single-step training collapses. Gradient norms must stay flat in our runs and explode in the collapsing ones.
  • Cost-matched certified front. At $\epsilon=2/255$, our front must lie within roughly one certified point of tuned SABR at a third of its GPU-hours. If it falls well short, the single-step anchor is too weak and the claim fails.
  • Defense-aware attack. The far-restart attack must not lower robust accuracy by more than it lowers it for SABR. A larger drop would mean the single anchor leaves untrained pockets, exactly the vulnerability we set out to rule out.