On-line learning of linear functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On-line learning of linear functions

Full text

Pdf (875 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 465 - 475

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Nicholas Littlestone	NEC Research Institute, Princeton, NJ
Philip M. Long	Univ. of California, Santa Cruz
Manfred K. Warmuth	Univ. of California, Santa Cruz

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 22, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/103418.103467 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.

	BHL	A. Blum, L. Hellerstein, and N. Littlestone. Learning in the presence of finitely many or infinitely many irrelevant attributes.Unpublished manuscript. Feb, 1991.
	Bil86	P. Billingsley. Probabilily and Measure. John Wiley and Sons, 1986.
	GL90	G.H. Golub and C.F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 1990.
	Hau88	D. Haussler. Learning conjunctive concepts in structural domains. Technical report, UC Santa Cruz, 1988.
	JM88	Wayne D. Joubert , Thomas A. Manteuffel, Iterative methods for nonsymmetric linear systems, Iterative methods for large linear systems, Academic Press Professional, Inc., San Diego, CA, 1990
	KLPV87	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
	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]
	Lit89	N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
	LW89	N. Littlestone and M.K. Warmuth. The weighted majority algorithm. 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 Sociely, 103(2):547-550, 1988.
	PR85	V Pan , J Reif, Efficient parallel solution of linear systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.143-152, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22161]
	PW90	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]

CITED BY 9

	Jyrki Kivinen , Manfred K. Warmuth, The perceptron algorithm vs. Winnow: linear vs. logarithmic mistake bounds when few input variables are relevant, Proceedings of the eighth annual conference on Computational learning theory, p.289-296, July 05-08, 1995, 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
	Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, 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
	Ethan J. Bernstein, Absolute error bounds for learning linear functions online, Proceedings of the fifth annual workshop on Computational learning theory, p.160-163, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	V. G. Vovk, A game of prediction with expert advice, Proceedings of the eighth annual conference on Computational learning theory, p.51-60, July 05-08, 1995, Santa Cruz, California, United States
	Sally A. Goldman , Manfred K. Warmuth, Learning binary relations using weighted majority voting, Proceedings of the sixth annual conference on Computational learning theory, p.453-462, July 26-28, 1993, Santa Cruz, California, United States
	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
	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada