Technical Note—Improved Sample-Complexity Bounds in Stochastic Optimization

Alok Baveja (), Amit Chavan (), Andrei Nikiforov (), Aravind Srinivasan () and Pan Xu ()
Additional contact information
Alok Baveja: Department of Supply Chain Management, Rutgers Business School, Rutgers, The State University of New Jersey, Piscataway, New Jersey 08854
Amit Chavan: Product and Engineering, Snowflake Inc., San Mateo, California 94402
Andrei Nikiforov: School of Business, Rutgers, The State University of New Jersey, Camden, New Jersey 08102
Aravind Srinivasan: Department of Computer Science, University of Maryland, College Park, Maryland 20742
Pan Xu: Department of Computer Science, New Jersey Institute of Technology, Newark, New Jersey 07102

Operations Research, 2025, vol. 73, issue 2, 986-994

Abstract: 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.

Keywords: Optimization; stochastic optimization; sample-average approximation; sample complexity (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2018.0340 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:2:p:986-994

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().