Adaptive Bilevel Optimization

We propose a new adaptive optimization algorithm based on mirror descent for a class of possibly non-convex smooth bilevel optimization problems. The bilevel optimization template is broadly applicable in machine learning as it features two coupled problems where the optimal solution set of an inner problem serves as a constraint set for the outer problem. Currently, available algorithms require knowledge of both inner and outer gradient Lipschitz constants, which are difficult to tune in practice. By using an “on the fly” accumulation strategy on gradient norms, our adaptive algorithm circumvents this difficulty, and to our knowledge, is the first adaptive algorithm for bilevel optimization. In the convex setting, we obtain a convergence rate of $\mathcal {O}(1/T)$ in terms of the outer objective function, where T is the number of iterations. For non-convex outer objective functions, our algorithm achieves a best-iterate guarantee of $\mathcal {O}(1/T)$ in terms of the squared norm of the gradient of the outer objective function. Additionally, we provide numerical evidence to support the theory in a reinforcement learning setting.