Implicit bias of gradient descent

Overview

Over-parameterized models have many training-loss minimizers, and the optimizer picks one of them. For a linear predictor on linearly separable data, the exponential or logistic loss has no finite minimizer, so the iterates diverge in norm and the question becomes which direction they take 1806.00468 §2.

In that separable-data setting, gradient descent converges in direction, under the paper's assumptions, and the limit direction is set by the parameterization rather than by the function class alone. Two linear models can represent the same predictors and still end in different directions 1806.00468 §2–§3.

A different linear setting gives a different kind of answer. A dense linear student trained on a teacher's soft labels, under gradient flow from zero, never leaves the span of its training inputs. With fewer examples than dimensions, its limit is the projection of the teacher onto that span 2105.13093 §4.1, Thm. 1. The loss there is cross-entropy against soft labels, not the exponential loss of the separable case 2105.13093 §3.

Outside linear models, the bias is less well mapped. Full-batch gradient descent on nonlinear networks with a fixed step size does not settle in the stable regime the classical analyses assume. Its top Hessian eigenvalue climbs to 2/η and then hovers there, so the step size fixes the sharpness of the region the iterates occupy 2103.00065 §3.2. The authors place this next to earlier work that describes the same instability as implicit regularization 2103.00065 §3.3. The paper does not measure which solutions generalize better.

Variants

The linear results come from two cards. The first covers linear networks with exponential loss on separable data, with several parameterizations of that setting. The second covers a dense linear student with soft labels. The nonlinear step-size result comes from a third card, in a different setting.

Fully connected linear network

Layers are dense matrices whose product is the predictor. The limit direction is the hard-margin SVM direction for every depth 1806.00468 §3, Thm. 1. Card: Implicit Bias of Gradient Descent on Linear Convolutional Networks.

Full-width linear convolutional network, depth 2

One circular convolution plus a dense output layer. The limit direction minimizes the l1 norm of the Fourier coefficients under the margin constraints 1806.00468 §3, Thm. 2. This result needs one extra assumption on the phases of the Fourier coefficients, which the paper states but does not prove 1806.00468 §3, Thm. 2 condition (c). Card: Implicit Bias of Gradient Descent on Linear Convolutional Networks.

Full-width linear convolutional network, depth L

The limit direction is a scaling of a first-order stationary point of the l_{2/L} quasi-norm of the Fourier coefficients 1806.00468 §3, Thm. 2a. For L > 2 the problem is non-convex, so the claim is stationarity, not a global minimum 1806.00468 §3. Card: Implicit Bias of Gradient Descent on Linear Convolutional Networks.

Diagonal network

Element-wise products of parameter vectors. The induced penalty is a l_{2/L}-type norm of the predictor itself, not of its Fourier transform 1806.00468 §5, Lemma (dn). Card: Implicit Bias of Gradient Descent on Linear Convolutional Networks.

General homogeneous parameterization

For any homogeneous polynomial parameterization P, gradient descent on the parameters converges in direction to a stationary point of the minimum l2-norm problem in parameter space 1806.00468 §4, Thm. 3. The architectures above are special cases. Card: Implicit Bias of Gradient Descent on Linear Convolutional Networks.

Dense linear student under gradient flow from zero

The teacher and the student are both linear classifiers. The student is trained on the teacher's sigmoid outputs with gradient flow, the infinitesimal-step limit of gradient descent, starting from zero 2105.13093 §3, §4.1. With at least as many transfer examples as input dimensions, the limit is the teacher's weight vector 2105.13093 Thm. 1. With fewer, it is the orthogonal projection of the teacher onto the span of the inputs, the closest point to the teacher that the updates can reach 2105.13093 §4.1, Thm. 1. The authors also report, on MNIST digits 0 and 1 with 100 transfer examples, that learners placed further from the gradient-descent solution have higher transfer risk. This is plotted, with no numbers in the text 2105.13093 §5.2, fig. 4. Card: Towards Understanding Knowledge Distillation.

Deep dense student, small non-zero initialization

With two or more layers, zero initialization is a stationary point, so the weights start small but non-zero. Under three conditions (a norm bound on the initial weights, an initial loss below the loss at zero, and balancedness between layers), the end-to-end weight vector approaches the same limit as the shallow student 2105.13093 §4.1, Thm. 2. Balancedness is only approximated by near-zero initialization, and the paper does not prove that approximation is enough 2105.13093 §4.1. Card: Towards Understanding Knowledge Distillation.

Step size sets the sharpness (nonlinear networks)

Full-batch gradient descent with a fixed step size η on nonlinear networks. The top Hessian eigenvalue rises to 2/η, then stays at or just above that value while the loss still falls over long windows 2103.00065 §3.2. The authors report this for fully connected, convolutional and batch-normalized networks on CIFAR-10 2103.00065 §4. Card: arXiv:2103.00065. The regime itself is covered on gradient-descent-stability.

When to use which

The rows from the linear-network card state what the theory implies, not what performs better in practice; that paper has no experiments 1806.00468 §1–§6. The distillation rows rest on the same kind of theory, and its experiments are author-reported and qualitative 2105.13093 §5. The last row rests on author-reported experiments 2103.00065 §4.

Implementation sketch

The paper has no code. This is the setting the theory describes: gradient descent on the factorized parameters, with the predictor recomputed from them. Check whether the direction of the predictor settles, not only its loss.

# Gradient descent on factorized linear parameters  [arxiv:1806.00468 §2, eq. 7]
# Input:  data (x_n, y_n) with labels in {-1, +1}, depth L, step sizes eta_t
# Output: parameters u, predictor w = P(u)

def train(data, L, steps):
    # Random initialization; the theorems hold for almost all initializations
    # and, for convolutions, need the initial spectra to be nonzero [§3, app. C]
    u = [random_init(D) for _ in range(L)]
    for t in range(steps):
        # Build the linear predictor the layers compute  [§2, eq. 1–3]
        w = P(u)
        # Exponential loss on the predictor, pulled back to every layer  [§2, eq. 7]
        g = grad_u(sum(exp(-y * dot(x, w)) for x, y in data), u)
        # Plain gradient step on each layer  [§2, eq. 7]
        u = [u_l - eta_t * g_l for u_l, g_l in zip(u, g)]
    # Track the direction of w over time; the claim is about its limit  [§3]
    return u, P(u)

The distillation card gives a closed-form target for a different linear setting: the projection of the teacher onto the input span, for fewer examples than dimensions 2105.13093 Thm. 1. It is stated for gradient flow, so a discrete check needs a small step and a tolerance.

Contradictions

No direct disagreement, because the cards study different settings. The linear-network paper's theorems name no particular step size and state only conditions on the steps (bounded for fully connected layers, below a local Lipschitz constant for convolutional ones) 1806.00468 §3, Thm. 1, Thm. 2. The nonlinear paper reports that, for fixed full-batch gradient descent, the step size sets the sharpness the iterates settle at 2103.00065 §3.2. Both can hold, but no paper here tests the two together, so the page does not resolve how they relate. The distillation paper's results are for gradient flow and say nothing about finite step sizes 2105.13093 §3.

The first and third linear results point the same way on depth. The fully connected result gives the same limit at every depth [arxiv:1806.00468 §3, Thm. 1], and the deep dense student reaches the shallow student's limit under its conditions 2105.13093 §4.1, Thm. 2. The settings differ (separable data with exponential loss, against soft labels with cross-entropy), so the agreement does not test either result. The linear-network paper's assumptions are hypotheses, not proofs, and logistic loss is a conjecture 1806.00468 §2, §3, §6.

Pitfalls

• Depth convention. Depth L counts all weight layers, so a convolutional network of depth L has L-1 convolutional layers. Counting L convolutional layers changes the exponent in l_{2/L} 1806.00468 §1, §2.
• Cross-correlation. The layer is a cross-correlation, not the textbook flipped convolution, and the output vector is flipped in P_conv. A standard convolution gives a different predictor 1806.00468 §2.
• Scaling. Each convolution carries a 1/sqrt(D) factor. The paper says other scalings should behave similarly but does not prove it 1806.00468 §2.
• Stationary, not global. For L > 2 the penalty is non-convex and only stationarity is shown 1806.00468 §3.
• Initialization. Zero or symmetric initializations that leave a spectral coordinate at zero are outside the theorem 1806.00468 app. C. For the dense student, zero start is covered for one layer, but a deep student needs small non-zero weights 2105.13093 §4.1.
• Step size. The convolutional theorem requires steps below a local Lipschitz constant. The paper gives no formula, so a fixed learning rate cannot be checked against it 1806.00468 §3.
• No rates. "Gradient descent converges" here is asymptotic and says nothing about how many steps are needed 1806.00468 §6.
• Linear results do not transfer. The theorems cover linear predictors. The nonlinear result is about sharpness under a fixed step size, a different quantity, and it is not a claim about max-margin or sparse solutions 1806.00468 §6 2103.00065 §4.
• Gradient flow, not descent, for the distillation result. Its theorems hold in the infinitesimal-step limit, and the paper does not analyse finite step sizes 2105.13093 §3.
• Projection only below the dimension. For n >= d the same setup returns the teacher itself, so the projection statement applies only when there are fewer examples than dimensions 2105.13093 Thm. 1.
• Exact soft labels. The distillation analysis assumes the teacher is exactly linear and its sigmoid outputs are the labels. Noisy labels, nonlinear teachers and a bias term are outside the stated theory 2105.13093 §3, §6.

Papers

• Implicit Bias of Gradient Descent on Linear Convolutional Networks: derives the limit directions for fully connected and full-width convolutional linear networks, and the induced penalties for several parameterizations. Theory only.
• Towards Understanding Knowledge Distillation, Phuong and Lampert: the limit of a dense linear student trained on soft labels under gradient flow, with a transfer-risk bound. Theory plus author-reported synthetic and MNIST experiments.
• arXiv:2103.00065, Cohen et al.: full-batch gradient descent on nonlinear networks drives sharpness to 2/η and keeps it there; author-reported experiments on CIFAR-10.