Source-linked AI summary
Geometry of Optimization and Implicit Regularization in Deep Learning
Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, Nathan Srebro
TL;DR
The paper asks why deep networks can generalize when network size alone does not explain their learning behavior. It studies implicit capacity control through optimization geometry and proposes Path-SGD, which outperforms gradient descent and AdaGrad on classification benchmarks.
Problem
Network size does not explain the observed generalization behavior, leaving open what implicit capacity control supports learning with deep networks.
Source: §1 · p. 2Method
The paper studies geometry suited to ReLU networks and proposes Path-SGD, an approximate steepest-descent method with respect to path regularization.
Source: §1 · pp. 2–3Results
Path-SGD outperforms gradient descent and AdaGrad for classification tasks on several benchmark datasets.
Source: §1 · p. 3Takeaways & Limitations
The authors report proof-of-concept evidence that an alternative optimization geometry can be beneficial for ReLU networks.
Source: §7 · p. 12Path-SGD is not the only rescaling-invariant update, and other invariant geometries might be better.
Source: §7 · p. 12
Abstract
from arXiv · showhide
We argue that the optimization plays a crucial role in generalization of deep learning models through implicit regularization. We do this by demonstrating that generalization ability is not controlled by network size but rather by some other implicit control. We then demonstrate how changing the empirical optimization procedure can improve generalization, even if actual optimization quality is not affected. We do so by studying the geometry of the parameter space of deep networks, and devising an optimization algorithm attuned to this geometry.
1. Introduction
Network size alone does not explain why deep networks can be learned or generalize, motivating a search for implicit capacity control and a geometry better suited to neural networks. The paper proposes Path-SGD as an optimization method tied to path regularization.
1. Introduction
- The paper frames learning as balancing a predictor class’s expressiveness and capacity with the computational cost of fitting a simple predictor.Network size is one conventional proxy for capacity, but the authors question whether it explains deep-network generalization.Source: §1 · pp. 1–2
- The authors argue that network size does not act as the capacity control in their experiments, pointing instead to a hidden control that may be the real inductive bias.They raise this question against the difficulty of efficiently learning even small feed-forward networks.Source: §1 · p. 2
- Optimization methods encode different geometries, which can act as implicit regularizers; ideally, the optimization geometry aligns with the inductive bias driving learning.Gradient descent corresponds to the ℓ2 norm, coordinate descent to ℓ1, and exp-gradient updates to an entropic divergence.Source: §1 · p. 2
- For ReLU networks, rescaling a hidden unit’s incoming and outgoing weights inversely preserves the computed function, motivating rescaling-invariant geometry and updates.The paper considers the minimum max-norm over weight rescalings as a path regularizer that can be computed efficiently.Source: §1 · p. 3
- Path-SGD is an approximate steepest-descent method with respect to path regularization, and it outperforms gradient descent and AdaGrad on several classification benchmarks.The paper presents this as evidence that optimization can introduce implicit regularization.Source: §1 · p. 3
2. Implicit Regularization
As networks grow beyond the size needed to fit the training data, test error can continue to fall rather than rise. The authors suggest that optimization implicitly favors low-complexity solutions, then motivate changing optimization geometry to improve generalization.
2. Implicit Regularization
- The experiments train single-hidden-layer networks by minimizing a truncated soft-max cross-entropy loss, with total weight count H(C + D).The described setup uses D real-valued inputs, H ReLU units, C outputs, and n labeled examples.Source: §2 · p. 3
- On MNIST and CIFAR-10, test error decreases past the network size needed for zero training error; generalization error does not rise even beyond the number of training examples.For MNIST, 32 units suffice for zero training error. Training used SGD with momentum and diminishing step sizes, without explicit regularization.Source: §2 · p. 4
- The observed lack of overfitting is attributed as a possibility to optimization implicitly seeking a low-complexity solution, even in an overparameterized network.The authors suggest larger networks may allow solutions of lower complexity.Source: §2 · p. 5
- Without explicit regularization and after reaching zero surrogate loss and training error, optimization appears to select a low-complexity global minimum among many that could overfit.The authors report nearly identical behavior with batch conjugate gradient descent.Source: §2 · p. 5
- Because optimization is proposed as the source of implicit regularization, the authors argue that changing its geometry may yield different generalization properties.They use this rationale to motivate an optimization algorithm tied to a geometry suited to neural networks.Source: §2 · p. 5
3. The Geometry of Optimization: Rescaling and Unbalanceness
For ReLU networks, rescaling incoming and outgoing weights can preserve the represented function, making rescaling-invariant optimization desirable. Gradient descent is not rescaling invariant and can behave poorly on unbalanced networks.
3. The Geometry of Optimization: Rescaling and Unbalanceness
- ReLU non-negative homogeneity permits rescaling incoming edges by a positive factor and outgoing edges by its reciprocal without changing the computed function.The paper denotes the resulting networks as rescaling equivalent.Source: §3 · p. 6
- The optimization setup represents each step as a weight update; in stochastic methods, gradients are computed on a subset of the training set.The stated objective is to minimize training-set loss.Source: §3 · p. 6
- Gradient descent is not rescaling invariant: scaling down an edge also scales up its gradient, opposite to the expected behavior of an invariant update.The paper defines rescaling invariance by requiring updates from equivalent starting weights to remain equivalent.Source: §3 · p. 6
- Randomly rescaling a balanced initialization produces an equivalent but unbalanced network, and SGD performance on MNIST shows a huge gap between the two initializations.The comparison is between networks related by random rescaling.Source: §3 · p. 6
- On unbalanced networks, gradient descent can blow up smaller weights while leaving larger weights nearly unchanged.The passage says relative weight changes also differ from those in a balanced network; equivalent networks can compute different functions after one update.Source: §3 · pp. 6–7
4. Magnitude/Scale measures for deep networks
The section considers group-norm measures, including per-unit max-norm, and seeks a rescaling-invariant measure for ReLU networks. The ℓp-path regularizer equals the minimum per-unit ℓp regularizer over rescaling-equivalent networks and is invariant to rescaling.
4. Magnitude/Scale measures for deep networks
- The group-norm framework groups incoming weights by unit; p = q = 1 gives overall ℓ1 regularization, while p = q = 2 gives weight decay.The max-norm is the maximum incoming-edge norm across units, corresponding to q = ∞.Source: §4 · p. 7
- For ReLU networks, per-unit ℓ2 regularization can be effective because the network can be rebalanced so hidden units have equal norms.The passage contrasts this with the extreme max-over-units form of per-unit regularization.Source: §4 · p. 7
- The paper distinguishes its max-norm from the matrix-factorization version, which concerns a minimum upper bound on input-unit outgoing and output-unit incoming ℓ2 norms in a two-layer network.The cited comparison is to Srebro and Shraibman (2005).Source: §4 · p. 7
- The ℓp-path regularizer is the minimum per-unit ℓp norm among rescaling-equivalent networks and remains unchanged under rescaling.Its path-vector coordinates are products of weights along input-to-output paths; the measure can be computed efficiently in a single forward step.Source: §4 · pp. 7–8
5. Path-SGD: An Approximate Path-Regularized Steepest Descent
The paper derives Path-SGD as a coordinate-wise approximation to steepest descent with respect to the path regularizer. It establishes rescaling invariance and describes an efficient implementation with a moderate runtime increase.
5. Path-SGD: An Approximate Path-Regularized Steepest Descent
- Path-SGD is an approximate steepest-descent method with respect to the path regularizer, derived by updating coordinates independently from the steepest-descent step.The paper names the stochastic use of path-normalized gradient descent Path-SGD.Source: §5 · pp. 8–9
- Path-SGD is rescaling invariant, so updates preserve equivalence between networks related by rescaling.The proof considers a rescaling of the current weights and shows the next update corresponds to that rescaling.Source: §5 · p. 9
- Path-SGD can be implemented in roughly (B + 1)T time for a mini-batch of size B when backpropagation takes BT, a moderate runtime increase.The update can be computed in no more than a forward-backward step on a single data point rather than explicitly considering exponentially many paths.Source: §5 · p. 9
- The section compares Path-SGD with other optimization methods in balanced and unbalanced settings.The supplied passage states the comparison setup but gives no outcome.Source: §5 · p. 9
6. Experiments on Path-SGD
The experiments compare Path-SGD with SGD and AdaGrad on four benchmarks, reporting faster convergence and better generalization in test-error plots. They also test balanced and unbalanced initializations and note potential gains from combining Path-SGD with adaptive methods or momentum.
6. Experiments on Path-SGD
- The experiments use four benchmarks: MNIST, CIFAR-10, CIFAR-100, and SVHN.The results are shown as cross-entropy, training-error, and test-error curves over optimization epochs; dropout is used for CIFAR-100 and SVHN experiments.Source: §6 · pp. 9–10
- Two-hidden-layer networks with 4,000 units per layer are trained with mini-batches of 100, with and without dropout.A validation set of 10,000 randomly selected points is used to choose the step size for each dataset.Source: §6 · p. 10
- Path-SGD outperforms SGD and AdaGrad by reaching the same accuracy faster and finding minima that generalize better, even at zero training error.The test-error plots also show better generalization while often reaching the same objective, training error, and test error faster.Source: §6 · p. 10, Figure 3 · p. 11
- Path-SGD produces identical curves from balanced and unbalanced initializations, despite numerical issues being checked explicitly.For the unbalanced setting, 2,000 hidden units are randomly selected and their incoming and outgoing edges rescaled inversely.Source: §6 · p. 11
- The authors suggest that combining Path-SGD with AdaGrad or Adam, or adding momentum, could potentially improve results.Source: §6 · p. 11
7. Discussion
The discussion presents Path-SGD as proof-of-concept that an alternative geometry can benefit optimization in ReLU networks. It leaves open other invariant updates and mirror descent, which the authors describe as challenging for non-convex neural networks.
7. Discussion
- The work presents experimental evidence for implicit regularization and discusses optimization geometry as a way to find low-complexity solutions.The authors characterize their Path-SGD results as proof-of-concept and expect potential benefit in large-scale training of very deep convolutional networks.Source: §7 · p. 12
- Path-SGD is not the only rescaling-invariant update, and other invariant geometries might be better.Source: §7 · p. 12
- Mirror descent with an appropriate potential might be preferable, but constructing it is challenging given neural-network non-convexity.Source: §7 · p. 12