Natural Hypergradient Descent: Algorithm Design, Convergence Analysis, and Parallel Implementation

In this work, we propose Natural Hypergradient Descent (NHGD), a new method for solving bilevel optimization problems. To address the computational bottleneck in hypergradient estimation, namely the need to compute or approximate Hessian inverses, we exploit the statistical structure of the inner optimization problem and use the empirical Fisher information matrix as an asymptotically consistent surrogate for the Hessian. This design enables a parallel optimize-and-approximate framework in which the Hessian-inverse approximation is updated synchronously with the stochastic inner optimization, reusing gradient information at negligible additional cost. Our main theoretical contribution establishes high-probability error bounds and sample complexity guarantees for NHGD that match those of state-of-the-art optimize-then-approximate methods, while significantly reducing computational time overhead. Empirical evaluations on representative bilevel learning tasks further demonstrate the practical advantages of NHGD, highlighting its scalability and effectiveness in large-scale machine learning settings.

Many machine learning systems involve a "problem within a problem": tuning a high-level goal requires repeatedly solving a separate, lower-level training task underneath it. This nested setup is called bilevel optimization, and it appears in tasks like automatic hyperparameter tuning, data-cleaning and meta-learning. However, connecting the two levels usually requires a costly mathematical step, for example, inverting a large matrix that captures how the lower problem curves. This step becomes a major computational bottleneck at scale. In this work, we introduce Natural Hypergradient Descent, a method that sidesteps this problem. Instead of directly inverting the matrix, we exploit the statistical structure already present in the training problem to build a cheap and reliable surrogate. This surrogate is updated alongside the standard training process by reusing information that is already computed. We prove that our method is just as accurate and data-efficient as existing approaches, while improving computational efficiency. Experiments on standard tasks confirm these gains.