A stochastic gradient method for trilevel optimization
This work addresses the need for efficient and theoretically sound methods in trilevel optimization, which is important for advancing machine learning formulations in this context, though it is incremental as it extends bilevel optimization techniques to a more complex setting.
The authors tackled the problem of solving trilevel optimization problems by proposing the first stochastic gradient descent method for unconstrained trilevel optimization, with a convergence theory covering various forms of inexactness, and demonstrated its effectiveness through numerical results on synthetic problems and hyperparameter adversarial tuning.
With the success that the field of bilevel optimization has seen in recent years, similar methodologies have started being applied to solving more difficult applications that arise in trilevel optimization. At the helm of these applications are new machine learning formulations that have been proposed in the trilevel context and, as a result, efficient and theoretically sound stochastic methods are required. In this work, we propose the first-ever stochastic gradient descent method for solving unconstrained trilevel optimization problems and provide a convergence theory that covers all forms of inexactness of the trilevel adjoint gradient, such as the inexact solutions of the middle-level and lower-level problems, inexact computation of the trilevel adjoint formula, and noisy estimates of the gradients, Hessians, Jacobians, and tensors of third-order derivatives involved. We also demonstrate the promise of our approach by providing numerical results on both synthetic trilevel problems and trilevel formulations for hyperparameter adversarial tuning.