PaperlayerView exact revision on arXiv

Source-linked AI summary

Will Bilevel Optimizers Benefit from Loops

Kaiyi Ji, Mingrui Liu, Yingbin Liang, Lei Ying

arXiv:2205.14224v3cs.LGmath.OCstat.ML

TL;DR

Existing analyses did not provide refined comparisons across the loop implementations of AID-BiO and ITD-BiO. The paper develops unified convergence analyses and complexity comparisons, finding that loops benefit AID-BiO and are necessary for vanishing convergence error in ITD-BiO.

  • Problem

    Existing studies covered only some AID-BiO and ITD-BiO loop choices, and their complexity bounds were not refined enough for rigorous implementation comparisons.

    Source: §1 · p. 3

  • Method

    The paper establishes unified convergence analyses for all loop-parameter choices in AID-BiO and ITD-BiO, then derives computational complexities for their implementations.

    Source: §1 · p. 3

  • Results

    AID-BiO benefits from both loops, while ITD-BiO requires loops for vanishing convergence error and its No-loop scheme has unavoidable non-vanishing error.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    Loop choices have different consequences across the two optimizers: they benefit AID-BiO's computational efficiency and ITD-BiO's convergence accuracy.

    Source: §7 · p. 12

    The ITD convergence bounds retain a gap on the order of αµ, which the authors leave for future work.

    Source: §5 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

The paper compares loop choices in AID-BiO and ITD-BiO, where inner-solution accuracy and hypergradient approximation affect computational efficiency. It develops unified convergence analyses to compare their implementations and finds different benefits for the two optimizers.

1 Introduction

  • Earlier AID-BiO analyses covered only some implementations and were not refined enough to compare their computational costs rigorously.The paper develops a unified convergence theory for all choices of N and Q and specializes it to all four implementations.Source: §1 · p. 3
  • AID-BiO benefits from both the inner-solution N-loop and the Hessian-inverse-vector Q-loop, despite the added work per update.The N-loop improves inner-solution accuracy, which matters because the bilevel hypergradient includes second-order derivatives; the Q-loop reduces gradient complexity.Source: §1 · pp. 2–3
  • ITD-BiO ties its two iteration counts, Q=N, leaving N-N-loop and No-loop implementations; whether loops improve efficiency had remained open.The paper develops a unified convergence theory for all N and compares the computational complexity of both implementations.Source: §1 · p. 3
  • For ITD-BiO, the looped scheme is necessary for vanishing convergence error, while No-loop has unavoidable non-vanishing error.The paper also gives a convergence lower bound supporting the necessity of N-N-loop.Source: §1 · pp. 3–4
  • For AID-BiO with small Q, convergence analysis handles a potentially large, nondecreasing Hessian-inverse approximation error by coupling it with inner-loop error.For ITD-BiO, the analysis removes the boundedness assumption on y*(x) through error analysis over the full execution.Source: §1 · p. 4

2 Algorithms

AID-BiO estimates an inner solution and an implicit hypergradient within each base-loop update, while ITD-BiO differentiates through the inner-update trajectory. Their loop parameters determine the available implementations.

2.1 AID-based Bilevel Optimization Algorithm

  • AID-BiO performs N gradient-descent steps on the inner function, optionally warm-starting each loop from the preceding inner solution.The choice of N ranges from a constant to a large value that forms an N-loop.Source: §2.1 · p. 4
  • AID-BiO estimates the hypergradient by solving a linear system with Q gradient-descent steps and uses Hessian- and Jacobian-vector products.A warm start is used for the linear-system solve; N and Q can each be small or large, yielding four implementations.Source: §2.1 · pp. 4–5

2.2 ITD-Based Bilevel Optimization Algorithm

  • ITD-BiO estimates the hypergradient by backpropagating through the N-step inner gradient-descent trajectory rather than using the implicit-gradient formulation.This computes tractable Hessian- and Jacobian-vector products instead of directly computing second-order derivatives.Source: §2.2 · p. 5
  • Because ITD-BiO sets Q=N, it has two base-loop implementations: N-N-loop with large N or No-loop with small N.The paper analyzes convergence and compares computational efficiency for both choices.Source: §2.2 · p. 5

3 Definitions and Assumptions

The analysis assumes a strongly convex inner problem and a possibly nonconvex outer objective, and measures stationarity and computational effort. A bounded-gradient assumption can be removed in specified cases.

3 Definitions and Assumptions

  • The inner-level function is assumed to be strongly convex in y, while the outer objective may be nonconvex in x.The paper defines an ϵ-accurate stationary point by requiring the output's outer-objective gradient norm to be at most ϵ.Source: §3 · p. 5
  • Computational complexity is measured by gradient evaluations and by Jacobian- and Hessian-vector product evaluations needed to reach an ϵ-accurate stationary point.Source: §3 · pp. 5–6
  • The analysis uses Lipschitz conditions on gradients and higher-order derivatives, and assumes bounded ∇yf(x, y*(x)).The boundedness condition applies at the inner-level minimizer rather than requiring ∇f to be bounded everywhere.Source: §3 · p. 6
  • The bounded-gradient assumption can be removed when the outer objective is convex or strongly convex, or when x is projected onto a bounded constraint set.Source: §3 · p. 6

4 Convergence Analysis of AID-BiO

The section establishes convergence analyses and computational complexity bounds for AID-BiO’s implementations. Its comparisons show that a larger inner loop improves overall complexity, while a larger Hessian-inverse-vector loop can reduce gradient complexity.

4 Convergence Analysis of AID-BiO

  • The section specializes the unified analyses into complexity bounds for the four implementations to compare their computational efficiency.It presents the broader convergence and complexity analysis as guidance for choosing an AID-BiO architecture.Source: §4 · p. 6, §4.1 · p. 7

4.1 Convergence Rate and Computational Complexity

  • Two unified AID-BiO convergence theorems cover all N and Q regimes; the first gives tighter bounds for small Q, while the alternative theorem gives tighter bounds for large Q.The large-Q analysis also relaxes the stepsize requirement.Source: §4.1 · p. 7

4.2 Comparison among Four Implementations

  • The N-loop improves matrix-vector complexity from e O(κ6ϵ−1) to e O(κ4ϵ−1) and gradient complexity from e O(κ6ϵ−1) to e O(κ5ϵ−1).The comparison is between N = 1 and N = Θ(κ ln κ), with Q fixed.Source: §4.2 · p. 8
  • A larger N reduces inner-level approximation error, permitting a more aggressive stepsize and faster convergence; bilevel gradients are more sensitive to this error because they involve additional second-order derivatives.The text contrasts this sensitivity with minimax optimization, where No-loop GDA with N = 1 can outperform N-loop GDA.Source: §4.2 · p. 8
  • With N = 1, Q-loop keeps matrix-vector complexity at e O(κ6ϵ−1) but reduces gradient complexity from e O(κ6ϵ−1) to e O(κ5ϵ−1).A similar gradient-complexity improvement is reported when comparing N-Q-loop with N-loop.Source: §4.2 · pp. 8–9
  • N-Q-loop and N-loop achieve matrix-vector complexity e O(κ4ϵ−1), versus e O(κ6ϵ−1) for Q-loop and No-loop; N-Q-loop has the lowest gradient complexity.The comparison covers all four AID-BiO implementations.Source: §4.2 · p. 9

5 Convergence Analysis of ITD-BiO

The section gives convergence analysis for ITD-BiO across choices of N, then derives complexity bounds for its two implementations. Upper and lower bounds show that large N is needed for vanishing error, while constant N incurs an unavoidable non-vanishing error under the stated assumptions.

Convergence bounds

  • The upper convergence bound combines a term that decays sublinearly with K and an error term independent of K that may not vanish for small N.The lower bound is introduced to establish that this small-N error is fundamental.Source: §5 · p. 9

Lower bound

  • The lower-bound and upper-bound error terms match in their dependence on M^2L^2(1−αµ)^N, but a gap of order αµ remains.The paper identifies closing this gap as future work.Source: §5 · p. 9

Convergence bounds

  • Large N is necessary for ITD-BiO to guarantee vanishing convergence error; constant N necessarily leaves a non-vanishing error under standard assumptions.The upper and lower bounds agree on the error term associated with small N.Source: §5 · pp. 9–10

N-N-loop complexity

  • The N-N-loop implementation guarantees an ϵ-accurate stationary point with gradient and matrix-vector product complexities eO(κ^4ϵ^-1).This bound is stated for N=Θ(κ ln κ/ϵ).Source: §5 · p. 10

No-loop and lower bound

  • For constant N, the convergence bound contains a non-vanishing error term that the lower bound shows is unavoidable.The paper notes an exception for settings with an extremely small response Jacobian, where constant-level N can still achieve a small error.Source: §5 · pp. 9–10

Small response Jacobian

  • When the response Jacobian is extremely small, the convergence error is proportional to its squared norm, so constant-level N can still achieve a small error.This setting is discussed as occurring in some deep-learning applications.Source: §5 · p. 10

6 Empirical Verification

Experiments compare AID-BiO implementations on MNIST and ITD-BiO implementations on a hyper-representation problem. The reported results favor multiple inner iterations for AID-BiO and show a lower validation loss for ITD-BiO with N-N-loop than with No-loop.

Experiments on AID-BiO

  • The AID-BiO experiment is a hyperparameter-optimization problem that minimizes validation loss at the optimal model parameters of regularized empirical risk minimization.The training and validation data define the inner and outer objectives, respectively.Source: §6 · pp. 10–11
  • With N=20, AID-BiO learning curves are significantly better than with N=1; N-Q-loop and N-loop perform comparably, as do Q-loop and No-loop.The authors report the comparison for training and test losses against running time on MNIST.Source: §6 · p. 11, Figure 1 · p. 11

Experiments on ITD-BiO

  • After 500 total iterations, ITD-BiO N-N-loop with N=20 reaches validation loss 0.004, versus 0.04 for No-loop with N=1.The experiment uses a hyper-representation problem with regression parameters as the inner variables and representation parameters as the outer variables.Source: §6 · p. 11, Table 3 · p. 12

7 Conclusion

The paper compares loop choices for AID-BiO and ITD-BiO through unified convergence analysis and computational-complexity results. It concludes that N-loops benefit AID-BiO efficiency and ITD-BiO accuracy, unlike the reported No-loop advantage in conventional minimax optimization.

Conclusion

  • Unified convergence analysis across loop-parameter choices enables formal comparison among implementations of AID-BiO and ITD-BiO.The paper says its analysis techniques may also be useful for studying stochastic and variance-reduced bilevel optimizers.Source: §7 · p. 12
  • N-loops are beneficial for better computational efficiency in AID-BiO and better convergence accuracy in ITD-BiO.Source: §7 · p. 12
  • This loop-related conclusion contrasts with conventional minimax optimization, where the No-loop scheme achieves better computational efficiency.Source: §7 · p. 12

Supplementary Materials

The supplementary related-work discussion surveys gradient-based and stochastic bilevel optimization, alongside machine-learning applications. It situates this paper's analysis as covering loop regimes left out of earlier deterministic convergence studies.

A Expanded Related Work

  • Earlier deterministic convergence analyses focused on N-Q-loop AID-BiO and N-N-loop ITD-BiO, while this study analyzes all N and Q regimes.The discussion also reviews AID- and ITD-based hypergradient methods and lower-complexity-bound work.Source: A Expanded Related Work · p. 15
  • Stochastic bilevel methods include SGD-type algorithms, variance reduction, momentum, adaptive learning rates, and Hessian-free Evolution Strategies.The paper focuses on deterministic bilevel optimization but says its techniques may extend to refined stochastic complexity analysis.Source: A Expanded Related Work · p. 15
  • Bilevel optimization is applied to hyperparameter optimization and few-shot meta-learning, including learning common task embeddings and task-specific adaptation.Source: A Expanded Related Work · p. 15

B Further Specifications on Hyperparameter Optimization Experiments

The experiments test different N and Q choices, while the proof sketch tracks hypergradient error from the inner-solution and linear-system approximations. Larger N permits a more aggressive outer stepsize, at the cost of more N-loop updates.

B Further Specifications on Hyperparameter Optimization Experiments

  • Experiments on 10-class MNIST add uniformly distributed label noise to 10% of the data; inner and outer learning rates are tuned over {0.1, 0.01, 0.001}, with results averaged across five random seeds.All experiments run on a single NVIDIA Tesla P100 GPU.Source: B Further Specifications on… · pp. 15–16

C Proof Sketch of Theorem 1

  • The proof decomposes hypergradient approximation error into inner-solution and linear-system errors, then bounds those errors using previous iterations’ errors.The two error components have iteratively decreasing terms that support the final convergence analysis.Source: C Proof Sketch of Theorem 1 · p. 16
  • A larger N permits a smaller λ and a more aggressive outer stepsize β, improving convergence at the cost of N inner-loop updates.With small N, such as N = 1, λ must be Θ(αµ), so β must be smaller and convergence slower.Source: C Proof Sketch of Theorem 1 · p. 16

D Proof of Theorem 1

The proof develops bounds for the approximation errors and combines them to establish convergence. Its Corollary 1 specialization gives an iteration count for reaching an ϵ-accurate stationary point.

Proof of Theorem 1

E Proof of Corollary 1

  • Under the Corollary 1 choices, the proof states that the quantity ew scales as Θ(κ^7).The complexity result is stated separately as an iteration count for ϵ-accuracy.Source: E Proof of Corollary 1 · p. 22
  • Corollary 1 gives K = O(κ^4ϵ^-1) iterations to reach an ϵ-accurate stationary point.The passage introduces matrix-vector product complexities but does not provide their values.Source: E Proof of Corollary 1 · p. 22

F Proof of Corollary 2

These proof sections specialize convergence and complexity arguments for different parameter choices. The supplied excerpts state an iteration bound for Corollary 2 and selected parameter scalings for later corollaries.

F Proof of Corollary 2

  • Corollary 2 gives K = O(κ^6ϵ^-1) iterations to reach an ϵ-accurate stationary point.The passage introduces matrix-vector product complexities but does not provide their values.Source: F Proof of Corollary 2 · p. 23

G Proof of Theorem 2

  • The Proof of Theorem 2 uses zero initialization for v when deriving its bound.The supplied proof excerpt refers to equations (30)–(34).Source: G Proof of Theorem 2 · pp. 23–24

H Proof of Corollary 3

  • The Corollary 3 proof chooses N = c_nκ ln κ and Q = c_qκ ln κ.The excerpt does not include the resulting complexity expression.Source: H Proof of Corollary 3 · p. 25

I Proof of Corollary 4

J Proof of Theorem 3

  • The Proof of Theorem 3 bounds an update quantity by applying gradient descent to the strongly convex, smooth inner function.The proof then telescopes that bound over the inner iterations.Source: J Proof of Theorem 3 · pp. 26–27

Proof of Theorem 3

  • The Proof of Theorem 3 telescopes an inequality over outer iterations as part of its convergence argument.The excerpt refers to the smoothness of the outer objective and a bound from Lemma 5.Source: Proof of Theorem 3 · p. 29

K Proof of Corollary 5

The Corollary 5 proof reports a gradient-complexity bound. The following proof excerpts give a stepsize scaling and introduce a construction of loss functions.

K Proof of Corollary 5

L Proof of Corollary 6

  • The Corollary 6 proof states β = Θ(κ^3) after specifying w = Θ(κ^4) and τ = Θ(κ).The excerpt does not state the resulting complexity.Source: L Proof of Corollary 6 · p. 31

M Proof of Theorem 4

  • Theorem 4’s proof introduces a construction of loss functions and analyzes the ITD-based method’s updates.The supplied excerpts do not specify the construction’s full form or its result.Source: M Proof of Theorem 4 · p. 31
Loading 2205.14224v3…