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
| CREATOR | Tingkai Jia, Cheng Chen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-11665