Fully First-Order Algorithms for Online Bilevel Optimization

Tingkai Jia, Cheng Chen · 2026

Read Fully First-Order Algorithms for Online Bilevel Optimization by Tingkai Jia, Cheng Chen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-11665.txt.

Description

Online bilevel optimization usually depends on hypergradient descent, which needs costly Hessian-vector products that can dominate computation. Tingkai Jia and one co-author remove that requirement entirely, reformulating the problem as a single-level online problem with inequality constraints and building a sequence of Lagrangian functions. The resulting algorithm uses only first-order information, yet still achieves regret bounds that grow slowly with time and with changes in the problem.

An improved variant with an adaptive inner-iteration scheme drops one dependence in the bound and reaches a cleaner logarithmic-plus-variation rate. The same first-order approach extends to the stochastic setting with a sublinear regret guarantee. Numerical experiments confirm the method works in practice and support the theory, offering a cheaper route to bilevel problems that arrive as a stream rather than a fixed batch.

Catalog record

CREATORTingkai Jia, Cheng Chen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-11665

Browse the full library · About the Tower of Babel