# Enhanced Bilevel Optimization via Bregman Distance

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 53 references that are in the map.
- First posted on arXiv 26 Jul 2021.

## Builds on (most cited first, 28 of 28)

- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [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)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [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)
- [A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton](https://mlsanity.com/paper/2006.04045/) (2020)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization](https://mlsanity.com/paper/2106.07991/) (2021)
- [Deep Bilevel Learning](https://mlsanity.com/paper/1809.01465/) (2018)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021)
- [Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee](https://mlsanity.com/paper/2009.00690/) (2020)
- [A General Descent Aggregation Framework for Gradient-based Bi-level Optimization](https://mlsanity.com/paper/2102.07976/) (2021)
- [On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1806.04781/) (2018)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization](https://mlsanity.com/paper/2106.16101/) (2021)
- [On ℓp-hyperparameter Learning via Bilevel Nonsmooth Optimization](https://mlsanity.com/paper/1806.01520/) (2018)
- [On the Adaptivity of Stochastic Gradient-Based Optimization](https://mlsanity.com/paper/1904.04480/) (2019)

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

- [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)
- [PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2308.02585/) (2023)
- [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 Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization](https://mlsanity.com/paper/2302.08766/) (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)
- [On Momentum-Based Gradient Methods for Bilevel Optimization with Nonconvex Lower-Level](https://mlsanity.com/paper/2303.03944/) (2023)
- [Communication-Efficient Robust Federated Learning with Noisy Labels](https://mlsanity.com/paper/2206.05558/) (2022)
- [Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization](https://mlsanity.com/paper/2407.17823/) (2024)
- [Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity](https://mlsanity.com/paper/2405.19697/) (2024)
- [Projection-Free Algorithm for Stochastic Bi-level Optimization](https://mlsanity.com/paper/2110.11721/) (2021)
- [Communication-Efficient Federated Bilevel Optimization with Local and Global Lower Level Problems](https://mlsanity.com/paper/2302.06701/) (2023)
- [Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization](https://mlsanity.com/paper/2305.18730/) (2023)
- [Moreau Envelope Based Difference-of-weakly-Convex Reformulation and Algorithm for Bilevel Programs](https://mlsanity.com/paper/2306.16761/) (2023)
- [A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and Nonsmooth Bi-level Optimization](https://mlsanity.com/paper/2203.16615/) (2022)
- [Fast Adaptive Federated Bilevel Optimization](https://mlsanity.com/paper/2211.01122/) (2022)
- [Spurious Stationarity and Hardness Results for Bregman Proximal-Type Algorithms](https://mlsanity.com/paper/2404.08073/) (2024)
- [A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming](https://mlsanity.com/paper/2211.04088/) (2022)
- [Adaptive Mirror Descent Bilevel Optimization](https://mlsanity.com/paper/2311.04520/) (2023)
- [Online Nonconvex Bilevel Optimization with Bregman Divergences](https://mlsanity.com/paper/2409.10470/) (2024)
- [On the Convergence of Momentum-Based Algorithms for Federated Bilevel Optimization Problems](https://mlsanity.com/paper/2204.13299/) (2022)
- [Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling](https://mlsanity.com/paper/2411.05868/) (2024)
- [Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization](https://mlsanity.com/paper/2602.06457/) (2026)
- [Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems](https://mlsanity.com/paper/2605.08006/) (2026)
- [Riemannian Manifold Learning for Stackelberg Games with Neural Flow Representations](https://mlsanity.com/paper/2502.05498/) (2025)
- [Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs](https://mlsanity.com/paper/2605.01242/) (2026)

## Abstract (arXiv)

Bilevel optimization has been recently used in many machine learning problems such as hyperparameter optimization, policy optimization, and meta learning. Although many bilevel optimization methods have been proposed, they still suffer from the high computational complexities and do not consider the more general bilevel problems with nonsmooth regularization. In the paper, thus, we propose a class of enhanced bilevel optimization methods with using Bregman distance to solve bilevel optimization problems, where the outer subproblem is nonconvex and possibly nonsmooth, and the inner subproblem is strongly convex. Specifically, we propose a bilevel optimization method based on Bregman distance (BiO-BreD) to solve deterministic bilevel problems, which achieves a lower computational complexity than the best known results. Meanwhile, we also propose a stochastic bilevel optimization method (SBiO-BreD) to solve stochastic bilevel problems based on stochastic approximated gradients and Bregman distance. Moreover, we further propose an accelerated version of SBiO-BreD method (ASBiO-BreD) using the variance-reduced technique, which can achieve a lower computational complexity than the best known computational complexities with respect to condition number kappa and target accuracy ε for finding an ε-stationary point. We conduct data hyper-cleaning task and hyper-representation learning task to demonstrate that our new algorithms outperform related bilevel optimization approaches.