Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper derives finite-sample generalization bounds for robust optimization and Wasserstein distributionally robust optimization. The authors consider a broad class of piecewise Hölder smooth loss functions, under both stochastic setting—i.i.d. or weakly dependent data—and adversarial environment, assuming that the underlying data-generating distribution satisfies transportation-information inequalities. The proofs are built on a general connection between robustness and variation regularization (including Lipschitz and gradient regularization, among others) and new local Rademacher complexity results for variation regularization. 
main_review: 1. Besides the  Wasserstein distributionally robust optimization (WO) problem，this paper considers the robust optimization (RO) problem and establishes new general bounds. Specifically, in the stochastic setting, under proper choice of the radius $\varrho_n$, this paper derive finite-sample guarantees for (RO) and (WO) that apply to non-i.i.d. data and non-smooth losses. For non-i.i.d. data, this paper exploits different notions of transport inequality and Rademacher complexity than the i.i.d. case. In the adversarial setting, generalization bounds for (Adv) with fixed small radius $\varrho_n$ are derived.

2. The analysis of this paper is based on the connection between robustness and regularization. The proposed results improve the sandwich bounds in Gao et al. (2017) for $p = 1$, and generalizes the results therein to piecewise Hölder smooth loss functions for $p\in (1,\infty].

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper aims to theoretically analyze (and compare) a number of different robust learning paradigms. In particular, it has been shown that three different notions of robustness, namely 1) robust optimization 2) Wasserstein distributionally robust optimization, and 3) variation regularization, would result in close loss functions (based on some non-asymptotic bounds) whenever the strength of attacks becomes infinitesimally small. While connections between such methods have been conjectured (or even analyzed) in some recent works, I still found the results in this paper interesting.

Also, author(s) have tried to achieve non-asymptotic generalization bounds for cases where data samples are weakly-dependent (instead of i.i.d. generated) and/or the space of loss functions are only piece-wise smooth. I have not checked the proofs for this part, and results have not been clearly discussed nor compared with existing ones.

Overall, a well-motivated paper which tries to add a number of nice contributions to the area. However, paper suffers from lack of clarifications and intuitive discussions in order to shed light on the technical significance of its many theorems. Also, some notations in parts of the paper (including theorem 2) are not properly framed. Another problem with this work is that author(s) might have missed many existing works that have already tried to analyze the same (or at least slightly different) problem sets. As a result, paper is not well-positioned w.r.t. the literature and cannot be easily compared with other researches.

I cannot recommend the paper for acceptance in its current shape, thus my vote at this stage is weak reject.

main_review: Strengths:

Paper is well-motivated. The fact that data samples can be generated in a weakly-dependent manner instead of the common i.i.d. assumption is nice. Also, considering piece-wise smooth functions instead of globally smooth ones is interesting for many applications. Moreover, author(s) have put so much effort to write the paper in a mathematically comprehensive way. This has (unfortunately) reduced the readability of the paper, but has made it technically rigor (except for a few parts, described below). By the way, I have not checked all the proofs.

----------------------------------------------------------------------------------------------------------------

Weaknesses: There are several issues with the manuscript

1) Paper is well-organized, but when someone goes into details it is not written in an informative way. In many cases, several layers of nested definitions have been made with few to no intuition for the reader. Understanding the statement of main theorems requires one to go through all these cryptic definitions with so many parameters and variables. This problem has reduced the clarity of results and has made the paper hard to read. A total of 8 assumptions have been made throughout the main manuscript (haven't completely checked the supplements), almost all mathematically encrypted. And authors have not provided enough discussion on why making such assumptions could be plausible in real-world. One reason for all the above-mentioned issues might be due to the fact that author(s) have tried to fit so much content in a page-limited manuscript. Therefore, I kindly suggest to the author(s) to consider sending the paper to a journal instead of a conference.


2) Paper is not well-positioned w.r.t. many recent works which have also addressed the generalization aspects of adversarial robustness in a distributionally robust setting. For example, Sinha et al. (2017), Carmon et al. (2019), Najafi et al. (2019), and several other works have recently proposed generalization guarantees for DRL (a.k.a. DRO) where generalization gap is $O\left(n^{-1/2}\right)$, similar to Theorem 6 of the current work. What has been improved in this work compared to existing results? This question is either left unanswered in this work, or the significance of the current results is buried under tones of cryptic and non-intuitive definitions and statements. In the latter case, author(s) should point out to the potential improvements and/or fundamental differences.


3) There are some technical ambiguities that need to be addressed: 
-Theorem 1 is interesting. However, author(s) have not compared it well enough w.r.t. to existing works in the literature. The fact that distributionally robust learning has connections to some types of smoothness regularization over the hypothesis space is already known to the community (For example, check the keyword "distributional smoothing"). What is the main advancement in this particular theorem? For example, how is it different from Gao et al. (2017), also cited by the author(s), since I noted a rather similar result in Lemma 1 of that work.


-Paper seems to be rushed in some parts. For example, Theorem 2 is supposed to be one of the main contributions, still its statement is not correctly framed: What is parameter $t$? Does having $\varrho_n\rightarrow 0$ when $n\rightarrow\infty$ suffice? does the rate of convergence toward zero matter? I assume they all affect the integer $N$, however, such issues need to be clarified. Otherwise, author(s) cannot claim the bound in this theorem is "non-asymptotic" since $N$ can become uncontrollably large.

---------------------------------------------------------------------------
Minor comments: 

-(Line 67): the word "generalization" is repeated.
-(Line 118): This line doesn't make sense, unless one assumes $\inf_{y\in\mathcal{D}_f}\left\Vert x-y\right\Vert$ instead of what has been written. Also, a full stop is missing.
limitations_and_societal_impact: No problem here.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper studies the generalization performance of minimizing Distributionally robust optimization (DRO) losses. In particular, it uses existing results that connect DRO to penalty (or regularization) based objectives and employs learning theoretic results to achieve concentration inequalities which ultimately manifest as a DRO generalization bound.
main_review: This submisison studies the generalization properties of DRO with quite interesting results by essentially merging different paradigms of proof techniques which appear nice conceptually. I believe the problem laid out is important however it is not clear to me how the offered bounds precisely resolves and adds anything actionable to the area of using DRO. Furthermore, this bleeds into my main concern which is that the results are highly inaccessible in their current form and difficult to understand their ramifications. I would prefer if the authors can clearly specify some benefits of their methods or existing work their methods provide validation for (specific methods as opposed to simply stating stochastic settings). 

The correctness of the paper is of high standard as I have not found any mistake in the proofs after checking them and I find that all notation is self-contained which the authors should be applauded for given the dense machinery they have employed.

With regards to related work, they have focused on discussing work that relates to their proof techniques while briefly touching upon the adversarial training set-up. It seems they are missing quite a key reference since they have an entire paragraph of their related work discussing previous work on the link between robustness (DRO) and regularization yet a quick search with the words "distributional robustness and regularization" yields a NeurIPS2020 paper [1] which they don't seem to discuss. Other papers along this line can also be found for other cases which may be relevant such as https://www.jmlr.org/papers/volume10/xu09b/xu09b.pdf. Can the authors comment as to how the results in these papers relate to this or why it is irrelevant? 

The applications they have are quite underwhelming since their motivation for a theoretical study is to better understand adversarial training (which often occurs in deep learning) yet their applications do not include a specific study on this - I would be interested to know any comments on this.

My other main concern is that the bounds contain several Rademacher complexities, some of which are highly inaccessible or difficult to grasp - my understanding is that Rademacher complexities are typically large and only for specific settings can be explicitly computed. For the case of neural networks, even a 2-layer neural network, do you have any comments on how the generalization bounds would look like? I'm especially interested to see the shape of Theorem 7.

Overall, while studying the generalization properties is important, I think the core theorems of the paper are quite simple combinations of existing DRO results and concentration inequalities which at the moment are unclear of their practical use for the motivated setting of adversarial robustness in deep learning. The specific analysis contains some more technical results however they are not motivated for the same problem and therefore fall short of a cohesive story. I will currently rate this as a reject however I am interested to see if the authors have any derivation for the deep learning setting or perhaps something more actionable for specific methods as opposed to explaining 'superior performance' of an entire paradigm they refer to as 'robust learning' - the ambiguity here is dangerous since there are many variants of robust learning which clearly have differing performances, not many of which the results at this stage comment on.

[1] Husain, H. (2020). Distributional Robustness with IPMs and links to Regularization and GANs arXiv preprint arXiv:2006.04349
limitations_and_societal_impact: Yes they have.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the finite-sample generalization bounds for robust optimization and Wasserstein distributionally robust optimization. The results are more general than existing literature as they extend to piecewise Holder smooth loss functions. Besides the major contribution, the authors also provide application of the theorems in several examples, e.g. expected shortfall in Section 6.4 and adversarial training in Section 6.5. These examples show the usefulness of the main theorems.
main_review: Originality: this paper has a clear literature review and compares the main results with the existing literature. The results in this paper are solid and novel.

Significance: this paper provides a lot of examples in various scenarios. These examples illustrate the significance of this paper to some extent. In addition, based on my knowledge, there is no existing literature that clearly studies the connection between distributional robustness and adversarial training. Improving the bounds is a contribution to this area, and utilizing it to other areas also brings more potentials.

Clarity and quality: this paper is well organized with clear illustrations. There is no experimental results, but numerical results are not essential for this paper.
limitations_and_societal_impact: No social impact.
review_title: null

Meta-review: Overall, the paper contains interesting technical contributions on generalization bounds for DRO problems. However, the technical exposition makes it difficult to access the results in the paper and has left much to be desired. In particular, the motivations and technical development need to be substantially improved.
Decision: Accept (Poster)