Subsampled inexact Newton methods for minimizing large sums of convex functions

By Stefania Bellavia, Natasa Krejic, Natasa Krklec Jerinkic. 2018

31 citations recorded by the source corpus.

This paper deals with the minimization of a large sum of convex functions by inexact Newton (IN) methods employing subsampled functions, gradients and Hessian approximations. The conjugate gradient method is used to compute the IN step and global convergence is enforced by a nonmonotone line-search procedure. The aim is to obtain methods with affordable costs and fast convergence. Assuming strongly convex functions, R-linear convergence and worst-case iteration complexity of the procedure are investigated when functions and gradients are approximated with increasing accuracy. A set of rules for the forcing parameters and subsample Hessian sizes are derived that ensure local q-linear/q-superlinear convergence of the proposed method. The random choice of the Hessian subsample is also considered and convergence in the mean square, both for finite and infinite sums of functions, is proved. Finally, the analysis of global convergence with asymptotic R-linear rate is extended to the case of the sum of convex functions and strongly convex objective function. Numerical results on well-known binary classification problems are also given. Adaptive strategies for selecting forcing terms and Hessian subsample size, streaming out of the theoretical analysis, are employed and the numerical results show that they yield effective IN methods.

Subfields: Computational Mechanics, Numerical Analysis, Optimization & Training, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Zhihua Zhang
2. Xiang Li
3. Shusen Wang

In Numerical Analysis

1. Zhihua Zhang
2. Xiang Li
3. Shusen Wang

In Optimization & Training

1. Xiang Li
2. Zhihua Zhang
3. Shusen Wang

In Mathematical Optimization

1. Shusen Wang
2. Xiang Li
3. Zhihua Zhang

Citations in the corpus

• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, neutral): “This is in contrast with the work of Bollapragada et al. (2018a) and Bellavia et al. (2018) that analyze sub-sampled Newton methods without interpolation, and require a geometrically increasing batch-size to achieve global linear convergence.”
• Do Subsampled Newton Methods Work for High-Dimensional Data? (2019, methodology): “This methodology has been discussed and practiced before [Bellavia et al., 2018; Shusen Wang et al., 2018].”