SIAM Journal on Optimization · 2017 · 176 citations · 46 references
Natural SciencesComputer ScienceMathematicsAlgorithmsOptimizationTheory Of ComputationAlgorithm AnalysisComputational MathematicsConvex OptimizationGradient-based OptimizationNumerical AlgorithmsStochastic OptimizationAlmost Sure ConvergenceGradient DescentNoisy OptimizationNonconvex OptimizationStationary PointsStochastic Gradient DescentSupport Vector ClassificationWorst-case Complexity
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.
46
A Stochastic Approximation Method
Herbert Robbins, Sutton Monro · The Annals of Mathematical Statistics · 1951 · 9.6K citations · Full text
A new approach to variable metric algorithms
R. Fletcher · The Computer Journal · 1970 · 4.1K citations · Full text
Conditioning of quasi-Newton methods for function minimization
David F. Shanno · Mathematics of Computation · 1970 · 3.7K citations · Full text