Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
This work addresses a foundational issue in machine learning theory for researchers, providing a more accurate framework to discuss the capabilities of linear predictors.
The paper tackles the problem of characterizing limitations of linear and kernel methods in machine learning by introducing approximate notions of dimensional and margin complexity, showing these are necessary and sufficient for learning, unlike exact variants.
We present and study approximate notions of dimensional and margin complexity, which correspond to the minimal dimension or norm of an embedding required to approximate, rather then exactly represent, a given hypothesis class. We show that such notions are not only sufficient for learning using linear predictors or a kernel, but unlike the exact variants, are also necessary. Thus they are better suited for discussing limitations of linear or kernel methods.