Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

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.

published in SIAM Journal on Optimization

References in corpus (5)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Stochastic Variance Reduction for Nonconvex Optimization
• RES: Regularized Stochastic BFGS Algorithm
• Global Convergence of Online Limited Memory BFGS

Cited by in corpus (2)

• Stochastic Conjugate Gradient Algorithm with Variance Reduction
• Estimation of discrete choice models with hybrid stochastic adaptive batch size algorithms