Optimization Online


Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

Xiao Wang (wangxiao***at***ucas.ac.cn)
Shiqian Ma (sqma***at***se.cuhk.edu.hk)
Donald Goldfarb (goldfarb***at***columbia.edu)
Wei Liu (wliu***at***ee.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


Download: [PDF]

Entry Submitted: 07/05/2016
Entry Accepted: 07/05/2016
Entry Last Modified: 05/21/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society