PaperlayerView exact revision on arXiv

Source-linked AI summary

Trainability and Accuracy of Neural Networks: An Interacting Particle System Approach

Grant M. Rotskoff, Eric Vanden-Eijnden

arXiv:1805.00915v3stat.MLcond-mat.stat-mechcs.LG

TL;DR

The paper addresses limited rigorous understanding of how neural-network training achieves accuracy and how approximation error scales with network size. It models training as an interacting particle system, establishing convergence results and an O(n^-1) approximation-error scaling, while analyzing SGD noise and training-parameter scaling.

  • Problem

    Universal Approximation Theorems do not explain how to optimize network parameters or how approximation error scales with network size after training.

  • Method

    The paper reinterprets network parameters as interacting particles and analyzes their empirical distribution using Law of Large Numbers and Central Limit Theorem results for GD and SGD.

  • Results

    O(n^-1) approximation error emerges as network width grows, with fluctuations of order O(n^-1/2) at finite times that can become O(n^-1) asymptotically.

  • Takeaways & Limitations

    The analysis provides a theoretical account of trainability and approximation quality, including guidance on scaling SGD time steps and batch sizes.

  • Takeaways & Limitations

    The results do not assure convergence in practice because suitable representing measures may be unknown and finite-n approximations must be learned.

Abstract

from arXiv · show

Neural networks, a central tool in machine learning, have demonstrated remarkable, high fidelity performance on image recognition and classification tasks. These successes evince an ability to accurately represent high dimensional functions, but rigorous results about the approximation error of neural networks after training are few. Here we establish conditions for global convergence of the standard optimization algorithm used in machine learning applications, stochastic gradient descent (SGD), and quantify the scaling of its error with the size of the network. This is done by reinterpreting SGD as the evolution of a particle system with interactions governed by a potential related to the objective or "loss" function used to train the network. We show that, when the number $n$ of units is large, the empirical distribution of the particles descends on a convex landscape towards the global minimum at a rate independent of $n$, with a resulting approximation error that universally scales as $O(n^{-1})$. These properties are established in the form of a Law of Large Numbers and a Central Limit Theorem for the empirical distribution. Our analysis also quantifies the scale and nature of the noise introduced by SGD and provides guidelines for the step size and batch size to use when training a neural network. We illustrate our findings on examples in which we train neural networks to learn the energy function of the continuous 3-spin model on the sphere. The approximation error scales as our analysis predicts in as high a dimension as $d=25$.

1. INTRODUCTION

The paper develops a particle-system analysis of neural-network training that addresses how common optimization algorithms achieve global convergence and how approximation error scales with network width. Its LLN and CLT results yield an n-independent convergence timescale and a universal O(n^-1) long-time approximation error, with implications for SGD noise, step size, and batch size.

  • Motivation: Neural-network approximation theory does not generally explain how to optimize parameters in practice or how post-training error scales with network size.Universal Approximation Theorems establish representational conditions but do not provide this training guidance.
  • Approach: The paper models network parameters as interacting particles whose loss function acts as an interaction potential, then analyzes their empirical distribution for large n.This reframes training as particle evolution and enables distribution-level analysis.
  • Main results: The empirical distribution follows gradient descent in the 2-Wasserstein metric on a convex energy landscape, with convergence toward equilibrium independent of n to leading order.The result is formulated through a Law of Large Numbers and dynamically realizes the Universal Approximation Theorem.
  • Main results: O(n^-1/2) finite-width fluctuations are controlled for finite times and, under certain conditions, heal to O(n^-1) as t → ∞.The fluctuation results rely on a Central Limit Theorem and imply universal O(n^-1) approximation-error scaling.
  • SGD: The analysis extends from idealized gradient descent to stochastic gradient descent and indicates how timestep and batch size should scale to achieve optimal error.The stochastic formulation also characterizes the noise introduced by SGD.
  • Numerical illustration: For the spherical continuous 3-spin model, neural networks accurately approximate the target through d = 25 with error scaling consistent with the theory.The examples use radial basis function and single hidden-layer sigmoid networks.

2. FUNCTIONAL FORMULATION OF THE LEARNING PROBLEM

The paper reformulates neural-network approximation through parameter distributions, turning the infinite-width problem into a convex functional problem under stated assumptions. This framework recovers universal approximation, quantifies finite-width error through limit theorems, and identifies practical limitations of realizing the distributional solution dynamically.

  • 2. FUNCTIONAL FORMULATION OF THE LEARNING PROBLEM: The infinite-width limit identifies representable functions and converts the limiting parameter-distribution objective into a convex problem.The finite-parameter loss may be non-convex, while the limiting functional for the parameter distribution is convex.
  • 2.1. Universal Approximation Theorem: Functions in F1 are represented by integrating neural units against finite-total-variation Radon measures on the feature space.The paper denotes the space of such measures by M( ˆD), with probability measures in M+( ˆD).
  • 2.1. Universal Approximation Theorem: Finite neural networks approximate the measure representation by sampling signed coefficients and features from its Jordan decomposition.The construction samples feature parameters from the normalized positive and negative measures and assigns coefficients according to their supports.
  • 2.1. Universal Approximation Theorem: The Law of Large Numbers gives the infinite-width representation, while the Central Limit Theorem quantifies its finite-n approximation error.The paper carries out the finite-width error calculation later in Section 3.4.
  • 2.1. Universal Approximation Theorem: Under closed-manifold, differentiability, and discriminating-unit assumptions, F1 is dense in L2(Ω,ν).The discriminating-unit condition ensures that only the zero function is orthogonal to all units, yielding density through the stated theorem.
  • 2.1. Universal Approximation Theorem: The universal approximation result is established by contradiction using Hahn–Banach and Riesz representation arguments.A nonzero orthogonal functional would produce a function violating the discriminating-unit assumption.
  • 2.1. Universal Approximation Theorem: When the target function is representable, it can be selected as the approximant in the universal approximation theorem.This is the role of Assumption 2.4, which states f ∈ F1.
  • 2.2. Convexification at distributional level: Although minimizers of the distributional objective can achieve zero loss under the assumptions, convergence is not automatically guaranteed in practice.The unknown representing measure must be approximated and learned dynamically, with the dynamics closing at the empirical-distribution level.

3. TRAINING BY GRADIENT DESCENT ON THE EXACT LOSS

The paper models gradient-descent training as an interacting particle system and studies its empirical parameter distribution in the large-width limit. The limiting dynamics follow Wasserstein gradient descent toward global minimizers, while finite-width fluctuations obey LLN and CLT behavior.

  • 3.1. Empirical distribution and limiting dynamics: Network parameters are treated as particles whose interactions are governed by the loss, allowing training to be analyzed through the empirical parameter distribution.The empirical distribution satisfies a nonlinear Liouville-type equation, whose large-n limit is a deterministic evolution.
  • 3.1. Empirical distribution and limiting dynamics: The limiting distribution evolves by gradient descent in the 2-Wasserstein metric on an energy landscape and preserves full support under the stated assumptions.The characteristic flow remains well-defined for finite times and preserves positivity and the projected support.
  • 3.2. Law of Large Numbers and global convergence: The empirical distribution satisfies a Law of Large Numbers, establishing convergence of finite-width network behavior to the deterministic limiting flow.The result is formalized in the LLN propositions for the empirical distribution and network approximation.
  • 3.2. Law of Large Numbers and global convergence: The limiting network function follows gradient descent on the loss and converges to the target function under the paper’s assumptions.The evolution can be expressed through a positive-semidefinite kernel and converges almost everywhere at long times.
  • 3.3. Long-time behavior—global convergence: Global convergence requires that the limiting measure converge to a probability measure, with additional support assumptions used in the long-time fluctuation results.The analysis does not exclude loss of mass at infinity; regularization is proposed as one way to preclude that scenario.
  • 3.4–3.5. Fluctuations and central limit behavior: O(n^-1/2) fluctuations persist at finite times, but under support and convergence conditions they become O(n^-1) or smaller as t →∞.The Central Limit Theorem characterizes finite-time fluctuations as Gaussian, while long-time dynamics exhibit self-healing.

4. TRAINING BY ONLINE STOCHASTIC GRADIENT DESCENT

The paper extends the particle-system analysis to online stochastic gradient descent, where finite batches introduce correlated noise. Appropriate scaling of batch size and time step preserves the deterministic limit and controls stochastic fluctuations.

  • 4.1. Online SGD and its stochastic differential equation: Online SGD replaces the exact data expectation with a freshly sampled batch of size P at every training step, introducing noise into the dynamics.The batch samples are redrawn independently from the data measure at each time step.
  • 4.1. Online SGD and its stochastic differential equation: The stochastic gradient is an unbiased estimator of the gradient-descent drift, so the discrete algorithm can be analyzed through an Euler–Maruyama approximation of an SDE.The SDE noise scale depends on the time step and batch size through σ.
  • 4.2. Dean’s equation for particles with correlated noise: SGD’s empirical-distribution equation contains additional drift and noise terms, with noise correlations between particles differing from standard Dean’s equation.The deterministic drift matches the gradient-descent equation, while the stochastic contribution is particle-correlated.
  • 4.3. Scaling the SGD noise: σ = a n^-2α with a > 0 and α > 0, achievable for example with P = O(n^2α), makes the additional stochastic terms vanish in the large-n limit.Under this scaling, the limiting empirical distribution solves the same deterministic equation as in gradient descent, up to discretization errors in Δt.
  • 4.4. Fluctuations in SGD: SGD fluctuations combine intrinsic particle-discreteness fluctuations of order O(n^-1/2) with noise-induced fluctuations of order O(n^-α).For α ≥ 1/2, noise is negligible relative to intrinsic fluctuations; for α ∈ (0,1/2), noise dominates at finite times.
  • 4.5. Long-time SGD fluctuations: The SGD noise self-quenches at long times under the convergence conditions, and its covariance tends to zero when the limiting support is full.The corresponding long-time fluctuation limit is zero under the stated support assumptions.

5. ILLUSTRATIVE EXAMPLE: 3-SPIN MODEL ON THE HIGH-DIMENSIONAL SPHERE

The paper tests its predictions on spherical 3-spin functions in dimensions up to 25, using Gaussian-kernel and sigmoid single-layer networks. The experiments show accurate representations and error scaling consistent with the theory.

  • The spherical 3-spin model supplies a difficult high-dimensional target because its number of critical points grows exponentially with dimension.
  • 5.1. Learning with Gaussian kernels.: In d = 5, a Gaussian-kernel network with n = 128 reproduces the target function’s level sets with good agreement.The training used n = 16, 32, 64, 128, and 256 with a time-discretized dynamics.
  • 5.1. Learning with Gaussian kernels.: The empirical loss in the d = 5 experiment decreases with n faster than n−1, consistent with the observed scaling.The loss was estimated using a batch of 10^6 uniformly sampled points on the sphere.
  • 5.2. Learning with single layer networks with sigmoid nonlinearity.: The sigmoid network experiments use d = 10 and d = 25, with SGD training followed by a batch-size increase near the end of optimization.The initial batch size is P = ⌊n/5⌋, followed by P = ⌊(n/5)^2⌋ during the partial quench.
  • 5.2. Learning with single layer networks with sigmoid nonlinearity.: The tested observables in d = 10 and d = 25 scale as n−1, matching the theoretical predictions.Figure 3 reports this scaling for the empirical loss and two additional observables.
  • 5.2. Learning with single layer networks with sigmoid nonlinearity.: For d = 25, n = 1024 yields a strong signal in one-dimensional slices, whereas smaller networks represent the target less faithfully.In d = 10, the representations capture the main target features with only small-scale deviations.

6. CONCLUDING REMARKS

The concluding analysis interprets network parameters as an interacting particle system, making the empirical distribution the object whose dynamics can be analyzed. It establishes dynamical approximation results, fluctuation scaling, and implications for SGD, while identifying finite-data error as outside the analysis.

  • Viewing parameters as particles and loss as an interaction potential enables statistical-physics tools to analyze trainability and approximation quality.
  • The empirical distribution descends on a quadratic loss landscape for large n, explaining trainability despite particle-level non-convexity.
  • A Central Limit Theorem specifies a universal approximation error for the neural-network representation.
  • The conclusions extend from gradient descent to stochastic gradient descent and indicate how batch size should scale with n given the time step.The batch-size adjustment can be made toward the end of training.
  • The analysis assumes a quadratic loss, although the results are stated to generalize to losses convex in f (n).
  • The study uses an infinite-data limit and therefore does not address error caused by a finite training dataset.

APPENDIX A. TRAINING AT FINITE (BUT SMALL) TEMPERATURE

The appendix introduces finite-temperature stochastic dynamics by adding regularization and noise to the particle equations. Under stated assumptions, the resulting system has a normalized equilibrium distribution and is ergodic.

  • Finite-temperature training is formulated by replacing the particle ODEs with stochastic differential equations containing regularization and additive noise.The noise amplitude is controlled by the inverse-temperature parameter β.
  • The regularizing distribution must have a continuously differentiable density with full support on the parameter domain.
  • The stochastic dynamics are overdamped Langevin equations associated with an energy equal to the original energy plus a regularizing term.
  • The assumptions ensure a normalized equilibrium density and ergodicity for every β > 0.

A.1. Dean’s equation.

Dean’s equation describes the empirical distribution’s stochastic evolution and clarifies which perturbations affect its mean-field and fluctuation regimes. The appendix focuses on long-time ergodic behavior and the scaling of diffusive, regularizing, and noise terms.

  • Applying Itô’s formula to the empirical distribution yields drift terms closed in terms of the empirical measure and separate noise terms.
  • Dean’s equation is a formal stochastic partial differential equation whose white-noise term represents the empirical-distribution noise.The equation is useful for analyzing the properties of the empirical measure despite difficulties giving the noise term a precise meaning.
  • When α = 0, diffusive and regularizing terms affect the mean-field limit while noise terms remain higher order.
  • In the α = 0 regime, the limiting fixed point can differ from the target through a correction proportional to β−1.
  • For α = 1, diffusive, regularizing, and noise terms all enter as O(n−1) perturbations, alongside finite-n discretization errors.
  • Adding noise guarantees ergodicity, so long-time analysis can focus on equilibrium fluctuations after memory of initial conditions is lost.

A.2. Multiple-scale expansion.

A two-timescale expansion separates the O(1) mean evolution from O(n^-1) fluctuations, using τ = t/n to analyze long-time behavior. The leading equation retains the same structure as the original dynamics and preserves the established finite-temperature conclusions.

  • Multiple-scale expansion: O(n^-1) fluctuations are incorporated through the expansion t = µt,τ + n^-1ωt,τ + o(n^-1), with τ = t/n.The rescaled time captures dynamics on O(n) timescales.
  • Multiple-scale expansion: τ = t/n provides the long-timescale variable needed to determine the mean behavior and guarantee solvability of the fluctuation equation.
  • Multiple-scale expansion: Collecting powers of n^-1 yields separate equations at orders O(1) and O(n^-1).
  • Multiple-scale expansion: The O(1) equation is identical to the earlier mean-field equation, so the finite-temperature results, including Proposition 3.5, continue to apply.

A.3. Law of Large Numbers at finite temperature.

The mean evolves on rescaled time τ = t/n toward stationary points of the leading finite-temperature equation.

  • Law of Large Numbers at finite temperature: µt,τ converges as t →∞ to a stationary point µτ of the leading equation on the rescaled time τ = t/n.

A.4. Global convergence on O(n) timescales.

On O(n) timescales, diffusion enforces positive density and removes the support assumption, while the strictly convex constrained energy selects global minimizers. Low-temperature convergence can require intermediate timescales beyond O(n).

  • A.4. Global convergence on O(n) timescales: µτ > 0 almost everywhere on D because the diffusive term β^-1∆µτ is present, implying the support condition and V(θ,[µτ]) = 0.
  • A.4. Global convergence on O(n) timescales: Strict convexity makes the stable fixed points of the Wasserstein gradient flow the minimizers of the constrained energy.
  • A.4. Global convergence on O(n) timescales: The empirical distribution converges toward the minimizer µ* under the stated condition bn/n →∞ as n →∞.
  • A.4. Global convergence on O(n) timescales: The minimizer satisfies finite relative entropy and full support, suppµ* = D.
  • A.4. Global convergence on O(n) timescales: µ* is independent of β because the factor β^-1 can be removed from the minimization objective.
  • A.4. Global convergence on O(n) timescales: At low temperature, convergence may be slower when the initial condition fails the support condition, occurring on timescales intermediate between O(1) and O(n).

A.5. Central Limit Theorem at finite temperature.

After the mean reaches the constrained minimizer, fluctuations are governed by a linear stochastic equation and become Gaussian. Their covariance determines the leading O(n^-1) approximation error, with zero-temperature quenching eliminating the long-time fluctuations.

  • A.5. Central Limit Theorem at finite temperature: Once µt has converged to µ*, the remaining fluctuation dynamics can be analyzed around the minimizer satisfying V(θ,[µ*]) = 0.
  • A.5. Central Limit Theorem at finite temperature: The fluctuation SPDE defines a Gaussian process because its drift is linear and its noise is additive.
  • A.5. Central Limit Theorem at finite temperature: The Gaussian fluctuation process gt determines the error in f(n)t at order O(n^-1).
  • A.5. Central Limit Theorem at finite temperature: The fluctuation equation can be reduced to a closed equation for gt using the kernel M([µ],x,x′).
  • A.5. Central Limit Theorem at finite temperature: At finite temperature, gt is a stationary Gaussian process whose mean and covariance are specified by the stated relations.
  • A.5. Central Limit Theorem at finite temperature: Quenching β →∞ yields gt → 0 as t →∞, matching the zero-temperature limit as ξ → 1.
Loading 1805.00915v3…