Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Bilevel OptimizationHyperparameter OptimizationMeta-LearningSimilar Papers 제목 키워드 기반
Efficient Bilevel Optimization with KFAC-Based Hypergradients
Bilevel optimization (BO) is widely applicable to many machine learning problems. Scaling BO, however, requires repeatedly computing hypergradients, which involves solving inverse Hessian-vector products (IHVPs). In prac…
Bilevel OptimizationA Barrier-Metric First-Order Method for Linearly Constrained Bilevel Optimization
We study bilevel optimization with a fixed polyhedral lower feasible set. Such problems are challenging for two reasons: active-set changes can make the upper objective nonsmooth, and existing hypergradient methods typic…
Bilevel OptimizationOn the Convergence Theory for Hessian-Free Bilevel Algorithms
Bilevel optimization has arisen as a powerful tool in modern machine learning. However, due to the nested structure of bilevel optimization, even gradient-based methods require second-order derivative approximations via …
Bilevel OptimizationMeta-LearningOnline Nonconvex Bilevel Optimization with Bregman Divergences
Bilevel optimization methods are increasingly relevant within machine learning, especially for tasks such as hyperparameter optimization and meta-learning. Compared to the offline setting, online bilevel optimization (OB…
Bilevel OptimizationHyperparameter OptimizationMeta-LearningConvergence Properties of Stochastic Hypergradients
Bilevel optimization problems are receiving increasing attention in machine learning as they provide a natural framework for hyperparameter optimization and meta-learning. A key step to tackle these problems is the effic…
Bilevel OptimizationHyperparameter OptimizationMeta-Learning