On the sample complexity of learning functions with bounded variation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the sample complexity of learning functions with bounded variation

Full text

Pdf (843 KB)

Source

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

Madison, Wisconsin, United States

Pages: 126 - 133

Year of Publication: 1998

ISBN:1-58113-057-0

Author

Philip M. Long

ISCS Department, National University of Singapore, Singapore 119260, Republic of Singapore

Sponsors

University of Wisconsin : University of Wisconsin
UC @ Santa Cruz : UC @ Santa Cruz
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): 2, Downloads (12 Months): 9, Citation Count: 1

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/279943.279970 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	Noga Alon , Shai Ben-David , Nicolò Cesa-Bianchi , David Haussler, Scale-sensitive dimensions, uniform convergence, and learnability, Journal of the ACM (JACM), v.44 n.4, p.615-631, July 1997 [doi>10.1145/263867.263927]
	2	P. L. Bartlett, S. R. Kulkami, and S. E. Posner. Coveting numbers for real-valued function classes. IEEE Transactions on Information Theory, 43(5):1721- 1724, 1997.
	3	Peter L. Bartlett , Philip M. Long, Prediction, learning, uniform convergence, and scale-sensitive dimensions, Journal of Computer and System Sciences, v.56 n.2, p.174-190, April 1998 [doi>10.1006/jcss.1997.1557]
	4	Rakesh D. Barve , Philip M. Long, On the complexity of learning from drifting distributions, Information and Computation, v.138 n.2, p.170-193, Nov. 1, 1997 [doi>10.1006/inco.1997.2656]
	5	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]
	6	R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. Wiley, 1973.
	7	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]
	8	David Haussler , Michael Kearns, Equivalence of models for polynomial learnability, Information and Computation, v.95 n.2, p.129-161, Dec. 1991 [doi>10.1016/0890-5401(91)90042-Z]
	9	D. Haussler , N. Littlestone , M. K. Warmuth, Predicting {0, 1}-functions on randomly drawn points, Information and Computation, v.115 n.2, p.248-292, Dec. 1994 [doi>10.1006/inco.1994.1097]
	10	David Haussler , Philip M. Long, A generalization of Sauer's lemma, Journal of Combinatorial Theory Series A, v.71 n.2, p.219-240, Aug. 1995 [doi>10.1016/0097-3165(95)90001-2]
	11	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]
	12	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]
	13	A. N. Kolmogorov and V. M. Tihomirov. ~-entropy and C-capacity of sets in functional spaces. American Mathematical Society Translations ( Ser. 2), 17:277- 364, 1961.
	14	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 [doi>10.1145/238061.238082]
	15	Philip M. Long, The complexity of learning according to two models of a drifting environment, Proceedings of the eleventh annual conference on Computational learning theory, p.116-125, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279968]
	16	B. K. Natarajan, Occam's razor for functions, Proceedings of the sixth annual conference on Computational learning theory, p.370-376, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168380]
	17	D. Pollard. Convergence of Stochastic Processes. Springer Verlag, 1984.
	18	D. Pollard. Empirical Processes: Theory and Applications, volume 2 of NSF-CBMS Regional Conference Series in Probability and Statistics. Institute of Math. Stat. and Am. Stat. Assoc., 1990.
	19	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 [doi>10.1145/168304.168392]
	20	H. L. Royden. Real Analysis. Macmillan, 1963.
	21	Hans Ulrich Simon, General bounds on the number of examples needed for learning probabilistic concepts, Journal of Computer and System Sciences, v.52 n.2, p.239-254, April 1996 [doi>10.1006/jcss.1996.0019]
	22	Hans Ulrich Simon, Bounds on the Number of Examples Needed for Learning Functions, SIAM Journal on Computing, v.26 n.3, p.751-763, June 1997 [doi>10.1137/S0097539793259185]
	23	P. Vaidya. A new algorithm for minimizing convex functions over convex sets. Proceedings of the 30thAnnual Symposium on the Foundations of Computer Science, pages 338-343, 1989.
	24	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]