  Bilevel optimization has become a powerful tool in a wide variety of machine
learning problems. However, the current nonconvex bilevel optimization
considers an offline dataset and static functions, which may not work well in
emerging online applications with streaming data and time-varying functions. In
this work, we study online bilevel optimization (OBO) where the functions can
be time-varying and the agent continuously updates the decisions with online
streaming data. To deal with the function variations and the unavailability of
the true hypergradients in OBO, we propose a single-loop online bilevel
optimizer with window averaging (SOBOW), which updates the outer-level decision
based on a window average of the most recent hypergradient estimations stored
in the memory. Compared to existing algorithms, SOBOW is computationally
efficient and does not need to know previous functions. To handle the unique
technical difficulties rooted in single-loop update and function variations for
OBO, we develop a novel analytical technique that disentangles the complex
couplings between decision variables, and carefully controls the hypergradient
estimation error. We show that SOBOW can achieve a sublinear bilevel local
regret under mild conditions. Extensive experiments across multiple domains
corroborate the effectiveness of SOBOW.
