The best algorithm for a computational problem generally depends on the
"relevant inputs," a concept that depends on the application domain and often
defies formal articulation. While there is a large literature on empirical
approaches to selecting the best algorithm for a given application domain,
there has been surprisingly little theoretical analysis of the problem.
This paper adapts concepts from statistical and online learning theory to
reason about application-specific algorithm selection. Our models capture
several state-of-the-art empirical and theoretical approaches to the problem,
ranging from self-improving algorithms to empirical performance models, and our
results identify conditions under which these approaches are guaranteed to
perform well. We present one framework that models algorithm selection as a
statistical learning problem, and our work here shows that dimension notions
from statistical learning theory, historically used to measure the complexity
of classes of binary- and real-valued functions, are relevant in a much broader
algorithmic context. We also study the online version of the algorithm
selection problem, and give possibility and impossibility results for the
existence of no-regret learning algorithms.

本文使用统计和在线学习理论的概念来分析特定应用领域下的算法选择问题，并将算法选择建模为统计学习问题，同时研究了在线算法选择问题的可能性和不可能性结果。