Fully First-Order Algorithms for Online Bilevel Optimization
This work addresses computational bottlenecks in online bilevel optimization for machine learning applications, offering incremental improvements over existing methods.
The paper tackles the computational cost of online bilevel optimization by eliminating the need for Hessian-vector products, proposing a fully first-order algorithm that achieves regret of O(1 + V_T + H_{2,T}) and an improved variant with O(√T + V_T) regret.
In this work, we study non-convex-strongly-convex online bilevel optimization (OBO). Existing OBO algorithms are mainly based on hypergradient descent, which requires access to a Hessian-vector product (HVP) oracle and potentially incurs high computational costs. By reformulating the original OBO problem as a single-level online problem with inequality constraints and constructing a sequence of Lagrangian function, we eliminate the need for HVPs arising from implicit differentiation. Specifically, we propose a fully first-order algorithm for OBO, and provide theoretical guarantees showing that it achieves regret of $O(1 + V_T + H_{2,T})$. Furthermore, we develop an improved variant with an adaptive inner-iteration scheme, which removes the dependence on the drift variation of the inner-level optimal solution and achieves regret of $O(\sqrt{T} + V_T)$. This regret have the advatange when $V_{T}\ge O(\sqrt{T})$.