No Access

LEARNING RATES FOR DENSITY LEVEL DETECTION

CLINT SCOVEL

Modeling, Algorithms and Informatics Group, CCS-3, Los Alamos National Laboratory, Los Alamos, New Mexico, 87545, USA

Search for more papers by this author

DON HUSH

Modeling, Algorithms and Informatics Group, CCS-3, Los Alamos National Laboratory, Los Alamos, New Mexico, 87545, USA

Search for more papers by this author

, and

INGO STEINWART

Modeling, Algorithms and Informatics Group, CCS-3, Los Alamos National Laboratory, Los Alamos, New Mexico, 87545, USA

Search for more papers by this author

https://doi.org/10.1142/S0219530505000625Cited by:6 (Source: Crossref)

Abstract

In this paper, we address learning rates for the density level detection (DLD) problem. We begin by proving a "No Free Lunch Theorem" showing that rates cannot be obtained in general. Then, we apply a recently established classification framework to obtain rates for DLD support vector machines under mild assumptions on the density.

Keywords:

AMSC: 68Q32, 68T05

References

S. Ben-David and M. Lindenbaum, J. Comput. System Sci. 55, 171 (1997), DOI: 10.1006/jcss.1997.1507. Crossref, Web of Science, Google Scholar
A. Cuevas, M. Febrero and R. Fraiman, Comput. Statist. Data Anal. 36, 441 (2001), DOI: 10.1016/S0167-9473(00)00052-9. Crossref, Web of Science, Google Scholar
L. Devroye , L. Györfi and G. Lugosi , A Probabilistic Theory of Pattern Recognition ( Springer , New York , 1996 ) . Crossref, Google Scholar
J. A. Hartigan , Clustering Algorithms ( Wiley , New York , 1975 ) . Google Scholar
J. A. Hartigan, J. Amer. Statist. Assoc. 82, 267 (1987), DOI: 10.2307/2289162. Crossref, Web of Science, Google Scholar
D. W. Müller and G. Sawitzki, J. Amer. Statist. Assoc. 86, 738 (1991), DOI: 10.2307/2290406. Web of Science, Google Scholar
W. Polonik, Ann. Stat. 23, 855 (1995). Crossref, Web of Science, Google Scholar
G. Sawitzki, The excess mass approach and the analysis of multi-modality, From Data to Knowledge: Theoretical and Practical Aspects of Classification, Data Analysis and Knowledge Organization, Proc. 18th Annual Conf. GfKl, eds. W. Gaul and D. Pfeifer (Springer, 1996) pp. 203–211. Google Scholar
I. Steinwart, D. Hush and C. Scovel, J. Mach. Learn. Res. 6, 211 (2005). Web of Science, Google Scholar
I. Steinwart and C. Scovel, Ann. Statist. (2004). Google Scholar
I. Steinwart and C. Scovel , Fast rates for support vector machines , Proc. 18th Conf. Learning Theory (COLT-2005) ( 2005 ) . Google Scholar
I. Steinwart, D. Hush and C. Scovel, Neural Inf. Process. Sys. 17, 1337 (2005). Web of Science, Google Scholar
A. B. Tsybakov, Ann. Stat. 25, 948 (1997), DOI: 10.1214/aos/1069362732. Crossref, Web of Science, Google Scholar
A. W. van der Vaart and J. A. Wellner , Weak Convergence and Empirical Processes ( Springer , New York , 1997 ) . Google Scholar