{"ID":2846440,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.01126","arxiv_id":"2511.01126","title":"Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization","abstract":"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 \\textit{window-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.","short_abstract":"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 \\textit{window-smoothed} regret minimization, which may not accurately reflect system performance when f...","url_abs":"https://arxiv.org/abs/2511.01126","url_pdf":"https://arxiv.org/pdf/2511.01126v3","authors":"[\"Parvin Nazari\",\"Bojian Hou\",\"Davoud Ataee Tarzanagh\",\"Li Shen\",\"George Michailidis\"]","published":"2025-11-03T00:29:36Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"math.NA\",\"math.OC\",\"math.ST\"]","methods":"[]","has_code":false}