Dynamic FISTA for Convex Composite Bilevel Optimization

In this paper, we study convex bilevel optimization problems where both the inner and outer levels are given as a composite convex minimization. We propose the Fast Bilevel Proximal Gradient (FBi-PG) algorithm, which can be interpreted as applying FISTA to a dynamic regularized composite objective function. The dynamic nature of the regularization parameters allows one to achieve an optimal fast convergence rate of [Formula: see text] in terms of the inner objective function. This is the fastest known convergence rate under no additional restrictive assumptions. We also show that FBi-PG achieves sublinear simultaneous rates in terms of both the inner and outer objective functions. Moreover, we show that under a Hölderian type error bound assumption on the inner objective function, the FBi-PG algorithm achieves improved simultaneous rates and converges to an optimal solution of the bilevel optimization problem. Finally, we present numerical experiments demonstrating the performance of the proposed scheme.