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

arXiv: https://arxiv.org/abs/2405.11349 · HTML: https://mlsanity.com/paper/2405.11349/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 44 references that are in the map.
- First posted on arXiv 18 May 2024.

## Builds on (most cited first, 13 of 13)

- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Model Evaluation, Model Selection, and Algorithm Selection in Machine Learning](https://mlsanity.com/paper/1811.12808/) (2018)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation](https://mlsanity.com/paper/2210.07394/) (2022)
- [Probabilistic Matrix Factorization for Automated Machine Learning](https://mlsanity.com/paper/1705.05355/) (2017)
- [Transductive Rademacher Complexity and its Applications](https://mlsanity.com/paper/1401.3441/) (2014)
- [Extreme Algorithm Selection With Dyadic Feature Representation](https://mlsanity.com/paper/2001.10741/) (2020)
- [Explorative Data Analysis of Time Series based AlgorithmFeatures of CMA-ES Variants](https://mlsanity.com/paper/2104.08098/) (2021)
- [Tight Risk Bounds for Multi-Class Margin Classifiers](https://mlsanity.com/paper/1507.03040/) (2015)
- [HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection](https://mlsanity.com/paper/2210.17341/) (2022)

## Abstract (arXiv)

In the 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. 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 different 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, such as the training scale of problem instances and candidate algorithms, model parameters, feature values, and distributional differences between the training and test data. Notably, we demonstrate how models will benefit from algorithm features in complex scenarios involving many algorithms, and proves the positive correlation between generalization error bound and chi2-divergence of distributions.