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

arXiv: https://arxiv.org/abs/2602.06457 · HTML: https://mlsanity.com/paper/2602.06457/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 33 references that are in the map.
- First posted on arXiv 6 Feb 2026.

## Builds on (most cited first, 23 of 23)

- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization](https://mlsanity.com/paper/1607.05447/) (2016)
- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [Multimodal Model-Agnostic Meta-Learning via Task-Aware Modulation](https://mlsanity.com/paper/1910.13616/) (2019)
- [A Fully First-Order Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2301.10945/) (2023)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [AutoBalance: Optimized Loss Functions for Imbalanced Data](https://mlsanity.com/paper/2201.01212/) (2022)
- [On the Convergence Theory for Hessian-Free Bilevel Algorithms](https://mlsanity.com/paper/2110.07004/) (2021)
- [Efficient Regret Minimization in Non-Convex Games](https://mlsanity.com/paper/1708.00075/) (2017)
- [Enhanced Bilevel Optimization via Bregman Distance](https://mlsanity.com/paper/2107.12301/) (2021)
- [Dynamic Local Regret for Non-convex Online Forecasting](https://mlsanity.com/paper/1910.07927/) (2019)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [A first-order augmented Lagrangian method for constrained minimax optimization](https://mlsanity.com/paper/2301.02060/) (2023)
- [Non-Convex Bilevel Optimization with Time-Varying Objective Functions](https://mlsanity.com/paper/2308.03811/) (2023)
- [Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization](https://mlsanity.com/paper/2511.01126/) (2025)
- [Non-Stationary Functional Bilevel Optimization](https://mlsanity.com/paper/2601.15363/) (2026)

## Built on by (most cited first, 1 of 1)

- [Fully First-Order Algorithms for Online Bilevel Optimization](https://mlsanity.com/paper/2602.11665/) (2026)

## Abstract (arXiv)

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 Omega(1+VT) with at most O(Tlog T) total inner-level gradient evaluations. We further develop a fully single-loop algorithm whose regret bound includes an additional gradient-variation terms. For the window-averaged bilevel local regret, we design an algorithm that captures linear environmental variation through a novel window-based analysis and achieves the optimal regret Omega(T/W2). The algorithm also supports an efficient single-loop structure, achieving an O(T/W) regret bound with O(WT) total gradient evaluations. Experiments validate our theoretical findings and demonstrate the practical effectiveness of the proposed methods.