Wide and Deep Neural Networks Achieve Optimality for Classification

Abstract

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.

References in corpus (22)

• Language Models are Few-Shot Learners
• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• Deep Neural Networks as Gaussian Processes
• On Exact Computation with an Infinitely Wide Neural Net
• Exponential expressivity in deep neural networks through transient chaos
• Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent
• On the Impact of the Activation Function on Deep Neural Networks Training
• Does data interpolation contradict statistical optimality?
• Neural Tangents: Fast and Easy Infinite Neural Networks in Python
• On the linearity of large non-linear models: when and why the tangent kernel is constant
• Finite Versus Infinite Neural Networks: an Empirical Study
• Dynamical Isometry and a Mean Field Theory of CNNs: How to Train 10,000-Layer Vanilla Convolutional Neural Networks
• Mean Field Residual Networks: On the Edge of Chaos
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks
• Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
• On the Similarity between the Laplace and Neural Tangent Kernels
• Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon
• Increasing Depth Leads to U-Shaped Test Risk in Over-parameterized Convolutional Networks
• Deep Networks Provably Classify Data on Curves

Cited by in corpus (1)

• Deep Minimax Classifiers for Imbalanced Datasets with a Small Number of Minority Samples