How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design
How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design
复制标题
DOI：
10.1145/3406325.3451036
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Maria-Florina Balcan;Dan F. DeBlasio;Travis Dick;Carl Kingsford;T. Sandholm;Ellen Vitercik
中科院分区：
文献类型：
--
作者：
Maria-Florina Balcan;Dan F. DeBlasio;Travis Dick;Carl Kingsford;T. Sandholm;Ellen Vitercik
算法通常具有可调整的参数，这些参数会影响运行时和解决方案质量等性能指标。对于实践中使用的许多算法，没有任何参数设置允许有意义的最坏情况界限，因此参数可供用户调整。或者，可以在最坏情况保证的证明中隐含地调整参数。然而，最糟糕的情况在实践中可能很少或根本不存在。越来越多的研究表明，数据驱动的算法设计可以显著提高性能。该方法使用从未知的、特定于应用的分布中采样的问题实例的训练集，并返回训练集上具有较强平均性能的参数设置。我们提供了一个广泛适用的理论来推导泛化保证，该保证限定了算法在训练集上的平均性能与其在未知分布上的期望性能之间的差异。无论参数如何调整，无论是通过自动方法还是手动方法，我们的结果都适用。挑战在于，对于许多类型的算法，性能是参数的不稳定函数：稍微扰动参数可能会导致行为发生很大变化。先前的研究(例如，Gupta和RoughGarden，SICOMP‘17；Balcan等，Colt’17，ICML‘18，EC’18)已经通过使用对贪婪算法、集群算法、整数规划算法和销售机制的逐个分析来证明泛化界限。我们发现了一个统一的结构，我们用它来证明极其一般的保证，但我们从以前的研究中恢复了界限。在最坏的情况下，我们的保证严格到对数因子，只要算法的性能是其参数的分段常量、线性或更一般的分段结构函数时，我们的保证就适用。我们的理论还暗示了计算生物学中投票机制和动态规划算法的新界限。
Algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit meaningful worst-case bounds, so the parameters are made available for the user to tune. Alternatively, parameters may be tuned implicitly within the proof of a worst-case guarantee. Worst-case instances, however, may be rare or nonexistent in practice. A growing body of research has demonstrated that data-driven algorithm design can lead to significant improvements in performance. This approach uses a training set of problem instances sampled from an unknown, application-specific distribution and returns a parameter setting with strong average performance on the training set. We provide a broadly applicable theory for deriving generalization guarantees that bound the difference between the algorithm’s average performance over the training set and its expected performance on the unknown distribution. Our results apply no matter how the parameters are tuned, be it via an automated or manual approach. The challenge is that for many types of algorithms, performance is a volatile function of the parameters: slightly perturbing the parameters can cause a large change in behavior. Prior research (e.g., Gupta and Roughgarden, SICOMP’17; Balcan et al., COLT’17, ICML’18, EC’18) has proved generalization bounds by employing case-by-case analyses of greedy algorithms, clustering algorithms, integer programming algorithms, and selling mechanisms. We uncover a unifying structure which we use to prove extremely general guarantees, yet we recover the bounds from prior research. Our guarantees, which are tight up to logarithmic factors in the worst case, apply whenever an algorithm’s performance is a piecewise-constant, -linear, or—more generally—piecewise-structured function of its parameters. Our theory also implies novel bounds for voting mechanisms and dynamic programming algorithms from computational biology.