Projection-free methods for solving smooth convex bilevel optimisation problems

Abstract

When faced with multiple minima of an "inner-level" convex optimisation problem, the convex bilevel optimisation problem selects an optimal solution which also minimises an auxiliary "outer-level" convex objective of interest. Bilevel optimisation requires a different approach compared to single-level optimisation problems since the set of minimisers for the inner-level objective is not given explicitly. In this thesis, we propose new projection-free methods for convex bilevel optimisation which require only a linear optimisation oracle over the base domain. We provide convergence guarantees for both inner- and outer-level objectives that hold under our proposed projection-free methods. In particular, we highlight how our guarantees are affected by the presence or absence of an optimal dual solution. Lastly, we conduct numerical experiments that demonstrate the performance of the proposed methods.