EPFL Proves Why Gradient Descent Finds Good Solutions on Non-Convex Networks
EPFL researchers deliver a rigorous proof that small-initialization gradient flow on shallow ReLU nets converges to a minimum-norm interpolator through saddle-to-saddle dynamics.
Takeaways
- EPFL trio proves gradient flow on shallow ReLU nets with orthogonal inputs converges to zero loss despite non-convexity.
- The selected minimizer has minimum L2 parameter norm, giving the first implicit-bias characterization for ReLU regression.
- Saddle-to-saddle dynamics, previously only conjectured for linear networks, is now rigorously proven in this setting.
- Proof decomposes training into alignment, positive-label fitting, saddle crossing, negative-label fitting, and local PL convergence.
- Toy code and animated figures available at github.com/eboursier/GFdynamics; full paper on arXiv 2206.00939.
- Key limits: orthogonality assumption, ReLU-specific L2 bias, and width exponential in dataset size for the analysis to apply.
Why does gradient descent, running on a wildly non-convex loss surface, keep landing on solutions that generalize? A team at EPFL has pushed that question closer to a real answer with a NeurIPS paper that pins down, with full mathematical rigor, what happens during training of a one-hidden-layer ReLU network on a specific but instructive setup: orthogonal input vectors, mean squared error loss, and vanishingly small initialization.
Etienne Boursier, Loucas Pillaud-Vivien, and Nicolas Flammarion prove three things that had previously only been observed empirically or conjectured: the flow converges to zero loss despite the non-convex landscape, it selects the interpolator with the smallest parameter norm, and it does so by hopping between saddle points of the loss.
The gap the paper closes
Despite recent progress, a complete theory explaining the success of gradient descent for neural networks is still missing. Two blind spots have persisted. Most convergence proofs live in the so-called lazy or Neural Tangent Kernel regime, where the network is so wide (or initialized so large) that neurons barely move and the dynamics reduce to a kernel method. That regime is analytically tractable but it does not do feature learning, which is arguably the interesting thing neural networks do.
Shrinking the initialization pushes training into the feature-learning (rich) regime, where the trajectory passes near saddle points and the standard Polyak-Lojasiewicz inequality (a gradient lower bound of the form ||grad L||^2 >= c L) fails. Prior tools break down there. Empirically, training curves plateau at these saddles and then jump, but nobody had proved this behavior in the regression setting.