On iteratively regularized first-order methods for simple bilevel optimization

Abstract

We consider simple bilevel optimization (SBO) problems where the goal is to compute among the optimal solutions of a composite convex optimization problem, one that minimizes a secondary objective function. Our main contribution is threefold. (i) When the upper-level objective is composite and strongly convex, we propose IR-ISTAs, an iteratively regularized proximal gradient method with a prescribed update rule for the regularization parameter. We establish asymptotic convergence of the iterates to the unique optimal solution and simultaneous sublinear rates for suitably defined infeasibility and suboptimality error metrics. (ii) For the same setting, we propose IR-VFISTAs, an iteratively regularized accelerated proximal gradient method, establish its asymptotic convergence, and, under weak sharp minimality, derive faster simultaneous rates than IR-ISTAs. These appear to be the best-known convergence rate guarantees for SBO problems with a strongly convex upper-level objective and improve upon the rates previously established for methods requiring convexity of both levels. (iii) When the upper-level objective is smooth and nonconvex, we propose IPR-VFISTAnc, an inexactly projected iteratively regularized accelerated gradient method, and establish both asymptotic and nonasymptotic convergence guarantees. To the best of our knowledge, this is the first asymptotic stationarity result for this class of SBO problems that does not rely on the weak sharp minimality of the lower-level problem. Moreover, the total iteration complexity of IPR-VFISTAnc matches that of existing methods, while providing a sharper lower-level infeasibility guarantee. We present preliminary numerical experiments on three ill-posed linear inverse problems and an optimal classifier-selection problem.