A stochastic quasi-Newton method for large-scale optimization

R. H. Byrd, S. L. Hansen, Jorge Nocedal, Y. Singer

Research output: Contribution to journalArticlepeer-review

113 Scopus citations

Abstract

The question of how to incorporate curvature information into stochastic approximation methods is challenging. The direct application of classical quasi-Newton updating techniques for deterministic optimization leads to noisy curvature estimates that have harmful effects on the robustness of the iteration. In this paper, we propose a stochastic quasi-Newton method that is efficient, robust, and scalable. It employs the classical BFGS update formula in its limited memory form, and is based on the observation that it is beneficial to collect curvature information pointwise, and at spaced intervals. One way to do this is through (subsampled) Hessian-vector products. This technique differs from the classical approach that would compute differences of gradients at every iteration, and where controlling the quality of the curvature estimates can be difficult. We present numerical results on problems arising in machine learning that suggest that the proposed method shows much promise.

Original languageEnglish (US)
Pages (from-to)1008-1031
Number of pages24
JournalSIAM Journal on Optimization
Volume26
Issue number2
DOIs
StatePublished - Jan 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science

Keywords

  • Large scale optimization
  • Quasi-Newton
  • Stochastic optimization
  • Sub sampling

Fingerprint Dive into the research topics of 'A stochastic quasi-Newton method for large-scale optimization'. Together they form a unique fingerprint.

Cite this