Source-linked AI summary
The Role of Permutation Invariance in Linear Mode Connectivity of Neural Networks
Rahim Entezari, Hanie Sedghi, Olga Saukh, Behnam Neyshabur
TL;DR
The paper addresses whether permutation invariance explains barriers between SGD solutions under linear interpolation. It formalizes and investigates this conjecture theoretically and empirically, finding that extensive attempts fall short of refuting it while identifying computational and task-scope limitations.
Problem
The paper asks whether apparent loss barriers between SGD solutions are artifacts of ignoring permutation invariance, a question relevant to understanding reachable loss landscapes.
Method
The authors combine a theoretical analysis with extensive experiments using randomly permuted versions of a fixed SGD solution as a proxy for solutions obtained from different seeds.
Results
Extensive empirical attempts fall short of refuting the conjecture, and a theorem establishes no barrier after permutation for sufficiently wide one-hidden-layer fully connected networks at random initialization.
Takeaways & Limitations
The conjecture suggests that permutation-aware loss landscapes may place different solutions in essentially the same basin, with implications for lottery tickets, ensembling, and distributed optimization.
Takeaways & Limitations
The search space is prohibitive for deep models, and the analysis focuses on image recognition rather than natural-language tasks.
Abstract
from arXiv · showhide
In this paper, we conjecture that if the permutation invariance of neural networks is taken into account, SGD solutions will likely have no barrier in the linear interpolation between them. Although it is a bold conjecture, we show how extensive empirical attempts fall short of refuting it. We further provide a preliminary theoretical result to support our conjecture. Our conjecture has implications for lottery ticket hypothesis, distributed training, and ensemble methods.
1 Introduction
The paper argues that permutation invariance may explain apparent barriers between SGD solutions and investigates this conjecture through theory and extensive empirical evidence. It frames the question as relevant to linear mode connectivity, lottery tickets, distributed training, and ensembles.
- Permutation symmetry contributes to multiple parameterizations of the same function and produces counter-intuitive loss-landscape geometry.
- The conjecture is connected to lottery ticket behavior, SGD stability, ensemble methods, and weight averaging for distributed optimization.
- The study examines linear mode connectivity across different initializations and varies width, depth, task difficulty, and architecture family.
- The paper conjectures that accounting for permutation invariance will likely remove barriers on linear interpolations between SGD solutions.
- The authors investigate the conjecture theoretically and show that it holds for a wide enough one-hidden-layer fully connected network at random initialization.
- Because direct permutation search is computationally difficult, the empirical study compares randomly permuted versions of one fixed SGD solution with real-world SGD solutions from different seeds.
2 Loss Barriers
This section defines linear loss barriers and studies how architecture, width, depth, and task difficulty affect them. Barriers generally decrease at large widths but increase substantially with depth, with patterns varying across architectures and datasets.
- 2.1 Definitions: The loss barrier is the maximum excess loss along linear interpolation compared with the linearly interpolated endpoint losses.
- 2.1 Definitions: Linear mode connectivity means that two networks have an approximately zero barrier along their linear path.
- 2.2 Empirical Investigation: Barriers: The paper studies barrier size across MLP, Shallow CNN, VGG, and ResNet architectures on MNIST, SVHN, CIFAR-10, and CIFAR-100.
- Width: For large widths, barriers become small, with the decrease beginning at lower widths on simpler datasets such as MNIST and SVHN.
- Width: The width experiments show a peak followed by decreasing barriers, a pattern described as reminiscent of double descent.
- Depth: Increasing depth produces a fast and significant barrier increase in fully connected and convolutional networks, eventually reaching saturation in VGG and ResNet.
3 Role of Invariance in Loss Barriers
The paper argues that hidden-unit permutation invariance may remove linear barriers between SGD solutions, simplifying the loss landscape. It supports this conjecture with a limited theoretical result and empirical proxy comparisons, while acknowledging search and scope limitations.
- Invariances in neural network function class: Permutation invariance is important because hidden-unit permutations preserve network functions and are equally likely under SGD.The paper focuses on permutation invariance rather than scale invariance because SGD is more likely to converge to particular rescalings, whereas permutations remain equally likely.
- Our Conjecture: The conjecture states that most SGD solutions can be permuted so every pair has approximately zero barrier along linear interpolation.Formally, a set S should contain SGD solutions with a permutation function Q such that B(P(θ1,Q(θ1)),θ2) ≈ 0.
- A theoretical result: The theoretical result proves the conjecture for wide enough one-hidden-layer fully connected networks at random initialization.With probability 1 − δ, a permutation exists that yields no barrier; extending the result beyond random initialization is left for future work.
- Direct empirical evaluation of Conjecture 1: Brute-force permutation search becomes infeasible as hidden-layer width grows, reaching 24! ≈ 2 · 10^13 permutations for a 24-neuron one-hidden-layer MLP.More advanced search can help, but failed searches cannot distinguish algorithmic failure from the nonexistence of a barrier-removing permutation.
- Our model vs real world: An alternative approach: The proposed proxy S′ consists of all valid permutations of one SGD solution, whose barriers can be removed by applying inverse permutations.The empirical goal is to show that real SGD solutions S resemble S′ in barrier behavior without exhaustively optimizing over all permutations.
4 Empirical Investigation
The empirical investigation compares real and permutation-invariant model barriers across architectures and settings, while testing simulated annealing for finding barrier-reducing permutations. Reduced search spaces improve the search, and the resulting barrier patterns support the conjecture.
- Barrier comparisons: The model S′ and real-world model S exhibit strikingly similar barriers across architecture families, datasets, widths, and depths.The similarity is reported as strong evidence for the conjecture.
- Permutation search: Simulated annealing searches permutations by minimizing either average pairwise barriers or the train error of an averaged permuted model.The study uses SA2 in its reported experiments because it is significantly less computationally expensive while performing similarly to SA1.
- Permutation search: Reducing the search space to permuting θ1 against θ2 helps simulated annealing find better permutations, especially for MNIST and SVHN across MLP and shallow CNN widths.Increasing depth did not produce significant improvements in this intervention.
- Permutation search: After search-space reduction, simulated annealing sometimes finds permutations producing zero barrier, including selected MNIST MLP depth and width settings.Reported examples include depth 1 across all widths, and depths 2 and 4 at width 210.
- Barrier comparisons: More than 3000 trained networks contribute to a density plot showing barrier similarity across architecture family, dataset, width, depth, and random seed.The aggregated empirical results support the main conjecture.
5 Discussions and Conclusion
The discussion interprets barriers as potentially arising from ignored permutation invariance and connects the conjecture to initialization, search, ensembles, distributed training, and pruning. The study is limited by search-space complexity and its focus on image recognition.
- Interpretation: The conjecture treats barriers between neural-network solutions as artifacts of ignoring permutation invariance, placing properly permuted solutions in essentially the same basin.This is presented as the paper’s central interpretation of the loss landscape.
- Initialization and search: The analysis suggests that permutation randomness in initialization may not affect the quality of the final result.The authors propose exploring initialization schemes that perturb a fixed permutation rather than sampling across permutations.
- Applications: Tracking an optimal permutation could enable more efficient weight averaging and ensemble construction for solutions brought into one basin.The paper frames ensemble and distributed-training applications as areas for further investigation.
- Applications: The analysis motivates questions about whether lottery tickets correspond one-to-one with permutations and about the usefulness of the conjecture for pruning.These questions are identified as subjects for future studies.
- Limitations: The study is constrained by permutation-search complexity, especially for deep models, and by experiments focused on image recognition rather than natural-language tasks.The authors identify stronger search algorithms and extension to natural-language tasks as future work.
A Implementation details
The experiments were managed in a reproducible Google Cloud AI Platform environment, with plotted values averaged over repeated runs and trained networks.
- Experiment setup: The experiments used Caliban to manage a reproducible environment in Google Cloud’s AI Platform.This describes the experiment-management infrastructure.
- Experiment setup: Each plotted point reports a mean over 10 runs involving 20 trained networks.The averaging procedure applies to the points shown in the plots.
A.1 Training Hyper-parameters
Training hyper-parameters for the different networks are summarized in Table 1, with SVHN, CIFAR10, and CIFAR100 among the listed datasets.
- Training setup: Table 1 summarizes the hyper-parameters used to train the different networks.The passage identifies the table’s purpose but does not enumerate the settings.
- Training setup: The listed datasets include SVHN, CIFAR10, and CIFAR100.These dataset names appear in the implementation details.
A.2 Performance Evaluation of Trained Models: Error and Loss
The evaluation reports train and test error/loss across width and depth experiments, using specified architectures, training durations, and stopping criteria.
- Width: Width experiments cover MLPs, shallow CNNs, ResNet18, and VGG16, with train and test error/loss tracked during training.MLPs use one hidden layer; shallow CNNs use two convolutional layers.
- Depth: Depth experiments vary the number of layers while fixing layer widths at 1024 hidden units for MLPs and specified channel counts for convolutional models.The channel counts are 1024 for shallow CNNs, 64 for VGG, and 64 for ResNet.
- Training protocol: All models train for 1000 epochs except MLPs, which train for 3000 epochs, stopping when cross-entropy loss reaches 0.01 or the epoch limit is reached.The same stopping rule is reported for both width and depth experiments.
A.3 Similarity of S and S′: Detailed view
Detailed experiments find that the model built from random permutations reproduces real-world barrier patterns across architectures, datasets, widths, depths, and seeds. Restricting the permutation search improves the ability to find lower or zero barriers.
- Aggregated evidence: More than 3000 trained networks show similar barriers between real-world SGD solutions and the random-permutation model across architectures, datasets, widths, depths, and seeds.Figure 10 aggregates these comparisons in one plot.
- Similarity of S and S′: Mean barrier sizes for S and S′ remain similar before permutation, and this similarity also appears after permutation using simulated annealing.The comparison varies architecture parameters such as width and depth across multiple datasets.
- Reduced search space: Reducing the search space makes simulated annealing more successful at finding permutations that reduce barriers across networks and datasets.The reduced setting permutes θ1 while comparing it with θ2, using n = 2.
- Zero-barrier cases: Zero-barrier permutations are found for several MLP and shallow-CNN settings across MNIST, SVHN, CIFAR10, and CIFAR100.Reported examples include shallow MLPs with depth 1 and width 23 or 24, and shallow CNNs with depth 2 and width 24.
- Width and depth: Barrier similarity between the real-world and model settings is preserved as width and depth increase when the search space is reduced.This pattern is reported before permutation across model types and datasets.
A.4 Simulated Annealing
The section describes simulated annealing as a search procedure for neuron permutations that evaluates linear-mode-connectivity barriers. Better permutations are found with reduced search spaces, more computation, and functional-difference matching, but the method is not always optimal.
- Annealing procedure: Simulated annealing randomly alters permutations, evaluates the resulting barrier, and accepts moves based on improvement or the current temperature.Worse moves can be accepted early, while later iterations favor permutations that improve the barrier.
- Annealing procedure: The annealing temperature decreases during the search, shifting selection toward permutations that improve the objective.The objective is the barrier associated with the permuted model.
- Scaling computation: Increasing the number of annealing steps exponentially helps find better solutions, while the barrier continues to decrease as computation increases.The paper reports 50K steps as the practical setting because of computational limits.
- Open search problem: Simulated annealing only reduces the barrier, motivating the question of whether another algorithm can find better permutations.The reduced search-space setting improves its performance but does not resolve the broader search problem.
- Alternative matching: Functional difference finds better permutations than simulated annealing by matching neurons using a distance matrix and greedy minimum-distance assignments.The resulting permutations improve the barrier between two solutions.
- Ensemble methods: Functional difference outperforms simulated annealing in the reported ensemble comparison, while subspace learning places solutions into one basin from scratch.The combined FD + SL approach is presented as combining functional diversity with basin alignment.
D Proof of Theorem 3.1
The theoretical section analyzes permutation-based alignment of randomly sampled one-hidden-layer ReLU networks and derives a high-probability approximation result. Additional experiments examine label noise, architecture scaling, and indirect barriers.
- Theorem statement: Theorem D.1 considers ReLU networks with hidden width h and input dimension d, with parameters sampled uniformly from bounded intervals.The theorem concerns two independently sampled parameterizations and a permutation of one network’s parameters.
- Theorem statement: With probability 1 − δ, a permutation exists such that interpolating the aligned parameters approximately matches interpolation of the corresponding network functions.The aligned parameters are denoted by v′′ and U′′.
- Proof strategy: The proof constructs a permutation by grouping rows of the weight matrices near grid points, matching corresponding groups, and separately handling size mismatches.Hoeffding bounds and a union bound control group sizes and matching errors.
- Proof bound: The resulting approximation error is bounded by ϵ = ˜O(h^−1/2d+4), according to the stated theorem analysis.The proof uses the Lipschitz property of ReLU activations to control the function difference.
- Label noise: Across five runs, increasing label noise does not change barrier-size behavior, although higher noise produces a small barrier increase.The experiment reports train and test loss, error, and train barrier under different noise levels.
- Additional analyses: For VGG and ResNet models, barriers remain saturated at high values as width and depth increase, while indirect barriers are defined through intermediate networks.Figure 18 examines direct and indirect barriers for pairs of networks trained from different initializations.
E.5 Similarity of S and S′ on the test set
Test-set barrier trends remain similar before and after permuting one solution, while simulated annealing can find permutations that nearly eliminate barriers across architectures, datasets, widths, and depths.
- SA performance on S and S′ yields similar test-barrier results before and after permutation.
- This similarity holds across a wide range of widths and depths for MLP and Shallow-CNN models on MNIST, SVHN, CIFAR-10, and CIFAR-100.
- Test barriers shrink for hard tasks such as CIFAR-10 and CIFAR-100, and also become small for simpler tasks at large widths.
- Low barriers occur at low depth, whereas increasing layers produces a fast and significant barrier increase across fully connected and CNN families.
- The similarity of loss barriers between the real-world setting and the model is preserved as width and depth increase before permutation.
- Reducing the search space improves SA’s ability to find permutations that produce almost zero test barriers across network and dataset settings.