- Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization Xiao Wang (wangxiaoucas.ac.cn) Shiqian Ma (sqmase.cuhk.edu.hk) Donald Goldfarb (goldfarbcolumbia.edu) Wei Liu (wliuee.columbia.edu) Abstract: 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 ($\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 $\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 L-BFGS (SdLBFGS) method, that falls under the proposed framework. Moreover, we incorporate the SVRG variance reduction technique into the proposed SdLBFGS method, and analyze its $\SFO$-calls complexity. Numerical results on a nonconvex binary classification problem using SVM, and a multiclass classification problem using neural networks are reported. Keywords: Stochastic Optimization, Nonconvex Optimization, Stochastic Approximation, Quasi-Newton Method, L-BFGS Method, Complexity Category 1: Nonlinear Optimization Citation: Download: [PDF]Entry Submitted: 07/05/2016Entry Accepted: 07/05/2016Entry Last Modified: 05/21/2017Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.