Optimal Zeroth-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_ | 1866918154401218560 |
|---|---|
| author | Aghasi, Alireza Kwon, Jeongyeol Ghadimi, Saeed |
| author_facet | Aghasi, Alireza Kwon, Jeongyeol Ghadimi, Saeed |
| contents | In this paper, we develop zeroth-order algorithms with provably (nearly) optimal sample complexity for stochastic bilevel optimization, where only noisy function evaluations are available. We propose two distinct algorithms: the first is inspired by Jacobian/Hessian-based approaches, and the second builds on using a penalty function reformulation. The Jacobian/Hessian-based method achieves a sample complexity of $\mathcal{O}(d^3/ε^2)$, which is optimal in terms of accuracy $ε$, albeit with polynomial dependence on the problem dimension $d$. In contrast, the penalty-based method sharpens this guarantee to $\mathcal{O}(d/ε^2)$, optimally reducing the dimension dependence to linear while preserving optimal accuracy scaling. Our analysis is built upon Gaussian smoothing techniques, and we rigorously establish their validity under the stochastic bilevel settings considered in the existing literature. To the best of our knowledge, this is the first work to provide provably optimal sample complexity guarantees for a zeroth-order stochastic approximation method in bilevel optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_03646 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Zeroth-Order Bilevel Optimization Aghasi, Alireza Kwon, Jeongyeol Ghadimi, Saeed Optimization and Control In this paper, we develop zeroth-order algorithms with provably (nearly) optimal sample complexity for stochastic bilevel optimization, where only noisy function evaluations are available. We propose two distinct algorithms: the first is inspired by Jacobian/Hessian-based approaches, and the second builds on using a penalty function reformulation. The Jacobian/Hessian-based method achieves a sample complexity of $\mathcal{O}(d^3/ε^2)$, which is optimal in terms of accuracy $ε$, albeit with polynomial dependence on the problem dimension $d$. In contrast, the penalty-based method sharpens this guarantee to $\mathcal{O}(d/ε^2)$, optimally reducing the dimension dependence to linear while preserving optimal accuracy scaling. Our analysis is built upon Gaussian smoothing techniques, and we rigorously establish their validity under the stochastic bilevel settings considered in the existing literature. To the best of our knowledge, this is the first work to provide provably optimal sample complexity guarantees for a zeroth-order stochastic approximation method in bilevel optimization. |
| title | Optimal Zeroth-Order Bilevel Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.03646 |