On the Convergence Theory for Hessian-Free Bilevel Algorithms

Daouda Sow, Kaiyi Ji, Yingbin Liang

TL;DR

Bilevel optimization is a powerful framework for meta-learning and hyperparameter tuning, but it traditionally requires expensive second-order derivatives (Hessians) that fail to scale to large neural networks. This paper introduces PZOBO (Partial Zeroth-Order-like Bilevel Optimizer), a "Hessian-free" algorithm that uses a clever zeroth-order trick to estimate only the most difficult part of the gradient. The authors provide the first formal convergence proof for this approach and demonstrate massive speedups—beating state-of-the-art meta-learners on complex tasks like ResNet-12 training.

The Bottleneck in Bilevel Optimization

Bilevel optimization involves two nested problems: an "outer" objective that depends on the optimal solution of an "inner" objective. In meta-learning, for example, the inner loop learns a specific task, while the outer loop learns the best initialization for all tasks.

The mathematical bottleneck in this process is the hypergradient—the gradient of the outer objective. Calculating it exactly requires computing the response Jacobian (how the inner solution changes when the outer variable changes). This typically involves second-order derivatives (Hessians), which are computationally brutal and memory-intensive for high-dimensional models like deep neural networks.

Existing "Hessian-free" methods either ignore these terms entirely (leading to poor accuracy) or attempt to estimate the entire hypergradient using zeroth-order methods (sampling function values). Unfortunately, full zeroth-order estimation suffers from extremely high variance and instability.

Introducing PZOBO: A Hybrid Approach

The authors propose PZOBO and its stochastic variant PZOBO-S to overcome these limitations.

The core innovation is a "hybrid" estimation strategy:

  1. Analytical Components: The parts of the hypergradient that are easy to compute (first-order derivatives) are calculated exactly using standard automatic differentiation.
  2. Zeroth-Order Jacobian Estimation: Instead of estimating the whole gradient, PZOBO estimates only the response Jacobian. It does this by running two separate inner-optimization paths: one starting from the current point $x$ and another from a slightly perturbed point $x + \mu u$. By taking the difference between the outputs of these two paths, the algorithm obtains a high-quality estimate of the Jacobian without ever calculating a second derivative.

The paper provides a rigorous theoretical analysis, proving that PZOBO achieves a sublinear convergence rate for the outer loop and a linear (exponentially fast) convergence rate for the inner loop.

Key Insights

  • Partial Estimation is Key: The breakthrough realization is that zeroth-order methods are too noisy for the whole hypergradient, but surprisingly effective and stable when applied exclusively to the response Jacobian.
Comparison of outer loss convergence between partial and full zeroth-order estimation.
  • Trajectory-Based Estimation: Unlike vanilla zeroth-order methods that only look at function values, PZOBO evaluates the difference between optimization trajectories. This captures the "response" of the inner learner much more accurately.
  • Hessian-Free Scalability: Because it only requires first-order gradients, PZOBO can handle architectures (like ResNet-12) that cause standard bilevel optimizers to run out of memory or take an impractical amount of time.
  • Robustness to Inner Steps: Experiments show that PZOBO's performance remains stable regardless of the number of inner gradient descent steps ($N$), making it highly practical to deploy.

Experimental Results

The authors evaluated their algorithms across four distinct bilevel problems, including shallow/deep Hyper-Representation (HR), Few-shot Meta-learning (miniImageNet), and Hyperparameter Optimization (20 Newsgroup).

Highlights include: * Superior Speed in Meta-Learning: On the miniImageNet task with a ResNet-12 backbone, PZOBO reached 69% accuracy in less than 3 hours. In contrast, the baseline MetaOptNet failed to reach that accuracy even after 20 hours. * Higher Accuracy on Deep Models: In deep hyper-representation tasks on MNIST, PZOBO-S achieved an accuracy of 0.98+, while other stochastic bilevel methods (like AID-FP and AID-CG) saturated around 0.93. * Unmatched Efficiency: PZOBO vastly outperforms full zeroth-order methods (like HOZOG) and other baselines because exploiting the analytical structure of the gradient leads to much lower variance and faster convergence.

Outer loss versus running time, demonstrating PZOBO's efficiency compared to baseline methods.

Limitations and Future Work

While highly effective, the theoretical convergence proof assumes the inner objective is strongly convex. While this holds for some tasks (like the final layer of a classifier), many deep learning problems feature non-convex inner loops. Additionally, the method relies on sampling Gaussian vectors; while a single sample works well in current tests, extremely high-dimensional problems might eventually require more samples to maintain accuracy.

Future directions include extending this "partial zeroth-order" logic to other complex optimization structures, such as minimax problems or non-convex inner-level constraints.

Summary updated

Abstract

Bilevel optimization has arisen as a powerful tool in modern machine learning. However, due to the nested structure of bilevel optimization, even gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations, which can be costly and unscalable in practice. Recently, Hessian-free bilevel schemes have been proposed to resolve this issue, where the general idea is to use zeroth- or first-order methods to approximate the full hypergradient of the bilevel problem. However, we empirically observe that such approximation can lead to large variance and unstable training, but estimating only the response Jacobian matrix as a partial component of the hypergradient turns out to be extremely effective. To this end, we propose a new Hessian-free method, which adopts the zeroth-order-like method to approximate the response Jacobian matrix via taking difference between two optimization paths. Theoretically, we provide the convergence rate analysis for the proposed algorithms, where our key challenge is to characterize the approximation and smoothness properties of the trajectory-dependent estimator, which can be of independent interest. This is the first known convergence rate result for this type of Hessian-free bilevel algorithms. Experimentally, we demonstrate that the proposed algorithms outperform baseline bilevel optimizers on various bilevel problems. Particularly, in our experiment on few-shot meta-learning with ResNet-12 network over the miniImageNet dataset, we show that our algorithm outperforms baseline meta-learning algorithms, while other baseline bilevel optimizers do not solve such meta-learning problems within a comparable time frame.
BibTeX
@inproceedings{sow2022convergence,
  author = {Daouda Sow and Kaiyi Ji and Yingbin Liang},
  title = {{On the Convergence Theory for Hessian-Free Bilevel Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=ZSVtnbdMFr},
}
Figure