The Famine of Forte: Few Search Problems Greatly Favor Your Algorithm
This foundational result explains why no single algorithm can dominate across many problems, impacting all of ML/AI by highlighting inherent limitations in algorithm design.
The paper demonstrates that for any fixed algorithm, the proportion of problems it can perform well on is strictly bounded, explaining the need for continual development of new methods or highly parameterized models, and provides an upper bound on expected performance based on mutual information between target and information resource.
Casting machine learning as a type of search, we demonstrate that the proportion of problems that are favorable for a fixed algorithm is strictly bounded, such that no single algorithm can perform well over a large fraction of them. Our results explain why we must either continue to develop new learning methods year after year or move towards highly parameterized models that are both flexible and sensitive to their hyperparameters. We further give an upper bound on the expected performance for a search algorithm as a function of the mutual information between the target and the information resource (e.g., training dataset), proving the importance of certain types of dependence for machine learning. Lastly, we show that the expected per-query probability of success for an algorithm is mathematically equivalent to a single-query probability of success under a distribution (called a search strategy), and prove that the proportion of favorable strategies is also strictly bounded. Thus, whether one holds fixed the search algorithm and considers all possible problems or one fixes the search problem and looks at all possible search strategies, favorable matches are exceedingly rare. The forte (strength) of any algorithm is quantifiably restricted.