论文摘要：

列子集选择问题（CSSP）和Nystrom方法是机器学习和科学计算中构造大数据集、小低阶秩近似的主要工具之一。这个领域的一个基本问题是：大小为k的数据子集与最佳秩k近似的竞争程度如何？

我们开发了利用数据矩阵的光谱（spectra）特性的技术，以获得超出标准最差用例（worstcase）分析的改进近似保证。对于已知奇异值衰减率（如多项式或指数衰减）的数据集，我们的方法可以得到更好的边界（bound）。

我们的分析还揭示了一个有趣的现象：近似因子作为k的函数可能会出现多个峰和谷，我们称之为多重下降曲线（multipledescent curve）。

我们建立的一个下限表明，这种行为不是我们分析的产物，而是CSSP和Nystrom任务的固有属性。

最后，以径向基函数（RBF）核为例，本文证明了只要改变RBF参数，我们的改进边界和多重下降曲线都可以在真实数据集上观察到。

获奖理由：

从大矩阵中选择一个小型但有代表性的列向量子集并不容易。针对这个问题，找到一种基于基数受限的行列式点过程（determinantal point processes，DPP）的方法，就代表要提供一个实用的近似解决方案。

这篇论文针对最佳可能的低秩近似（low-rank approximation）推导了近似解中近似因子的新上限和下限，甚至可以捕获子集尺寸的多重下降行为。此外，该论文将分析进一步扩展，以获得Nyström方法。

由于这些近似技巧已在机器学习中得到广泛应用，因此，这篇论文有望产生重大影响，并为核方法、特征选择和神经网络的双下降行为等提供新的见解。

获奖理由：

相关均衡（correlated equilibria，CE）容易计算，对社会的帮助比常见的纳什均衡（Nash equilibria）大很多。在许多博弈中，CE都展示了一个令人惊讶的性能：可以通过简单且分散的算法将所谓的内部遗憾降到最低，从而找到CE。 

这篇论文表明，在大规模博弈中，即广义（或树型）博弈中，确实存在能够将遗憾降到最低的、收敛到CE的算法。

论文结果通过博弈论、计算机科学和经济学的交叉解决了一个长期存在的开放性问题，并且对涉及调解器的博弈具有潜在的巨大影响，比如通过导航app有效规划交通路线。