282. A unified Lyapunov analysis for first and second order methods attached to bilevel optimization
Invited abstract in session WC-2: Systematic and computer-aided analyses VI: Systematic approaches to the analyses of proximal and higher-order methods, stream Systematic and computer-aided analyses of optimization algorithms.
Wednesday, 14:00-16:00Room: B100/7011
Authors (first author is the speaker)
| 1. | David Alexander Hulett
|
| Faculty of Mathematics, University of Vienna | |
| 2. | Radu Ioan Bot
|
| Faculty of Mathematics, University of Vienna | |
| 3. | Enis Chenchene
|
| 4. | Robert Csetnek
|
| University of Vienna |
Abstract
In a real Hilbert space, we address a convex bilevel optimization problem, where both the inner and outer levels have a composite smooth+nonsmooth structure. We study two algorithms, which at each step execute a proximal gradient step on a dynamically regularized objective function: one without momentum, in the spirit of the Bi-SG algorithm introduced by Merchav and Sabach in 2023, and one with momentum, in the spirit of the FBi-PG algorithm introduced by Merchav, Sabach and Teboulle in 2024. Attached to these algorithms we formulate a family of Lyapunov energy functionals which satisfy a certain descent property, and which allow us, in a streamlined way, to show convergence rates statements which match or surpass those already present in the literature. When the inner function satisfies a Hölderian error bound, we achieve small o rates for the inner and outer functional values along the last iterate, which is a first for this class of problems; additionally, the iterates converge weakly to a solution of the bilevel problem. These algorithms can be seen as forward discretizations of their continuous-time counterparts, which are respectively a first- and a second-order differential equation. The simpler, continuous-time Lyapunov analysis provides a guide and suggests the inequalities which should be reached in the discrete-time case.
Keywords
- Multi-level optimization
Status: accepted
Back to the list of papers