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 is increasingly central to modern machine learning, powering applications from meta-learning to neural architecture search. It involves an "outer" optimization problem nested with an "inner" one: $$\min_{x} \Phi(x) := f(x, y^*(x)), \quad \text{s.t. } y^*(x) = \arg \min_{y} g(x, y)$$ The primary bottleneck is computing the hypergradient $\nabla \Phi(x)$, which requires the response Jacobian—the derivative of the inner solution $y^*$ with respect to the outer variable $x$. Standard approaches rely on second-order derivatives (Hessians), which scale poorly with model size. While "Hessian-free" zeroth-order methods exist, they often suffer from high variance when estimating the entire hypergradient.
The PZOBO Framework
Researchers from The Ohio State University and the University of Michigan propose the Partial Zeroth-Order-like Bilevel Optimizer (PZOBO). The core insight is that while full zeroth-order estimation is unstable, using it specifically for the response Jacobian while maintaining analytical first-order gradients for other terms is highly effective.
PZOBO estimates the response Jacobian by comparing two parallel inner optimization trajectories: one starting at $x$ and another at a perturbed point $x + \mu u$. This "trajectory-based" estimation captures inner-solver dynamics more accurately than point-wise differences. The authors also introduced PZOBO-S, a stochastic variant for large-scale datasets.
Theoretical Contributions
This work provides the first formal convergence guarantees for this class of trajectory-dependent Hessian-free algorithms. The analysis overcomes the challenge of compounding errors along the optimization path, establishing a sublinear convergence rate by characterizing the bias and variance of the estimator.
Experimental Results
The effectiveness of PZOBO 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. Baseline methods like MetaOptNet failed to reach this performance even after 20 hours.
- Deep Hyper-Representation: In MNIST classification with a LeNet backbone, PZOBO-S achieved over 98% accuracy, significantly outperforming other bilevel baselines which saturated at lower levels.
- Hyperparameter Optimization: PZOBO demonstrated superior stability and lower variance compared to full-gradient approximation methods like HOZOG.
Conclusion
PZOBO bridges the gap between the scalability of Hessian-free methods and the stability of gradient-based optimization. By focusing zeroth-order estimation on the Jacobian "bottleneck," it enables efficient bilevel optimization for high-dimensional models like ResNets. Future work may extend these "partial" estimation strategies to non-convex inner problems and other complex structures like minimax optimization.
Summary updated