Will Bilevel Optimizers Benefit from Loops

Kaiyi JiMingrui LiuYingbin LiangLei Ying

article2022NeurIPS56 citations

Establishes a unified convergence and computational complexity framework for approximate implicit differentiation and iterative differentiation bilevel optimizers, resolving whether inner-level loops improve efficiency and proving that iterative differentiation requires loops to avoid non-vanishing convergence error.

Listen

Bilevel optimization has become an essential framework for solving modern machine learning challenges, including hyperparameter tuning, meta-learning, and reinforcement learning. In these frameworks, an outer objective depends directly on the solution of an inner sub-problem. Standard optimization algorithms generally solve these problems either by running multi-step inner loops that iterate until high accuracy is achieved or by using single-step, no-loop approximations to reduce the computational cost per update. Prior literature lacked a unified framework to systematically evaluate whether adding these internal loops truly improves overall efficiency or merely introduces unnecessary computation.

The main objective of the article is to establish a comprehensive theoretical convergence analysis for the two most prominent gradient-based bilevel optimizer families: Approximate Implicit Differentiation (AID-BiO) and Iterative Differentiation (ITD-BiO). By analyzing all possible configurations of inner-level loops and linear-system approximation loops, the article provides rigorous computational complexity bounds that clearly determine the most efficient architectural choices.

To conduct this evaluation, the analysis models a non-convex outer problem alongside a strongly convex inner problem under standard mathematical smoothness conditions. The analysis tracks the required gradient evaluations and matrix-vector product calculations across all implementation variants. The authors also eliminate restrictive assumptions present in prior research, such as assuming bounded inner solutions, and establish both theoretical upper and lower error bounds, validating the results with numerical benchmarks on standard image and representation tasks.

The findings demonstrate that internal loops are critical for bilevel optimization. First, for AID-BiO, running an inner optimization loop significantly improves total computational complexity compared to a no-loop design, accelerating the overall convergence rate. Second, adding a loop to approximate the outer-level linear system further reduces gradient evaluations. Third, for ITD-BiO, internal loops are mathematically required: the theoretical lower bound proves that single-step implementations suffer from an unavoidable, permanent estimation error that prevents exact convergence. Finally, empirical tests confirm that multi-iteration loop configurations achieve substantially lower loss values and faster runtimes than single-step counterparts.

These findings have direct operational implications for engineering machine learning pipelines. While simpler single-loop algorithms appear less computationally demanding per step, they are substantially slower to converge overall and risk producing inaccurate models in ITD-based settings. Unlike standard minimax optimization, where single-loop methods are often superior, bilevel optimization relies heavily on second-order derivative accuracy, making inner loop precision vital for performance and stability.

Practitioners should prioritize multi-step inner loops when deploying bilevel optimizers. For AID-BiO, teams facing memory or hardware constraints can use a single-step linear system solver combined with a multi-step inner solver to maintain peak matrix-vector efficiency while keeping per-iteration resource usage manageable. For ITD-BiO, multi-step loops must always be used to ensure valid convergence. Future research should focus on closing the theoretical gap between the upper and lower error bounds for ITD algorithms and extending this unified analysis to stochastic and variance-reduced settings.

George Mason University The Ohio State University University at Buffalo University of Michigan ITD-based bilevel optimization AID-based bilevel optimization bilevel programming

arXiv: 2205.14224

Paper: OptNet: Differentiable Optimization as a Layer in Neural Networks, Brandon Amos et al. (2017). Provides the foundational framework for implicit differentiation through optimization problems that underlies modern Approximate Implicit Differentiation (AID) bilevel optimization.
Paper: Automatic differentiation in machine learning: a survey, Atilim Gunes Baydin et al. (2018). Surveys the mechanics of reverse-mode automatic differentiation and iterative differentiation (ITD) essential for understanding back-propagation through unrolled optimization steps.
Paper: On First-Order Meta-Learning Algorithms, Alex Nichol et al. (2018). Analyzes the dynamics and trade-offs of first-order approximations versus unrolled inner steps in gradient-based meta-learning pipelines.
Book: Convex Optimization: Algorithms and Complexity, Sébastien Bubeck (2015). Establishes foundational oracle complexity bounds and convergence rates for first-order convex optimization that underwrite the analysis of inner-loop accuracy.

Paper: Lower Bounds and Accelerated Algorithms for Bilevel Optimization, Kaiyi Ji et al. (2023). Extends the complexity analysis of bilevel optimization by deriving lower bounds for convex and strongly-convex settings and proposing accelerated algorithms.
Paper: A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse, Junyi Li et al. (2022). Introduces a fully single-loop bilevel algorithm that tracks auxiliary hyper-gradient states, directly addressing the trade-offs of inner loops analyzed in the source.
Paper: BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach, Bo Liu et al. (2022). Develops a value-function, first-order reformulation of bilevel problems that circumvents the explicit multi-step inner loops and linear solvers scrutinized in the source.

Cover for Will Bilevel Optimizers Benefit from Loops

Abstract

Bilevel optimization has arisen as a powerful tool for solving a variety of machine learning problems. Two current popular bilevel optimizers AID-BiO and ITD-BiO naturally involve solving one or two sub-problems, and consequently, whether we solve these problems with loops (that take many iterations) or without loops (that take only a few iterations) can significantly affect the overall computational efficiency. Existing studies in the literature cover only some of those implementation choices, and the complexity bounds available are not refined enough to enable rigorous comparison among different implementations. In this paper, we first establish unified convergence analysis for both AID-BiO and ITD-BiO that are applicable to all implementation choices of loops. We then specialize our results to characterize the computational complexity for all implementations, which enable an explicit comparison among them. Our result indicates that for AID-BiO, the loop for estimating the optimal point of the inner function is beneficial for overall efficiency, although it causes higher complexity for each update step, and the loop for approximating the outer-level Hessian-inverse-vector product reduces the gradient complexity. For ITD-BiO, the two loops always coexist, and our convergence upper and lower bounds show that such loops are necessary to guarantee a vanishing convergence error, whereas the no-loop scheme suffers from an unavoidable non-vanishing convergence error. Our numerical experiments further corroborate our theoretical results.

Keywords

ITD-based bilevel optimization AID-based bilevel optimization bilevel programming hyperparameter optimization stochastic bilevel optimization linear bilevel optimization minimax optimization inner-loop error gradient-based hyperparameter optimization computational complexity

1 Introduction
2 Algorithms
2.1 AID-based Bilevel Optimization Algorithm
2.2 ITD-Based Bilevel Optimization Algorithm
3 Definitions and Assumptions
4 Convergence Analysis of AID-BiO
4.1 Convergence Rate and Computational Complexity
4.2 Comparison among Four Implementations
5 Convergence Analysis of ITD-BiO
6 Empirical Verification
7 Conclusion
Acknowledgements
References
Checklist

Knowls

Knowl 1 — AID-Based Bilevel Optimization with Double Warm Starts
algorithm
The approximate implicit differentiation-based bilevel optimizer (AID-BiO) solves the bilevel optimization problem: $\min_{x \in \mathbb{R}^p} \Phi(x) := f(x, y^*(x)) \quad \text{s.t.} \quad y^*(x) = \arg\min_{y \in \mathbb{R}^q} g(x, y)$ where $g(x, y)$ is $\mu$ -strongly convex in $y$ , and the outer function $\Phi(x)$ is possibly nonconvex in $x$ . The algorithm approximates the true hypergradient: $\nabla \Phi(x_k) = \nabla_x f(x_k, y^*(x_k)) - \nabla_x \nabla_y g(x_k, y^*(x_k)) v_k^*$ where $v_k^*$ solves $\nabla_y^2 g(x_k, y^*(x_k)) v = \nabla_y f(x_k, y^*(x_k))$ . AID-BiO executes $N$ inner gradient descent steps for $y$ initialized with warm start $y_k^0 = y_{k-1}^N$ , and solves the linear system for $v$ via $Q$ steps initialized with warm start $v_k^0 = v_{k-1}^Q$ .
Input: Stepsizes $\alpha, \beta > 0$ , inner step count $N$ , linear solver step count $Q$ , initial points $x_0, y_0, v_0$
for $k = 0, 1, 2, \dots, K-1$ do
    if $k > 0$ then
         $y_k^0 = y_{k-1}^N$
    else
         $y_k^0 = y_0$
    end if
    for $t = 1, \dots, N$ do
         $y_k^t = y_k^{t-1} - \alpha \nabla_y g(x_k, y_k^{t-1})$
    end for
    if $k > 0$ then
         $v_k^0 = v_{k-1}^Q$
    else
         $v_k^0 = v_0$
    end if
    Compute $v_k^Q$ by applying $Q$ steps of gradient descent to $\frac{1}{2} \langle v, \nabla_y^2 g(x_k, y_k^N) v \rangle - \langle \nabla_y f(x_k, y_k^N), v \rangle$ starting from $v_k^0$
    Compute hypergradient estimator $\widehat{\nabla} \Phi(x_k) = \nabla_x f(x_k, y_k^N) - \nabla_x \nabla_y g(x_k, y_k^N) v_k^Q$
    Update outer variable $x_{k+1} = x_k - \beta \widehat{\nabla} \Phi(x_k)$
end for
Output: $x_K$
Knowl 2 — ITD-Based Bilevel Optimization with Warm Start
algorithm
The iterative differentiation-based bilevel optimizer (ITD-BiO) solves bilevel optimization problems of the form $\min_{x \in \mathbb{R}^p} \Phi(x) := f(x, y^*(x))$ subject to $y^*(x) = \arg\min_{y \in \mathbb{R}^q} g(x, y)$ . ITD-BiO computes the hypergradient by differentiating through the $N$ inner-loop gradient descent iterations via automatic differentiation / backpropagation. Because the differentiation tracks the exact trajectory of length $N$ , the parameter $Q$ is implicitly equal to $N$ .
Input: Stepsizes $\alpha, \beta > 0$ , inner step count $N$ , initializations $x_0, y_0$
for $k = 0, 1, 2, \dots, K-1$ do
    if $k > 0$ then
         $y_k^0 = y_{k-1}^N$
    else
         $y_k^0 = y_0$
    end if
    for $t = 1, \dots, N$ do
         $y_k^t = y_k^{t-1} - \alpha \nabla_y g(x_k, y_k^{t-1})$
    end for
    Compute hypergradient estimator via backpropagation along the inner trajectory:
     $\widehat{\nabla} \Phi(x_k) = \nabla_x f(x_k, y_k^N) - \alpha \sum_{t=0}^{N-1} \nabla_x \nabla_y g(x_k, y_k^t) \left( \prod_{j=t+1}^{N-1} (I - \alpha \nabla_y^2 g(x_k, y_k^j)) \right) \nabla_y f(x_k, y_k^N)$
    Update outer variable $x_{k+1} = x_k - \beta \widehat{\nabla} \Phi(x_k)$
end for
Output: $x_K$

Knowl 3 — Computational Complexity Comparison of AID-BiO Implementations

data/table

The computational complexities of four AID-BiO implementations to reach an $\epsilon$ -accurate stationary point (where $\|\nabla \Phi(x)\|^2 \le \epsilon$ ) are compared below. The inner objective condition number is $\kappa = L / \mu$ . Gradient descent (GD) is used as the linear solver in all cases. $\text{MV}(\epsilon)$ denotes the total number of Jacobian- and Hessian-vector product computations, $\text{Gc}(\epsilon)$ denotes the total number of gradient computations, and $\widetilde{\mathcal{O}}(\cdot)$ hides logarithmic factors of $\kappa / \epsilon$ .

Algorithms	$Q$	$N$	$\text{MV}(\epsilon)$	$\text{Gc}(\epsilon)$
Bilevel Approximation (BA)	$\Theta(\kappa \ln \kappa)$	$\frac{(k+1)^{1/4}}{2}$	$\widetilde{\mathcal{O}}(\kappa^5 \epsilon^{-1})$	$\widetilde{\mathcal{O}}(\kappa^5 \epsilon^{-1.25})$
AID-BiO (Prior Art)	$\Theta(\kappa \ln \kappa)$	$\Theta(\kappa \ln \kappa)$	$\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$	$\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$
N-Q-loop AID	$\Theta(\kappa \ln \kappa)$	$\Theta(\kappa \ln \kappa)$	$\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$	$\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$
Q-loop AID	$\Theta(\kappa \ln \kappa)$	$1$	$\widetilde{\mathcal{O}}(\kappa^6 \epsilon^{-1})$	$\widetilde{\mathcal{O}}(\kappa^5 \epsilon^{-1})$
N-loop AID	$\mathcal{O}(1)$	$\Theta(\kappa \ln \kappa)$	$\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$	$\widetilde{\mathcal{O}}(\kappa^5 \epsilon^{-1})$
No-loop AID	$\mathcal{O}(1)$	$1$	$\widetilde{\mathcal{O}}(\kappa^6 \epsilon^{-1})$	$\widetilde{\mathcal{O}}(\kappa^6 \epsilon^{-1})$

The table demonstrates that choosing a large inner loop $N = \Theta(\kappa \ln \kappa)$ improves matrix-vector complexity from $\widetilde{\mathcal{O}}(\kappa^6 \epsilon^{-1})$ to $\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$ , while a large linear solver loop $Q = \Theta(\kappa \ln \kappa)$ reduces the gradient complexity.

Knowl 4 — Complexity and Convergence Error Comparison for ITD-BiO Implementations

data/table

The convergence rates and computational complexities of ITD-BiO implementations to achieve an $\epsilon$ -accurate stationary point (where $\|\nabla \Phi(x)\|^2 \le \epsilon$ ) are compared below. The inner objective condition number is $\kappa = L / \mu$ , where $\mu$ is the strong-convexity constant of $g(x, \cdot)$ and $L$ is the Lipschitz constant. 'N/A' indicates that the complexity to achieve arbitrary $\epsilon$ -accuracy is not reachable due to a non-vanishing convergence error. $\widetilde{\mathcal{O}}(\cdot)$ hides logarithmic factors of $\kappa / \epsilon$ .

Algorithms	$N$	Convergence rate	$\text{MV}(\epsilon)$	$\text{Gc}(\epsilon)$
ITD-BiO (Prior Art)	$\Theta(\kappa \ln \kappa)$	$\mathcal{O}\left(\frac{\kappa^3}{K} + \epsilon\right)$	$\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$	$\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$
N-N-loop ITD	$\Theta(\kappa \ln \kappa)$	$\mathcal{O}\left(\frac{\kappa^3}{K} + \epsilon\right)$	$\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$	$\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$
No-loop ITD	$\Theta(1)$	$\mathcal{O}\left(\frac{\kappa^3}{K} + \kappa^3\right)$	N/A	N/A
Lower bound	$\Theta(1)$	$\Omega(\kappa^2)$	N/A	N/A

The table shows that for ITD-BiO, choosing $N = \Theta(\kappa \ln(\kappa/\epsilon))$ is necessary to ensure a vanishing convergence error, whereas a constant number of inner steps $N = \Theta(1)$ suffers from an unavoidable non-vanishing error.

Knowl 5 — Unified Convergence Analysis of AID-BiO for General Linear System Iterations
theoretical result
Let $f(x, y)$ and $g(x, y)$ satisfy the standard regularity assumptions (Assumptions 1–4) with condition number $\kappa = L / \mu$ , smoothness parameter of the outer objective $L_\Phi = \Theta(\kappa^3)$ , and gradient bound $M$ . Choose parameters $\alpha, \eta, \lambda$ such that: $(1 + \lambda)(1 - \alpha \mu)^N \left(1 + r\left(1 + \frac{1}{\eta \mu}\right)\right) \le 1 - \eta \mu$ where $r = \Theta(\mu^2 C_Q^2)$ and: $C_Q = \Theta\left( \frac{(1-\eta \mu)^{Q-1} \eta Q}{\mu} + \frac{1 - (1-\eta \mu)^Q (1 + \eta Q \mu)}{\mu^2} + (1 - (1-\eta \mu)^Q)\frac{L}{\mu} \right)$ Define $\widetilde{w} = \Theta\left( \frac{\eta \mu \kappa^4}{\lambda r} + \frac{\kappa^4}{\eta \mu} \left( \frac{(1-\eta \mu)^{2Q}}{\mu^2} + \frac{\eta \mu}{\lambda} \right) \right)$ . Choosing $\beta = \min\left\{ \frac{1}{L_\Phi}, \sqrt{\frac{\eta \mu}{\widetilde{w}}} \right\}$ , the iterates generated by AID-BiO satisfy: $\frac{1}{K} \sum_{k=0}^{K-1} \|\nabla \Phi(x_k)\|^2 = \mathcal{O}\left( \frac{\Phi(x_0) - \Phi(x^*)}{\beta K} + \frac{\kappa^2 \|v_0^*\|^2 + (\frac{3M}{\mu} + \kappa^2)}{\eta \mu K} \right)$

Specializing this result to specific loop configurations yields:
1. N-loop AID-BiO ( $N = \Theta(\kappa \ln \kappa)$ and $Q = \Theta(1)$ ): With $\eta = \frac{1}{L}$ , $\alpha = \frac{1}{L}$ , and $\lambda = 1$ , the average squared gradient norm is $\mathcal{O}\left(\frac{\kappa^4}{K} + \frac{\kappa^3}{K}\right)$ , giving computational complexities $\text{Gc}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^5 \epsilon^{-1})$ and $\text{MV}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$ .
2. No-loop AID-BiO ( $N = 1$ and $Q = \Theta(1)$ ): With $\alpha = \frac{1}{L}$ , $\lambda = \frac{\alpha \mu}{2}$ , and $\eta = \min\left\{ \frac{1}{128} \frac{\alpha \mu^2}{Q^2 L^2}, \frac{\alpha}{4}, \frac{1}{\mu Q} \right\}$ , the average squared gradient norm is $\mathcal{O}\left(\frac{\kappa^6}{K} + \frac{\kappa^5}{K}\right)$ , giving computational complexities $\text{Gc}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^6 \epsilon^{-1})$ and $\text{MV}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^6 \epsilon^{-1})$ .
Knowl 6 — Convergence Analysis of AID-BiO for Large Linear System Iterations
theoretical result
Under Assumptions 1–4, with initialization $v_k^0 = 0$ , define: $\tau = \Theta\left( (1 - \alpha \mu)^N \left( 1 + \lambda + (1 + \lambda^{-1})(\kappa^2 + C_Q^2)\kappa^2 \beta^2 \right) \right)$ $w = \Theta\left( (1 - \alpha \mu)^N (\kappa^2 + C_Q^2)(1 + \lambda^{-1})\kappa^2 \right)$ where $C_Q$ is a positive constant depending on $Q$ . Choose $\alpha, \beta$ such that $\tau < 1$ and $\beta L_\Phi + w \beta^2 \left(\frac{1}{2} + \beta L_\Phi\right) \frac{1}{1-\tau} \le \frac{1}{4}$ . Then the iterates of AID-BiO satisfy: $\frac{1}{K} \sum_{k=0}^{K-1} \|\nabla \Phi(x_k)\|^2 = \mathcal{O}\left( \frac{\Phi(x_0) - \Phi(x^*)}{\beta K} + \frac{1}{K} \frac{\delta_0}{1 - \tau} + \kappa^2 (1 - \eta \mu)^{2Q} \right)$ where $\delta_0 = \Theta\left( (\kappa^2 + C_Q^2)(1 - \alpha \mu)^N \|y_0^* - y_0\|^2 \right)$ .

Specializing this theorem for large $Q = \Theta(\kappa \ln(\kappa / \epsilon))$ yields:
1. N-Q-loop AID-BiO ( $N = \Theta(\kappa \ln \kappa)$ , $Q = \Theta(\kappa \ln(\kappa / \epsilon))$ ): Setting $\eta = \alpha = \frac{1}{L}$ , $\lambda = 1$ , and $\beta = \Theta(\kappa^{-3})$ , the rate is $\mathcal{O}\left(\frac{\kappa^3}{K} + \epsilon\right)$ , yielding complexities $\text{Gc}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$ and $\text{MV}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$ .
2. Q-loop AID-BiO ( $N = 1$ , $Q = \Theta(\kappa \ln(\kappa / \epsilon))$ ): Setting $\alpha = \eta = \frac{1}{L}$ , $\lambda = \frac{\alpha \mu}{2}$ , and $\beta = \Theta(\kappa^{-4})$ , the rate is $\mathcal{O}\left(\frac{\kappa^5}{K} + \frac{\kappa^4}{K} + \epsilon\right)$ , yielding complexities $\text{Gc}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^5 \epsilon^{-1})$ and $\text{MV}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^6 \epsilon^{-1})$ .
Knowl 7 — Unified Convergence Rate of ITD-BiO
theoretical result
Under Assumptions 1–4, define: $w = \Theta\left( \frac{\kappa^2}{\alpha \mu} (1 - \alpha \mu)^N \lambda_N + \frac{w_N^2}{\mu^2} \right), \quad \tau = (\lambda_N + N^2)(1 - \alpha \mu)^N + w_N^2$ where $\lambda_N = \Theta\left( \frac{w_N^2 + (1 + \alpha L N)^2}{1 - \frac{1}{4}\alpha \mu - (1 - \alpha \mu)^N(1 + \frac{1}{2}\alpha \mu)} \right)$ and $w_N = \Theta\left( \left( 1 + \frac{\alpha (1 - (1 - \alpha \mu)^{N/2})}{1 - \sqrt{1 - \alpha \mu}} \right) \frac{\alpha (1 - (1 - \alpha \mu)^{N/2})}{1 - \sqrt{1 - \alpha \mu}} (1 - \alpha \mu)^{\frac{N}{2} - 1} \right)$ .

Choosing parameters such that $\beta^2 \le \frac{1 - \frac{1}{4}\alpha \mu}{2w}$ , $\alpha \le \frac{1}{2L}$ , and $\beta L_\Phi + \frac{8}{\alpha \mu} \left(\frac{1}{2} + \beta L_\Phi\right) w \beta^2 < \frac{1}{4}$ , where $L_\Phi = \Theta(\kappa^3)$ , the iterates satisfy: $\frac{1}{K} \sum_{k=0}^{K-1} \|\nabla \Phi(x_k)\|^2 = \mathcal{O}\left( \frac{\Delta_\Phi}{\beta K} + \frac{\tau \Delta_y}{\mu^2 K} + \frac{(1 - \alpha \mu)^{2N}}{\mu^3 K} + \frac{M^2 (1 - \alpha \mu)^{2N} L^2}{\alpha \mu^3} \right)$ where $\Delta_\Phi = \Phi(x_0) - \min_x \Phi(x)$ and $\Delta_y = \|y_0 - y^*(x_0)\|^2$ .

Specializations for ITD-BiO:
1. N-N-loop ITD-BiO ( $N = \Theta(\kappa \ln(\kappa / \epsilon))$ ): With $\alpha = \frac{1}{2L}$ and $\beta = \min\left\{ \sqrt{\frac{\alpha \mu}{40w}}, \sqrt{\frac{1 - \frac{\alpha \mu}{4}}{2w}}, \frac{1}{8L_\Phi} \right\}$ , the convergence rate is $\mathcal{O}\left(\frac{\kappa^3}{K} + \epsilon\right)$ , with complexities $\text{Gc}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$ and $\text{MV}(\epsilon) = \widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$ .
2. No-loop ITD-BiO ( $N = \Theta(1)$ ): With $\alpha = \frac{1}{2NL}$ and $\beta = \min\left\{ \sqrt{\frac{\alpha \mu}{40w}}, \sqrt{\frac{1 - \frac{\alpha \mu}{4}}{2w}}, \frac{1}{8L_\Phi} \right\}$ , the convergence bound contains a non-vanishing error term: $\frac{1}{K} \sum_{k=0}^{K-1} \|\nabla \Phi(x_k)\|^2 = \mathcal{O}\left( \frac{\kappa^3}{K} + \frac{M^2 L^2}{\alpha \mu^3} \right)$
Knowl 8 — Non-Vanishing Error Lower Bound for ITD-BiO with Small Inner Loops
theoretical result
For ITD-BiO with stepsizes $\alpha \le \frac{1}{L}$ , $\beta \le \frac{1}{L_\Phi}$ , and inner loop size $N \le \mathcal{O}(1)$ , where $L_\Phi$ is the smoothness parameter of $\Phi(x)$ , there exist objective functions $f(x, y)$ and $g(x, y)$ satisfying Assumptions 1, 2, 3, and 4 such that for all outer iterates $x_K$ ( $K \ge 1$ ): $\|\nabla \Phi(x_K)\|^2 \ge \Omega\left( \frac{L^2 M^2}{\mu^2} (1 - \alpha \mu)^{2N} \right)$ This lower bound establishes that a non-vanishing error is unavoidable for ITD-BiO whenever $N = \Theta(1)$ , demonstrating that choosing a large inner loop $N = \Theta(\kappa \ln(\kappa / \epsilon))$ is fundamentally necessary for ITD-BiO to reach an $\epsilon$ -accurate stationary point.
Knowl 9 — Standard Smoothness, Strong Convexity, and Bounded Inner-Gradient Assumptions
assumption
The analysis of AID-BiO and ITD-BiO relies on four assumptions on the outer objective $f(x, y)$ and the inner objective $g(x, y)$ for $z = (x, y) \in \mathbb{R}^p \times \mathbb{R}^q$ :
1. Inner Strong Convexity: The lower-level function $g(x, y)$ is $\mu$ -strongly convex with respect to $y$ , i.e., $\nabla_y^2 g(x, y) \succeq \mu I$ .
2. Lipschitz Gradients: The gradients $\nabla f(z)$ and $\nabla g(z)$ are $L$ -Lipschitz continuous: $\|\nabla f(z) - \nabla f(z')\| \le L\|z - z'\|, \quad \|\nabla g(z) - \nabla g(z')\| \le L\|z - z'\|$
3. Lipschitz Derivatives: The higher-order derivatives $\nabla_x \nabla_y g(z)$ and $\nabla_y^2 g(z)$ are $\rho$ -Lipschitz continuous: $\|\nabla_x \nabla_y g(z) - \nabla_x \nabla_y g(z')\| \le \rho\|z - z'\|, \quad \|\nabla_y^2 g(z) - \nabla_y^2 g(z')\| \le \rho\|z - z'\|$
4. Bounded Gradient at Inner Minimizer: There exists a constant $M > 0$ such that for all $x$ , $\|\nabla_y f(x, y^*(x))\| \le M$ , where $y^*(x) = \arg\min_y g(x, y)$ .

Knowl 10 — Empirical Evaluation of Loop Configurations in AID-BiO and ITD-BiO

empirical result

Empirical evaluations on hyperparameter optimization on MNIST and synthetic hyper-representation problems validate the theoretical findings on loop choices:

AID-BiO on MNIST Hyperparameter Optimization:
- Comparing inner loop sizes $N \in \{1, 20, 50\}$ and linear solver iterations $Q \in \{1, 20, 50\}$ , configurations with $N=20$ or $N=50$ converge significantly faster in wall-clock time and achieve lower training/test loss than configurations with $N=1$ .
- Fixing $N=20$ , the convergence curves for $Q=20$ and $Q=1$ are comparable, which aligns with the theoretical prediction that the dominant matrix-vector complexity $\widetilde{\mathcal{O}}(\kappa^4 \epsilon^{-1})$ is governed by $N$ .
ITD-BiO on Hyper-Representation:
- In hyper-representation optimization of $\min_\lambda \frac{1}{2p} \|h(X_V; \lambda)w^* - Y_V\|^2$ subject to $w^* = \arg\min_w \frac{1}{2q} \|h(X_T; \lambda)w - Y_T\|^2 + \frac{\gamma}{2}\|w\|^2$ , validation loss across iterations demonstrates the non-vanishing error for $N=1$ versus vanishing error for $N=20$ :

No-loop ITD stalls at a loss of $0.04$ , whereas N-N-loop ITD achieves $0.004$ , empirically confirming the theoretical non-vanishing error lower bound for constant $N$ .

Coverage note — None was omitted; all key theoretical theorems, corollaries, algorithm definitions, lower bounds, complexity comparison tables, and empirical results from the paper have been represented as self-contained knowls.

References

1.L. Bertinetto, J. F. Henriques, P. Torr, and A. Vedaldi. Meta-learning with differentiable closed-form solvers. In International Conference on Learning Representations (ICLR), 2018.
2.T. Chen, Y. Sun, and W. Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems (NeurIPS), 34:25294–25307, 2021.
3.T. Chen, Y. Sun, and W. Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2102.04671, 2021.
4.J. Domke. Generic methods for optimization-based modeling. In Artificial Intelligence and Statistics (AISTATS), pages 318–326, 2012.
5.M. Feurer and F. Hutter. Hyperparameter optimization. In Automated Machine Learning, pages 3–33. Springer, Cham, 2019.
6.C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proc. International Conference on Machine Learning (ICML), pages 1126–1135, 2017.
7.R. Flamary, A. Rakotomamonjy, and G. Gasso. Learning constrained task similarities in graphregularized multi-task learning. Regularization, Optimization, Kernels, and Support Vector Machines, page 103, 2014.
8.L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning (ICML), pages 1165–1173, 2017.
9.L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning (ICML), pages 1568–1577, 2018.
10.S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018.
11.R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In Proc. International Conference on Machine Learning (ICML), 2020.
12.Z. Guo, Y. Xu, W. Yin, R. Jin, and T. Yang. On stochastic moving-average estimators for non-convex optimization. arXiv preprint arXiv:2104.14840, 2021.
13.Z. Guo and T. Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint arXiv:2105.02266, 2021.
14.P. Hansen, B. Jaumard, and G. Savard. New branch-and-bound rules for linear bilevel programming. SIAM Journal on Scientific and Statistical Computing, 13(5):1194–1217, 1992.
15.M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05170, 2020.
16.M. Huang, K. Ji, S. Ma, and L. Lai. Efficiently escaping saddle points in bilevel optimization. arXiv preprint arXiv:2202.03684, 2022.
17.K. Ji, J. D. Lee, Y. Liang, and H. V. Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. arXiv preprint arXiv:2006.09486, 2020.
18.K. Ji and Y. Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv:2102.03926, 2021.
19.K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882–4892. PMLR, 2021.
20.K. Ji, J. Yang, and Y. Liang. Theoretical convergence of multi-step model-agnostic meta-learning. Journal of Machine Learning Research (JMLR), 23:29–1, 2022.
21.P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. arXiv preprint arXiv:2102.07367, 2021.
22.V. R. Konda and J. N. Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems (NeurIPS), pages 1008–1014, 2000.
23.G. Kunapuli, K. P. Bennett, J. Hu, and J.-S. Pang. Classification model selection via bilevel programming. Optimization Methods & Software, 23(4):475–489, 2008.
24.Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
25.J. Li, B. Gu, and H. Huang. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint arXiv:2009.00690, 2020.
26.J. Li, B. Gu, and H. Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. arXiv preprint arXiv:2112.04660, 2021.
27.T. Lin, C. Jin, and M. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning (ICML), pages 6083–6093. PMLR, 2020.
28.R. Liu, X. Liu, X. Yuan, S. Zeng, and J. Zhang. A value-function-based interior-point method for non-convex bi-level optimization. In International Conference on Machine Learning (ICML), 2021.
29.R. Liu, Y. Liu, S. Zeng, and J. Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
30.R. Liu, P. Mu, X. Yuan, S. Zeng, and J. Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning (ICML), 2020.
31.D. Maclaurin, D. Duvenaud, and R. Adams. Gradient-based hyperparameter optimization through reversible learning. In International Conference on Machine Learning (ICML), pages 2113–2122, 2015.
32.G. M. Moore. Bilevel programming algorithms for machine learning model selection. Rensselaer Polytechnic Institute, 2010.
33.F. Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning (ICML), pages 737–746, 2016.
34.A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems (NeurIPS), pages 113–124, 2019.
35.A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated back-propagation for bilevel optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1723–1732, 2019.
36.C. Shi, J. Lu, and G. Zhang. An extended kuhn–tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51–63, 2005.
37.J. Snell, K. Swersky, and R. Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems (NIPS), 2017.
38.D. Sow, K. Ji, Z. Guan, and Y. Liang. A constrained optimization approach to bilevel optimization with multiple inner minima. arXiv preprint arXiv:2203.01123, 2022.
39.D. Sow, K. Ji, and Y. Liang. Es-based jacobian enables faster bilevel optimization. arXiv preprint arXiv:2110.07004, 2021.
40.J. Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
41.J. Zhang, P. Xiao, R. Sun, and Z. Luo. A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems. Advances in Neural Information Processing Systems (NeurIPS), 33:7377–7389, 2020.
42.M. Zhang, S. W. Su, S. Pan, X. Chang, E. M. Abbasnejad, and R. Haffari. idarts: Differentiable architecture search with stochastic implicit gradients. In International Conference on Machine Learning (ICML), pages 12557–12566. PMLR, 2021.

Citation

MLA

Ji, K., et al. “Will Bilevel Optimizers Benefit from Loops”. Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 3011–23, https://proceedings.neurips.cc/paper_files/paper/2022/file/1413947ef79a733e4b839d339e3dffa7-Paper-Conference.pdf.

APA

Ji, K., Liu, M., Liang, Y., & Ying, L. (2022). Will Bilevel Optimizers Benefit from Loops. Advances in Neural Information Processing Systems, 35, 3011–3023. https://proceedings.neurips.cc/paper_files/paper/2022/file/1413947ef79a733e4b839d339e3dffa7-Paper-Conference.pdf

Chicago

Ji, K., M. Liu, Y. Liang, and L. Ying. 2022. “Will Bilevel Optimizers Benefit from Loops”. Advances in Neural Information Processing Systems 35: 3011–23. https://proceedings.neurips.cc/paper_files/paper/2022/file/1413947ef79a733e4b839d339e3dffa7-Paper-Conference.pdf.

Harvard

Ji, K. et al. (2022) “Will Bilevel Optimizers Benefit from Loops”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 3011–3023. Available at: https://proceedings.neurips.cc/paper_files/paper/2022/file/1413947ef79a733e4b839d339e3dffa7-Paper-Conference.pdf.

Vancouver

1. Ji K, Liu M, Liang Y, Ying L (2022) Will Bilevel Optimizers Benefit from Loops. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 3011–3023

BibTeX

@inproceedings{ji2022will,
  title = {Will Bilevel Optimizers Benefit from Loops},
  author = {Ji, Kaiyi and Liu, Mingrui and Liang, Yingbin and Ying, Lei},
  year = {2022},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {35},
  pages = {3011-3023},
  url = {https://proceedings.neurips.cc/paper_files/paper/2022/file/1413947ef79a733e4b839d339e3dffa7-Paper-Conference.pdf}
}

Metadata:DOI registry

Access the Paper

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

Open PDF

License: Authors

Algorithm	$k=10$	$k=50$	$k=100$	$k=500$	$k=1000$
N-N-loop ITD ( $N=20$ )	9.32	0.11	0.01	0.004	0.004
No-loop ITD ( $N=1$ )	435	6.9	0.04	0.04	0.04

Will Bilevel Optimizers Benefit from Loops

Abstract

Keywords

Table of Contents

Knowls

Knowl 1 — AID-Based Bilevel Optimization with Double Warm Starts

Knowl 2 — ITD-Based Bilevel Optimization with Warm Start

Knowl 3 — Computational Complexity Comparison of AID-BiO Implementations

Knowl 4 — Complexity and Convergence Error Comparison for ITD-BiO Implementations

Knowl 5 — Unified Convergence Analysis of AID-BiO for General Linear System Iterations

Knowl 6 — Convergence Analysis of AID-BiO for Large Linear System Iterations

Knowl 7 — Unified Convergence Rate of ITD-BiO

Knowl 8 — Non-Vanishing Error Lower Bound for ITD-BiO with Small Inner Loops

Knowl 9 — Standard Smoothness, Strong Convexity, and Bounded Inner-Gradient Assumptions

Knowl 10 — Empirical Evaluation of Loop Configurations in AID-BiO and ITD-BiO

References

Citation

BibTeX

Access the Paper