Absolute error bounds for learning linear functions online

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Absolute error bounds for learning linear functions online

Full text

Pdf (361 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: 160 - 163

Year of Publication: 1992

ISBN:0-89791-497-X

Author

Ethan J. Bernstein

Computer Science Division, University of California, Berkeley, Berkeley, 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): 14, Downloads (12 Months): 33, Citation Count: 2

Additional Information:

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

ABSTRACT

In this note, we consider the problem of learning a linear function from ** to ** online. Two previous algorithms have been presented which achieve an optimal sum of squared error terms. We show that neither algorithm performs well with respect to absolute error. We also show that in both problem settings, very simple ideas given an algorithm which achieves optimal or close to optimal worst case absolute error.

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.

	LLW91a	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]
	LLW91b	Nicholas Littlestone , Philip M. Long , Manfred K. Warmuth, ON-LINE LEARNING OF LINEAR FUNCTIONS, University of California at Santa Cruz, Santa Cruz, CA, 1991
	Myc88	J. Mycielski. A learning algorithm for linear operators. Proceedi~gs of the Amertca~ Mathe,lat~cal ,S'oc~ety, 103(2):54T-550, 1988.

CITED BY 2

	Norbert Klasner , Hans Ulrich Simon, From noise-free to noise-tolerant and from on-line to batch learning, Proceedings of the eighth annual conference on Computational learning theory, p.250-257, July 05-08, 1995, Santa Cruz, California, United States
	Philip M. Long, On-line evaluation and prediction using linear functions, Proceedings of the tenth annual conference on Computational learning theory, p.21-31, July 06-09, 1997, Nashville, Tennessee, United States