Contribution
A proof that mode connectivity follows from dropout stability or noise stability, for fully connected (and, with channel-wise dropout, convolutional) ReLU nets of any depth, with an explicit piecewise-linear path; and a counterexample showing that it does not follow from overparametrization alone.
Key insight
A network that only needs half its capacity has a free half. Zero out the redundant half without loss, use it as scratch space to copy, swap and reorder the working units, and two such networks can be morphed into each other without ever leaving low loss. Connectivity is cheap whenever solutions are robust, and robustness is what training is already known to produce.
Assumptions
- Architecture: fully connected ReLU nets x_i = A_i φ(x_{i−1}), d layers; convolutional nets with channel-wise dropout (Remark 1).
- Loss convex in the output; for Section 4, β-Lipschitz in the output (cross-entropy over softmax is √2-Lipschitz).
- ε-connected (§2): a continuous path with L(f_{π(t)}) ≤ max{L(θ_A), L(θ_B)} + ε.
- ε-dropout stable (Definition 1): for every i, at most ⌊h_j/2⌋ units in each layer j from i to d − 1 can be kept and rescaled by r, the rest zeroed, at loss cost ≤ ε.
- ε-noise stable (Definitions 2–4): layer cushion µ_i, minimal interlayer cushion µ_{i→} (with the spectral norm of the Jacobian in place of Arora et al.’s Frobenius norm), activation contraction c, interlayer smoothness ρ ≥ 3d, h_min = Ω̃(1), and spread activations; then ε = βc d^{3/2} max‖f_θ(x)‖ / (h_min^{1/2} min_i µ_i µ_{i→}).
- Theorems 3 and Lemma 3 also need ‖[A_i]_j‖ = O(√p)‖A_i‖_F: no single column dominates a weight matrix.
Key results
- Lemma 1: a path from θ to its dropout version through each θ_i with loss ≤ L(θ) + ε, built from two kinds of steps: interpolate top-layer weights (loss convex there), or change the input weights of units whose outputs are already zeroed (Fig. 1: six segments for a 3-layer net).
- Lemma 4: any permutation of the non-zero units of a half-zeroed network in five segments at constant loss.
- Lemma 2: two half-zeroed networks are connected by 8 segments with loss ≤ max of the two.
- Theorem 1: dropout-stable solutions are ε-connected.
- Lemma 3: an ε-noise-stable network can be interpolated linearly to a random dropout version with loss ≤ L(θ) + Õ(√p ε), with probability ≥ 1/4, for Ω̃(1/h_min) < p ≤ 3/4.
- Theorem 2: two ε-noise-stable networks are joined by 10 segments with barrier Õ(ε).
- Theorem 3: if a network θ* of widths h_i achieves loss L(θ), then for 1.5 max_i(h_i/h_i) ≤ p ≤ 3/4 there is a 13-segment path with loss ≤ max{L(θ_A) + Õ(√p ε), L(θ_B) + Õ(√p ε), L(θ)}.
- Theorem 4: for any h and convex loss minimized at ŷ = y, some dataset generated by a two-hidden-unit teacher has disconnected global minimizers for an h-unit student.
- Experiments (§6, App. D): MNIST, 3 conv layers of 32 3×3 filters, best of 20 sampled dropout subnetworks, averaged over 5 trials (Fig. 2); a linear path from the net to its p = 0.2 dropout version; narrow nets of a few filters reaching low loss. CIFAR-10 VGG-11 with channel-wise dropout (p = 0.25 in the first three layers, 0.5 elsewhere) reaches 95%/91% train/test accuracy with dropout on, 99%/92% off; its noise-stability quantities are well behaved (Fig. 3), and networks trained without channel-wise dropout behave similarly except in the first few layers.
Claims
| id | claim | strength | support |
|---|---|---|---|
| C1 | Dropout-stable ReLU solutions are mode connected by piecewise-linear paths | strong (proof) | Theorem 1, App. A |
| C2 | Noise-stable solutions are connected by 10 segments with barrier Õ(ε) | strong (proof), under strong assumptions | Theorem 2, App. B |
| C3 | Overparametrization alone does not imply connectivity of all global minima | strong (construction) | Theorem 4, App. C |
| C4 | Trained convnets satisfy the assumptions approximately | weak to moderate: MNIST convnets and one VGG-11 | §6, Figs. 2–3 |
Concepts
- ε-mode connectivity w.r.t. a class C: every pair of minimizers in C is ε-connected; the paper restricts to dropout- or noise-stable solutions.
- spurious valley: a non-global minimum surrounded by higher loss.
- dropout stability, noise stability: as in Assumptions.
Connections
- Garipov et al. (LIT-673), Draxler et al. (LIT-653). The phenomenon explained. The paper notes that their evidence covers only “typical optima discovered by gradient-based optimization”, which Theorem 4 shows is essential.
- Freeman & Bruna (2016), Venturi et al. (2018), Nguyen et al., not held: earlier connectivity results needing exponential width or more neurons than data.
- Arora et al. (2018), not held: the noise-stability quantities, from a compression-based generalization bound.
Bearing on the record
- Supports the THEORY candidate that SGD optima lie in one connected low-loss set, and qualifies it: the set is connected among robust solutions, not among all minima.
- Its Lemma 4 is the proof-level version of the claim that permutations cost nothing when there is spare capacity, which bears on the candidate that barriers are mostly permutation artefacts.
Limitations
- Paths are long and not linear. Dropout-stable paths grow in segments with depth; even the noise-stable path has 10 segments. Nothing here explains why Garipov et al. find one bend enough, or anything about straight lines.
- Dropout stability at half width is strong. The paper itself relaxes it in experiments (Fig. 2 allows wider subnetworks) and leans on Theorem 3.
- Thin experimental check: MNIST and one CIFAR-10 VGG-11, trained with channel-wise dropout.
- Theorem 4 is an existence result for a constructed dataset; it says nothing about how common disconnected minima are on real data.
Open questions
- Does SGD provably produce dropout- or noise-stable solutions? Shevchenko and Mondelli (2020, not held), cited by Ferbach et al., answer this for wide two-layer nets in the mean-field regime.
- Can the number of segments be brought down to the one bend seen in practice?
Corrections
- none to a seeded skim (there was no seed)