Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper describes a connection between flatness of minima and generalization in deep neural networks. The authors define a concept called feature robustness and show that it is related to flatness. This is derived through a straightforward observation that perturbations in feature space can be recast as perturbations of the model in parameter space. This allows the authors to define a flatness measure for minima in deep networks (this flatness measure is also invariant to rescalings of the layers in neural networks with positively homogenous activations). The authors combine their notion of feature robustness with epsilon representativeness of a function to connect flatness to generalization. They present empirical evaluations and comparison to other measures on CIFAR10.
main_review: This paper is able to once again confirm the relationship between flatness and generalization in an empirical manner. The measure presented in this paper shows better correlation to generalization than other measures proposed in the literature. However the authors do not provide the details about which layer was used to divide the model into the $\phi, \psi$ decomposition. The authors also do not specify whether the correlation holds for every possible choice of $\phi$ and $\psi$ to decompose the model. These details will help us understand the flatness phenomenon better.

The key theorem relating generalization and flatness is Theorem 6 (following from equation 5) which decomposes the generalization gap for a function $f$ into the $\epsilon$-representativeness of the feature mapping $\phi (S)$ for the distribution $\mathcal{D}$ and the feature robustness of the full model. The relationship between feature robustness and flatness follows directly from a Taylor expansion of the empirical loss, and the relationship between $\epsilon$-representativeness and generalization follows by definition. Proposition 2 is helpful in showing a relationship between local truncated normal distributions and orthogonal matrices. However, can one show a result of the form - for every local distribution $\lambda_i (\xi_i)$ there exists a distribution on linear perturbations $A$ such that the equivalence between feature perturbations and sampling from the distribution holds in expectation? It seems to me that this is an important step in establishing the link between feature robustness and generalization. Moreover, are there specific functions $\phi$ which make this possible, or does this hold for all feature mappings $\phi$? The synthetic experiments in Figures 3 and 4 are encouraging but are still performed with deep networks. Do the authors expect this to hold for deep linear networks, for instance?

Experiments on synthetic data showing the relationship between the feature robustness and $\epsilon$-representativeness terms would be helpful. What is the contribution of each term to the generalization gap? Is there a tradeoff between them or are more robust feature maps $\phi$ also more representative?
limitations_and_societal_impact: This is a theoretical paper that does not have immediate societal implications. The assumptions required for the analysis are outlined but a clearer discussion of the limitations of the conclusions is needed (this is only an upper bound on generalization, etc.)
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper investigates the connection between loss-based flatness and generalization. The authors relate flatness to interpolation from representative data in the feature space, and use two notions to do that: 1) representativness and 2) feature robustness. They derive a new flatness metric -- a relative flatness -- and on a small set of empirical observations show that it correlates well with generalization and that it has some other desirable theoretical properties such as reparametrization invariance.
main_review: I like the paper, it deals with and important problem, is pretty clearly written, and contains both theory and an empirical validation. Here are some of my detailed points, questions, and potential problems that could be addressed by the authors to make the paper better:

THE POSITIVES:
1) the paper deals with an important question of the relationship between local loss Hessian based flatness and generalization. Flatness is a local property of the loss landscape, while generalization is a much higher level concept. A lot has been written on the connection, but as far as I can tell there hasn't been a satisfactory explanation for why the connection exists. This paper is a good step in that direction.
2) The paper is pretty clearly written and I had an easy time following the argument.
3) I appreciate that the authors ran an empirical validation of their theoretical results using a pretty large network and a non-trivial dataset (CIFAR-10) rather than just synthetic data.
4) I like that the authors discuss the limitations of their approach, such as the assumption of constant labels.

QUESTIONS AND WEAKER POINTS:
1) Constant labels. I am a bit confused about the constant labels assumption. If I get it correctly, the assumption is that when you look at the partitioning of the input / feature space, as discussed from line 90 further, the cells are considered to have the same true label as the centroid of the cell? This seems pretty reasonable on the face of it, but I do wonder if small soft changes in the true label, e.g. from (1,0,0) to (1-e,e/2,e/2) as you move within the cell would do something to your theory? I think it is entirely plausible that the labels could be changing as judged by a human as a reference for the ground truth. Furthermore, how does the reference 35 use the constant labels? I didn't get that connection.

2) The partitioning you are looking at could be e.g. a Voronoi partitioning (a minor point)? Do distances matter. Do shapes of the cells make any difference. Do they have to be convex? ​

3) The verification in section 6 is only done on a single architecture and dataset, yet the validity of the measure is asserted generally. I think it would be better to do a broader set of experiments, including other data modalities and networks, given the breath of your theoretical claim. I am not suggesting you need to go to imagenet directly, but more diversity in architectures and dataset would be good to add.

RELATED PAPERS?
I remember seeing a proof relating the changes in weights to changes in features / logits in https://arxiv.org/abs/2002.03432 which might be relevant to you. Another paper that I got reminded of in your summary of the works on Tr(H) was https://arxiv.org/abs/1807.02581 .

VERY  MINOR STUFF:
1) I think  \mathrm{Tr} for an operator looks better than Tr
2) the colors in Figure 5 are hard to distinguish, could you use more different colors?

UPDATE AFTER REPLY:
I am happy with the detailed response and increase my score from 6 to 7. Thank you!

 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper develops a theoretical approach to tackling the relationship between flatness of the loss landscape around trained models and generalization. To accomplish this, the authors need to make certain assumptions about the data such as locally constant labels as well as its representativeness. The authors show that flatness with respect to the last layer parameters is related to feature robustness, and ultimately show that generalization performance can be bounded by their flatness quantity. The paper then presents a few experiments on synthetic datasets or small models to test the performance of the theory. They find that their measure performs similarly to others such as PacBayes and Trace.
main_review: Unless I misunderstood (which is definitely possible!) the theory only applies to models with a fixed feature embedding and where only the last layer parameters are trainable. If so, this limits the general applicability of the work and my excitement for it. It would be good for the authors to comment one way or another on this, perhaps in a limitations section which is missing. (Or not if I misunderstood.)

What is the measure of correlation shown in Figure 5? Is it rank correlation? More details on the experimental setup would be appreciated.

My interpretation is that their measure works about as well as the other well-performing measures in the plot. Could the authors comment if the improvement should be considered significant?

In the relative flatness and trace measures in Figure 5, it looks like they both have a vertical “clump” of points that behaves very differently from the other points. Do the authors understand the origin of this clump? Is there a particular set of hyper parameters for which the measure does not seem to change? In some sense, this is worse performance to me than say PacBayes, which doesn’t seem to exhibit this.


limitations_and_societal_impact: The authors discussed the limitations with respect to approximating representativeness, but a discussion of other limitations would be good. There is not a societal impacts section but I don’t know if that’s necessary for this paper.
review_title: null

Meta-review: This paper provides a theoretical account of the relation between flatness of minima and generalization in deep neural networks. This is an important problem that attracted recent attention. The results presented here (Theorem 6) provide novel insight and are validated by experiments. The presentation is clear.
Decision: Accept (Poster)