Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: ### POST-REBUTTAL ###
I would like to thank the authors for their reply. I am pretty satisfied with the justification for setting $c(k,d)=1$. The comparison between the different related works also looks great. I am not raising my score further to Accept as I still see the presence of the Lipschitz constant in the bound as a weakness but this is common to many works and hopefully its estimation will see some advances in the nearest future. 
### POST-REBUTTAL ###

This paper presents margin-based generalization bounds for deep neural networks based on the k-variance. This latter is a new way of measuring the variance in the observed data (or the probability distribution generating it) based on optimal transportation (OT) theory and the Wasserstein distance related to it. The obtained generalization bounds are claimed to have several important advantages as k-variance: 1) can be computed from the available data contrary to other complexity measures such as the popular Rademacher complexity; 2) portrays more truthfully the underlying generalization capacity of the considered model. In addition to k-variance, the obtained bound also relies on the Lipschitz constant of the margin function with respect to (wrt) the encoder and the desired threshold on the margin used to define the empirical risk. Experimental results on large-scale datasets suggest the usefulness of the introduced complexity measure in capturing the generalization of deep neural networks. 
main_review: **Originality**

This works tackles an important problem in machine learning which is to find complexity measures that reflect generalisation capacities of deep neural networks. As mentioned by the authors, some existing complexity measures have a solid theory behind them but fail in the situations of practical interest, while others work well in practice without any formal justification. The author’s attempt to provide a generalisation bound with a practically useful complexity term based on k-variance seems to be novel as, to the best of my knowledge, k-variance has never been used in generalisation bounds. Also, it indeed addresses several drawbacks of existing complexity measures. 

**Quality**

Overall, the paper appears to be technically sound even though some parts of it need a more thorough discussion. Below, I formulate a couple of concerns that I had while reading the paper:

1. p.3. l.94: Assuming $c(k,d) = 1$ is an important deviation from the original work of Solomon et al. but the implications of it are not discussed in the paper. Indeed, Solomon et al. say in their work that this factor is “the ambient scaling rate chosen to account for the rate at which the expectation approaches zero”. If the authors consider the case where $d>2$ (I believe that this is the case of interest when considering neural nets), it implies $c(k,d) = k^{\frac{2}{d}} = 1$. What does it mean in the context of this work? My guess is that for reasonable values of $k$, one expects large values of $d$ to compensate for the lack of scaling here but I am not totally sure about it and would like the authors to discuss it. 
2. Given Lemma 3.1 in [4] and Eq. (3), why not using the former to derive Theorem 2 simply as its corollary by applying Eq. (3) to bound the Rademacher complexity? 
3. Solomon et al. derive several properties of k-variance that are used in Section 6 and appear to be useful in the considered context. However, some other more “puzzling” properties of k-variance are not mentioned in this work. For instance, there are distributions with d<=5 for which the variance estimate diverges ([49], Example 6.4) and thus cannot potentially be used as a valid complexity measure. I would suggest including this remark as an assumption to this work. 

**Clarity**

The paper is clearly written and is rather easy to follow. The experimental section is a little be compressed but that is to be expected given the existing page limit. Some minor remarks are:

1. Section 2 can benefit a lot from presenting some generalisation bounds explicitly or at least by presenting a summary table showing other complexity measures used to derive margin-based generalisation bounds for neural nets. At the the very least, the work of [4] deserves to be presented with more details as it relies on Rademacher complexity to which the authors compare k-variance throughout the text. Also, the complexity terms from the two works can be compared as well as both have the ratio of Lipschitz constants/margin threshold terms in them. 
2. p.4 l.141: how do we know that label corruption is handled by k-variance solely from the shape of the generalisation bound? Maybe at this point it is worth referring to experimental results directly.
3. In the experimental results, the authors use the lower bound on the Lipschitz constant to evaluate the considered complexity measure or set it to 1. In both cases, I think that one cannot really rely on the obtained values as they necessarily carry some bias (as mentioned in Appendix C.1) if the tightness of the approximation is not taken into account. This raises the question of whether the obtained theoretical results are really evaluated in the experimental study or whether they are very rough approximation of the latter. At the very least, the fact of evaluating Lipschitz constant may not be considered as an advantage when compared to [24] (p.9 l.224-225).

**Significance**

Unfortunately, I have several doubts regarding the significance of the obtained results after this initial round of review. K-variance is definitely an interesting measure of complexity to consider to assess the generalisation of neural nets, but its experimental evaluation and its introduction into the bounds raises several question to which I would like to hear the authors’ answers before revisiting my opinion. I am highly inclined to reconsider the given score if the authors manage to reply in a convincing manner to my remarks.
limitations_and_societal_impact: Regretfully, the authors only partially discuss the limitations of their work in the main paper and postpone the discussion regarding the Lipschitz constant to Appendix.  I think that discussion the drawbacks of the k-variance and the quality of approximation for the proposed complexity measure should appear in the main part of the paper.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes margin-based generalization bounds based on the k-variance, a generalization of the variance based on ideas from optimal transport. The k-variance, like the Rademacher complexity, is a data-dependent term, and captures certain properties of the data such as concentration and separation of features. Unlike the Rademacher complexity, the k-variance is easily empirically estimated. 

The authors proceed to empirically evaluate how well their bounds can predict generalization, using the framework of recent work in the literature, namely the PGDL competition. The authors show competitive empirical results on these tasks. Although there are existing generalization measures which perform as well or better, this work is notable as it's bounds are theoretically supported. 
main_review: This work addresses an important problem: finding theoretically motivated generalization bounds which actually reflect empirical observations in the literature. As the authors note in their review of related work, the current state of affairs for this problem is (1) many theoretically supported bounds do not reflect empirical generalization trends for deep models (2) the best empirical bounds (e.g. the Mixup*DBI winning solution of PGDL 2020) are heuristic in nature and are not grounded in theory. 

Theoretically grounded measures which have some empirical are of clear interest to the community: the theory provides insight into the provide to the extent it fits empirical observations. 

The paper is clearly written, albeit quite dense with technical details. I would like to see a fuller conclusion section discussing the limitations of the work, e.g. what gaps remains between theory and practice, and avenues for future work.
limitations_and_societal_impact: I did not find significant discussion of this limitations of this work. Although this paper makes a contribution towards closing the gap between theory and practice, the gap is nevertheless not closed. I would like to see more discussion of how much more work there is left to do in this area.


I found the discussion of potential negative societal impacts of this work in the appendix adequate.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper develops generalization bounds based on class margins and the optimal transport cost (in Wasserstein-1 distance) between two independent random subsets sampled from the training distribution. The authors argue that the optimal transport cost term explains the correlation between clustered representations and good generalization. Empirically, they show that mixup+OT cost improves over mixup+DBI in predicting generalization error.
main_review: Explaining generalization in deep learning is an important problem. This paper nicely combined theory with empirical progress. 

However, there are a number of weaknesses:
1. The main bound seems to be a minor variation of the standard margin-based Rademacher complexity bound; the technique isn't very novel.
2. There is no justification for why Wasserstein 1 distance should be preferred over Wasserstein 2 distance, TV, or DBI for measuring intraclass clustering, other than that it is easy to prove a generalization bound for Wasserstein 1 as a variation of the Rademacher bound. It is possible that similar bounds can be shown for other metrics as well.
3. Can the authors comment on why OT distance needs to be combined with mixup accuracy for SOTA prediction of generalization performance?
4. Why not turn this OT cost into a regularization term in training? Will models have better generalization with this regularization?
5. In table 1, why does kV work better than 1st layer, but kV-GN works better with 8th layer?
6. Although some ablations are performed (in appendix), the results are not discussed. What are the conclusions?
7. Why is Mixup + kV-GN-Margin in Table 2, column 1 smaller than kV-GN-Margin-8th in Table 1, column 1?


Minor:
1. Line 562 in appendix: Missing citation

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Firstly, the authors proposed new margin bounds based on k-variance which
can better capture the structural properties of the data distribution than other
margin based bounds. Secondly, they further developed a variant called gradient
normalized margin bounds which perform well empirically on the large scale
PGDL challenge data. Moreover, they informally showed the k-variance bounds'
ability to capture the low-dimensional structure of data distribution. Last but
not least, they showed that maximizing the margin will give rise to the feature
separation. The main contribution of the paper is to introduce the idea of
k-variance generalization bounds.
main_review: Overall, I think it is a good paper. The authors introduced the idea of k-variance
(Solomon et al. 2020) to margin based generalization bounds, which is original
and meaningful. But technically, it is not a hard paper. Most of the theory seem
simple corollaries of some existing ones, for example, proposition 8 and 9 can
be easily derived from Solomon et al. 2020. Furthermore, more interpretation
of the k-variance bound is desirable.
 potentially major comment:
- Proposition 8 needs formal denition for the low dimensional structure of the
measure.
- Optimal transport is a much bigger topic than Wasserstein distance. The
authors are using the Wasserstein distance generalization bounds, so I suggest
change the title to  "Measuring Generalization with k-variance".
minor comments:
- line 640, n_k instead of m_k"
- line 681 and so forth, \mathcal{N}_{\epsilon^{\prime}}
limitations_and_societal_impact: There are no obvious limitations or potential negative societal impact of their
work.
review_title: null

Meta-review: The paper proposes a novel generalization bound that is both theoretically grounded and works in practice. This is an important achievement that has been acknowledged by all reviewers. The least convinced reviewer appreciated your answers and the consensus during the discussion was for accepting the paper. Still the discussion with the reviewer about the constant c(k,d) is important and should be added in the final version of the paper.
Decision: Accept (Spotlight)