Venue: ICLR 2018 conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper studied the generalization ability of learning algorithms from the robustness viewpoint in a deep learning context. To achieve this goal, the authors extended the notion of the (K, \epsilon)- robustness proposed in Xu and Mannor, 2012 and introduced the ensemble robustness. 

Pros: 

1, The problem studied in this paper is interesting. Both robustness and generalization are important properties of learning algorithms. It is good to see that the authors made some efforts towards this direction.
2, The paper is well shaped and is easy to follow. The analysis conducted in this paper is sound. Numerical experiments are also convincing. 
3, The extended notion "ensemble robustness" is shown to be very useful in studying the generalization properties of several deep learning algorithms. 

Cons:    

1,  The terminology "ensemble" seems odd to me, and seems not to be informative enough.
2,  Given that the stability is considered as a weak notion of robustness, and the fact that the stability of a learning algorithm and its relations to the generalization property have been well studied, in my view, it is quite necessary to mention the relation of the present study with stability arguments. 
3, After Definition 3, the author stated that ensemble robustness is a weak notion of robustness proposed in Xu and Manner, 2012. It is better to present an example here immediately to illustrate. 
review_title: Clear accept

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:
This paper presents an adaptation of the algorithmic robustness of Xu&Mannor'12 to a notion robustness of ensemble of hypothesis allowing the authors to study generalization ability of stochastic learning algorithms for Deep Learning Networks. 
Generalization can be established as long as the sensitiveness of the learning algorithm to adversarial perturbations is bounded.
The paper presents learning bounds and an experimental showing correlation between empirical ensemble robustness and generalization error.

Quality:
Globally correct

Clarity:
Paper clear

Originality:
Limited with respect to the original definition of algorithmic robustness

Significance:
The paper provides a new theoretical analysis for stochastic learning of Deep Networks but the contribution is limited in its present form.


Pros:
-New theoretical study for DL algorithms 
-Focus on adversarial learning
Cons
-I find the contribution a bit limited
-Some aspects have to be precised/more argumented
-Experimental study could have been more complete


Comments:
---------


*About the proposed framework.
The idea of taking a max over instances of partition C_i (Def 3) already appeared in the proof of results of Xu&Mannor, and the originality of the contribution is essentially to add an expectation over the result of the algorithm.


In Xu&Mannor paper, there is a notion of weak robustness that is proved to be necessary and sufficient to generalize. The contribution of the authors would be stronger if they can discuss an equivalent notion in their context.

The partition considered by the framework is never discussed nor taken into account, while this is an important aspect of the analysis. In particular, there is a tradeoff between \epsilon(s) and K:  using a very fine tiling it is always possible to have a very small \epsilon(s) at the price of a very large K (if you think of a covering number, K can be exponential in the size of the tiling and hard to calculate). 
In the context of adversarial examples, this is actually important because it can be very likely that the adversarial example can belong to a partition set different from the set the original example belong to. 
In this context, I am not sure to understand the validity of the framework because we can then compare 2 instances of different set which is outside of the framework. 
So I wonder if the way the adervarial examples are generates should be taken into account for the definition of the partition.
Additionnally, the result is given in the contect of IID data, and with a multinomial distribution according to the partition set - adversarial generation can violate this IID assumption.

In the experimental setup, the partition set is not explained and we have no guarantee to compare instances of the same set. Nothing is said about $r$ and its impact on the results. This is a clear weak aspect of the experimental analysis
In the experimental setup, as far as I understand the setup, I find the term "generalization error" a bit abusive since it is actually the error on the test set. 
Using cross validation or considering multiple training/test sets would be more appropriate.


In the proof of Lemma 2, I am not sure to understand where the term 1/n comes from in the term 2M^2/2 (before "We then bound the term H as follows")


review_title: Paper that provides a novel theoretical framework for stochastic learning of Deep Networks, the proposed framework is an extension of an existing framework and the contribution is a bit limited in its present form.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes a study of the generalization ability of deep learning algorithms using an extension of notion of stability called ensemble robustness. It requires that algorithm is stable on average with respect to randomness of the algorithm. The paper then gives bounds on the generalization error of a randomized algorithm in terms of stability parameter and provides empirical study attempting to connect theory with practice.

While I believe that paper is trying to tackle an important problem and maybe on the right path to find notions that are responsible for generalization in NNs, I believe that contributions in this work are not sufficiently strong for acceptance.

Firstly, it should be noted that the notion of generalization considered in this work is significantly weaker than standard notions of generalization in learning theory since (a) results are not high probability results (b) the bounds are with respect to randomness of both sample and sample (which gives extra slack).

Stabiltiy parameter epsilon_bar(n) is not studied anywhere. How does it scale with sample size n for standard algorithms? How do we know it does not make bounds vacuous?

It is only allude it to that NN learning algorithms may poses ensemble robustness. It is not clear and not shown anywhere that they do. Indeed, simulations demonstrate that this could be the case but this still presents a significant gap between theory and practice (just like any other analysis that paper criticizes in intro).

Minor:

1. After Theorem 2: "... can substantially improve ..." not sure if improvement is substantial since it is still not a high probability bound.

2. In intro, "Thus statistical learning theory ... struggle to explain generalization ...". Note that the work of Zhang et al does not establish that learning theory struggle to explain generalization ability of NNs since results in that paper do not study margin bounds. To this end refer to some recent work Bartlett et al, Cortes et al., Neyshabur et al.

3. Typos in def. 3. missing z in "If s \in C_i...". No bar on epsilon.
review_title: Paper proposes to study generalization ability via new notion of stability. Improtant problem and a beginning of interesting idea but paper is not ready for a publication since results are not sufficiently strong.

Meta-review: The paper proposes a new way to understand why neural networks generalize well. They introduce the concept of ensemble robustness and try to explain DNN generalization based on this concept. The reviewers feel the paper is a bit premature for publication in a top conference although this new way of explaining generalization is quite interesting.
Decision: Invite to Workshop Track