# Truncated Back-propagation for Bilevel Optimization

arXiv: https://arxiv.org/abs/1810.10667 · HTML: https://mlsanity.com/paper/1810.10667/

## Key facts

- Cited by 190 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Oct 2018.

## Built on by (most cited first, 30 of 190)

- [Graph Contrastive Learning Automated](https://mlsanity.com/paper/2106.07594/) (2021)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [Is Attention Better Than Matrix Decomposition?](https://mlsanity.com/paper/2109.04553/) (2021)
- [On Training Implicit Models](https://mlsanity.com/paper/2111.05177/) (2021)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Trace is the Next AutoDiff: Generative Optimization with Rich Feedback, Execution Traces, and LLMs](https://mlsanity.com/paper/2406.16218/) (2024)
- [Theseus: A Library for Differentiable Nonlinear Optimization](https://mlsanity.com/paper/2207.09442/) (2022)
- [Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond](https://mlsanity.com/paper/2110.00455/) (2021)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization](https://mlsanity.com/paper/2106.07991/) (2021)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [Improving Object-centric Learning with Query Optimization](https://mlsanity.com/paper/2210.08990/) (2022)
- [Advancing Model Pruning via Bi-level Optimization](https://mlsanity.com/paper/2210.04092/) (2022)
- [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021)
- [Unbiased Gradient Estimation in Unrolled Computation Graphs with Persistent Evolution Strategies](https://mlsanity.com/paper/2112.13835/) (2021)
- [iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradients](https://mlsanity.com/paper/2106.10784/) (2021)
- [Self-Guided Noise-Free Data Generation for Efficient Zero-Shot Learning](https://mlsanity.com/paper/2205.12679/) (2022)
- [AutoBalance: Optimized Loss Functions for Imbalanced Data](https://mlsanity.com/paper/2201.01212/) (2022)
- [Object Representations as Fixed Points: Training Iterative Refinement Algorithms with Implicit Differentiation](https://mlsanity.com/paper/2207.00787/) (2022)
- [Model Agnostic Sample Reweighting for Out-of-Distribution Learning](https://mlsanity.com/paper/2301.09819/) (2023)
- [Challenging Forgets: Unveiling the Worst-Case Forget Sets in Machine Unlearning](https://mlsanity.com/paper/2403.07362/) (2024)
- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [Multi-Objective Meta Learning](https://mlsanity.com/paper/2102.07121/) (2021)

## Abstract (arXiv)

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.