张智杰，孙晓明，张家琳，陈卫

1. 中国科学院计算技术研究所，北京 100086；2. 中国科学院大学，北京 100049；3. 微软亚洲研究院，北京 100080

1 引言

为了解决实际生活中遇到的统筹优化问题，人们通常要建立一个问题模型，并确定模型的参数和优化目标函数，然后设计算法进行求解。然而，在大数据时代，许多应用场景无法提供足够的信息来确定模型参数和目标函数。人们只能通过观察到的历史样本数据来获取模型的信息，并进行优化。在这类场景下，人们通常使用机器学习的方法进行处理：首先近似地学习一个替代的目标函数，然后优化这个替代的函数。尽管这个方法在实际应用中获得了巨大的成功，但是在很多实际问题中，这个方法缺乏理论上的保证。事实上，它可能存在如下两个问题：① 即使针对原函数的优化问题是可求解或者可近似求解的，但是针对替代函数的优化问题也可能是不可近似的，这是因为替代函数可能丢失了一些原函数所具有的良好性质（如次模性）；② 即使替代函数是可近似的，而且从整体上看和原函数很接近，但是它的最优解相较于原函数的最优解也可能是一个很差的近似。这些担忧自然地引出了如下问题：人们是否真的能从一系列样本数据中求解目标函数的优化问题？

1.1 样本优化模型

为了回答基于样本的组合优化是否可能的问题，Balkanski E等人[1]定义了另一种计算模型——样本优化（optimization from samples，OPS）模型。

定义1（OPS模型）给定参数如果存在算法A（不一定是多项式时间的），给定参数并将样本集作为输入，其中，Si独立同分布于D，，算法A返回S∈M，并满足