Research map / Adversarial robustness and security / Certified and empirical robustness
Stop Walking in Circles! Bailing Out Early in Projected Gradient Descent
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PGD with Cycle Detection (PGDCD), which terminates PGD early when an iterate repeats under a fixed step size, giving identical robust accuracy to standard PGD with large iteration savings.
Problem
Standard PGD adversarial robustness evaluation under L-infinity needs up to 1000+ iterations per image, which is computationally expensive, especially for robust models where most images are never misclassified.
Approach
With a fixed step size, PGD iterates on robust inputs often fall into closed cycles on the L-infinity ball boundary; storing hashes of perturbations and terminating upon revisiting a point (or upon successful misclassification) yields exactly the same robust accuracy with far fewer forward/backward passes.
Key results
- PGD with cycle detection reproduces standard PGD robust accuracy exactly on all 12 RobustBench models while reducing iterations by up to 96%; ImageNet models typically see about 90% reduction (~10x).
- On CIFAR10, some models reach over 95% iteration reduction (about 20-25x), with a worst case of roughly 45%.
- Tricked images are detected in a median of 3 PGD iterations across robust models, and PGDCD with restarts matches or beats APGD on CIFAR at lower compute.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add cycle detection and terminate PGD when an iterate repeats | PGD · ImageNet | robust accuracy: 58.15 -> 58.15; 59.27 -> 59.27; 42.70 -> 42.70; 55.03 -> 55.03; 67.52 -> 67.52 | No clear effect |
| Add cycle detection and terminate PGD when an iterate repeats | PGD · ImageNet | PGD iterations: 29,110,933 -> 2,681,126; 29,396,885 -> 2,646,549; 21,409,926 -> 2,160,645; 27,555,582 -> 16,073,533; 33,784,085 -> 2,758 | Helped |
| Add cycle detection and terminate PGD when an iterate repeats | PGD · CIFAR100 | robust accuracy: 44.93 -> 44.93; 38.93 -> 38.93; 48.19 -> 48.19; 40.22 -> 40.22 | No clear effect |
| Add cycle detection and terminate PGD when an iterate repeats | PGD · CIFAR100 | PGD iterations: 4,525,073 -> 4,448,355; 3,903,289 -> 170,518; 4,826,965 -> 184,368; 4,052,162 -> 3,984,016 | Mixed |
| Add cycle detection and terminate PGD when an iterate repeats | PGD · CIFAR10 | robust accuracy: 62.01 -> 62.01; 59.05 -> 59.05; 59.61 -> 59.61 | No clear effect |
| Add cycle detection and terminate PGD when an iterate repeats | PGD · CIFAR10 | PGD iterations: 6,214,308 -> 3,371,294; 5,919,769 -> 274,794; 5,968,606 -> 215,905 | Helped |
| Add random jumps to a new initialization after cycle detection (ablation) | PGDCD · CIFAR100 and CIFAR10 | robust accuracy: 45.02 -> 45.03; 38.93 -> 38.68; 48.19 -> 47.85; 40.30 -> 40.33; 62.02 -> 61.92; 59.05 -> 58.78; 59.61 -> 59.34 | Mixed |
| Use PGDCD instead of APGD | PGD attack evaluation · CIFAR100 and CIFAR10 | robust accuracy: 56.48 -> 45.02; 38.46 -> 38.93; 48.41 -> 48.19; 51.01 -> 40.30; 69.35 -> 62.02; 70.09 -> 59.05; 58.38 -> 59.61 | Mixed |
Surprising findings
- Standard PGD with a fixed step size often matches or exceeds APGD, the supposedly stronger adaptive attack, on newer RobustBench architectures.
- Cycles are essentially always on the boundary of the L-infinity ball; no interior cycles were observed in experiments.
Limitations
- Savings are concentrated on robust inputs; gains are small or absent for some CIFAR100 models (<2% or failure cases).
- Hashing on CPU is slow; the authors use an unoptimized hash and note a CUDA hash would be faster.
- Exact cycle detection is tied to fixed step size PGD; cosine-similarity-based inexact breaking was not explored.
Experimental setup
Datasets: CIFAR10 CIFAR100 ImageNet
Benchmarks: CIFAR10 CIFAR100 ImageNet RobustBench
Metrics: robust accuracy number of PGD iterations wall-clock time reduction
Baselines: standard PGD APGD AutoAttack ensemble (RobustBench)
Builds on: Projected Gradient Descent AutoAttack RobustBench
Closest papers by meaning
- Robustness Guarantees for Adversarially Trained Neural Networks (NeurIPS 2023 · similarity 0.88)
- Finding Actual Descent Directions for Adversarial Training (ICLR 2023 · similarity 0.87)
- Mind the Box: $l_1$-APGD for Sparse Adversarial Attacks on Image Classifiers (ICML 2021 · similarity 0.87)
- Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks (ICML 2020 · similarity 0.87)
- RP-PGD: Boosting Segmentation Robustness with a Region-and-Prototype Based Adversarial Attack (AAAI 2025 · similarity 0.86)
- Enhancing the Adversarial Robustness via Manifold Projection (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.