Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: 1. The authors prove a mild condition for mode connectivity for deep nets. The proof is a natural generalization of (Kuditipudi et al., 2019) and the condition required in this paper is provably weaker than the dropout stability. The authors also demonstrate in experiments that their condition can still hold when dropout stability fails.

2. The author provides a nice conceptual connection between their results and the memorization capacity of neural nets. In detail, they show if the product of widths of the last two layers is $\Omega(N)$, then solutions are connected via a low-loss path with minimal assumptions.
main_review: This paper made a nice observation that the proof technique in (Kuditipudi et al., 2019) could be generalized in the following sense: for a fixed subset of the neurons per layer, to find a low-loss path, one doesn't have to rescale the original weights. Instead, it's possible to optimize weights in all further layers, thus further reducing the loss. Despite the simplicity of the idea, this new construction actually gives paths of much lower cost, as demonstrated in Figure 2 and 3.

This paper is clearly written and I enjoyed reading this paper. The setting of the experiments is clearly stated and I checked the proof of the main theorem and it sounds correct to me. The topic of mode-connectivity in deep learning is closely related to the interest of Neurips community. As the authors remarked, the mystery of mode-connectivity is still unsolved because we don't know why SGD find networks satisfying the assumption or if this is in general true for deep nets. However, I think this paper makes a solid step towards understanding mode-connectivity. Thus I suggest accepting this paper.

Other comments:
I really appreciate the authors' effort in making Figure 1, which helps readers to understand the notation of subnetwork used in this paper. Similarly, I think the paper will benefit from making several graphical demonstrations for the proof sketch, e.g., the operations you take to move from the right to the right subfigure in Figure 1.
limitations_and_societal_impact: Yes, in Sec 7.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces an upgrade of the existing research on the existence of low-loss paths connecting minima (or random points) on the loss surface of a neural network. The main idea is to bound the loss of the points along the path by the loss of the sparse subnetworks of the original network. The technique is demonstrated to be more widely applicable as compared to the existing dropout-stability technique. Moreover, the connection to memorization ability is shown with smaller requirements to the width of the layers, which is also demonstrated in the experiments (by the price of considering only SGD solutions and not the full parameter space). The theory gives an insight on the trade-off between quality of features and overparametrization of the layers.
The empirical evaluation demonstrates that the proposed approach can find connection path on each level and with significantly better approximation than the dropout stability technique. Also it requires less overparametrization for precise estimations.
main_review: The paper is clearly written and provides the proofs for all the presented results. Empirical evaluation demonstrates the validity of the proposed technique also showing the advantages compared to the current state-of-the-art.

Some minor points can improve the understanding of the interesting details:
- Clearer discussion on memorization, including the notion of memorization used and how it is connecting to the low-loss-paths
- Clearer discussion on why only SGD solutions should be considered in the theory and what are the possible problems with it (will the parameter configurations built for the low-loss-path always an SGD solution for example?)

Possibly there is a typo in eq.4 (second max in RHS)

Overall, the theory is clear and well explained, the empirical results are good, so my suggestion would be to accept the paper for the conference.

---
I am satisfied with the rebuttal discussion and not changing my score.
limitations_and_societal_impact: The authors included a detailed discussion of limitations, all of which seem to be viable.

As a theoretical paper it does not have any direct societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a theoretical explanation to the mode connectivity phenomena observed in neural networks. Specifically, it is shown that any two points in parameter space may be connected by a piece-wise linear path of low loss.  Technically this is done by assuming that there exists a tradeoff between feature quality and over parameterization at every layer. The authors note that this tradeoff assumption is milder than the dropout stability assumption made in previous work. Given this assumption, the authors improve upon the conditions for the existence of level set connectivity by requiring that the last two hidden layers only contain O(\sqrt{N}) neurons, instead of O(N).
main_review: I am mainly concerned with the actual significance of the results, and with the writing/presentation in general. 
As with the results themselves, i am a bit unsure as to how significant the results really are, given the strong assumption on the quality/over parameterization tradeoff. Concretely, Theorem 4.1 is proven by constructing sub networks connecting a set of neurons from each layer, to the output. The bound in Theorem 4.1 therefore depends on the error that these subnetworks can achieve (Eq 8), which crucially depend on the quality of the set of features chosen. It is not clear to me how significant this bound is given this assumption. (this is also true for the dropout stability assumption in prior work).   It appears to me that the main novelty of the paper is by formalizing a stronger assumption (which is eq 8 needs to be small) than dropout stability (the validity of both is not clear), and using it to get stronger results. 

In addition, i find it hard to judge the impact of this paper due to the lack of discussion on why the subject matter is of any relevance. Besides it being intellectually intriguing to some, what is the significance of the findings in this paper, practically or otherwise?  To be clear, i feel this is more of a presentation issue than anything, and could be cleared out by the authors with some additional discussion.

Some additional comments:

- The authors mention that "This improvement comes at the cost of ensuring a weaker guarantee (connectivity of SGD solutions, as opposed to connectivity of all sublevel sets)". Can the authors expand on this further, how are the results in the paper specifically relevant for solutions found by SGD? Is the intention that the connecting path is found by SGD? This is not clear from the draft.

- While i appreciate figure 1 and the Proof techniques section, i feel that the readability of the proof of Theorem 4.1 could and should be improved. This is especially true since it is part of the main draft. For instance, i find it hard to parse the sentence ". Now, set the
incoming weights of the neurons ....  to the corresponding values given by...." right before Eq 13. This could be made much clearer by some additional figures similar to fig 1.

----------Post Rebuttal

The authors have addressed my concerns to an adequate degree, hence i have updated my score accordingly and recommend acceptance. 

limitations_and_societal_impact: They are addressed
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the connectivity of two parameters such as two SGD solutions of the deep neural networks. The general result subsumes several conditions including dropout stability, memorization capacity, and linear separable features. In particular, the theory shows that the connectivity occurs when the last two layers have $\Omega(\sqrt{N})$ neuron. The theory is validated by numerical experiments. 
main_review: Overall, I think the main message is interesting, and the presentation is clear. Since the main contribution claimed in this paper is on the milder overparametrization, the assumption (A1-b) on the feature quality deems further justifications. This assumption possibly implicitly put stringent requirements on the level of overparametrization of previous layers. The discussion might also help understand the difference between deep nets and two-layer nets where $\Omega(N)$ neurons are necessary. 
limitations_and_societal_impact: The limitations are discussed in the paper. The potential negative societal impacts are not available, as this paper focuses on the mathematical theory for the solutions of deep networks.
review_title: null

Meta-review: The primary contribution of this work is in proving results similar to existing ones (connectedness of solutions in neural network training landscapes), but under milder assumptions.  Reviewers generally agreed that while the work is incremental by nature, it is technically sound and of interest to the community.  The AC sides with this view and recommends acceptance.
Decision: Accept (Poster)