# Optimal learning of high-dimensional classification problems using deep neural networks

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 49 references that are in the map.
- First posted on arXiv 23 Dec 2021.

## Builds on (most cited first, 17 of 17)

- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't](https://mlsanity.com/paper/2009.10713/) (2020)
- [Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networks](https://mlsanity.com/paper/2101.12365/) (2021)
- [Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with  ℓ1  and  ℓ0  Controls](https://mlsanity.com/paper/1607.07819/) (2016)
- [A Priori Estimates of the Population Risk for Two-layer Neural Networks](https://mlsanity.com/paper/1810.06397/) (2018)
- [The Modern Mathematics of Deep Learning](https://mlsanity.com/paper/2105.04026/) (2021)
- [Representation formulas and pointwise properties for Barron functions](https://mlsanity.com/paper/2006.05982/) (2020)
- [Deep Neural Networks Learn Non-Smooth Functions Effectively](https://mlsanity.com/paper/1802.04474/) (2018)
- [Fast convergence rates of deep neural networks for classification](https://mlsanity.com/paper/1812.03599/) (2018)
- [Analysis of the Generalization Error: Empirical Risk Minimization over Deep Artificial Neural Networks Overcomes the Curse of Dimensionality in the Numerical Approximation of Black-Scholes Partial Differential Equations](https://mlsanity.com/paper/1809.03062/) (2018)
- [On the Banach spaces associated with multi-layer ReLU networks: Function representation, approximation theory and gradient descent dynamics](https://mlsanity.com/paper/2007.15623/) (2020)
- [Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces](https://mlsanity.com/paper/2104.02746/) (2021)
- [Neural network approximation and estimation of classifiers with classification boundary in a Barron class](https://mlsanity.com/paper/2011.09363/) (2020)
- [Risk Bounds for High-dimensional Ridge Function Combinations Including Neural Networks](https://mlsanity.com/paper/1607.01434/) (2016)

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

- [A general approximation lower bound in Lp norm, with applications to feed-forward neural networks](https://mlsanity.com/paper/2206.04360/) (2022)
- [Lp sampling numbers for the Fourier-analytic Barron space](https://mlsanity.com/paper/2208.07605/) (2022)
- [Deep ReLU networks and high-order finite element methods II: Chebyshev emulation](https://mlsanity.com/paper/2310.07261/) (2023)
- [High-dimensional classification problems with Barron regular boundaries under margin conditions](https://mlsanity.com/paper/2412.07312/) (2024)
- [Optimal Learning](https://mlsanity.com/paper/2203.15994/) (2022)
- [Dimension-independent learning rates for high-dimensional classification problems](https://mlsanity.com/paper/2409.17991/) (2024)
- [Super-fast Rates of Convergence for Neural Network Classifiers under the Hard Margin Condition](https://mlsanity.com/paper/2505.08262/) (2025)
- [Minimax learning rates for estimating binary classifiers under margin conditions](https://mlsanity.com/paper/2505.10628/) (2025)
- [Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks](https://mlsanity.com/paper/2607.01266/) (2026)

## Abstract (arXiv)

We study the problem of learning classification functions from noiseless training samples, under the assumption that the decision boundary is of a certain regularity. We establish universal lower bounds for this estimation problem, for general classes of continuous decision boundaries. For the class of locally Barron-regular decision boundaries, we find that the optimal estimation rates are essentially independent of the underlying dimension and can be realized by empirical risk minimization methods over a suitable class of deep neural networks. These results are based on novel estimates of the L1 and L^∞ entropies of the class of Barron-regular functions.