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 的学习理论分析集合组合与算法选择的方法，并通过实验证明个体算法选择器的复杂性和算法性能的学习理论复杂性将会对方案的性能产生重要影响。

基于组合投资算法选择的泛化性能

Generalization in portfolio-based algorithm selection

To appear in Theory and Practice of Logic Programming (TPLP). Building on the
award-winning, portfolio-based ASP solver claspfolio, we present claspfolio 2,
a modular and open solver architecture that integrates several different
portfolio-based algorithm selection approaches and techniques. The claspfolio 2
solver framework supports various feature generators, solver selection
approaches, solver portfolios, as well as solver-schedule-based pre-solving
techniques. The default configuration of claspfolio 2 relies on a light-weight
version of the ASP solver clasp to generate static and dynamic instance
features. The flexible open design of claspfolio 2 is a distinguishing factor
even beyond ASP. As such, it provides a unique framework for comparing and
combining existing portfolio-based algorithm selection approaches and
techniques in a single, unified framework. Taking advantage of this, we
conducted an extensive experimental study to assess the impact of different
feature sets, selection approaches and base solver portfolios. In addition to
gaining substantial insights into the utility of the various approaches and
techniques, we identified a default configuration of claspfolio 2 that achieves
substantial performance gains not only over clasp's default configuration and
the earlier version of claspfolio 2, but also over manually tuned
configurations of clasp.

论文介绍了 claspfolio2，它是一个基于 ASP 求解器的模块化、开放的求解器架构，并支持不同的算法选择方法和技术，并针对不同特征集、选择方法和基础求解器组合进行了广泛的实验研究，得出了默认配置的 claspfolio 2 具有显著的性能优势。