199. Adaptive bilevel optimisation
Invited abstract in session FC-5: Recent advances in bilevel optimization III, stream Bilevel optimization: strategies for complex decision-making.
Friday, 11:25 - 12:40Room: M:N
Authors (first author is the speaker)
| 1. | Kimon Antonakopoulos
|
| EPFL | |
| 2. | Shoham Sabach
|
| Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology | |
| 3. | Luca Viano
|
| École Polytechnique Fédérale de Lausanne | |
| 4. | Mingyi Hong
|
| University of Minnesota | |
| 5. | Volkan Cevher
|
| School of Engineering, EPFL |
Abstract
We propose a new \textit{adaptive} optimization algorithm based on mirror descent for a class of possibly non-convex smooth bilevel optimization problems. The 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. As such, existing algorithms require knowledge of gradient Lipschitz constants of both inner and outer levels and are often challenging to tune in practice. Our adaptive algorithm, to our knowledge the first in this setting, circumvents this difficulty by using an AdaGrad-type accumulation strategy on gradient norms and obtains a convergence rate of in terms of the outer objective function, when it is convex, where is the number of iterations. When the outer objective is non-convex, our algorithm obtains an best-iterate guarantee for the squared norm of the gradient of the outer objective function. We also provide numerical evidence to support the theory in a reinforcement learning setting where all problem parameters are accessible.
Keywords
- Multilevel optimization
Status: accepted
Back to the list of papers