Truncated Back-propagation for Bilevel Optimization

Abstract

Bilevel optimization has been recently revisited for designing and analyzing algorithms in hyperparameter tuning and meta learning tasks. However, due to its nested structure, evaluating exact gradients for high-dimensional problems is computationally challenging. One heuristic to circumvent this difficulty is to use the approximate gradient given by performing truncated back-propagation through the iterative optimization procedure that solves the lower-level problem. Although promising empirical performance has been reported, its theoretical properties are still unclear. In this paper, we analyze the properties of this family of approximate gradients and establish sufficient conditions for convergence. We validate this on several hyperparameter tuning and meta learning tasks. We find that optimization with the approximate gradient computed using few-step back-propagation often performs comparably to optimization with the exact gradient, while requiring far less memory and half the computation time.

References in corpus (8)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Practical Bayesian Optimization of Machine Learning Algorithms
• Prototypical Networks for Few-shot Learning
• Insights into analysis operator learning: From patch-based sparse models to higher-order MRFs
• On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization
• Scalable Gradient-Based Tuning of Continuous Regularization Hyperparameters
• Learning to Optimize Neural Nets
• Enabling user-driven Checkpointing strategies in Reverse-mode Automatic Differentiation

Cited by in corpus (7)

• Meta-Learning Update Rules for Unsupervised Representation Learning
• Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee
• Delta-STN: Efficient Bilevel Optimization for Neural Networks using Structured Response Jacobians
• UFO-BLO: Unbiased First-Order Bilevel Optimization
• Gradient-based algorithms for multi-objective bi-level optimization
• Learning Composable Energy Surrogates for PDE Order Reduction
• Efficient Gradient Approximation Method for Constrained Bilevel Optimization