Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets

Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, Sanjeev Arora

Introduction

This paper provides a rigorous mathematical explanation for mode connectivity—the surprising empirical observation that different high-performing neural network solutions are connected by simple, low-loss paths in the parameter space. By defining properties such as "dropout stability" and "noise stability," the authors prove that these paths exist for realistic multilayer networks and can be constructed using just a few linear segments.

The Landscape Connectivity Problem

When training deep neural networks, optimization algorithms often converge to different "optima" (sets of weights resulting in low training loss) depending on the random initialization. Historically, researchers assumed these optima were isolated in separate "valleys" divided by high-loss "walls."

However, recent empirical studies have discovered that these valleys are actually connected: it is possible to traverse from one solution to another along a path where the loss remains nearly constant. While this phenomenon has been widely observed in practice, a solid theoretical explanation has been missing for realistic, multilayer architectures. Previous proofs either only applied to simple two-layer networks or required the networks to be "exponentially wide" (having an unrealistic number of neurons). This paper bridges that theoretical gap.

Core Concepts: Stability and Robustness

The authors propose that mode connectivity is a natural consequence of the robustness properties that well-trained networks naturally acquire during optimization. They focus on two key concepts:

  1. Dropout Stability: A network is "dropout stable" if one can remove a significant portion of its neurons (setting their outputs to zero) and rescale the remaining ones such that the loss remains low. This property suggests the network has learned significant internal redundancy.
  2. Noise Stability: This is a stronger property indicating that the network's output is insensitive to Gaussian noise injected into its hidden layers.
Loss and accuracy as a function of dropout probability, demonstrating dropout stability.

Constructing the Path: The "Thinning" Trick

The core of the authors' proof is a novel method to build a path between two distinct solutions, $\theta^A$ and $\theta^B$. Because a direct straight line between solutions usually fails (resulting in a high-loss barrier), they construct a piece-wise linear path.

The "aha moment" of their strategy is the realization that you do not have to move directly between two complex models. Instead, the path construction involves:

  • Shrinking: Reducing the first network to a "thin" version where many neurons are zeroed out, leveraging its dropout stability.
  • Navigating: Moving through the parameter space while the network is in this simplified, thin state where the two models share a common structure.
  • Expanding: Growing the network back into the second solution.

Interestingly, the authors also provide a counter-example, constructing a specific dataset and network where global optima are not connected. This proves that connectivity isn't a universal law of all networks, but rather a specific property of networks that generalize well and exhibit stability.

Key Insights and Results

  • Connectivity is a byproduct of robustness: The same properties that help a network generalize to new data—like being unfazed by noise or missing neurons—are exactly what allow it to be connected to other solutions in the loss landscape.
  • Overparameterization isn't enough: Simply having more parameters than data points does not guarantee connectivity. The structure of the solution and its stability are the true determining factors.
  • Theoretical Guarantees: The authors mathematically prove that if two solutions are dropout stable, they are $\epsilon$-connected. For noise-stable networks, they guarantee connectivity via a path of 10 to 13 line segments.
Loss and accuracy along the constructed path between two solutions.

To validate their theoretical findings, the authors tested standard benchmarks, including MNIST with a 3-layer CNN and CIFAR-10 with a VGG-11 architecture. They showed that while a direct linear interpolation between two models causes accuracy to plummet to ~10%, their theoretically-inspired path keeps accuracy high and loss low throughout the entire transition. Furthermore, they empirically confirmed that standard networks naturally satisfy the "layer cushion" and "interlayer smoothness" conditions required for their noise stability theory.

Limitations and Future Directions

While this paper makes significant theoretical strides, several open questions remain:

  • The Segment Gap: There is a discrepancy between theory and practice regarding path complexity. Theory suggests 10-13 segments are needed, but empirical experiments often find that just 2 segments are sufficient. Closing this theoretical bound is an open challenge.
  • Origin of Stability: The proofs assume networks are noise or dropout stable (which aligns with empirical observations). However, the paper does not fully explain why standard training algorithms like Stochastic Gradient Descent (SGD) consistently gravitate toward these stable regions in the first place.
  • Architecture Scope: The current theory covers multilayer ReLU networks and CNNs. Extending these proofs to more complex, modern structures like Transformers or Attention mechanisms represents a promising direction for future work.

Summary updated

Abstract

Mode connectivity is a surprising phenomenon in the loss landscape of deep nets. Optima -- at least those discovered by gradient-based optimization -- turn out to be connected by simple paths on which the loss function is almost constant. Often, these paths can be chosen to be piece-wise linear, with as few as two segments. We give mathematical explanations for this phenomenon, assuming generic properties (such as dropout stability and noise stability) of well-trained deep nets, which have previously been identified as part of understanding the generalization properties of deep nets. Our explanation holds for realistic multilayer nets, and experiments are presented to verify the theory.
BibTeX
@inproceedings{kuditipudi2019explaining,
  author = {Rohith Kuditipudi and Xiang Wang and Holden Lee and Yi Zhang and Zhiyuan Li and Wei Hu and Rong Ge and Sanjeev Arora},
  title = {{Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure