# Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Oct 2016.

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

- [Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis](https://mlsanity.com/paper/2209.10825/) (2022)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz condition](https://mlsanity.com/paper/2507.01932/) (2025)
- [A first-order method for constrained nonconvex-nonconcave minimax optimization](https://mlsanity.com/paper/2510.01168/) (2025)
- [Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence](https://mlsanity.com/paper/2604.17067/) (2026)

## Abstract (arXiv)

We consider optimization algorithms that successively minimize simple Taylor-like models of the objective function. Methods of Gauss-Newton type for minimizing the composition of a convex function and a smooth map are common examples. Our main result is an explicit relationship between the step-size of any such algorithm and the slope of the function at a nearby point. Consequently, we (1) show that the step-sizes can be reliably used to terminate the algorithm, (2) prove that as long as the step-sizes tend to zero, every limit point of the iterates is stationary, and (3) show that conditions, akin to classical quadratic growth, imply that the step-sizes linearly bound the distance of the iterates to the solution set. The latter so-called error bound property is typically used to establish linear (or faster) convergence guarantees. Analogous results hold when the step-size is replaced by the square root of the decrease in the model's value. We complete the paper with extensions to when the models are minimized only inexactly.