On efficient agnostic learning of linear combinations of basis functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On efficient agnostic learning of linear combinations of basis functions

Full text

Pdf (1.01 MB)

Source

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

Santa Cruz, California, United States

Pages: 369 - 376

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Wee Sun Lee	Dept. of Systems Engineering, RSISE, Aust. National University, Canberra, ACT 0200, Australia
Peter L. Bartlett	Dept. of Systems Engineering, RSISE, Aust. National University, Canberra, ACT 0200, Australia
Robert C. Williamson	Department of Engineering, Australian National University, Canberra, ACT 0200, Australia

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 23, Citation Count: 4

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

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler. Scale-sensitive dimensions, uniform convergence and learnability. In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci., 1993.
	3	D. Angluin and L. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matching. J. Comput. Syst. Sci., 18:155-193, 1970.
	4	Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
	5	A. Barton. Universal approximation bounds for superposition of a sigmoidal function. IEEE Trans. on Information Theory, 39:930-945, 1993.
	6	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 [doi>10.1145/180139.181158]
	7	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
	8	Leonid Gurvits , Pascal Koiran, Approximation and learning of convex superpositions, Proceedings of the Second European Conference on Computational Learning Theory, p.222-236, March 13-15, 1995
	9	David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
	10	W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301): 13-30, March 1963.
	11	Klaus-Uwe Höffgen , Hans Ulrich Simon, Robust trainability of single neurons, Proceedings of the fifth annual workshop on Computational learning theory, p.428-439, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130431]
	12	Mark Jerrum, Simple translation-invariant concepts are hard to learn, Information and Computation, v.113 n.2, p.300-311, Sept. 1994 [doi>10.1006/inco.1994.1074]
	13	L. K. Jones. A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training. The Annals of Statistics, 20:608-613, 1992.
	14	Michael J. Kearns , Robert E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, v.48 n.3, p.464-497, June 1994 [doi>10.1016/S0022-0000(05)80062-5]
	15	Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward Efficient Agnostic Learning, Machine Learning, v.17 n.2-3, p.115-141, Nov./Dec. 1994 [doi>10.1007/BF00993468]
	16	Pascal Koiran, Efficient learning of continuous neural networks, Proceedings of the seventh annual conference on Computational learning theory, p.348-355, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181177]
	17	W. S. Lee, P. L. Bartlett, and R. C. Williamson. Efficient agnostic learning of neural networks with bounded fan-in. Technical report, Department of Systems Engineering, Australian National University, 1994.
	18	W. Maass. Agnostic PAC-learning of functions on analog neural networks. Technical report, Institute for Theoretical Computer Science, Technische Universitaet Graz, Graz, Austria, 1993.
	19	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	20	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

CITED BY 4

	Wee Sun Lee , Peter L. Bartlett , Robert C. Williamson, The importance of convexity in learning with squared loss, Proceedings of the ninth annual conference on Computational learning theory, p.140-146, June 28-July 01, 1996, Desenzano del Garda, Italy
	Nigel Duffy , David Helmbold, Boosting Methods for Regression, Machine Learning, v.47 n.2-3, p.153-200, May-June 2002
	Vassilis A. Papavassiliou , Stuart Russell, Convergence of reinforcement learning with general function approximators, Proceedings of the 16th international joint conference on Artificial intelligence, p.748-755, July 31-August 06, 1999, Stockholm, Sweden
	Vitaly Feldman, On The Power of Membership Queries in Agnostic Learning, The Journal of Machine Learning Research, 10, p.163-182, June 2009