Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods
Abstract
This paper introduces \textit{online bilevel optimization} in which a sequence of time-varying bilevel problems is revealed one after the other. We extend the known regret bounds for single-level online algorithms to the bilevel setting. Specifically, we provide new notions of \textit{bilevel regret}, develop an online alternating time-averaged gradient method that is capable of leveraging smoothness, and give regret bounds in terms of the path-length of the inner and outer minimizer sequences.
Cite
Text
Ataee Tarzanagh et al. "Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods." Artificial Intelligence and Statistics, 2024.Markdown
[Ataee Tarzanagh et al. "Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods." Artificial Intelligence and Statistics, 2024.](https://mlanthology.org/aistats/2024/ataeetarzanagh2024aistats-online/)BibTeX
@inproceedings{ataeetarzanagh2024aistats-online,
title = {{Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods}},
author = {Ataee Tarzanagh, Davoud and Nazari, Parvin and Hou, Bojian and Shen, Li and Balzano, Laura},
booktitle = {Artificial Intelligence and Statistics},
year = {2024},
pages = {2854-2862},
volume = {238},
url = {https://mlanthology.org/aistats/2024/ataeetarzanagh2024aistats-online/}
}