EUVIMEDEUVIMED entdecken
Crossref

Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions

Yuya Hikima, Akiko Takeda

Proceedings of the AAAI Conference on Artificial Intelligence · 11.04.2025 · 39 (16) · 17195-17203

DOI: 10.1609/aaai.v39i16.33890 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 11.04.2025. Verfasst von Yuya Hikima und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this study, we consider an optimization problem with uncertainty dependent on decision variables, which has recently attracted attention due to its importance in machine learning and pricing applications. In this problem, the gradient of the objective function cannot be obtained explicitly because the decision-dependent distribution is unknown. Therefore, several zeroth-order methods have been proposed, which obtain noisy objective values by sampling and update the iterates. Although these existing methods have theoretical convergence for optimization problems with decision-dependent uncertainty, they require strong assumptions about the function and distribution or exhibit large variances in their gradient estimators. To overcome these issues, we propose two zeroth-order methods under mild assumptions. First, we develop a zeroth-order method with a new one-point gradient estimator including a variance reduction parameter. The proposed method updates the decision variables while adjusting the variance reduction parameter. Second, we develop a zeroth-order method with a two-point gradient estimator. There are situations where only one-point estimators can be used, but if both one-point and two-point estimators are available, it is more practical to use the two-point estimator. As theoretical results, we show the convergence of our methods to stationary points and provide the worst-case iteration and sample complexity analysis. Our simulation experiments with real data on a retail service application show that our methods output solutions with lower objective values than the conventional zeroth-order methods.

Zitieren

APA

Hikima, Y., & Takeda, A. (2025). Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions. Proceedings of the AAAI Conference on Artificial Intelligence, 39(16), 17195-17203. https://doi.org/10.1609/aaai.v39i16.33890

Vancouver

Hikima Y, Takeda A. Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions. Proceedings of the AAAI Conference on Artificial Intelligence. 2025;39(16):17195-17203. doi:10.1609/aaai.v39i16.33890

BibTeX
@article{Hikima2025,
  author = {Hikima, Yuya and Takeda, Akiko},
  title = {Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2025},
  volume = {39},
  number = {16},
  pages = {17195--17203},
  doi = {10.1609/aaai.v39i16.33890}
}
Kostenlos starten →