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

Fine-grained visual categorization (FGVC) is a challenging task due to
similar visual appearances between various species. Previous studies always
implicitly assume that the training and test data have the same underlying
distributions, and that features extracted by modern backbone architectures
remain discriminative and generalize well to unseen test data. However, we
empirically justify that these conditions are not always true on benchmark
datasets. To this end, we combine the merits of invariant risk minimization
(IRM) and information bottleneck (IB) principle to learn invariant and minimum
sufficient (IMS) representations for FGVC, such that the overall model can
always discover the most succinct and consistent fine-grained features. We
apply the matrix-based R{\'e}nyi's $\alpha$-order entropy to simplify and
stabilize the training of IB; we also design a ``soft" environment partition
scheme to make IRM applicable to FGVC task. To the best of our knowledge, we
are the first to address the problem of FGVC from a generalization perspective
and develop a new information-theoretic solution accordingly. Extensive
experiments demonstrate the consistent performance gain offered by our IMS.

通过适用于不变风险最小化和信息瓶颈原理的方法，从泛化的角度解决细粒度视觉分类问题，并应用 Rényi 的 α- 阶熵和软环境分割方案来训练模型，以学习不变和最小化的表示。实验证实了该方案在细粒度视觉分类中能显著提高性能。