Zeroth-order gradient estimators for stochastic problems with decision-dependent distributions
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_ | 1866914121271738368 |
|---|---|
| author | Hikima, Yuya Takeda, Akiko |
| author_facet | Hikima, Yuya Takeda, Akiko |
| contents | Stochastic optimization problems with unknown decision-dependent distributions have attracted increasing attention in recent years due to its importance in applications. Since the gradient of the objective function is inaccessible as a result of the unknown distribution, various zeroth-order methods have been developed to solve the problem. However, it remains unclear which search direction to construct a gradient estimator is more appropriate and how to set the algorithmic parameters. In this paper, we conduct a unified sample complexity analysis of zeroth-order methods across gradient estimators with different search directions. As a result, we show that gradient estimators that average over multiple directions, either uniformly from the unit sphere or from a Gaussian distribution, achieve the lowest sample complexity. The attained sample complexities improve those of existing zeroth-order methods in the problem setting that allows nonconvexity and unboundedness of the objective function. Moreover, by simulation experiments on multiple products pricing and strategic classification applications, we show practical performance of zeroth-order methods with various gradient estimators. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24929 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Zeroth-order gradient estimators for stochastic problems with decision-dependent distributions Hikima, Yuya Takeda, Akiko Optimization and Control 90C15, 90C30, 65K05 G.1.6; G.3 Stochastic optimization problems with unknown decision-dependent distributions have attracted increasing attention in recent years due to its importance in applications. Since the gradient of the objective function is inaccessible as a result of the unknown distribution, various zeroth-order methods have been developed to solve the problem. However, it remains unclear which search direction to construct a gradient estimator is more appropriate and how to set the algorithmic parameters. In this paper, we conduct a unified sample complexity analysis of zeroth-order methods across gradient estimators with different search directions. As a result, we show that gradient estimators that average over multiple directions, either uniformly from the unit sphere or from a Gaussian distribution, achieve the lowest sample complexity. The attained sample complexities improve those of existing zeroth-order methods in the problem setting that allows nonconvexity and unboundedness of the objective function. Moreover, by simulation experiments on multiple products pricing and strategic classification applications, we show practical performance of zeroth-order methods with various gradient estimators. |
| title | Zeroth-order gradient estimators for stochastic problems with decision-dependent distributions |
| topic | Optimization and Control 90C15, 90C30, 65K05 G.1.6; G.3 |
| url | https://arxiv.org/abs/2510.24929 |