A Variance Reduced Stochastic Newton Method

Aurelien Lucchi; Brian McWilliams; Thomas Hofmann

Source-linked AI summary

A Variance Reduced Stochastic Newton Method

Aurelien Lucchi, Brian McWilliams, Thomas Hofmann

arXiv:1503.08316v4Mar 28, 2015cs.LG

TL;DR

Stochastic quasi-Newton methods can have sublinear convergence and unreliable updates because noisy Hessian approximations amplify stochastic-gradient variance. VITE combines stochastic BFGS with multi-stage variance reduction, achieving geometric convergence with a constant step size under smooth strong convexity and outperforming stochastic BFGS and variance-reduced SGD experimentally.

Problem
Existing stochastic quasi-Newton methods typically have sublinear convergence and can suffer from gradient noise amplified by approximate Hessians.
Method
VITE is a stochastic BFGS method that progressively reduces stochastic-gradient variance without exploiting the specific form of the approximate Hessian.
Results
VITE achieves geometric convergence with a constant step size for smooth strongly convex functions and experimentally outperforms stochastic BFGS and variance-reduced SGD.
Takeaways & Limitations
Variance reduction on the gradient estimate is sufficient for fast convergence when the inverse-Hessian approximation is sufficiently well behaved.
Takeaways & Limitations
The analysis assumes a positive-definite, controlled-variance approximate Hessian and does not exploit its specific stochastic evolution.

Abstract

from arXiv · show

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.

1 Introduction

The paper motivates VITE as a stochastic quasi-Newton method that combines variance reduction with approximate curvature information to address noisy, unreliable updates. It claims geometric convergence with a constant step size and improved empirical performance.

Related work: Existing stochastic quasi-Newton approaches typically require decreasing step sizes and achieve sublinear rather than superlinear convergence.RES and SQN are cited as examples with sublinear convergence guarantees.
Motivation: Stochastic quasi-Newton methods can suffer amplified gradient noise because Hessian estimates may magnify variance and produce poor descent directions.This limits the reliability of stochastic second-order updates despite their potential curvature benefits.
Contribution: VITE applies a multi-stage scheme to progressively reduce stochastic-gradient variance in a stochastic BFGS method.The method periodically uses a pivot point to reduce variance while retaining quasi-Newton updates.
Contribution: For smooth strongly convex functions, VITE reaches the optimum geometrically using a constant step size.The paper presents this as the first stochastic quasi-Newton method with these properties.
Evaluation: The paper reports experiments on real-world datasets comparing VITE with stochastic quasi-Newton and variance-reduced stochastic-gradient methods.The experiments are intended to demonstrate performance improvements over existing competitors.

2 Stochastic second order optimization

The section develops stochastic second-order optimization from expected-loss minimization, explaining how quasi-Newton methods approximate curvature without explicit Hessian inversion. It then reviews stochastic BFGS variants and their convergence limitations.

2.1 Problem setting: Large datasets make full-gradient and Hessian computations impractical, motivating stochastic gradients and approximate second-order methods.Newton’s method can achieve quadratic convergence, but its Hessian computation and inversion are expensive.
2.2 Newton’s method and BFGS: BFGS incrementally estimates the inverse Hessian through gradient measurements and a secant-condition update instead of computing the Hessian directly.The resulting approximation is positive definite when initialized with a positive definite matrix.
2.3 Stochastic BFGS: Stochastic BFGS variants replace deterministic gradients with sampled estimates, using independent data subsets for curvature and descent information.oBFGS uses a fixed step-size sequence, while stochastic estimates determine both the direction and inverse-Hessian approximation.
2.3 Stochastic BFGS: RES regularizes the stochastic inverse-Hessian estimate by bounding its eigenvalues and adding an identity-bias term.The bound uses positive constants γ and δ and constrains the approximation in the positive-semidefinite order.
2.3 Stochastic BFGS: RES and SQN converge at O(1/t) with decreasing step sizes under Hessian-eigenvalue assumptions.These guarantees establish convergence but not the geometric, constant-step-size behavior targeted by VITE.

3 The VITE algorithm

VITE combines stochastic quasi-Newton updates with a multi-stage variance-reduction scheme, using a periodically refreshed pivot gradient to reduce noise while retaining the inverse-Hessian update. Its corrected direction preserves the expected descent direction, and its variance vanishes as iterates converge, enabling a constant step-size.

3 The VITE algorithm: VITE explicitly reduces update variance to offset the computational trade-off of using smaller sets A and B for inverse-Hessian and stochastic-gradient estimates.The method is motivated by the fact that smaller sets improve efficiency but increase update variance.
3 The VITE algorithm: The analysis treats the inverse-Hessian estimate as positive definite with controlled variance rather than exploiting its specific stochastic evolution.This assumption is justified as holding under weak conditions from the BFGS update, with regularization suggested for variance control.
3 The VITE algorithm: VITE replaces the stochastic gradient direction with a pivot-corrected estimator, vt = ∇fB(wt) − ∇fB(˜w) + ˜ν, while updating the inverse-Hessian approximation each iteration.The pivot ˜w is periodically refreshed in an outer loop, and inner-loop lengths follow a geometric distribution.
3 The VITE algorithm: The corrected direction has the same expectation as the stochastic gradient at wt, while its variance goes to zero when wt and ˜w converge to w∗.This variance reduction supports convergence with a constant step-size.

4 Analysis

The analysis extends variance-reduced first-order arguments to stochastic quasi-Newton updates by controlling the inverse-Hessian approximation through eigenvalue bounds. Under smoothness, strong convexity, and a well-behaved inverse-Hessian estimate, VITE achieves local geometric convergence with a constant learning rate and logarithmic dependence on target accuracy.

4 Analysis: The proof reduces the stochastic quasi-Newton analysis to eigenvalue bounds on the inverse-Hessian approximation and variance-reduced gradient properties.The analysis does not use the specific stochastic evolution equations for ˆJt.
4 Analysis: The theorem uses rescaled constants µ′ := γµ ≤ µ and L′ := ρL ≥ L, with η constrained by a bound involving these quantities.The inverse-Hessian approximation is assumed to remain well behaved, and its bounds enter the rescaled constants.
4 Analysis: When ˆJt is a good approximation to the Hessian, the learning-rate upper bound simplifies after substituting γ = L and ρ = µ.This remark connects the general theorem’s eigenvalue bounds to a favorable inverse-Hessian approximation.
4 Analysis: VITE has a local geometric convergence rate with a constant learning rate under the stated assumptions.The proof establishes geometric decay of expected suboptimality for the epoch iterates.
4 Analysis: The overall complexity is O((n + 2m(|A| + |B|)) log(1/ε)) component gradient evaluations.Each stage requires n + m(2|A| + 2|B|) component gradient evaluations, and the number of stages scales logarithmically with 1/ε.

5 Experimental Results

Experiments on least-square and logistic regression compare VITE with SGD, SVRG, and RES using gradient evaluations as the cost measure. VITE converges faster than the competing methods, especially with small gradient batches where variance reduction is most beneficial.

Experiments cover least-square regression on COV and logistic regression on ADULT and IJCNN1.The datasets range from 32,561 to 581,012 datapoints and use between 22 and 123 features.
For small |B|, VITE reaches a lower objective value faster than RES because variance reduction offsets noisy stochastic gradients.As |B| increases, the convergence gap narrows because stochastic-gradient variance decreases.
Increasing |A| increases gradient-evaluation cost, and a good-enough curvature estimate is obtained at |A| = O(10^-5n).The experiments compare methods as a function of gradient evaluations because their per-iteration costs differ.
VITE consistently converges faster than RES and SVRG, while both outperform SGD.The comparison uses objective values against the number of gradient evaluations, with constant step sizes for VITE and SVRG.

6 Conclusion

The conclusion presents VITE as a variance-reduced stochastic BFGS method with geometric convergence and stronger empirical performance than stochastic BFGS and variance-reduced SGD. It also identifies broader quasi-Newton extensions and the gap between theoretical and empirical rates as future directions.

VITE achieves geometric convergence for smooth convex functions and experimentally outperforms variance-reduced SGD and stochastic BFGS.The authors describe this as the first stochastic Quasi-Newton algorithm with this property.
The framework requires only a bound on inverse-Hessian eigenvalues and may extend to L-BFGS and ADAGRAD.
An open question is whether stochastic BFGS can achieve theoretical rates matching its empirical improvement over SVRG.

7 Appendix

The appendix studies how the inverse-Hessian sample set A affects convergence. Smaller |A| performs better because larger curvature-estimation sets increase gradient-evaluation cost beyond their benefit.

The analysis bounds a variance term using E ||ξ − Eξ||2 ≤ E ||ξ||2 and a Lipschitz-function inequality.
7.2 Selection of the parameter |A|.: Smaller |A| yields better convergence for both RES and VITE, while VITE outperforms RES across all tested values.The experiments use |A| = {0.00001, 0.0001} × n.
7.2 Selection of the parameter |A|.: Increasing |A| slows convergence because its gradient-evaluation penalty outweighs the benefit of improved curvature estimates.This observation is consistent with a similar finding in [12].