AISTATS 2024poster13 citations
Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods
Davoud Ataee Tarzanagh, Parvin Nazari, Bojian Hou, Li Shen, Laura Balzano
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.
BibTeX
@InProceedings{pmlr-v238-ataee-tarzanagh24a,
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 = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics},
pages = {2854--2862},
year = {2024},
editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen},
volume = {238},
series = {Proceedings of Machine Learning Research},
month = {02--04 May},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v238/ataee-tarzanagh24a/ataee-tarzanagh24a.pdf},
url = {https://proceedings.mlr.press/v238/ataee-tarzanagh24a.html},
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.}
}