A fast natural Newton method.

Nicolas Le Roux, Andrew W FitzgibbonICML 2010 · OpenReview

Abstract

Standard second-order optimization methods for machine learning often treat training as a pure optimization problem, ignoring the sampling noise inherent in finite datasets. We present the "Natural-Newton" method, which integrates second-order Hessian information with natural gradient principles. By modeling the Newton direction as a noisy estimate within a Bayesian framework, the algorithm achieves faster convergence and greater stability than traditional methods like SGD-QN, particularly in large-scale learning scenarios where computational efficiency is paramount.

Introduction

In machine learning, the objective is typically to minimize a cost function estimated from a finite training set. While second-order optimizers like Newton’s method leverage the Hessian to navigate the loss surface's curvature, they often fail to account for the uncertainty introduced by data sampling. Conversely, natural gradient methods address this uncertainty via gradient covariance but frequently overlook second-order curvature. The Natural-Newton method bridges this gap by combining the Hessian (local geometry) with the covariance (sampling noise) to produce more robust parameter updates.

Methodology

The Natural-Newton method treats the ideal Newton step as a latent variable to be estimated. Using a Bayesian framework, the algorithm derives a "direction of maximum expected gain" by defining a posterior distribution over the true gradient given the observed empirical gradient.

The resulting update rule functions as a data-dependent regularized Newton step. When gradient estimates are noisy (high covariance), the method takes more conservative steps. As the sample size $n$ grows, the "natural" correction diminishes, and the method converges to a standard Newton update. To maintain computational efficiency for large-scale tasks, the implementation utilizes exponentially moving averages for tracking statistics, diagonal approximations for linear complexity, and delayed covariance updates to minimize overhead.

Experimental Evaluation

The method was evaluated on several datasets from the Pascal Large Scale Learning Challenge, including Alpha, Face, and others. These benchmarks represent scenarios where data is abundant but training time is the critical constraint.

Natural-Newton demonstrates superior convergence speed compared to SGD, TONGA, and SGD-QN on large-scale classification tasks.

Key Results

  • Superior Convergence: On the Alpha dataset, Natural-Newton achieved significantly faster convergence than both first-order SGD and second-order SGD-QN.
  • Enhanced Stability: In datasets characterized by high noise, such as Epsilon and Zeta, Natural-Newton produced markedly smoother error curves. While standard second-order methods often oscillate in response to noisy gradient estimates, the "Natural" correction provides a stabilizing effect.
The Natural-Newton method (blue) exhibits significantly higher stability and lower error compared to oscillating baselines in noisy training environments.
  • Robust Performance: In scenarios where covariance information offered less benefit, the algorithm's performance remained on par with SGD-QN, ensuring no degradation in optimization quality.
  • Computational Efficiency: By updating the covariance matrix less frequently than the Hessian, the authors maintained a computational cost nearly identical to existing second-order methods.

Discussion and Conclusion

The Natural-Newton method clarifies the distinction between the Hessian and gradient covariance, treating them as complementary sources of information rather than redundant approximations. By automatically regularizing steps based on data reliability, it prevents overreaction to stochastic noise at the start of training. Future work may involve refining the Bayesian priors and exploring the method's performance in the non-convex landscapes typical of deep neural networks.

Summary updated

BibTeX
@inproceedings{roux2010fast,
  author = {Nicolas Le Roux and Andrew W Fitzgibbon},
  title = {{A fast natural Newton method.}},
  booktitle = {ICML},
  year = {2010},
  url = {https://openreview.net/forum?id=RqvLVwDw2qE},
}
Figure