On the mathematical foundations of learning

Cucker, Felipe; Smale, Steve

doi:10.1090/S0273-0979-01-00923-5

On the mathematical foundations of learning
HTML articles powered by AMS MathViewer

by Felipe Cucker and Steve Smale PDF

Bull. Amer. Math. Soc. 39 (2002), 1-49 Request permission

References

Lars V. Ahlfors, Complex analysis, 3rd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York, 1978. An introduction to the theory of analytic functions of one complex variable. MR 510197
P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
Andrew R. Barron, Complexity regularization with application to artificial neural networks, Nonparametric functional estimation and related topics (Spetses, 1990) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 335, Kluwer Acad. Publ., Dordrecht, 1991, pp. 561–576. MR 1154352
Jöran Bergh and Jörgen Löfström, Interpolation spaces. An introduction, Grundlehren der Mathematischen Wissenschaften, No. 223, Springer-Verlag, Berlin-New York, 1976. MR 0482275, DOI 10.1007/978-3-642-66451-9
M. Š. Birman and M. Z. Solomjak, Piecewise polynomial approximations of functions of classes $W_{p}{}^{\alpha }$, Mat. Sb. (N.S.) 73 (115) (1967), 331–355 (Russian). MR 0217487
Christopher M. Bishop, Neural networks for pattern recognition, The Clarendon Press, Oxford University Press, New York, 1995. With a foreword by Geoffrey Hinton. MR 1385195
Åke Björck, Numerical methods for least squares problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1386889, DOI 10.1137/1.9781611971484
Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636, DOI 10.1007/978-1-4612-0701-6
Bernd Carl and Irmtraud Stephani, Entropy, compactness and the approximation of operators, Cambridge Tracts in Mathematics, vol. 98, Cambridge University Press, Cambridge, 1990. MR 1098497, DOI 10.1017/CBO9780511897467
Peter Craven and Grace Wahba, Smoothing noisy data with spline functions. Estimating the correct degree of smoothing by the method of generalized cross-validation, Numer. Math. 31 (1978/79), no. 4, 377–403. MR 516581, DOI 10.1007/BF01404567
M. J. Donahue, L. Gurvits, C. Darken, and E. Sontag, Rates of convex approximation in non-Hilbert spaces, Constr. Approx. 13 (1997), no. 2, 187–220. MR 1437210, DOI 10.1007/s003659900038
Lokenath Debnath and Piotr Mikusiński, Introduction to Hilbert spaces with applications, 2nd ed., Academic Press, Inc., San Diego, CA, 1999. MR 1670332
J. P. Dedieu and M. Shub, Newton’s method for overdetermined systems of equations, Math. Comp. 69 (2000), no. 231, 1099–1115. MR 1651750, DOI 10.1090/S0025-5718-99-01115-1
Ronald A. DeVore and George G. Lorentz, Constructive approximation, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 303, Springer-Verlag, Berlin, 1993. MR 1261635, DOI 10.1007/978-3-662-02888-9
Jean Duchon, Splines minimizing rotation-invariant semi-norms in Sobolev spaces, Constructive theory of functions of several variables (Proc. Conf., Math. Res. Inst., Oberwolfach, 1976) Lecture Notes in Math., Vol. 571, Springer, Berlin, 1977, pp. 85–100. MR 0493110
D. E. Edmunds and H. Triebel, Function spaces, entropy numbers, differential operators, Cambridge Tracts in Mathematics, vol. 120, Cambridge University Press, Cambridge, 1996. MR 1410258, DOI 10.1017/CBO9780511662201
Theodoros Evgeniou, Massimiliano Pontil, and Tomaso Poggio, Regularization networks and support vector machines, Adv. Comput. Math. 13 (2000), no. 1, 1–50. MR 1759187, DOI 10.1023/A:1018946025316
David Haussler, Decision-theoretic generalizations of the PAC model for neural net and other learning applications, Inform. and Comput. 100 (1992), no. 1, 78–150. MR 1175977, DOI 10.1016/0890-5401(92)90010-D
Harry Hochstadt, Integral equations, Pure and Applied Mathematics, John Wiley & Sons, New York-London-Sydney, 1973. MR 0390680
A. N. Kolmogorov and S. V. Fomīn, Introductory real analysis, Dover Publications, Inc., New York, 1975. Translated from the second Russian edition and edited by Richard A. Silverman; Corrected reprinting. MR 0377445
A. N. Kolmogorov and V. M. Tihomirov, $\varepsilon$-entropy and $\varepsilon$-capacity of sets in function spaces, Uspehi Mat. Nauk 14 (1959), no. 2 (86), 3–86 (Russian). MR 0112032
Wee Sun Lee, Peter L. Bartlett, and Robert C. Williamson, The importance of convexity in learning with squared loss, IEEE Trans. Inform. Theory 44 (1998), no. 5, 1974–1980. MR 1664079, DOI 10.1109/18.705577
Peter Li and Shing-Tung Yau, On the parabolic kernel of the Schrödinger operator, Acta Math. 156 (1986), no. 3-4, 153–201. MR 834612, DOI 10.1007/BF02399203
George G. Lorentz, Manfred v. Golitschek, and Yuly Makovoz, Constructive approximation, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 304, Springer-Verlag, Berlin, 1996. Advanced problems. MR 1393437, DOI 10.1007/978-3-642-60932-9
Albert Eagle, Series for all the roots of the equation $(z-a)^m=k(z-b)^n$, Amer. Math. Monthly 46 (1939), 425–428. MR 6, DOI 10.2307/2303037
Jean Meinguet, Multivariate interpolation at arbitrary points made simple, Z. Angew. Math. Phys. 30 (1979), no. 2, 292–304 (English, with French summary). MR 535987, DOI 10.1007/BF01601941

Perceptrons

The informational complexity of learning

A. Pietsch, Eigenvalues and $s$-numbers, Mathematik und ihre Anwendungen in Physik und Technik [Mathematics and its Applications in Physics and Technology], vol. 43, Akademische Verlagsgesellschaft Geest & Portig K.-G., Leipzig, 1987. MR 917067
Allan Pinkus, $n$-widths in approximation theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 7, Springer-Verlag, Berlin, 1985. MR 774404, DOI 10.1007/978-3-642-69894-1

Machine learning, machine vision, and the brain

20

David Pollard, Convergence of stochastic processes, Springer Series in Statistics, Springer-Verlag, New York, 1984. MR 762984, DOI 10.1007/978-1-4612-5254-2

Partial differential equations vii: Spectral theory of differential operators

Metric spaces and completely monotone functions

39

Igor R. Shafarevich, Basic algebraic geometry. 1, 2nd ed., Springer-Verlag, Berlin, 1994. Varieties in projective space; Translated from the 1988 Russian edition and with notes by Miles Reid. MR 1328833
G. A. Miller, Groups which contain ten or eleven proper subgroups, Proc. Nat. Acad. Sci. U.S.A. 25 (1939), 540–543. MR 31, DOI 10.1073/pnas.25.10.540

Mathematical problems for the next century

Estimating the approximation error in learning theory

Michael E. Taylor, Partial differential equations, Texts in Applied Mathematics, vol. 23, Springer-Verlag, New York, 1996. Basic theory. MR 1395147, DOI 10.1007/978-1-4684-9320-7

A theory of the learnable

27

Empirical processes in m-estimation

Vladimir N. Vapnik, Statistical learning theory, Adaptive and Learning Systems for Signal Processing, Communications, and Control, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. MR 1641250

Intelligent production machines: benefiting from synergy amongst modelling, sensing and learning

Estimation of the complexity of the tabulation problem

Theory of the Transmission and Processing of the Information

Grace Wahba, Spline models for observational data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442, DOI 10.1137/1.9781611970128

Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators