Glocal Hypergradient Estimation with Koopman Operator

Ryuichiro Hataya, Yoshinobu Kawahara

Introduction

In deep learning, hyperparameter optimization (HPO) is typically framed as a bi-level optimization problem. The "outer level" seeks the optimal hyperparameters (e.g., learning rates, weight decay), while the "inner level" involves training the model parameters given those hyperparameters. Efficiently estimating the gradient of the outer objective with respect to hyperparameters—the hypergradient—is critical for scaling HPO to complex models.

The Challenge: Efficiency vs. Accuracy

Current gradient-based HPO methods generally fall into two categories:

  1. Global Hypergradients: These methods compute gradients by backpropagating through the entire training trajectory. While accurate, they are computationally expensive, requiring $O(ST)$ time (where $S$ is the number of hyperparameter updates and $T$ is total training steps).
  2. Local Hypergradients: These methods update hyperparameters frequently during training (e.g., every $\tau$ steps). While efficient ($O(T)$), they suffer from "short-horizon bias," where greedy local updates lead to poor long-term performance.

Methodology: The Glocal Approach

Hataya and Kawahara propose Glocal Hypergradient Estimation, a method that combines the efficiency of local updates with the long-term perspective of global gradients. The core idea is to treat the sequence of local hypergradients as a nonlinear dynamical system.

Overview of glocal hypergradient estimation, illustrating the relationship between local trajectories and the estimated global gradient.

By applying Koopman Operator Theory, the authors linearize the dynamics of these hypergradients. Specifically, they use Dynamic Mode Decomposition (DMD) to approximate the Koopman operator from a short trajectory of local gradients. This allows the algorithm to predict the "steady state" or global hypergradient ($\hat{h}_\infty$) without completing the full training run.

Complexity and Performance

The "glocal" method maintains the computational efficiency of local methods while achieving the accuracy of global ones. As shown in the complexity table below, the glocal approach matches the time complexity of local methods while introducing only a minor increase in space complexity proportional to the trajectory length $\tau$.

Comparison of time and space complexity for Global, Local, and Glocal hypergradient estimation methods.

Experimental Results

The method was evaluated on standard benchmarks including MNIST, Fashion-MNIST, and CIFAR-10/100.

  • Speed: On a LeNet architecture, the Glocal method achieved a ~50x speedup over the Global baseline (58.3s vs. 2891.2s), performing nearly as fast as the Local method (58.2s).
  • Accuracy: In data reweighting tasks on imbalanced CIFAR-10, the Glocal method significantly outperformed the Local baseline (0.715 vs. 0.520 test accuracy), demonstrating its ability to overcome short-horizon bias.

Key Insights

  • Optimization as Dynamics: Viewing the optimization process as a dynamical system allows for the application of powerful system identification tools like DMD.
  • Scalability: Since DMD relies on SVD on small matrices (determined by the number of hyperparameters), the overhead is negligible for most deep learning tasks.
  • Stability: By aiming for a predicted long-term equilibrium, the glocal approach avoids the aggressive, often unstable updates characteristic of purely local methods.

Conclusion and Future Work

Glocal Hypergradient Estimation provides a robust "middle way" for bi-level optimization. While highly effective, the method currently assumes a degree of predictability in the meta-objective trajectory. Future research may explore the use of the Perron-Frobenius operator to better account for the stochasticity inherent in small-batch SGD and adversarial training environments.

Summary updated

Abstract

Gradient-based hyperparameter optimization methods update hyperparameters using hypergradients, gradients of a meta criterion with respect to hyperparameters. Previous research used two distinct update strategies: optimizing hyperparameters using global hypergradients obtained after completing model training or local hypergradients derived after every few model updates. While global hypergradients offer reliability, their computational cost is significant; conversely, local hypergradients provide speed but are often suboptimal. In this paper, we propose *glocal* hypergradient estimation, blending "global" quality with "local" efficiency. To this end, we use the Koopman operator theory to linearize the dynamics of hypergradients so that the global hypergradients can be efficiently approximated only by using a trajectory of local hypergradients. Consequently, we can optimize hyperparameters greedily using estimated global hypergradients, achieving both reliability and efficiency simultaneously. Through numerical experiments of hyperparameter optimization, including optimization of optimizers, we demonstrate the effectiveness of the glocal hypergradient estimation.
BibTeX
@misc{hataya2024glocal,
  author = {Ryuichiro Hataya and Yoshinobu Kawahara},
  title = {{Glocal Hypergradient Estimation with Koopman Operator}},
  year = {2024},
  eprint = {2402.02741},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.02741},
}
Figure