Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes theoretically the robustness of adversarial training of two layer neural network.
The analysis is done on a linearly separable dataset through slightly modifying the objective of PGD attacks.
Experimental analysis of the proposed modification of PGD attacks are carried our on small scale problems.
strength_and_weaknesses: The main strength of this paper is the theoretical analysis presented in section 3. It is very useful to analyze the convergence of such popular approach in building robust models to allow theoretically supported robustness enhancements. However, there are key concerns about the effectiveness of this work:

- First, the experimental results are very limited to very small scale problems. The argument of this work would have been much stronger if it was demonstrated on standard robustness benchmarks showing robustness improvements.

- The analysis presented in sections 2 and 3 assumes Leaky ReLU activation function, while the experiments are carried out on ReLU-based networks. However, substituting $\alpha \rightarrow 0$ in Theorem 3.4 would yield $T_{tr} \leq \infty$. That is, if I understood correctly, Theorem 3.4 does not bring useful conclusions about adversarial training  under the experimental setup even when using a two-layer network. Please correct me if I am missing something in the previous argument.

- The assumptions in the theoretical analysis limit the usefulness of the results. For instance, why is the weights of the second linear layer, $i.e.$ are kept fixed? In Assumption 3.3, the input space is assumed to be bounded. However, $R$ could be extremely large in reality $e.g. R=(255)\sqrt{d}$ for images where $d$ is the number of pixels. This would result in an extremely small learning rate as per Theorem 3.4.

Minor concerns:

- The writing of the paper can be further improved. There are few typos such as: "in terms of the and..." in page 4. 

- Table 1 is hard to read. Please consider highlighting main number in the table with stating the main message in the caption.

- The proof sketch in section 3.1 seems a bit disconnected from the rest of the paper. Please consider moving it to the appendix.

- The main result of this work (Theorem 3.4) is about the convergence guarantees of adversarial training. Please consider reflecting that into the title as robustness guarantees usually refers to some sort of certified robustness.


clarity,_quality,_novelty_and_reproducibility: The claims in this work as clear and novel in some aspects. However, the presented results have limited impact.
summary_of_the_review: My main concerns about this work are: (1) The limited experimental analysis. (2) The mismatch between the theoretical results and the experimental setup. (3) The usefulness of the theoretical results under the stated assumptions. 
Please refer to the review for more details.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the robust adversarial learning problem for a binary classification task, where the standard adversary's logistic loss function is reflected around the origin. Specifically, the classifier is chosen to be a one-hidden layer neural network with leaky-ReLU activation, and the two classes are assumed to be linearly separable. Under these assumptions, the paper proves a convergence guarantee for the projected gradient descent optimization algorithm. The paper presents some numerical results on binary and multi-class classification problems to support the proposed bi-level adversarial training approach and the shown convergence results. 
strength_and_weaknesses: Strengths:

1) The paper is well-written and the presentation is satisfactory.

2) The idea of reflecting the surrogate logistic loss around the origin sounds highly interesting to me, since it resolves the non-concavity of the surrogate loss in the adversary's maximization problem. The idea seems to be potentially useful for other theoretical analyses of adversarial training problems as well. 

Weaknesses:

1) The paper's convergence analysis is based on two relatively strong assumptions: 1) the analysis targets a binary classification problem and its extension to multi-class classification problems looks challenging, 2) the two classes are supposed to be linearly separable.

2) While I very much like the reflection idea for the inner maximization problem, this change leads to a different bi-level optimization problem from the standard min-max adversarial training problem. Therefore, while the paper's introduction sets the goal of understanding the convergence properties of robust adversarial training, the proposed framework deviates from standard robust training approaches. 
I am wondering what the results of the paper could imply about the convergence of standard min-max adversarial training. 
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, and the analysis and results look novel to me.
summary_of_the_review: This paper proposes a new approach to robust adversarial training by proposing a novel bi-level optimization problem based on reflecting the maximization surrogate loss function around the origin. While the analysis is restricted to binary classification problems with linearly separable classes, I think the paper contributes interesting ideas for analyzing adversarial training problems.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to reflect the surrogate loss about the origin for the inner maximization of adversarial training. This paper proves convergence guarantees for the PGD attack under a margin separability assumption on such a surrogate loss with two-layer neural networks with the Leaky ReLU activation function.
strength_and_weaknesses: Strengths :

- The paper is well written.

- A novel technique was used for proof.

Weaknesses :

- (critical) It considers two-layer neural networks with the Leaky ReLU activation function under a linearly separability assumption. But what is the point of robustness of neural networks models for linearly separable data? Since some works already showed robust generalization error guarantees for adversarially trained linear models under a linearly separability assumption, I wonder what are the new contributions.

- The results of the experiment are not significantly good.
clarity,_quality,_novelty_and_reproducibility: There is no particular problem with quality, clarity and originality.

summary_of_the_review: This paper proves convergence guarantees for the PGD attack under a linearly separability assumption with two-layer neural networks. Although it's technique was impressive, I'm not sure what the point of robustness of neural networks models for linearly separable data is.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on convergence analysis of adversarial training for finite-width two-layer Leaky ReLU networks. Convergence guarantees are given for both inner-loop PGD-style adversarial attack (in deterministic form) and end-to-end adversarial training with imperfect attack (in expectation form). To ease the analysis, the framework focuses on binary classification setting with only first-layer weights updatable. Moreover, in the inner-loop attack, authors propose a lower bound of 0-1 loss as the surrogate and the training gradients use the classical binary sigmoid loss as the surrogate. Lastly, the lower bound surrogate loss is demonstrated to be effective in practice (on MNIST, CIFAR-10).
strength_and_weaknesses: Strengths:
- Strong theoretical guarantees of adversarial training under loose assumptions. Theorem 4 establishes the convergence of adversarial training in terms of a small expected error of large-margin adversarial examples, for finite-width two-layer Leaky-ReLU networks. These results seem to be the first of this kind. Technically, the proof relies on the monotonicity of gradients - a specific mathematical property of the well-designed surrogate loss along with telescoping cancellation, which is not straightforward.

- The paper also establishes the deterministic convergence guarantee for adversarial training.

- The proposed lower bound surrogate loss for the adversarial attack is effective in practice which may of independent interests.

- The writing quality in the main text is great and it is easy to follow.

Weaknesses:
- The analysis is limited in the following aspects: (1) The analyzed two-layer neural network does not allow the weight evolvement in the second-layer, which is different from the adversarial training practice. (2) The latent assumption of linear separation (second point of Asumption 3.3) seems strong. (3) Extension of the analysis to multi-class settings may be hard.

- The proof can be made more rigorous. For instance, I got lost in the following places:

  1. Proof of Thm 3.2: Let $G := ||W||_F$ and $\kappa \sqrt m ||W||_F =: G$ seem to be contradicting.
  2. Proof of Thm 3.2, page 13 upper part: how does average case guarantee $\frac{1}{T} \sum_{t=1}^T -\ell_- (yf_W(\delta_t)) \le ...$ lead to single instance guarantee $-\ell_-(yf_W(\delta_{att})) \le ...$? From the bottom of page 13, it seems to be because $-\ell_-(yf_W(\delta_{att})) = \min_{t\in[T]} -\ell_-(yf_W(\delta_t))$. However, why is this guaranteed? Since it is a project GD, when the step size is sufficiently small I can see it holds, but does it hold generally?
  3. Proof of Lemma 3.7, page 14: why is it an equality in $y_t \sum_{r=1}^m \langle a_r \sigma'(w_r \cdot \delta)\delta, \frac{1}{\sqrt m} \mathrm{sgn}(a_r)v_* \rangle = \frac{\kappa}{\sqrt m} \sum_{r=1}^m \sigma'(w_r\cdot \delta) y_t\langle \delta, v_*\rangle$? We only know $||a||_{\infty} \le \kappa$ but does it lead to $a_r = \kappa$ for any $r$?
  4. Proof of Lemma 3.7, bottom of page 15: how does $\tau \le ...$ connect to $T \le ...$? If I understand correctly, we need $T \ge \lceil \tau \rceil + 1$ to lead to contradiction. But here, RHS of $\tau \le ...$ seems to be squared which may not imply $T \ge \lceil \tau \rceil + 1$.

- How does this convergence-guaranteed adversarial training of two-layer DNN compare to exact-convex-opt-solving-based adversarial training (e.g., [1])?

[1] Bai, Yatong, Tanmay Gautam, and Somayeh Sojoudi. "Efficient global optimization of two-layer relu networks: Quadratic-time algorithms and adversarial training." arXiv preprint arXiv:2201.01965 (2022).


Minor:
1. After Definition 3.1, "in terms of the and the negated loss derivative": missing noun
2. After Theorem 3.2, $O(\beta^2 / \epsilon)$ iteration may need further justification
3. Section 4.1 may be moved to appendix to gain space for proof sketching of Thm. 3.2 and Lemma 3.7
4. Table 2's result is hard to parse. Why larger attack steps for RA columns can lead to significantly larger robust accuracy? Also, what does SA mean? When attach size $\nu$ is specified in the table, how is it different from caption of Table 2 which says $\nu = 8/255$?

clarity,_quality,_novelty_and_reproducibility: The clarify and quality of the main text is generally great. The result is novel to the best of my knowledge. However, some steps in the appendix proof may be unclear.
summary_of_the_review: Though I got lost in some steps of the proofs, assuming that the proofs are all correct and will be revised clear, and the related work is discussed comprehensively (I'm not working in DL theory so cannot evaluate this aspect), I think the contribution is sufficient, of interest to the community, and worth acceptance - the results further our theoretical understanding of adversarial training.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies adversarial training on shallow Leaky ReLU networks under a linear separability assumption, and is able to prove guarantees using a modified adversarial attack.  Reviewers were almost exactly borderline, and discussion also was heavily borderline. 
 Unfortunately, due to the high bar at ICLR this year, a final calibration put this paper just microscopically away from the decision boundary, on the reject side.  We apologize for this disappointment, and urge the authors to refine their work and submit to a future venue.

One concern that arose late in the review phase was that the proof is very closely related to prior work due to Frei et al., to the extent that here is some concern that the modified loss was reverse engineered to allow that proof to go through.  Furthermore, it's not clear why this proof technique requires linear separability (plus noise).  We hope that these comments, plus various reviewer comments, can all be addressed by the authors to make their work even more exciting and a clear accept at a future venue.
justification_for_why_not_higher_score: The assumptions are very strong (linear separability with smaller adversarial perturbations), and the proof and technical content are highly reliant on a proof in similar settings by Frei et al (as cited in this work).  Indeed the paper seems highly incremental from that prior work, and while it constitutes definite progress, I feel this incremental nature contributed to the (consistent!) indecision of the reviewers.
Decision: Reject