# Optimal Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 46 references that are in the map.
- First posted on arXiv 30 Mar 2022.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Finite Depth and Width Corrections to the Neural Tangent Kernel](https://mlsanity.com/paper/1909.05989/) (2019)
- [Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networks](https://mlsanity.com/paper/2101.12365/) (2021)
- [Characterization of the Variation Spaces Corresponding to Shallow Neural Networks](https://mlsanity.com/paper/2106.15002/) (2021)
- [The Barron Space and the Flow-induced Function Spaces for Neural Network Models](https://mlsanity.com/paper/1906.08039/) (2019)
- [A unifying representer theorem for inverse problems and machine learning](https://mlsanity.com/paper/1903.00687/) (2019)
- [Deep Neural Networks Are Effective At Learning High-Dimensional Hilbert-Valued Functions From Limited Data](https://mlsanity.com/paper/2012.06081/) (2020)
- [Optimal learning of high-dimensional classification problems using deep neural networks](https://mlsanity.com/paper/2112.12555/) (2021)

## Abstract (arXiv)

This paper studies the problem of learning an unknown function f from given data about f. The learning problem is to give an approximation hat f to f that predicts the values of f away from the data. There are numerous settings for this learning problem depending on (i) what additional information we have about f (known as a model class assumption), (ii) how we measure the accuracy of how well hat f predicts f, (iii) what is known about the data and data sites, (iv) whether the data observations are polluted by noise. A mathematical description of the optimal performance possible (the smallest possible error of recovery) is known in the presence of a model class assumption. Under standard model class assumptions, it is shown in this paper that a near optimal hat f can be found by solving a certain discrete over-parameterized optimization problem with a penalty term. Here, near optimal means that the error is bounded by a fixed constant times the optimal error. This explains the advantage of over-parameterization which is commonly used in modern machine learning. The main results of this paper prove that over-parameterized learning with an appropriate loss function gives a near optimal approximation hat f of the function f from which the data is collected. Quantitative bounds are given for how much over-parameterization needs to be employed and how the penalization needs to be scaled in order to guarantee a near optimal recovery of f. An extension of these results to the case where the data is polluted by additive deterministic noise is also given.