Sub-sampled Newton Methods with Non-uniform Sampling

Abstract

We consider the problem of finding the minimizer of a convex function $F:{\mathbb{R}}^d\to \mathbb{R}$ of the form $F(w):={\sum }_{i=1}^n{f}_i(w)+R(w)$ where a low-rank factorization of ${\nabla }^2{f}_i(w)$ is readily available. We consider the regime where $n\gg d$. As second-order methods prove to be effective in finding the minimizer to a high-precision, in this work, we propose randomized Newton-type algorithms that exploit \textit{non-uniform} sub-sampling of $\{{\nabla }^2{f}_i(w){\}}_{i=1}^n$, as well as inexact updates, as means to reduce the computational complexity. Two non-uniform sampling distributions based on {\it block norm squares} and {\it block partial leverage scores} are considered in order to capture important terms among $\{{\nabla }^2{f}_i(w){\}}_{i=1}^n$. We show that at each iteration non-uniformly sampling at most $\mathcal{O}(d\log d)$ terms from $\{{\nabla }^2{f}_i(w){\}}_{i=1}^n$ is sufficient to achieve a linear-quadratic convergence rate in $w$ when a suitable initial point is provided. In addition, we show that our algorithms achieve a lower computational complexity and exhibit more robustness and better dependence on problem specific quantities, such as the condition number, compared to similar existing methods, especially the ones based on uniform sampling. Finally, we empirically demonstrate that our methods are at least twice as fast as Newton's methods with ridge logistic regression on several real datasets.

minor fix on v1

References in corpus (6)

• Sketching as a Tool for Numerical Linear Algebra
• Randomized algorithms for matrices and data
• 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 (15)

• PyHessian: Neural Networks Through the Lens of the Hessian
• Second-Order Methods with Cubic Regularization Under Inexact Information
• Stochastic Newton and Quasi-Newton Methods for Large Linear Least-squares Problems
• Regularization by Denoising Sub-sampled Newton Method for Spectral CT Multi-Material Decomposition
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Lower Bounds for Higher-Order Convex Optimization
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• Fast Approximation of the Gauss-Newton Hessian Matrix for the Multilayer Perceptron
• Importance Sampling via Local Sensitivity
• Speeding up Linear Programming using Randomized Linear Algebra
• SPAN: A Stochastic Projected Approximate Newton Method
• Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality
• Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions
• Curvature-Exploiting Acceleration of Elastic Net Computations
• Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates