On the complexity of function learning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of function learning

Full text

Pdf (1.03 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the sixth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 392 - 401

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Peter Auer
Philip M. Long
Wolfgang Maass
Gerhard J. Woeginger

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 34, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/168304.168384 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AL93	P. Auer and P.M. Long. Learning without explanations nearly as well as with them, 1993. Manuscript.
	Ang88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	Bar92	I. Barl,md. Some ideas on learning with directional feedback. Master's thesis, UC Santa Crus, June 1992.
	Ber68	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.
	CFHW93	N. Cesa-Bianchi, Y. Freund, D. Helmhold, and M.K. Warmuth. On-line prediction and conversion strategies. Manuscript, 1993.
	ES92	P. Erd'66 and J. Spencer. Probabilistic methods in computer science. Academic Press, New York, 1992.
	FM91	V. Faber and J. Mycielski. Applications of learning theorems. Fundamenta {nformaticae, 15(2):145-167, 1991.
	KL92	Don Kimber , Philip M. Long, The learning complexity of smooth functions of a single variable, Proceedings of the fifth annual workshop on Computational learning theory, p.153-159, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130402]
	KSS92	Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130424]
	Lit88	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	LLW91	Nicholas Littlestone , Philip M. Long , Manfred K. Warmuth, On-line learning of linear functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.465-475, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103467]
	LW91	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.
	LW93	Philip M. Long , Manfred K. Warmuth, Composite geometric concepts and polynomial predictability, Information and Computation, v.113 n.2, p.230-252, Sept. 1994 [doi>10.1006/inco.1994.1071]
	Maa91	Wolfgang Maass, On-line learning with an oblivious environment and the power of randomization, Proceedings of the fourth annual workshop on Computational learning theory, p.167-178, August 05-07, 1991, Santa Cruz, California, United States
	MT92	Wolfgang Maass , György Turán, Lower Bound Methods and Separation Results for On-Line Learning Models, Machine Learning, v.9 n.2-3, p.107-145, July 1992 [doi>10.1007/BF00992674]
	Myc88	J. Mycielski. A learning algorithm for linear operators. Proceedings of the American Mathematical Society, 103(2):547-550, 1988.
	RMK+80	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.
	Spe92	Joel Spencer, Ulam's searching game with a fixed number of lies, Theoretical Computer Science, v.95 n.2, p.307-321, March 30, 1992 [doi>10.1016/0304-3975(92)90270-P]
	Usp48	J.V. Uspensky. Theory of Equations. McGraw-Hill, 1948.

CITED BY 2

	Peter L. Bartlett , Philip M. Long , Robert C. Williamson, Fat-shattering and the learnability of real-valued functions, Proceedings of the seventh annual conference on Computational learning theory, p.299-310, July 12-15, 1994, New Brunswick, New Jersey, United States
	Peter Auer , Philip M. Long, Simulating access to hidden information while learning, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.263-272, May 23-25, 1994, Montreal, Quebec, Canada