# Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Sep 2020.

## Built on by (most cited first, 28 of 28)

- [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)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (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)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [Will Bilevel Optimizers Benefit from Loops](https://mlsanity.com/paper/2205.14224/) (2022)
- [Enhanced Bilevel Optimization via Bregman Distance](https://mlsanity.com/paper/2107.12301/) (2021)
- [Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2302.03407/) (2023)
- [Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction](https://mlsanity.com/paper/2205.01608/) (2022)
- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [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)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [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)
- [Communication-Efficient Robust Federated Learning with Noisy Labels](https://mlsanity.com/paper/2206.05558/) (2022)
- [Sharpness-Aware Data Poisoning Attack](https://mlsanity.com/paper/2305.14851/) (2023)
- [Non-Convex Bilevel Optimization with Time-Varying Objective Functions](https://mlsanity.com/paper/2308.03811/) (2023)
- [Scalable One-Pass Optimisation of High-Dimensional Weight-Update Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/2110.10461/) (2021)
- [A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and Nonsmooth Bi-level Optimization](https://mlsanity.com/paper/2203.16615/) (2022)
- [Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis](https://mlsanity.com/paper/2410.05140/) (2024)
- [Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2604.04090/) (2026)
- [A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming](https://mlsanity.com/paper/2211.04088/) (2022)
- [Achieving O(ε-1.5) Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization](https://mlsanity.com/paper/2312.03807/) (2023)
- [On Stability and Generalization of Bilevel Optimization Problem](https://mlsanity.com/paper/2210.01063/) (2022)
- [DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2606.21153/) (2026)

## Abstract (arXiv)

Due to the hierarchical structure of many machine learning problems, bilevel programming is becoming more and more important recently, however, the complicated correlation between the inner and outer problem makes it extremely challenging to solve. Although several intuitive algorithms based on the automatic differentiation have been proposed and obtained success in some applications, not much attention has been paid to finding the optimal formulation of the bilevel model. Whether there exists a better formulation is still an open problem. In this paper, we propose an improved bilevel model which converges faster and better compared to the current formulation. We provide theoretical guarantee and evaluation results over two tasks: Data Hyper-Cleaning and Hyper Representation Learning. The empirical results show that our model outperforms the current bilevel model with a great margin. emphThis is a concurrent work with citetliu2020generic and we submitted to ICML 2020. Now we put it on the arxiv for record.