Small-Data, Large-Scale Linear Optimization with Uncertain Objectives

Vishal Gupta () and Paat Rusmevichientong ()
Additional contact information
Vishal Gupta: Data Science and Operations, University of Southern California Marshall School of Business, Los Angeles, California 90089
Paat Rusmevichientong: Data Science and Operations, University of Southern California Marshall School of Business, Los Angeles, California 90089

Management Science, 2021, vol. 67, issue 1, 220-241

Abstract: Optimization applications often depend on a huge number of uncertain parameters. In many contexts, however, the amount of relevant data per parameter is small, and hence, we may only have imprecise estimates. We term this setting—in which the number of uncertainties is large but all estimates have low precision—the small-data, large-scale regime . We formalize a model for this new regime, focusing on optimization problems with uncertain linear objectives. We show that common data-driven methods, such as sample average approximation, data-driven robust optimization, and certain regularized policies, may perform poorly in this new setting. We then propose a novel framework for selecting a data-driven policy from a given policy class. As with the aforementioned data-driven methods, our new policy enjoys provably good performance in the large-sample regime. Unlike these methods, we show that in the small-data, large-scale regime, our data-driven policy performs comparably to an oracle best-in-class policy under some mild conditions. We strengthen this result for linear optimization problems and two natural policy classes, the first inspired by the empirical Bayes literature and the second by regularization techniques. For both classes, the suboptimality gap between our proposed policy and the oracle policy decays exponentially fast in the number of uncertain parameters even for a fixed amount of data. Thus, these policies retain the strong large-sample performance of traditional methods and additionally enjoy provably strong performance in the small-data, large-scale regime. Numerical experiments confirm the significant benefits of our methods.

Keywords: data-driven optimization; small-data; large-scale regime; Stein's unbiased risk estimation (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1287/mnsc.2019.3554 (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:ormnsc:v:67:y:2021:i:1:p:220-241

Access Statistics for this article

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