A Variance Reduced Stochastic Newton Method

By Aurélien Lucchi, Brian McWilliams, Thomas Hofmann. 2015

52 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Our result is in contrast to previous work that shows the global linear convergence of stochastic BFGS algorithms by either using variance-reduction (Kolte et al., 2015; Lucchi et al., 2015; Moritz et al., 2016) or progressive batching strategies (Bollapragada et al.”
A Linearly-Convergent Stochastic L-BFGS Algorithm (2015, methodology): “Lucchi et al. (2015) independently propose a variance-reduction procedure to speed up stochastic quasi-Newton methods and to achieve a linear rate of convergence.”
Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method (2017, methodology): “…incremental Hessian updates (G¨urb¨uzbalaban et al., 2015), stochastic dual Newton ascent (Qu et al., 2016), and stochastic quasi-Newton methods (Schraudolph et al., 2007; Mokhtari and Ribeiro, 2014, 2015; Lucchi et al., 2015; Moritz et al., 2016; Byrd et al., 2016; Mokhtari et al., 2017).”
Accelerating SVRG via second-order information (2015, background): “Naturally, there have also been quite a few recent works that aim to accelerate convergence of stochastic methods by incorporating curvature information [3, 4, 16, 10, 11], while maintaining a per-iteration complexity of O(p).”
IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate (2017, methodology): “The idea of variance reduction in [16, 20] is successful in achieving a linear convergence rate and improving the guaranteed sublinear convergence rates in [18, 19, 6]; however, they fail to recover the superlinear convergence rate of deterministic quasi-Newton methods.”
Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy (2016, methodology): “This difficulty is addressed by incremental computations in [11] and subsampling in [8] or circumvented altogether in stochastic quasi-Newton methods [22, 3, 14, 15, 16, 10].”