An investigation of Newton-Sketch and subsampled Newton methods

By Albert S. Berahas, Raghu Bollapragada, Jorge Nocedal. 2017

123 citations recorded by the source corpus.

ABSTRACT Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that perform dimensionality reduction in data space: Hessian subsampling and randomized Hadamard transformations. Each has its own advantages, and their relative tradeoffs have not been investigated in the optimization literature. Our study focuses on practical versions of the two methods in which the resulting linear systems of equations are solved approximately, at every iteration, using an iterative solver. The advantages of using the conjugate gradient method vs. a stochastic gradient iteration are revealed through a set of numerical experiments, and a complexity analysis of the Hessian subsampling method is presented.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, 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 Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, background): “If the iterates lie within a bounded set, then the above assumption holds for some ﬁnite γ (Bollapragada et al., 2018a; Berahas et al., 2020; Harikandeh et al., 2015).”
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].”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “In [10], the numerical performance of the Newton sketch method and different sub-sampled Newton approaches is compared.”
Quasi-Newton Methods for Deep Learning: Forget the Past, Just Sample (2019, methodology): “References [1] Albert S Berahas, Raghu Bollapragada, and Jorge Nocedal.”
Do Subsampled Newton Methods Work for High-Dimensional Data? (2019, methodology): “…(SSN) methods for reducing the per-iteration complexity of the Newton’s method (Byrd et al. 2011; Pilanci and Wain-wright 2015; Roosta-Khorasani and Mahoney 2016; Pi-lanci and Wainwright 2017; Xu, Roosta Khorasan, and Ma-honey 2017; Berahas, Bollapragada, and Nocedal 2017; Ye, Luo, and Zhang 2017).”
Scaling Up Quasi-newton Algorithms: Communication Efficient Distributed SR1 (2019, background): “, step size parameter) and are cumbersome to tune, and they suffer from ill-conditioning [3, 10, 47, 58].”
Subsampled inexact Newton methods for minimizing large sums of convex functions (2018, methodology): “1 Related work Our analysis is strictly related to that developed in [5, 7, 36, 37], where convergence of Inexact subsampled Newton methods is investigated both in probability [36, 37] and expectation [9, 7, 5].”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, methodology): “17 Another approach to scaling up second order methods is to use randomized sketching to reduce the 18 dimension, and hence the complexity of the Hessian and the updates involving the Hessian [23, 35], 19 or subsampled Hessian matrices when the objective function is a sum of many loss functions [2, ”
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].”