Back

A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse

Junyi LiBin GuHeng Huang

article2022AAAI95 citations

Proposes a fully single-loop bilevel optimization algorithm that eliminates expensive Hessian inverses and inner-loop hyper-gradient evaluations by tracking historical gradient information with guaranteed O(ϵ−2)O(\epsilon^{-2}) convergence.

Listen

Modern machine learning applications—such as hyperparameter tuning, meta-learning, and neural architecture search—are frequently formulated as bilevel optimization problems involving nested outer and inner decision layers. Solving these problems at scale has historically been computationally prohibitive because traditional gradient methods require a slow double-loop procedure or costly matrix inversions to compute the outer gradient, known as the hyper-gradient. Even recent single-loop alternatives fail to be fully single-loop because they still execute sub-loops to approximate the hyper-gradient at each step.

The article aims to design a unified theoretical framework for hyper-gradient approximation and introduce a truly single-loop algorithm that completely eliminates internal iteration loops and matrix inversions while preserving rigorous convergence guarantees.

To achieve this, the authors develop a unified formulation showing that common approximation techniques—including back-propagation through time, Neumann series, and conjugate gradient methods—are specific cases of a single general structure. Building on this insight, the authors introduce the Fully Single Loop Algorithm (FSLA). FSLA tracks historical hyper-gradient information using an auxiliary state variable and updates the inner parameters, outer parameters, and hyper-gradient estimates simultaneously in a single step per iteration. The authors evaluate this approach through theoretical proofs under nonconvex-strongly-convex assumptions and test it empirically on synthetic quadratic datasets and real-world image cleaning tasks using MNIST, Fashion-MNIST, and QMNIST datasets.

The investigation yields three primary findings. First, existing hyper-gradient approximation techniques can be integrated into one framework with proven convergence conditions. Second, FSLA achieves a theoretical convergence rate of O(1/ϵ^2) for nonconvex-strongly-convex objectives, matching standard single-level stochastic optimization rates. Third, in data hyper-cleaning benchmarks with an 80% label noise rate, FSLA significantly outperformed competing methods; for instance, it converged to lower validation loss faster than back-propagation and conjugate gradient baselines, requiring only constant per-iteration vector operations rather than costly multi-step computations.

These findings demonstrate that organizations can train complex bilevel models much faster without sacrificing solution quality. By replacing expensive iterative sub-solvers with a lightweight tracking state, FSLA substantially reduces computational runtime, memory requirements, and cloud infrastructure costs for large-scale learning systems.

Organizations developing complex nested machine learning pipelines should adopt fully single-loop tracking updates like FSLA in place of nested-loop or matrix inversion approaches to accelerate training cycles. Before deploying FSLA in production, engineering teams should conduct pilot tests to calibrate learning rate parameters across specific architectures and workflows.

The primary theoretical limitation is that the formal guarantees rely on standard smoothness and strongly convex inner-problem assumptions. While empirical performance remained robust on deep neural networks across multiple benchmark image datasets, practitioners should exercise appropriate care when applying the algorithm to problems with highly non-convex inner objectives.

Mohamed bin Zayed University of Artificial IntelligenceUniversity of Pittsburghbackpropagation algorithmoptimizationoptimization problemssingle-loop bilevel optimizationbilevel optimizationHessian inverse
arXiv: 2112.04660
  • Paper: On First-Order Meta-Learning Algorithms, Alex Nichol et al. (2018). Analyzes first-order approximations in meta-learning to avoid costly higher-order derivatives, providing key motivation for developing Hessian-free bilevel optimization algorithms.
  • Paper: Learning to learn by gradient descent by gradient descent, Marcin Andrychowicz et al. (2016). Formulates optimization as a learned nested process via recurrent dynamics, introducing foundational principles of gradient-based hyperparameter and meta-parameter updates.
  • Book: Convex Optimization: Algorithms and Complexity, Sébastien Bubeck (2015). Provides foundational complexity theory and convergence bounds for first-order black-box optimization essential for understanding stationary-point convergence rates in bilevel settings.
  • Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). Establishes core convergence properties and complexity trade-offs of stochastic gradient methods that underpin the alternate update and rate analyses in modern bilevel algorithms.
Cover for A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse

Abstract

In this paper, we propose a novel Hessian inverse free Fully Single Loop Algorithm (FSLA) for bilevel optimization problems. Classic algorithms for bilevel optimization admit a double loop structure which is computationally expensive. Recently, several single loop algorithms have been proposed with optimizing the inner and outer variable alternatively. However, these algorithms not yet achieve fully single loop. As they overlook the loop needed to evaluate the hyper-gradient for a given inner and outer state. In order to develop a fully single loop algorithm, we first study the structure of the hyper-gradient and identify a general approximation formulation of hyper-gradient computation that encompasses several previous common approaches, e.g. back-propagation through time, conjugate gradient, etc. Based on this formulation, we introduce a new state variable to maintain the historical hyper-gradient information. Combining our new formulation with the alternative update of the inner and outer variables, we propose an efficient fully single loop algorithm. We theoretically show that the error generated by the new state can be bounded and our algorithm converges with the rate of O(ϵ^{-2}). Finally, we verify the efficacy our algorithm empirically through multiple bilevel optimization based machine learning tasks. A long version of this paper can be found in: https://arxiv.org/abs/2112.04660.

Topics

backpropagation algorithmoptimizationoptimization problemsadaptive algorithms

Keywords

single-loop bilevel optimizationbilevel optimizationHessian inversehyperparameter optimizationhyper-gradient computationmomentum-based variance reductionmeta-learningdifferentiable architecture search

Table of Contents

  • Introduction
  • Related Works
  • A General Formulation of Hyper-Gradient Approximation
  • New Fully Single Loop Algorithm (FSLA)
  • Theoretical Analysis
  • Experiments
  • Synthetic Dataset: Quadratic Objective
  • Hyper Data-cleaning
  • Conclusion
  • References

Knowls

  1. Knowl 1 — Fully Single Loop Algorithm for Bilevel Optimization

    algorithm

    The Fully Single Loop Algorithm (FSLA) solves stochastic bilevel optimization problems without requiring inner-loop iterations or explicit Hessian matrix inversions. It simultaneously updates the outer variable λ\lambda, the inner variable ω\omega, an auxiliary vector vv tracking historical hyper-gradient curvature information, and a momentum-based variance-reduced direction dd.

    Input: Initial outer state λ0∈Λ\lambda_0 \in \Lambda, initial inner state ω0∈Rn\omega_0 \in \mathbb{R}^n, initial vector v0v_0, initial direction d0d_0, total iterations KK, constants cτ,cβ,cη,δ>0c_\tau, c_\beta, c_\eta, \delta > 0
    for k=0k = 0 to K−1K - 1 do
        αk←δ/k+1\alpha_k \leftarrow \delta / \sqrt{k+1}
        λk+1←λk−αkdk\lambda_{k+1} \leftarrow \lambda_k - \alpha_k d_k
        τk+1←cταk\tau_{k+1} \leftarrow c_\tau \alpha_k
        βk+1←cβαk\beta_{k+1} \leftarrow c_\beta \alpha_k
        ηk+1←cηαk\eta_{k+1} \leftarrow c_\eta \alpha_k
        Sample independent stochastic mini-batches ξk+1=(ξk+1,1,…,ξk+1,5)\xi_{k+1} = (\xi_{k+1,1}, \dots, \xi_{k+1,5})
        ωk+1←ωk−τk+1∂ωG(λk+1,ωk;ξk+1,1)\omega_{k+1} \leftarrow \omega_k - \tau_{k+1} \partial_\omega G(\lambda_{k+1}, \omega_k; \xi_{k+1,1})
        vk+1←βk+1∂ωF(λk+1,ωk;ξk+1,2)+(I−βk+1∂ω2G(λk+1,ωk;ξk+1,3))vkv_{k+1} \leftarrow \beta_{k+1} \partial_\omega F(\lambda_{k+1}, \omega_k; \xi_{k+1,2}) + (I - \beta_{k+1} \partial_\omega^2 G(\lambda_{k+1}, \omega_k; \xi_{k+1,3})) v_k
        ∇fk+1(ξk+1)←∂λF(λk+1,ωk+1;ξk+1,4)−∂ωλG(λk+1,ωk+1;ξk+1,5)vk+1\nabla f_{k+1}(\xi_{k+1}) \leftarrow \partial_\lambda F(\lambda_{k+1}, \omega_{k+1}; \xi_{k+1,4}) - \partial_{\omega \lambda} G(\lambda_{k+1}, \omega_{k+1}; \xi_{k+1,5}) v_{k+1}
        dk+1←∇fk+1(ξk+1)+(1−ηk+1)(dk−∇fk(ξk+1))d_{k+1} \leftarrow \nabla f_{k+1}(\xi_{k+1}) + (1 - \eta_{k+1})(d_k - \nabla f_k(\xi_{k+1}))
    end for
    Output: Final outer variable λK\lambda_K

    Key Operations and Properties:

    • Hessian-Vector Update: The state variable vk∈Rnv_k \in \mathbb{R}^n recursively approximates [∂ω2G(λ,ωλ)]−1∂ωF(λ,ωλ)[\partial_\omega^2 G(\lambda, \omega_\lambda)]^{-1} \partial_\omega F(\lambda, \omega_\lambda) via a single Hessian-vector product (I−βk+1∂ω2G(… ))vk(I - \beta_{k+1} \partial_\omega^2 G(\dots))v_k per iteration, requiring O(1)\mathcal{O}(1) Hessian-vector products and O(n)\mathcal{O}(n) memory.
    • Variance Reduction: The tracking variable dkd_k applies a recursive momentum-based variance reduction step (analogous to STORM) to mitigate the variance of stochastic hyper-gradient estimates without large batch sizes.
    • Single Loop: Inner and outer variables are updated alternatingly with one step per hyper-iteration, eliminating nested inner-loop routines entirely.

  2. Knowl 2 — Convergence Rate of FSLA for Nonconvex-Strongly-Convex Bilevel Problems

    theoretical result

    Let the outer objective function f(λ):=F(λ,ωλ)f(\lambda) := F(\lambda, \omega_\lambda) be nonconvex and continuously differentiable with LfL_f-Lipschitz gradient, and let the inner objective G(λ,ω)G(\lambda, \omega) be μG\mu_G-strongly convex in ω\omega. Suppose the gradient, Hessian, and mixed partial derivative estimators have bounded variances bounded by σ2\sigma^2.

    Setting the hyperparameters as αk=δ/k\alpha_k = \delta / \sqrt{k}, τk=cταk\tau_k = c_\tau \alpha_k, βk=cβαk\beta_k = c_\beta \alpha_k, and ηk=cηαk\eta_k = c_\eta \alpha_k for positive constants δ,cτ,cβ,cη\delta, c_\tau, c_\beta, c_\eta, the sequence of outer variables {λk}k=0K−1\{\lambda_k\}_{k=0}^{K-1} generated by the Fully Single Loop Algorithm (FSLA) satisfies:

    1K∑k=0K−1E[∥∇f(λk)∥2]≤2Φ0δK+2δCˉσ2K\frac{1}{K} \sum_{k=0}^{K-1} \mathbb{E}\left[ \|\nabla f(\lambda_k)\|^2 \right] \le \frac{2\Phi_0}{\delta \sqrt{K}} + \frac{2\delta \bar{C} \sigma^2}{\sqrt{K}}

    where Φ0\Phi_0 is the initial value of a potential Lyapunov function Φk:=f(λk)+D1E[∥ωk−ωλk∥2]+D2E[∥vk−vλk∥2]+D3E[∥∇fk−dk∥2]\Phi_k := f(\lambda_k) + D_1 \mathbb{E}[\|\omega_k - \omega_{\lambda_k}\|^2] + D_2 \mathbb{E}[\|v_k - v_{\lambda_k}\|^2] + D_3 \mathbb{E}[\|\nabla f_k - d_k\|^2] for positive constants D1,D2,D3D_1, D_2, D_3, and Cˉ\bar{C} is a positive constant independent of KK.

    Consequently, FSLA achieves an ϵ\epsilon-stationary point (where 1K∑k=0K−1E[∥∇f(λk)∥2]≤ϵ2\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}[\|\nabla f(\lambda_k)\|^2] \le \epsilon^2) with an iteration and sample complexity of O(ϵ−2)\mathcal{O}(\epsilon^{-2}), matching the optimal rate for single-level nonconvex stochastic optimization.

  3. Knowl 3 — Unified General Formulation of Hyper-Gradient Approximation

    model/method

    For the bilevel optimization problem min⁡λ∈Λf(λ):=F(λ,ωλ)\min_{\lambda \in \Lambda} f(\lambda) := F(\lambda, \omega_\lambda) subject to ωλ=arg⁡min⁡ωG(λ,ω)\omega_\lambda = \arg\min_\omega G(\lambda, \omega), common hyper-gradient evaluation strategies can be unified into a single framework.

    Given an approximation horizon K∈N+K \in \mathbb{N}_+, a sequence of inner states {ωk}k=0K−1\{\omega_k\}_{k=0}^{K-1}, vector representations {pk}k=0K−1\{p_k\}_{k=0}^{K-1}, and momentum/stepsize coefficients {βk}k=0K−1\{\beta_k\}_{k=0}^{K-1}, the general approximate hyper-gradient evaluated at outer state λ\lambda is defined as:

    ∇λfK=∂λF(λ,ωK)−∑k=0K−1βksk\nabla_\lambda f_K = \partial_\lambda F(\lambda, \omega_K) - \sum_{k=0}^{K-1} \beta_k s_k

    where sks_k admits two modes based on how pp and ∂ωλG\partial_{\omega \lambda} G are indexed:

    • Backward mode: sk=∂ωλG(λ,ωk)[∏s=k+1K−1(I−βs∂ω2G(λ,ωs))]pKs_k = \partial_{\omega \lambda} G(\lambda, \omega_k) \left[ \prod_{s=k+1}^{K-1} \left(I - \beta_s \partial_\omega^2 G(\lambda, \omega_s)\right) \right] p_K
    • Forward mode: sk=∂ωλG(λ,ωK)[∏s=k+1K−1(I−βs∂ω2G(λ,ωs))]pks_k = \partial_{\omega \lambda} G(\lambda, \omega_K) \left[ \prod_{s=k+1}^{K-1} \left(I - \beta_s \partial_\omega^2 G(\lambda, \omega_s)\right) \right] p_k

    with the convention ∏s=mnAs=Am×⋯×An\prod_{s=m}^n A_s = A_m \times \dots \times A_n if m≤nm \le n and ∏s=mnAs=I\prod_{s=m}^n A_s = I if m>nm > n.

    Special Cases Encompassed:

    1. Back-Propagation through Time (BP): Operates in backward mode with ωk=ω^k\omega_k = \hat{\omega}_k (the sequence generated by running KK steps of gradient descent on GG), pk=∂ωF(λ,ω^k)p_k = \partial_\omega F(\lambda, \hat{\omega}_k), and βk=ηk\beta_k = \eta_k (inner gradient descent step sizes).
    2. Neumann Series (NS): Operates in backward mode with fixed state ωk=ω^\omega_k = \hat{\omega}, fixed vector pk=∂ωF(λ,ω^)p_k = \partial_\omega F(\lambda, \hat{\omega}), and constant coefficient βk=β\beta_k = \beta.
    3. Conjugate Gradient (CG): Operates in forward mode with fixed state ωk=ω^\omega_k = \hat{\omega}, while {pk}\{p_k\} and {βk}\{\beta_k\} are generated adaptively by linear conjugate gradient descent steps applied to the system ∂ω2G(λ,ω^)x=∂ωF(λ,ω^)\partial_\omega^2 G(\lambda, \hat{\omega}) x = \partial_\omega F(\lambda, \hat{\omega}).

  4. Knowl 4 — Convergence Conditions and Error Bounds for Hyper-Gradient Approximation

    theoretical result

    Let mK:=∏s=0K(1−μGβs)m_K := \prod_{s=0}^K (1 - \mu_G \beta_s), eω,k:=∥ωk−ωλ∥e_{\omega, k} := \|\omega_k - \omega_\lambda\|, and ep,k:=∥pk−∂ωF(λ,ωλ)∥e_{p, k} := \|p_k - \partial_\omega F(\lambda, \omega_\lambda)\|, where μG>0\mu_G > 0 is the strong convexity parameter of G(λ,⋅)G(\lambda, \cdot).

    Sufficient Conditions for Convergence: Under standard Lipschitz smoothness assumptions, the general approximate hyper-gradient ∇λfK\nabla_\lambda f_K converges to the exact hyper-gradient ∇λf(λ)\nabla_\lambda f(\lambda) as K→∞K \to \infty if:

    1. lim⁡K→∞mK=0\lim_{K \to \infty} m_K = 0,
    2. lim⁡K→∞eω,K=0\lim_{K \to \infty} e_{\omega, K} = 0,
    3. lim⁡K→∞mK∑k=0K−1βkeω,kmk<∞\lim_{K \to \infty} m_K \sum_{k=0}^{K-1} \frac{\beta_k e_{\omega, k}}{m_k} < \infty, and
    4. Either lim⁡K→∞ep,K=0\lim_{K \to \infty} e_{p, K} = 0 (for backward mode) or lim⁡K→∞mK∑k=0K−1βkep,kmk<∞\lim_{K \to \infty} m_K \sum_{k=0}^{K-1} \frac{\beta_k e_{p, k}}{m_k} < \infty (for forward mode).

    Specific Asymptotic Rates:

    • Neumann Series Setting: If ωk=ω^K\omega_k = \hat{\omega}_K, pk=∂ωF(λ,ω^K)p_k = \partial_\omega F(\lambda, \hat{\omega}_K), and βk=β∈(ϵ/μG,1/μG)\beta_k = \beta \in (\epsilon / \mu_G, 1 / \mu_G) for some constant ϵ∈(0,1)\epsilon \in (0, 1), the estimation error is bounded by: ∥∇λfK−∇λf∥=O(eω,K)\|\nabla_\lambda f_K - \nabla_\lambda f\| = \mathcal{O}(e_{\omega, K})
    • Stochastic Back-Propagation Setting: If inner states are updated via stochastic gradient descent such that eω,k=O(k−0.5)e_{\omega, k} = \mathcal{O}(k^{-0.5}) with stepsize βk=O(k−1)\beta_k = \mathcal{O}(k^{-1}) and pk=∂ωF(λ,ω^K)p_k = \partial_\omega F(\lambda, \hat{\omega}_K), the estimation error satisfies: ∥∇λfK−∇λf∥=O(K−0.5)\|\nabla_\lambda f_K - \nabla_\lambda f\| = \mathcal{O}(K^{-0.5})

  5. Knowl 5 — One-Iteration Progress Bound for FSLA

    theoretical result

    Under LFL_F-Lipschitz smoothness of FF, LGL_G-Lipschitz smoothness of GG, μG\mu_G-strong convexity of G(λ,⋅)G(\lambda, \cdot), and bounded partial derivative operators, the expected outer objective value at iteration k+1k+1 in FSLA satisfies the descent inequality:

    E[f(λk+1)]≤f(λk)−αk2∥∇f(λk)∥2+αkΓ22E[∥ωk−ωλk∥2]+4αkΓ12E[∥vk−vλk∥2]+αkE[∥∇fk−dk∥2]−αk2(1−αkLf)E[∥dk∥2]\mathbb{E}[f(\lambda_{k+1})] \le f(\lambda_k) - \frac{\alpha_k}{2} \|\nabla f(\lambda_k)\|^2 + \alpha_k \Gamma_2^2 \mathbb{E}[\|\omega_k - \omega_{\lambda_k}\|^2] + 4\alpha_k \Gamma_1^2 \mathbb{E}[\|v_k - v_{\lambda_k}\|^2] + \alpha_k \mathbb{E}[\|\nabla f_k - d_k\|^2] - \frac{\alpha_k}{2}(1 - \alpha_k L_f) \mathbb{E}[\|d_k\|^2]

    where:

    • vλ:=[∂ω2G(λ,ωλ)]−1∂ωF(λ,ωλ)v_{\lambda} := [\partial_\omega^2 G(\lambda, \omega_\lambda)]^{-1} \partial_\omega F(\lambda, \omega_\lambda),
    • Γ12:=CG,ωλ2\Gamma_1^2 := C_{G, \omega \lambda}^2, with CG,ωλC_{G, \omega \lambda} bounding ∥∂ωλG∥\|\partial_{\omega \lambda} G\|,
    • Γ22:=2LF,λ2+4CF,ω2LG,ωλ2μG2\Gamma_2^2 := 2L_{F, \lambda}^2 + \frac{4 C_{F, \omega}^2 L_{G, \omega \lambda}^2}{\mu_G^2}, with LF,λL_{F, \lambda} and LG,ωλL_{G, \omega \lambda} denoting smoothness constants and CF,ωC_{F, \omega} bounding ∥∂ωF∥\|\partial_\omega F\|,
    • LfL_f is the Lipschitz constant of the full hyper-gradient ∇f(λ)\nabla f(\lambda).

    This inequality establishes that progress in minimizing f(λ)f(\lambda) is controlled by three tracking error terms: the inner-variable error Ak:=E[∥ωk−ωλk∥2]A_k := \mathbb{E}[\|\omega_k - \omega_{\lambda_k}\|^2], the auxiliary hyper-gradient state error Bk:=E[∥vk−vλk∥2]B_k := \mathbb{E}[\|v_k - v_{\lambda_k}\|^2], and the gradient momentum error Ck:=E[∥∇fk−dk∥2]C_k := \mathbb{E}[\|\nabla f_k - d_k\|^2].

  6. Knowl 6 — Bilevel Optimization Problem and Implicit Hyper-Gradient Formulation

    definition

    The general bilevel optimization problem is defined as:

    min⁡λ∈Λf(λ):=F(λ,ωλ)s.t.ωλ=arg⁡min⁡ωG(λ,ω)\min_{\lambda \in \Lambda} f(\lambda) := F(\lambda, \omega_\lambda) \quad \text{s.t.} \quad \omega_\lambda = \arg\min_\omega G(\lambda, \omega)

    where Λ⊆Rm\Lambda \subseteq \mathbb{R}^m denotes the constraint domain for the outer variable λ\lambda, ω∈Rn\omega \in \mathbb{R}^n denotes the inner variable, F:Λ×Rn→RF: \Lambda \times \mathbb{R}^n \to \mathbb{R} is the outer objective function, and G:Λ×Rn→RG: \Lambda \times \mathbb{R}^n \to \mathbb{R} is the inner objective function.

    Assuming that for every λ∈Λ\lambda \in \Lambda, the inner problem has a unique minimizer ωλ\omega_\lambda and the Hessian ∂ω2G(λ,ωλ)\partial_\omega^2 G(\lambda, \omega_\lambda) is invertible, the implicit function theorem defines the exact hyper-gradient ∇λf(λ)\nabla_\lambda f(\lambda) as:

    ∇λf(λ)=∂λF(λ,ωλ)+∇λωλ⊤∂ωF(λ,ωλ)\nabla_\lambda f(\lambda) = \partial_\lambda F(\lambda, \omega_\lambda) + \nabla_\lambda \omega_\lambda^\top \partial_\omega F(\lambda, \omega_\lambda)

    where the Jacobian of the inner solution mapping with respect to λ\lambda is:

    ∇λωλ=−∂ωλG(λ,ωλ)[∂ω2G(λ,ωλ)]−1\nabla_\lambda \omega_\lambda = - \partial_{\omega \lambda} G(\lambda, \omega_\lambda) \left[ \partial_\omega^2 G(\lambda, \omega_\lambda) \right]^{-1}

  7. Knowl 7 — Empirical Convergence and Complexity on Synthetic Quadratic Bilevel Objective

    empirical result

    The theoretical convergence rate and query complexity of hyper-gradient approximation methods were evaluated on a synthetic 5-dimensional quadratic bilevel problem with 10,000 data points:

    min⁡λ∈Λf(λ):=∥Aoωλ−bo∥2s.t.ωλ=arg⁡min⁡ω∥Ai,λλ+Ai,ωω−bi∥2\min_{\lambda \in \Lambda} f(\lambda) := \|A_o \omega_\lambda - b_o\|^2 \quad \text{s.t.} \quad \omega_\lambda = \arg\min_\omega \|A_{i,\lambda} \lambda + A_{i,\omega} \omega - b_i\|^2

    Key Findings:

    • Estimation Error Convergence: FSLA, Neumann Series (NS), Back-Propagation through Time (BP), and Conjugate Gradient (CG) all converge to the exact analytical hyper-gradient ∇λf\nabla_\lambda f.
    • Computational Efficiency: FSLA requires O(1)\mathcal{O}(1) matrix-vector queries per iteration by updating the tracking state vkv_k, whereas BP, NS, and CG require O(K)\mathcal{O}(K) matrix-vector queries per hyper-iteration for an approximation horizon KK. As a result, FSLA achieves lower estimation error in substantially less wall-clock running time.
    • Rate Validation: When inner variable sequences are constructed synthetically as ωk=ω∗+ω~/kα\omega_k = \omega^* + \tilde{\omega} / k^\alpha for α∈{2,1,0.5,0.25}\alpha \in \{2, 1, 0.5, 0.25\}, the squared hyper-gradient estimation error ∥∇fK−∇f∥2\|\nabla f_K - \nabla f\|^2 converges at rates matching the theoretical bounds predicted by the inner state sequence convergence.

  8. Knowl 8 — Performance of FSLA on Data Hyper-Cleaning Benchmarks

    empirical result

    FSLA was evaluated against Back-Propagation (BP), Neumann Series (NS), and Conjugate Gradient (CG) on data hyper-cleaning tasks over MNIST, Fashion-MNIST, and QMNIST datasets using a 4-layer convolutional neural network. The training set DiD_i contained 5,000 images with label perturbation rate γ=0.8\gamma = 0.8, and the validation set DoD_o contained 5,000 clean images. The outer objective optimizes sample weights σ(λj)∈(0,1)\sigma(\lambda_j) \in (0,1) via a sigmoid function to minimize validation loss:

    min⁡λl(ωλ;Do)s.t.ωλ=arg⁡min⁡ω1Ni∑j=1Niσ(λj)l(ω,Di,j)\min_{\lambda} l(\omega_\lambda; D_o) \quad \text{s.t.} \quad \omega_\lambda = \arg\min_\omega \frac{1}{N_i} \sum_{j=1}^{N_i} \sigma(\lambda_j) l(\omega, D_{i,j})

    Empirical Results:

    • Iteration Efficiency: On MNIST, FSLA converges to lower validation loss faster than BP variants across all tested inner steps (T∈{1,11,21,51,101,201}T \in \{1, 11, 21, 51, 101, 201\}), surpassing the best BP baseline (BP with T=201T=201) within 500 hyper-iterations.
    • Running Time Efficiency: In terms of wall-clock time log⁡10(Running Time)\log_{10}(\text{Running Time}), FSLA converges significantly faster than NS and CG baselines. NS runtime is dominated by multi-term Neumann series evaluations, and multi-step CG incurs substantial linear system solver overhead.
    • Superiority Over Single-Step Baselines: When compared directly with single-step CG with warm start (CG1,1CG_{1,1}), which incurs comparable per-iteration compute, FSLA converges much faster because CG1,1CG_{1,1} discards historical hyper-gradient information whereas FSLA accumulates it via vkv_k.

Coverage note — None was omitted; all key theoretical formulations (unified approximation lemma, sufficient convergence conditions, FSLA algorithm, one-iteration descent bound, nonconvex convergence theorem) and empirical benchmark results from the paper have been represented.

References

  1. 1.Bao, R.; Gu, B.; and Huang, H. 2019. Efficient Approximate Solution Path Algorithm for Order Weight L 1-Norm with Accuracy Guarantee. In 2019 IEEE International Conference on Data Mining (ICDM), 958–963. IEEE.
  2. 2.Bao, R.; Gu, B.; and Huang, H. 2020. Fast oscar and owl regression via safe screening rules. In International Conference on Machine Learning, 653–663. PMLR.
  3. 3.Bengio, Y. 2000. Gradient-based optimization of hyperparameters. Neural computation, 12(8): 1889–1900.
  4. 4.Chen, D.; and Hagan, M. T. 1999. Optimal use of regularization and cross-validation in neural network modeling. In IJCNN’99. International Joint Conference on Neural Networks. Proceedings (Cat. No. 99CH36339), volume 2, 1275–1280. IEEE.
  5. 5.Chen, T.; Sun, Y.; and Yin, W. 2021. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2102.04671.
  6. 6.Cutkosky, A.; and Orabona, F. 2019. Momentum-based variance reduction in non-convex sgd. arXiv preprint arXiv:1905.10018.
  7. 7.Do, C. B.; Foo, C.-S.; and Ng, A. Y. 2007. Efficient multiple hyperparameter learning for log-linear models. In NIPS, volume 2007, 377–384. Citeseer.
  8. 8.Domke, J. 2012. Generic methods for optimization-based modeling. In Artificial Intelligence and Statistics, 318–326. PMLR.
  9. 9.Ferris, M. C.; and Mangasarian, O. L. 1991. Finite perturbation of convex programs. Applied Mathematics and Optimization, 23(1): 263–273.
  10. 10.Franceschi, L.; Donini, M.; Frasconi, P.; and Pontil, M. 2017. Forward and reverse gradient-based hyperparameter optimization. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, 1165–1173. JMLR. org.
  11. 11.Franceschi, L.; Frasconi, P.; Salzo, S.; Grazzi, R.; and Pontil, M. 2018. Bilevel programming for hyperparameter optimization and meta-learning. arXiv preprint arXiv:1806.04910.
  12. 12.Gao, C.; Chen, Y.; Liu, S.; Tan, Z.; and Yan, S. 2020. Adversarialnas: Adversarial neural architecture search for gans. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 5680–5689.
  13. 13.Ghadimi, S.; and Wang, M. 2018. Approximation Methods for Bilevel Programming. arXiv preprint arXiv:1802.02246.
  14. 14.Grazzi, R.; Franceschi, L.; Pontil, M.; and Salzo, S. 2020. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, 3748–3758. PMLR.
  15. 15.Guo, Z.; Xu, Y.; Yin, W.; Jin, R.; and Yang, T. 2021. On Stochastic Moving-Average Estimators for Non-Convex Optimization. arXiv preprint arXiv:2104.14840.
  16. 16.Hong, M.; Wai, H.-T.; Wang, Z.; and Yang, Z. 2020. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05170.
  17. 17.Huang, F.; and Huang, H. 2021a. BiAdam: Fast Adaptive Bilevel Optimization Methods. arXiv preprint arXiv:2106.11396.
  18. 18.Huang, F.; and Huang, H. 2021b. Enhanced Bilevel Optimization via Bregman Distance. arXiv preprint arXiv:2107.12301.
  19. 19.Huang, F.; Li, J.; and Huang, H. 2021. SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients. arXiv preprint arXiv:2106.08208.
  20. 20.Ji, K.; and Liang, Y. 2021. Lower Bounds and Accelerated Algorithms for Bilevel Optimization. arXiv preprint arXiv:2102.03926.
  21. 21.Ji, K.; Yang, J.; and Liang, Y. 2020. Provably Faster Algorithms for Bilevel Optimization and Applications to Meta-Learning. arXiv preprint arXiv:2010.07962.
  22. 22.Khanduri, P.; Zeng, S.; Hong, M.; Wai, H.-T.; Wang, Z.; and Yang, Z. 2021. A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum. arXiv preprint arXiv:2102.07367.
  23. 23.Larsen, J.; Hansen, L. K.; Svarer, C.; and Ohlsson, M. 1996. Design and regularization of neural networks: the optimal use of a validation set. In Neural Networks for Signal Processing VI. Proceedings of the 1996 IEEE Signal Processing Society Workshop, 62–71. IEEE.
  24. 24.LeCun, Y.; Cortes, C.; and Burges, C. 2010. MNIST handwritten digit database. ATT Labs [Online]. Available: http://yann. lecun. com/exdb/mnist, 2.
  25. 25.Li, J.; Gu, B.; and Huang, H. 2020. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint arXiv:2009.00690.
  26. 26.Liao, R.; Xiong, Y.; Fetaya, E.; Zhang, L.; Yoon, K.; Pitkow, X.; Urtasun, R.; and Zemel, R. 2018. Reviving and improving recurrent back-propagation. In International Conference on Machine Learning, 3082–3091. PMLR.
  27. 27.Liu, H.; Simonyan, K.; and Yang, Y. 2018. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.09055.
  28. 28.Liu, R.; Gao, J.; Zhang, J.; Meng, D.; and Lin, Z. 2021. Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. arXiv preprint arXiv:2101.11517.
  29. 29.Lorraine, J.; and Duvenaud, D. 2018. Stochastic hyperparameter optimization through hypernetworks. arXiv preprint arXiv:1802.09419.
  30. 30.Maclaurin, D.; Duvenaud, D.; and Adams, R. 2015. Gradient-based hyperparameter optimization through reversible learning. In International Conference on Machine Learning, 2113–2122.
  31. 31.Mehra, A.; and Hamm, J. 2019. Penalty method for inversion-free deep bilevel optimization. arXiv preprint arXiv:1911.03432.
  32. 32.Nocedal, J.; and Wright, S. 2006. Numerical optimization. Springer Science & Business Media.
  33. 33.Okuno, T.; Takeda, A.; and Kawana, A. 2018. Hyperparameter learning via bilevel nonsmooth optimization. arXiv preprint arXiv:1806.01520.
  34. 34.Pedregosa, F. 2016. Hyperparameter optimization with approximate gradient. arXiv preprint arXiv:1602.02355.
  35. 35.Poon, C.; and Peyré, G. 2021. Smooth Bilevel Programming for Sparse Regularization. Advances in Neural Information Processing Systems, 34.
  36. 36.Sabach, S.; and Shtern, S. 2017. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2): 640–660.
  37. 37.Shaban, A.; Cheng, C.-A.; Hatch, N.; and Boots, B. 2018. Truncated back-propagation for bilevel optimization. arXiv preprint arXiv:1810.10667.
  38. 38.Soh, J. W.; Cho, S.; and Cho, N. I. 2020. Meta-transfer learning for zero-shot super-resolution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 3516–3525.
  39. 39.Solodov, M. 2007. An explicit descent method for bilevel convex optimization. Journal of Convex Analysis, 14(2): 227.
  40. 40.Song, X.; Gao, W.; Yang, Y.; Choromanski, K.; Pacchiano, A.; and Tang, Y. 2019. Es-maml: Simple hessian-free meta learning. arXiv preprint arXiv:1910.01215.
  41. 41.Sow, D.; Ji, K.; Guan, Z.; and Liang, Y. 2022. A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima. arXiv preprint arXiv:2203.01123.
  42. 42.Tian, Y.; Shen, L.; Su, G.; Li, Z.; and Liu, W. 2020. Alphagan: Fully differentiable architecture search for generative adversarial networks. arXiv preprint arXiv:2006.09134.
  43. 43.Tschiatschek, S.; Ghosh, A.; Haug, L.; Devidze, R.; and Singla, A. 2019. Learner-aware teaching: Inverse reinforcement learning with preferences and constraints. arXiv preprint arXiv:1906.00429.
  44. 44.Willoughby, R. A. 1979. Solutions of ill-posed problems (an tikhonov and vy arsenin). SIAM Review, 21(2): 266.
  45. 45.Wong, C.; Houlsby, N.; Lu, Y.; and Gesmundo, A. 2018. Transfer learning with neural automl. arXiv preprint arXiv:1803.02780.
  46. 46.Xiao, H.; Rasul, K.; and Vollgraf, R. 2017. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747.
  47. 47.Xu, Y.; Xie, L.; Zhang, X.; Chen, X.; Qi, G.-J.; Tian, Q.; and Xiong, H. 2019. PC-DARTS: Partial channel connections for memory-efficient architecture search. arXiv preprint arXiv:1907.05737.
  48. 48.Yadav, C.; and Bottou, L. 2019. Cold case: The lost mnist digits. In Advances in Neural Information Processing Systems, 13443–13452.
  49. 49.Yamada, I.; Yukawa, M.; and Yamagishi, M. 2011. Minimizing the Moreau envelope of nonsmooth convex functions over the fixed point set of certain quasi-nonexpansive mappings. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering, 345–390. Springer.
  50. 50.Yang, J.; Ji, K.; and Liang, Y. 2021. Provably Faster Algorithms for Bilevel Optimization. arXiv preprint arXiv:2106.04692.
  51. 51.Zintgraf, L.; Shiarli, K.; Kurin, V.; Hofmann, K.; and Whiteson, S. 2019. Fast context adaptation via meta-learning. In International Conference on Machine Learning, 7693–7702. PMLR.

Citation

MLA
Li, J., et al. “A Fully Single Loop Algorithm for Bilevel Optimization Without Hessian Inverse”. arXiv, 2021, http://arxiv.org/abs/2112.04660v2.
APA
Li, J., Gu, B., & Huang, H. (2021). A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse. arXiv. http://arxiv.org/abs/2112.04660v2
Chicago
Li, J., B. Gu, and H. Huang. 2021. “A Fully Single Loop Algorithm for Bilevel Optimization Without Hessian Inverse”. arXiv. http://arxiv.org/abs/2112.04660v2.
Harvard
Li, J., Gu, B. and Huang, H. (2021) “A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2112.04660v2.
Vancouver
1. Li J, Gu B, Huang H (2021) A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse. arXiv

BibTeX

@article{li2021fully,
  title = {A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse},
  author = {Li, Junyi and Gu, Bin and Huang, Heng},
  year = {2021},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2112.04660v2},
  eprint = {2112.04660}
}
Metadata:arXiv

Access the Paper

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

Open PDF