# On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2019.

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

- [Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks](https://mlsanity.com/paper/2109.08844/) (2021)
- [Transformers are Minimax Optimal Nonparametric In-Context Learners](https://mlsanity.com/paper/2408.12186/) (2024)
- [Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input](https://mlsanity.com/paper/2305.18699/) (2023)
- [Generalization Ability of Wide Neural Networks on ℝ](https://mlsanity.com/paper/2302.05933/) (2023)
- [Flow matching achieves almost minimax optimal convergence](https://mlsanity.com/paper/2405.20879/) (2024)
- [A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Models](https://mlsanity.com/paper/2401.07187/) (2024)
- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspective](https://mlsanity.com/paper/2403.14917/) (2024)
- [Adaptive deep learning for nonlinear time series models](https://mlsanity.com/paper/2207.02546/) (2022)
- [Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methods](https://mlsanity.com/paper/2205.14818/) (2022)
- [On the inability of Gaussian process regression to optimally learn compositional functions](https://mlsanity.com/paper/2205.07764/) (2022)
- [Misclassification bounds for PAC-Bayesian sparse deep learning](https://mlsanity.com/paper/2405.01304/) (2024)
- [Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation](https://mlsanity.com/paper/2301.11936/) (2023)
- [How many samples are needed to train a deep neural network?](https://mlsanity.com/paper/2405.16696/) (2024)
- [Deep learning from strongly mixing observations: Sparse-penalized regularization and minimax optimality](https://mlsanity.com/paper/2406.08321/) (2024)
- [Optimality and Adaptivity of Deep Neural Features for Instrumental Variable Regression](https://mlsanity.com/paper/2501.04898/) (2025)
- [Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size](https://mlsanity.com/paper/2502.11467/) (2025)
- [Optimally taming biases in black-box models for efficient semiparametric estimation](https://mlsanity.com/paper/2606.06368/) (2026)
- [Nonasymptotic theory for two-layer neural networks: Beyond the bias-variance trade-off](https://mlsanity.com/paper/2106.04795/) (2021)
- [Pointwise convergence of Fourier series and deep neural network for the indicator function of d-dimensional ball](https://mlsanity.com/paper/2304.08172/) (2023)
- [Model-free filtering in high dimensions via projection and score-based diffusions](https://mlsanity.com/paper/2510.23197/) (2025)
- [Provable Target Sample Complexity Improvements as Pre-Trained Models Scale](https://mlsanity.com/paper/2602.04233/) (2026)
- [A Theory of Nonparametric Covariance Function Estimation for Discretely Observed Data](https://mlsanity.com/paper/2603.23302/) (2026)
- [Provable Data Scaling Law for Meta Learning via Complexity Minimization](https://mlsanity.com/paper/2606.02008/) (2026)

## Abstract (arXiv)

Deep learning has been applied to various tasks in the field of machine learning and has shown superiority to other common procedures such as kernel methods. To provide a better theoretical understanding of the reasons for its success, we discuss the performance of deep learning and other methods on a nonparametric regression problem with a Gaussian noise. Whereas existing theoretical studies of deep learning have been based mainly on mathematical theories of well-known function classes such as H"older and Besov classes, we focus on function classes with discontinuity and sparsity, which are those naturally assumed in practice. To highlight the effectiveness of deep learning, we compare deep learning with a class of linear estimators representative of a class of shallow estimators. It is shown that the minimax risk of a linear estimator on the convex hull of a target function class does not differ from that of the original target function class. This results in the suboptimality of linear methods over a simple but non-convex function class, on which deep learning can attain nearly the minimax-optimal rate. In addition to this extreme case, we consider function classes with sparse wavelet coefficients. On these function classes, deep learning also attains the minimax rate up to log factors of the sample size, and linear methods are still suboptimal if the assumed sparsity is strong. We also point out that the parameter sharing of deep neural networks can remarkably reduce the complexity of the model in our setting.