# A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 28 Oct 2023.

## Builds on (most cited first, 23 of 23)

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (2015)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [From Symmetry to Geometry: Tractable Nonconvex Problems](https://mlsanity.com/paper/2007.06753/) (2020)
- [Global convergence rate analysis of unconstrained optimization methods based on probabilistic models](https://mlsanity.com/paper/1505.06070/) (2015)
- [Stochastic Optimization Using a Trust-Region Method and Random Models](https://mlsanity.com/paper/1504.04231/) (2015)
- [A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization](https://mlsanity.com/paper/1803.02924/) (2018)
- [Accelerated Methods for Non-Convex Optimization](https://mlsanity.com/paper/1611.00756/) (2016)
- [Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization](https://mlsanity.com/paper/1706.03131/) (2017)
- [Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise](https://mlsanity.com/paper/1910.04055/) (2019)
- [A Stochastic Trust Region Algorithm Based on Careful Step Normalization](https://mlsanity.com/paper/1712.10277/) (2017)
- [Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization](https://mlsanity.com/paper/1912.04365/) (2019)
- [A Subsampling Line-Search Method with Second-Order Results](https://mlsanity.com/paper/1810.07211/) (2018)
- [Sample Complexity Analysis for Adaptive Optimization Algorithms with Stochastic Oracles](https://mlsanity.com/paper/2303.06838/) (2023)
- [Inexact Newton-CG Algorithms With Complexity Guarantees](https://mlsanity.com/paper/2109.14016/) (2021)
- [Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques](https://mlsanity.com/paper/2112.06176/) (2021)
- [Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function](https://mlsanity.com/paper/2310.11866/) (2023)

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

- [Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing](https://mlsanity.com/paper/2403.10547/) (2024)

## Abstract (arXiv)

We consider minimization of a smooth nonconvex function with inexact oracle access to gradient and Hessian (without assuming access to the function value) to achieve approximate second-order optimality. A novel feature of our method is that if an approximate direction of negative curvature is chosen as the step, we choose its sense to be positive or negative with equal probability. We allow gradients to be inexact in a relative sense and relax the coupling between inexactness thresholds for the first- and second-order optimality conditions. Our convergence analysis includes both an expectation bound based on martingale analysis and a high-probability bound based on concentration inequalities. We apply our algorithm to empirical risk minimization problems and obtain improved gradient sample complexity over existing works.