Treffer: Technical Note—Improved Sample-Complexity Bounds in Stochastic Optimization.

Faster Methods to Handle Optimization Problems That Display Uncertainty In the paper "Improved Sample-Complexity Bounds in Stochastic Optimization," the authors Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu consider a classic approach to modeling uncertainty in optimization problems—stochastic optimization. A general way to model such uncertainty is to assume access to a probability distribution from which the different possible scenarios of an optimization problem can be sampled; a powerful way to work with such access is to sample explicit scenarios a fixed number of times and to then "average over" all these explicit deterministic scenarios. The key question then becomes as follows. How many such scenarios should be sampled? By a careful analysis, this work shows that the number of samples needed is much less than known before, thus speeding up several algorithms for stochastic-optimization problems. Real-world network-optimization problems often involve uncertain parameters during the optimization phase. Stochastic optimization is a key approach introduced in the 1950s to address such uncertainty. This paper presents improved upper bounds on the number of samples required for the sample-average approximation method in stochastic optimization. It enhances the sample complexity of existing approaches in this setting, providing faster approximation algorithms for any method that employs this framework. This work is particularly relevant for solving problems like the stochastic Steiner tree problem. Funding: The research of A. Baveja is partially supported by the United States Department of Transportation (via the University Transportation Research Center Program) [Grant 49198-25-26] and the British Council [the UKIERI Research Program]. The work of A. Chavan was done while he was a graduate student at the University of Maryland. The research of A. Srinivasan is partially supported by the National Science Foundation [Awards CNS 1010789, CCF-1422569, CCF-1749864, and CCF-1918749]; Adobe, Inc. [research awards]; Amazon, Inc.; and Google, Inc. The research of P. Xu was supported in part by the National Science Foundation [Awards CNS 1010789 and CCF-1422569 (when he was a graduate student)] and is partially funded by the National Science Foundation [CRII Award IIS-1948157]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2018.0340. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Volltext ist im Gastzugang nicht verfügbar. Login für vollen Zugriff.