Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2412.00659 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915042404859904 |
|---|---|
| author | Li, Jianhui Pu, Shi Chen, Jianqi Wu, Junfeng |
| author_facet | Li, Jianhui Pu, Shi Chen, Jianqi Wu, Junfeng |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00659 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linear Convergence Analysis of Single-loop Algorithm for Bilevel Optimization via Small-gain Theorem Li, Jianhui Pu, Shi Chen, Jianqi Wu, Junfeng Optimization and Control 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. |
| title | Linear Convergence Analysis of Single-loop Algorithm for Bilevel Optimization via Small-gain Theorem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.00659 |