In the field of algorithm selection research, the discussion surrounding
algorithm features has been significantly overshadowed by the emphasis on
problem features. Although a few empirical studies have yielded evidence
regarding the effectiveness of algorithm features, the potential benefits of
incorporating algorithm features into algorithm selection models and their
suitability for different scenarios remain unclear. It is evident that relying
solely on empirical research cannot adequately elucidate the mechanisms
underlying performance variations. In this paper, we address this gap by
proposing the first provable guarantee for algorithm selection based on
algorithm features, taking a generalization perspective. We analyze the
benefits and costs associated with algorithm features and investigate how the
generalization error is affected by several factors. Specifically, we examine
adaptive and predefined algorithm features under transductive and inductive
learning paradigms, respectively, and derive upper bounds for the
generalization error based on their model's Rademacher complexity. Our
theoretical findings not only provide tight upper bounds, but also offer
analytical insights into the impact of various factors, including model
complexity, the number of problem instances and candidate algorithms, model
parameters and feature values, and distributional differences between the
training and test sets. Notably, we demonstrate that algorithm feature-based
models outperform traditional models relying solely on problem features in
complex multi-algorithm scenarios in terms of generalization, and are
particularly well-suited for deployment in scenarios under distribution shifts,
where the generalization error exhibits a positive correlation with the
chi-square distance between training and test sets.

通过算法特征以及一般化观点，我们提出了基于算法特征的算法选择具有可证的保证的第一个模型，并分析了几个因素对一般化误差的影响。我们证明了在复杂的多算法场景中，基于算法特征的模型在一般化方面优于仅依赖问题特征的传统模型，并在分布变化的场景中表现出正相关的一般化误差和训练集与测试集之间的卡方距离。