Source-linked AI summary
Path-SGD: Path-Normalized Optimization in Deep Neural Networks
Behnam Neyshabur, Ruslan Salakhutdinov, Nathan Srebro
TL;DR
Deep-network optimization depends on choosing a geometry suited to function-preserving weight rescalings, but standard SGD is not invariant to them. The paper introduces Path-SGD, an approximate steepest-descent method based on path regularization, and reports gains over SGD and AdaGrad on benchmark classification tasks.
Problem
The paper asks whether ℓ2 geometry is appropriate for deep-network weights and whether a different geometry could improve optimization and implicit regularization.
Method
The paper introduces Path-SGD, an approximate steepest-descent method with respect to a rescaling-invariant path regularizer related to max-norm regularization.
Results
Path-SGD outperforms gradient descent and AdaGrad on classification tasks across several benchmark datasets.
Takeaways & Limitations
Using an alternative geometry for RELU networks can be beneficial, while rescaling invariance is an appropriate but non-unique design property.
Takeaways & Limitations
The work is a proof-of-concept, and other rescaling-invariant geometries may perform better.
Abstract
from arXiv · showhide
We revisit the choice of SGD for training deep neural networks by reconsidering the appropriate geometry in which to optimize the weights. We argue for a geometry invariant to rescaling of weights that does not affect the output of the network, and suggest Path-SGD, which is an approximate steepest descent method with respect to a path-wise regularizer related to max-norm regularization. Path-SGD is easy and efficient to implement and leads to empirical gains over SGD and AdaGrad.
1 Introduction
The paper questions whether ℓ2 geometry is appropriate for deep-network weights and proposes a rescaling-invariant alternative based on path regularization. This motivates Path-SGD as an approximate steepest-descent method for improving optimization and implicit regularization.
- Deep-network training remains slow despite heuristics and optimization methods built around SGD, adaptive stepsizes, and momentum.
- Optimization geometry determines update behavior and is linked to both convergence properties and the learning regularizer.
- The paper asks whether ℓ2 weight geometry is appropriate for deep networks or whether another geometry could enable faster optimization and better implicit regularization.
- For RELU networks, compensating incoming and outgoing weight rescalings preserve the computed function, motivating a geometry invariant to such transformations.
- The proposed geometry uses the minimum max-norm over equivalent rescalings, expressed as a path regularizer that can be computed efficiently.
- Path-SGD approximates steepest descent under path regularization and outperforms gradient descent and AdaGrad on classification benchmarks.
2 Rescaling and Unbalanceness
The paper shows that equivalent RELU networks can behave very differently under ordinary gradient updates because gradient descent is not rescaling invariant. This creates severe sensitivity to unbalanced weight magnitudes and motivates invariant update rules.
- RELU homogeneity permits multiplying incoming edges and dividing outgoing edges of a hidden unit while preserving the network function.
- Rescaling-equivalent networks compute the same function, and rescaling invariance requires their updates to remain rescaling equivalent over time.
- Gradient descent is not rescaling invariant because reducing an edge weight increases its gradient, producing the opposite scaling behavior expected from invariant updates.
- SGD shows a huge performance gap between balanced and unbalanced equivalent initializations on MNIST.
- In unbalanced networks, gradient updates can greatly change smaller weights while barely changing larger ones, causing equivalent networks to compute different functions after one update.
3 Magnitude/Scale measures for deep networks
The paper develops path-based scale measures for deep networks by minimizing per-unit regularization over rescaling-equivalent representations. The resulting path regularizer is rescaling invariant and computationally tractable.
- Group-norm regularizers organize weights entering each node and include overall ℓ1 regularization and weight decay as special cases.
- Max-norm regularization uses the maximum norm of incoming edges across units and corresponds to per-unit regularization with q = ∞.
- The ℓp-path regularizer is the ℓp norm of the vector whose coordinates are products of weights along input-to-output paths.
- The ℓp-path regularizer equals the minimum per-unit ℓp norm among all rescaling-equivalent networks.
- Although its definition contains exponentially many path terms, the regularizer can be computed by dynamic programming in a single forward step.
- The ℓp path regularizer is invariant under rescaling-equivalent transformations.
4 Path-SGD : An Approximate Path-Regularized Steepest Descent
Path-SGD approximates steepest descent under a path regularizer and is designed to preserve equivalence under weight rescaling. Its update rule is efficiently computable and is evaluated against other optimization methods.
- Path-SGD method: The path-normalized update references paths from input units to output units that include each updated edge.These path contributions determine the coordinate-wise update derived by setting the relevant partial derivative to zero.
- Path-SGD method: Path-normalized gradient descent uses coordinate-wise updates based on an approximate steepest descent step for the path regularizer; in stochastic settings, it is called Path-SGD.The exact steepest descent step is difficult to compute, so the method updates coordinates independently and synchronously.
- Rescaling invariance: Path-SGD is rescaling invariant: rescaling-equivalent networks remain rescaling equivalent after each update.The proof establishes that applying the update after rescaling produces the correspondingly rescaled next iterate.
- Efficient implementation: Path-SGD can be computed in roughly (B + 1)T time for a mini-batch of size B when backpropagation costs BT.This avoids explicitly enumerating exponentially many paths and adds approximately one forward-backward pass on a single data point.
- Experiments: The section compares Path-SGD with other optimization methods in balanced and unbalanced settings.The comparison is introduced as an evaluation across both types of network settings.
5 Experiments
Experiments compare ℓ2-Path-SGD with SGD and AdaGrad on four benchmark datasets, using balanced and unbalanced initializations with and without dropout. Path-SGD remains stable under rescaling and generally reaches comparable accuracy faster, with often better test generalization.
- Experimental setup: Experiments compare ℓ2-Path-SGD, SGD, and AdaGrad on MNIST, CIFAR-10, CIFAR-100, and SVHN.Networks had two hidden layers with 4000 units each and were trained with mini-batches of 100.
- Initialization and evaluation: Path-SGD updates were identical for balanced and unbalanced initializations, so only one Path-SGD curve was shown.The authors verified this identity experimentally despite numerical issues.
- Without dropout: Unbalanced initialization considerably hurts SGD and AdaGrad, while Path-SGD performs essentially the same.For SGD and AdaGrad, training and test errors were often outside the plotted range.
- Without dropout: In balanced settings, Path-SGD often reaches the same objective, training error, and test error faster than SGD and AdaGrad.The comparison uses learning curves for cross-entropy, training error, and test error.
- Generalization and dropout: Path-SGD sometimes has considerably lower final generalization error than SGD and AdaGrad, except on CIFAR-100, where SGD is slightly better.With dropout, Path-SGD converges much faster and generalizes better than SGD or AdaGrad except on MNIST.
- Overall findings: The results suggest two advantages: achieving the same accuracy faster and obtaining better generalization even when training error is zero.The authors also note that Path-SGD can be combined with AdaGrad or momentum.
6 Discussion
The discussion presents Path-SGD as a beneficial alternative geometry for RELU networks while acknowledging that other rescaling-invariant updates or geometries may perform better. The method uses steepest descent for implementation simplicity, whereas mirror descent remains a challenging alternative for non-convex neural networks.
- Discussion: The work shows proof-of-concept benefits from replacing Euclidean geometry with an alternative geometry for RELU networks.The authors expect possible benefits in large-scale training for very deep convolutional networks.
- Open alternatives: Path-SGD is not the only rescaling-invariant update, and other invariant geometries might be better.The authors frame the method as an invitation to consider other geometries, regularizers, and update rules.
- Methodological boundary: The method uses steepest descent for simplicity, while mirror descent with an appropriate potential remains difficult for non-convex neural networks.The discussion identifies the choice as an implementation-driven design decision.