Organizations: School of Electrical and Computer Engineering, Georgia Institute of Technology · College of Computing, Georgia Institute of Technology · School of Mathematics, Georgia Institute of Technology · H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology
Overparameterized ML models, including neural networks, typically induce underdetermined training objectives with multiple global minima. The implicit bias refers to the limiting global minimum that is attained by a common optimization algorithm, such as gradient descent (GD). In this paper, we characterize the implicit bias of GD for training a shallow ReLU model with the squared loss on high-dimensional random features. Prior work (Vardi and Shamir, 2021) showed that the implicit bias does not exist in the worst-case, or corresponds exactly to the minimum-ℓ2-norm interpolating solution under exactly orthogonal data (Boursier et al., 2022). Our work interpolates between these two extremes and shows that, for sufficiently high-dimensional random data, the implicit bias approximates the minimum-ℓ2-norm solution with high probability with a gap on the order Θ(n/∣∣λ∣∣1), where n is the number of training examples and λ denotes the spectrum of the data covariance matrix. Our results are obtained through a novel primal-dual analysis that carefully tracks the evolution of predictions, data-span coefficients, as well as their interactions, and show that the ReLU activation pattern quickly stabilizes with high probability over random data.
Figures & tables
Orthogonal data
High dimensional data
Worst-case data
ReLU models ( k=1 ) h(x):=∑k=1mskσ(wk⊤x)
Implicit bias characterization ( Boursier et al., 2022 ) w(∞)=w∈{w:Xw=y}argminw−w(0)2
Global convergence only ( Dana et al., 2025 )
No implicit bias in general ( Vardi and Shamir, 2021 ) w(∞)−w(0)2≤2⋅w⋆−w(0)2
This work w(∞)−w⋆2≍∥λ∥1n
Linear models h(x):=w⊤x
Implicit bias coincides with maximum ℓ2 margin SVM ( Hsu et al., 2021 )
w(∞)=w∈{w:Xw=y}argminw−w(0)2 ( Engl et al., 1996 )
Table 1: Our results contextualized with related literature.
Figure 2
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: We illustrate the prediction dynamics of gradient descent for a single ReLU model under different random initializations when d is comparable with n . In both cases, with sufficiently small step size, the final solution converges to a linear minimum- ℓ2 -norm interpolator on some subset of the training examples, i.e. of the form wlinear-MNI,S=XS⊤(XSXS⊤)−1y~S , where y~S,i=max{yi,0} . In contrast to the high-dimensional regime, different initializations lead to different subsets S , indicating that ReLU training implicitly performs an example “selection” process, that is initialization-dependent, rather than fitting all positively-labeled samples. The experiment uses n=10 , d=50 , x∼N(0,I) , y∼N(0,1) , w(0)∼N(0,2×10−6I) , and η=10−4 .
Figure 4: Simulation illustrating Theorem 3 . In the high-dimensional regime and under our “all-positive” initialization, after the first gradient step, examples with positive labels remain active while examples with negative labels become inactive, consistent with Lemma 13 . The blue region shows primal variables that remain positive over training, whereas the red region corresponds to dual variables that are sufficiently negative and remain unchanged. As training proceeds, w⊕ fits all positively labeled examples and w⊖ fits all negatively labeled examples. The experiment uses n=10 , d=2000 , features x∼N(0,I) , and labels satisfying ∣y∣∼U(0.1,1) with sign(y) uniformly distributed over {±1} .
Figure 5: Simulation with random initialization in the high-dimensional regime, which violates our initialization assumption in Theorem 3 . Under random initialization, the sufficient conditions of Lemma 13 are violated at the first gradient step. As a result, positively labeled examples do not all remain in the active (blue) regime (e.g., example no. 5), nor do negatively labeled examples consistently enter the inactive (red) regime (e.g., example no. 7). Consequently, during training, this model fails to converge to a global minimum. The experiment uses n=10 , d=2000 , features x∼N(0,I) , and labels satisfying ∣y∣∼U(0.1,1) with sign(y) uniformly distributed over {±1} .
Figure 6: Simulation with all-positive initialization outside the high-dimensional regime. When the data dimension is not sufficiently large, the feature vectors are no longer approximately orthogonal. As a result, the clear separation into active (blue) and inactive (red) regimes observed in Figures 4 and 5 disappears. Consequently, the gradient dynamics become highly coupled across examples and are no longer analytically tractable using our high-dimensional arguments. The experiment uses n=10 , d=15 , features x∼N(0,I) , and labels satisfying ∣y∣∼U(0.1,1) with sign(y) uniformly distributed over {±1} .
Figure 7: Failure of stable activation patterns in multiple ReLU models. We illustrate the training dynamics of a multiple ReLU model when multiple neurons share the same sign. In this setting, the sufficient conditions of Lemma 15 are violated, and positive primal variables do not necessarily remain in the active (blue) regime throughout training (e.g. training example no. 0). As a result, the activation pattern becomes unstable, and the resulting primal dynamics are no longer tractable. The experiment uses n=10 , d=2000 , m=4 , with neuron signs s1=s2=1 and s3=s4=−1 , features x∼N(0,I) , and labels satisfying ∣y∣∼U(0.1,1) with sign(y) uniformly distributed over {±1} .
We study the implicit bias of noisy stochastic gradient descent in training wide two-layer ReLU networks for multivariate regression. In a mean-field regime, the training dynamics are approximated by a Wasserstein gradient flow that converges to a unique stationary measure. We characterize the structure of this stationary measure and the predictor it represents. We show that, despite the network being infinitely overparameterized, the learned predictor admits an effectively finite representation: the input weights and biases align along finitely many directions, leading to an effective width collapse. In particular, the solution function is continuous piecewise affine, with affine regions determined by the cells of a finite hyperplane arrangement. The number of learned directions, and hence hyperplanes, is bounded above by 2P−1, where P denotes the number of linear dichotomies realizable on the training inputs. We further establish a non-redundancy property of the learned representation by proving that each learned direction induces a unique ternary activation pattern on the training data. Consequently, the complexity of the learned predictor is governed by the combinatorial geometry of the training data.
Shuang Liang, Tom Jacobs, Guido Montúfar
Department of Statistics & Data Science University of California, Los Angeles Los Angeles, CA 90095, USA · CISPA Helmholtz Center for Information Security · Departments of Mathematics and Statistics & Data Science University of California, Los Angeles; and Max Planck Institute for Mathematics in the Sciences
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≳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 ℓ2-norm scaling as n, which is within a constant factor of the minimal ℓ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.
James Town, Etienne Boursier, Ben Lewis +2
University of Warwick · INRIA LMO, Université Paris-Saclay
Deep learning systems are known to exhibit implicit regularization (alt. implicit bias), favoring simple solutions instead of merely minimizing the loss function. In some cases, we can analytically derive the implicit regularization -- connecting it to an equivalent penalty that augments the learning objective. However, modern deep learning systems are complex, carrying modifications to the training procedure and architecture (e.g. early stopping, minibatching, dropout) whose effects are not always directly interpretable. Although estimating the resulting implicit regularization could aid theorists in algorithm design and practitioners in interpreting their hyperparameter choices, this problem has received little direct attention. It is also tractable: regularization makes weight updates deviate from loss gradients, promising a signal for identifying implicit bias. Here we provide gradient matching methods that can be used to empirically estimate the implicit regularization. Our method works on networks with known regularization, recovering popular explicit penalties like ℓ1 and ℓ2. It also replicates known implicit effects, like the quadratic weight penalty induced by early stopping in gradient descent, demonstrating that it can be used to test theories of implicit regularization. Crucially, because our method is empirical, it can handle implicit regularization in arbitrary networks. We demonstrate this use by characterizing the effects of dropout in deep networks, showing implicit ℓ2 effects in this popular method. Our work shows that practitioners can use gradient matching to understand regularization in networks with implicit biases that are too complicated to derive analytically.