Fully First-Order Algorithms for Online Bilevel Optimization

arXiv:2602.11665v2 Announce Type: replace Abstract: 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 + V_T + H_{2,T}) with a total of O(Tlog T) iterations, where V_T measures the variation in function values and H_{2,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 H_{2,T} and achieves regret of O(log T + V_T). Finally, under the stochastic OBO setting, we establish the regret bound for the fully first-order algorithm, i.e., O(T^{2/3}(1 + sigma^2) + V_T + H_{2,T}). Numerical experiments demonstrate the feasibility of our algorithm and support our theoretical findings.

Source: arXiv cs.LG | 2026-05-12