Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.00659 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Bilevel optimization has gained considerable attention due to its broad applicability across various fields. While several studies have investigated the convergence rates in the strongly-convex-strongly-convex (SC-SC) setting, no prior work has proven that a single-loop algorithm can achieve linear convergence. This paper employs a small-gain theorem in {robust control theory} to demonstrate that a single-loop algorithm based on the implicit function theorem attains a linear convergence rate of $\mathcal{O}(ρ^{k})$, where $ρ\in(0,1)$ is specified in Theorem 3. Specifically, We model the algorithm as a dynamical system by identifying its two interconnected components: the controller (the gradient or approximate gradient functions) and the plant (the update rule of variables). We prove that each component exhibits a bounded gain and that, with carefully designed step sizes, their cascade accommodates a product gain strictly less than one. Consequently, the overall algorithm can be proven to achieve a linear convergence rate, as guaranteed by the small-gain theorem. The gradient boundedness assumption adopted in the single-loop algorithm (\cite{hong2023two, chen2022single}) is replaced with a gradient Lipschitz assumption in Assumption 2.2. To the best of our knowledge, this work is first-known result on linear convergence for a single-loop algorithm.