A Gradient Method for Multilevel Optimization
This work addresses the difficulty of multilevel optimization in machine learning, offering a novel algorithm with theoretical guarantees, though it is incremental as it builds on prior bilevel methods.
The authors tackled the problem of multilevel optimization by developing a gradient-based algorithm for n-level problems, proving asymptotic convergence to the original problem. Numerical experiments showed that a trilevel hyperparameter learning model produced more stable prediction results than an existing bilevel model in noisy data settings.
Although application examples of multilevel optimization have already been discussed since the 1990s, the development of solution methods was almost limited to bilevel cases due to the difficulty of the problem. In recent years, in machine learning, Franceschi et al. have proposed a method for solving bilevel optimization problems by replacing their lower-level problems with the $T$ steepest descent update equations with some prechosen iteration number $T$. In this paper, we have developed a gradient-based algorithm for multilevel optimization with $n$ levels based on their idea and proved that our reformulation asymptotically converges to the original multilevel problem. As far as we know, this is one of the first algorithms with some theoretical guarantee for multilevel optimization. Numerical experiments show that a trilevel hyperparameter learning model considering data poisoning produces more stable prediction results than an existing bilevel hyperparameter learning model in noisy data settings.