Truncated Back-propagation for Bilevel Optimization (2018-10-25T00:00:00.000000Z)

TL;DR

It is found that optimization with the approximate gradient computed using few-step back-propagation often performs comparably to optimized with the exact gradient, while requiring far less memory and half the computation time.

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.

Authors

Byron Boots

4 papers

Amirreza Shaban

2 papers

Ching-An Cheng

1 papers

TL;DR

Abstract

Authors

References38 items

Descent

A Bridge Between Hyperparameter Optimization and Larning-to-learn

Prototypical Networks for Few-shot Learning

Online Learning Rate Adaptation with Hypergradient Descent

Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks

Forward and Reverse Gradient-Based Hyperparameter Optimization

Learning to Optimize Neural Nets

Optimization as a Model for Few-Shot Learning

Introduction to Online Convex Optimization

On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization

Learning to learn by gradient descent by gradient descent

Hyperparameter optimization with approximate gradient

Human-level concept learning through probabilistic program induction

Deep Residual Learning for Image Recognition

Scalable Gradient-Based Tuning of Continuous Regularization Hyperparameters

Automatic differentiation in machine learning: a survey

Gradient-based Hyperparameter Optimization through Reversible Learning

Adam: A Method for Stochastic Optimization

Insights Into Analysis Operator Learning: From Patch-Based Sparse Models to Higher Order MRFs

Practical Bayesian Optimization of Machine Learning Algorithms

Generic Methods for Optimization-Based Modeling

Random Search for Hyper-Parameter Optimization

ImageNet: A large-scale hierarchical image database

Enabling user-driven Checkpointing strategies in Reverse-mode Automatic Differentiation

One-shot learning of object categories

Learning Multiple Tasks with Kernel Methods

Fields of Experts: a framework for learning image priors

Economic inequality and burden-sharing in the provision of local environmental quality

Gradient-Based Optimization of Hyperparameters

Multitask Learning

Design and regularization of neural networks: the optimal use of a validation set

An Introduction to the Conjugate Gradient Method Without the Agonizing Pain

HyperFace: A Deep Multi-Task Learning Framework for Face Detection, Landmark Localization, Pose Estimation, and Gender Recognition

Learning to learn by gradient descent by gradient descent

Automatic di↵erentiation in machine Truncated Back-propagation for Bilevel Optimization learning: A survey

Gaussian process optimization in the bandit setting: No regret and experimental design

Gradient-based learning applied to document recognition

Principles of Mathematical Analysis , volume 3

Field of Study

Venue Information

Name

Type

URL

Alternate Names