mlsanityData to 14 Oct 2026

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

arXiv 2003.04180 ↗First posted 9 Mar 2020cs.LG stat.MLcited by 25

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 25 papers in the map (data through 14 Oct 2026). First posted on arXiv 9 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 4; 2023: 4; 2024: 4; 2025: 3; 2026: 2.

25 papers.

Sort:

  1. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  2. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  3. 2021Quantum machine learning beyond kernel methodscited by 92
  4. 2022A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Featurescited by 49
  5. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  6. 2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
  7. 2022Random Feature Amplification: Feature Learning and Generalization in Neural Networkscited by 35
  8. 2021On the Approximation Power of Two-Layer Networks of Random ReLUscited by 29
  9. 2021The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networkscited by 26
  10. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  11. 2021Understanding the Eluder Dimensioncited by 19
  12. 2022On the non-universality of deep learning: quantifying the cost of symmetrycited by 18
13 more
  1. 2021Learning a Single Neuron with Bias Using Gradient Descentcited by 17
  2. 2023Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networkscited by 16
  3. 2023Provable Guarantees for Neural Networks via Gradient Feature Learningcited by 14
  4. 2023Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luckcited by 13
  5. 2021Reconstruction on Trees and Low-Degree Polynomialscited by 10
  6. 2024On the Benefits of Rank in Attention Layerscited by 5
  7. 2025Spherical dimensioncited by 4
  8. 2026Is Dimensionality a Barrier for Retrieval Models?cited by 3
  9. 2024RedEx: Beyond Fixed Representation Methods via Convex Optimizationcited by 1
  10. 2024On Reductions and Representations of Learning Problems in Euclidean Spacescited by 1
  11. 2025The Power of Random Features and the Limits of Distribution-Free Gradient Descentcited by 0
  12. 2025Dimension lower bounds for linear approaches to function approximationcited by 0
  13. 2026Structured vs. Unstructured Pruning: An Exponential Gapcited by 0