TL;DR
This paper introduces "multidimensional backtracking," a novel algorithm that automatically finds optimal per-coordinate step-sizes (diagonal preconditioners) for smooth convex optimization problems. It achieves theoretical guarantees of performance competitive with the best possible diagonal preconditioner, without requiring manual tuning.
What Problem Does This Paper Address?
Training machine learning models often involves tuning hyperparameters, with step-size selection for gradient descent being a common challenge. While backtracking line-search effectively tunes a single step-size, it has limitations for ill-conditioned problems. Per-coordinate step-sizes (diagonal preconditioners) can significantly improve performance by adapting to the problem's geometry. However, existing methods for tuning these preconditioners lack theoretical guarantees of achieving convergence rates comparable to the optimal diagonal preconditioner. This paper aims to bridge this gap by providing a provably competitive and automatic method for finding good diagonal preconditioners.
Methods
The core contribution is multidimensional backtracking, an extension of the standard backtracking line-search to the space of diagonal preconditioners. The key insight is to leverage hypergradients (gradients with respect to the step-sizes) to define separating hyperplanes. These hyperplanes are then used within a cutting-plane method framework to efficiently search for valid preconditioners.
Instead of computationally expensive general cutting-plane methods like the ellipsoid method, the authors develop tailored, efficient algorithms. They explore two main strategies for managing the search space of preconditioners:
- Boxes: Maintaining a box of candidate diagonal preconditioners and iteratively shrinking it.
- Axis-aligned Ellipsoids: Using axis-aligned ellipsoids to represent the search space, offering a better competitive ratio.
The algorithm guarantees that the selected preconditioner is "y-competitive" (meaning it performs well relative to other candidates in the current search set) and that the search space shrinks when a candidate fails to yield sufficient progress.
Datasets
The paper evaluates its method on several standard datasets for regularized linear and logistic regression:
- Linear Regression: cpusmall, california-housing, power-plant, concrete, mg
- Logistic Regression: breast-cancer, australian, heart, diabetes, ionosphere, news20, rcv1
These datasets are publicly available from sources like LIBSVM, Scikit-Learn, and the UCI repository.
Key Insights and Ideas
- Hypergradients as Separating Hyperplanes: The paper elegantly shows that hypergradients can define hyperplanes that effectively separate valid from invalid preconditioners, enabling a systematic search.
- Cutting-Plane for Preconditioners: Adapting cutting-plane methods, typically used for convex optimization, to the problem of finding optimal preconditioners is a novel approach.
- Provable Competitiveness: Unlike many heuristic "adaptive" methods, multidimensional backtracking offers theoretical guarantees of performance competitive with the optimal diagonal preconditioner, up to a $\sqrt{2d}$ factor.
- No Manual Tuning: The algorithm is designed to be parameter-free, eliminating the need for manual hyperparameter tuning, which is a significant practical advantage.
- Ellipsoids for Better Ratios: Using axis-aligned ellipsoids for the search space allows for a stronger competitive ratio ($1/\sqrt{d}$) compared to the box-based approach ($1/d$).
Key Results
- Theoretical Guarantees: Multidimensional backtracking achieves a convergence rate competitive with gradient descent using the optimal diagonal preconditioner, with a factor of $\sqrt{2d}$ (where $d$ is the number of coordinates).
- Empirical Performance: Experiments show that multidimensional backtracking finds good preconditioners and achieves competitive performance, especially on ill-conditioned problems where other methods struggle.
- Robustness: The method demonstrates robust performance across various datasets and problem types, a clear advantage stemming from its worst-case theoretical guarantees.
- Efficiency: The cutting-plane methods are tailored to be computationally efficient, with complexity related to $O(d)$ for operations like updating the search space.
Limitations and Future Work
- Convexity Assumption: The current theoretical guarantees rely on the assumption of convex deterministic optimization. Extending these results to the stochastic overparameterized regime or non-convex settings is a significant open challenge.
- Non-linear Preconditioners: The paper focuses on diagonal preconditioners. Exploring more complex preconditioner structures could be a future direction.
- Practical Improvements: The authors suggest several avenues for practical improvements, including better forward step strategies, incorporating hypergradient information from accepted steps, and exploring alternative preconditioner structures.
Summary updated