PaperlayerView exact revision on arXiv

Source-linked AI summary

Implicit Bias of Gradient Descent on Linear Convolutional Networks

Suriya Gunasekar, Jason Lee, Daniel Soudry, Nathan Srebro

arXiv:1806.00468v2cs.LGstat.ML

TL;DR

The paper asks how gradient descent selects among equivalent linear predictors under different deep parameterizations. It analyzes fully connected and full-width convolutional linear networks, finding depth-independent hard-margin behavior for the former and depth-dependent frequency-domain sparsity for the latter.

  • Problem

    Over-parameterized linear models can represent the same predictors while optimization may select different global minima depending on parameterization.

  • Method

    The paper characterizes gradient descent's implicit bias for homogeneous parameterizations of linear predictors, including fully connected and full-width convolutional networks.

  • Results

    Fully connected networks converge to the hard-margin support-vector-machine solution regardless of depth, whereas depth-L convolutional networks favor frequency-domain sparsity related to the ||β̂||2/L bridge penalty.

  • Takeaways & Limitations

    Changing only the parameterization can radically change the classifier selected by gradient descent, with convolutional parameterization increasingly inducing frequency-domain sparsity as depth grows.

  • Takeaways & Limitations

    For L > 2, the associated bridge-penalty problem is non-convex, so the analysis guarantees convergence only to a first-order stationary point rather than a global minimum.

Abstract

from arXiv · show

We show that gradient descent on full-width linear convolutional networks of depth $L$ converges to a linear predictor related to the $\ell_{2/L}$ bridge penalty in the frequency domain. This is in contrast to linearly fully connected networks, where gradient descent converges to the hard margin linear support vector machine solution, regardless of depth.

1 Introduction

The paper studies how optimization algorithms and parameterizations select particular solutions among many global minima in over-parameterized linear models. It contrasts depth-independent hard-margin behavior in fully connected networks with depth-dependent frequency-domain sparsity in convolutional networks.

  • Motivation: Over-parameterized neural networks can have many global minima that fit the training data perfectly, yet optimization selects special solutions among them.These optimization-induced preferences are called implicit biases and can affect the learned model's generalization properties.
  • Motivation: Changing the optimization algorithm can change the implicit bias without changing the model, as coordinate descent yields a maximum ℓ1 margin instead of the hard-margin support-vector solution.The comparison is given for linearly separable linear logistic regression.
  • Motivation: Fully connected and convolutional linear networks can implement the same linear transformations, but gradient descent produces very different solutions across the two parameterizations.The paper therefore treats parameterization as a source of implicit bias, not merely model capacity.
  • Main result: For depth L fully connected networks with single output, gradient descent converges to the homogeneous hard-margin support-vector-machine solution regardless of depth.This matches direct gradient descent on the linear predictor.
  • Main result: For depth L convolutional networks, gradient descent favors frequency-domain-sparse separators and is related to minimizing the ||β̂||2/L bridge penalty under margin constraints.Here 2/L ≤ 1, and the sparsity-inducing effect becomes stronger as depth increases.
  • Scope: The analysis characterizes which global minimum gradient descent approaches while assuming suitable step sizes make the iterates asymptotically minimize the optimization objective.It does not address when gradient descent reaches a global minimum of the non-convex empirical loss.

2 Multi-layer Linear Networks

The paper formulates deep fully connected and convolutional architectures as parameterizations of linear predictors and studies gradient descent on separable classification objectives. Although both architectures can express the same predictors, their parameterizations can induce different limiting directions.

  • Network formulation: A feed-forward linear network maps x ∈ R^D to ⟨x, β_w⟩, where β_w is its effective linear predictor.The network parameters w determine the predictor through the architecture's parameterization.
  • Network formulation: An L-layer network is a composition of L linear maps, with layer outputs indexed from the input layer l = 0 to the output layer l = L.The intermediate representation at layer l is denoted h^l.
  • Architectures: Fully connected networks use densely connected matrix layers, whereas the convolutional architecture uses D-dimensional circular convolutions in each non-output layer.The output layer of the convolutional network is fully connected, and the filters are full dimensional.
  • Assumptions: The convolution operation uses circular convolution scaled by 1/D, while narrower filters or different padding may alter the implicit bias.The analysis restricts attention to full-width filters in sufficiently over-parameterized models.
  • Separable classification: The classification setup uses separable binary data and surrogate losses such as logistic or exponential loss, with the analysis focusing on exponential loss.For separable data, asymptotically minimizing the loss sends the predictor norm to infinity, motivating convergence in direction.
  • Architectures: Both architectures can realize any β ∈ R^D, so they define the same unconstrained class of linear predictors despite different parameterizations.The parameter-to-predictor mappings are denoted P_full and P_conv.
  • Implicit bias: Direct gradient descent on β converges in direction to the hard-margin support-vector-machine solution for linearly separable data.The paper uses this result as the baseline for studying alternative parameterizations.
  • Implicit bias: Gradient descent on parameterized networks asks which limit direction emerges as the parameter norm diverges, even though the predictor-space optimization has the same global minima.The paper emphasizes that equivalent optimization problems can yield different classifiers under different parameterizations.

3 Main Results

The paper characterizes gradient descent’s implicit bias in fully connected and convolutional linear networks. Fully connected depth does not change the hard-margin solution, whereas convolutional depth produces frequency-domain sparsity associated with a bridge penalty.

  • Overview: The main results characterize which linear predictor gradient descent approaches for multilayer fully connected and convolutional networks with linear activations.The induced predictor is β(t) = P(w(t)).
  • Fully connected networks: For fully connected networks, any depth yields the hard-margin support vector machine classifier, matching direct gradient descent on the linear predictor.This conclusion is stated for single-output networks under the theorem’s separability and convergence conditions.
  • Convolutional networks: Adding convolutional layers changes the implicit bias toward linear separators with frequency-domain sparsity.The comparison is with fully connected networks, whose bias is depth-independent.
  • Convolutional networks: For convolutional networks of any depth L, the normalized predictor approaches a scaling of a first-order stationary point associated with the ℓ_{2/L} bridge penalty.The bridge penalty is a norm at p = 1 and a quasi-norm when p < 1.
  • Convolutional networks: When L > 2, p = 2/L < 1 makes the optimization problem non-convex and intractable, so the analysis guarantees stationary-point convergence rather than global optimality.The stationary points are defined using sub-stationarity for nonsmooth, non-convex objectives.
  • Analysis strategy: Fourier-domain analysis shows that full-dimensional convolutional networks have equivalent dynamics to linear diagonal networks with complex-valued parameters.This representation simplifies the analysis of convolutional networks.

4 Understanding Gradient Descent in the Parameter Space

The paper separates implicit bias into parameter-space optimization and its induced predictor-space effect for homogeneous polynomial parameterizations. Under stated assumptions, gradient descent converges directionally to a scaled first-order stationary point, with important limits for non-convex or non-homogeneous settings.

  • Gradient descent’s implicit bias can be analyzed through parameter-space bias and its translation into the predictor β = P(w).
  • For homogeneous polynomial parameterizations, Theorem 4 links the limiting parameter direction to a positive scaling of a first-order stationary point.The theorem assumes asymptotic loss minimization, directional convergence to a positive-margin separator, and directional convergence of predictor gradients.
  • The proof uses convergence of predictor-space gradients toward a positive span of support vectors and derives KKT conditions for the explicitly regularized parameter problem.
  • When the parameterization is non-homogeneous, unnormalized margins lack significance and the stated first-order stationarity conditions need not hold.
  • For many cases including linear convolutional networks, the regularized parameter problem is non-convex and intractable, so global minimization is not guaranteed.
  • The induced predictor-space penalty is defined by minimizing the squared parameter norm over parameters representing the same predictor.

5 Understanding Gradient Descent in Predictor Space

The predictor-space penalty reveals how parameterization changes the learned linear predictor. Fully connected networks retain a depth-independent Euclidean-norm bias, whereas diagonal and full-width convolutional networks yield frequency-structured penalties.

  • Fully connected networks: For fully connected networks, the predictor-space penalty is monotone in the ℓ2 norm, making the resulting constrained solution independent of depth.
  • Fully connected networks: Gradient descent on fully connected networks converges in direction to the hard-margin support vector machine solution.
  • Diagonal networks: For depth-L diagonal networks, the induced penalty is monotone in ∥β∥_2/L.
  • Convolutional networks: For full-width linear convolutional networks, the induced penalty is monotone in the frequency-domain norm ∥bβ∥_2/L.

6 Discussion

The discussion concludes that convolutional parameterization changes implicit bias even when the model class remains the same, producing frequency-domain sparsity. The results are bounded by assumptions about convolution width, outputs, architecture, loss, and stationarity.

  • Full-width convolutional parameterization induces a radically different bias from fully connected parameterization despite implementing the same linear model class.
  • Gradient descent on the convolutional representation biases learned linear predictors toward sparsity in the frequency domain.
  • Scope: The analysis uses one-dimensional circular convolutions, with higher-dimensional extensions stated as direct and zero-padding extensions expected to require edge-effect analysis.
  • Scope: Practical bounded-width convolutions fall within the homogeneous framework, but their predictor-space penalty requires additional work to characterize.
  • Open problems: The paper studies single-output networks; implicit bias for multiple outputs requires further characterization.
  • Scope: The exact bias is not expected to carry over unchanged to larger networks with parallel filters, pooling, and nonlinear activations.
  • Technical limits: The generic characterization assumes homogeneous polynomial parameterizations and provides only first-order parameter-space stationarity, not predictor-space stationarity.
  • Future work: Further work includes extending results to additional losses, degenerate datasets, and exact convergence rates.

A Homogeneous Polynomial Parameterization: Proof of Theorem 4

The proof of Theorem 4 converts asymptotic gradient-descent behavior into KKT conditions for a norm-regularized problem. Homogeneity, positive-margin directional convergence, and support-vector gradient structure are the central ingredients.

  • Theorem 4 considers gradient descent for exponential loss under a homogeneous polynomial map from parameters w to linear predictors.
  • The proof assumes the iterates asymptotically minimize loss, converge directionally to a positive-margin separator, and have directionally convergent predictor gradients.
  • Homogeneity transfers directional convergence from parameters to predictors through the degree of the polynomial map.
  • KKT conditions: The proof constructs nonnegative multipliers supported on asymptotic support vectors to establish stationarity and complementary slackness.
  • KKT conditions: A positive rescaling of the limiting parameter vector satisfies primal feasibility by normalizing the minimum training margin to one.
  • Limit argument: The gradient-descent decomposition shows the Jacobian-gradient term dominates the residual term, yielding w∞ = γ∇wP(w∞)z∞ for γ > 0.
  • Homogeneity: Euler’s homogeneous function theorem relates the Jacobian of P to P itself and supports the limiting stationarity argument.

B Linear Fully Connected Networks: Proof of Theorem 1

For fully connected linear networks, gradient descent produces the same hard-margin SVM direction as direct linear-predictor optimization, regardless of depth, under the stated conditions.

  • Theorem 1: For any depth L, gradient descent on fully connected networks converges in predictor direction to the homogeneous hard-margin SVM solution.The theorem applies to almost all linearly separable datasets and initializations under bounded step sizes and exponential loss.
  • Proof strategy: The proof uses asymptotic loss minimization, positive-margin separation, and directional convergence of the predictor gradients to identify the limiting direction.These assumptions allow the limiting predictor to satisfy the maximum-margin optimality conditions.
  • Setup: The network predictor β(t) is the product of the layer matrices and therefore forms a homogeneous polynomial of degree L.This parameterization still represents linear predictors despite its multilayer structure.
  • KKT characterization: A positively scaled limit predictor satisfies the KKT conditions for the ℓ2 maximum-margin problem.The argument constructs compatible scalings for the predictor and dual variables and uses homogeneity to normalize the margin.
  • Stationarity: The layer-product stationarity relation connects the limiting parameter gradients to the predictor-gradient direction required by the SVM solution.For the fully connected product, the resulting predictor is proportional to the limiting negative gradient direction.

C Linear Convolutional Networks: Proof of Theorem 2–2a

The convolutional-network analysis transforms full-width circular convolutions into coordinatewise diagonal dynamics in the Fourier domain, preserving both representations and gradient-descent updates.

  • Representation equivalence: Full-width convolutional networks are equivalent in representation to complex-valued linear diagonal networks in the Fourier basis.This equivalence makes the convolutional analysis reducible to diagonal-network dynamics.
  • Proof mechanics: The proof derives the predictor representation by repeatedly applying the convolution–Fourier correspondence and the complex inner-product identities.These identities convert network outputs into products of frequency-domain layer coefficients.
  • Fourier representation: The discrete Fourier transform represents convolutional predictors as coordinatewise products of the transformed layer parameters.For β = Pconv(w), its Fourier coefficients satisfy bβ = bw1 ⊙ bw2 ⊙ ... ⊙ bwL.
  • Optimization reformulation: The convolutional empirical-loss minimization problem becomes an optimization over the corresponding diagonal parameterization in Fourier coordinates.The transformed parameters encode each frequency independently through Hadamard products.
  • Dynamics equivalence: Fourier transformation preserves the incremental gradient-descent update directions up to the corresponding Fourier transformations.Thus, the original convolutional iterates can be analyzed through gradient descent on the complex diagonal parameters.

C.1 Proof of Theorem 2–2a

Under the theorem’s convergence assumptions, gradient descent on depth-L convolutional networks approaches a normalized first-order stationary point of the frequency-domain ℓ2/L optimization problem.

  • Theorem 2a: For any depth L, the normalized convolutional predictor converges to a scaling of a first-order stationary point of the frequency-domain optimization problem.The result holds under the conditions of Theorem 2, including asymptotic loss minimization and directional convergence assumptions.
  • Proof strategy: The proof uses Fourier-domain gradient dynamics, complex phases, and magnitudes to establish stationarity of the limiting predictor.Layerwise magnitude products and phase alignment connect the parameter-space stationarity condition to the sub-differential conditions.
  • Frequency dynamics: For nonzero frequency components, the limiting layer magnitudes balance while their products determine the predictor magnitude.The two-layer argument establishes the key balancing behavior used in the general-depth analysis.

D Computing RP(β): Proofs of Lemmas in Section 5

The induced parameter-space complexity of linear networks can be computed through the minimum squared parameter norm required to realize a predictor, yielding depth-dependent penalties.

  • Induced regularizer: For a predictor β = P(w), RP(β) is the minimum squared parameter norm among all parameters realizing β.This induced regularizer links network parameterization to an optimization penalty in predictor space.
  • Diagonal networks: For depth-L diagonal networks, the minimum parameter norm equals L∥β∥2/L_2, a monotone transformation of the ℓ2/L bridge penalty.The minimizing construction distributes each coordinate’s magnitude evenly across layers.
  • Convolutional networks: For depth-L convolutional networks, the corresponding minimum norm equals L∥bβ∥2/L_2/L in the Fourier domain.The convolutional calculation adapts the diagonal-network argument to complex Fourier coefficients.
  • Proof construction: The convolutional minimizer matches the diagonal-network construction after transforming predictors and parameters into Fourier coordinates.Coordinatewise magnitude allocation and phase choices realize the target Fourier predictor with the stated norm.

E Background Results

The section presents a norm inequality and states conditions for applying the Stolz–Cesaro theorem.

  • 2 ≤ ∥b_w∥_2^2 ≤ L∥b_β∥_{2/L}^{2/L}.
  • The Stolz–Cesaro theorem assumes a strictly monotonic, diverging sequence {b_k}.
  • Under the stated conditions, lim_{k→∞} a_k/b_k exists and equals L.
Loading 1806.00468v2…