PaperlayerView exact revision on arXiv

Source-linked AI summary

A jamming transition from under- to over-parametrization affects loss landscape and generalization

Stefano Spigler, Mario Geiger, Stéphane d'Ascoli, Levent Sagun, Giulio Biroli, Matthieu Wyart

arXiv:1810.09665v5cs.LGcond-mat.dis-nnstat.ML

TL;DR

The paper asks how over-parametrization determines whether fully-connected networks can fit data and how this transition relates to generalization. It models hinge-loss training as constraint satisfaction and analyzes the resulting jamming transition. The transition separates finite-loss from zero-loss regimes, while generalization decreases, then rises to a cusp, and finally decreases slowly in the over-parametrized regime.

  • Problem

    Neural networks lack a general theory explaining the conditions for fitting data, optimization behavior, and how parameterization affects their loss landscapes and generalization.

  • Method

    The paper recasts hinge-loss minimization as a continuous constraint-satisfaction problem and studies a critical transition in the (N, P) parameter plane.

  • Results

    Generalization error decreases before the transition, increases to a cusp near it, and then decreases monotonically but slowly throughout the over-parametrized phase.

  • Takeaways & Limitations

    The jamming transition identifies the region of strongest over-fitting and the subsequent over-parametrized region where generalization continues improving slowly.

  • Takeaways & Limitations

    The conclusions rely on assumptions about effective parameters and the negative eigenspace of the Hessian-like matrix, including a conjectured finite negative-eigenvalue fraction for generic settings.

Abstract

from arXiv · show

We argue that in fully-connected networks a phase transition delimits the over- and under-parametrized regimes where fitting can or cannot be achieved. Under some general conditions, we show that this transition is sharp for the hinge loss. In the whole over-parametrized regime, poor minima of the loss are not encountered during training since the number of constraints to satisfy is too small to hamper minimization. Our findings support a link between this transition and the generalization properties of the network: as we increase the number of parameters of a given model, starting from an under-parametrized network, we observe that the generalization error displays three phases: (i) initial decay, (ii) increase until the transition point --- where it displays a cusp --- and (iii) slow decay toward a constant for the rest of the over-parametrized regime. Thereby we identify the region where the classical phenomenon of over-fitting takes place, and the region where the model keeps improving, in line with previous empirical observations for modern neural networks.

1. Introduction

The paper studies how parameter count shapes neural-network loss landscapes, fitting, and generalization. It frames a sharp jamming transition between regimes where training can or cannot reach zero loss, with a cusp in generalization near that transition.

  • 1. Introduction: The paper addresses the lack of a general theory explaining neural networks’ fitting conditions, optimization dynamics, and depth-dependent loss landscapes.These questions remain largely empirical despite major progress in network design and training.
  • 1. Introduction: Earlier glass analogies predicted trapping in high-loss minima, whereas studies of over-parametrized networks suggest connected level sets and many flat directions.These observations differ from the exponentially rugged landscapes associated with physical glasses.
  • 1.1. Jamming transition and supervised learning: The authors analyze jamming in the (N, P) plane, where N is network degrees of freedom and P is training-set size, using fully-connected ReLU networks on random data and MNIST.A critical line N⋆(P) separates zero-training-loss learning from finite-loss outcomes, although its exact location can depend on the dynamics.
  • 1.1. Jamming transition and supervised learning: Generalization error increases before jamming, forms a cusp at the transition, and decreases monotonically afterward in the over-parametrized phase.Early stopping removes the cusp, identifying the transition as the region where over-fitting is strongest.
  • 1. Introduction: The work connects this behavior to prior empirical studies of cusp-shaped test error and monotonic post-cusp decay under early stopping.Related work examined two-layer teacher–student networks, while later studies extended the phenomenon to other models and regression settings.

2. Theoretical framework

The framework models supervised learning as a jamming transition between under-parameterized networks with nonzero training loss and over-parameterized networks that can satisfy all constraints. It analyzes this transition through effective degrees of freedom, Hessian stability, and the discontinuous behavior of unsatisfied constraints.

  • Set-up: The network is treated as a fully connected architecture, with learning formulated as binary classification using a quadratic hinge loss.The hinge loss counts patterns violating classification or margin constraints as unsatisfied.
  • Effective parameters: Effective degrees of freedom Neff(W) can be smaller than the parameter count N because some parameter directions do not change the network output.Poor signal propagation can reduce Neff to 1, while linear activations impose dimension-dependent bounds.
  • Jamming transition: The jamming point N⋆(P) separates an under-parameterized phase with L > 0 from an over-parameterized phase with L = 0.Increasing N at fixed P leads to vanishing training loss at the transition.
  • Stability of minima: For smooth activations, Hessian stability constrains positive-loss minima because the positive-semidefinite term has rank at most N∆, leaving a kernel of dimension at least N − N∆.Intersecting this kernel with the negative eigenspace of the remaining Hessian term yields the condition N∆ ≥ N−.
  • Main theoretical results: Under the stated spectral assumptions, smooth networks have a transition satisfying N⋆(P) ≤ P/C0, with N∆/N jumping discontinuously to a value between C0 and 1.For ReLU, C0 = 1/2; cusps complicate the stability analysis but the transition remains sharp.

3. Location of the jamming transition

The jamming boundary N∗(P) is estimated numerically and separates parameter regimes where fully-connected networks can or cannot fit the training data. Its location depends strongly on data structure, while depth, input dimension, and loss function have little effect in this setup.

  • N∗ is estimated by decreasing network size until the final training loss becomes positive.
  • Changing input dimension, depth, or loss function has little effect on the transition.The comparison includes cross-entropy and hinge losses.
  • The transition separates a zero-training-loss phase from a phase ending in finite loss.
  • Real images require significantly fewer parameters than random data to fit, and N∗ grows more slowly with sample size.For P ≫ 1, N∗(P) could be sub-linear or approach a finite asymptote.
  • The constraint-to-parameter ratio N∆/N jumps discontinuously at the transition, with finite-size scatter near jamming.Plotting the ratio against loss removes the observed scatter.

4. Generalization at and beyond jamming

Generalization changes sharply around jamming: over-fitting is strongest at intermediate network sizes near the transition, while performance improves slowly beyond it. The transition produces a cusp in test error that remains visible after rescaling network size by N∗(P).

  • Over-fitting is weak at small and large N but becomes substantial at intermediate N.The gap between late-training and minimum test error measures over-fitting.
  • The final test-error curve develops a cusp at the jamming transition when N is rescaled by N∗(P).The comparison uses final test error and the smallest error reached at earlier training steps.
  • Beyond jamming, accuracy keeps improving as the number of parameters increases, although the improvement is quite slow.
  • The overall trends in Figure 4 qualitatively persist across other network depths.
  • Perceptrons also show a cusp, but their test error asymptotically increases with N rather than decreasing beyond the transition.

5. Conclusions

The paper interprets fitting in fully-connected networks through a jamming transition that separates under- and over-parametrized regimes. It links this transition to loss-landscape accessibility, the absence of poor finite-loss minima, and a three-phase pattern in generalization.

  • The hinge-loss minimization is recast as constraint satisfaction with continuous degrees of freedom.
  • Above the critical curve N∗(P), global minima become accessible and poor finite-loss local minima are not encountered during training.The stated mechanism is that too few constraints hamper minimization in the over-parametrized regime.
  • For smooth activations, the analysis predicts no bad minimum for N ≥ P/C0; for ReLU, the expected constant is C0 = 1/2.
  • For random data N∗(P) scales linearly with P, whereas for structured data it appears sub-linear.The paper identifies predicting the full transition curve as an open challenge.
  • Generalization decreases for N ≪ N∗, rises to a cusp near N ≈ N∗, then decreases slowly throughout the over-parametrized phase.

Appendix A. Network properties

The numerical analysis examines network properties predicted by the preceding theoretical treatment and provides numerical confirmation together with a more detailed characterization.

  • The authors analyze numerically the network properties used in the previous analysis.
  • The numerical study is intended to confirm the theoretical arguments and characterize the networks in greater depth.

Appendix A.1. Effective number of degrees of freedom

The paper defines an effective parameter dimension from local function and gradient variations, accounting for symmetries and inactive or poorly configured network components. For properly initialized constant-width fully connected networks, it finds Neff approximately equals N, with the main reduction caused by ReLU symmetries.

  • Sources of reduction: Inactive neurons, signal-blocking initialization, adversarial inputs, bottlenecks, and poor design can reduce Neff below N.If the network output is constant near the training data, Neff can collapse to one.
  • Definition: Neff is defined as the dimension of the manifold’s tangent space generated by varying network parameters near training points.The construction uses function and gradient expansions in neighborhoods of each training input.
  • Empirical result: For MNIST with L = 3 and 10 PCA components, Neff shows no noticeable reduction beyond one ReLU-induced symmetry per neuron.The same behavior was observed for random data.

Appendix A.2. sp(Hp) is symmetric for ReLu activation functions and random data

The appendix argues that random-label sign symmetry makes odd Hessian traces vanish for ReLU networks, under self-averaging assumptions. This yields a symmetric spectrum for Hp, with equal fractions of negative and positive eigenvalues.

  • Setup: Hp is constructed from label-weighted Hessians of the network function, and the appendix studies its spectrum at large N.The Hessian is taken with respect to network weights and uses the ReLU activation.
  • Assumptions: The argument assumes finite powers of Hp self-average and that sub-leading corrections to trace concentration can be neglected.The first assumption follows the expected concentration of a very large random matrix; the second is explicitly described as more difficult.
  • Conclusion: Odd traces of Hp vanish, implying a symmetric spectrum with equal fractions of negative and positive eigenvalues.The same symmetry is used for odd products of Hessian matrices.
  • Symmetry argument: Reversing the final-layer weights and all random labels leaves the loss unchanged and makes relevant odd-order Hessian contributions change sign.Terms involving the last layer occur an even number of times, so odd products acquire an overall sign reversal.

Appendix A.3. Density of pre-activations for ReLU activation functions

Pre-activation densities near the jamming transition contain a training-set-specific delta peak at zero, corresponding to network directions where the loss has cusps.

  • Pre-activation density: For L = 5 random-data networks just above jamming, pre-activation densities show a delta distribution at zero only on the training set.Previously unseen random data has an otherwise overlapping density without this peak.
  • Measured fractions: The zero pre-activation fraction is Nc ≈ 0.21N for L = 5 random data, ≈ 0.19N for MNIST, and ≈ 0.25N for L = 2 random data.These values represent directions in phase space where cusps are present in the loss function.

Appendix B.1. Random data

The random-data experiments locate the jamming transition by varying network width and training-set size, using fully connected networks with random spherical inputs and labels. The appendix documents training procedures, convergence checks, and measurements near the transition.

  • Setup: The dataset uses P random points on a d-dimensional hypersphere with labels yµ = ±1, and networks are fully connected with depth L and width h.The transition is identified by reducing h at fixed L until perfect classification is no longer reached within the selected training time.
  • Transition procedure: The transition point N* is estimated by starting from a sufficiently wide fitting network and decreasing width until classification fails within the chosen learning time.Weights and biases use PyTorch’s default uniform initialization with σ^2 = 1/fin.
  • Cross-entropy training: Cross-entropy training uses SGD with two learning rates over 10^6 total steps, batch size min(P/2, 1024), batch normalization, and no explicit regularization.Figure B1 checks that 10^6 steps are sufficient for convergence.
  • Hinge-loss training: Hinge-loss training uses orthogonal initialization, no batch normalization, ADAM for 2 · 10^6 steps, full-batch updates, and no explicit regularization.In section 3 experiments, the learning rate is divided by 10 every 250k steps.
  • Transition measurements: Near the transition, three architectures with L = 2, 3, and 5 and N ≈ 8000 are studied by varying P and minimizing for 10^7 steps.For the L = 3 architecture, 128 runs vary P from 21991 to 25918; the effective parameter count is adjusted for ReLU symmetries.

Appendix B.2. Real data

The appendix evaluates fully connected networks on PCA-reduced MNIST, using hinge loss and comparing training configurations across parameter counts and depths.

  • Architecture and task: The networks use cascades of fully connected layers with h neurons and a single scalar output for even-versus-odd classification.Labels are yµ = ±1, and the loss is always hinge loss.
  • Data and preprocessing: MNIST images are reduced to 10 principal components carrying the most variance before training.The reduction avoids concentrating most weights in the first layer when using the original 784-pixel input.
  • Experimental setup: Experiments vary depth, width, and parameter count, including depth 1, 3, and 5 networks trained for 2M steps.For selected parameter counts, width is decreased from a large value until the trained networks no longer reach zero loss.
  • Experimental setup: A depth-5, input-dimension-10 network with width 30 is trained for 3M steps while the parameter count varies from 31k to 68k.Both MNIST training and test sets are used.
  • Generalization comparison: Generalization experiments use depth 5 and input dimension 10, varying width from 1 to 3k at parameter counts of 10k, 20k, and 50k.Appendix Fig. B2 compares the resulting generalization behavior for depths L = 5 and L = 2.
Loading 1810.09665v5…