Source-linked AI summary
In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
Behnam Neyshabur, Ryota Tomioka, Nathan Srebro
TL;DR
The paper asks what capacity control enables generalization when network size does not explain the behavior of deep networks. It combines experiments with a matrix-factorization analogy to study implicit regularization, finding evidence that optimization favors low-complexity, potentially low-norm solutions. The authors note that the hidden notion of complexity remains unidentified.
Problem
Learning requires capacity control for generalization, but experiments suggest network size does not explain how feed-forward networks avoid overfitting.
Method
The paper experimentally studies increasingly wide single-hidden-layer networks and interprets the results through matrix factorization and dimensionality-versus-norm control.
Results
Test error continues decreasing after zero training error on standard and five-percent-noisy data, while explicit weight decay only slightly improves generalization.
Takeaways & Limitations
The findings suggest implicit regularization, possibly toward low-norm models, is a central inductive bias in deep-network learning.
Takeaways & Limitations
The experiments do not identify the hidden notion of complexity that optimization selects.
Abstract
from arXiv · showhide
We present experiments demonstrating that some other form of capacity control, different from network size, plays a central role in learning multilayer feed-forward networks. We argue, partially through analogy to matrix factorization, that this is an inductive bias that can help shed light on deep learning.
1 INTRODUCTION
Learning requires an inductive bias that controls capacity while retaining an expressive, computationally tractable hypothesis class. Experiments suggest network size is not the operative capacity control, motivating implicit regularization and a norm-based perspective.
- Inductive bias controls predictor capacity and supports generalization by restricting or encouraging simple predictors.Learning success depends on the expressiveness of the resulting simple-predictor class, its induced capacity, and the computational cost of fitting it.
- For feed-forward networks, capacity is conventionally associated with the number of weights in a fixed architecture.This view justifies networks when realistic functions can be represented by not-too-large architectures.
- Even small feed-forward networks can be computationally intractable to learn efficiently, including when the target is exactly representable by such a network.The cited hardness results motivate looking beyond straightforward network-size control.
- The paper begins by revisiting network size as the presumed capacity control in order to clarify what governs learning.
- Experiments with increasingly wide single-hidden-layer networks indicate that size does not act as the relevant capacity-control parameter.The authors infer that another, implicit form of capacity control may be the inductive bias in deep learning.
- The proposed perspective draws on matrix factorization to contrast dimensionality control with norm control.The paper further connects implicit ℓ2 weight decay in an infinite two-layer network to a convex neural net with infinite width and ℓ1 top-layer regularization.
2 NETWORK SIZE AND GENERALIZATION
Across standard, censored, and noisy datasets, increasing network size beyond zero training error does not produce the expected overfitting. The experiments instead motivate implicit low-complexity regularization as an explanation for continued generalization.
- Network setup: Two-layer networks use d real-valued inputs, H rectified linear hidden units, and k outputs, with weights learned by minimizing a truncated soft-max cross-entropy loss.The total number of weights is H(d + k).
- Expected size effect: The classic approximation-estimation tradeoff predicts that test error should eventually rise as increasing size weakens capacity control.
- Network size and generalization: For MNIST and CIFAR-10, test error continues decreasing after networks become large enough to achieve zero training error, even beyond the number of training examples.For MNIST, 32 hidden units suffice for zero training error, yet adding units still lowers test error.
- Experimental setup: The experiments use stochastic gradient descent with momentum and diminishing step sizes, without explicit regularization, on downsampled MNIST and CIFAR-10.Figure 1 uses training sets of 50000 examples for MNIST and 40000 for CIFAR-10, with validation sets of size 10000.
- Censored data: Censored datasets make approximation error zero once networks reach the small teacher size, yet test error continues decreasing after zero training error.The censored labels are generated from networks with H0 = 4 on MNIST and H0 = 16 on CIFAR-10.
- Noisy data: With five percent random label noise, test error still continues decreasing as network size grows beyond that required for zero training error, without significant overfitting.
- Implicit regularization: The authors propose that optimization implicitly selects a low-complexity global minimum rather than an arbitrary interpolating solution.They report similar behavior with batch conjugate gradient descent and explicitly exclude penalties, dropout, weight decay, and one-pass stochastic methods from the baseline setup.
- Explicit regularization: Explicit weight decay slightly improves generalization, but increasing network size continues to help.
3 A MATRIX FACTORIZATION ANALOGY
The matrix-factorization analogy suggests that norm control, rather than dimensionality or network size, can provide a more tractable and realistic inductive bias. This perspective motivates interpreting deep-network learning as implicitly favoring low-norm models.
- Matrix factorization and rank: With linear activations, limiting hidden units constrains the rank of W, creating a low-rank inductive bias that is computationally difficult to optimize.The factorization is W = VU^⊤, so hidden-layer dimensionality corresponds directly to factorization rank.
- Matrix factorization and norms: Constraining factor norms instead yields trace-norm or other norm regularizers without fixing the inner dimensionality.Frobenius-norm constraints on U and V correspond to trace-norm regularization.
- Optimization: Unlike rank constraints, trace-norm factorization is convex and can lead to tractable learning, with sufficiently high-dimensional local searches converging to global minima.The low-rank setting instead has abundant local minima, whereas norm-regularized factorization can retain global optimization guarantees.
- Inductive bias: Low-norm factorizations support generalization and correspond to factor models with many factors of limited overall influence.The passages also report empirical evidence that low-norm factorization can be more appropriate than low-rank modeling.
- Implications for deep learning: The experiments are interpreted as evidence that optimization may implicitly favor small-norm representations, potentially accounting for both generalization and tractable local search.This interpretation replaces small-unit representations with small-overall-norm representations as the relevant explanation.
- Infinite-dimensional perspective: Under this interpretation, infinite-sized bounded-norm networks are the conceptual target, while finite networks approximate them for computational reasons rather than statistical capacity control.Increasing allowed dimensionality can improve generalization by better approximating the infinite model.
4 INFINITE SIZE, BOUNDED NORM NETWORKS
The paper develops infinite-size, bounded-norm network formulations and connects global ℓ2 weight decay to convex neural networks with top-layer ℓ1 regularization. With sufficiently many hidden units, finite and infinite formulations become equivalent.
- Convex neural networks: Global ℓ2 regularization over network weights is shown to be equivalent to a convex neural network with ℓ1 regularization on the top layer.The convex neural network has an infinite hidden layer and differs from infinite networks using ℓ2 regularization.
- Scope: The paper’s aim is to explain the behavior of neural networks rather than reproduce deep-model performance with a known shallow model.This distinguishes the proposed convex-network connection from performance-matching approaches.
- Finite-network equivalence: For finite two-layer ReLU networks, ℓ2 regularization on both layers is equivalent to unit-norm constraints on hidden weights and ℓ1 regularization on the output weights.Rescaling preserves the input-output mapping because ReLU is piecewise linear and its active piece is invariant under weight rescaling.
- Convex neural networks: Convex neural networks represent predictions using measures over a fixed library of normalized hidden weight vectors, with complexity measured by the total positive and negative measure.For a finite library, this reduces to ℓ1 regularization on the second layer.
- Finite support: Even with an infinite continuous hidden-unit library, an optimum exists as a discrete measure supported on at most n + 1 units.Thus the infinite formulation admits an equivalent finite-support optimum.
- Infinite size and bounded norm: The infinite formulation removes any explicit limit on the number of hidden units and instead selects units under an ℓ1-norm constraint.When H is sufficiently large, the finite and infinite formulations are equivalent.
- Equivalence and implicit regularization: Learning and selecting become equivalent when the number of hidden units is sufficiently large, supporting ℓ1 regularization as an alternative view of ℓ2 or implicit regularization.The stated condition for the weight-decay equivalence is H > n.
- Multiple outputs: The equivalence extends to multiple outputs, replacing scalar ℓ1 regularization with group lasso; for linear activations, this corresponds to the trace norm.The group-lasso regularizer is expressed as a sum of output-unit norms.
APPENDIX
The appendix formalizes hardness results for learning feed-forward ReLU networks, showing that efficient learning is impossible under cryptographic assumptions even when labels are perfectly represented by small networks. The proof reduces intersections of homogeneous halfspaces to shallow networks and extends the barrier beyond small-network fitting to larger representations and agnostic learning.
- Formal learning question: The appendix asks whether polynomial samples and computation can learn functions perfectly represented by H-unit ReLU networks.The target distribution is over binary inputs and labels, and the learner receives i.i.d. data.
- Hardness theorem: The theorem rules out any algorithm satisfying these learning conditions under the cryptographic assumptions of Daniely et al. (2014).The impossibility applies to the stated polynomial-time, polynomial-sample learning setup.
- Hardness theorem: Even a single hidden layer with any super-constant number of hidden units, such as log(D), can represent perfectly predictive labels without making learning efficiently possible.The theorem therefore applies despite exact realizability by a shallow network.
- Reduction: Intersections of k homogeneous halfspaces can be realized with H = 2k ReLU hidden units, linking halfspace-learning hardness to shallow neural-network hardness.The construction uses two hidden units per halfspace and produces a unit-margin realization.
- Reduction: The reduction uses integer inputs and weights so each clipped-ReLU difference is zero or one, thereby realizing the intersection of the halfspaces with unit margin.This establishes the relevant halfspace-intersection hypothesis class as a subset of the neural-network hypothesis class.
- Implications: The result extends beyond NP-hardness of fitting small networks: larger polynomial-size representations do not ensure tractable learning, and exact-realizability hardness also rules out low-error agnostic learning.The restriction applies regardless of whether the learner uses larger networks, mixtures, or trees over networks.