Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization
This work addresses a bottleneck in gradient-based methods for bilevel optimization, which is important for applications like hyperparameter optimization and meta-learning, but it is incremental as it builds on existing hypergradient computation methods.
The paper tackles the problem of hypergradient approximation in bilevel optimization by proposing a computationally efficient technique that incorporates curvature information, resulting in improved computational complexity and significant practical performance benefits in numerical experiments.
Bilevel optimization is a powerful tool for many machine learning problems, such as hyperparameter optimization and meta-learning. Estimating hypergradients (also known as implicit gradients) is crucial for developing gradient-based methods for bilevel optimization. In this work, we propose a computationally efficient technique for incorporating curvature information into the approximation of hypergradients and present a novel algorithmic framework based on the resulting enhanced hypergradient computation. We provide convergence rate guarantees for the proposed framework in both deterministic and stochastic scenarios, particularly showing improved computational complexity over popular gradient-based methods in the deterministic setting. This improvement in complexity arises from a careful exploitation of the hypergradient structure and the inexact Newton method. In addition to the theoretical speedup, numerical experiments demonstrate the significant practical performance benefits of incorporating curvature information.