mlsanityData to 14 Oct 2026

A Sublinear Adversarial Training Algorithm

arXiv 2208.05395 ↗First posted 10 Aug 2022cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

Adversarial training is a widely used strategy for making neural networks resistant to adversarial perturbations. For a neural network of width m, n input training data in d dimension, it takes Omega(mnd) time cost per training iteration for the forward and backward computation. In this paper we analyze the convergence guarantee of adversarial training procedure on a two-layer neural network with shifted ReLU activation, and shows that only o(m) neurons will be activated for each input data per iteration. Furthermore, we develop an algorithm for adversarial training with time cost o(m n d) per iteration by applying half-space reporting data structure.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Builds on 35 of its 48 references that are in the map. First posted on arXiv 10 Aug 2022.

Builds on

35 of 48 references.

References · 35

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2013Intriguing properties of neural networkscited by 5,155
  3. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,998
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  5. 2020Reformer: The Efficient Transformercited by 1,668
  6. 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,268
  7. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  8. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  9. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  10. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  11. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  12. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
23 more
  1. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  2. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  3. 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
  4. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  5. 2019Quadratic Suffices for Over-parametrization via Matrix Chernoff Boundcited by 59
  6. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  7. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  8. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  9. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  10. 2020Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionalitycited by 36
  11. 2021Solving SDP Faster: A Robust IPM Framework and Efficient Implementationcited by 33
  12. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  13. 2020A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Pathcited by 29
  14. 2020Generalized Leverage Score Sampling for Neural Networkscited by 26
  15. 2022Speeding Up Sparsification using Inner Product Search Data Structurescited by 22
  16. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  17. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  18. 2021Accelerating SLIDE Deep Learning on Modern CPUs: Vectorization, Quantizations, Memory Optimizations, and Morecited by 15
  19. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  20. 2022Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysiscited by 15
  21. 2022Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structurescited by 9
  22. 2022A Faster Interior-Point Method for Sum-of-Squares Optimizationcited by 7
  23. 2016Principal Component Projection Without Principal Component Analysiscited by 6

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 15; 2024: 3; 2025: 2.

22 papers.

Sort:

  1. 2023An Over-parameterized Exponential Regressioncited by 45
  2. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  3. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  4. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  5. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  6. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  7. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  8. 2023Beyond Classical Attention: Quantum Attention for Scalable Computationcited by 18
  9. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  10. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  11. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  12. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
10 more
  1. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  2. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  3. 2023Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?cited by 8
  4. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  5. 2023Structured and Fast Optimization: The Kronecker SGD Algorithmcited by 5
  6. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  7. 2023Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTKcited by 2
  8. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  9. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  10. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0