Confidence Sets for the Sample Average Approximation of Stochastic Discrete Optimization Problems

Mario Martinoli, Raffaello Seri and Samuele Tonati

LEM Papers Series from Laboratory of Economics and Management (LEM), Sant'Anna School of Advanced Studies, Pisa, Italy

Abstract: We propose a method to build confidence sets for the solutions of stochastic discrete optimization problems solved through the sample average approximation method. By combining the concept of Model Confidence Set (MCS) with shrinkage estimation of large covariance matrices, we accommodate sampling mechanisms that allow for arbitrary dependence across alternatives, even when the number of alternatives is larger than the sample size, and deliver confidence sets asymptotically containing the solution set with probability at least 1-α for predetermined α. We derive bounds for the error induced by replacing the true covariance matrix with an estimator and characterize the impact of this error on the asymptotic distribution of the MCS test statistics. We test the theoretical properties of our set estimator in finite samples through an extensive Monte Carlo experiment involving the computation of the covariance matrix using different shrinkage estimators. This research is the first to provide generally applicable measures of uncertainty in discrete optimization. Whenever a stochastic discrete optimization problem is solved using the sample average approximation method, the confidence set should be reported alongside the solution in order to provide a measure of uncertainty. The main contribution of the paper is to offer, for the first time, a method for computing confidence sets for the solutions of stochastic discrete optimization problems. We also derive a bound on the accuracy of the asymptotic distribution for a class of test statistics involving covariance matrices estimated with non-standard estimators.

Keywords: Stochastic discrete optimization; Sample average approximation; Confidence set; Shrinkage estimation; Covariance structure. (search for similar items in EconPapers)
Date: 2026-03-05
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.lem.sssup.it/WPLem/files/2026-09.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.lem.santannapisa.it:443 (certificate verify failed) (http://www.lem.sssup.it/WPLem/files/2026-09.pdf [302 Found]--> https://www.lem.santannapisa.it/WPLem/files/2026-09.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:ssa:lemwps:2026/09

Access Statistics for this paper

More papers in LEM Papers Series from Laboratory of Economics and Management (LEM), Sant'Anna School of Advanced Studies, Pisa, Italy Contact information at EDIRC.
Bibliographic data for series maintained by ().