# A Subsampling Line-Search Method with Second-Order Results

arXiv: https://arxiv.org/abs/1810.07211 · HTML: https://mlsanity.com/paper/1810.07211/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2018.

## Built on by (most cited first, 8 of 8)

- [Direct-Search for a Class of Stochastic Min-Max Problems](https://mlsanity.com/paper/2102.11386/) (2021)
- [A Globally Convergent Evolutionary Strategy for Stochastic Constrained Optimization with Applications to Reinforcement Learning](https://mlsanity.com/paper/2202.10464/) (2022)
- [Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function](https://mlsanity.com/paper/2310.11866/) (2023)
- [Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing](https://mlsanity.com/paper/2403.10547/) (2024)
- [A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees](https://mlsanity.com/paper/2310.18841/) (2023)
- [Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions](https://mlsanity.com/paper/2104.12949/) (2021)
- [GOALS: Gradient-Only Approximations for Line Searches Towards Robust and Consistent Training of Deep Neural Networks](https://mlsanity.com/paper/2105.10915/) (2021)
- [A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques](https://mlsanity.com/paper/2403.11163/) (2024)

## Abstract (arXiv)

In many contemporary optimization problems such as those arising in machine learning, it can be computationally challenging or even infeasible to evaluate an entire function or its derivatives. This motivates the use of stochastic algorithms that sample problem data, which can jeopardize the guarantees obtained through classical globalization techniques in optimization such as a trust region or a line search. Using subsampled function values is particularly challenging for the latter strategy, which relies upon multiple evaluations. On top of that all, there has been an increasing interest for nonconvex formulations of data-related problems, such as training deep learning models. For such instances, one aims at developing methods that converge to second-order stationary points quickly, i.e., escape saddle points efficiently. This is particularly delicate to ensure when one only accesses subsampled approximations of the objective and its derivatives. In this paper, we describe a stochastic algorithm based on negative curvature and Newton-type directions that are computed for a subsampling model of the objective. A line-search technique is used to enforce suitable decrease for this model, and for a sufficiently large sample, a similar amount of reduction holds for the true objective. By using probabilistic reasoning, we can then obtain worst-case complexity guarantees for our framework, leading us to discuss appropriate notions of stationarity in a subsampling context. Our analysis encompasses the deterministic regime, and allows us to identify sampling requirements for second-order line-search paradigms. As we illustrate through real data experiments, these worst-case estimates need not be satisfied for our method to be competitive with first-order strategies in practice.