Small-Data, Large-Scale Linear Optimization with Uncertain Objectives
Small-Data, Large-Scale Linear Optimization with Uncertain Objectives
复制标题
目标不确定的小数据、大规模线性优化
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Paat Rusmevichientong
中科院分区：
文献类型：
--
作者：
Vishal Gupta;Paat Rusmevichientong
优化应用通常依赖于大量的不确定参数。然而，在许多情况下，每个参数的相关数据量很小，因此，我们可能只有不精确的估计。我们将这种不确定性数量很大但所有估计精度较低的环境称为小数据、大规模体系。我们为这种新机制形式化了一个模型，重点关注具有不确定线性目标的优化问题。我们表明，常见的数据驱动方法，例如样本平均近似、数据驱动的鲁棒优化和某些正则化策略，在这种新环境中可能表现不佳。然后，我们提出了一个新的框架，用于从给定的策略类别中选择数据驱动的策略。与上述数据驱动方法一样，我们的新策略在大样本情况下具有良好的性能。与这些方法不同的是，我们表明，在小数据、大规模的情况下，我们的数据驱动策略在某些温和条件下的表现与预言机同类最佳策略相当。我们针对线性优化问题和两个自然策略类别强化了这一结果，第一个类别受到经验贝叶斯文献的启发，第二个类别受到正则化技术的启发。对于这两个类别，即使对于固定数量的数据，我们提出的策略和预言机策略之间的次优差距在不确定参数的数量上也会呈指数级快速衰减。因此，这些策略保留了传统方法强大的大样本性能，并且在小数据、大规模的情况下也享有可证明的强大性能。数值实验证实了我们的方法的显着优点。该论文被叶银宇接收，优化。
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. This paper was accepted by Yinyu Ye, optimization.