Generalization Bounds for Model-based Algorithm Configuration
Zhiyang Chen, Hailong Yao, Xia Yin
Abstract
Algorithm configuration, which involves selecting algorithm parameters based on sampled problem instances, is a crucial step in applying modern algorithms such as SAT solvers. Although prior work has attempted to understand the theoretical foundations of algorithm configuration, we still lack a comprehensive understanding of why practical algorithm configurators exhibit strong generalization performances in real-world scenarios. In this paper, through the lens of machine learning theory, we provide an algorithm-dependent generalization bound for the widely used model-based algorithm configurators under mild assumptions. Our approach is based on the algorithmic stability framework for generalization bounds. To the best of our knowledge, this is the first generalization bound that applies to a model closely approximating practical model-based algorithm configurators.
BibTeX
@inproceedings{
chen2025generalization,
title={Generalization Bounds for Model-based Algorithm Configuration},
author={Zhiyang Chen and Hailong Yao and Xia Yin},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=bAJCfIywYl}
}