On the mathematical foundations of learning

By Felipe Cucker, Steve Smale. 2001

1,745 citations recorded by the source corpus.

(1) A main theme of this report is the relationship of approximation to learning and the primary role of sampling (inductive inference). We try to emphasize relations of the theory of learning to the mainstream of mathematics. In particular, there are large roles for probability theory, for algorithms such as least squares, and for tools and ideas from linear algebra and linear analysis. An advantage of doing this is that communication is facilitated and the power of core mathematics is more easily brought to bear. We illustrate what we mean by learning theory by giving some instances. (a) The understanding of language acquisition by children or the emergence of languages in early human cultures. (b) In Manufacturing Engineering, the design of a new wave of machines is anticipated which uses sensors to sample properties of objects before, during, and after treatment. The information gathered from these samples is to be analyzed by the machine to decide how to better deal with new input objects (see [43]). (c) Pattern recognition of objects ranging from handwritten letters of the alphabet to pictures of animals, to the human voice. Understanding the laws of learning plays a large role in disciplines such as (Cognitive) Psychology, Animal Behavior, Economic Decision Making, all branches of Engineering, Computer Science, and especially the study of human thought processes (how the brain works). Mathematics has already played a big role towards the goal of giving a universal foundation of studies in these disciplines. We mention as examples the theory of Neural Networks going back to McCulloch and Pitts [25] and Minsky and Papert [27], the PAC learning of Valiant [40], Statistical Learning Theory as developed by Vapnik [42], and the use of reproducing kernels as in [17] among many other mathematical developments. We are heavily indebted to these developments. Recent discussions with a number of mathematicians have also been helpful. In

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistical Learning Theory

Citations in the corpus

On the Equivalence between Herding and Conditional Gradient Algorithms (2012, neutral): “Moreover, ( λ 1 / 2 k e k ) k > 1 is known to be an orthonormal basis of the associated feature space F (Cucker & Smale, 2002), and for all x, y ∈ X , ˜ k ( x, y ) = k > 1 λ k e k ( x ) e k ( y ), with uniform convergence.”
Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “Readers who are interested particularly in the typical applications of kernels in machine learning, e.g., support vector machines (SVMs) and Gaussian processes (GPs), are encouraged to read Cucker and Smale (2002), Burges (1998), Rasmussen and Williams (2005) and references therein.”
Generalization in anti-causal learning (2018, background): “Statistical learning theory provides a rigorous framework describing when learning is possible (Vapnik, 1998; Cucker and Smale, 2002).”
On the Error of Random Fourier Features (2015, background): “It’s compact, with diameter at most 2 (cid:96) , so we can ﬁnd an ε -net covering X ∆ with at most T = (4 (cid:96)/r ) d balls of radius r (Cucker and Smale 2001, Proposition 5).”
On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, background): “(1), it is natural to consider sampling n elements v 1 , . . . , v n ∈ V from the distribution dτ and deﬁne the kernel approximation which deﬁnes a ﬁnite-dimensional RKHS ˆ F .”
Kernel Mean Shrinkage Estimators (2014, methodology): “of the integral operator Tk induced by the kernel kand the approximation properties of H. This link has been extensively used for the analysis of some state-of-the-art learning algorithms, see, e.g., Cucker and Smale (2002); Mendelson and Neeman (2010) and references therein, and will prove helpful ”
Random Feature Maps for Dot Product Kernels (2012, methodology): “Obtain the Maclaurin expansion of f d selecting each coordinate using fair coin tosses.”
Kernels for Vector-Valued Functions: a Review (2011, background): “This latter concept plays a key role, so we review a few essential concepts (see [87, 6, 105, 25]).”
Estimating Divergence Functionals and the Likelihood Ratio by Convex Risk Minimization (2008, methodology): “It was shown that the RKHS can be embedded in a Sobolev space of smoothness α > d/2 (Cucker and Smale, 2001), thus we should also obtain √ n-estimation error rate. For the Gaussian kernel, it was shown by Zhou (2002) that the entropy number for F is much smaller, i.”
On Invariance and Selectivity in Representation Learning (2015, background): “The sample complexity can be shown [13,39] to be proportional to the logarithm of the covering number, i.”
VECTOR VALUED REPRODUCING KERNEL HILBERT SPACES OF INTEGRABLE FUNCTIONS AND MERCER THEOREM (2006, background): “Extensions of the Mercer theorem can be found in [9, 27, 20] and references therein.”
Quasi-oracle estimation of heterogeneous treatment effects (2017, background): “…that have been thoroughly studied in the statistical learning literature (see, e.g., Bartlett and Mendelson, 2006; Caponnetto and De Vito, 2007; Cucker and Smale, 2002; Steinwart and Christmann, 2008; Mendelson and Neeman, 2010), and thus provides an ideal case study for highlighting the…”
Greedy approximation (2008, methodology): “results on σm(F, T )p and Gm(F, T )p for different classes F in DeVore and Temlyakov (1995) and Temlyakov (1998c, 2000a, 2002a).”
Learning Deep Kernels for Non-Parametric Two-Sample Tests (2020, methodology): “…we place T points { ω i } Ti =1 such that for any point ω ∈ Ω , min i (cid:107) ω − ω i (cid:107) ≤ q ; Assumption ( B ) ensures this is possible with at most T = (4 R Ω /q ) D points (Cucker & Smale, 2001, Proposition 5). i (cid:54) = j H ij , and via Assumption ( A ) we know | H ij | ≤ 4 ν .”
Unsupervised learning of invariant representations with low sample complexity: the magic of sensory cortex or a new framework for machine learning? (2013, background): “[36] Under certain conditions (in particular, the Heisenberg boxes associated with each wavelet must together cover the space-frequency plane) the Gabor wavelet family becomes a Gabor wavelet frame.”