Access Restriction

Author Cesa-Bianchi, Nicol ♦ Dichterman, Eli ♦ Fischer, Paul ♦ Shamir, Eli ♦ Simon, Hans Ulrich
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword PAC learning ♦ Learning with malicious noise
Abstract In this paper, we prove various results about PAC learning in the presence of malicious noise. Our main interest is the sample size behavior of learning algorithms. We prove the first nontrivial sample complexity lower bound in this model by showing that order of ε/Δ2 + $\textit{d}/Δ$ (up to logarithmic factors) examples are necessary for PAC learning any target class of {0,1}-valued functions of VC dimension $\textit{d},$ where ε is the desired accuracy and &eegr; = ε/(1 + ε) - Δ the malicious noise rate (it is well known that any nontrivial target class cannot be PAC learned with accuracy ε and malicious noise rate &eegr; ≥ ε/(1 + ε), this irrespective to sample complexity). We also show that this result cannot be significantly improved in general by presenting efficient learning algorithms for the class of all subsets of $\textit{d}$ elements and the class of unions of at most $\textit{d}$ intervals on the real line. This is especialy interesting as we can also show that the popular minimum disagreement strategy needs samples of size $\textit{d}$ ε/Δ2, hence is not optimal with respect to sample size. We then discuss the use of randomized hypotheses. For these the bound ε/(1 + ε) on the noise rate is no longer true and is replaced by 2ε/(1 + 2ε). In fact, we present a generic algorithm using randomized hypotheses that can tolerate noise rates slightly larger than ε/(1 + ε) while using samples of size $\textit{d}/ε$ as in the noise-free case. Again one observes a quadratic powerlaw (in this case $\textit{d}ε/Δ2,$ Δ = 2ε/(1 + 2ε) - &eegr;) as Δ goes to zero. We show upper and lower bounds of this order.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 46
Issue Number 5
Page Count 36
Starting Page 684
Ending Page 719

Open content in new tab

   Open content in new tab
Source: ACM Digital Library