Research map / Adversarial robustness and security / Certified and empirical robustness
A Sublinear Adversarial Training Algorithm
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.
Proves convergence of adversarial training for a two-layer shifted-ReLU network and gives a half-space-reporting-based algorithm whose per-iteration cost is sublinear (o(mnd)) in network width.
Problem
Adversarial training of wide two-layer neural networks costs Omega(mnd) per iteration for forward and backward passes, which is expensive for large width m and n training points.
Approach
Shows that with a shifted ReLU activation only o(m) neurons are activated per input during adversarial training, and uses a half-space reporting data structure over neuron weights to find activated neurons quickly, giving sublinear per-iteration time while retaining convergence guarantees under adversarial perturbations.
Key results
- Main theorem claims expected per-iteration time o(mnd) for the adversarial training algorithm on a two-layer shifted-ReLU network.
- Shows only o(m) neurons are activated per input per iteration, with the number of sign-changed neurons bounded by O(n m^{7/8}) over training.
- Per-iteration running time stated as roughly m^{1-Theta(1/d)} n d up to polylog factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use half-space range reporting to identify activated neurons | Sublinear adversarial training · Adversarial training, per iteration | time cost: o(mnd) | Helped |
| Use shifted ReLU activation | Two-layer neural network · Training data, per input and iteration | activated neurons: o(m) | Helped |
| Train with the proposed algorithm against a bounded adversary | Two-layer shifted-ReLU neural network · Worst-case adversarial training loss | robust training loss | Helped |
Limitations
- Purely theoretical; no experiments validate the speedup or convergence in practice.
- Requires very large width (m polynomial in n, d, 1/epsilon) and a strong well-separated data assumption.
- Analysis applies only to two-layer networks with shifted ReLU and fixed output weights.
Experimental setup
Metrics: per-iteration time complexity robust training loss convergence
Builds on: neural tangent kernel over-parameterization analysis SLIDE half-space range reporting data structure
Closest papers by meaning
- Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality (NeurIPS 2020 · similarity 0.89)
- Stability and Generalization of Adversarial Training for Shallow Neural Networks with Smooth Activation (NeurIPS 2024 · similarity 0.88)
- Adversarial Examples Exist in Two-Layer ReLU Networks for Low Dimensional Linear Subspaces (NeurIPS 2023 · similarity 0.88)
- Clarifying the Behavior and the Difficulty of Adversarial Training (AAAI 2024 · similarity 0.87)
- You Only Propagate Once: Accelerating Adversarial Training via Maximal Principle (NeurIPS 2019 · similarity 0.86)
- Adversarial Training Should Be Cast as a Non-Zero-Sum Game (ICLR 2024 · 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.