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

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

## 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 (most cited first, 30 of 30)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [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)
- [A Stochastic Quasi-Newton Method for Large-Scale Optimization](https://mlsanity.com/paper/1401.7020/) (2014)
- [A Progressive Batching L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1802.05374/) (2018)
- [Disentangling Adaptive Gradient Methods from Learning Rates](https://mlsanity.com/paper/2002.11803/) (2020)
- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization](https://mlsanity.com/paper/1502.02268/) (2015)
- [Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation](https://mlsanity.com/paper/1910.04920/) (2019)
- [Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information](https://mlsanity.com/paper/2109.05198/) (2021)
- [Adaptive Gradient Methods Converge Faster with Over-Parameterization (but you should do a line-search)](https://mlsanity.com/paper/2006.06835/) (2020)
- [Quasi-Newton Methods for Machine Learning: Forget the Past, Just Sample](https://mlsanity.com/paper/1901.09997/) (2019)
- [On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions](https://mlsanity.com/paper/1606.09365/) (2016)
- [Fast and Near-Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2008.01722/) (2020)
- [Amortized Proximal Optimization](https://mlsanity.com/paper/2203.00089/) (2022)
- [Grad-GradaGrad? A Non-Monotone Adaptive Stochastic Gradient Method](https://mlsanity.com/paper/2206.06900/) (2022)
- [First-Order Preconditioning via Hypergradient Descent](https://mlsanity.com/paper/1910.08461/) (2019)
- [Step-size Adaptation Using Exponentiated Gradient Updates](https://mlsanity.com/paper/2202.00145/) (2022)
- [Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2209.00809/) (2022)
- [Variable Metric Proximal Gradient Method with Diagonal Barzilai-Borwein Stepsize](https://mlsanity.com/paper/1910.07056/) (2019)
- [Speed learning on the fly](https://mlsanity.com/paper/1511.02540/) (2015)

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

- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Gradient Methods with Online Scaling](https://mlsanity.com/paper/2411.01803/) (2024)
- [MetaOptimize: A Framework for Optimizing Step Sizes and Other Meta-parameters](https://mlsanity.com/paper/2402.02342/) (2024)
- [Two-level overlapping additive Schwarz preconditioner for training scientific machine learning applications](https://mlsanity.com/paper/2406.10997/) (2024)
- [Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent](https://mlsanity.com/paper/2502.11229/) (2025)
- [Gradient Methods with Online Scaling Part I. Theoretical Foundations](https://mlsanity.com/paper/2505.23081/) (2025)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)
- [A Learn-to-Optimize Approach for Coordinate-Wise Step Sizes for Quasi-Newton Methods](https://mlsanity.com/paper/2412.00059/) (2024)
- [Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles](https://mlsanity.com/paper/2607.17607/) (2026)

## 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.