Amortized Implicit Differentiation for Stochastic Bilevel Optimization
We study a class of algorithms for solving bilevel optimization problems in both stochastic and deterministic settings when the inner-level objective is strongly convex. Specifically, we consider algorithms based on inexact implicit differentiation and we exploit a warm-start strategy to amortize the estimation of the exact gradient. We then introduce a unified theoretical framework inspired by the study of singularly perturbed systems (Habets, 1974) to analyze such amortized algorithms. By using this framework, our analysis shows these algorithms to match the computational complexity of oracle methods that have access to an unbiased estimate of the gradient, thus outperforming many existing results for bilevel optimization. We illustrate these findings on synthetic experiments and demonstrate the efficiency of these algorithms on hyper-parameter optimization experiments involving several thousands of variables.
Code (1)
Tasks
Bilevel OptimizationSimilar Papers 제목 키워드 기반
Efficiently Escaping Saddle Points in Bilevel Optimization
Bilevel optimization is one of the fundamental problems in machine learning and optimization. Recent theoretical developments in bilevel optimization focus on finding the first-order stationary points for nonconvex-stron…
Bilevel OptimizationBilevel Optimization: Convergence Analysis and Enhanced Design
Bilevel optimization has arisen as a powerful tool for many machine learning problems such as meta-learning, hyperparameter optimization, and reinforcement learning. In this paper, we investigate the nonconvex-strongly-c…
Bilevel OptimizationHyperparameter OptimizationMeta-LearningProvably Faster Algorithms for Bilevel Optimization and Applications to Meta-Learning
Bilevel optimization has arisen as a powerful tool for many machine learning problems such as meta-learning, hyperparameter optimization, and reinforcement learning. In this paper, we investigate the nonconvex-strongly-c…
Bilevel OptimizationHyperparameter OptimizationMeta-LearningOn the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation
Stochastic Bilevel Optimization has emerged as a fundamental framework for meta-learning and hyperparameter optimization. Despite the practical prevalence of single-loop algorithms--which update lower and upper variables…
Hyperparameter OptimizationComputational EfficiencyBilevel OptimizationImplicit Diffusion: Efficient Optimization through Stochastic Sampling
We present a new algorithm to optimize distributions defined implicitly by parameterized stochastic diffusions. Doing so allows us to modify the outcome distribution of sampling processes by optimizing over their paramet…
Bilevel Optimization