Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling
This work addresses a bottleneck in bilevel optimization for researchers and practitioners by providing a more efficient algorithm, though it is incremental as it builds on existing stochastic gradient methods.
The paper tackles the computational inefficiency of bilevel optimization algorithms due to independent sampling by introducing a without-replacement sampling algorithm, achieving a faster convergence rate as validated by numerical results on synthetic and real-world applications.
Bilevel Optimization has experienced significant advancements recently with the introduction of new efficient algorithms. Mirroring the success in single-level optimization, stochastic gradient-based algorithms are widely used in bilevel optimization. However, a common limitation in these algorithms is the presumption of independent sampling, which can lead to increased computational costs due to the complicated hyper-gradient formulation of bilevel problems. To address this challenge, we study the example-selection strategy for bilevel optimization in this work. More specifically, we introduce a without-replacement sampling based algorithm which achieves a faster convergence rate compared to its counterparts that rely on independent sampling. Beyond the standard bilevel optimization formulation, we extend our discussion to conditional bilevel optimization and also two special cases: minimax and compositional optimization. Finally, we validate our algorithms over both synthetic and real-world applications. Numerical results clearly showcase the superiority of our algorithms.