# First-order penalty methods for bilevel optimization

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 75 references that are in the map.
- First posted on arXiv 4 Jan 2023.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Gradient Episodic Memory for Continual Learning](https://mlsanity.com/paper/1706.08840/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [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)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [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)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications](https://mlsanity.com/paper/1705.06270/) (2017)
- [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 Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters](https://mlsanity.com/paper/2006.09486/) (2020)
- [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021)
- [Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization](https://mlsanity.com/paper/2105.02266/) (2021)
- [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021)
- [An accelerated inexact proximal point method for solving nonconvex-concave min-max problems](https://mlsanity.com/paper/1905.13433/) (2019)
- [Bilevel methods for image reconstruction](https://mlsanity.com/paper/2109.09610/) (2021)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [Difference of convex algorithms for bilevel programs with applications in hyperparameter selection](https://mlsanity.com/paper/2102.09006/) (2021)
- [A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization](https://mlsanity.com/paper/2003.04375/) (2020)

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

- [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)
- [On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation](https://mlsanity.com/paper/2309.01753/) (2023)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweighting](https://mlsanity.com/paper/2406.19976/) (2024)
- [Unleashing the Power of Data Tsunami: A Comprehensive Survey on Data Assessment and Selection for Instruction Tuning of Language Models](https://mlsanity.com/paper/2408.02085/) (2024)
- [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)
- [Efficient Fine-Tuning and Concept Suppression for Pruned Diffusion Models](https://mlsanity.com/paper/2412.15341/) (2024)
- [On Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Level](https://mlsanity.com/paper/2303.03944/) (2023)
- [On the Complexity of First-Order Methods in Stochastic Bilevel Optimization](https://mlsanity.com/paper/2402.07101/) (2024)
- [Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization](https://mlsanity.com/paper/2407.17823/) (2024)
- [First-Order Methods for Linearly Constrained Bilevel Optimization](https://mlsanity.com/paper/2406.12771/) (2024)
- [A first-order augmented Lagrangian method for constrained minimax optimization](https://mlsanity.com/paper/2301.02060/) (2023)
- [Direct Prediction Set Minimization via Bilevel Conformal Classifier Training](https://mlsanity.com/paper/2506.06599/) (2025)
- [Safety at One Shot: Patching Fine-Tuned LLMs with A Single Instance](https://mlsanity.com/paper/2601.01887/) (2026)
- [A Generalized Alternating Method for Bilevel Learning under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2306.02422/) (2023)
- [Bilevel ZOFO: Efficient LLM Fine-Tuning and Meta-Training](https://mlsanity.com/paper/2502.03604/) (2025)
- [LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace](https://mlsanity.com/paper/2404.03331/) (2024)
- [A First-order Generative Bilevel Optimization Framework for Diffusion Models](https://mlsanity.com/paper/2502.08808/) (2025)
- [Solving bilevel optimization via sequential minimax optimization](https://mlsanity.com/paper/2511.07398/) (2025)
- [Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles](https://mlsanity.com/paper/2511.19656/) (2025)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)
- [Adaptive Mirror Descent Bilevel Optimization](https://mlsanity.com/paper/2311.04520/) (2023)
- [Differentially Private Bilevel Optimization](https://mlsanity.com/paper/2409.19800/) (2024)
- [Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization](https://mlsanity.com/paper/2509.15399/) (2025)
- [Bilevel Data Curation for LLM Fine-tuning: Offline Selection and Online Self-Refining Generation](https://mlsanity.com/paper/2511.21056/) (2025)
- [Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates](https://mlsanity.com/paper/2506.12994/) (2025)
- [Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization](https://mlsanity.com/paper/2509.02937/) (2025)

## Abstract (arXiv)

In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower level is a possibly nonsmooth convex optimization problem, while the upper level is a possibly nonconvex optimization problem. We introduce a notion of varepsilon-KKT solution for them and show that an varepsilon-KKT solution leads to an O(√varepsilon)- or O(varepsilon)-hypergradient based stionary point under suitable assumptions. We also propose first-order penalty methods for finding an varepsilon-KKT solution of them, whose subproblems turn out to be a structured minimax problem and can be suitably solved by a first-order method recently developed by the authors. Under suitable assumptions, an operation complexity of O(varepsilon-4logvarepsilon-1) and O(varepsilon-7logvarepsilon-1), measured by their fundamental operations, is established for the proposed penalty methods for finding an varepsilon-KKT solution of the unconstrained and constrained bilevel optimization problems, respectively. Preliminary numerical results are presented to illustrate the performance of our proposed methods. To the best of our knowledge, this paper is the first work to demonstrate that bilevel optimization can be approximately solved as minimax optimization, and moreover, it provides the first implementable method with complexity guarantees for such sophisticated bilevel optimization.