Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

By Xiao Wang, Shiqian Ma, Donald Goldfarb, Wei David Liu. 2016

198 citations recorded by the source corpus.

In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that only stochastic information of the gradients of the objective function is available via a stochastic first-order oracle (SFO). Firstly, we propose a general framework of stochastic quasi-Newton methods for solving nonconvex stochastic optimization. The proposed framework extends the classic quasi-Newton methods working in deterministic settings to stochastic settings, and we prove its almost sure convergence to stationary points. Secondly, we propose a general framework for a class of randomized stochastic quasi-Newton methods, in which the number of iterations conducted by the algorithm is a random variable. The worst-case SFO-calls complexities of this class of methods are analyzed. Thirdly, we present two specific methods that fall into this framework, namely stochastic damped-BFGS method and stochastic cyclic Barzilai-Borwein method. Finally, we report numerical results to demonstrate the efficiency of the proposed methods.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, unknown): “In particular, many of these new methods are based on stochastic BFGS updates [29, 35, 20, 21, 6, 8, 3].”
Revisiting Recursive Least Squares for Training Deep Neural Networks (2021, methodology): “The third type mainly uses the L-BFGS method to approximate the inverse Hessian [21], [22].”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “As in [66, 5, 86], this additional noise-free information is stored and utilized in the computation of the stochastic oracles for the following iterations.”
A Linearly-Convergent Stochastic L-BFGS Algorithm (2015, background): “The inverse Hessian approximation H r is deﬁned from the pairs ( s j , y j ) for r − M + 1 ≤ j ≤ r using the standard L-BFGS update rule, which is described in Section 2.1.”