Portfolio-based algorithm selection has seen tremendous practical success
over the past two decades. This algorithm configuration procedure works by
first selecting a portfolio of diverse algorithm parameter settings, and then,
on a given problem instance, using an algorithm selector to choose a parameter
setting from the portfolio with strong predicted performance. Oftentimes, both
the portfolio and the algorithm selector are chosen using a training set of
typical problem instances from the application domain at hand. In this paper,
we provide the first provable guarantees for portfolio-based algorithm
selection. We analyze how large the training set should be to ensure that the
resulting algorithm selector's average performance over the training set is
close to its future (expected) performance. This involves analyzing three key
reasons why these two quantities may diverge: 1) the learning-theoretic
complexity of the algorithm selector, 2) the size of the portfolio, and 3) the
learning-theoretic complexity of the algorithm's performance as a function of
its parameters. We introduce an end-to-end learning-theoretic analysis of the
portfolio construction and algorithm selection together. We prove that if the
portfolio is large, overfitting is inevitable, even with an extremely simple
algorithm selector. With experiments, we illustrate a tradeoff exposed by our
theoretical analysis: as we increase the portfolio size, we can hope to include
a well-suited parameter setting for every possible problem instance, but it
becomes impossible to avoid overfitting.

本文探讨了基于组合算法选择的一个有效算法配置过程，分析了三种情况可能导致多样性的算法集合与性能预测之间的差距，提出了一种 end-to-end 的学习理论分析集合组合与算法选择的方法，并通过实验证明个体算法选择器的复杂性和算法性能的学习理论复杂性将会对方案的性能产生重要影响。