[edit]
Near-Optimal Convex Simple Bilevel Optimization with a Bisection Method
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:2008-2016, 2024.
Abstract
This paper studies a class of simple bilevel optimization problems where we minimize a composite convex function at the upper-level subject to a composite convex lower-level problem. Existing methods either provide asymptotic guarantees for the upper-level objective or attain slow sublinear convergence rates. We propose a bisection algorithm to find a solution that is ϵf-optimal for the upper-level objective and ϵg-optimal for the lower-level objective. In each iteration, the binary search narrows the interval by assessing inequality system feasibility. Under mild conditions, the total operation complexity of our method is O(max. Here, a unit operation can be a function evaluation, gradient evaluation, or the invocation of the proximal mapping, L_{f_1} and L_{g_1} are the Lipschitz constants of the upper- and lower-level objectives’ smooth components, and {\mathcal{O}} hides logarithmic terms. Our approach achieves a near-optimal rate in unconstrained smooth or composite convex optimization when disregarding logarithmic terms. Numerical experiments demonstrate the effectiveness of our method.