Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a new algorithm for performing adversarially robust training via a dual characterization.
main_review: This paper considers the problem of learning adversarially robust classifiers. The problem is traditionally formulated as that of minimizing the robust loss where on any given point (x,y) the loss is evaluated at (x+delta, y) where delta is a perturbation among a set of allowed perturbations. The loss at (x,y), \ell(x,y) is then the maximum loss in the neighborhood of x, i.e, \ell((x+\delta, y)). The robust loss is intractable in general and in fact even the maximization problem of finding the worst perturbation for a given (x,y) is hard unless the classifiers is a simple model, such as linear classifiers. 

The paper proposes to solve the constrained robust learning problem where the goal is to minimize the robust loss subject to the fact that the standard (non-robust) loss is small as well. This formulation addresses practical concerns where optimizing for the robust loss typically leads to an increase in the standard loss. The authors propose a dual formulation of the problem by providing a dual characterization of the inner maximization problem. In the dual space the inner maximization can be written as optimizing over a set of distributions over perturbations (for a given (x,y)). The main result of the paper is a characterization of the optimal distribution. Based on this the authors propose a sampling approach, where for each (x,y) the perturbation is sampled from an approximation to the optimal perturbation distribution. The approximation essentially samples a perturbation delta with probability proportional to \ell(x+delta, y). The authors present empirical results on CIFAR-10 and MNIST and show that the method proposed is competitive with existing approaches. 

Overall the paper presents a novel take on adversarial robustness. Proposition 3.2 is the key result. It would be interesting to consider better approximations to the optimal distribution than the choice made in the paper (given that the empirical improvements obtained are within 1-2%). 
The paper also presents generalization bounds, but they more of less follow standard techniques. 

limitations_and_societal_impact: Some technical limitations of the work are addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper provided a novel connection between the well-known adversarial training problem and a statistical problem over perturbation distributions. The former requires obtaining worst-case adversarial perturbations of a neural network as an inner optimization procedure, which has been known as a challenging task. The later can avoid this but needs to solve a new inner optimization over perturbation distributions instead. The authors demonstrated that the statistical problem recovered several existing adversarial training problems with sub-optimal perturbation distributions. Inspired by this connection, the paper introduced an alternative adversarial training algorithm that used a smoothed version of the optimal perturbation distribution and showed that the proposed algorithm can achieve competitive or even better performance compared to previous approaches in terms of empirical adversarial robustness (evaluated using empirical attacks) on image classification tasks such as MNIST and CIFAR-10.
main_review: The writing is clear and easy to follow. Even though there are some typos/missing definitions in the main body, I believe they are largely innocuous and do not hinder understanding. 

My main concern of the paper at the current state is its lack of empirical evaluations:

1) *Lack of evaluations on the trade-off between using more Langevin iterations vs. model performance*
The proposed method uses projected Langevin sampler to approximate the optimal distribution of the perturbation.
Having enough number of steps (L) in the sampling step is usually crucial to the quality of the approximation, but can incur a big computation cost at the same time.  
Because of this, I believe it is important to analyze the trade-off between $L$/training time and the performance, and I think the current paper does not do that thoroughly. 
The authors did provide some results to show the difference in performance with different $L$'s. For example, the performance is reported with $L=1$ and $L=100$ for MNIST and $L=10$ for CIFAR-10, but they alone don't tell much about how practical these settings are when scaling up to larger networks without learning about their training time.  

2) *Lack of experimental details*
The experimental section didn't specify the threat model (e.g., under which norm ball the perturbation should be confined in). 
This is an important detail that should be included since the difficulty of robust classification varies greatly among different norms. 
Also, the hyperparameters for the PGD attack evaluations are also missing. 
As the authors also noted that adversarial attacks rely on "heuristics such as random initializations and random starts, ...", providing these details and the tuning procedures for the attacks would be helpful for a more thorough examination of the proposed method's performance.

Aside from these two main issues, the experiment section could also be benefited from a more diverse set of perturbation radius and perturbation shape (e.g., different norms). 

*Some More Detailed Comments*
- Algorithm 1, L8 - What is the difference between $\tilde{l}$ and $l$? Is it a typo?
- Algorithm 1, L5 - I think $g, T$ should be defined somewhere in the main body rather than only in the Appendix. 
- L238 - same as above. I think $\mathcal{H}$ is never defined in the main body. 
- L303 - typo "it is well-know that..." => well-known
- The references are missing for some baselines in the experiment section (e.g., FAB, A-PGD, MART).

Overall, I think it is a really wonderful paper with a novel reformulation of the adversarial learning problem accompanied with an effective practical algorithm. I would recommend acceptance and I think improving the empirical section could greatly further strengthen the paper. 
limitations_and_societal_impact: I think that the paper can be benefited from adding more discussion of the limitations of the proposed algorithm. For example,
- What is the run-time of the proposed algorithm? (e.g., how large does $L$ need to be to be competitive of existing approaches and what is the resulting run-time?)
- The proposition 3.2 assumed that the loss function $(x, y) \mapsto \ell(f_\theta(x), y) \in L^2$. Does this assumption usually hold for the neural networks of interest?
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the adversarial robustness through semi-infinite optimization and non-convex duality theory. By leveraging tools from constrained optimization and duality theory, the authors find the adversarial training formulation is equivalent to learning from a perturbation distribution. The authors propose a constrained learning problem for achieving model robustness while maintaining the nominal performance on clean samples. The authors propose an unconstrained saddle point reformulation for solving the constrained optimization problem via duality, and develop an LMC-based algorithm. Empirically, the authors find the new algorithm can achieve better performance on some standard benchmark tasks.
main_review: Pros:
1. The identified connection between constrained formulation in (P-RO) and the statistical counterpart (in Eq. (5)) is interesting, which provides theoretical insights on the constrained problem as well as the trade-off between robustness and accuracy.

Cons:
1. The results in Proposition 3.6 are meaningless. Since $\zeta_{R}(N)$ is the difference between the expected robust risk and the empirical robust risk (defined in Eq. (9a)). $\zeta_{R}(N)$ is relatively large, which suggests $|P^{\star} - \hat{D}^{\star}|$ is large. More specifically, if $\zeta_{R}(N)$ is small, then the model already achieves robust generalization. However, clear robust overfitting has been observed in the literature. 
2. The empirical results in Section 6 are not convincing to support the claim 'improved results over state-of-the-art benchmarks' mentioned in the abstract. For example, I would suggest the authors apply tools from RobustBench [85] to evaluate the robust accuracy properly (in order to avoid fake robustness). Also, AWP [46] should be included in section 6.2.

Typo:
1. $(x_n, y_n)$ in Line 268, $x_n$ should be bolded. 

Missing reference:
1. Strong duality for non-convex problems, [BLW+2019].

Overall, I think the paper is marginally below the acceptance bar.

[BLW+2019]. Non-Convex Matrix Completion and Related Problems via Strong Duality. Maria-Florina Balcan, Yingyu Liang, David P. Woodruff. Journal of Machine Learning Research, 2019.

limitations_and_societal_impact: N.A.
review_title: null

Meta-review: The paper proposes to solve the constrained robust learning problem via a dual formulation of the problem by where the inner maximization can be written as optimizing over a set of distributions over perturbations (for a given (x,y)). The main result of the paper is a characterization of the optimal distribution. Based on this the authors propose a sampling approach, where for each (x,y) the perturbation is sampled from an approximation to the optimal perturbation distribution. The paper presents a practical algorithm based on the theory that achieves competitive results on benchmark datasets.

The reviewers raised concern about some of the theoretical portions of the paper that follow from standard tools. Given that the empirical results are competitive with algorithms such as TRADES (that are also based on theoretical insights), it was unclear whether the main theoretical result (proposition 3.2) is novel enough for NeurIPS. It was also pointed out by the reviewers that the empirical comparisons where not conducted with respect to proper benchmarks such as RobustBench (this was addressed by the authors in the response via additional experimental results). Overall this is a borderline paper.
Decision: Accept (Poster)