Abstract
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.
Introduction
In the realm of smooth optimization, the step-size (or learning rate) remains one of the most critical yet difficult hyperparameters to tune. A step-size that is too large leads to divergence, while one that is too small results in agonizingly slow convergence. While the classic backtracking line-search provides a robust mechanism for automatically tuning a single scalar step-size, it often struggles with "ill-conditioned" problems—scenarios where different features or dimensions vary at vastly different scales.
In these cases, a single scalar step-size is a compromise that fails to optimize for any specific dimension. To address this, researchers have long sought efficient ways to find diagonal preconditioners (per-coordinate step-sizes). However, existing adaptive methods often lack the theoretical guarantees necessary to ensure they are as fast as the theoretically optimal diagonal preconditioner. This paper introduces Multidimensional Backtracking (MB), a method that bridges this gap by extending line-search principles into higher dimensions using the geometry of hypergradients.
The Multidimensional Backtracking Approach
The core innovation of MB lies in how it treats failed optimization steps. In standard backtracking, if a step-size fails the Armijo condition (meaning the objective function did not decrease sufficiently), the step-size is simply shrunk. MB, however, extracts more information from these failures.
Hypergradients as Separating Hyperplanes
When a candidate set of per-coordinate step-sizes fails to meet the required descent criteria, the algorithm calculates the gradient of the progress with respect to the step-sizes—a "hypergradient." This hypergradient defines a separating hyperplane in the space of all possible diagonal preconditioners. This hyperplane effectively "cuts" the search space, identifying a region where the optimal preconditioner cannot reside.
Efficient Geometric Search
Searching for an optimal point in $d$-dimensional space using black-box cutting-plane methods (like the Ellipsoid method) is typically computationally expensive, often scaling at $O(d^2)$. To maintain the efficiency of first-order methods, the authors developed a specialized search algorithm using axis-aligned ellipsoids or boxes. This refinement ensures that the per-iteration cost remains $O(d)$, making the computational overhead comparable to standard gradient descent while providing much more sophisticated scaling.
Theoretical and Empirical Results
Provable Competitiveness
MB is not just a heuristic; it is provably competitive with the best possible fixed diagonal preconditioner. The method recovers the optimal convergence rate within a factor of $\sqrt{2d}$. While this factor scales with the dimension, it represents the inherent cost of the added degrees of freedom provided by tuning $d$ independent step-sizes. Furthermore, because MB adapts to the local geometry of the function at each iteration, it can occasionally outperform even the theoretically optimal fixed global preconditioner.
Performance on Ill-Conditioned Benchmarks
The authors evaluated MB on various regularized linear and logistic regression tasks, ranging from small, highly ill-conditioned datasets like cpusmall to large-scale benchmarks like news20 and rcv1 (featuring up to 1.3 million features).
Key findings include:
- Robustness: On the
cpusmalldataset, which is notoriously difficult for first-order methods due to its scaling, MB was the only method to approach the performance of second-order methods (such as those using the diagonal of the Hessian). - Efficiency: Despite the theoretical possibility of many backtracking steps, the algorithm typically identifies a high-performing preconditioner within a few dozen to a hundred gradient evaluations.
- Zero Tuning: The algorithm functions entirely without manual intervention, starting with a generous initial guess and narrowing the search space based on the actual behavior of the objective function.
Limitations and Future Directions
Currently, the strengths of Multidimensional Backtracking are most evident in deterministic, convex optimization. The cutting-plane logic relies on the reliability of the hypergradient to discard regions of the search space—a logic that may be challenged by the noise and non-convexity inherent in stochastic deep learning environments.
Future research directions include extending these guarantees to the stochastic overparameterized regime, utilizing information from successful steps (rather than just failed ones) to refine the search space, and exploring non-diagonal structures, such as block-diagonal preconditioners, to capture correlations between features.
Summary updated