A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization

Abstract

In this paper, a novel stochastic extra-step quasi-Newton method is developed to solve a class of nonsmooth nonconvex composite optimization problems. We assume that the gradient of the smooth part of the objective function can only be approximated by stochastic oracles. The proposed method combines general stochastic higher order steps derived from an underlying proximal type fixed-point equation with additional stochastic proximal gradient steps to guarantee convergence. Based on suitable bounds on the step sizes, we establish global convergence to stationary points in expectation and an extension of the approach using variance reduction techniques is discussed. Motivated by large-scale and big data applications, we investigate a stochastic coordinate-type quasi-Newton scheme that allows to generate cheap and tractable stochastic higher order directions. Finally, the proposed algorithm is tested on large-scale logistic regression and deep learning problems and it is shown that it compares favorably with other state-of-the-art methods.

41 pages

References in corpus (21)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Deep Learning in Neural Networks: An Overview
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Extremely Large Minibatch SGD: Training ResNet-50 on ImageNet in 15 Minutes
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• A Universal Catalyst for First-Order Optimization
• RES: Regularized Stochastic BFGS Algorithm
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Global Convergence of Online Limited Memory BFGS
• Forward-backward quasi-Newton methods for nonsmooth optimization problems
• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• Convergence rates of sub-sampled Newton methods
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Sub-sampled Newton Methods with Non-uniform Sampling
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• Forward-backward truncated Newton methods for convex composite optimization
• Local Convergence Properties of SAGA/Prox-SVRG and Acceleration
• Stochastic Second-Order Optimization via von Neumann Series
• Fast Variance Reduction Method with Stochastic Batch Size

Cited by in corpus (1)

• Orthant Based Proximal Stochastic Gradient Method for ${\ell }_1$-Regularized Optimization