Boosting in the Presence of Noise (Extended Abstract)
Adam Tauman Kalai, Rocco A. Servedio · 2003
Boosting algorithms are procedures that \\boost " low accu-racy weak learning algorithms to achieve arbitrarily high ac-curacy. Over the past decade boosting has been widely used in practice and has become a major research topic in com-putational learning theory. In this paper we study boosting in the presence of random classication noise, giving both positive and negative results. We show that a modied version of a boosting algorithm due to Mansour and McAllester [14] can achieve accuracy arbitrarily close to the noise rate. We also give a matching lower bound by showing that no ecient black-box boosting algorithm can boost accuracy1 beyond the noise rate (as-suming that one-way functions exist). Finally, we consider a variant of the standard scenario for boosting in which the \\weak learner " satises a slightly stronger condition than the usual weak learning guarantee. We give an ecient al-gorithm in this framework which can boost to arbitrarily high accuracy in the presence of classication noise.