Decomposable Probability-of-Success Metrics in Algorithmic Search
This work addresses a theoretical bottleneck for researchers in machine learning by providing a more flexible framework for analyzing search algorithms, though it appears incremental as it builds on existing impossibility results.
The paper tackles the limitation of existing success metrics in algorithmic search that hinder generalization to other machine learning forms like transfer learning by introducing decomposable metrics, and demonstrates theorems that bound search success, generalizing prior results.
Previous studies have used a specific success metric within an algorithmic search framework to prove machine learning impossibility results. However, this specific success metric prevents us from applying these results on other forms of machine learning, e.g. transfer learning. We define decomposable metrics as a category of success metrics for search problems which can be expressed as a linear operation on a probability distribution to solve this issue. Using an arbitrary decomposable metric to measure the success of a search, we demonstrate theorems which bound success in various ways, generalizing several existing results in the literature.