PaperlayerView exact revision on arXiv

Source-linked AI summary

An Investigation into Neural Net Optimization via Hessian Eigenvalue Density

Behrooz Ghorbani, Shankar Krishnan, Ying Xiao

arXiv:1901.10159v1cs.LGstat.ML

TL;DR

The paper addresses the difficulty of understanding neural-network optimization through complete Hessian spectra, which are costly to compute exactly. It develops a scalable spectrum-estimation tool and uses it to show that outlier eigenvalues are linked to slow training, while batch normalization largely removes these effects.

  • Problem

    Exact Hessian spectra are computationally infeasible for large neural networks, limiting analysis to small models or a few eigenvalues despite the spectrum's role in local curvature and optimization.

  • Method

    The paper combines stochastic Lanczos quadrature with Hessian-vector products to estimate and track the full Hessian eigenvalue density at neural-network scale.

  • Results

    The main experimental result is that outlier eigenvalues slow optimization, whereas batch normalization pushes them into the bulk and helps explain faster training.

  • Takeaways & Limitations

    Full-spectrum analysis provides a comprehensive view of loss geometry and a framework for studying how architectural choices affect optimization.

  • Takeaways & Limitations

    The authors note that normalizing individual weight matrices and filters can cause blowup in some gradient components.

Abstract

from arXiv · show

To understand the dynamics of optimization in deep neural networks, we develop a tool to study the evolution of the entire Hessian spectrum throughout the optimization process. Using this, we study a number of hypotheses concerning smoothness, curvature, and sharpness in the deep learning literature. We then thoroughly analyze a crucial structural feature of the spectra: in non-batch normalized networks, we observe the rapid appearance of large isolated eigenvalues in the spectrum, along with a surprising concentration of the gradient in the corresponding eigenspaces. In batch normalized networks, these two effects are almost absent. We characterize these effects, and explain how they affect optimization speed through both theory and experiments. As part of this work, we adapt advanced tools from numerical linear algebra that allow scalable and accurate estimation of the entire Hessian spectrum of ImageNet-scale neural networks; this technique may be of independent interest in other applications.

1 Introduction

The paper introduces a scalable tool for tracking entire Hessian spectra during neural-network optimization, using it to study curvature hypotheses and outlier eigenvalues. Its central finding is that outliers are associated with slower training, while batch normalization pushes them into the bulk.

  • Contributions: The authors develop a tool for estimating entire Hessian spectra in models with tens of millions of parameters and millions of data points.The system is validated to double-precision accuracy of 10^-14 and scales to ResNets and Inception V3 on ImageNet.
  • Contributions: The released code and framework are intended to support further research on optimization, generalization, and architecture design.The authors explicitly present the framework as a research tool for the community.
  • Contributions: Tracking spectra throughout optimization provides evidence for and against hypotheses about curvature, learning rates, residual connections, and loss-surface geometry.The authors characterize these findings as evidence rather than definitive proofs or refutations across all models.
  • Outlier eigenvalues and optimization: Models with significant outlier Hessian eigenvalues train slowly because curvature energy is distributed across tiny bulk eigenvalues and stochastic gradients couple to outlier directions.The proposed explanation connects spectral structure with optimization progress.
  • Outlier eigenvalues and optimization: Batch normalization pushes outlier eigenvalues back into the bulk, providing insight into how it speeds optimization.The introduction identifies this as the paper's main experimental result.
  • Relation to prior work: The work extends prior Hessian studies from small models or partial spectra to models exceeding 10^7 parameters and datasets exceeding 10^6 examples.It also tracks spectral evolution during optimization rather than examining only the final state.

2 Accurate and Scalable Estimation of Hessian Eigenvalue Densities for n > 107

The paper estimates smoothed Hessian eigenvalue densities without explicit eigendecomposition by combining stochastic quadratic-form estimation with Gaussian quadrature and Lanczos iterations. The resulting method is accurate, scalable, and empirically effective for large neural-network models.

  • Density estimation: The exact spectral density is relaxed by Gaussian convolution because computing all eigenvalues is intractable for large parameter counts.For sufficiently small σ^2, the smoothed density retains practically relevant eigenvalue information.
  • Stochastic Lanczos quadrature: A quadrature rule with m nodes is exact for polynomials through degree 2m − 1, motivating the Gaussian quadrature approximation used here.The maximal guaranteed exactness degree is 2m − 1.
  • Stochastic Lanczos quadrature: Gaussian quadrature approximates the relevant integral using nodes and non-negative weights derived from a Lanczos tridiagonalization of H.Lanczos with full re-orthogonalization provides a numerically stable way to compute the quadrature construction.
  • Accuracy: For σ^2 = 10^-5, order 80 achieves maximum double-precision accuracy of 10^-14 on a 15910-parameter MNIST network, motivating m = 90 in experiments.The approximation error decreases exponentially in m under the stated analysis.
  • Validation and runtime: The estimator achieves L1(φσ, bφσ) ≈ 0.0012 and runs at ImageNet scale using O(mk) full-batch Hessian-vector products.For ResNet-18 on ImageNet, one draw takes about half the time required to train the model.

3 Spectral densities throughout optimization

The full Hessian spectrum provides curvature evidence throughout optimization, revealing rapid early changes, mostly flat spectra, persistent negative curvature on ImageNet, and effects of learning-rate drops and residual connections.

  • Spectral-density tracking provides direct evidence for and against hypotheses about loss-surface geometry and optimization.The analysis studies ResNet and VGG architectures on CIFAR-10 and ImageNet.
  • Within fewer than 1% of training steps, large negative eigenvalues disappear and the spectrum stabilizes.For ResNet-32, Figure 2 places this transition after 400 momentum steps; the observation is reproducible on ImageNet.
  • For the remainder of optimization, more than 99.99% of eigenvalues remain close to 0, producing an almost entirely flat spectrum.The emergence of large outliers depends strongly on whether batch normalization is present.
  • At optimization’s end on ImageNet, negative curvature remains substantial: negative and positive L1 energies are 0.434 and 0.449, respectively.The corresponding L2 energies are 0.025 and 0.036; CIFAR-10 shows a larger positive-versus-negative L2 contrast of 0.025 versus 0.179.
  • After the learning-rate drop at 40,000 steps, large eigenvalues contract substantially and density decreases at nearly all λ values.This is opposite to the hypothesis that lower learning rates produce sharper optima.
  • Removing residual connections contracts eigenvalues toward zero, making the Hessian appear smoother than in the residual network.This observation conflicts with the cited two-dimensional visualization hypothesis about residual connections and landscape smoothness.

4 Outlier Eigenvalues Slow Optimization; Batch Norm Suppresses Outliers

The paper finds that non-BN networks develop large Hessian outliers and concentrate gradient energy in their directions, slowing optimization, while BN suppresses these effects.

  • Outlier structure: Non-BN networks develop Hessian outliers that are much larger and farther from the spectral bulk than those in BN networks.The scale-invariant ratio ζ(t) tracks the relative size of the largest eigenvalue against the bulk.
  • Outlier structure: Batch normalization suppresses outlier eigenvalues, providing the paper’s proposed mechanism for faster optimization.The authors test this mechanism by comparing networks with and without BN.
  • Curvature and optimization: For small Hessian eigenvalues relative to λ1, convergence is slow, yet nearly 50% of a converged non-BN ResNet-32’s Hessian L1 energy lies near zero.Successful optimization must therefore make progress in these slowly converging directions.
  • Gradient concentration: In a ResNet-32 without BN, almost 99% of gradient-energy covariance is concentrated in the top few subspaces after 9k training steps.The covariance distributions are normalized to the same mean for comparison.
  • Testing the hypothesis: The paper’s gradient–path diagnostic uses the end-of-training parameters as a surrogate optimum and finds BN gradients better aligned with the optimization path.The non-BN gradient direction is described as nearly orthogonal to that path.
  • Gradient concentration: Outlier directions over-influence stochastic gradients, concentrating updates away from flatter directions needed to reduce the loss.The paper links this concentration to slow training and reports that BN networks have less concentration in high-curvature directions.
  • Gradient concentration: Almost all non-BN gradient variance lies in the subspace spanned by the 10 dominant Hessian eigenvectors, leaving negligible projection onto its complement.BN substantially reduces this gradient concentration.
  • Testing the hypothesis: Full-batch BN trains much more slowly than mini-batch BN despite similar largest Hessian eigenvalue magnitudes, indicating that λ1 alone misses optimization hardness.Full-batch BN exhibits stronger spectral outliers.

5 Conclusion

The paper concludes that scalable full-spectrum Hessian analysis reveals how loss geometry evolves and clarifies batch normalization’s effect on optimization.

  • Conclusion: The proposed numerical-analysis tools compute deep-network Hessian spectra accurately and scalably, providing a comprehensive view of local loss geometry.The authors present the tool as useful for studying neural-network behavior and future research questions.
  • Conclusion: Full-spectrum analysis supports new perspectives on curvature and optimization and identifies batch normalization’s suppression of outliers as an explanation for faster training.The framework is presented as applicable to other architecture choices.

A Concentration of Quadratic Forms

This appendix establishes concentration bounds for quadratic-form estimates used in the spectrum-density framework and shows that modest sample sizes can provide tight high-probability accuracy.

  • Concentration result: The appendix invokes a concentration lemma for Gaussian quadratic forms involving a Gaussian vector ζ and an arbitrary matrix A.The lemma supplies the probabilistic bound used in the proof.
  • Proof strategy: The proof rewrites the estimator as a quadratic form w^T A w with independently Gaussian coordinates, then applies the lemma.The concatenated vector w is normalized to obtain the required Gaussian distribution.
  • Proof strategy: The resulting bound worsens as the auxiliary quantities a and b increase, with worst-case bounds obtained from the Gaussian density.The proof substitutes b ≤ 1/(√(2π)σ) and a ≤ √n b.
  • Concentration result: Figure 14 shows that even modest k values yield tight bounds on ε with high probability.The probability bound is expressed through 2 exp(−x).

B Numerical Verification on Small Models

On a small MNIST network with an exactly computable Hessian, the proposed quadrature estimator closely matches the exact smoothed density and detects spectral outliers.

  • Estimator validation: Increasing the Gaussian kernel width σ2 changes the estimator’s accuracy, motivating the selected large-scale setting σ2 = 10^-5.The figure compares estimated and exact smoothed densities on [0.4, +∞).
  • Estimator validation: For a 15,910-parameter one-hidden-layer MNIST network, 90 quadrature points approximate the exact smoothed density with L1 error approximately 0.0012.The estimator is evaluated over both the near-zero bulk and the outlier interval.
  • Estimator validation: The estimator recovers information at the density edges and detects outlier eigenvalues in the small-model experiment.The comparison uses σ2 = 10^-5, k = 10, and degree-90 quadrature.

C Implementation Details

The system scales Hessian-spectrum estimation through distributed, deterministic Lanczos computations, but substantial runtime, memory, and engineering costs remain for large models.

  • Distributed computation: Distributed Lanczos parallelizes Hessian-vector products across workers, which the chief aggregates before QR orthogonalization and synchronization.Workers process data partitions, while semaphores coordinate iterations and shared memory stores results.
  • Numerical control: Hessian-vector computations eliminate nondeterminism from data subsampling, shuffle order, random seeds, and parallel summary processing.This ensures the Lanczos iteration corresponds to a well-defined matrix.
  • Numerical control: Double precision is required for Hessian-vector accumulation and Lanczos orthogonalization, while TensorFlow locking protects accumulator updates.Worker coordination relies on semaphore variables because TensorFlow lacks direct inter-worker communication.
  • Cost and limitations: 90 Lanczos iterations take about 1 hour on CIFAR-10, 20 hours for ImageNet Resnet-18, and 3 days for Inception V3.The authors could not run larger models because of TensorFlow out-of-memory bugs and had not optimized parameter-transfer overhead.
  • Cost and limitations: Peak GPU memory can increase dramatically for the largest models when TensorFlow graph optimizations are enabled.The implementation therefore requires careful memory management.

D Comparison with Other Spectrum Estimation Methods

The paper compares Chebyshev polynomial approximation with Gaussian quadrature for Hessian-spectrum estimation and finds that Chebyshev requires prohibitively high orders for accurate narrow-kernel approximation.

  • Polynomial approximation: Polynomial methods approximate f(·, t, σ2) with a degree-m polynomial g_m(·), using Hessian-vector products to evaluate required moments.With k probe vectors, Algorithm 1 requires k m Hessian-vector products.
  • Chebyshev method: Chebyshev polynomials are computationally and theoretically attractive for approximating smooth functions, but their accuracy deteriorates for small kernel widths.The comparison uses σ2 = 10^-5 and equal Hessian-vector-product computation against Gaussian quadrature.
  • Comparison: The Chebyshev method fails to provide an accurate spectrum estimate under the directly comparable computation and kernel-width settings.The paper expects matching Gaussian-quadrature accuracy to require orders of magnitude more Hessian-vector products.
  • Chebyshev method: 500-degree Chebyshev approximation still differs significantly from the exact kernel when σ2 = 10^-5.Figure 18 indicates that orders of 500 or more are needed for accurate approximation, despite their instability and computational expense.
  • Comparison: Figure 17 reports Chebyshev spectral-density estimates in both linear and logarithmic scales using a degree-90 polynomial and σ2 = 10^-5.Exact eigenvalue moments were supplied to remove noise from moment estimation.

E Gradient Concentration in the Quadratic Case

The quadratic analysis explains gradient concentration by decomposing stochastic-gradient updates along Hessian eigenvectors and showing that eigenvalue separation and noise covariance shape long-run alignment.

  • Setup: The analysis studies stochastic gradient descent on a quadratic loss, with Hessian eigenpairs (λ_i, q_i), Gaussian initialization, and zero-mean stochastic perturbations.The noise covariance is denoted S.
  • Theorem: Theorem E.1 analyzes one constant-learning-rate update with η ≈ c/λ_1 for a constant c < 1.The theorem quantifies update alignment with individual Hessian eigenvectors.
  • Derivation: A stochastic gradient step expands as θ_t = θ_{t−1} − ηH(θ_{t−1} + z_{t−1}), and each update is analyzed through its dot product with q_i.This separates dynamics along individual eigendirections.
  • Asymptotic behavior: As t →∞, the deterministic contribution vanishes, leaving the noise-dependent term to determine asymptotic update variance.The remaining expression depends on η, λ_i, and q_i^T S q_i.
  • Interpretation: Greater eigenvalue separation produces quadratic alignment of gradient updates with top eigenspaces.Aligning S with H enhances top-eigenspace concentration, whereas aligning S with H^-1 diminishes it.

F Experimental Details

Experiments evaluate CIFAR-10 and ImageNet models with specified architectures, optimization schedules, and label smoothing to ensure finite local minima.

  • CIFAR-10: CIFAR-10 experiments include Resnet-32 with 460k parameters and VGG-11 with over 10 million parameters.Resnet-32 uses scheduled SGD, while VGG-11 uses constant-rate SGD; both use batch size 128.
  • CIFAR-10: Resnet-32 reaches 92% validation accuracy with data augmentation and around 85% without it.The model decays its learning rate by factors of 10 at steps 40k, 60k, and 80k.
  • Training setup: Label smoothing of 0.1 is introduced to ensure a finite local minimum without affecting validation accuracy.The lowest attained cross-entropy loss is 0.509.
  • ImageNet: The ImageNet Resnet-18 experiment uses 299 × 299 images, asynchronous training on 50 GPUs, batch size 32, and an initial learning rate of 0.045.It reaches 71.9% validation accuracy and has over 11 million parameters.

G Batch normalization with population statistics

The population-loss experiment with batch normalization is difficult to run on CIFAR-10 and requires substantially modified optimization settings. Figure 19 compares optimization progress using mini-batch versus population statistics.

  • The experiment was difficult to run on CIFAR-10, including failure to train Inception V3 except with a learning rate of 10^-6.
  • The learning rate had to be divided by 100 for the population-statistics experiment.
  • At least 400 initial steps with learning rate 0 were used to stabilize batch-normalization population statistics.This provided a better initialization than the default mean of 0.0 and variance of 1.0.
  • Figure 19 compares optimization progress in terms of loss for batch normalization using mini-batch statistics versus population statistics.
Loading 1901.10159v1…