A Variance Reduced Stochastic Newton Method

Abstract

Quasi-Newton methods are widely used in practise for convex loss minimization problems. These methods exhibit good empirical performance on a wide variety of tasks and enjoy super-linear convergence to the optimal solution. For large-scale learning problems, stochastic Quasi-Newton methods have been recently proposed. However, these typically only achieve sub-linear convergence rates and have not been shown to consistently perform well in practice since noisy Hessian approximations can exacerbate the effect of high-variance stochastic gradient estimates. In this work we propose Vite, a novel stochastic Quasi-Newton algorithm that uses an existing first-order technique to reduce this variance. Without exploiting the specific form of the approximate Hessian, we show that Vite reaches the optimum at a geometric rate with a constant step-size when dealing with smooth strongly convex functions. Empirically, we demonstrate improvements over existing stochastic Quasi-Newton and variance reduced stochastic gradient methods.

References in corpus (5)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• RES: Regularized Stochastic BFGS Algorithm
• A Stochastic Quasi-Newton Method for Large-Scale Optimization

Cited by in corpus (11)

• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Practical Quasi-Newton Methods for Training Deep Neural Networks
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
• A Stochastic Quasi-Newton Method with Nesterov's Accelerated Gradient
• An efficient Averaged Stochastic Gauss-Newton algorithm for estimating parameters of non linear regressions models
• Analysis of regularized federated learning
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• Faster Stochastic Quasi-Newton Methods
• Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization
• mL-BFGS: A Momentum-based L-BFGS for Distributed Large-Scale Neural Network Optimization