Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity

Abstract

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.

References in corpus (1)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks

Cited by in corpus (7)

• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• On the Approximation Power of Two-Layer Networks of Random ReLUs
• When Hardness of Approximation Meets Hardness of Learning
• A case where a spindly two-layer linear network whips any neural network with a fully connected input layer
• The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks