Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the optimization landscape of neural networks. In particular, this paper touches on the question of whether two local minima of the optimization landscape are connected by a “line” of linearly-interpolated neural networks. To probe this question, this paper evaluates the loss gap (so called “barrier”) between two local minima and their linear interpolation. The finding is that this barrier is non-zero. Next, the authors conjecture that if one takes into account permutation invariance of a local minimum, the barrier should be reduced to zero. To support this conjecture, the authors considered a simulated annealing algorithm to search for permutations of the weight matrices, to show that the barrier reduces after applying the simulated annealing algorithm
main_review: ## Strength

- Understanding properties about the optimization landscape of neural networks is a central problem in deep learning. While there has been lots of theoretical studies, they typically apply only to particular styles of data models or rely on particular assumptions on the initialization. This paper instead directly studies properties of the optimization landscape through large-scale experiments. The findings are both interesting and novel.

- The authors have stated a Conjecture that could potentially inspire future studies. This Conjecture is in line with existing results in the literature. A preliminary result in the large-width limit is provided to support the Conjecture.

- The scale of the experiments is on a large range of datasets and models, with over 3,000 runs, giving validity to the supporting arguments.

## Weakness

- Based on Conjecture 1, one would expect the barrier to go to zero, provided with sufficient computation to find the “right” permutation to apply to the weight matrices. Figure 6 goes into supporting this Conjecture, by showing that Simulated Annealing helps reduce the barrier. However, the reduction in the barrier is marginal at best. Thus, I am not entirely convinced by the result of this experiment.
    - Could the authors show a scaling cost as for whether the barrier would continue to decrease, provided more computation? For example, suppose the barrier continues to decrease as the amount of computation increases and does not plateau, then this would suggest that with enough computation, the barrier could eventually go to zero. The current result shown in Figure 6 looks marginally supportive at best.
- Based on the nature of this paper, I think the discussions should be stated more concretely.
    - For example, the authors state “Another area where our analysis is of importance is for ensembles and distributed training.” It’s unclear what this refers to.
    - It’s also unclear when the authors state “whether there is a one-to-one mapping between lottery tickets and permutations. We believe our analysis laid the ground for investigating these important questions…”

**Questions**
- From the paper by Zhang et al. (ICLR’17), we know that neural nets can memorize random labels and regularization methods can help mitigate such memorization (Figure 2a) though not entirely. Would Conjecture 1 still be true if one takes into account the effect of regularization? For example, while the permutation invariance property holds for regularization methods such as weight decay, it does not hold for $\ell_1$ penalty or data augmentation.
- Additionally, it would be interesting to see whether the barrier changes if one starts to inject random labels into the training dataset, similar to Zhang et al.’s experiments.
- I was also curious what the prediction performance of the linearly-interpolated model is. For example, it would be interesting to see a figure similar to Figure 2 but with the y-axis being the prediction accuracy.

**References**
- Understanding Deep Learning Requires Rethinking Generalization. Zhang, Bengio, Hardt, Recht, and Vinyals. ICLR’17.

**Typos**
- Extra space on page 2: “In Section 4”
- Missing white space on page 8: “$\Psi$ to”
summary_of_the_review: This paper presents several interesting and novel ideas regarding the linear mode connectivity of the optimization landscape of neural networks. The findings are supported by extensive experiments. An interesting Conjecture is stated, which could be interesting for future studies. On the other hand, I think the writing of this paper could still be improved.

**Update after rebuttal:** The rebuttal addressed my main concerns mentioned under the Main Review section; thus, I increased my score. I particularly appreciated the empirical strength and the insights of this paper.

On the other hand, I agree with other reviewers that the authors need to clearly state the version of the conjecture that is already proved in prior works.

My other remaining concern is about the loss function used in the proposed conjecture. As in the current form, the conjecture is stated for the minimizers of generic loss landscapes of neural networks. However, it doesn't explicitly clarify whether there are any regularization penalties (e.g., $\ell_2$ or $\ell_1$ loss of weight matrices) in the loss function, which I believe is used in the experiments (e.g., weight decay). I think this aspect needs to be stated more carefully.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors present a bold and thought-provoking conjecture: neural networks trained with SGD converge to the same low-loss basin, up to permutations of their hidden neurons. They go on to provide some limited but intriguing evidence in support of this conjecture. First, they prove that it holds for sufficiently wide one-hidden-layer neural networks at random initialization. Second, they empirically show that the loss barriers between different SGD solutions are similar in magnitude to the loss barriers between different permutations of a single SGD solution, across a range of models, tasks, and hyperparameters (e.g. width, depth). The paper also includes a number of experiments investigating the effects of width, depth, task, and architecture on loss barrier size.
main_review: If true, this conjecture would have significant implications for both our theoretical understanding of neural networks and our use of them in practice (e.g. ensembling). The challenge of course is finding evidence for it, given that optimizing permutations between large neural networks is computationally infeasible. I think the authors take a meaningful first step in showing that a simple simulated annealing algorithm is largely unsuccessful in finding winning permutations. However I wish they had explored this direction a little further - perhaps by using other heuristics to preliminarily sort the neurons (e.g. weight norms or activations on a set of test images), and then further refining the permutation from this starting point.

As a second idea, since the function implemented by a neural network is invariant to permutation of its hidden neurons, if the authors' conjecture is correct then for two SGD solutions NN1 and NN2 there exists a solution NN2' (a permutation of NN2) which implements the same function as NN2 but lies in the same basin as NN1. Rather than finding NN2' by identifying a winning permutation, could NN2' be found by fine-tuning NN1 to implement the same function as NN2? without leaving the low-loss basin?

The authors' approach of comparing the loss barriers between different SGD solutions to the loss barriers between permutations of the same solution is interesting, and the close match is certainly intriguing. But it is only a small step towards demonstrating that their conjecture holds. I was left wondering whether there are other measurable properties of pairs of neural networks (beyond loss barriers) which could provide further evidence for (or against) their claim. For instance, some recent works [1] have shown that ensembling networks which lie in different loss basins yields significantly better performance (diverse predictions etc) than ensembling networks which lie in the same loss basin. Could a property like this be used to distinguish the real-world setting $S$ from the authors' model $S'$?

The paper is well written and clearly organized. Experiments are well-motivated and carefully described. And I think the investigations of width, depth, task and architecture on loss barrier size are independently interesting.


[1] Fort, Stanislav, Huiyi Hu, and Balaji Lakshminarayanan. "Deep ensembles: A loss landscape perspective." arXiv preprint arXiv:1912.02757 (2019).

summary_of_the_review: Overall, I think the conjecture presented by the authors is highly interesting and it is the first time I have seen it in writing. While the authors' empirical and theoretical results fall far short of verifying their conjecture in realistic settings, I think they are sufficient to recommend acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper makes a bold conjecture that all the solutions that SGD reaches on deep feedforward networks are linearly interpolatable if they are permuted correctly, and if the network is wide enough. They conduct fairly extensive experiments that are unable to refute this conjecture, but do not prove it with certainty. They prove a theorem that shows that such a result holds at random initialization for a fully connected 1-hidden layer ReLU.
main_review: Strengths:
- The experiments are fairly extensive covering several network architectures over MNIST, Cifar10, SVHN and Cifar100.
- Though the computational burden of checking such a conjecture exhaustively is intractable, the authors use innovative approximations that might still be describing the real behavior.
- Linear Mode Connectivity is currently of great interest to the community due to the Lottery ticket hypothesis and may hold key insights into the learning dynamics of SGD on overparameterized DNNs.

Concerns/Comments:
-  In Sec 2.2, and for most of the main paper, the authors restrict their attention to training loss barrier as the "barrier to linear interpolation". I understand that this is something that can be computed at train time, but isn't the claim of linear interpolation to do with the "true" landscape of the loss function? If so, I feel understanding the test loss barrier is more interesting. I'm happy to see that it has been discussed in the appendix, but I would like to see a more thorough treatment for it.
- All the plots have a maximum barrier of $1.0$ even though I don't see any normalization in the computation of the barrier function. Is this just an artifact of the specifics of the problem? If there is no normalization, I find it hard to understand what value of barrier is large enough to be considered a refutation of linear interpolation.
- The authors note that VGG and ResNet architectures have a high barrier at all widths. Is there any explanation for why this might hold? Does it imply that SGD somehow has different dynamics on feedforward networks when compared to ResNets? And if so, how does linear mode connectivity now interact with generalization? I understand that these are very hard questions, but I thought I'd ask more out of curiosity than a criticism of the work.
- In footnote 2, it is mentioned that the experiments are conducted over $5$ pairs of solutions and that the barrier is reported at $\alpha=1/2$. Is it ensured anywhere that the solutions in those $5$ pairs are reasonably far away from each other? Reporting the barrier at $\alpha=1/2$ makes sense if the solutions were actually linearly connected, but would be unrepresentative if they were not. Something like a weighted average over the interval might make more sense to be sure of the findings.
- In section 3.1, it is stated that "In the case of permutations, all permutations are equally likely for SGD". Is there a reference for this claim?
- Section 3.3 has a typo "Bellow => Below"
- I am a little unsatisfied with the theoretical result since it has nothing to do with SGD which is the main topic of study. Moreover, the fact that it holds for all $x \in \mathbb{R}^d$ shows that this is more to do with the concentration we get from the random initialization than the network. However, I appreciate that the authors sufficiently state the limitations of this result.
- Sec 3.5 defines the "Our model" approach where the authors consider the set of all permutations as a proxy for the brute force search. While this is creative, I'm a little bit confused as to how to interpret the results. If the barriers were all non-existent up to permutations, then shouldn't the experiments on $S'$ show a lower barrier than the other experiments? I was under the impression that experiments in Figures 2 and 3 do not involve permutations.
- The footnote 3 in Section 4 seems to be missing.
summary_of_the_review: I think the paper is a fairly thorough empirical evaluation and makes some valuable findings. However, I find it lacking for (what even the authors consider) a "bold" conjecture. I am a little confused as to the exact message of some of the experiments, and therefore am on the fence when it comes to recommending acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors empirically study the linear mode connectivity property for four model types, their scalings, and four datasets. Their main contribution is a conjecture: 'all solutions can be linearly connected by permuting the hidden neurons of one of the solutions.'
main_review: The paper makes a rigorous empirical study of their main claim across several datasets and many architectures. The barrier predictions of their model using SA are convincing. 

One concern remains on the novelty of the conjecture. How do the authors compare their conjecture to the Theorem 4.2 of Simsek et. al., 2021 (https://arxiv.org/pdf/2105.12221.pdf)? It looks like this theorem has already proven the conjecture for two-layers networks for a special activation function and in an infinite data regime. 
summary_of_the_review: The authors study the effect of width, depth, skip connections on the barriers (via lines, i.e., LMC) after having rotating one of the solutions with a suitable permutation.
review_title: null

Meta-review: This paper investigates the linear mode connectivity of the loss landscape of neural networks, i.e. whether a convex combination of two parameters of local optima on the SGD paths has low loss values (i.e. low barrier) up to some permutations. To probe this question, this paper empirically studies the loss gap, named as “barrier”, between two local minima and their convex combinations or linear interpolation. Before permutations, such barriers are typically non-zero; yet, after taking into account of permutation invariance of models, such barriers could be reduced along to zero with the width increasing, a main conjecture formulated in the paper. To support this conjecture, the authors proposed a simulated annealing algorithm to search for such permutations, demonstrating that the barrier reduces after such permutations.

The reviewers unanimously accept the paper, if the authors make the proposed improvement in the final version. In particular, a reader points out a paper by Singh and Jaggi, 'Model Fusion via Optimal Transport', NeurIPS 2020, that supports the same conjecture with a constructive algorithm to find optimal permutations or matching using optimal transport. This should be included in the final version as the authors replied.
Decision: Accept (Poster)