Accelerating diagonal methods for bilevel optimization: Unified convergence via continuous-time dynamics
摘要
We analyze fast diagonal methods for simple bilevel programs. Guided by the analysis of the corresponding continuous-time dynamics, under a mild general assumption we provide convergence rates for the inner residual and upper bounds for the outer residual along an ergodic sequence. As the key point of our work, under geometric assumptions for the inner function—namely, a weaker condition attributed to Attouch and Czarnecki and a stronger Hölderian error bound—we provide a unified convergence analysis, which yields explicit last-iterate convergence rates and guarantees weak convergence to a solution of the bilevel problem. In particular, we improve and extend recent results on accelerated schemes, offering novel insights into the trade-offs between geometry, regularization decay, and algorithmic design. Numerical experiments illustrate the advantages of more flexible methods and support our theoretical findings.