The learning complexity of smooth functions of a single variable

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The learning complexity of smooth functions of a single variable

Full text

Pdf (589 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the fifth annual workshop on Computational learning theory table of contents

Pittsburgh, Pennsylvania, United States

Pages: 153 - 159

Year of Publication: 1992

ISBN:0-89791-497-X

Authors

Don Kimber	Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA
Philip M. Long	Computer Science Department, UC Santa Cruz, Santa Cruz, CA

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): 1, Downloads (12 Months): 10, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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/130385.130402 What is a DOI?

ABSTRACT

We study the on-line learning of classes of functions of a single real variable formed through bounds on various norms of functions' derivatives. We determine the best bounds obtainable on the worst-case sum of squared errors (also “absolute” errors) for several such classes.

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.

	Bar91	A. R. Barron, Approximation and estimation bounds for artificial neural networks, Proceedings of the fourth annual workshop on Computational learning theory, p.243-249, August 05-07, 1991, Santa Cruz, California, United States
	FM91	V. Faber and J. Mycielski. Applications of learning theorems. Fundamenia Informaticae, 15(2):145-167, 1991.
	Har91	W. Hardle. Smoothing Techniques. Springer Verlag, 1991.
	Hau89	D. Haussler. Generalizing the PAC model: sample size bounds from metric dimensionbased uniform convergence results. Proceedings of the 30th Annual Symposium on the Foundations of Computer Science, 1989.
	Lei81	G. Leitmann. The Calculus of Variations and Optimal Control. Plenum Press, 1981.
	Lit89	N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
	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]
	LW89	N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Proceedings of the 30th Annual Symposium on the Foundations of Computer Science, 1989.
	MT89	W. Maass and G. Turan. On the complexity of learning from counterexamples. Proceedings of the 30th Annual Symposium on the Foundations of Computer Science, 1989.
	Myc88	J. Mycielski. A learning algorithm for linear operators. Proceedings of the American Mathematical Society, 103(2):547-550, 1988.
	WH60	B. Widrow and M.E. Hoff. Adaptive switching circuits. 1960 IRE WESCON Cony. Record, pages 96-104, 1960.

CITED BY 3

	S. E. Posner , S. R. Kulkarni, On-line learning of functions of bounded variation under various sampling schemes, Proceedings of the sixth annual conference on Computational learning theory, p.439-445, July 26-28, 1993, Santa Cruz, California, United States
	Nicolò Cesa Bianchi , Philip M. Long , Manfred K. Warmuth, Worst-case quadratic loss bounds for a generalization of the Widrow-Hoff rule, Proceedings of the sixth annual conference on Computational learning theory, p.429-438, July 26-28, 1993, Santa Cruz, California, United States
	Peter Auer , Philip M. Long , Wolfgang Maass , Gerhard J. Woeginger, On the complexity of function learning, Proceedings of the sixth annual conference on Computational learning theory, p.392-401, July 26-28, 1993, Santa Cruz, California, United States