Entezari et al. (2021) — ARXIV-2110.06296
Key takeaways
States the conjecture (§1; formalized as Conjecture 1, §3.2) that “if invariances are taken into account, there will likely be no barrier on the linear interpolation of SGD solutions”. The authors call it “bold”. The support is a proof in a very limited setting plus indirect empirical evidence. The paper does not find permutations that remove the barrier between deep networks. It names the implications for ensembling and distributed training (§1, §5) but does not test them.
- Theorem 3.1 (the only theorem). Take a fully-connected network with one hidden layer of h ReLU units, f(x) = v⊤σ(Ux). Sample U, U′ uniformly from [−1/√d, 1/√d] and v, v′ from [−1/√h, 1/√h], i.e. the networks are at random initialization, not trained. Fix an input x with ‖x‖₂ = √d. Then with probability 1 − δ there is a permutation of the second network such that the interpolated network’s output at x differs from the interpolation of the two outputs by Õ(h^{−1/(2d+4)}). Holds when: one hidden layer, random initialization, a single fixed input. The bound is on network output, not on loss, and the paper’s gloss calls it “no barrier at random initialization” (§3.3). There is no condition on dead neurons. The rate weakens as input dimension d grows.
- Empirical — barriers without alignment. Barriers grow quickly with depth (Figure 3). For MLPs and Shallow CNNs they first rise and then fall with width, which the paper likens to double descent. For VGG and ResNet they saturate at a high value and do not change with width (§2.2, Figure 2). Holds when: MLP, Shallow CNN, VGG and ResNet on MNIST, SVHN, CIFAR-10 and CIFAR-100 (ImageNet in Figure 4 only). Training-loss barrier, measured at α = ½.
- Empirical — “our model vs real world” (§3.5, §4.1). Barriers between independently trained networks closely match barriers between random permutations of one network, before and after search (Figures 5, 7). This is the paper’s main evidence for the conjecture. It is indirect: a set of permuted copies satisfies the conjecture by construction, and the paper shows the real set behaves like it. Git Re-Basin, LIT-333, argues in its Appendix A.2 that this is also consistent with barriers between all solutions.
- Empirical — permutation search. Simulated annealing over n = 5 networks did not reduce pairwise barriers significantly (Figure 6, left). Reduced to two networks, it lowered barriers for MLPs and Shallow CNNs on MNIST and SVHN. It reached zero barrier for MNIST MLPs at depth 1, and at depths 2 and 4 at width 2^10 (Figures 6–7). It gave no significant improvement as depth grew. For VGG and ResNet, the search found no permutation that reduced the barrier (§4, Appendix E.2). Holds when: SA with the train error of the averaged model as objective. Appendix B finds a greedy functional-difference matching does better than SA.
What the evidence does not cover
- The theorem covers one hidden layer at random initialization, with output difference at a single fixed input. It says nothing about trained networks, depth, or loss barriers over a dataset. The paper hopes an NTK extension is possible and leaves it to future work.
- No permutation that removes the barrier was found for deep networks (VGG, ResNet). The paper names search strength as “the biggest limiting factor”. It also says a failed search cannot separate a weak search from no such permutation existing (§3.4).
- Image classification only. The paper names language tasks as future work.
Standing in the anthology
Read — the reading is NOTE-131. Arrived in the imported batch, which brought in the permutation-symmetry line, which is why two independently trained networks cannot simply be averaged.