Implicit Bias of Gradient Descent on Linear Convolutional Networks

In plain words

When a network can fit the training data in many ways, gradient descent does not pick one at random. It drifts toward a particular fit, and which fit it drifts toward depends on how the network is written down, not only on the model's set of possible answers.

This paper studies networks with no nonlinearities, so the whole network computes one linear function. A fully connected stack of such layers can represent exactly the same functions as one layer, yet gradient descent on its weights always ends at the same kind of "widest-margin" separator, whatever the depth. A stack of convolutions does not behave that way. Gradient descent prefers separators that use few frequency components, and the more layers the network has, the more strongly it prefers that sparsity.

The point for an engineer: the architecture chooses an inductive bias even when the function class is unchanged, and it does so through the optimizer.

TL;DR

• Linear networks of depth L with exponential loss on separable data: gradient descent on the weights converges in direction. §3
• Fully connected: the limit is the hard-margin SVM direction for every depth. §3
• Full-width circular convolutions: the limit is a stationary point of a penalty on the Fourier coefficients, the l_{2/L} bridge penalty, so depth matters. §3
• Theory only. The source has no experiments, no datasets and no numerical results. §1–§6

Problem

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

Earlier work showed that gradient descent on a linear predictor directly converges in direction to the hard-margin SVM. §2, eq. 6 This paper asks what happens when the predictor is written as a product of parameters, a fully connected network or a convolutional network, and gradient descent acts on those parameters. The predictor class is unchanged in both cases: each architecture can realise every linear predictor on R^D. §2

The paper assumes that the iterates minimize the loss, converge in direction to a positive-margin separator, and have gradients that converge in direction. It does not prove these; it takes them as hypotheses. §3, assumptions

Method

Setup

Inputs x_n in R^D with labels y_n in {-1, +1}, n = 1..N. The network has parameters u = [u_l] and computes the linear predictor w = P(u), so that f(x) = <x, P(u)>. §2, eq. 4–5

• Fully connected, depth L: layer l has a dense matrix u_l, and P_full(u) is the product u_1 u_2 ... u_L. §2, eq. 1
• Convolutional, depth L: layers 1..L-1 are full-width circular convolutions with filters u_l in R^D, scaled by 1/sqrt(D). The output layer is a dense vector u_L in R^D. §2, eq. 2–3. The operation is a cross-correlation, not the textbook convolution. §2, footnote 1
• Depth counts all weight layers, so depth L has L-1 convolutional layers. §2, §1

The loss is the exponential loss, exp(-u y). The paper states its theory for exponential loss and says it expects the logistic loss to behave the same way. That extension is conjectured, not proved. §2, after eq. 7; §6

Training dynamics

Gradient descent on the parameters, with step sizes eta_t, is

u[t+1] = u[t] - eta_t * (Jacobian of P)^T * (gradient of the loss in w)  [§2, eq. 7]

The iterates induce predictors w[t] = P(u[t]). The question is the limit direction of w[t]. §2, §3

Convolutional networks in the Fourier domain

For full-width convolutions, a Fourier transform turns each circular convolution into an elementwise product. The Fourier transform of the predictor equals the elementwise product of the Fourier transforms of all L layers. §3, Lemma (fft) The Fourier transform is the unitary DFT with 1/sqrt(D) normalization and kernel exp(-2 pi i p d / D). §1 notation, §3

# Predictor of a depth-L full-width linear convolutional network  [§3, Lemma (fft)]
# Input:  filters, a list of L real vectors, each (D,)
# Output: predictor w, (D,) real

def conv_predictor(filters):
    # Start from the neutral element of elementwise multiplication
    response = ones(D)                             # (D,) complex
    for layer in filters:
        # Multiply in the Fourier coefficients of this layer  [§3, Lemma (fft)]
        response = response * fourier(layer)       # (D,) complex
    # Back to the input domain; the paper's P_conv also flips the output
    # vector, so match its convention before using this  [§2, eq. 3]
    return inverse_fourier(response)               # (D,) real

Results

The three main results all concern the limit direction of gradient descent on the parameters u.

1. Fully connected, any depth §3, Thm. 1. If the assumptions hold, the limit direction is the hard-margin SVM direction: the minimum l2-norm w subject to margin constraints y_n <x_n, w> >= 1. §3, eq. 8 Depth has no effect.
2. Convolutional, depth 2 §3, Thm. 2. The limit direction is the normalized minimizer of the l1-norm of the Fourier coefficients, subject to the same margin constraints. §3, eq. 9 Here the assumptions include one extra condition: the phases of the Fourier coefficients of w[t] converge coordinate by coordinate. §3, Thm. 2 condition (c)
3. Convolutional, any depth L §3, Thm. 2a. The limit direction is a scaling of a first-order stationary point of the problem: minimize the l_{2/L} quasi-norm of the Fourier coefficients, subject to the margins. §3, eq. 10 For L = 2 this is convex (p = 1). For L > 2 (p < 1) the problem is non-convex, so the paper claims a stationary point, not a global minimum. §3, text after eq. 10

Stationary points are defined through Clarke's subdifferential. For p < 1 the subdifferential is given in closed form. §3, eq. 11–13

The general mechanism is in §4. For a homogeneous polynomial parameterization P, gradient descent on u converges in direction to a stationary point of min ||u||_2^2 subject to the margins written through P(u). §4, Thm. 3, eq. 14 Full connection and full-width convolution are both special cases.

§5 computes the induced penalty on the predictor, R_P(w) = min over u with P(u) = w of ||u||_2^2. §5, eq. 15 The paper gives these closed forms:

• Fully connected: R(w) = L * ||w||_2^{2/L}, which is monotone in ||w||_2. §5, Lemma (fcn)
• Diagonal network: R(w) = L * ||w||_{2/L}^{2/L}. §5, Lemma (dn)
• Full-width convolutional: R(w) = L * ||ŵ||_{2/L}^{2/L}, where ŵ is the Fourier transform of w. §5, Lemma (cn)

The constants L and the power 2/L come from these lemmas. For the fully connected case the lemma is an equality; for the other two the paper states the penalty as a monotone function of the norm, which is what the margin problems need. §5

The paper also notes that the diagonal network P_diag(u) = diag(u_1)...diag(u_{L-1}) u_L has the same structure as the convolutional network in Fourier space. §3, after Lemma (fft); §5

Hyperparameters

The paper has no training hyperparameters. Its theorems are stated for any configuration that satisfies the conditions, so the table lists the conditions.

Results

No numerical results. The paper reports theorems and lemmas only. The table below lists its formal claims; each row is a theorem, not a measurement.

Stated scope: the paper says its results are for "almost all" separable data and initializations, under the three assumptions in §3, and that they characterize the limit direction, not the rate. §3, §6

Paper vs code

No official code.

The source has no code links, and the arXiv metadata has none. I searched in this order and found nothing by the authors:

• Paper and metadata: no repository link, no project page.
• GitHub repository search (WebFetch): "implicit bias linear convolutional networks", "implicit bias gradient descent" and "linear convolutional networks gradient descent bridge". The first and third returned no results; the second returned repositories by other people, none linked to an author.
• GitHub user lookup for one author name returned 404.

The authors are at TTI Chicago, USC and Technion, not at a GitHub organization, so no organization search applied. [author affiliations: arXiv metadata and LaTeX title block]

Pitfalls

• Depth convention. Depth L counts all weight layers, so a convolutional network of depth L has L-1 convolutional layers. Using "L convolutional layers" changes the exponent in l_{2/L}. §1, §2
• Convolution is cross-correlation. The layer uses u[k] * h[(d+k) mod D], not the textbook flipped kernel. The predictor P_conv flips the output vector. An implementation that uses a standard convolution will get a different predictor. §2, footnote 1, eq. 3
• Scaling. Each convolution carries a 1/sqrt(D) factor. The result is stated for this scaling; the paper says other conventions should behave similarly but does not prove it. §2, remark after eq. 3
• Phase assumption. Theorem 2 needs the phases of the Fourier coefficients to converge coordinate-wise. The paper derives this for coordinates where the limit is nonzero from the convergence of u[t], and assumes it for the rest. Treat it as an assumption, not a fact. §3, text before Thm. 2
• Stationary, not global. For L > 2 the penalty is non-convex, and the paper proves only stationarity. Do not read Theorem 2a as "the global minimum of the l_{2/L} problem". §3, text after eq. 10
• Sparsity claim. "Sparse in the frequency domain" is the paper's description of the l_{2/L} penalty, which the introduction calls sparsity-inducing and more aggressive with depth. No sparsity level is measured. §1, §3
• Initialization is not arbitrary. The proof uses the fact that initial spectra are nonzero almost surely. Zero initialization, or a symmetric initialization that leaves a coordinate at zero, is outside what the theorem covers. app. C; §3
• Step size. The convolutional theorem requires step sizes below a local Lipschitz constant that depends on the iterate. The paper gives no formula for it, so a fixed learning rate cannot be checked against the theorem. §3, Thm. 2
• Logistic loss. The text says the results should extend to logistic loss; that is a conjecture in the paper. §2, after eq. 7; §6
• Finite filters and nonlinearities. The bias for filters of width K < D, with zero padding, pooling, nonlinear activations, or multiple channels is not derived. The paper says it expects related behaviour and that width restriction "requires additional work". §6
• No rates. There are no iteration counts or convergence rates. "Gradient descent converges" is asymptotic and says nothing about how many steps are needed. §6

Lineage

• Builds on: Soudry et al. (2017), cited as \citet{soudry2017implicit} in the source, for the hard-margin result on a linear predictor trained by gradient descent. §2
• Builds on: Gunasekar et al. (2018), cited as \citet{gunasekar2018characterizing} in the source, for the steepest-descent framework and the gradient-direction lemma that the appendix paraphrases. §2, appendix preamble
• Compared against: the paper's own fully connected result, which it presents as the baseline for the convolutional result. §3
• Superseded by: not stated in the source.