# Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 71 references that are in the map.
- First posted on arXiv 22 Jun 2023.

## Builds on (most cited first, 30 of 35)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Adaptive Gradient Methods with Dynamic Bound of Learning Rate](https://mlsanity.com/paper/1902.09843/) (2019)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Online Learning Rate Adaptation with Hypergradient Descent](https://mlsanity.com/paper/1703.04782/) (2017)
- [Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Be](https://mlsanity.com/paper/2304.13960/) (2023)
- [Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition](https://mlsanity.com/paper/1308.6370/) (2013)
- [Toward Understanding Why Adam Converges Faster Than SGD for Transformers](https://mlsanity.com/paper/2306.00204/) (2023)
- [A Progressive Batching L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1802.05374/) (2018)
- [Training Neural Networks for and by Interpolation](https://mlsanity.com/paper/1906.05661/) (2019)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [The importance of better models in stochastic optimization](https://mlsanity.com/paper/1903.08619/) (2019)
- [Probabilistic Line Searches for Stochastic Optimization](https://mlsanity.com/paper/1502.02846/) (2015)
- [Stochastic Polyak Stepsize with a Moving Target](https://mlsanity.com/paper/2106.11851/) (2021)
- [Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation](https://mlsanity.com/paper/1910.04920/) (2019)
- [Cutting Some Slack for SGD with Adaptive Polyak Stepsizes](https://mlsanity.com/paper/2202.12328/) (2022)
- [Parabolic Approximation Line Search for DNNs](https://mlsanity.com/paper/1903.11991/) (2019)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [Backtracking gradient descent method for general C1 functions, with applications to Deep Learning](https://mlsanity.com/paper/1808.05160/) (2018)

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

- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Stepping on the Edge: Curvature Aware Learning Rate Tuners](https://mlsanity.com/paper/2407.06183/) (2024)
- [An adaptively inexact first-order method for bilevel optimization with application to hyperparameter learning](https://mlsanity.com/paper/2308.10098/) (2023)
- [Parameter-free Clipped Gradient Descent Meets Polyak](https://mlsanity.com/paper/2405.15010/) (2024)
- [Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster](https://mlsanity.com/paper/2503.00229/) (2025)
- [Convergence Conditions for Stochastic Line Search Based Optimization of Over-parametrized Models](https://mlsanity.com/paper/2408.03199/) (2024)
- [Adaptive Backtracking Line Search](https://mlsanity.com/paper/2408.13150/) (2024)
- [AutoSGD: Automatic Learning Rate Selection for Stochastic Gradient Descent](https://mlsanity.com/paper/2505.21651/) (2025)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)
- [Why Line Search when you can Plane Search? SO-Friendly Neural Networks allow Per-Iteration Optimization of Learning and Momentum Rates for Every Layer](https://mlsanity.com/paper/2406.17954/) (2024)
- [No learning rates needed: Introducing SALSA -- Stable Armijo Line Search Adaptation](https://mlsanity.com/paper/2407.20650/) (2024)
- [Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems](https://mlsanity.com/paper/2411.07102/) (2024)
- [First-ish Order Methods: Hessian-aware Scalings of Gradient Descent](https://mlsanity.com/paper/2502.03701/) (2025)
- [Relationship between Batch Size and Number of Steps Needed for Nonconvex Optimization of Stochastic Gradient Descent using Armijo Line Search](https://mlsanity.com/paper/2307.13831/) (2023)
- [Large-scale empirical tuning and comparison of default optimizers for variational inference](https://mlsanity.com/paper/2606.07841/) (2026)

## Abstract (arXiv)

Recent works have shown that line search methods can speed up Stochastic Gradient Descent (SGD) and Adam in modern over-parameterized settings. However, existing line searches may take steps that are smaller than necessary since they require a monotone decrease of the (mini-)batch objective function. We explore nonmonotone line search methods to relax this condition and possibly accept larger step sizes. Despite the lack of a monotonic decrease, we prove the same fast rates of convergence as in the monotone case. Our experiments show that nonmonotone methods improve the speed of convergence and generalization properties of SGD/Adam even beyond the previous monotone line searches. We propose a POlyak NOnmonotone Stochastic (PoNoS) method, obtained by combining a nonmonotone line search with a Polyak initial step size. Furthermore, we develop a new resetting technique that in the majority of the iterations reduces the amount of backtracks to zero while still maintaining a large initial step size. To the best of our knowledge, a first runtime comparison shows that the epoch-wise advantage of line-search-based methods gets reflected in the overall computational time.