A Sublinear Adversarial Training Algorithm

Thank you for your meticulous review and valuable suggestions. We will revise the typos in the next version. We would like to respond to your questions respectively:

1. Our paper is theoretically relevant and analyzes the convergence guarantee of adversarial training procedures on a two-layer neural network with shifted ReLU activation, demonstrating that only a sublinear number of neurons (o(m)) are activated for each input data per iteration​ and developing an algorithm for adversarial training with time cost o(mnd) per iteration by applying half-space reporting data structure.
2. The generalization of our method to multiple layers is a very interesting question. However, as the main purpose of our submission is to build an algorithm with guaranteed performance and rigorous analysis, we focus on over-parametrized two-layer neural network, which is a common object studied in many recent works about neural tangent kernel [1,2,3,4,5,6] and theoretical papers about deep learning [7,8,9]. We also note that there are new empirical results on multi-layer neural network settings [10,11]. We highly appreciate such efforts and would make theoretical analysis of multiple-layer neural network settings our future work.
3. We thank you for pointing out the writing improvement suggestions. We will update the overall structure in the next version.

As for your questions:

1. The contribution of this paper is a theoretical. The introduced half-space reporting data structure used in this paper will take additional $O(n \log n)$ space [12] . To have an intuitive understanding of the level of such additional memory usage, we would point out that the weights of neural networks takes $O(n d)$ space. So when the neural network is over-parameterized, i.e., $d$ is very large, the additional memory usage by our algorithm is not the dominant term in space complexity.

2. The definition of $\epsilon$-net is defined as follows: Given a metric space $(X, d)$, a subset $Y$ of $X$ is said to be an $\epsilon$-net if

   (i) For $a, b \in Y$ , we have $d(a, b) \ge \epsilon$, and

   (ii) For all $x \in X$, there exists an $a \in Y$ such that $d(x, a) < \epsilon$.

3. As for deeper NN, please refer to point (2) in the weakness part response.

[1] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In NeurIPS. arXiv preprint arXiv:1811.04918, 2019a.

[2] Arthur Jacot, Franck Gabriel, and Cl ́ement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571–8580, 2018.

[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In ICML, 2019b.

[4] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In NeurIPS, 2019c

[5] Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over-parameterized adversarial training: An analysis overcoming the curse of dimensionality. Advances in Neural Information Processing Systems, 33:679–688, 2020.

[6] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In ICLR, 2019.

[7] Zhong, Kai, et al. "Recovery guarantees for one-hidden-layer neural networks." International conference on machine learning. PMLR, 2017.

[8] Du, Simon, et al. "Gradient descent finds global minima of deep neural networks." International conference on machine learning. PMLR, 2019.

[9] Mei, Song, Andrea Montanari, and Phan-Minh Nguyen. "A mean field view of the landscape of two-layer neural networks." Proceedings of the National Academy of Sciences 115.33 (2018): E7665-E7671.

[10] Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, et al. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. Proceedings of Machine Learning and Systems, 2:291–306, 2020

[11] Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. Mongoose: A learnable lsh framework for efficient neural network training. In International Conference on Learning Representations, 2021.

[12] Pankaj K Agarwal, David Eppstein, and Jiri Matousek. Dynamic half-space reporting, geometric optimization, and minimum spanning trees. In Annual Symposium on Foundations of Computer Science, volume 33, pages 80–80. IEEE COMPUTER SOCIETY PRESS, 1992

We deeply appreciate your insightful feedback and are grateful for the time you took to share it.

1. This is a very interesting future direction. We also note that there are new empirical works on multi-layer neural network settings [1, 2] that find a similar phenomenon of sparsity that inspired this work. We highly appreciate such efforts and would make theoretical analysis of multiple layer neural network setting as our future work.
2. We would point out that if the adversarial example construction is not optimal, it does not hurt the acceleration achieved by our algorithm. However, we also admit that if we are not using the optimal adversarial construction, then the error bound in Theorem 4.4 for weights will be worse. Depending on what specific assumptions we make for the non-optimal adversarial examples, e.g. we are using adversarial construction $A$ instead of the optimal one $A^*$, the error bound for $W$ will be correspondingly worse.
3. As mentioned in point 1, some empirical works observe a similar phenomenon of sparsity in multi-layer neural networks. Hence the intuition might still be avoiding making redundant $0$-update for non-activated neurons. The major difficulty would then be designing new data structures that could efficiently maintain activated neurons during the adversarial training procedure, which we make as a very interesting future direction.

[1] Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, et al. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. Proceedings of Machine Learning and Systems, 2:291–306, 2020

[2] Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. Mongoose: A learnable lsh framework for efficient neural network training. In International Conference on Learning Representations, 2021.

Thank you for your valuable questions. We would revise the typos in the next version.

1. We take standard adversarial example construction in our algorithm. So if we let $T$ denote the complexity for the adversarial example oracle, then the improvement our algorithm achieved is $o(nmdT)$ compared to standard algorithm $\Omega(nmdT)$.
2. As mentioned above, if we let $T=O(1)$, i.e., use $x_i$ as training example, then our algorithm achieves $o(nmd)$ compared to the well-known standard result $\Omega(nmd)$.

Thank you for your valuable feedback. We would revise the typos in the next version. We admit it is very important to take memory usage into consideration in this work. The introduced half-space reporting data structure used in this paper will take additional $O(n \log n)$ space [1] . To have an intuitive understanding of the level of such additional memory usage, we would point out that the weights of neural networks takes $O(n d)$ space. So when the neural network is over-parameterized, i.e., $d$ is very large, the additional memory usage by our algorithm is not the dominant term in space complexity.

[1] Pankaj K Agarwal, David Eppstein, and Jiri Matousek. Dynamic half-space reporting, geometric optimization, and minimum spanning trees. In Annual Symposium on Foundations of Computer Science, volume 33, pages 80–80. IEEE COMPUTER SOCIETY PRESS, 1992