mlsanityData to 14 Oct 2026

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

arXiv 2306.12747 ↗First posted 22 Jun 2023math.OC cs.LGcited by 15

Not on the map. Why?

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.

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

35 of 71 references.

References · 35

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  4. 2016Densely Connected Convolutional Networkscited by 6,720
  5. 2019EfficientNet: Rethinking Model Scaling for Convolutional Neural Networkscited by 6,442
  6. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  7. 2016Pointer Sentinel Mixture Modelscited by 3,096
  8. 2016Wide Residual Networkscited by 3,070
  9. 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,850
  10. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  11. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  12. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
23 more
  1. 2019Adaptive Gradient Methods with Dynamic Bound of Learning Ratecited by 183
  2. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  3. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  4. 2017Online Learning Rate Adaptation with Hypergradient Descentcited by 118
  5. 2023Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Becited by 114
  6. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  7. 2023Toward Understanding Why Adam Converges Faster Than SGD for Transformerscited by 53
  8. 2018A Progressive Batching L-BFGS Method for Machine Learningcited by 45
  9. 2019Training Neural Networks for and by Interpolationcited by 45
  10. 2016Barzilai-Borwein Step Size for Stochastic Gradient Descentcited by 33
  11. 2019The importance of better models in stochastic optimizationcited by 32
  12. 2015Probabilistic Line Searches for Stochastic Optimizationcited by 29
  13. 2021Stochastic Polyak Stepsize with a Moving Targetcited by 19
  14. 2019Fast and Furious Convergence: Stochastic Second Order Methods under Interpolationcited by 18
  15. 2022Cutting Some Slack for SGD with Adaptive Polyak Stepsizescited by 18
  16. 2019Parabolic Approximation Line Search for DNNscited by 14
  17. 2022SP2: A Second Order Stochastic Polyak Methodcited by 13
  18. 2018Backtracking gradient descent method for general C1 functions, with applications to Deep Learningcited by 6
  19. 2018A Stochastic Line Search Method with Convergence Rate Analysiscited by 5
  20. 2019The Search direction Correction makes first-order methods fastercited by 1
  21. 2019A Generalized Worst-Case Complexity Analysis for Non-Monotone Line Searchescited by 1
  22. 2021A stochastic first-order trust-region method with inexact restoration for finite-sum minimizationcited by 1
  23. 2023Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Conditioncited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 7; 2025: 4; 2026: 1.

15 papers.

Sort:

  1. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
  2. 2024Stepping on the Edge: Curvature Aware Learning Rate Tunerscited by 8
  3. 2023An adaptively inexact first-order method for bilevel optimization with application to hyperparameter learningcited by 4
  4. 2024Parameter-free Clipped Gradient Descent Meets Polyakcited by 3
  5. 2025Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Fastercited by 3
  6. 2024Convergence Conditions for Stochastic Line Search Based Optimization of Over-parametrized Modelscited by 2
  7. 2024Adaptive Backtracking Line Searchcited by 2
  8. 2025AutoSGD: Automatic Learning Rate Selection for Stochastic Gradient Descentcited by 2
  9. 2025Glocal Smoothness: Line search and adaptive step sizes can help in theory too!cited by 2
  10. 2024Why Line Search when you can Plane Search? SO-Friendly Neural Networks allow Per-Iteration Optimization of Learning and Momentum Rates for Every Layercited by 1
  11. 2024No learning rates needed: Introducing SALSA -- Stable Armijo Line Search Adaptationcited by 1
  12. 2024Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problemscited by 1
3 more
  1. 2025First-ish Order Methods: Hessian-aware Scalings of Gradient Descentcited by 1
  2. 2023Relationship between Batch Size and Number of Steps Needed for Nonconvex Optimization of Stochastic Gradient Descent using Armijo Line Searchcited by 0
  3. 2026Large-scale empirical tuning and comparison of default optimizers for variational inferencecited by 0