# Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 60 references that are in the map.
- First posted on arXiv 1 Oct 2021.

## Builds on (most cited first, 30 of 39)

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [Matching Networks for One Shot Learning](https://mlsanity.com/paper/1606.04080/) (2016)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Learning to Compare: Relation Network for Few-Shot Learning](https://mlsanity.com/paper/1711.06025/) (2017)
- [On First-Order Meta-Learning Algorithms](https://mlsanity.com/paper/1803.02999/) (2018)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Meta-Learning for Semi-Supervised Few-Shot Classification](https://mlsanity.com/paper/1803.00676/) (2018)
- [TADAM: Task dependent adaptive metric for improved few-shot learning](https://mlsanity.com/paper/1805.10123/) (2018)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAML](https://mlsanity.com/paper/1909.09157/) (2019)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluation](https://mlsanity.com/paper/1904.12760/) (2019)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms](https://mlsanity.com/paper/1908.10400/) (2019)
- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [DARTS+: Improved Differentiable Architecture Search with Early Stopping](https://mlsanity.com/paper/1909.06035/) (2019)
- [Meta-Learning with Warped Gradient Descent](https://mlsanity.com/paper/1909.00025/) (2019)
- [A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton](https://mlsanity.com/paper/2006.04045/) (2020)
- [Meta-Curvature](https://mlsanity.com/paper/1902.03356/) (2019)
- [Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters](https://mlsanity.com/paper/2006.09486/) (2020)
- [A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization](https://mlsanity.com/paper/2106.07991/) (2021)

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

- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [A Fully First-Order Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2301.10945/) (2023)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [SEAL: Safety-enhanced Aligned LLM Fine-tuning via Bilevel Data Selection](https://mlsanity.com/paper/2410.07471/) (2024)
- [A Task-guided, Implicitly-searched and Meta-initialized Deep Model for Image Fusion](https://mlsanity.com/paper/2305.15862/) (2023)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis](https://mlsanity.com/paper/2301.00712/) (2023)
- [Will Bilevel Optimizers Benefit from Loops](https://mlsanity.com/paper/2205.14224/) (2022)
- [On the Convergence Theory for Hessian-Free Bilevel Algorithms](https://mlsanity.com/paper/2110.07004/) (2021)
- [PR-Attack: Coordinated Prompt-RAG Attacks on Retrieval-Augmented Generation in Large Language Models via Bilevel Optimization](https://mlsanity.com/paper/2504.07717/) (2025)
- [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023)
- [Betty: An Automatic Differentiation Library for Multilevel Optimization](https://mlsanity.com/paper/2207.02849/) (2022)
- [Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2302.03407/) (2023)
- [PAIF: Perception-Aware Infrared-Visible Image Fusion for Attack-Tolerant Semantic Segmentation](https://mlsanity.com/paper/2308.03979/) (2023)
- [Bilevel Fast Scene Adaptation for Low-Light Image Enhancement](https://mlsanity.com/paper/2306.01343/) (2023)
- [Functional Bilevel Optimization for Machine Learning](https://mlsanity.com/paper/2403.20233/) (2024)
- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm](https://mlsanity.com/paper/2401.16164/) (2024)
- [Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy](https://mlsanity.com/paper/2405.09927/) (2024)
- [Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomy](https://mlsanity.com/paper/2406.16087/) (2024)
- [Value Function Based Difference-of-Convex Algorithm for Bilevel Hyperparameter Selection Problems](https://mlsanity.com/paper/2206.05976/) (2022)
- [Efficient Gradient Approximation Method for Constrained Bilevel Optimization](https://mlsanity.com/paper/2302.01970/) (2023)
- [Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis](https://mlsanity.com/paper/2401.09587/) (2024)
- [On Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Level](https://mlsanity.com/paper/2303.03944/) (2023)
- [SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learning](https://mlsanity.com/paper/2305.19442/) (2023)
- [A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima](https://mlsanity.com/paper/2203.01123/) (2022)
- [Is Bayesian Model-Agnostic Meta Learning Better than Model-Agnostic Meta Learning, Provably?](https://mlsanity.com/paper/2203.03059/) (2022)
- [Asynchronous Distributed Bilevel Optimization](https://mlsanity.com/paper/2212.10048/) (2022)
- [Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2308.07536/) (2023)

## Abstract (arXiv)

In recent years, Bi-Level Optimization (BLO) techniques have received extensive attentions from both learning and vision communities. A variety of BLO models in complex and practical tasks are of non-convex follower structure in nature (a.k.a., without Lower-Level Convexity, LLC for short). However, this challenging class of BLOs is lack of developments on both efficient solution strategies and solid theoretical guarantees. In this work, we propose a new algorithmic framework, named Initialization Auxiliary and Pessimistic Trajectory Truncated Gradient Method (IAPTT-GM), to partially address the above issues. In particular, by introducing an auxiliary as initialization to guide the optimization dynamics and designing a pessimistic trajectory truncation operation, we construct a reliable approximate version of the original BLO in the absence of LLC hypothesis. Our theoretical investigations establish the convergence of solutions returned by IAPTT-GM towards those of the original BLO without LLC. As an additional bonus, we also theoretically justify the quality of our IAPTT-GM embedded with Nesterov's accelerated dynamics under LLC. The experimental results confirm both the convergence of our algorithm without LLC, and the theoretical findings under LLC.