Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916026722025472 |
|---|---|
| author | Nazari, Parvin Hou, Bojian Tarzanagh, Davoud Ataee Shen, Li Michailidis, George |
| author_facet | Nazari, Parvin Hou, Bojian Tarzanagh, Davoud Ataee Shen, Li Michailidis, George |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_01126 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization Nazari, Parvin Hou, Bojian Tarzanagh, Davoud Ataee Shen, Li Michailidis, George Machine Learning Numerical Analysis Optimization and Control Statistics Theory 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. |
| title | Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization |
| topic | Machine Learning Numerical Analysis Optimization and Control Statistics Theory |
| url | https://arxiv.org/abs/2511.01126 |