Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods
Online optimization is a well-established optimization paradigm that aims to
make a sequence of correct decisions given knowledge of the correct answer to
previous decision tasks. Bilevel programming involves a hierarchical
optimization problem where the feasible region of the so-called outer problem
is restricted by the graph of the solution set mapping of the inner problem.
This paper brings these two ideas together and studies an online bilevel
optimization setting in which a sequence of time-varying bilevel problems are
revealed one after the other. We extend the known regret bounds for
single-level online algorithms to the bilevel setting. Specifically, we
introduce new notions of bilevel regret, develop an online alternating
time-averaged gradient method that is capable of leveraging smoothness, and
provide regret bounds in terms of the path-length of the inner and outer
minimizer sequences.