How Gradient Descent Selects Simple Solutions

283 concepts228 papers1 proposal

Modern deep learning models are famously overparameterized: they contain far more parameters than training examples. Classical statistical theory warns that such models possess the capacity to perfectly memorize noise, leading to catastrophic overfitting. Yet, in practice, these massive networks generalize remarkably well to unseen data.

This phenomenon hinges on implicit bias: even when the training loss landscape contains an infinite number of global minima that perfectly fit the data, gradient-based optimization algorithms do not choose a random solution. Instead, the mechanics of the optimization process implicitly steer the model toward "simple" or highly structured functions.

Understanding why gradient descent prefers simplicity requires looking closely at how different loss functions, network architectures, and optimization dynamics interact.

Classification and Margin Maximization

Why does gradient descent avoid complex, jagged decision boundaries when training a classifier? The answer lies in how gradient updates behave under exponential-tail losses, such as logistic or cross-entropy loss.

Consider a dataset that is linearly separable. To drive the logistic loss to zero, the model must make its predictions as confident as possible. Because the loss only approaches zero as the logits approach infinity, the weight vector $w$ must grow infinitely large in magnitude.

As $w$ grows, what happens to its direction? Mor Shpigel Nacson et al. demonstrated in Convergence of Gradient Descent on Separable Data that the direction of $w$ asymptotically converges to the $L_2$ maximum-margin separator—the exact same solution found by a hard-margin Support Vector Machine (SVM).

The intuition behind this convergence comes from the gradient of the loss function. The gradient of the logistic loss $\log(1 + e^{-y w^T x})$ is proportional to:

$$\frac{-y x}{1 + e^{y w^T x}}$$

As the weights grow, the term $e^{y w^T x}$ grows exponentially for data points that are safely on the correct side of the decision boundary, causing their contribution to the gradient to vanish. The only points that continue to exert a meaningful force on the gradient are those closest to the decision boundary—the support vectors. Consequently, gradient descent spends its final iterations pushing the boundary as far away from these closest points as possible, naturally maximizing the margin.

This margin-maximizing behavior is not restricted to linear models. Kaifeng Lyu et al. proved in Gradient Descent Maximizes the Margin of Homogeneous Neural Networks that gradient descent maximizes the margin for homogeneous neural networks (such as multi-layer ReLU networks without bias terms). Even in complex multiclass settings, Hrithik Ravi et al. showed in The Implicit Bias of Gradient Descent on Separable Multiclass Data that a multiclass exponential tail property ensures the optimizer favors hard-margin solutions over other interpolating functions.

Matrix Factorization and Low-Rank Structure

In regression or matrix completion tasks, overparameterization manifests differently. If we train a model to fill in a matrix or fit a sequence of linear layers, there are infinite ways to interpolate the training labels. Yet, gradient descent consistently finds low-complexity, low-rank solutions.

To understand why, consider a matrix factorization problem where we learn a matrix $W$ parameterized as the product of two factors, $W = U V^T$. Running gradient descent directly on the entries of $W$ yields no regularizing bias. However, running gradient descent on the individual factors $U$ and $V$ fundamentally alters the dynamics.

As shown by Suriya Gunasekar et al. in Implicit Regularization in Matrix Factorization, optimizing the factors implicitly minimizes the nuclear norm (the sum of the singular values) of $W$. This mathematical bias directly forces the model toward low-rank solutions.

The physical mechanism driving this bias is multiplicative growth. The continuous-time gradient flow updates for the factors couple together, meaning the rate of change of $W$ depends directly on its current magnitude:

$$\dot{W} \propto U \dot{V}^T + \dot{U} V^T$$

When initialized with very small weights, the components of $W$ corresponding to the largest singular values grow exponentially faster than the smaller ones. Gauthier Gidel et al. formalized this in Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks, proving that discrete gradient steps cause the network to learn the most important low-rank features of the data sequentially, one by one, effectively filtering out high-rank noise.

Network architecture further refines this structural bias:

The Tug-of-War Between Initialization and Regimes

The implicit bias of an optimizer is not a fixed law; it is highly sensitive to where the optimization path begins. The scale of initialization determines whether a model enters the "rich" (feature learning) regime or the "lazy" (kernel) regime.

Initialization Scale:
Small --------------------------------------------------------> Large
[Rich / Feature Learning Regime]               [Lazy / Kernel Regime]
- Weights change significantly                 - Weights barely move
- Learns sparse, low-rank structures           - Behaves like a fixed linear kernel
- Strong implicit bias                         - Weak implicit bias

When a model is initialized with tiny weights near zero, it must change its internal representations dramatically to fit the data. This allows the non-linear coupling between layers to take full effect, driving the model toward sparse or low-rank solutions.

Conversely, if the initialization scale is large, the model enters the lazy regime. Here, individual weights only need to move a microscopic distance to achieve zero training error, and the network behaves like a linear model fixed around its random initialization.

Blake Woodworth et al. mapped out this transition in Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy. They showed that the choice between a sparse $L_1$-norm bias and a dense $L_2$-norm bias is a delicate balance between initialization scale and training accuracy. If a model is initialized with large weights, it can only escape the lazy regime and reach the rich, sparse regime if it is trained to astronomical levels of accuracy (e.g., driving cross-entropy loss down to $10^{-100}$).

Hancheng Min et al. unified these insights in On the Explicit Role of Initialization on the Convergence and Implicit Bias of Overparametrized Linear Networks, showing how the initialization matrix explicitly dictates optimization speed and the resulting simplicity bias.

This relationship can be understood geometrically. Zhiyuan Li et al. proved in Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descent that running standard gradient descent on a reparameterized model (like a neural network) is mathematically equivalent to running mirror descent—an optimization algorithm that minimizes specific non-Euclidean regularizers depending on the geometry of the parameterization.

How Stochasticity and Optimizers Alter the Bias

Full-batch Gradient Descent (GD) and Stochastic Gradient Descent (SGD) do not always arrive at the same solutions. The noise introduced by mini-batch sampling provides an additional layer of implicit regularization.

Zihan Wang et al. uncovered a striking property of this noise in Implicit bias of SGD in $L_2$-regularized linear DNNs: One-way jumps from high to low rank. They showed that the stochasticity of SGD enables "one-way jumps" in the optimization path: the model can transition from complex, high-rank solutions to simpler, low-rank ones, but the noise prevents it from ever jumping back.

Similarly, Nikhil Ghosh et al. demonstrated in The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning that mini-batch SGD drives autoencoders to learn sparse, data-aligned features, whereas full-batch GD frequently gets trapped near its initialization, producing dense, uninformative representations.

However, modifying the optimization algorithm can also inadvertently damage these beneficial biases. Adaptive optimizers like AdaGrad and Adam scale their updates coordinate-wise based on historical gradients to speed up training.

Qian Qian et al. in The Implicit Bias of AdaGrad on Separable Data and Chenyang Zhang et al. in The Implicit Bias of Adam on Separable Data demonstrated that this coordinate-wise rescaling distorts the geometry of margin maximization. Instead of maximizing the clean $L_2$ margin, adaptive methods maximize a distorted margin that can over-index on noisy features, explaining why Adam sometimes generalizes worse than standard SGD on simple classification tasks.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_implicit_bias_b816d99b,
  title = {implicit bias},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/implicit-bias/rdr_b816d99be8a14724a18dfcd5f1381e52},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_implicit_bias_b816d99b_v1,
  title = {implicit bias},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/implicit-bias/rdr_b816d99be8a14724a18dfcd5f1381e52/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake