2018

Truncated Back-propagation for Bilevel Optimization

Shaban, Amirreza, Cheng, Ching-An, Hatch, Nathan et al.

Understand

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.

Built on

Principles of Mathematical Analysis , volume 3
Walter Rudin · 1964
Earlier work this paper cites.
Matrix analysis
Roger A Horn and Charles R Johnson · 1990
Earlier work this paper cites.
An introduction to the conjugate gradient method without the agonizing pain, 1994
Jonathan Richard Shewchuk · 1994
Earlier work this paper cites.
Design and regularization of neural networks: the optimal use of a validation set
Jan Larsen, Lars Kai Hansen, Claus Svarer, and M Ohlsson · 1996
Earlier work this paper cites.
Multitask learning
Rich Caruana · 1998
Earlier work this paper cites.
Gradient-based learning applied to document recognition
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner · 1998
Earlier work this paper cites.
Gradient-based optimization of hyperparameters
Yoshua Bengio · 2000
Earlier work this paper cites.
Fields of experts: A framework for learning image priors
Stefan Roth and Michael J Black · 2005
Earlier work this paper cites.
Learning multiple tasks with kernel methods
Theodoros Evgeniou, Charles A Micchelli, and Massimiliano Pontil · 2005
Earlier work this paper cites.
One-shot learning of object categories
Li Fei-Fei, Rob Fergus, and Pietro Perona · 2006
Earlier work this paper cites.
Enabling user-driven checkpointing strategies in reverse-mode automatic differentiation
Laurent Hascoet and Mauricio Araya-Polo · 2006
Earlier work this paper cites.
Imagenet: A large-scale hierarchical image database
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei · 2009
Earlier work this paper cites.

Similar

Gaussian process optimization in the bandit setting: No regret and experimental design
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger · 2010
Cited alongside, same era.
Generic methods for optimization-based modeling
Justin Domke · 2012
Cited alongside, same era.
Random search for hyper-parameter optimization
James Bergstra and Yoshua Bengio · 2012
Cited alongside, same era.
Practical bayesian optimization of machine learning algorithms
Jasper Snoek, Hugo Larochelle, and Ryan P Adams · 2012
Cited alongside, same era.
Insights into analysis operator learning: From patch-based sparse models to higher order mrfs
Yunjin Chen, Rene Ranftl, and Thomas Pock · 2014
Cited alongside, same era.
Gradient-based hyperparameter optimization through reversible learning
Dougal Maclaurin, David Duvenaud, and Ryan Adams · 2015
Cited alongside, same era.
Human-level concept learning through probabilistic program induction
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum · 2015
Cited alongside, same era.
Adam: A method for stochastic optimization
Diederik P Kingma and Jimmy Ba · 2015
Cited alongside, same era.
Hyperparameter optimization with approximate gradient
Fabian Pedregosa · 2016
Cited alongside, same era.
On differentiating parameterized argmin and argmax problems with application to bi-level optimization
Original
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo · 2016
Cited alongside, same era.
Scalable gradient-based tuning of continuous regularization hyperparameters
Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko · 2016
Cited alongside, same era.
Forward and reverse gradient-based hyperparameter optimization
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil
Cited in the paper.

Then

Learning to learn by gradient descent by gradient descent
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, and Nando de Freitas · 2016
Later among the works it cites.
Introduction to online convex optimization
Elad Hazan et al · 2016
Later among the works it cites.
Deep residual learning for image recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun · 2016
Later among the works it cites.
A bridge between hyperparameter optimization and larning-to-learn
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil · 2017
Later among the works it cites.
Hyperface: A deep multi-task learning framework for face detection, landmark localization, pose estimation, and gender recognition
Rajeev Ranjan, Vishal M Patel, and Rama Chellappa · 2017
Later among the works it cites.
Optimization as a model for few-shot learning
Sachin Ravi and Hugo Larochelle · 2017
Later among the works it cites.
Prototypical networks for few-shot learning
Jake Snell, Kevin Swersky, and Richard S Zemel · 2017
Later among the works it cites.
Model-agnostic meta-learning for fast adaptation of deep networks
Chelsea Finn, Pieter Abbeel, and Sergey Levine · 2017
Later among the works it cites.
Learning to optimize neural nets
Original
Ke Li and Jitendra Malik · 2017
Later among the works it cites.
Automatic differentiation in machine learning: A survey
Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind · 2017
Later among the works it cites.
Online learning rate adaptation with hypergradient descent
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…