BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach

Bo LiuMao YeStephen WrightPeter StoneQiang Liu

article2022NeurIPS168 citations

Presents a fast, fully first-order bilevel optimization algorithm that bypasses expensive Hessian calculations through a value-function reformulation, backed by non-asymptotic convergence guarantees for non-convex deep learning objectives.

Listen

Modern machine learning applications—including automated hyperparameter tuning, meta-learning, and continual learning—frequently rely on bilevel optimization, a framework where an outer objective is optimized subject to the solution of an inner minimization problem. However, traditional bilevel methods are computationally expensive and impractical for large-scale deep learning because they require calculating complex second-order derivatives (such as Hessian matrices) or unrolling long optimization paths. While fully first-order alternatives have been sought, existing options either fail to converge reliably to correct solutions or suffer from extreme hyperparameter sensitivity on practical problems.

The article designs and evaluates a simple, efficient, fully first-order bilevel optimization algorithm, termed Bilevel Optimization Made Easy (BOME), that avoids second-order derivative calculations entirely and remains effective for large-scale, non-convex objectives. The authors formulate bilevel optimization as a single-level constrained problem using a value-function approach, which mathematically eliminates the need for implicit differentiation. They solve this formulation by employing a dynamic barrier gradient descent method that alternately optimizes the primary objective while driving constraint violations toward zero, approximating the optimal inner variable via a short sequence of standard gradient descent steps without backpropagating through the optimization trajectory. The method was rigorously tested across theoretical convergence proofs, three benchmark toy problems, and three real-world machine learning tasks (data hyper-cleaning on image datasets, learnable regularization on text classification, and continual learning benchmarks).

The evaluation yielded several key findings. First, the proposed method establishes the first known non-asymptotic convergence rate for a fully first-order bilevel algorithm under general non-convex settings. Second, across toy challenges (including mini-max games and degenerate inner problems), the method reliably converged to true global optima where existing first-order and penalty baselines failed. Third, in real-world hyperparameter tuning and text classification tasks, the approach converged significantly faster while matching or exceeding the accuracy of state-of-the-art methods, showing especially large efficiency gains in high-dimensional settings. Fourth, when integrated into continual learning pipelines, the method boosted overall test accuracy (e.g., from 78.40% to 80.70% on Permuted MNIST) and reduced catastrophic forgetting (reducing negative backward transfer from 5.62 to 4.09) compared to standard implicit gradient methods.

These results demonstrate that organizations can execute complex bilevel workflows at a fraction of the computational and memory overhead required by traditional Hessian-based approaches. By eliminating complex matrix inversions and sensitive barrier tuning, the method substantially reduces infrastructure costs and engineering complexity for large neural network pipelines. Decision-makers should consider adopting this approach as a drop-in optimizer for large-scale hyperparameter tuning, model weighting, and lifelong learning systems.

For practical deployment, technical teams are recommended to implement the method using standard first-order optimizers (such as Adam) and default hyperparameter settings, noting that running as few as 1 to 10 inner steps is sufficient in practice. Future work should explore bridging the gap between theoretical inner-loop requirements and its superior empirical efficiency, as well as testing performance on larger, distributed foundation models.

Sony Corporation University of Texas at Austin University of Wisconsin Madison optimization optimization problems bilevel optimization first-order bilevel optimization hypergradient descent

arXiv: 2209.08709 Cranial-XIX/BOME

Paper: On First-Order Meta-Learning Algorithms, Alex Nichol et al. (2018). It analyzes the effectiveness and mechanics of first-order approximations in gradient-based meta-learning, directly motivating the need for scalable first-order bilevel optimization.
Paper: Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks, Chelsea Finn et al. (2017). It establishes the canonical bilevel formulation of gradient-based meta-learning that traditionally relies on differentiating through optimization steps.
Paper: Meta-Learning With Differentiable Convex Optimization, Kwonjoon Lee et al. (2019). It details how implicit differentiation and optimality conditions are conventionally applied to bilevel problems in deep meta-learning, highlighting the computational bottlenecks addressed by BOME.
Paper: Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming, Saeed Ghadimi et al. (2013). It provides the foundational convergence analysis and complexity rates for first-order stochastic optimization on non-convex objectives.
Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). It surveys the theoretical and practical principles of large-scale stochastic first-order methods underpinning modern deep learning optimization.
Paper: Learning to learn by gradient descent by gradient descent, Marcin Andrychowicz et al. (2016). It explores learning-to-learn via gradient-based meta-optimization, framing the structural bilevel problem that motivates simplified first-order techniques.

No sufficiently relevant recommendations were found.

Cover for BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach

Abstract

Bilevel optimization (BO) is useful for solving a variety of important machine learning problems including but not limited to hyperparameter optimization, meta-learning, continual learning, and reinforcement learning. Conventional BO methods need to differentiate through the low-level optimization process with implicit differentiation, which requires expensive calculations related to the Hessian matrix. There has been a recent quest for first-order methods for BO, but the methods proposed to date tend to be complicated and impractical for large-scale deep learning applications. In this work, we propose a simple first-order BO algorithm that depends only on first-order gradient information, requires no implicit differentiation, and is practical and efficient for large-scale non-convex functions in deep learning. We provide a non-asymptotic convergence analysis of the proposed method to stationary points for non-convex objectives and present empirical results that show its superior practical performance.

Topics

optimization optimization problems

Keywords

bilevel optimization first-order bilevel optimization hypergradient descent hyperparameter optimization value-function formulation constrained optimization learnable regularization sequential minimization

1 Introduction
2 Background
3 Method
4 Analysis
4.1 KKT Conditions
4.2 Convergence with unimodal g
4.3 Convergence with multimodal g
5 Related Works
6 Experiment
6.1 Experiment Problems and Results
6.2 Observations
7 Conclusion and Future Work
8 Acknowledgement
References
Societal Impacts
Checklist

Knowls

Knowl 1 — Bilevel Optimization Made Easy Algorithm
algorithm
Bilevel Optimization Made Easy (BOME) is a fully first-order method designed to solve the general bilevel optimization problem:
$\min_{v, \theta} f(v, \theta) \quad \text{s.t.} \quad \theta \in \arg\min_{\theta'} g(v, \theta')$
where $v \in \mathbb{R}^m$ is the outer variable and $\theta \in \mathbb{R}^n$ is the inner variable. BOME reformulates the nested problem into a constrained optimization problem using the value-function approach, relaxing the constraint with a surrogate function $\hat{q}(v, \theta) = g(v, \theta) - g(v, \theta_k^{(T)})$ , where $\theta_k^{(T)}$ is computed via $T$ gradient descent steps on the lower objective and treated as a constant (stop-gradient).
Input: Initial variables ( $v_0 \in \mathbb{R}^m, \theta_0 \in \mathbb{R}^n$ ), inner step count $T \ge 1$ , outer step size $\xi > 0$ , inner step size $\alpha > 0$ (default $\alpha = \xi$ ), control coefficient $\eta > 0$ (default $\eta = 0.5$ )
Output: Optimized variables ( $v_K, \theta_K$ )
for $k = 0, 1, \dots, K-1$ do
     $\theta_k^{(0)} = \theta_k$
    for $t = 0, 1, \dots, T-1$ do
         $\theta_k^{(t+1)} = \theta_k^{(t)} - \alpha \nabla_\theta g(v_k, \theta_k^{(t)})$
    Set $\hat{q}(v, \theta) = g(v, \theta) - g(v, \theta_k^{(T)})$ , treating $\theta_k^{(T)}$ as a constant
    Compute $\nabla \hat{q}(v_k, \theta_k) = (\nabla_{v_k} g(v_k, \theta_k) - \nabla_1 g(v_k, \theta_k^{(T)}), \nabla_{\theta_k} g(v_k, \theta_k))$
    Compute $\nabla f(v_k, \theta_k) = (\nabla_{v_k} f(v_k, \theta_k), \nabla_{\theta_k} f(v_k, \theta_k))$
    Set $\phi_k = \eta \|\nabla \hat{q}(v_k, \theta_k)\|^2$
    if $\|\nabla \hat{q}(v_k, \theta_k)\| == 0$ then
         $\lambda_k = 0$
    else
         $\lambda_k = \max\left( \frac{\phi_k - \langle \nabla f(v_k, \theta_k), \nabla \hat{q}(v_k, \theta_k) \rangle}{\|\nabla \hat{q}(v_k, \theta_k)\|^2}, 0 \right)$
    Update $(v_{k+1}, \theta_{k+1}) = (v_k, \theta_k) - \xi (\nabla f(v_k, \theta_k) + \lambda_k \nabla \hat{q}(v_k, \theta_k))$
return $(v_K, \theta_K)$
The algorithm computes updates entirely using first-order gradients without requiring implicit differentiation, Hessian inversions, or Jacobian-vector products. Default hyperparameter settings are $T=10$ , $\eta=0.5$ , and $\alpha=\xi$ .
Knowl 2 — Value-Function Reformulation and Stop-Gradient Gradient for Bilevel Optimization
model/method
The bilevel optimization problem $\min_{v, \theta} f(v, \theta)$ subject to $\theta \in \arg\min_{\theta'} g(v, \theta')$ is equivalently reformulated as a single-level constrained optimization problem:
$\min_{v, \theta} f(v, \theta) \quad \text{s.t.} \quad q(v, \theta) := g(v, \theta) - g^*(v) \le 0$
where $g^*(v) := \min_{\theta'} g(v, \theta') = g(v, \theta^*(v))$ is the value function. By Danskin's theorem, the gradient of the value function with respect to $v$ satisfies:
$\nabla_v g^*(v) = \nabla_1 g(v, \theta^*(v)) + \nabla_v \theta^*(v) \nabla_2 g(v, \theta^*(v)) = \nabla_1 g(v, \theta^*(v))$
because $\nabla_2 g(v, \theta^*(v)) = 0$ at the lower-level optimum $\theta^*(v)$ , where $\nabla_1$ denotes differentiation with respect to the first argument $v$ .

To avoid exact calculation of $\theta^*(v)$ , the optimum is approximated at iteration $k$ by $\theta_k^{(T)}$ , obtained via $T$ steps of gradient descent on $g(v_k, \cdot)$ starting from $\theta_k$ . BOME defines the plug-in surrogate constraint:
$\hat{q}(v, \theta) := g(v, \theta) - g(v, \theta_k^{(T)})$
where $\theta_k^{(T)}$ is treated as a constant (stop-gradient), eliminating the need to differentiate through the optimization trajectory. The surrogate gradient evaluated at $(v_k, \theta_k)$ is:
$\nabla_{v_k} \hat{q}(v_k, \theta_k) = \nabla_{v_k} g(v_k, \theta_k) - \nabla_1 g(v_k, \theta_k^{(T)})$
and $\nabla_{\theta_k} \hat{q}(v_k, \theta_k) = \nabla_{\theta_k} g(v_k, \theta_k)$ .
Knowl 3 — Stationarity Metric for Constrained Value-Function Bilevel Optimization
definition
For the value-function constrained bilevel optimization problem $\min_{v, \theta} f(v, \theta)$ s.t. $q(v, \theta) := g(v, \theta) - g^*(v) \le 0$ , the stationarity of a candidate solution $(v, \theta)$ is measured by the metric $\mathcal{K}(v, \theta)$ :
$\mathcal{K}(v, \theta) := \min_{\lambda \ge 0} \|\nabla f(v, \theta) + \lambda \nabla q(v, \theta)\|^2 + q(v, \theta)$
where $\nabla f(v, \theta) = (\nabla_v f(v, \theta), \nabla_\theta f(v, \theta))$ and $\nabla q(v, \theta) = (\nabla_v g(v, \theta) - \nabla_1 g(v, \theta^*(v)), \nabla_\theta g(v, \theta))$ .

The metric consists of two terms:
1. $\min_{\lambda \ge 0} \|\nabla f(v, \theta) + \lambda \nabla q(v, \theta)\|^2$ : measures local improvement conflict between descending $f$ and maintaining feasibility of $q$ , which is equal to the squared $\ell_2$ -norm of the solution to $\min_\delta \|\nabla f(v, \theta) - \delta\|^2 \text{ s.t. } \langle \nabla q(v, \theta), \delta \rangle \ge 0$ .
2. $q(v, \theta) = g(v, \theta) - g^*(v)$ : measures feasibility violation of the lower-level optimization problem $\theta \in \arg\min_{\theta'} g(v, \theta')$ .
If a sequence $(v_k, \theta_k)$ satisfies $\nabla f(v_k, \theta_k) + \lambda_k \nabla q(v_k, \theta_k) \to 0$ and $q(v_k, \theta_k) \to 0$ with $q(v_k, \theta_k) \ne 0$ for all $k$ , and the limit point $(v^*, \theta^*)$ satisfies constant rank constraint qualification (CRCQ) with $\nabla_\theta q = \nabla_\theta g$ , then $(v^*, \theta^*)$ satisfies the stationarity condition $\nabla f(v^*, \theta^*) + \nabla(\nabla_\theta g(v^*, \theta^*)) \omega^* = 0$ for some Lagrange multiplier $\omega^* \in \mathbb{R}^n$ .
Knowl 4 — Non-Asymptotic Convergence Rate of BOME under the Polyak-Łojasiewicz Inequality
theoretical result
Let the following conditions hold:
1. Polyak-Łojasiewicz (PL) inequality: For all $v$ , $g(v, \cdot)$ has a unique minimizer $\theta^*(v)$ , and there exists $\kappa > 0$ such that $\|\nabla_\theta g(v, \theta)\|^2 \ge \kappa (g(v, \theta) - g(v, \theta^*(v)))$ for all $(v, \theta)$ .
2. Smoothness: $f$ and $g$ are differentiable, and their gradients $\nabla f$ and $\nabla g$ are $L$ -Lipschitz with respect to $(v, \theta)$ for some $L \in (0, \infty)$ .
3. Boundedness: There exists $M < \infty$ such that $\|\nabla g(v, \theta)\|$ , $\|\nabla f(v, \theta)\|$ , $|f(v, \theta)|$ , and $|g(v, \theta)|$ are all upper bounded by $M$ .
For BOME with outer step size $\xi \le 1/L$ , inner step size $\alpha \le 1/L$ , control barrier $\phi_k = \eta \|\nabla \hat{q}(v_k, \theta_k)\|^2$ with $\eta > 0$ , there exists a constant $c$ (depending on $\alpha, \kappa, \eta, L$ ) such that when $T \ge c$ , for any iteration horizon $K \ge 0$ :
$\min_{k \le K} \mathcal{K}(v_k, \theta_k) = \mathcal{O}\left( \sqrt{\xi} + \sqrt{\frac{q_0}{\xi K}} + \frac{1}{\xi K} + \exp(-bT) \right)$
where $q_0 = q(v_0, \theta_0) = g(v_0, \theta_0) - g^*(v_0)$ and $b > 0$ is a constant depending on $\kappa, L, \alpha$ .

Specific convergence rates under optimal step-size choices:
- For general initialization $q_0 = \mathcal{O}(1)$ , selecting $\xi = \mathcal{O}(K^{-1/2})$ yields a rate of $\mathcal{O}(K^{-1/4} + \exp(-bT))$ .
- For warm initialization $q_0 = \mathcal{O}((\xi K)^{-1})$ , selecting $\xi = \mathcal{O}(K^{-2/3})$ yields a rate of $\mathcal{O}(K^{-1/3} + \exp(-bT))$ .
Knowl 5 — Non-Asymptotic Convergence Rate of BOME for Multimodal Inner Objectives
theoretical result
Let $\theta^\dagger(v, \theta)$ denote the attraction point of $(v, \theta)$ , defined as the limit of the gradient descent sequence $\theta^{(t+1)} = \theta^{(t)} - \alpha \nabla_\theta g(v, \theta^{(t)})$ starting from $\theta^{(0)} = \theta$ . The local constraint and stationarity metrics are defined as:
$q^\dagger(v, \theta) := g(v, \theta) - g(v, \theta^\dagger(v, \theta))$ $\mathcal{K}^\dagger(v, \theta) := \min_{\lambda \ge 0} \|\nabla f(v, \theta) + \lambda \nabla q^\dagger(v, \theta)\|^2 + q^\dagger(v, \theta)$
Suppose the following assumptions hold:
1. Smoothness: $\nabla f$ and $\nabla g$ are $L$ -Lipschitz with respect to $(v, \theta)$ .
2. Boundedness: $\|\nabla g\|$ , $\|\nabla f\|$ , $|f|$ , and $|g|$ are bounded by $M < \infty$ .
3. Local PL-inequality: For every $(v, \theta)$ , $\theta^\dagger(v, \theta)$ exists and satisfies $\|\nabla_\theta g(v, \theta)\|^2 \ge \kappa (g(v, \theta) - g(v, \theta^\dagger(v, \theta)))$ for some $\kappa > 0$ .
4. Differentiability: $q^\dagger$ is differentiable at all iterates $(v_k, \theta_k)$ for $k \ge 0$ .
Under BOME with $\xi, \alpha \le 1/L$ , $\phi_k = \eta \|\nabla \hat{q}(v_k, \theta_k)\|^2$ with $\eta > 0$ , and inner step count $T \ge c$ (where $c$ depends on $\alpha, \kappa, \eta, L$ ):
$\min_{k \le K} \mathcal{K}^\dagger(v_k, \theta_k) = \mathcal{O}\left( \sqrt{\xi} + \sqrt{\frac{1}{\xi K}} + \exp(-bT) \right)$
where $b > 0$ depends on $\kappa, L, \alpha$ . Choosing $\xi = \mathcal{O}(K^{-1/2})$ yields an overall convergence rate of $\min_{k \le K} \mathcal{K}^\dagger(v_k, \theta_k) = \mathcal{O}(K^{-1/4} + \exp(-bT))$ .

Knowl 6 — Continual Learning Performance of BOME on PMNIST and Split CIFAR

data/table

BOME was evaluated in an online continual learning setting using the Contextual Transformation Network (CTN) framework, where a quickly updated backbone network parameterized by $\theta$ is trained on inner task loss while a slowly updated controller parameterized by $v$ minimizes outer validation loss across sequential tasks $\tau = 1, \dots, t$ .

Performance is measured by three metrics:

Average Accuracy (ACC $\uparrow$ ): Mean test accuracy across all seen tasks after training completion, $\text{ACC} = \frac{1}{t} \sum_{\tau \le t} a_t^\tau$ .
Negative Backward Transfer (NBT $\downarrow$ ): Measure of catastrophic forgetting, $\text{NBT} = \frac{1}{t} \sum_{\tau \le t} (a_\tau^\tau - a_t^\tau)$ , where lower values indicate less forgetting.
Forward Transfer (FT $\uparrow$ ): Speed of learning new tasks, $\text{FT} = \text{ACC} + \text{NBT}$ .

Method	PMNIST			Split CIFAR
	ACC ( $\uparrow$ )	NBT ( $\downarrow$ )	FT ( $\uparrow$ )	ACC ( $\uparrow$ )	NBT ( $\downarrow$ )	FT ( $\uparrow$ )
Offline	84.95 $\pm$ 0.95	–	–	74.11 $\pm$ 0.66	–	–
MER	76.59 $\pm$ 0.74	5.73 $\pm$ 0.59	82.32 $\pm$ 0.34	60.32 $\pm$ 0.86	8.91 $\pm$ 0.86	69.23 $\pm$ 0.40
CTN (+ITD)	78.40 $\pm$ 0.28	5.62 $\pm$ 0.39	84.02 $\pm$ 0.29	67.7 $\pm$ 60.96	4.88 $\pm$ 0.77	72.58 $\pm$ 0.62
CTN (+BVFSM)	77.78 $\pm$ 0.32	7.25 $\pm$ 0.28	85.03 $\pm$ 0.28	67.04 $\pm$ 0.76	6.97 $\pm$ 0.62	74.01 $\pm$ 0.57
CTN (+BOME)	80.70 $\pm$ 0.26	4.09 $\pm$ 0.27	84.79 $\pm$ 0.25	68.16 $\pm$ 0.60	4.72 $\pm$ 0.75	72.88 $\pm$ 0.48

All results reflect the mean and standard error over 5 independent runs. CTN integrated with BOME achieved the highest final accuracy and lowest forgetting (NBT) on both PMNIST and Split CIFAR compared to other bilevel optimizers (ITD, BVFSM) and continual learning baselines (MER).

Knowl 7 — Empirical Robustness and Efficiency in Hyperparameter Optimization
empirical result
BOME was evaluated across two hyperparameter optimization benchmarks:
1. Data Hyper-Cleaning (MNIST): Learning sample weights $v \in \mathbb{R}^m$ for $m$ noisy training points (with $50\%$ random label corruption) to minimize validation loss. BOME achieves test loss comparable to or lower than implicit/explicit methods (AID-CG, AID-FP, reverse AD, ITD) and first-order methods (BSG-1, BVFSM) while requiring less computation time.
2. Learnable Regularization (20 Newsgroups): Learning high-dimensional regularization coefficients $W_v = \text{diag}(\exp(v))$ for classification. BOME converges to lower test loss substantially faster than second-order methods and BVFSM.
Ablation studies demonstrated parameter robustness:
- Inner loop steps $T$ : Setting $T = 1$ provides performance and convergence speed nearly identical to $T = 10$ and $T = 20$ , making single-step inner optimization practical.
- Control barrier parameter $\eta$ : BOME is insensitive across $\eta \in \{0.1, 0.5, 0.9\}$ .
- Form of control barrier $\phi_k$ : The gradient-norm barrier $\phi_k = \eta \|\nabla \hat{q}(v_k, \theta_k)\|^2$ and functional barrier $\phi_k = \eta \hat{q}(v_k, \theta_k)$ yield virtually indistinguishable performance when properly scaled.
- Step size $\alpha$ : Setting the inner step size equal to the outer step size ( $\alpha = \xi$ ) works robustly across tasks without separate tuning.
Knowl 8 — Empirical Behavior of BOME on Non-Convex and Degenerate Toy Problems
empirical result
BOME was tested on three synthetic problem formulations that pose failure modes for standard bilevel optimization algorithms:
1. Toy Coreset Problem: Finding the nearest point to $x_0 \in \mathbb{R}^2$ within the convex hull of $X = [x_1, x_2, x_3, x_4] \in \mathbb{R}^{2 \times 4}$ :
$\min_{v, \theta} \|\theta - x_0\|^2 \quad \text{s.t.} \quad \theta \in \arg\min_{\theta'} \|\theta' - X \sigma(v)\|^2$
where $\sigma(v)$ is the softmax function. BOME converges directly to the true optimum while driving the surrogate constraint $\hat{q}$ to zero, whereas BSG-1, BVFSM, and penalty methods struggle or stall.
1. Toy Mini-Max Game: A fully conflicting zero-sum bilevel game ( $f = -g$ ):
$\min_{v, \theta \in \mathbb{R}} v\theta \quad \text{s.t.} \quad \theta \in \arg\max_{\theta' \in \mathbb{R}} v\theta'$
with true optimum $(v^*, \theta^*) = (0, 0)$ . Standard gradient descent-ascent diverges, and other first-order BO baselines fail to reach the optimum. BOME successfully converges to $(0,0)$ .
1. Degenerate Low-Level Problem (Violation of Low-Level Singleton Assumption):
$\min_{v \in \mathbb{R}, \theta \in \mathbb{R}^2} \|\theta - [v; 1]\|_2^2 \quad \text{s.t.} \quad \theta \in \arg\min_{(\theta'_1, \theta'_2) \in \mathbb{R}^2} (\theta'_1 - v)^2$
with optimal solution $v^* = 1, \theta^* = (1, 1)$ . Methods relying on unique low-level minimizers (LLS) fail, whereas BOME converges directly to the true minimizer.
Knowl 9 — Theoretical vs. Empirical Inner-Loop Iteration Gap in BOME
limitation
A theoretical limitation of BOME is that the non-asymptotic convergence guarantees (Theorems 1 and 2) require the inner gradient descent iterations $T$ to satisfy $T \ge c$ for a threshold constant $c$ , which implies $T$ must scale logarithmically with the outer iteration horizon $K$ to make the approximation error $\exp(-bT)$ negligible relative to the $\mathcal{O}(K^{-1/4})$ or $\mathcal{O}(K^{-1/3})$ outer error terms.

However, empirical benchmarks demonstrate that BOME achieves optimal performance with a fixed, small number of inner steps (such as $T = 1$ or $T = 10$ ) throughout training, showing that theoretical error bounds currently overestimate the number of inner steps needed in practice.

Coverage note — None was omitted; the knowls cover the algorithmic framework, value-function reformulation, stationarity metric, theoretical convergence bounds for unimodal and multimodal objectives, toy benchmarks, hyperparameter optimization, continual learning results, and identified limitations.

References

1.Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. arXiv preprint arXiv:2111.14580, 2021.
2.Jonathan F Bard. Practical bilevel optimization: algorithms and applications, volume 30. Springer Science & Business Media, 2013.
3.Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puneet K Dokania, Philip HS Torr, and Marc’Aurelio Ranzato. On tiny episodic memories in continual learning. arXiv preprint arXiv:1902.10486, 2019.
4.Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2102.04671, 2021.
5.Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv:1711.00141, 2017.
6.Stephan Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002.
7.Stephan Dempe and Alain Zemkoho. Bilevel optimization. Springer, 2020.
8.Stephan Dempe, Nguyen Dinh, Joydeep Dutta, and Tanushree Pandit. Simple bilevel programming and extensions. Mathematical Programming, 188(1):227–253, 2021.
9.Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141–142, 2012.
10.Nguyen Dinh, B Mordukhovich, and Tran TA Nghia. Subdifferentials of value functions and optimality conditions for dc and bilevel infinite and semi-infinite programs. Mathematical Programming, 123(1):101–138, 2010.
11.Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, pages 1165–1173. PMLR, 2017.
12.Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, pages 1568–1577. PMLR, 2018.
13.Spencer Frei and Quanquan Gu. Proxy convexity: A unified framework for the analysis of neural networks trained by gradient descent. Advances in Neural Information Processing Systems, 34, 2021.
14.Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018.
15.Tommaso Giovannelli, Griffin Kent, and Luis Nunes Vicente. Bilevel stochastic methods for optimization and machine learning: Bilevel stochastic descent and darts. arXiv preprint arXiv:2110.00604, 2021.
16.Chengyue Gong, Xingchao Liu, and Qiang Liu. Automatic and harmless regularization with constrained and lexicographic optimization: A dynamic barrier approach. Advances in Neural Information Processing Systems, 34, 2021.
17.Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748–3758. PMLR, 2020.
18.Zhishuai Guo and Tianbao Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint arXiv:2105.02266, 2021.
19.Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05170, 2020.
20.Robert Janin. Directional derivative of the marginal function in nonlinear programming. In Sensitivity, Stability and Parametric Analysis, pages 110–126. Springer, 1984.
21.Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv:2102.03926, 2021.
22.Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882–4892. PMLR, 2021.
23.Haoming Jiang, Zhehui Chen, Yuyang Shi, Bo Dai, and Tuo Zhao. Learning to defend by learning to attack. In International Conference on Artificial Intelligence and Statistics, pages 577–585. PMLR, 2021.
24.Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795–811. Springer, 2016.
25.Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. arXiv preprint arXiv:2102.07367, 2021.
26.Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
27.Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on learning theory, pages 1246–1257. PMLR, 2016.
28.Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. arXiv preprint arXiv:2112.04660, 2021.
29.Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard Zemel. Reviving and improving recurrent back-propagation. In International Conference on Machine Learning, pages 3082–3091. PMLR, 2018.
30.Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022.
31.Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning, pages 6305–6315. PMLR, 2020.
32.Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. arXiv preprint arXiv:2101.11517, 2021.
33.Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-function-based interior-point method for non-convex bi-level optimization. arXiv preprint arXiv:2106.07991, 2021.
34.Risheng Liu, Xuan Liu, Shangzhi Zeng, Jin Zhang, and Yixuan Zhang. Value-function-based sequential minimization for bi-level optimization. arXiv preprint arXiv:2110.04974, 2021.
35.Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34, 2021.
36.David Lopez-Paz and Marc’Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30:6467–6476, 2017.
37.Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference on Artificial Intelligence and Statistics, pages 1540–1552. PMLR, 2020.
38.Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. arXiv preprint arXiv:1903.03088, 2019.
39.Akshay Mehra and Jihun Hamm. Penalty method for inversion-free deep bilevel optimization. In Asian Conference on Machine Learning, pages 347–362. PMLR, 2021.
40.Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer Science & Business Media, second edition, 2006.
41.Jivrí V Outrata. On the numerical solution of a class of stackelberg problems. Zeitschrift für Operations Research, 34(4):255–277, 1990.
42.Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on machine learning, pages 737–746. PMLR, 2016.
43.Quang Pham, Chenghao Liu, Doyen Sahoo, and HOI Steven. Contextual transformation networks for online continual learning. In International Conference on Learning Representations, 2020.
44.Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine. Meta-learning with implicit gradients. 2019.
45.Matthew Riemer, Ignacio Cases, Robert Ajemian, Miao Liu, Irina Rish, Yuhai Tu, and Gerald Tesauro. Learning to learn without forgetting by maximizing transfer and minimizing interference. arXiv preprint arXiv:1810.11910, 2018.
46.Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back-propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723–1732. PMLR, 2019.
47.Michael Shub. Global stability of dynamical systems. Springer Science & Business Media, 2013.
48.Chaehwan Song, Ali Ramezani-Kebrya, Thomas Pethick, Armin Eftekhari, and Volkan Cevher. Subquadratic overparameterization for shallow neural networks. Advances in Neural Information Processing Systems, 34, 2021.
49.Yann Traonmilin and Jean-Francois Aujol. The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem. Inverse Problems, 36(4):045003, 2020.
50.Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.
51.Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. arXiv preprint arXiv:2106.04692, 2021.
52.Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost. 2019.
53.JJ Ye and DL Zhu. Optimality conditions for bilevel programming problems. Optimization, 33(1):9–27, 1995.

Citation

MLA

Liu, B., et al. “BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach”. Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 17248–62, https://proceedings.neurips.cc/paper_files/paper/2022/file/6dddcff5b115b40c998a08fbd1cea4d7-Paper-Conference.pdf.

APA

Liu, B., Ye, M., Wright, S., Stone, P., & Liu, Q. (2022). BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach. Advances in Neural Information Processing Systems, 35, 17248–17262. https://proceedings.neurips.cc/paper_files/paper/2022/file/6dddcff5b115b40c998a08fbd1cea4d7-Paper-Conference.pdf

Chicago

Liu, B., M. Ye, S. Wright, P. Stone, and Q. Liu. 2022. “BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach”. Advances in Neural Information Processing Systems 35: 17248–62. https://proceedings.neurips.cc/paper_files/paper/2022/file/6dddcff5b115b40c998a08fbd1cea4d7-Paper-Conference.pdf.

Harvard

Liu, B. et al. (2022) “BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 17248–17262. Available at: https://proceedings.neurips.cc/paper_files/paper/2022/file/6dddcff5b115b40c998a08fbd1cea4d7-Paper-Conference.pdf.

Vancouver

1. Liu B, Ye M, Wright S, Stone P, Liu Q (2022) BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 17248–17262

BibTeX

@inproceedings{liu2022bome,
  title = {BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach},
  author = {Liu, Bo and Ye, Mao and Wright, Stephen and Stone, Peter and Liu, Qiang},
  year = {2022},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {35},
  pages = {17248-17262},
  url = {https://proceedings.neurips.cc/paper_files/paper/2022/file/6dddcff5b115b40c998a08fbd1cea4d7-Paper-Conference.pdf}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Bilevel Optimization Made Easy Algorithm

Knowl 2 — Value-Function Reformulation and Stop-Gradient Gradient for Bilevel Optimization

Knowl 3 — Stationarity Metric for Constrained Value-Function Bilevel Optimization

Knowl 4 — Non-Asymptotic Convergence Rate of BOME under the Polyak-Łojasiewicz Inequality

Knowl 5 — Non-Asymptotic Convergence Rate of BOME for Multimodal Inner Objectives

Knowl 6 — Continual Learning Performance of BOME on PMNIST and Split CIFAR

Knowl 7 — Empirical Robustness and Efficiency in Hyperparameter Optimization

Knowl 8 — Empirical Behavior of BOME on Non-Convex and Degenerate Toy Problems

Knowl 9 — Theoretical vs. Empirical Inner-Loop Iteration Gap in BOME

References

Citation

BibTeX

Source Code

Access the Paper