# Penalty Method for Inversion-Free Deep Bilevel Optimization

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2019.

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

- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [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)
- [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)
- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [HYDRA: Hypergradient Data Relevance Analysis for Interpreting Deep Neural Networks](https://mlsanity.com/paper/2102.02515/) (2021)
- [On Implicit Bias in Overparameterized Bilevel Optimization](https://mlsanity.com/paper/2212.14032/) (2022)
- [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)
- [An Optimization-Based Meta-Learning Model for MRI Reconstruction with Diverse Dataset](https://mlsanity.com/paper/2110.00715/) (2021)
- [A Learnable Variational Model for Joint Multimodal MRI Reconstruction and Synthesis](https://mlsanity.com/paper/2204.03804/) (2022)
- [On Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Level](https://mlsanity.com/paper/2303.03944/) (2023)
- [Asynchronous Distributed Bilevel Optimization](https://mlsanity.com/paper/2212.10048/) (2022)
- [Understanding the Limits of Unsupervised Domain Adaptation via Data Poisoning](https://mlsanity.com/paper/2107.03919/) (2021)
- [Communication-Efficient Robust Federated Learning with Noisy Labels](https://mlsanity.com/paper/2206.05558/) (2022)
- [First-Order Methods for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2406.12771/) (2024)
- [INTERACT: Achieving Low Sample and Communication Complexities in Decentralized Bilevel Learning over Networks](https://mlsanity.com/paper/2207.13283/) (2022)
- [Scalable One-Pass Optimisation of High-Dimensional Weight-Update Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/2110.10461/) (2021)
- [DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization](https://mlsanity.com/paper/2212.02376/) (2022)
- [A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints](https://mlsanity.com/paper/2406.10148/) (2024)
- [PCENet: High Dimensional Surrogate Modeling for Learning Uncertainty](https://mlsanity.com/paper/2202.05063/) (2022)
- [A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2306.02422/) (2023)
- [Effective Bilevel Optimization via Minimax Reformulation](https://mlsanity.com/paper/2305.13153/) (2023)
- [A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming](https://mlsanity.com/paper/2211.04088/) (2022)
- [Multi-Objective Bilevel Learning](https://mlsanity.com/paper/2511.07824/) (2025)
- [Bilevel Optimization for Neural Architecture Search](https://mlsanity.com/paper/2606.29582/) (2026)
- [A Globally Convergent Gradient-based Bilevel Hyperparameter Optimization Method](https://mlsanity.com/paper/2208.12118/) (2022)
- [Hyperparameter Tuning Through Pessimistic Bilevel Optimization](https://mlsanity.com/paper/2412.03666/) (2024)

## Abstract (arXiv)

Solving a bilevel optimization problem is at the core of several machine learning problems such as hyperparameter tuning, data denoising, meta- and few-shot learning, and training-data poisoning. Different from simultaneous or multi-objective optimization, the steepest descent direction for minimizing the upper-level cost in a bilevel problem requires the inverse of the Hessian of the lower-level cost. In this work, we propose a novel algorithm for solving bilevel optimization problems based on the classical penalty function approach. Our method avoids computing the Hessian inverse and can handle constrained bilevel problems easily. We prove the convergence of the method under mild conditions and show that the exact hypergradient is obtained asymptotically. Our method's simplicity and small space and time complexities enable us to effectively solve large-scale bilevel problems involving deep neural networks. We present results on data denoising, few-shot learning, and training-data poisoning problems in a large-scale setting. Our results show that our approach outperforms or is comparable to previously proposed methods based on automatic differentiation and approximate inversion in terms of accuracy, run-time, and convergence speed.