Revisiting Sub-sampled Newton Methods

Abstract

Many machine learning models depend on solving a large scale optimization problem. Recently, sub-sampled Newton methods have emerged to attract much attention for optimization due to their efficiency at each iteration, rectified a weakness in the ordinary Newton method of suffering a high cost at each iteration while commanding a high convergence rate. In this work we propose two new efficient Newton-type methods, Refined Sub-sampled Newton and Refined Sketch Newton. Our methods exhibit a great advantage over existing sub-sampled Newton methods, especially when Hessian-vector multiplication can be calculated efficiently. Specifically, the proposed methods are shown to converge superlinearly in general case and quadratically under a little stronger assumption. The proposed methods can be generalized to a unifying framework for the convergence proof of several existing sub-sampled Newton methods, revealing new convergence properties. Finally, we empirically evaluate the performance of our methods on several standard datasets and the results show consistent improvement in computational efficiency.

References in corpus (6)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Sketching as a Tool for Numerical Linear Algebra
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Second-Order Stochastic Optimization for Machine Learning in Linear Time
• Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence

Cited by in corpus (2)

• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• An inexact subsampled proximal Newton-type method for large-scale machine learning