Improved Sample-Complexity Bounds in Stochastic Optimization

• 成果类型: Article
• 署名作者: Baveja, Alok; Chavan, Amit; Nikiforov, Andrei; Srinivasan, Aravind; Xu, Pan
• 署名单位: Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University Camden; Rutgers University New Brunswick; University System of Maryland; University of Maryland College Park; New Jersey Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.0340
• 发表日期: 2025
• 关键词: approximation algorithms; lp

摘要

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.