Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

作者：Xiao Wang, Shiqian Ma, Donald Goldfarb, Wei Liu · 发表于：SIAM Journal on Optimization · 年份：2017 · DOI：10.1137/15m1053141 · 被引用次数：179 · 研究领域：Stochastic Gradient Optimization Techniques、Sparse and Compressive Sensing Techniques、Advanced Bandit Algorithms Research

In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle ($\mathcal{SFO}$). We propose a general framework for such methods, for which we prove almost sure convergence to stationary points and analyze its worst-case iteration complexity. When a randomly chosen iterate is returned as the output of such an algorithm, we prove that in the worst case, the $\mathcal{SFO}$-calls complexity is $O(\epsilon^{-2})$ to ensure that the expectation of the squared norm of the gradient is smaller than the given accuracy tolerance $\epsilon$. We also propose a specific algorithm, namely, a stochastic damped limited-memory BFGS (SdLBFGS) method, that falls under the proposed framework. Moreover, we incorporate the stochastic variance reduced gradient variance reduction technique into the proposed SdLBFGS method and analyze its $\mathcal{SFO}$-calls complexity. Numerical results on a nonconvex binary classification problem using a support vector machine and a multiclass classification problem using neural networks are reported.