EUVIMEDEUVIMED entdecken
Crossref

Stochastic Optimization with Decision-Dependent Distributions

Dmitriy Drusvyatskiy, Lin Xiao

Mathematics of Operations Research · 2023-05 · 48 (2) · 954-998

DOI: 10.1287/moor.2022.1287 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, 2023-05. Verfasst von Dmitriy Drusvyatskiy und 1 weiteren Autor:innen. Die Arbeit wurde bisher 39-mal zitiert (Crossref) und nennt 36 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Stochastic optimization problems often involve data distributions that change in reaction to the decision variables. This is the case, for example, when members of the population respond to a deployed classifier by manipulating their features so as to improve the likelihood of being positively labeled. Recent works on performative prediction identify an intriguing solution concept for such problems: find the decision that is optimal with respect to the static distribution that the decision induces. Continuing this line of work, we show that, in the strongly convex setting, typical stochastic algorithms—originally designed for static problems—can be applied directly for finding such equilibria with little loss in efficiency. The reason is simple to explain: the main consequence of the distributional shift is that it corrupts algorithms with a bias that decays linearly with the distance to the solution. Using this perspective, we obtain convergence guarantees for popular algorithms, such as stochastic gradient, clipped gradient, prox-point, and dual averaging methods, along with their accelerated and proximal variants. In realistic applications, deployment of a decision rule is often much more expensive than sampling. We show how to modify the aforementioned algorithms so as to maintain their sample efficiency when performing only logarithmically many deployments. Funding: This work was supported by the Division of Computing and Communication Foundations [Grant 1740551] and Division of Mathematical Sciences [Grant 1651851].

Zitieren

APA

Drusvyatskiy, D., & Xiao, L. (2023). Stochastic Optimization with Decision-Dependent Distributions. Mathematics of Operations Research, 48(2), 954-998. https://doi.org/10.1287/moor.2022.1287

Vancouver

Drusvyatskiy D, Xiao L. Stochastic Optimization with Decision-Dependent Distributions. Mathematics of Operations Research. 2023;48(2):954-998. doi:10.1287/moor.2022.1287

BibTeX
@article{Drusvyatskiy2023,
  author = {Drusvyatskiy, Dmitriy and Xiao, Lin},
  title = {Stochastic Optimization with Decision-Dependent Distributions},
  journal = {Mathematics of Operations Research},
  year = {2023},
  volume = {48},
  number = {2},
  pages = {954--998},
  doi = {10.1287/moor.2022.1287}
}
Kostenlos starten →