# Wide and Deep Neural Networks Achieve Optimality for Classification

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 51 references that are in the map.
- First posted on arXiv 29 Apr 2022.

## Builds on (most cited first, 30 of 33)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Exponential expressivity in deep neural networks through transient chaos](https://mlsanity.com/paper/1606.05340/) (2016)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Dynamical Isometry and a Mean Field Theory of CNNs: How to Train 10,000-Layer Vanilla Convolutional Neural Networks](https://mlsanity.com/paper/1806.05393/) (2018)
- [The Principles of Deep Learning Theory](https://mlsanity.com/paper/2106.10165/) (2021)
- [Finite Versus Infinite Neural Networks: an Empirical Study](https://mlsanity.com/paper/2007.15801/) (2020)
- [Neural Tangents: Fast and Easy Infinite Neural Networks in Python](https://mlsanity.com/paper/1912.02803/) (2019)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [On the linearity of large non-linear models: when and why the tangent kernel is constant](https://mlsanity.com/paper/2010.01092/) (2020)
- [On the Impact of the Activation Function on Deep Neural Networks Training](https://mlsanity.com/paper/1902.06853/) (2019)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks](https://mlsanity.com/paper/1910.01663/) (2019)
- [Mean Field Residual Networks: On the Edge of Chaos](https://mlsanity.com/paper/1712.08969/) (2017)
- [On the Similarity between the Laplace and Neural Tangent Kernels](https://mlsanity.com/paper/2007.01580/) (2020)
- [Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective](https://mlsanity.com/paper/2002.06262/) (2020)
- [Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon](https://mlsanity.com/paper/1812.11167/) (2018)
- [Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks](https://mlsanity.com/paper/2108.00131/) (2021)
- [Disentangling Trainability and Generalization in Deep Neural Networks](https://mlsanity.com/paper/1912.13053/) (2019)
- [Activation function design for deep networks: linearity and effective initialisation](https://mlsanity.com/paper/2105.07741/) (2021)

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

- [A prediction rigidity formalism for low-cost uncertainties in trained neural networks](https://mlsanity.com/paper/2403.02251/) (2024)
- [From Complexity to Clarity: Analytical Expressions of Deep Neural Network Weights via Clifford's Geometric Algebra and Convexity](https://mlsanity.com/paper/2309.16512/) (2023)
- [Can sparse autoencoders make sense of gene expression latent variable models?](https://mlsanity.com/paper/2410.11468/) (2024)
- [Can predictive models be used for causal inference?](https://mlsanity.com/paper/2306.10551/) (2023)
- [Beyond Benign Overfitting in Nadaraya-Watson Interpolators](https://mlsanity.com/paper/2502.07480/) (2025)
- [Ensemble Multi-Quantiles: Adaptively Flexible Distribution Prediction for Uncertainty Quantification](https://mlsanity.com/paper/2211.14545/) (2022)
- [Universal Consistency of Wide and Deep ReLU Neural Networks and Minimax Optimal Convergence Rates for Kolmogorov-Donoho Optimal Function Classes](https://mlsanity.com/paper/2401.04286/) (2024)
- [Classifying Overlapping Gaussian Mixtures in High Dimensions: From Optimal Classifiers to Neural Nets](https://mlsanity.com/paper/2405.18427/) (2024)
- [Generalization bounds for regression and classification on adaptive covering input domains](https://mlsanity.com/paper/2407.19715/) (2024)
- [Deep Minimax Classifiers for Imbalanced Datasets with a Small Number of Minority Samples](https://mlsanity.com/paper/2502.16948/) (2025)
- [Asymptotic convexity of wide and shallow neural networks](https://mlsanity.com/paper/2507.01044/) (2025)
- [Hamiltonian Graph Inference Networks: Joint structure discovery and dynamics prediction for lattice Hamiltonian systems from trajectory data](https://mlsanity.com/paper/2604.23606/) (2026)

## Abstract (arXiv)

While neural networks are used for classification tasks across domains, a long-standing open problem in machine learning is determining whether neural networks trained using standard procedures are optimal for classification, i.e., whether such models minimize the probability of misclassification for arbitrary data distributions. In this work, we identify and construct an explicit set of neural network classifiers that achieve optimality. Since effective neural networks in practice are typically both wide and deep, we analyze infinitely wide networks that are also infinitely deep. In particular, using the recent connection between infinitely wide neural networks and Neural Tangent Kernels, we provide explicit activation functions that can be used to construct networks that achieve optimality. Interestingly, these activation functions are simple and easy to implement, yet differ from commonly used activations such as ReLU or sigmoid. More generally, we create a taxonomy of infinitely wide and deep networks and show that these models implement one of three well-known classifiers depending on the activation function used: (1) 1-nearest neighbor (model predictions are given by the label of the nearest training example); (2) majority vote (model predictions are given by the label of the class with greatest representation in the training set); or (3) singular kernel classifiers (a set of classifiers containing those that achieve optimality). Our results highlight the benefit of using deep networks for classification tasks, in contrast to regression tasks, where excessive depth is harmful.