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

arXiv: https://arxiv.org/abs/2003.04180 · HTML: https://mlsanity.com/paper/2003.04180/

## Key facts

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

## Built on by (most cited first, 25 of 25)

- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features](https://mlsanity.com/paper/2206.01717/) (2022)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2110.03922/) (2021)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [Understanding the Eluder Dimension](https://mlsanity.com/paper/2104.06970/) (2021)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/2307.06887/) (2023)
- [Provable Guarantees for Neural Networks via Gradient Feature Learning](https://mlsanity.com/paper/2310.12408/) (2023)
- [Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck](https://mlsanity.com/paper/2309.03800/) (2023)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [On the Benefits of Rank in Attention Layers](https://mlsanity.com/paper/2407.16153/) (2024)
- [Spherical dimension](https://mlsanity.com/paper/2503.10240/) (2025)
- [Is Dimensionality a Barrier for Retrieval Models?](https://mlsanity.com/paper/2605.23556/) (2026)
- [RedEx: Beyond Fixed Representation Methods via Convex Optimization](https://mlsanity.com/paper/2401.07606/) (2024)
- [On Reductions and Representations of Learning Problems in Euclidean Spaces](https://mlsanity.com/paper/2411.10784/) (2024)
- [The Power of Random Features and the Limits of Distribution-Free Gradient Descent](https://mlsanity.com/paper/2505.10423/) (2025)
- [Dimension lower bounds for linear approaches to function approximation](https://mlsanity.com/paper/2508.13346/) (2025)
- [Structured vs. Unstructured Pruning: An Exponential Gap](https://mlsanity.com/paper/2603.02234/) (2026)

## 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.