General convergence results for linear discriminant updates

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

General convergence results for linear discriminant updates

Full text

Pdf (1.95 MB)

Source

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

Nashville, Tennessee, United States

Pages: 171 - 183

Year of Publication: 1997

ISBN:0-89791-891-6

Authors

Adam J. Grove	NEC Research Institute, 4 Independence Way, Princeton NJ
Nick Littlestone	NEC Research Institute, 4 Independence Way, Princeton NJ
Dale Schuurmans	Institute for Research in Cognitive Science, University of Pennsylvania, 3401 Walnut Street, Suite 400A, Philadelphia, PA and NEC Research Institute, 4 Independence Way, Princeton NJ

Sponsors

AT&T Labs :
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Vanderbilt University : Vanderbilt University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 19, Citation Count: 13

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/267460.267493 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.

	Blo62	H. D. Block. The perceptron: a model for brain functioning. Reviews of Modem Physics, 34(1):123-135,1962.
	CFH+93	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 [doi>10.1145/167088.167198]
	CHP96	Nicolò Cesa-Bianchi , David P. Helmbold , Sandra Panizza, On Bayes methods for on-line Boolean prediction, Proceedings of the ninth annual conference on Computational learning theory, p.314-324, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238162]
	DH73	Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
	Ell85	R. Ellis. Entropy, Lurge Deviations, and Sfatistiral Mechanics. Springer-Verlag, New York, 1985.
	HKW96	D. Helmbold, J. Kivinen, and M. Warmuth. Worst-case loss bounds for single neurons. In Proceedings of NIPS-g, pages 309-3 15,1996.
	KW95	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 [doi>10.1145/225298.225333]
	KW97a	Katy Kazoury and Manfred K. Warmuth. Relative loss bounds and the exponential family of distributions. (unpublished manuscript), 1997.
	KW97b	Jyrki Kivinen , Manfred K. Warmuth, Exponentiated gradient versus gradient descent for linear predictors, Information and Computation, v.132 n.1, p.1-63, Jan. 10, 1997 [doi>10.1006/inco.1996.2612]
	KW97c	Jyrki Kivinen and Manfred Warmuth. Relative loss bounds for multiclass regression problems. (unpublished manuscript), 1997.
	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
	Lit91	Nicholas Littlestone, Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow, Proceedings of the fourth annual workshop on Computational learning theory, p.147-156, August 05-07, 1991, Santa Cruz, California, United States
	Lit95	N. Littlestone. Comparing several linearthreshold learning algorithms on tasks involving superfluous attributes. In Proceedings ML-95, pages 353-361, 1995.
	Lit97	N. Littlestone. An apobayesian relative of winnow. In Advances in Neural Information Processing Systems 9, 1997.
	LW89	N. Littlestone and M. Warmuth. The weighted majority algorithm. In Proceedings FOCS-89, pages 256-26 1,1989.
	MP69	M. L. Minsky and S. A. Papert. Perceptrons. MIT Press, Cambridge, MA, 1969.
	Nil65	N. J. Nilsson. Learning Machines. Morgan Kaufmann, San Mateo, CA, 1965.
	Pap61	S. Papert. Some mathematical models of leaming. In Proceedings of the Fourth London Symposium on Information Theory, 196 1.
	Roc70	R. Rockafellar. Convex Analvsis. Princeton University Press, 1970.
	Ros62	F. Rosenblatt. Principles of Neurodynumics: Perceptrons and the Theory of Bruin Mechanisms. Spartan Books, Washington, D. C., 1962.
	Vov90	Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
	War97	Manfred Warmuth. Personal communication, 1997.
	WJ97	Manfred K. Warmuth and Arun Jagota. Continuous time non-linear gradient descent: Convergence and relative loss bounds. (unpublished manuscript). 1997.

CITED BY 13

	Adam J. Grove , Nick Littlestone , Dale Schuurmans, General Convergence Results for Linear Discriminant Updates, Machine Learning, v.43 n.3, p.173-210, June 2001
	Katy S. Azoury , M. K. Warmuth, Relative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions, Machine Learning, v.43 n.3, p.211-246, June 2001
	Mark Herbster , Manfred K. Warmuth, Tracking the best regressor, Proceedings of the eleventh annual conference on Computational learning theory, p.24-31, July 24-26, 1998, Madison, Wisconsin, United States
	J. Kivinen , M. K. Warmuth, Relative Loss Bounds for Multidimensional Regression Problems, Machine Learning, v.45 n.3, p.301-329, December 2001
	Nigel Duffy , David Helmbold, A geometric approach to leveraging weak learners, Theoretical Computer Science, v.284 n.1, p.67-108, 6 July 2002
	Nicolò Cesa-Bianchi , Gábor Lugosi, Potential-Based Algorithms in On-Line Prediction and Game Theory, Machine Learning, v.51 n.3, p.239-261, June 2003
	Claudio Gentile , Nick Littlestone, The robustness of the p-norm algorithms, Proceedings of the twelfth annual conference on Computational learning theory, p.1-11, July 07-09, 1999, Santa Cruz, California, United States
	Robert E. Mahony , Robert C. Williamson, Prior knowledge and preferential structures in gradient descent learning algorithms, The Journal of Machine Learning Research, 1, p.311-355, 9/1/2001
	R. Servedio, PAC Analogues of Perceptron and Winnow Via Boosting the Margin, Machine Learning, v.47 n.2-3, p.133-151, May-June 2002
	Rocco A. Servedio, Smooth boosting and learning with malicious noise, The Journal of Machine Learning Research, 4, p.633-648, 12/1/2003
	Tong Zhang, On the Dual Formulation of Regularized Linear Systems with Convex Risks, Machine Learning, v.46 n.1-3, p.91-129, 2002
	Lu Zhang , Frans Coenen , Paul Leng, Setting attribute weights for k-NN based binary classification via quadratic programming, Intelligent Data Analysis, v.7 n.5, p.427-441, October 2003
	Giovanni Cavallanti , Nicolò Cesa-Bianchi , Claudio Gentile, Tracking the best hyperplane with a simple budget Perceptron, Machine Learning, v.69 n.2-3, p.143-167, December 2007