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

Frederik Kunstner, Victor Sanches Portella, Mark Schmidt, Nicholas J. A. Harvey

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:

  1. Boxes: Maintaining a box of candidate diagonal preconditioners and iteratively shrinking it.
  2. 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

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 step-sizes. 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 hyper-gradients, 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.
BibTeX
@inproceedings{kunstner2023searching,
  author = {Frederik Kunstner and Victor Sanches Portella and Mark Schmidt and Nicholas J. A. Harvey},
  title = {{Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=rWjU0cd8Ma},
}
Figure