Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



On the mathematical foundations of learning

Authors: Felipe Cucker and Steve Smale
Journal: Bull. Amer. Math. Soc. 39 (2002), 1-49
MSC (2000): Primary 68T05, 68P30
Published electronically: October 5, 2001
MathSciNet review: 1864085
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • 1. L.V. Ahlfors, Complex analysis, 3rd ed., McGraw-Hill, 1978. MR 80c:30001
  • 2. N. Aronszajn, Theory of reproducing kernels, Transactions of the Amer. Math. Soc.68 (1950), 337-404. MR 14:479c
  • 3. A.R. Barron, Complexity regularization with applications to artificial neural networks, Nonparametric Functional Estimation (G. Roussa, ed.), Kluwer, Dordrecht, 1990, pp. 561-576. MR 93b:62052
  • 4. J. Bergh and J. Löfström, Interpolation spaces. an introduction, Springer-Verlag, 1976. MR 58:2349
  • 5. M.S. Birman and M.Z. Solomyak, Piecewise polynomial approximations of functions of the classes ${W}^\alpha_p$, Mat. Sb. 73 (1967), 331-355; English translation in Math. USSR Sb. (1967), 295-317. MR 36:576
  • 6. C.M. Bishop, Neural networks for pattern recognition, Cambridge University Press, 1995. MR 97m:68172
  • 7. A. Björck, Numerical methods for least squares problems, SIAM, 1996. MR 97g:65004
  • 8. L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer-Verlag, 1998. MR 99a:68070
  • 9. B. Carl and I. Stephani, Entropy, compactness and the approximation of operators, Cambridge University Press, 1990. MR 92e:47002
  • 10. P. Craven and G. Wahba, Smoothing noisy data with spline functions: estimating the correct degree of smoothing by the method of generalized cross-validation, Numer. Math. 31 (1979), 377-403. MR 81g:65018
  • 11. C. Darken, M. Donahue, L. Gurvits, and E. Sontag, Rates of convex approximation in non-Hilbert spaces, Construct. Approx. 13 (1997), 187-220. MR 98c:41051
  • 12. L. Debnath and P. Mikusinski, Introduction to Hilbert spaces with applications, 2nd ed., Academic Press, 1999. MR 99k:46001
  • 13. J.-P. Dedieu and M. Shub, Newton's method for overdetermined systems of equations, Mathematics of Computation 69 (2000), 1099-1115. MR 2000j:65133
  • 14. R.A. DeVore and G.G. Lorentz, Constructive approximation, Grundlehren der mathematischen Wissenschaften, vol. 303, Springer-Verlag, 1993. MR 95f:41001
  • 15. J. Duchon, Spline minimizing rotation-invariant semi-norms in Sobolev spaces, Constructive theory of functions on several variables (W. Schempp and K. Zeller, eds.), Lecture Notes in Math. 571, Springer-Verlag, Berlin, 1977. MR 58:12146
  • 16. D.E. Edmunds and H. Triebel, Function spaces, entropy numbers, differential operators, Cambridge University Press, 1996. MR 97h:46045
  • 17. T. Evgeniou, M. Pontil, and T. Poggio, Regularization Networks and Support Vector Machines, Advances in Computational Mathematics 13 (2000), 1-50. MR 2001f:68053
  • 18. D. Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation 100 (1992), 78-150. MR 93i:68149
  • 19. H. Hochstadt, Integral equations, John Wiley & Sons, 1973. MR 52:11503
  • 20. A.N. Kolmogorov and S.V. Fomin, Introductory real analysis, Dover Publications Inc., 1975. MR 51:13617
  • 21. A.N. Kolmogorov and V.M. Tikhomirov, $\varepsilon$-entropy and $\varepsilon$-capacity of sets in function spaces, Uspecki 14 (1959), 3-86. MR 22:2890
  • 22. W.-S. Lee, P. Bartlett, and R. Williamson, The importance of convexity in learning with squared loss, IEEE Transactions on Information Theory 44 (1998), 1974-1980. MR 99k:68160
  • 23. P. Li and S.-T. Yau, On the parabolic kernel of the Schrödinger operator, Acta Math. 156 (1986), 153-201. MR 87f:58156
  • 24. G.G. Lorentz, M. Golitschek, and Y. Makovoz, Constructive approximation; advanced problems, Springer-Verlag, 1996. MR 97k:41002
  • 25. W.S. McCulloch and W. Pitts, A logical calculus of the ideas immanent in nervous activity, Bulletin of Mathematical Biophysics 5 (1943), 115-133. MR 6:12a
  • 26. J. Meinguet, Multivariate interpolation at arbitrary points made simple, J. Appl. Math. Phys. 30 (1979), 292-304. MR 81e:41014
  • 27. M.L. Minsky and S.A. Papert, Perceptrons, MIT Press, 1969.
  • 28. P. Niyogi, The informational complexity of learning, Kluwer Academic Publishers, 1998.
  • 29. A. Pietsch, Eigenvalues and s-numbers, Cambridge University Press, 1987. MR 88j:47022b
  • 30. A. Pinkus, $N$-widths in approximation theory, Springer-Verlag, New York, 1986. MR 86k:41001
  • 31. T. Poggio and C.R. Shelton, Machine learning, machine vision, and the brain, AI Magazine 20 (1999), 37-55.
  • 32. D. Pollard, Convergence of stochastic processes, Springer-Verlag, 1984. MR 86i:60074
  • 33. G.V. Rozenblum, M.A. Shubin, and M.Z. Solomyak, Partial differential equations vii: Spectral theory of differential operators, Encyclopaedia of Mathematical Sciences, vol. 64, Springer-Verlag, 1994.
  • 34. I.J. Schoenberg, Metric spaces and completely monotone functions, Ann. of Math. 39 (1938), 811-841.
  • 35. I.R. Shafarevich, Basic algebraic geometry, 2nd ed., vol. 1: Varieties in Projective Space, Springer-Verlag, 1994. MR 95m:14001
  • 36. S. Smale, On the Morse index theorem, J. Math. and Mech. 14 (1965), 1049-1056, With a Corrigendum in J. Math. and Mech. 16, 1069-1070, (1967). MR 31:6251; MR 34:5108
  • 37. -, Mathematical problems for the next century, Mathematics: Frontiers and Perspectives (V. Arnold, M. Atiyah, P. Lax, and B. Mazur, eds.), AMS, 2000, pp. 271-294. CMP 2000:13
  • 38. S. Smale and D.-X. Zhou, Estimating the approximation error in learning theory, Preprint, 2001.
  • 39. M.E. Taylor, Partial differential equations i: Basic theory, Applied Mathematical Sciences, vol. 115, Springer-Verlag, 1996. MR 98b:35002b
  • 40. L.G. Valiant, A theory of the learnable, Communications of the ACM27 (1984), 1134-1142.
  • 41. S. van de Geer, Empirical processes in m-estimation, Cambridge University Press, 2000.
  • 42. V. Vapnik, Statistical learning theory, John Wiley & Sons, 1998. MR 99h:62052
  • 43. P. Venuvinod, Intelligent production machines: benefiting from synergy amongst modelling, sensing and learning, Intelligent Production Machines: Myths and Realities, CRC Press LLC, 2000, pp. 215-252.
  • 44. A.G. Vitushkin, Estimation of the complexity of the tabulation problem, Nauka (in Russian), 1959, English Translation appeared as Theory of the Transmission and Processing of the Information, Pergamon Press, 1961.
  • 45. G. Wahba, Spline models for observational data, SIAM, 1990. MR 91g:62028
  • 46. R. Williamson, A. Smola, and B. Schölkopf, Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators, Tech. Report NC2-TR-1998-019, NeuroCOLT2, 1998.

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 68T05, 68P30

Retrieve articles in all journals with MSC (2000): 68T05, 68P30

Additional Information

Felipe Cucker
Affiliation: Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong

Steve Smale
Affiliation: Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong
Address at time of publication: Department of Mathematics, University of California, Berkeley, California 94720

Received by editor(s): April 1, 2000
Received by editor(s) in revised form: June 1, 2001
Published electronically: October 5, 2001
Additional Notes: This work has been substantially funded by CERG grant No. 9040457 and City University grant No. 8780043.
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society