Skip to content

SingleProp enables fast training of provably robust neural networks

Fast Training of Provably Robust Neural Networks by SingleProp

arXiv· arXiv:2102.01208· Akhilan Boopathy, Tsui-Wei Weng, Sijia Liu, Pin-Yu Chen, Gaoyuan Zhang, Luca DanielMassachusetts Institute of Technology; MIT-IBM Watson AI Lab, IBM ResearchIndexed 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 certified robust training method SingleProp, which adds only one forward pass per step; on MNIST/CIFAR-10 its certified accuracy is close to IBP, and training is 1.54×–2.24× faster.

Threat modelNorm-bounded threat model: the nominal input xnom is perturbed by δ to give x = xnom + δ, ||δ||p ≤ ǫ (experiments use ℓ∞, MNIST ǫtrain = 0.3, CIFAR-10 ǫtrain = 8/255); the goal is to remain correctly classified under any perturbation within this ℓp ball, and certified accuracy is given by the verifier (IBP, Fast-Lin, CNN-Cert-Zero).

Questions
Certified robust training can give neural networks provable adversarial robustness, but existing certified defenses use certifiers during training and are computationally expensive: convex outer-bound methods exceed standard training by 100×, and the fastest, IBP, also requires 3× training time.
Methods
The authors propose SingleProp: approximate the layer-wise bounds of linear bound certifiers (Fast-Lin/CROWN class) as recursive propagation of v, constructing a regularization term that requires only one additional forward pass, together with adaptive hyperparameter selection (AHS) to schedule λ.
Experiments and results
On MNIST and CIFAR-10, SingleProp's certified accuracy is close to IBP (e.g., 82.93% vs. 84.82% for Small CNN MNIST at ǫ=0.3), training is 1.54×–2.24× faster, and memory is 1.5× lower; on the Fast-Lin verifier, SingleProp-FastLin outperforms IBP-trained models.
Limitations and future work
The authors do not set aside a dedicated limitations section; the text states that the slight drop in certified accuracy stems from approximation, and that slower methods such as IBP and CROWN-IBP can achieve higher certified accuracy. Experiments cover only MNIST/CIFAR-10, four CNNs, and ℓ∞ perturbations, and the main verifier IBP favors IBP-trained models.
Experimental setupSmall CNN、Medium CNN et al. · MNIST、CIFAR-10 · certified accuracy、clean accuracy et al.
Evaluated models
Small CNNMedium CNNWide CNNLarge CNN
Benchmarks
MNISTCIFAR-10
Metrics
certified accuracyclean accuracyper epoch runtime
AI summaryThe researchers propose a regularization method, SingleProp, for training neural networks that are resistant to adversarial attacks and have certified guarantees; training requires only one additional forward pass, making it more efficient than existing certified defenses. Experiments on MNIST and CIFAR-10 show that the method trains faster than state-of-the-art certified defenses with comparable certified accuracy.

The researchers propose a regularization method, SingleProp, for training neural networks that are resistant to adversarial attacks and have certified guarantees; training requires only one additional forward pass, making it more efficient than existing certified defenses. Experiments on MNIST and CIFAR-10 show that the method trains faster than state-of-the-art certified defenses with comparable certified accuracy.

Paper analysis

6 questions; open one to read the full answer

  1. What problem does this paper attempt to solve?

    Certified robust training is expensive; the authors propose SingleProp, which adds only one forward pass per step, aiming for certified accuracy comparable to IBP.

    Core problem: certified robust training is computationally expensive; the authors aim to train networks whose certified accuracy is comparable to the fastest existing methods with minimal additional cost (only one additional forward pass).

    • Problem setting and importance: DNNs are vulnerable to adversarial examples; certified robustness methods can give provable guarantees of correct classification under any perturbation within an ℓp ball; but incorporating verification bounds into training makes each training step several times slower than standard training, and convex outer bound methods empirically exceed 100× the cost of standard training (Kolter and Wong 2018).
    • Shortcomings of existing methods: the authors state that IBP, the fastest effective certified training method at the time, still requires 2 additional forward passes, for a total training time of 3× standard training; CROWN-IBP achieves higher certified accuracy but trains 9× slower than IBP, equivalent to 26× the additional cost of standard training.
    • Core observation: robust training such as IBP can be written as a standard loss plus a regularization term Rθ(ln, un, y); the authors find that the layer-wise bounds of linear bound certifiers (Fast-Lin/CROWN) can be recursively approximated with a single quantity v, requiring only one propagation.
    • Proposed in the paper: the robust training algorithm SingleProp (with two variants, SingleProp-FastLin and SingleProp-Zero) and adaptive hyperparameter selection (AHS), which the authors call the fastest and most efficient among SOTA certified training algorithms.
    • Threat model:
      • Attacker goal: add perturbation δ to the nominal input xnom to make the network misclassify.
      • Perturbation constraint: ||δ||p ≤ ǫ; the main derivations in the paper use the ℓ∞ norm (a footnote states other p can be derived similarly).
      • Victim system: fully connected networks and general CNN (including residual network) classifiers.
      • Success criterion: the proportion still correctly classified under any perturbation within the ǫ-ℓp ball, i.e., certified accuracy, given by the verifier.
  2. What related research exists?

    Related work falls into two lines: verifiers and certified defenses; the direct baseline for comparison in this paper is IBP, and the benchmarks are MNIST and CIFAR-10.

    Verification methods

    • Exact verification: Katz et al. 2017, Cheng et al. 2017, Carlini et al. 2017 use mixed integer programming (MIP) and the like to find the exact minimum adversarial perturbation, which is computationally expensive; the exact certifier of Tjeng and Tedrake 2019 can be accelerated by the training design of Xiao et al. 2019.
    • Relaxed verification: Kolter and Wong 2018, Raghunathan et al. 2018 and others improve efficiency by convexifying the adversarial polytope but lose bound tightness; Fast-Lin (Weng et al. 2018) and the subsequent Neurify and DeepZ belong to the linear bound framework, with tighter bounds than IBP; CROWN (Zhang et al. 2018) generalizes to general activation functions, and CNN-Cert (Boopathy et al. 2019) generalizes to CNN/RNN.
    • IBP: Gowal et al. 2019 and Gehr et al. 2018 propagate interval bounds layer by layer; the paper notes that their box bounds may be very loose for general networks.

    Certified defenses

    • Adversarial training: Madry et al. 2018 and Sinha et al. 2018 are empirically resistant to attacks, but the paper notes they are not aimed at verification or certification and do not count as certified defenses.
    • Parameter regularization: Xiao et al. 2019 uses sparse weight penalties plus adversarial training to obtain easily verifiable models, and ReLU stability regularization further enhances verifiability, but the paper notes that layer regularization alone does not help certified robustness and costs at least 3× standard training.
    • Certifier-oriented training: Kolter and Wong 2018 and Wong et al. 2018 use convex outer bounds to bound the adversarial loss, with good results but slow training; IBP training (Gowal et al. 2019) is cheap and has become SOTA; CROWN-IBP (Zhang et al. 2020) achieves certified accuracy up to 2.74% on MNIST and up to 9.16% on CIFAR, but trains 9× slower than IBP. The paper notes that these "certified" defenses are not truly certified and still require a certifier on unseen points.

    Baselines and benchmarks: the direct comparison baseline is IBP (Gowal et al. 2019); Table 1 additionally lists the certified accuracy of Standard, Adv Training (Madry et al. 2018) and TRADES (Zhang et al. 2019), and Table 3 compares CROWN-IBP; the benchmarks are MNIST and CIFAR-10.

    Positioning of this paper: the authors state that SingleProp's computational cost (only 1× additional over standard training) is lower than IBP-type defenses, with performance comparable to existing methods, and that because it emphasizes efficiency it is compared in depth only with IBP rather than CROWN-IBP.

  3. How does the paper address this problem?

    Approximate the layer-wise bounds of linear bound certifiers as recursive propagation of a single quantity v, constructing a robust regularization term that requires only one additional forward pass.

    Overall idea: replace the two bounds (ln, un) in the IBP-style robust loss with an approximate bound quantity v that can be computed with a single forward pass, yielding the SingleProp regularization term; the total training cost is 2 forward + 2 backward passes.

    Problem setup and robust loss form

    • Network and threat model: an n-layer network zi+1 = Wi+1 σ(zi) + bi+1, input x = xnom + δ, ||δ||p ≤ ǫ; the main derivation assumes the ℓ∞ norm.
    • Robust loss: Lθ(zn, y) + λ Rθ, where the IBP regularization term depends on the layer output upper and lower bounds un, ln and requires two additional propagations.
    • SingleProp regularization term: Rθ(vn, znnom, y) = E[L((znnom − vn) ∘ y + (znnom + vn) ∘ (1−y), y) − L(znnom, y)], using vn to play the role of both the upper and lower bound gap.

    Recursive derivation of v (core of SingleProp)

    • Half-bound gap: define vi = ½(ziU − ziL), assuming the bound mean approximates the nominal forward value, i.e. zinom ≈ ½(ziU + ziL), so each layer's value range is approximately [znom − v, znom + v].
    • Recursion: expanding and bounding the linear bound definition of Fast-Lin gives vi ≈ |Wi|[(αi−1U + αi−1L)/2 · vi−1 + (βi−1U − βi−1L)/2] + |Wi|(αi−1U − αi−1L)/2 · zi−1nom (Eq. 6); v0 is initialized to ǫ1.
    • Approximation property: Eq. 6 is originally an approximate inequality; taking equality approximately overestimates the true bound; the authors report that this approximation is empirically very accurate, with the difference between zinom and the bound mean on the order of 1e-7 (Sec 4.1).

    Two variants: choice of activation bounds

    • SingleProp-FastLin: uses Fast-Lin-style bounds for ReLU; stable neurons ((zi−1nom + vi−1)j(zi−1nom − vi−1)j > 0) propagate by αj, unstable neurons propagate by ¾ vji−1 + ½(zi−1nom)j (Eq. 7), corresponding to an approximate Fast-Lin certifier.
    • SingleProp-Zero: the lower-bound slope of unstable neurons is taken as 0, i.e. ½(zi−1nom + vi−1)j (Eq. 8); the paper notes that it corresponds to a variant of CROWN whose lower bound always takes zero slope, and that this variant is strictly stronger than IBP, so SingleProp-Zero can be viewed as approximating the IBP bound with a single propagation.

    Runtime analysis

    • Forward: given each layer's zinom, all vi are computed with one forward pass; the robust loss requires 2 forward passes in total.
    • Backward: ∇vi can be computed layer by layer from ∇vi+1, and one more backward pass gives ∇zinom, for 2 backward passes in total.
    • Cost conclusion: compared with standard training, only 1 extra forward pass, 1 extra backward pass and 1× memory are added; the authors report it is 1.5× faster than IBP (empirically 1.5–2×) and uses 1.5× less memory, while other methods cost at least 3–27× standard training.

    Training procedure and hyperparameters

    • Procedure: a standard optimizer minimizes L + λR (Appendix B Algorithm 1); λ = 0 degenerates to standard training, and ǫ and λ each increase according to their own schedules during training.
    • Adaptive hyperparameter selection (AHS): each epoch sets λ = γLval,θ / ((1+γ)Lval,θ + Rval,θ) based on the validation set, where γ > 0 controls the trade-off between robustness and standard accuracy; the baseline is the piecewise-linear λ schedule used by IBP (increasing from 0 to 0.5).
    • ǫ schedule: follows IBP's piecewise-linear schedule, with ǫ = 0 during warmup (2000 steps for MNIST, 5000 steps for CIFAR), increasing linearly to the target value (10000 steps for MNIST, 50000 steps for CIFAR) and then fixed; the learning rate schedule is tuned separately per method on the validation set.
  4. What experiments did the paper conduct?

    Compared with IBP on four CNNs on MNIST/CIFAR-10: certified accuracy is slightly lower, training is 1.54×–2.24× faster, and it surpasses IBP-trained models on the Fast-Lin verifier.

    Experimental setup

    • Networks tested: Small CNN (4 layers), Medium CNN (7 layers), Wide CNN (5 layers) for MNIST; Small CNN (4 layers), Large CNN (7 layers) for CIFAR-10, with architectures consistent with the IBP (Gowal et al. 2019) code.
    • Datasets and training: MNIST trained for 100 epochs, batch size 100; CIFAR-10 trained for 350 epochs, batch size 50 (Gowal et al.'s original setting was 3200 epochs, batch 1600; the authors state this was computationally infeasible and they used its alternative setting). Training target perturbation ǫtrain: MNIST 0.3, CIFAR-10 8/255.
    • Comparison methods: SingleProp-FastLin, SingleProp-Zero compared with IBP; Table 1 additionally lists Standard, Adv Training, TRADES; Table 3 lists CROWN-IBP.
    • Metrics and certifiers: certified accuracy (certified acc.) and clean accuracy (clean acc.); the main certifier is IBP (the authors note this favors IBP-trained models), and Fast-Lin and CNN-Cert-Zero are additionally used to certify on 100 random test points (Table 6 uses 100/200 points).
    • Evaluation scope: under the IBP certifier, results are reported on the full test set of 10000 points, with ǫ range MNIST [0, 0.4], CIFAR [0, 9/255]; the proportion of points jointly certifiable by IBP+SingleProp is also reported (the authors state this is not the certified accuracy of a single model or an ensemble).
    • Number of repetitions: MNIST Small CNN 5 trials, CIFAR Small CNN 3 trials (Table 7), with different random initializations and batch orders.

    Main results

    Table 1: full test set IBP certified accuracy and per-epoch runtime (ǫtrain = 0.3 / 8/255).

    Swipe horizontally to read the table

    ModelMethodclean (ǫ=0)certified acc.@target ǫtime per epochspeedup
    Small CNN MNISTIBP96.21%84.82% (ǫ=0.3)6.3s—
    Small CNN MNISTSingleProp-Zero94.71%82.93% (ǫ=0.3)4.0s×1.58
    Medium CNN MNISTIBP97.17%88.63% (ǫ=0.3)15.0s—
    Medium CNN MNISTSingleProp-Zero97.45%86.05% (ǫ=0.3)7.1s×2.12
    Wide CNN MNISTIBP98.52%89.35% (ǫ=0.3)87.7s—
    Wide CNN MNISTSingleProp-Zero97.01%87.59% (ǫ=0.3)53.1s×1.65
    Small CNN CIFARIBP36.46%25.99% (ǫ=8/255)14.8s—
    Small CNN CIFARSingleProp-FastLin37.79%24.51% (ǫ=8/255)7.2s×2.07
    • Accuracy gap: the authors state SingleProp's certified accuracy drops only slightly; in Table 1 the gap at the target ǫ is MNIST −1.89% (Small), −2.58% (Medium), −1.76% (Wide), CIFAR Small −1.48%, Large −3.74% (Large row: IBP 25.68% vs. SingleProp-FastLin 21.94%, speedup ×2.02).
    • Speed: the authors report speedup ratios of 1.54×–2.24× (Table 1 and Table 4), exceeding the 1.5× expected from the number of forward passes.
    • Exceptions: on Medium CNN MNIST, SingleProp-Zero's clean acc. is higher than IBP's (+0.28%); on CIFAR Small the clean acc. is also higher (+1.33%).

    Performance under other certifiers (Table 5, Table 6)

    • What was tested: IBP, Fast-Lin and CNN-Cert-Zero were used to certify IBP- and SingleProp-trained models on 100 random test points.
    • Results: on CIFAR Small CNN, under the Fast-Lin certifier the IBP model reaches only 14% at ǫ=8/255, while SingleProp-FastLin reaches 29%; under the IBP certifier the two are 34% and 30%. On MNIST, IBP and CNN-Cert-Zero certification results are similar (e.g., at ǫ=0.3, IBP model 93%, SingleProp-Zero 91–92%).
    • Authors' interpretation: SingleProp-FastLin maintains accuracy under Fast-Lin similar to that under the IBP certifier, indicating it is indeed suited to Fast-Lin; joint Fast-Lin+IBP certification is similar to IBP alone, on which basis the authors consider using IBP as the main certifier reasonable.

    Certification complementarity and multiple trials (Table 7)

    • What was tested: the union of the point sets each certifiable by IBP and SingleProp ({A}), and the mean and standard deviation over multiple trials.
    • Results: on CIFAR Small CNN, joint certification reaches 33.79%–34.73% at ǫ=8/255 (3 trials), an improvement of +7.22% to +8.53% relative to the single IBP model; among 5 trials on MNIST Small CNN, SingleProp-Zero's certified accuracy has a maximum standard deviation of 2.36% (ǫ=0.3). The authors state joint certification improves by 2–4% on MNIST ǫ=0.3 and by 6–9% on CIFAR ǫ=8/255.
    • Authors' interpretation: the points certified by IBP and SingleProp are complementary, and the complementarity with SingleProp-FastLin is stronger; the authors suggest this may be because SingleProp-FastLin approximates Fast-Lin and can certify points that IBP-type training finds hard to certify.

    Other ablations and analyses

    • Approximation error (Sec 4.1): on Small CNN MNIST, metric 1 (the difference between zinom and the bound mean) has mean IBP 8.83E-07, SingleProp-Zero 4.08E-07; metric 2 (relative gap) IBP 0.018, SingleProp-Zero 0.003, which the authors call accurate approximation.
    • AHS comparison (Table 4): except for the IBP model on Small CNN MNIST, AHS improves certified accuracy at the target ǫ; for SingleProp models it improves by about 1% at most ǫ and drops by at most 0.05%.
    • Comparison with CROWN-IBP (Table 3): CIFAR Small CNN ǫ=8/255 certified accuracy SingleProp-FastLin 24.51% (1× cost), IBP 25.99% (2×), CROWN-IBP 29.24% (26×).
    • 100 vs. 200 points (Table 6): on CIFAR Small CNN the 100-point and 200-point certification results are similar (e.g., SingleProp-FastLin, Zero certifier: 25% vs. 20.0%); note the networks used differ from Table 5.
    • Negative result: on Large CNN CIFAR, SingleProp-FastLin is lower than IBP at every ǫ (clean −2.44%, −3.74% at ǫ=8/255); the authors note that slower methods can achieve higher certified accuracy, corresponding to different points on the trade-off curve between training time and certification level.
  5. What are some points that can be further explored?

    The paper does not set aside a dedicated limitations section; experiments cover only MNIST/CIFAR-10, four CNNs, and ℓ∞ perturbations, and the main verifier favors IBP.

    Limitations and future directions noted by the authors

    • Slight drop in certified accuracy stems from approximation: in Sec 4.1 and the Conclusion, the authors state that SingleProp's slightly lower certified accuracy than IBP is the expected result of the approximation used by the method.
    • Slower methods have higher accuracy: Sec 4.1 (Runtime Improvement) notes that slower methods such as IBP and CROWN-IBP can obtain higher certified accuracy at the cost of computational efficiency, corresponding to different points on the trade-off curve between training time and certification level; the authors state SingleProp may be more suitable when computational and memory costs are considered.
    • Risks in the ethics statement: the Ethical Impact section notes that reliance on verification may give users unfamiliar with verification techniques a false sense of security, and users may understand verification results as covering a broader range of attacks than the perturbation norm actually verified; the authors consider it important to properly communicate the type and degree of robustness implied by verification to reduce risk.
    • The paper has no separate Limitations or Future Work section; the above comes from Sec 4.1, the Conclusion and Ethical Impact.

    Scope of experimental coverage

    • Datasets and models: only MNIST and CIFAR-10; the networks tested are four CNN types—Small, Medium, Wide, Large (the first three for MNIST, Small and Large for CIFAR-10).
    • Perturbation type: experiments use only ℓ∞ perturbations (MNIST ǫtrain = 0.3, CIFAR-10 ǫtrain = 8/255); other ℓp norms are only stated in a footnote to be derivable similarly, with no experiments.
    • Certifiers: the main certifier is IBP (the authors note this favors IBP-trained models); Fast-Lin and CNN-Cert-Zero are evaluated only on 100 random test points, with Table 6 additionally using 200 points.
    • Number of repetitions: multiple trials appear only for MNIST Small CNN (5) and CIFAR Small CNN (3) (Table 7); the paper does not report repetition counts for the Medium, Wide and Large models.
    • Training setup: due to computational constraints, CIFAR uses 350 epochs and batch size 50 rather than Gowal et al.'s 3200 epochs and batch size 1600; the authors note this differs from Gowal et al.'s main results, and that they use the IBP certifier rather than its MILP exact certifier, giving lower certified accuracy.
  6. Summarize the main content of the paper

    SingleProp approximates linear bound certifiers with a single additional forward pass; certified accuracy is close to IBP, and training is 1.54×–2.24× faster.

    A defense paper on the efficiency of certified robust training, aimed at training scenarios for provably correct classification under ℓp-norm-bounded adversarial perturbations.

    • Problem addressed: existing certified defense training is expensive—convex outer-bound methods exceed standard training by 100×, and the fastest, IBP, also requires 3× training time; the authors ask: what is the minimum computational cost needed to achieve certified robustness.
    • Method highlights: they propose SingleProp, which approximates the inter-layer upper and lower bounds of Fast-Lin/CROWN-type linear bound certifiers as recursive propagation of a single quantity v (assuming the bound mean is approximately equal to the nominal forward value), constructing a robust regularizer that requires only one additional forward pass; depending on the activation bound selection it is divided into two variants, SingleProp-FastLin and SingleProp-Zero, and they propose validation-set-based adaptive hyperparameter selection (AHS) to schedule λ.
    • Main results (Table 1): MNIST Small CNN, at ǫ=0.3, SingleProp-Zero certified accuracy 82.93% vs. IBP 84.82%, speedup ×1.58; CIFAR Small CNN, at ǫ=8/255, SingleProp-FastLin 24.51% vs. IBP 25.99%, speedup ×2.07; speedup ratios across settings 1.54×–2.24×, memory savings 1.5×.
    • Other results: under the Fast-Lin certifier, SingleProp-FastLin outperforms the IBP-trained model (CIFAR ǫ=8/255: 29% vs. 14%, Table 5); IBP and SingleProp certified points are complementary, and joint certification improves by 6–9% at CIFAR ǫ=8/255 (Table 7); CROWN-IBP has higher accuracy (29.24%) but costs 26× (Table 3).
    • Authors' conclusion: the authors state that SingleProp is the fastest and most efficient of the SOTA certified training algorithms, with certified accuracy comparable to IBP; the slight accuracy drop is the expected cost of approximation, slower methods correspond to different points on the trade-off curve, and SingleProp may be more suitable when computational and memory costs are considered.

Related papers

Show 3 more papers
Read originalarxiv.org