UFO-BLO: Unbiased First-Order Bilevel Optimization

Abstract

Bilevel optimization (BLO) is a popular approach with many applications including hyperparameter optimization, neural architecture search, adversarial robustness and model-agnostic meta-learning. However, the approach suffers from time and memory complexity proportional to the length $r$ of its inner optimization loop, which has led to several modifications being proposed. One such modification is \textit{first-order} BLO (FO-BLO) which approximates outer-level gradients by zeroing out second derivative terms, yielding significant speed gains and requiring only constant memory as $r$ varies. Despite FO-BLO's popularity, there is a lack of theoretical understanding of its convergence properties. We make progress by demonstrating a rich family of examples where FO-BLO-based stochastic optimization does not converge to a stationary point of the BLO objective. We address this concern by proposing a new FO-BLO-based unbiased estimate of outer-level gradients, enabling us to theoretically guarantee this convergence, with no harm to memory and expected time complexity. Our findings are supported by experimental results on Omniglot and Mini-ImageNet, popular few-shot meta-learning benchmarks.

References in corpus (23)

• Auto-Encoding Variational Bayes
• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Categorical Reparameterization with Gumbel-Softmax
• DARTS: Differentiable Architecture Search
• Normalizing Flows: An Introduction and Review of Current Methods
• Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism
• Training Deep Nets with Sublinear Memory Cost
• Variational Dropout and the Local Reparameterization Trick
• Adversarial Attacks on Graph Neural Networks via Meta Learning
• Reformer: The Efficient Transformer
• Meta-Learning with Implicit Gradients
• The Reversible Residual Network: Backpropagation Without Storing Activations
• REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models
• On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization
• Online Meta-Learning
• Iterative Methods for Computing Eigenvalues and Eigenvectors
• Unbiasing Truncated Backpropagation Through Time
• Optimizing Millions of Hyperparameters by Implicit Differentiation
• Graph Normalizing Flows
• Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning
• Estimating the Hessian by Back-propagating Curvature
• Truncated Back-propagation for Bilevel Optimization
• Enabling user-driven Checkpointing strategies in Reverse-mode Automatic Differentiation

Cited by in corpus (4)

• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning
• Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks
• A Markov Decision Process Approach to Active Meta Learning