Truncated Back-propagation for Bilevel Optimization

By Amirreza Shaban, Ching-An Cheng, Nathan Hatch, Byron Boots. 2018

334 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

AutoHAS: Differentiable Hyper-parameter and Architecture Search (2020, methodology): “Following that, different approximation methods have been proposed [33, 37, 42].”
Online Meta-Learning (2019, positive): “5 includes only one gradient step, we observed that it is beneﬁcial to take multiple gradient steps in the inner loop (i.e., in U t ), which is consistent with prior works (Finn et al., 2017; Grant et al., 2018; Antoniou et al., 2018; Shaban et al., 2018).”
Meta-Learning in Neural Networks: A Survey (2020, background): “Popular solutions include implicit differentiation of v [154], [163], [293], forward-mode differentiation of v [67], [69], [294], gradient preconditioning [105], evolutionary strategies [295], solving for a greedy version of v online by alternating inner and outer steps [21], [42], [198], truncation”
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, background): “Copyright 2023 by the author(s). of problems has attracted great attention due to their applications in hyper-parameter optimization (Franceschi et al., 2018; Shaban et al., 2019), meta-learning (Rajeswaran et al., 2019; Bertinetto et al., 2019), and reinforcement learning (Hong et al., 2020).”
Super-efficiency of automatic differentiation for functions defined as a minimum (2020, methodology): “Note that truncated backpropagation (Shaban et al., 2019) can also be used to reduce the memory cost of using automatic differentiation, with approximation.”
Optimizing Millions of Hyperparameters by Implicit Differentiation (2019, methodology): “We save memory because we reuse last w i times, while [7] needs the last i w ’s. Scaling the Hessian by the learning rate α is key for convergence.”
Bilevel Optimization: Convergence Analysis and Enhanced Design (2020, methodology): “For example, for the data hyper-cleaning application proposed by Franceschi et al. 2018; Shaban et al. 2019, the predictor is modeled by a linear classiﬁer, and the loss function L ( w ; ξ ) is convex w.r.t. w and R w,λ is a strongly-convex regularizer, e.g., L 2 regularization.”
Meta-Learning Update Rules for Unsupervised Representation Learning (2018, methodology): “To improve stability and reduce the computational cost we approximate the gradients ∂ [ MetaObjective ] ∂θ via truncated backprop through time (Shaban et al., 2018).”
Meta-Learning with Implicit Gradients (2019, methodology): “Truncated backprop [53] also invokes A lg i to obtain a δ -approximate solution but instead performs a truncated or partial back-propagation so that it uses a smaller number of iterations when computing the gradient through the path of A lg i ( θ ) .”
iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradients (2021, methodology): “(24), we have Based Assumption 1.3, we have and based Assumption 2.2 that we have Based on Assumption 1.3, we know is also bounded by (cid:107)∇ α w ( α ) (cid:107) ≤ L w .”
Graph Contrastive Learning Automated (2021, methodology): “…(Srinivas et al., 2010; Snoek et al., 2012), automatic differentiation (Luketina et al., 2016; Franceschi et al., 2017; Baydin et al., 2017; Shaban et al., 2019), or ﬁrst-order techniques based on some inner-loop approximated solution (Maclaurin et al., 2015; Pedregosa, 2016; Gould et al.,…”
MetaPoison: Practical General-purpose Clean-label Data Poisoning (2020, methodology): “K-step methods have been found to have exponentially decreasing approximation error [Shaban et al., 2019] and generalization benefits [Franceschi et al.”
AutoHAS: Efficient Hyperparameter and Architecture Search. (2020, methodology): “Despite of their efﬁciency, they can only be applied to differentiable hyperparameters such as weight decay, but not non-differentiable hyperparameters, such as learning rate (Lorraine et al., 2020) or optimizer (Shaban et al., 2019).”