Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-Start
Riccardo Grazzi, Massimiliano Pontil, Saverio Salzo; 24(167):1−37, 2023.
Abstract
This study examines a broad range of bilevel problems, where the upper-level problem focuses on minimizing a smooth objective function and the lower-level problem involves finding the fixed point of a smooth contraction map. These problems encompass meta-learning, equilibrium models, hyperparameter optimization, and data poisoning adversarial attacks. Recent works have proposed algorithms that utilize warm-start, where the previous lower-level approximate solution is used as a starting point for the lower-level solver. This warm-start approach enhances sample complexity in both stochastic and deterministic settings, achieving near-optimal sample complexity in some cases. However, there are situations, such as meta learning and equilibrium models, where the warm-start procedure is unsuitable or ineffective. This paper demonstrates that even without warm-start, it is still possible to achieve near-optimal sample complexity. The authors propose a simple method that employs stochastic fixed point iterations at the lower-level and projected inexact gradient descent at the upper-level. This method achieves an ε-stationary point using O(ε^{-2}) and ~O(ε^{-1}) samples for the stochastic and deterministic settings, respectively. Additionally, compared to methods using warm-start, this approach offers a simpler analysis that does not require studying the interactions between the upper-level and lower-level iterates.
[abs]