Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911666052005888 |
|---|---|
| author | Jia, Tingkai Wang, Haiguang Chen, Cheng |
| author_facet | Jia, Tingkai Wang, Haiguang Chen, Cheng |
| contents | Online bilevel optimization (OBO) has emerged as a powerful framework for many machine learning problems. Prior works have developed several algorithms that minimize the standard bilevel local regret or the window-averaged bilevel local regret of the OBO problem, but the optimality of existing regret bounds remains unclear. In this work, we establish optimal regret bounds for both settings. For standard bilevel local regret, we propose an algorithm with adaptive iteration strategy that achieves the optimal regret $Ω(1+V_T)$ with at most $O(T\log T)$ total inner-level gradient evaluations. We further develop a fully single-loop algorithm whose regret bound includes an additional gradient-variation terms. For the window-averaged bilevel local regret, we design an algorithm that captures linear environmental variation through a novel window-based analysis and achieves the optimal regret $Ω(T/W^2)$. The algorithm also supports an efficient single-loop structure, achieving an $O(T/W)$ regret bound with $O(WT)$ total gradient evaluations. Experiments validate our theoretical findings and demonstrate the practical effectiveness of the proposed methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_06457 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization Jia, Tingkai Wang, Haiguang Chen, Cheng Machine Learning Optimization and Control Online bilevel optimization (OBO) has emerged as a powerful framework for many machine learning problems. Prior works have developed several algorithms that minimize the standard bilevel local regret or the window-averaged bilevel local regret of the OBO problem, but the optimality of existing regret bounds remains unclear. In this work, we establish optimal regret bounds for both settings. For standard bilevel local regret, we propose an algorithm with adaptive iteration strategy that achieves the optimal regret $Ω(1+V_T)$ with at most $O(T\log T)$ total inner-level gradient evaluations. We further develop a fully single-loop algorithm whose regret bound includes an additional gradient-variation terms. For the window-averaged bilevel local regret, we design an algorithm that captures linear environmental variation through a novel window-based analysis and achieves the optimal regret $Ω(T/W^2)$. The algorithm also supports an efficient single-loop structure, achieving an $O(T/W)$ regret bound with $O(WT)$ total gradient evaluations. Experiments validate our theoretical findings and demonstrate the practical effectiveness of the proposed methods. |
| title | Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2602.06457 |