# Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2025.

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

- [Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization](https://mlsanity.com/paper/2602.06457/) (2026)
- [Fully First-Order Algorithms for Online Bilevel Optimization](https://mlsanity.com/paper/2602.11665/) (2026)
- [IGT-OMD: Implicit Gradient Transport for Decision-Focused Learning under Delayed Feedback](https://mlsanity.com/paper/2605.12693/) (2026)
- [Beyond Post-Hoc Temperature Scaling: Bilevel Optimization for LLM Calibration](https://mlsanity.com/paper/2608.07419/) (2026)

## Abstract (arXiv)

Online bilevel optimization (OBO) is a powerful framework for machine learning problems where both outer and inner objectives evolve over time, requiring dynamic updates. Current OBO approaches rely on deterministic textitwindow-smoothed regret minimization, which may not accurately reflect system performance when functions change rapidly. In this work, we introduce a novel search direction and show that both first- and zeroth-order (ZO) stochastic OBO algorithms leveraging this direction achieve sublinear stochastic bilevel regret without window smoothing. Beyond these guarantees, our framework enhances efficiency by: (i) reducing oracle dependence in hypergradient estimation, (ii) updating inner and outer variables alongside the linear system solution, and (iii) employing ZO-based estimation of Hessians, Jacobians, and gradients. Experiments on online parametric loss tuning and black-box adversarial attacks validate our approach.