Algorithms for Structured Simple Bilevel Problems

Abstract: Simple convex bilevel optimization problems, in which we seek to minimize an (outer) objective function over a feasible set, which itself is the set of minimizers of another (inner) function. Such problems can be found in the machine learning and signal processing applications. In this work, we address the case where both outer and inner functions are convex and composite. Our solution approach is based on the ITerative Approximation and Level-set EXpansion (ITALEX) method, suggested by Doron and Shtern (2022), which alternates between expanding the level-set of the outer function and approximately optimizing the inner function over this level-set. The original implementation of ITALEX assumes there exits an efficient closed form projection onto the level-set of the outer function. In our work, we remove this assumption and instead introduce the Level Constrained Proximal Gradient (LCPG) method as an alternative approximation oracle for ITALEX. As a result, we introduce a revised iteration complexity analysis of ITALEX and show convergence rates identical to those by ITALEX, up to a logarithmic factor: O(1/k) rate of convergence to the inner function, and O(1/sqrt(k)) to the outer function. We conduct numerical experiment to test our theoretical results, and to compare the performance of our algorithm to ITALEX and other existing methods.