Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization

Tingkai Jia, Haiguang Wang, Cheng Chen

arXivarxiv/2602.06457Feb 6, 2026cs.LGscore 0

Online bilevel optimization (OBO) has emerged as a powerful framework for many machine learning problems. Prior works have developed several algorithms that minimize the standard bilevel local regret or the window-averaged bilevel local regret of the OBO problem, but the optimality of existing regret bounds remains unclear. In this work, we establish optimal regret bounds for both settings. For standard bilevel local regret, we propose an algorithm with adaptive iteration strategy that achieves the optimal regret $Ω(1+V_T)$ with at most $O(T\log T)$ total inner-level gradient evaluations. We…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.06457
curl -X POST /api/v1/records/arxiv/2602.06457/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.06457/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'