The Bias-Expressivity Trade-off
This addresses a foundational issue in machine learning theory, providing insights into algorithm design trade-offs, but it is incremental as it builds on existing concepts of bias and expressivity.
The paper tackles the problem of balancing bias and expressivity in learning algorithms, demonstrating a trade-off where increased bias improves performance over random sampling but reduces flexibility, with derived bounds proving inherent limitations.
Learning algorithms need bias to generalize and perform better than random guessing. We examine the flexibility (expressivity) of biased algorithms. An expressive algorithm can adapt to changing training data, altering its outcome based on changes in its input. We measure expressivity by using an information-theoretic notion of entropy on algorithm outcome distributions, demonstrating a trade-off between bias and expressivity. To the degree an algorithm is biased is the degree to which it can outperform uniform random sampling, but is also the degree to which is becomes inflexible. We derive bounds relating bias to expressivity, proving the necessary trade-offs inherent in trying to create strongly performing yet flexible algorithms.