Article

Free access

On the complexity of function learning

Authors:

Peter Auer,

Philip M. Long,

Wolfgang Maass,

Gerhard J. WoegingerAuthors Info & Claims

COLT '93: Proceedings of the sixth annual conference on Computational learning theory

Pages 392 - 401

https://doi.org/10.1145/168304.168384

Published: 01 August 1993 Publication History

PDF eReader

References

[1]

P. Auer and P.M. Long. Learning without explanations nearly as well as with them, 1993. Manuscript.

Google Scholar

[2]

D. Angluin. Queries and concept learning. Machine Learning, 2:319-342, 1988.

Digital Library

Google Scholar

[3]

I. Barl,md. Some ideas on learning with directional feedback. Master's thesis, UC Santa Crus, June 1992.

Google Scholar

[4]

E. It. Berlekamp. Error Correcting Codes, chapter Block coding for the binary symmetric channel with noiseless, delayless feedback, pages 61-85. Wiley, New York, 1968.

Google Scholar

[5]

N. Cesa-Bianchi, Y. Freund, D. Helmhold, and M.K. Warmuth. On-line prediction and conversion strategies. Manuscript, 1993.

Google Scholar

[6]

P. Erd'66 and J. Spencer. Probabilistic methods in computer science. Academic Press, New York, 1992.

Google Scholar

[7]

V. Faber and J. Mycielski. Applications of learning theorems. Fundamenta {nformaticae, 15(2):145-167, 1991.

Google Scholar

[8]

D. Kimber and P.M. Long. The learning complexity of smooth functions of a single variable. The 199~ Workshop on Computational Learning Theory, pages 153-159, 1992.

Digital Library

Google Scholar

[9]

M.J. Kearns, R.E. Schapire, and L.M. Sellie. Toward efficient agnostic learning. The I99~ Workshop on Computational Learning Theory, pages 341-352, 1992.

Digital Library

Google Scholar

[10]

N. Littlestone. Learning quickly when irrelevant attributes abound: a new linearthreshold algorithm. Machine Learning, 2:285-318, 1988.

Digital Library

Google Scholar

[11]

N. Littlestone, P.M. Long, and M.K. Warmuth. On-line learning of linear functions. Proceedings of the ~3rd ACM Symposium on the Theory of Computation, pages 465-475, 1991.

Digital Library

Google Scholar

[12]

N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Technical Report UCSC-CRL-91-28, UC Santa Cruz, October 1991. A preliminary version appeared in the Proceedings of the SOth Annual IEEE Symposium on the Foundations of Computer Science, October 89, pages 256-261.

Digital Library

Google Scholar

[13]

P.M. Long and M. K. Warmuth. Composite geometric concepts and polynomial predictability. Information and Computation, 1993. To appear.

Digital Library

Google Scholar

[14]

W. Maazs. On-line learning with an oblivious environment and the power of randomization. The 1991 Workshop on Computational Learning Theory, pages 167-175, 1991.

Digital Library

Google Scholar

[15]

W. Maass and G. Turin. Lower bound methods and separation results for on-line learning models. Machine Learning, 9:107- 145, 1992.

Digital Library

Google Scholar

[16]

J. Mycielski. A learning algorithm for linear operators. Proceedings of the American Mathematical Society, 103(2):547-550, 1988.

Crossref

Google Scholar

[17]

R.L. Rivest, A.R. Meyer, D.J. Kleitman, K. Winklmann, and J. Spencer. Coping with errors in binary search procedures. Journal of Computer and System Sciences, 20:396-404, 1980.

Crossref

Google Scholar

[18]

J. Spencer. Ulam's searching game with a fixed number of lies. Theoretical Computer Science, 95(2):307-321, 1992.

Digital Library

Google Scholar

[19]

J.V. Uspensky. Theory of Equations. McGraw-Hill, 1948.

Google Scholar

Cited By

View all

Bartlett PLong PWilliamson R(1996)Fat-Shattering and the Learnability of Real-Valued FunctionsJournal of Computer and System Sciences10.1006/jcss.1996.003352:3(434-452)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1006/jcss.1996.0033
Auer PLong PMaass WWoeginger G(1995)On the Complexity of Function LearningMachine Language10.1007/BF0099341018:2-3(187-230)Online publication date: 1-Feb-1995
https://dl.acm.org/doi/10.1007/BF00993410
Auer PLong PLeighton FGoodrich M(1994)Simulating access to hidden information while learningProceedings of the twenty-sixth annual ACM symposium on Theory of Computing10.1145/195058.195152(263-272)Online publication date: 23-May-1994
https://dl.acm.org/doi/10.1145/195058.195152
Show More Cited By

Index Terms

On the complexity of function learning
1. Computing methodologies
  1. Machine learning
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees

Recommendations

Learning-Based Complexity Evaluation of Radial Basis Function Networks

Recently, the complexity control of dynamic neural models has gained significant attention. The performance of such a process depends highly on the applied definition of ‘model complexity’. On the other hand, the learning theory creates a framework to ...
Radial basis function networks and complexity regularization in function learning

We apply the method of complexity regularization to derive estimation bounds for nonlinear function estimation using a single hidden layer radial basis function network. Our approach differs from previous complexity regularization neural-network ...
Radial basis function networks and complexity regularization in function learning
NIPS'96: Proceedings of the 9th International Conference on Neural Information Processing Systems

In this paper we apply the method of complexity regularization to derive estimation bounds for nonlinear function estimation using a single hidden layer radial basis function network. Our approach differs from the previous complexity regularization ...

Comments

Information & Contributors

Information

Published In

COLT '93: Proceedings of the sixth annual conference on Computational learning theory

August 1993

463 pages

ISBN:0897916115

DOI:10.1145/168304

Editor:
Lenny Pitt
Univ. of Illinois, Urbana

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

6COLT93

Sponsor:

6COLT93: 6th Annual Conference on Computational Learning Theory

July 26 - 28, 1993

California, Santa Cruz, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
202
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)8

Reflects downloads up to 13 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bartlett PLong PWilliamson R(1996)Fat-Shattering and the Learnability of Real-Valued FunctionsJournal of Computer and System Sciences10.1006/jcss.1996.003352:3(434-452)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1006/jcss.1996.0033
Auer PLong PMaass WWoeginger G(1995)On the Complexity of Function LearningMachine Language10.1007/BF0099341018:2-3(187-230)Online publication date: 1-Feb-1995
https://dl.acm.org/doi/10.1007/BF00993410
Auer PLong PLeighton FGoodrich M(1994)Simulating access to hidden information while learningProceedings of the twenty-sixth annual ACM symposium on Theory of Computing10.1145/195058.195152(263-272)Online publication date: 23-May-1994
https://dl.acm.org/doi/10.1145/195058.195152
Bartlett PLong PWilliamson RWarmuth M(1994)Fat-shattering and the learnability of real-valued functionsProceedings of the seventh annual conference on Computational learning theory10.1145/180139.181158(299-310)Online publication date: 16-Jul-1994
https://dl.acm.org/doi/10.1145/180139.181158

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Learning-Based Complexity Evaluation of Radial Basis Function Networks

Radial basis function networks and complexity regularization in function learning

Radial basis function networks and complexity regularization in function learning

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF

eReader

Login options

Full Access

References

Cited By

Index Terms

Recommendations

Learning-Based Complexity Evaluation of Radial Basis Function Networks

Radial basis function networks and complexity regularization in function learning

Radial basis function networks and complexity regularization in function learning

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations