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.

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

解锁算法特性的力量：算法选择的推广分析

Unlock the Power of Algorithm Features: A Generalization Analysis for  Algorithm Selection

Algorithm selection aims to identify the most suitable algorithm for solving
a specific problem before execution, which has become a critical process of the
AutoML. Current mainstream algorithm selection techniques rely heavily on
feature representations of various problems and employ the performance of each
algorithm as supervised information. However, there is a significant research
gap concerning the consideration of algorithm features. This gap is primarily
attributed to the inherent complexity of algorithms, making it particularly
challenging to find a universally effective feature extraction method that is
applicable across a diverse range of algorithms. Unfortunately, neglecting this
aspect undoubtedly impacts the accuracy of algorithm selection and indirectly
necessitates an increased volume of problem data for training purposes. This
paper takes a significant stride towards addressing this gap by proposing an
approach that integrates algorithm representation into the algorithm selection
process. Specifically, our proposed model employs distinct modules to extract
representations of both problems and algorithms, where the algorithm
representation leverages the capabilities of pre-trained LLMs in the realm of
code comprehension. Following the extraction of embedding vectors for both
algorithms and problems, the most suitable algorithm is determined through
calculations of matching degrees. Our experiments not only validate the
effectiveness of the proposed model but also showcase the performance of
different embedded pre-trained LLMs, which suggests that the proposed algorithm
selection framework holds the potential to serve as a baseline task for
evaluating the code representation capabilities of LLMs.

该论文提出了一种将算法表示集成到算法选择过程中的方法，通过模块化提取问题和算法的表示，利用预训练的 LLMs 来计算匹配度，实验证实了该模型的有效性以及预训练 LLMs 的性能，表明该算法选择框架有潜力作为评估 LLMs 编码表示能力的基准任务。