Fully First-Order Algorithms for Online Bilevel Optimization

In this work, we study nonconvex-strongly convex online bilevel optimization (OBO) using only first-order oracle. 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 + VT + H2,T) with a total of O(Tlog T) iterations, where VT measures the variation in function values and H2,T characterizes the drift variation of the inner-level optimal solution. We also establish a sublinear regret bound under the single-loop structure by introducing additional gradient-variation terms. Furthermore, we develop an improved variant with an adaptive inner-iteration scheme, which removes the dependence on H2,T and achieves regret of O(log T + VT). Finally, under the stochastic OBO setting, we establish the regret bound for the fully first-order algorithm, i.e., O(T2/3(1 + σ2) + VT + H2,T). Numerical experiments demonstrate the feasibility of our algorithm and support our theoretical findings.