mlsanityData to 14 Oct 2026

Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking

arXiv 2306.02527 ↗First posted 5 Jun 2023math.OC cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

The backtracking line-search is an effective technique to automatically tune the step-size in smooth optimization. It guarantees similar performance to using the theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes, also known as diagonal preconditioners, but none of the existing methods are provably competitive with the optimal per-coordinate stepsizes. We propose multidimensional backtracking, an extension of the backtracking line-search to find good diagonal preconditioners for smooth convex problems. Our key insight is that the gradient with respect to the step-sizes, also known as hypergradients, yields separating hyperplanes that let us search for good preconditioners using cutting-plane methods. As black-box cutting-plane approaches like the ellipsoid method are computationally prohibitive, we develop an efficient algorithm tailored to our setting. Multidimensional backtracking is provably competitive with the best diagonal preconditioner and requires no manual tuning.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 30 of its 84 references that are in the map. First posted on arXiv 5 Jun 2023.

Builds on

30 of 84 references.

References · 30

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  3. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 641
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  5. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 360
  6. 2020ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learningcited by 202
  7. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  8. 2020A Simple Convergence Proof of Adam and Adagradcited by 171
  9. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
  10. 2016Coin Betting and Parameter-Free Online Learningcited by 133
  11. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  12. 2017Online Learning Rate Adaptation with Hypergradient Descentcited by 118
18 more
  1. 2014A Stochastic Quasi-Newton Method for Large-Scale Optimizationcited by 69
  2. 2018A Progressive Batching L-BFGS Method for Machine Learningcited by 45
  3. 2020Disentangling Adaptive Gradient Methods from Learning Ratescited by 42
  4. 2021Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimizationcited by 21
  5. 2015SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimizationcited by 19
  6. 2019Fast and Furious Convergence: Stochastic Second Order Methods under Interpolationcited by 18
  7. 2021Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Informationcited by 16
  8. 2020Adaptive Gradient Methods Converge Faster with Over-Parameterization (but you should do a line-search)cited by 15
  9. 2019Quasi-Newton Methods for Machine Learning: Forget the Past, Just Samplecited by 12
  10. 2016On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functionscited by 9
  11. 2020Fast and Near-Optimal Diagonal Preconditioningcited by 9
  12. 2022Amortized Proximal Optimizationcited by 9
  13. 2022Grad-GradaGrad? A Non-Monotone Adaptive Stochastic Gradient Methodcited by 9
  14. 2019First-Order Preconditioning via Hypergradient Descentcited by 8
  15. 2022Step-size Adaptation Using Exponentiated Gradient Updatescited by 7
  16. 2022Optimal Diagonal Preconditioningcited by 7
  17. 2019Variable Metric Proximal Gradient Method with Diagonal Barzilai-Borwein Stepsizecited by 4
  18. 2015Speed learning on the flycited by 2

Built on by

Cited by year (2026 to 14 Oct)

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

9 papers.

  1. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
  2. 2024Gradient Methods with Online Scalingcited by 11
  3. 2024MetaOptimize: A Framework for Optimizing Step Sizes and Other Meta-parameterscited by 5
  4. 2024Two-level overlapping additive Schwarz preconditioner for training scientific machine learning applicationscited by 5
  5. 2025Provable and Practical Online Learning Rate Adaptation with Hypergradient Descentcited by 5
  6. 2025Gradient Methods with Online Scaling Part I. Theoretical Foundationscited by 3
  7. 2025Glocal Smoothness: Line search and adaptive step sizes can help in theory too!cited by 2
  8. 2024A Learn-to-Optimize Approach for Coordinate-Wise Step Sizes for Quasi-Newton Methodscited by 0
  9. 2026Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oraclescited by 0