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.
Introduction
Bilevel optimization represents a hierarchical structure where one optimization problem (the outer loop) contains another (the inner loop) as a constraint. This framework is essential for modern machine learning tasks such as meta-learning, hyperparameter optimization, and neural architecture search. However, the computational burden is significant: updating the outer variables requires the "hypergradient," which necessitates calculating how the inner loop's optimal solution responds to changes in the outer loop. Traditionally, this involves expensive second-order derivatives like Jacobian-vector or Hessian-vector products, which struggle to scale with the millions of parameters in deep learning models.
The PZOBO Framework: A Surgical Approach to Approximation
To address these scalability issues, researchers have explored "Hessian-free" methods. While previous attempts tried to approximate the entire hypergradient using zeroth-order methods, these often suffered from high variance and instability.
The proposed PZOBO (Partial Zeroth-Order-like Bilevel Optimizer) introduces a more refined strategy. Instead of approximating the whole hypergradient, it decomposes the gradient into "easy" components (direct gradients) and the "hard" component—the response Jacobian. PZOBO applies a zeroth-order-like approximation only to this response Jacobian bottleneck.
As shown in the figure above, this partial estimation approach leads to significantly faster and more stable convergence compared to full hypergradient estimation. The algorithm achieves this by running two parallel inner optimization paths—one standard and one with a small random perturbation—and using the difference between their trajectories to estimate the Jacobian.
Theoretical Contributions
A major contribution of this work is the first rigorous convergence rate analysis for this specific class of Hessian-free bilevel algorithms. The authors prove that PZOBO achieves a sublinear convergence rate for the outer loop and a linear rate for the inner loop. The primary theoretical challenge involved characterizing the approximation and smoothness properties of an estimator that depends on the entire optimization trajectory, rather than just static function values.
Experimental Evaluation
The effectiveness of PZOBO and its stochastic variant, PZOBO-S, was validated across several benchmarks:
- Few-Shot Meta-Learning: On the miniImageNet dataset using a ResNet-12 backbone, PZOBO reached 69% test accuracy in just 2.8 hours. In contrast, the baseline MetaOptNet required over 20 hours to reach the same performance level.
- Deep Hyper-Representation: On the MNIST dataset with a LeNet architecture, PZOBO-S achieved over 98% accuracy, matching state-of-the-art one-phase methods while other bilevel baselines plateaued significantly lower.
- Hyperparameter Optimization: Using the 20 Newsgroup dataset, the method demonstrated superior scalability, solving high-dimensional problems where traditional optimizers like AID or ITD faced memory or time constraints.
Conclusion
PZOBO offers a "Goldilocks" solution for bilevel optimization: it is faster than exact second-order methods and more stable than full zeroth-order approximations. By focusing on the response Jacobian bottleneck and leveraging trajectory-based estimation, it enables bilevel optimization to scale to complex deep learning architectures. Future work will aim to relax the current requirement for strong convexity in the inner loop, extending these promising results to more general non-convex landscapes.
Summary updated