# Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise

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

## Key facts

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

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

- [Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming](https://mlsanity.com/paper/2109.11502/) (2021)
- [Enhancing Efficiency of Safe Reinforcement Learning via Sample Manipulation](https://mlsanity.com/paper/2405.20860/) (2024)
- [A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2301.00477/) (2023)
- [Analyzing Inexact Hypergradients for Bilevel Learning](https://mlsanity.com/paper/2301.04764/) (2023)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [An adaptively inexact first-order method for bilevel optimization with application to hyperparameter learning](https://mlsanity.com/paper/2308.10098/) (2023)
- [Recursive Bound-Constrained AdaGrad with Applications to Multilevel and Domain Decomposition Minimization](https://mlsanity.com/paper/2507.11513/) (2025)
- [Finding Optimal Policy for Queueing Models: New Parameterization](https://mlsanity.com/paper/2206.10073/) (2022)
- [A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees](https://mlsanity.com/paper/2310.18841/) (2023)
- [The limitation of neural nets for approximation and optimization](https://mlsanity.com/paper/2311.12253/) (2023)
- [A New Formulation for Zeroth-Order Optimization of Adversarial EXEmples in Malware Detection](https://mlsanity.com/paper/2405.14519/) (2024)
- [Painless Federated Learning: An Interplay of Line-Search and Extrapolation](https://mlsanity.com/paper/2408.17145/) (2024)
- [A Parameter-Free First-Order Algorithm for Non-Convex Optimization with tildemkern1mu O(ε-5/3) Global Rate](https://mlsanity.com/paper/2605.02127/) (2026)

## Abstract (arXiv)

In this paper, we develop convergence analysis of a modified line search method for objective functions whose value is computed with noise and whose gradient estimates are inexact and possibly random. The noise is assumed to be bounded in absolute value without any additional assumptions. We extend the framework based on stochastic methods from [Cartis and Scheinberg, 2018] which was developed to provide analysis of a standard line search method with exact function values and random gradients to the case of noisy functions. We introduce two alternative conditions on the gradient which when satisfied with some sufficiently large probability at each iteration, guarantees convergence properties of the line search method. We derive expected complexity bounds to reach a near optimal neighborhood for convex, strongly convex and nonconvex functions. The exact dependence of the convergence neighborhood on the noise is specified.