Non-Convex Bilevel Optimization with Time-Varying Objective Functions
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- An Improved Unconstrained Approach for Bilevel OptimizationSIAM Journal on Optimization, 2023
- A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-CriticSIAM Journal on Optimization, 2023
- Second-Order Online Nonconvex OptimizationIEEE Transactions on Automatic Control, 2020
- Introduction to Online Convex OptimizationFoundations and Trends® in Optimization, 2016
- Online Learning and Online Convex OptimizationFoundations and Trends in Machine Learning, 2012
- A penalty function method based on Kuhn–Tucker condition for solving linear bilevel programmingApplied Mathematics and Computation, 2007
- An extended Kuhn–Tucker approach for linear bilevel programmingApplied Mathematics and Computation, 2005
- New Branch-and-Bound Rules for Linear Bilevel ProgrammingSIAM Journal on Scientific and Statistical Computing, 1992
- Mathematical Programs with Optimization Problems in the ConstraintsOperations Research, 1973