Mildly Overparameterized ReLU Networks on Orthogonal Data: Incremental Learning and Implicit Bias
AuthorsJames Town, Etienne Boursier, Ben Lewis, Matthias Englert, Ranko Lazic
Resources
This paper proves that small two-layer ReLU networks can learn one neuron at a time in a saddle-to-saddle process, and it quantifies how close the resulting solution is to the simplest possible interpolator.
Key results
The experiment shown in Figure 1 trains the two-layer ReLU network on 64 orthonormal data points in 64 dimensions to visualize the predicted saddle-to-saddle dynamics.
Figure 1 uses a two-layer ReLU network with 6 neurons, and the observed loss plateaus and sharp drops match the predicted neuron-activation jumps.
The main convergence theorem applies in this width regime, where the accelerated gradient-flow trajectory converges to a saddle-to-saddle jump process.
The learned interpolator’s squared parameter norm scales as √n, and the paper states this is within a constant factor of the minimal ℓ2-norm interpolator’s scaling.
What the paper found
This paper gives the first rigorous characterization of gradient-flow dynamics for a two-layer ReLU network in the small-initialization, mildly overparameterized regime on orthogonal training data. The main result is a saddle-to-saddle limit process as the initialization scale α→0 after a log(1/α) time rescaling: the network stays near a saddle, then abruptly activates exactly one new neuron, fits a new subset of samples, and repeats. This produces an incremental learning mechanism that is absent from prior NTK-style or infinite-width analyses. The recursion is made explicit in Algorithm 1, which computes jump times and active neurons directly from the orthogonal data and the initialization mask, without simulating training. Under widths log(n)≲m≪exp(n log 2 /2), the authors prove that the accelerated trajectory converges uniformly away from jump times and recover Dana et al. (2025)’s interpolation guarantee. The novelty is the implicit-bias theorem: although the learned interpolator is not the minimum-ℓ2 solution once m≲2n, its squared parameter norm is still O(√n) and within a constant factor of the optimal ℓ2 interpolator’s scaling. Empirically, on 64 orthonormal points in 64 dimensions with a six-neuron ReLU network, the loss exhibits long plateaus followed by sharp drops, exactly matching the predicted saddle transitions, and the neuron norms grow exponentially with piecewise-linear log-norms.
Original abstract
The successful training of neural networks hinges on the use of first order optimization methods, yet the theoretical characterization of these methods remains incomplete. This is especially true in settings with mild overparameterization. In this work, we study the gradient flow dynamics of two-layer ReLU networks from small initialization with orthogonal training data. We prove the limiting flow converges to a saddle-to-saddle jump process as the initialization scale tends to zero, revealing an incremental learning phenomenon in which a new neuron activates at each saddle. This analysis recovers the known result of Dana et al. (2025, arXiv:2502.16977) that the network interpolates the training data with high probability as soon as $m \gtrsim \log(n)$, where $m$ is the network width and $n$ is the number of training samples. This incremental process characterization also allows us to derive a novel implicit bias result: the learned interpolator has a squared $\ell_2$-norm scaling as $\sqrt{n}$, which is within a constant factor of the minimal $\ell_2$-norm interpolator. More broadly, our work provides the first rigorous proof of an incremental learning process for ReLU networks, whilst suggesting mildly overparameterized networks can converge to interpolating solutions whose complexity is of the same order as that of the optimal interpolator.
Read the original paperMore in Neural Networks
Browse all 22 papers →End-to-End Hard-Label Cryptanalytic Model Extraction Using Efficient Sign Recovery
Akira Ito, Takayuki Miura, Yosuke Todo
A new query-efficient technique makes it possible to steal the parameters of small black-box neural networks using only their predicted labels.
Retrieving Individual Stems from Music Mixtures with Slot Embeddings
David Braun, Junyi Fan, Pranay Manocha, Donald S. Williamson, Adam Finkelstein
Stembed lets music producers search for individual instrument sounds hidden inside a full song by representing the mixture as multiple searchable stem-like embeddings.
The Linear Representation Hypothesis Needs a Group Action
Louie Hong Yao, Yuhao Li, Shengchao Liu
This paper argues that claims about linear representations only become meaningful once we specify which transformations leave a representation essentially unchanged.