Source-linked AI summary
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant
TL;DR
The paper asks how SGD can select simple, generalizing solutions among many zero-error fits. It analyzes SGD with independent label noise through an implicit regularizer and finds that, across several settings, the dynamics favor simple models after reaching zero training error.
Problem
The paper addresses why overparameterized networks trained by SGD can generalize despite fitting arbitrary training labels and having many zero-error solutions.
Method
The paper characterizes noisy-SGD dynamics near zero-training-error parameters using an implicit regularizer based on summed squared parameter-gradient norms, applicable across network structures.
Results
The characterization identifies attractive zero-error fixed points with local minima of the regularizer and explains simple solutions in matrix sensing, one-dimensional ReLU interpolation, and single-point sigmoid or tanh networks.
Takeaways & Limitations
Noisy SGD first reaches the zero-training-error manifold and then favors simpler models by reducing the implicit regularizer within that manifold.
Takeaways & Limitations
The paper leaves extensions to other stochasticity, deeper ReLU networks, and settings beyond one-dimensional data or single-point sigmoid and tanh tasks for future work.
Abstract
from arXiv · showhide
We consider networks, trained via stochastic gradient descent to minimize $\ell_2$ loss, with the training labels perturbed by independent noise at each iteration. We characterize the behavior of the training dynamics near any parameter vector that achieves zero training error, in terms of an implicit regularization term corresponding to the sum over the data points, of the squared $\ell_2$ norm of the gradient of the model with respect to the parameter vector, evaluated at each data point. This holds for networks of any connectivity, width, depth, and choice of activation function. We interpret this implicit regularization term for three simple settings: matrix sensing, two layer ReLU networks trained on one-dimensional data, and two layer networks with sigmoid activations trained on a single datapoint. For these settings, we show why this new and general implicit regularization effect drives the networks towards "simple" models.
1 Introduction
The paper studies why noisy SGD can select simple zero-error networks, introducing an implicit regularizer that characterizes attractive fixed points and applying it across several model settings.
- The paper motivates a rigorous account of why overparameterized networks trained by SGD can generalize despite fitting arbitrary labels.
- Noisy SGD perturbs each training label independently at every update, a setting that reliably produces simple models unlike ordinary SGD in small-data regimes.
- Zero-training-error attractive fixed points occur exactly at local minima of an implicit regularizer restricted to the zero-error manifold.
- The regularizer is proportional to the sum over data points of the squared parameter-gradient norm of the model, and noisy SGD can be viewed as optimizing it after reaching zero training error.
- The framework explains simple solutions in matrix sensing, one-dimensional two-layer ReLU networks, and single-point sigmoid or tanh networks.
- In matrix sensing, the regularizer tends toward minimum-rank solutions; in one-dimensional ReLU interpolation, it favors the minimum necessary convexity changes.
- For a single labeled point, stable noisy-SGD parameters use only a restricted pattern of hidden-unit outputs, showing that arbitrarily wide networks need not exploit their full expressive capacity.
- The analysis remains limited in scope: extensions to other stochasticity, deeper ReLU networks, and dimensions beyond one are identified as future directions.
2 Formal statement of general characterization
Theorem 1 characterizes which zero-training-error parameters remain stable under noisy-label SGD by whether the implicit regularizer has zero gradient along the zero-error manifold. Nonzero gradient directions make such parameters repellent, while zero gradients make them non-repellent with high probability over the stated time window.
- General characterization: The implicit regularizer sums the squared parameter-gradient norms of the model predictions across training points and applies to arbitrary network width, depth, and smooth activation functions.It provides the criterion used to analyze noisy-label SGD near zero-training-error solutions.
- Repellent parameters: A zero-training-error parameter is repellent when the implicit regularizer has a nonzero gradient in a zero-error-manifold direction.The dynamics move away and decrease the implicit regularizer with probability 1 − exp(−1/poly(η)).
- Formal definitions: The characterization is formalized by comparing repulsion from, and persistence near, zero-training-error parameters under sufficiently small learning rates.Definition 1 describes strong repulsion, while Definition 2 bounds the distance from a non-repellent point through t ≤ η^-1.6.
- Formal definitions: The framework defines strongly repellent points through a substantial decrease in the implicit regularizer over t = η^-1.6 steps.The decrease is cη^0.4 + o(η^0.4) for a constant c > 0.
- Non-repellent parameters: A zero-training-error parameter is non-repellent when the implicit regularizer has zero gradient along directions tangent to the local zero-error manifold.The dynamics remain near such a parameter with high probability for the time horizon in Definition 2.
3 Intuition of the implicit regularizer, via an Ornstein-Uhlenbeck like analysis
The analysis models noisy-label SGD as an Ornstein-Uhlenbeck-like process whose mean reversion and stationary fluctuations induce optimization of an implicit regularizer after training error reaches zero. The regularizer is the summed squared parameter-gradient norm across training points, and its dynamics mainly act along directions without linear damping.
- Diagonalized dynamics: Directions with γ_j > 0 decay exponentially toward zero, while directions with γ_j = 0 lack this restoring force.The decay time constant in direction j is 1/(2ηγ_j).
- Ornstein-Uhlenbeck intuition: Noisy-label SGD combines update noise with exponential mean reversion, producing an Ornstein-Uhlenbeck-like process in parameter space.The mean-reversion strength is controlled by the eigenvalues γ_j of the expected gradient Gram matrix.
- Implicit regularization: The implicit regularizer is the sum over training points of the squared norm of the model gradient with respect to parameters.In the paper’s notation, this quantity is represented through the gradient terms appearing in the higher-order update.
- Implicit regularization: After the noisy dynamics equilibrate, the higher-order update term behaves in expectation like gradient descent on the implicit regularizer at a learning rate slower by an additional factor of η.The Ornstein-Uhlenbeck intuition yields uncorrelated coordinates with variance proportional to η, producing the regularizer’s gradient.
- Over-parameterized networks: Because the gradient Gram matrix has rank at most the number of datapoints, over-parameterized networks generally contain many undamped directions where regularizer-driven motion can accumulate.The regularizer therefore acts primarily within the γ_j = 0 subspace once training error is zero.
A Proof of Theorem 1
The proof analyzes noisy-label SGD near a zero-training-error parameter by expanding its update and separating mean-reverting, martingale-noise, and higher-order error terms. Concentration bounds then control the stochastic contributions over the relevant time scales.
- Setup: The proof studies SGD near a parameter vector with zero training error, translated to the origin for a third-order expansion.The analysis assumes bounded derivatives and treats the zero-error point as the expansion center.
- Stable directions: For directions with γ_j > 0, bootstrapping shows contraction toward a scale near η^1/2 under a boundedness assumption.Lemma 4 gives |θ_j| ≤ ∥θ(0)∥e^−Ω(ηT) + η^1/2−ϵ with probability at least 1 − exp(−poly(1/η)).
- Update decomposition: The parameter update is decomposed into deterministic contraction, a mean-zero stochastic term, and a higher-order deterministic error.The stochastic term is bounded by O(η), while the error term depends on powers of the parameter norm.
- Concentration: The accumulated stochastic contribution is controlled by representing it as a martingale and applying an Azuma-Hoeffding tail bound.The resulting bound gives deviations of order η^1/2 with suitably chosen parameters.
A.1 Analysis of concentration of the time average of θjθk in the γj > 0 directions
This section establishes concentration of time-averaged coordinate products in directions with positive mean reversion. It uses second-moment updates, batching over intervals longer than the mean-reversion time, and martingale concentration.
- Second-moment dynamics: For directions with γ_j + γ_k > 0, the coordinate product θ_jθ_k evolves through mean reversion plus noise and bounded error terms.The mean-reversion factor is approximately 1 − 2η(γ_j + γ_k), with a modified factor for diagonal second moments.
- Noise contribution: The stochastic label-noise contribution has zero mean except for the variance term that injects diagonal second-moment energy.For j = k, the expected noise contribution is proportional to η^2 Var[e_i]γ_j; for j ≠ k, it is zero.
- Batched concentration: The proof groups updates into batches longer than the mean-reversion time so martingale differences remain sufficiently small for concentration.The batch size satisfies S ≫ 1/η^(1+ϵ), allowing the dynamics to forget earlier parameter values.
- Martingale analysis: Conditional expectations become insensitive to earlier parameter values after roughly 1/η^(1+ϵ) updates when γ_j + γ_k > 0.This weak dependence controls the effect of revealing one batch in the Doob martingale.
- Concentration result: The time-averaged covariance concentrates around a noise-determined value, with cross terms vanishing when at least one direction has positive γ.The proof concludes with estimates of the form η Var[e_i] plus lower-order terms for diagonal moments.
A.2 Proof of Theorem 1
The theorem proof combines the positive-γ concentration result with an induction over time to control all parameter directions. Damped directions remain small, while γ_j = 0 directions accumulate a systematic drift driven by label-noise variance.
- Undamped directions: Directions with γ_j = 0 have no linear mean reversion, so their evolution must be analyzed using the concentrated covariance estimates from the previous lemma.This separates the undamped coordinates from the directions already controlled by Lemma 4.
- Inductive control: An induction over time intervals shows that all coordinates remain bounded by η^0.4−ϵ through the relevant polynomial time horizon.The argument uses martingale concentration and the positive-γ bounds at each induction step.
- Damped directions: For positive-γ directions, the proof preserves the tighter η^1/2−ϵ bound while extending control across successive time intervals.The tighter bound follows from Lemma 4 once the global parameter norm remains sufficiently small.
- Conclusion: The resulting bounds complete the theorem’s characterization of stable behavior near zero-training-error parameters.The proof controls stochastic and higher-order terms with exponentially high probability in the inverse learning rate.
- Undamped directions: For γ_j = 0 directions, the accumulated update includes a systematic term proportional to the label-noise variance rather than linear mean reversion.Lemma 6 yields θ_j(T) = θ_j(0) minus a variance-dependent drift, up to controlled error terms.
B Proof of Theorem 2
The proof constructs infinitesimal perturbations of two-layer ReLU networks that preserve every training value while decreasing the implicit regularizer. It analyzes the four unit configurations around consecutive datapoints and tracks how active regions, function values, and regularization change.
- ReLU geometry: The ReLU unit is defined by its intercept −b_i/a_i and classified as convex when c_i > 0 or concave when c_i < 0.A zero output weight makes the unit functionally irrelevant.
- Proof strategy: The proof seeks a parameter perturbation that preserves all datapoint values while decreasing the implicit regularizer.It proceeds by contradiction from a function with excess changes of convexity and constructs such a direction.
- Case analysis: For a middle datapoint between two ReLU intercepts, the four sign configurations determine perturbations of the two units.Cases 2 and 3 additionally adjust the directly connected linear and bias units, while output weights remain fixed.
- Case analysis: In the analyzed case, shifting one intercept left and the other right preserves the middle datapoint and yields a regularization decrease proportional to the perturbation size.For points left of the first intercept, activity is unchanged; at the middle point, the first unit’s contribution is preserved and the second remains inactive.
- Conclusion: The same construction applies to the remaining configurations, including cases where the middle datapoint lies at an intercept.The perturbations preserve function values at the training points while the total regularization term strictly decreases.
C Tanh and Logistic Activations (Proof of Theorem 3)
For two-layer networks trained on one nonzero datapoint, the analysis studies logistic and tanh activations through the structure of non-repellent zero-error parameters. It shows that such parameters organize hidden units into only a few equivalent types.
- Setup: The single-datapoint setting uses a two-layer network with arbitrary width and analyzes logistic and tanh activations.The datapoint is (x, y) with x ≠ 0, and hidden-unit outputs are represented through their activation values and output weights.
- Main implication: At non-repellent points, the hidden units can be partitioned into a constant number of essentially equivalent neurons.This is the structural implication established for the single-datapoint analysis.
C.1 “Non-repellent” points for logistic activation
For logistic activations, non-repellent points force all hidden units into at most two output-value groups, with each group sharing its corresponding activation and output-weight values.
- Conclusion: Consequently, each hidden unit has either (c_i, h_i) = (α_1, β_1) or (α_2, β_2) at a non-repellent point.This is the proposition’s explicit two-group characterization.
- Characterization: Non-repellent points require the implicit regularizer to have zero gradient along directions that preserve the network output.The analysis rewrites the regularizer using hidden-unit outputs and examines output-preserving parameter changes.
- Characterization: The stationarity condition determines each hidden activation as a function of its hidden-unit output.The corresponding output weight is also determined by that output, so equal outputs imply equal unit parameters.
- Logistic structure: At most two distinct hidden-unit outputs can satisfy the logistic stationarity equation.The resulting scalar equation has at most two solutions because its transformed form is strictly convex, strictly concave, or linear according to the sign of a.
C.2 “Non-repellent” points for tanh activation
For tanh activations, the derivative of the scalar regularizer is injective away from zero, so non-repellent points contain one nonzero unit type up to sign, together with possible zero units.
- Conclusion: Non-repellent tanh networks have unit parameters of the form (α, β), (−α, −β), or (0, 0).The proposition allows sign-matched pairs and units that are completely zero.
- Proof strategy: The tanh analysis uses the same output-preserving perturbation logic but relies on injectivity of the derivative of the scalar regularizer.Unlike the logistic case, the derivative is undefined at zero.
- Tanh structure: All nonzero-output hidden units must share the same output at a non-repellent point.The derivative is injective away from zero, while zero output remains a separate possibility.
- Zero-output units: If a hidden unit has zero output, non-repellence forces both its activation and output weight to be zero.Such a unit therefore does not affect the network output for any input.