Sub-sampled Newton Methods with Non-uniform Sampling

By Peng Xu, Jiyan Yang, Farbod Roosta-Khorasani, Christopher R'e, Michael W. Mahoney. 2016

124 citations recorded by the source corpus.

We consider the problem of finding the minimizer of a convex function $F: \mathbb R^d \rightarrow \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.

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, background): “Similarly, Xu et al. (2016) achieve a local linear-quadratic convergence in high probability by using non-uniform sampling to select the batch.”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “Our GIANT method is motivated by the subsampled Newton method [33, 42, 25].”
Shampoo: Preconditioned Stochastic Tensor Optimization (2018, background): “, 2011; Kingma and Ba, 2014), a sketched version (Gonen and Shalev-Shwartz, 2015; Pilanci and Wainwright, 2017), or various estimations thereof (Erdogdu and Montanari, 2015; Agarwal et al., 2016; Xu et al., 2016).”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In particular on inexact variants of the Sketch-Newton method and subsampled Newton Method for minimize convex and nonconvex functions [172, 9, 14, 204, 205, 207].”
Optimization Methods for Supervised Machine Learning: From Linear Models to Deep Learning (2017, methodology): “Several variants of subsampled Newton methods have been proposed and analyzed for solving (strongly) convex formulations of problem (11) [68, 69, 25, 9, 87].”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, unknown): “Another approach to scaling up second order methods is to use randomized sketching to reduce the dimension, and hence the complexity of the Hessian and the updates involving the Hessian [26, 38], or subsampled Hessian matrices when the objective function is a sum of many loss functions [5, 2, 1, 37]”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, background): “For these problems, [10, 20, 42, 51] provide sketching/sampling techniques for Newton methods, where guarantees are established for sampling size and convergence rates; and [49–51, 54] show that sketching/sampling methods can significantly reduce the need for data in approximate Hessian computation.”
A Survey of Optimization Methods From a Machine Learning Perspective (2019, methodology): “It estimates the product Hv by some technique, and thus is called “Hessian free”.”
ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning (2020, background): “There have also been multiple theoretical studies showing better convergence rate of second order based meth-ods [2, 3, 5, 10, 12, 13, 42, 52–54, 56, 60].”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “In particular on inexact variants of the Sketch-Newton method and subsampled Newton Method for minimize convex and non-convex functions [48, 2, 4, 56, 57, 58].”
Subsampled inexact Newton methods for minimizing large sums of convex functions (2018, background): “On the other hand several papers investigate the use of second order methods in this framework and demonstrate advantages in some important problems if the second order methods are correctly implemented, [4, 7, 5, 10, 11, 18, 36, 37, 34, 40, 41].”
Do Subsampled Newton Methods Work for High-Dimensional Data? (2019, background): “• We study the convex and smooth problem (2). we show the convergence of the standard SSN with the effective-dimension dependence and improves (Xu et al. 2016).”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, background): “[94] present convergence and complexity results for a sub-sampled Newton-type approach with non-uniform sampling.”
An investigation of Newton-Sketch and subsampled Newton methods (2017, methodology): “, n} is chosen either uniformly at random (with or without replacement) or in a non-uniform manner as described in [26].”
Exact and Inexact Subsampled Newton Methods for Optimization (2016, methodology): “For example, solving (1.4) using a stochastic gradient iteration (SGI) has the potential advantage that the sample Sk in (1.4) can be changed at every iteration, in contrast with the Newton-CG method where it is essential to fix the sample Sk throughout the CG iteration.”
Approximate Newton Methods and Their Local Convergence (2017, methodology): “, 2011), and subsampled Newton with nonuniformly sampling (Xu et al., 2016), all have the same convergence properties; that is, they have a linear-quadratic convergence rate.”