Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors consider two problems: 1) relating convex surrogate losses with zero-ones losses in adversarial training; 2) bounding the (adversarial) convex risk of shallow ReLU networks. 

For the former, the authors' results apply to a very broad setting -- arbitrary perturbation sets and general data distributions. They show a global relation between convex and zero-one losses. Previous work indicated that convex losses may not be calibrated, making them inadequate surrogates for the zero-one loss in adversarial settings. The authors show that if an optimal threshold is chosen, one can bound the zero-one loss via the convex surrogate.

For the latter problem, the authors restrict their attention to $\ell_2$ perturbations. Following the approach of [2], the authors characterize the (adversarial) risk near initialization of training shallow ReLU networks using the logistic loss.
strength_and_weaknesses: # Strengths

The results connecting zero-one losses with convex surrogates are elegant and easy to follow. In particular, I like how the simple statement of Lemma 3.1 opens the door for the remaining results in Section 3.

# Weaknesses
There are multiple axes along which the current paper falls short of applying to realistic settings: 1) the assumption that one is given an oracle adversary, i.e. we have access to the worst-case perturbation (as opposed to a noisy gradient oracle, i.e. just doing PGD); 2) the results in section 4 apply only to shallow fully-connected ReLU networks; 3) the results hold only in a regime very close to initialization and it is assumed one has an early stopping criterion/oracle.

Weaknesses 2) and 3) are not unique to this work, and thus I heavily discount their severity when considering my overall recommendation.
clarity,_quality,_novelty_and_reproducibility: # Clarity
- Figure 1 seems misleading -- it implies that the paper tackles the "early phase" of training before robust overfitting kicks in, which could span on the order of tens of epochs. In contrast, if I understand correctly (according to e.g. Figure 1 in [2]), the "early phase" considered in this paper is significantly shorter -- empirically one would expect it to span only a few batch updates.


# Novelty
The proposed approach is a clever combination of the idea that only *calibrated* convex losses are useful as surrogates for the 0-1 loss in adversarially robust classification [1], and the ideas presented in [2] relating early stopping and calibration


[1] Bao, Han, Clay Scott, and Masashi Sugiyama. "Calibrated surrogate losses for adversarially robust classification." Conference on Learning Theory. PMLR, 2020.

[2] Ji, Ziwei, Justin Li, and Matus Telgarsky. "Early-stopped neural networks are consistent." Advances in Neural Information Processing Systems 34 (2021): 1805-1817.
summary_of_the_review: The authors present novel ideas about convex surrogates for adversarial training, and extend previous works on generalization from standard training to the adversarial training. The paper is well-written. Overall, I believe it will be a valuable addition to the field. Thus, I recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides generalization bounds for the adversarial risk of two-layers neural networks trained with early stopping and an ideal adversary (i.e., an adversary that computes perfect adversarial attacks). They do so by providing new results on the Rademacher complexity of the outcome of adversarial attacks on linearized two-layers NNs close to initialization.
strength_and_weaknesses: ## Strengths:

- The results seem novel
- The question of learning efficient, robust classifiers is a critical question. Establishing connections between generalization and robustness is an important problem. 
- The paper is well written, and the authors made an effort to make the results accessible to a broad audience of experts. 

## Weaknesses: 

- This paper does not provide any experiments to test the gap between their theory and the practice. Since showing non-vacuous standard generalization bounds for NNs is not fully solved, it seems too much to expect it is the more challenging setting of adversarial test risk. However, I think the author could still propose some experimental exploration in the same vein as what they mention in the discussion. (more width helps, influence of the perturbation radius,...)  

clarity,_quality,_novelty_and_reproducibility: Clarity: This paper is great 

Quality and novelty: To the extent of my knowledge, the results seem to be interesting for the ICLR audience.

Reproducibility: there are no experiments (except Fig 1 which corresponds to reproducing an experiment from Rice et al.)

summary_of_the_review: This paper is well written. The presentation of the contributions and the results is clear and the results seem significant (to the extent of my knowledge). It is a clear accept to me.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper contains two parts. The first part discusses properties of optimal adversarial estimators w.r.t. convex loss and 0-1 loss, including their connection. The second part discusses adversarial lazy training of one-layer wide network, and demonstrates a convergence of population adversarial loss.
strength_and_weaknesses: Strength: Overall the paper delivers reasonable theoretical results.
Weakness: results in section 4 are restricted to a relatively simple model; results in section 3 and section 4 are not well integrated, and they feels like two separate topics.

Thm 4.1: I don't understand the role of t. If we let t go to infinite, the definition of W_{<=t} essentially doesn't change. However, one of the terms in upper bound decays to zero.

Col 4.2: The condition says m needs to be bounded (big O notation). But I believe the author(s) means that m needs to be larger than the given rate.

The conditions of Lemma 4.4-4.6 are not mentioned in theorem 4.1.

According to Thm 3.3, to get a good zero-one loss, one can train a model based on convex loss and tune the threshold t value. Does Fig 1 reflect this tuning?
clarity,_quality,_novelty_and_reproducibility: Clarity: the paper delivers well on its core message. But some details need some future clarifications to avoid confusion.
Novelty: I believe the result is new, and generalizes existing results on clean training.
Reproducibility: N.A. 
summary_of_the_review: I currently recommend marginal acceptance.
Although the results are new, but it does depends on limited model setup.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper considers two problems. The first is relating adversarial zero-one loss to convex surrogates. The results in this section are clearly written and easy to follow; they also apply to a broad setting. The second problem is about adversarial lazy training of one-layer wide network. They restrict attention to l_2 loss and characterize the adversarial risk near initialization of training such networks using the logistic loss.


justification_for_why_not_higher_score: The results seem fine, but may be of limited interest.
justification_for_why_not_lower_score: Clearly above the acceptance threshold.
Decision: Accept: poster