Research map / Bandits and online learning / Online convex optimization and games
Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SOGD and ZO-SOGD, single-loop simultaneous online gradient methods for stochastic online bilevel optimization that achieve sublinear bilevel local regret without window smoothing, with the zeroth-order variant using only function-value oracles.
Problem
Stochastic online bilevel optimization with nonconvex outer objectives and time-varying inner/outer functions; existing methods rely on window-smoothed regret and gradient/Hessian/Jacobian oracles and costly inner linear-system solvers.
Approach
A new momentum-type search direction with a correction term, used in a single-loop simultaneous update of inner variable y, auxiliary system variable v (projected onto a ball), and outer x, giving sublinear projected-gradient local regret without window smoothing; a ZO variant estimates gradients, Hessian-vector and Jacobian-vector products by finite differences of function values.
Key results
- Theoretical bound BL-Reg_T = O(T^{1/3}(sigma^2+Delta_T)+T^{2/3}Psi_T) for SOGD without window smoothing; ZO-SOGD bound O((d1+d2)^{3/4}T^{1/3}(sigma_hat^2+Delta_hat_T)+(d1+d2)^{3/2}T^{2/3}Psi_hat_T).
- On online parametric loss tuning (MNIST, imbalanced to balanced shift), SOGD is the fastest method per the paper and achieves competitive accuracy versus OAGD and SOBOW.
- On online black-box adversarial attacks on MNIST, ZO-SOGD (Adam) surpasses ZO-O-Adam and all baselines in accuracy under perturbation, while ZO-SOGD has slower runtime than single-level baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SOGD's proposed search direction without window smoothing | Stochastic OBO · Stochastic OBO | bilevel local regret: T^{-2/3}\sigma^2 ... improving over the T^{-1/2}\sigma^2 bound | Helped |
| Use ZO-SOGD with function-value feedback | Stochastic zeroth-order OBO · Stochastic zeroth-order OBO | bilevel local regret | Helped |
| Use ZO-SOGD instead of ZO-O-GD or ZO-O-ConservSGD | Online black-box adversarial attacks · MNIST | test accuracy on perturbed samples | Helped |
| Use ZO-SOGD (Adam) instead of ZO-O-Adam and other baselines | Online black-box adversarial attacks · MNIST | test accuracy on perturbed samples | Helped |
| Add outer-level optimization on x using ZO-SOGD | Online black-box adversarial attacks · MNIST | runtime | Hurt |
| Use simultaneous updates instead of the compared solver approaches | Parametric loss tuning · MNIST | runtime | Helped |
| Use SOGD for parametric loss tuning | Parametric loss tuning · MNIST | test accuracy | Mixed |
| Use SOGD instead of SOBOW's conjugate-gradient solver | Parametric loss tuning · MNIST | runtime | Helped |
Surprising findings
- Window-smoothed regret may misrepresent regret behavior when functions change rapidly, so smoothing-free projected-gradient regret is used instead.
Limitations
- Results cover only nonconvex regret bounds; no guarantees for convex settings.
- Sublinear guarantees require regularity measures (path length, function variation) to be sublinear in specified rates.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: regret bound test accuracy balanced accuracy runtime infinity norm of perturbation
Baselines: OAGD SOBOW OGD ZO-O-GD ZO-O-Adam ZO-O-SignSGD ZO-O-ConservSGD
Builds on: OAGD SOBOW online gradient descent window-smoothed local regret
Closest papers by meaning
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.87)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.87)
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (NeurIPS 2024 · similarity 0.86)
- On The Complexity of First-Order Methods in Stochastic Bilevel Optimization (ICML 2024 · similarity 0.86)
- On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation (ICLR 2024 · similarity 0.86)
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.