ポートフォリオベースのアルゴリズム選択は、過去20年間で素晴らしい実績を上げてきました。この手法では、まず多様なアルゴリズムのパラメータ設定からなるポートフォリオを選択し、特定の問題に対して予測されるパフォーマンスが優れた設定を選ぶアルゴリズム選択器を用います。本論文では、ポートフォリオベースのアルゴリズム選択に関する初めての証明可能な保証を提示し、トレーニングセットのサイズが結果の選択器のパフォーマンスにどのように影響するかを分析しています。ポートフォリオのサイズやアルゴリズム選択器の複雑さなど、パフォーマンス予測の不確実性に関わる3つの要因を考慮しながら、ポートフォリオの大きさが過剰適合（オーバーフィッティング）を引き起こすことを証明しています。実験を通じて、ポートフォリオのサイズを増やすことで全ての問題事例に合った設定を含める可能性が高まる一方で、過剰適合を避けることが不可能になるトレードオフを示しています。