PaperlayerView exact revision on arXiv

Source-linked AI summary

Bilevel Optimization: Convergence Analysis and Enhanced Design

Kaiyi Ji, Junjie Yang, Yingbin Liang

arXiv:2010.07962v3cs.LGmath.OCstat.ML

TL;DR

Bilevel optimization lacks comprehensive convergence guarantees for important nonconvex-strongly-convex settings and efficient stochastic methods. The paper analyzes AID and ITD deterministically and proposes stocBiO stochastically, obtaining sharper or lower-order complexity guarantees and experimental validation.

  • Problem

    The paper addresses nonconvex-strongly-convex bilevel optimization, where existing deterministic analyses are limited and stochastic applications require more sample-efficient algorithms.

  • Method

    The paper provides unified convergence analyses for ITD-BiO and AID-BiO, using practical constant inner-loop steps and warm starts, and proposes stocBiO with a Neumann-series hypergradient estimator.

  • Results

    The deterministic analysis sharpens AID guarantees, establishes ITD guarantees, and stocBiO improves prior stochastic computational complexities orderwise with respect to κ and ϵ.

  • Takeaways & Limitations

    The results provide theoretical guarantees for bilevel optimizers used in meta-learning and hyperparameter optimization, with experiments validating the theory and stocBiO's efficiency.

  • Takeaways & Limitations

    The analysis assumes a strongly convex lower-level function and a nonconvex total upper-level objective, including corresponding stochastic assumptions.

Abstract

from arXiv · show

Bilevel optimization has arisen as a powerful tool for many machine learning problems such as meta-learning, hyperparameter optimization, and reinforcement learning. In this paper, we investigate the nonconvex-strongly-convex bilevel optimization problem. For deterministic bilevel optimization, we provide a comprehensive convergence rate analysis for two popular algorithms respectively based on approximate implicit differentiation (AID) and iterative differentiation (ITD). For the AID-based method, we orderwisely improve the previous convergence rate analysis due to a more practical parameter selection as well as a warm start strategy, and for the ITD-based method we establish the first theoretical convergence rate. Our analysis also provides a quantitative comparison between ITD and AID based approaches. For stochastic bilevel optimization, we propose a novel algorithm named stocBiO, which features a sample-efficient hypergradient estimator using efficient Jacobian- and Hessian-vector product computations. We provide the convergence rate guarantee for stocBiO, and show that stocBiO outperforms the best known computational complexities orderwisely with respect to the condition number $κ$ and the target accuracy $ε$. We further validate our theoretical results and demonstrate the efficiency of bilevel optimization algorithms by the experiments on meta-learning and hyperparameter optimization.

1. Introduction

The paper studies nonconvex-strongly-convex bilevel optimization, developing sharper deterministic convergence analyses and a more sample-efficient stochastic algorithm. It establishes orderwise complexity improvements, compares ITD and AID, and validates the results experimentally.

  • Problem setting: The paper focuses on bilevel problems with a nonconvex upper-level objective and a strongly convex lower-level function.This setting occurs in applications including meta-learning and hyperparameter optimization.
  • Deterministic optimization: The first focus is a unified, sharper convergence and complexity analysis covering ITD- and AID-based deterministic bilevel optimizers.The analysis uses practical constant inner-loop steps and a warm-start strategy.
  • Deterministic optimization: AID-BiO improves prior deterministic complexity orders by κ, κϵ^-1/4, κ, and κ for gradient, inner-gradient, Jacobian-vector, and Hessian-vector evaluations, respectively.The improvement is attributed to refined analysis with constant inner-loop steps and warm starts.
  • Deterministic optimization: AID-BiO requires fewer Jacobian- and Hessian-vector products than ITD-BiO by orders of κ and κ^1/2, respectively.The paper interprets this comparison as indicating greater computational and memory efficiency for AID.
  • Stochastic optimization: stocBiO uses a mini-batch implicit-differentiation hypergradient estimator based on the Neumann series and achieves lower complexity orders than BSA and TTSA.Relative to BSA, its gradient complexities improve by orders of κ and ϵ^-1, while its Jacobian-vector complexity improves by κ; relative to TTSA, complexities improve by ϵ^-1/2.
  • Empirical validation: Experiments validate the deterministic theory and demonstrate stocBiO's efficiency in stochastic bilevel optimization, including meta-learning and hyperparameter optimization.The paper also frames bilevel optimization as relevant to reinforcement learning and other machine learning applications.

2. Algorithms

The paper presents deterministic AID-BiO and ITD-BiO methods with nested inner optimization and outer hypergradient estimation, then introduces stocBiO for stochastic bilevel optimization. stocBiO uses stochastic inner updates and a Neumann-series hypergradient estimator based on Hessian-vector products.

  • Deterministic bilevel algorithms: AID-BiO and ITD-BiO use nested loops: inner gradient descent approximates y*(x), while the outer loop estimates and updates the hypergradient.AID-BiO uses conjugate-gradient iterations for its implicit hypergradient; ITD-BiO differentiates through the inner gradient-descent updates.
  • Deterministic bilevel algorithms: Warm-starting each inner loop from the preceding output enables tracking-error backpropagation across loops.The method initializes the next inner loop with the previous inner-loop output rather than a random point.
  • Deterministic bilevel algorithms: AID-BiO estimates the hypergradient by approximately solving a linear system with conjugate gradients and computing Jacobian-vector products.The construction uses Hessian-vector products for conjugate-gradient iterations and Jacobian-vector products through automatic differentiation.
  • Stochastic bilevel algorithm: stocBiO performs D stochastic-gradient inner updates, then estimates the hypergradient using independent mini-batches and a Neumann-series procedure.Its estimator constructs v_Q through recursively applied Hessian-vector products rather than explicitly forming Hessians.
  • Stochastic bilevel algorithm: The stochastic estimator assigns exponentially decaying batch sizes across Neumann-series components to reduce hypergradient-estimation complexity.The analysis accounts for each component’s different contribution to variance and uses smaller batches for later-indexed components.

3. Definitions and Assumptions

The analysis assumes a nonconvex upper-level objective and a lower-level function strongly convex in its inner variable, with smoothness and stochastic variance conditions. It evaluates methods by gradient, Jacobian-vector, and Hessian-vector product complexity for reaching an approximate stationary point.

  • Core problem setting: The lower-level function is μ-strongly convex in y, while the total objective Φ(x) is nonconvex in x.The stochastic setting adopts corresponding assumptions for G(x,y;ζ) and Φ(x).
  • Stationarity criterion: An ε-accurate stationary point satisfies E∥∇Φ(x̄)∥2 ≤ ε for the algorithm’s output x̄.This criterion is used because the objective is nonconvex.
  • Complexity metrics: Complexity is measured by partial-gradient evaluations plus Jacobian-vector and Hessian-vector products.The metrics count operations involving f and g, with analogous stochastic metrics for F.
  • Regularity assumptions: The deterministic assumptions include joint continuous differentiability and Lipschitz conditions on high-order derivatives.These conditions apply to derivatives such as ∇x∇yg and ∇²_yg.
  • Stochastic assumptions: The stochastic analysis assumes bounded variance for the lower-level stochastic gradient, with variance bounded by σ².The stated condition controls deviations of ∇G(z;ζ) from its mean gradient ∇g(z).

4. Main Results for Bilevel Optimization

The paper proves convergence and complexity guarantees for AID-BiO, ITD-BiO, and stocBiO in the nonconvex-strongly-convex setting. AID-BiO is more efficient than ITD-BiO in product complexities, while stocBiO improves prior stochastic methods in condition-number and accuracy dependence.

  • Deterministic Bilevel Optimization: AID-BiO reaches an ε-accurate stationary point with gradient complexities O(κ^3ε^-1) for f and O(κ^4ε^-1) for g.Its parameter choices use D = Θ(κ) inner iterations and N = Θ(√κ) conjugate-gradient iterations.
  • Deterministic Bilevel Optimization: The refined AID-BiO analysis improves prior complexities by orders κ, κε^-1/4, κ, and κ for gradient and product metrics.The improvement uses a constant number of inner-loop steps and warm-start tracking-error analysis.
  • Deterministic Bilevel Optimization: ITD-BiO reaches an ε-accurate stationary point with Gc(f, ε) = O(κ^3ε^-1) and Gc(g, ε) = eO(κ^4ε^-1).The theorem permits D ≥ Θ(κ log 1/ε) inner-loop steps under the stated assumptions.
  • Deterministic Bilevel Optimization: AID-BiO improves ITD-BiO’s Jacobian-vector and Hessian-vector product complexities by orders κ and κ^0.5, respectively.The paper interprets this comparison as making AID-BiO more computationally and memory efficient.
  • Stochastic Bilevel Optimization: stocBiO’s Jacobian- and Hessian-vector product complexities are JV(G, ε) = O(κ^5ε^-2) and HV(G, ε) = eO(κ^6ε^-2).Theorem 3 states sublinear convergence, with error decaying exponentially in Q and sublinearly in the batch sizes.
  • Stochastic Bilevel Optimization: stocBiO improves BSA by orders κ and ε^-1 for gradient complexities and by order κ for Jacobian-vector products.It improves TTSA’s gradient, Jacobian-vector, and Hessian-vector product complexities by order ε^-0.5.

5. Applications to Meta-Learning

The meta-learning application casts task adaptation and shared representation learning as a bilevel procedure, then evaluates deterministic bilevel optimizers against established meta-learning methods. Experiments show faster convergence and greater stability for the proposed bilevel approaches in the reported settings.

  • 5. Applications to Meta-Learning: Meta-learning adapts task-specific parameters in a lower-level stage and optimizes shared embedding parameters using held-out task data in an upper-level stage.
  • 5. Applications to Meta-Learning: Task-specific lower-level losses are strongly convex because task parameters often form the final linear layer with an L2-like strongly-convex regularizer, while the upper-level objective is generally nonconvex.
  • 5.1. Experiments: AID-BiO-constant converges faster than AID-BiO-increasing on miniImageNet and FC100 for both training and test accuracy, and achieves better final test accuracy than ANIL and MAML.
  • 5.1. Experiments: AID-BiO is slightly faster than ITD-BiO on training and test accuracy, consistent with the theoretical comparison.
  • 5.1. Experiments: With T = 10 on miniImageNet and T = 20 on FC100, ITD-BiO remains stable with small variance, whereas ANIL suddenly descends or diverges.

6. Applications to Hyperparameter Optimization

The hyperparameter-optimization application uses stochastic bilevel optimization because training and validation datasets are often large. Across logistic regression and data hyper-cleaning experiments, stocBiO shows faster convergence than the compared stochastic methods.

  • 6. Applications to Hyperparameter Optimization: Hyperparameter optimization searches representation or regularization parameters by minimizing validation error evaluated at parameters minimizing regularized training error.
  • 6. Applications to Hyperparameter Optimization: Large training and validation datasets make stochastic algorithms preferable, so the hyperparameter-optimization problem fits the stochastic bilevel setting addressed by stocBiO.
  • 6.1. Experiments: On logistic regression with 20 Newsgroup, stocBiO achieves the fastest convergence and best test accuracy among the comparison algorithms.
  • 6.1. Experiments: StocBiO outperforms HOAG for batch sizes 100, 500, 1000, and 2000, with performance reported as not very sensitive to batch size.
  • 6.1. Experiments: On MNIST data hyper-cleaning, stocBiO has the fastest convergence in training and test loss, with a more significant improvement at smaller corruption rates.
  • 6.1. Experiments: TTSA converges slowly with large variance, while stocBiO provides smaller hypergradient-estimation variance and faster convergence in the reported hyperparameter-optimization experiment.

7. Conclusion

The paper develops enhanced convergence analyses for deterministic nonconvex-strongly-convex bilevel optimization and proposes stocBiO for the stochastic setting. Theoretical guarantees and experiments support improved complexity and practical efficiency across bilevel applications.

  • The paper analyzes deterministic bilevel optimization and proposes a novel stochastic algorithm with orderwise computational-complexity improvements.
  • The convergence analysis provides theoretical guarantees for ITD-BiO, AID-BiO, and stocBiO in meta-learning and hyperparameter optimization.
  • Experiments validate the deterministic theory and demonstrate stocBiO's superior efficiency for stochastic bilevel optimization.

Supplementary Materials

The supplementary materials specify the datasets, architectures, optimizers, and hyperparameters used for deterministic meta-learning experiments. They cover FC100 and miniImageNet with shared convolutional-network and optimization settings.

  • Datasets and Model Architectures: FC100 contains 100 classes with 600 32×32 images per class, split into 60 training, 20 validation, and 20 testing classes.
  • Datasets and Model Architectures: All algorithms use four-layer convolutional neural networks composed of four convolutional blocks.
  • Datasets and Model Architectures: miniImageNet contains 100 classes with 600 84×84 images per class, partitioned into 64 training, 16 validation, and 20 testing classes.
  • Optimization and Hyperparameters: ANIL and MAML use repository implementations, while Adam is used for every algorithm's outer-loop update.
  • Optimization and Hyperparameters: The experiments vary inner-loop stepsizes, outer-loop stepsizes, task or mini-batch sizes, and inner-loop iteration counts across figures.

B. Further Specifications on Hyperparameter Optimization Experiments

This section details the hyperparameter-optimization experiments and introduces supporting lemmas for hypergradient and convergence analysis. It covers data hyper-cleaning, logistic regression, stochastic sampling choices, and bounds used in the proofs.

  • Experiments: The experiments evaluate stocBiO on data hyper-cleaning and logistic regression hyperparameter-optimization problems.
  • Logistic Regression on 20 Newsgroup: The logistic-regression study compares stocBiO with reverse, AID-FP, AID-CG, and HOAG on 20 Newsgroup.
  • Logistic Regression on 20 Newsgroup: For logistic regression, 20 topics and feature dimension 101631 define the problem, while stocBiO uses η = 0.5 and Q = 10.
  • Data Hyper-Cleaning on MNIST: The data hyper-cleaning experiment uses MNIST-derived datasets with 20000 training, 5000 validation, and 10000 testing images.
  • Supporting Analysis: The supporting lemmas characterize derivative regularity, hypergradient-estimation error, and quantities used in the convergence proofs.

E.1. Proof of Theorem 1

The proof establishes AID-BiO's iteration and derivative-complexity bounds, while the ITD analysis controls gradient-estimation error through the inner-loop differentiation path. Strong convexity and smoothness assumptions underpin these guarantees.

  • AID-BiO: The proof selects inner-loop parameters satisfying D ≥ Θ(κ) and N ≥ Θ(√κ) to control the approximation error.
  • AID-BiO: AID-BiO requires K = O(κ^3ϵ^-1) outer iterations to reach an ϵ-accurate stationary point.
  • ITD-BiO: The ITD analysis derives the estimator by differentiating through the inner-loop gradient-descent path and using the lower-level optimum's strong-convexity condition.
  • ITD-BiO: For ITD-BiO, the gradient-estimation error decays exponentially with the number D of inner-loop steps.

F.1. Proof of Theorem 2

The proof derives convergence and complexity guarantees for ITD-BiO by controlling gradient-estimation error, variance, and inner-loop tracking error under strong convexity.

  • ITD-BiO requires K = O(κ3ϵ−1) outer iterations to reach an ϵ-accurate stationary point.The complexity analysis then expresses gradient, Jacobian, and Hessian-vector product costs in terms of K and inner-loop parameters.
  • The theorem’s complexity accounting includes gradient evaluations together with Jacobian- and Hessian-vector product computations.The listed gradient complexity includes Gc(f, ϵ) = 2K = O(κ3ϵ−1) and Gc(g, ϵ) = KD.
  • The resulting convergence proof combines estimator bias, variance, and tracking bounds through conditional expectations and telescoping over outer iterations.The argument invokes strong convexity, Cauchy–Schwarz, Young’s inequality, and matrix inverse perturbation bounds.
  • The analysis bounds the gradient estimator’s first-moment error and variance, with both depending on the inner-loop tracking error ∥yDk−y∗(xk)∥2.Separate lemmas characterize estimator error, variance, and tracking error before they are combined in the theorem proof.
  • The tracking-error bound follows from strong convexity and smoothness of the lower-level objective, with inner-loop stepsize α = 2/(L+µ) and D selected so λ < 1.The proof uses telescoping inequalities over inner-loop steps and the prescribed geometric batch-size choice.

G.3. Proof of Theorem 3

The proof of Theorem 3 establishes stochastic convergence by combining smoothness, estimator variance, and inner-loop tracking bounds, then derives parameter choices and computational complexity.

  • The proof combines smoothness of Φ with bounds on gradient-estimation variance and tracking error to control the expected stationarity measure.The analysis chooses β = 1/(4Lφ), applies the supporting lemmas, and telescopes the resulting inequality over outer iterations.
  • The inner-loop length D is chosen to control the tracking error generated by D gradient-descent steps at each outer iteration.The lower-level task losses are assumed µ-strongly-convex in their inner variables.
  • The theorem provides parameter choices sufficient for an ϵ-accurate stationary point, with the output selected uniformly from x0, ..., xK−1.The proof states the stationarity condition as E∥∇Φ(x̄)∥2 ≤ ϵ.
  • The resulting stochastic gradient complexities are Gc(F, ϵ) = O(κ5ϵ−2) and Gc(G, ϵ) = O(κ9ϵ−2).The corresponding Jacobian-vector product complexity is JV(G, ϵ) = O(κ5ϵ−2).
  • The proof’s estimator analysis separately controls bias and variance before substituting these bounds into the theorem’s convergence inequality.Supporting lemmas characterize the first-moment error, variance, and inner-loop tracking behavior.
Loading 2010.07962v3…