ICS 2010

Welcome to ICS2010
Innovations in Computer Science  ICS 2010, Tsinghua University, Beijing, China, January 57, 2010. Proceedings, 241250,
9787302217527
Tsinghua University Press
We consider the problem of boosting the accuracy of weak learning algorithms in the agnostic learning framework of Haussler (1992) and Kearns et al. (1992). Known algorithms for this problem (BenDavid et al., 2001; Gavinsky, 2002; Kalai et al., 2008) follow the same strategy as boosting algorithms in the PAC model: the weak learner is executed on the same target function but over different distributions on the domain. Application of such boosting algorithms usually requires a distributionindependent weak agnostic learners. Here we demonstrate boosting algorithms for the agnostic learning framework that only modify the distribution on the labels of the points (or, equivalently, modify the target function). This allows boosting a distributionspecific weak agnostic learner to a strong agnostic learner with respect to the same distribution. Our algorithm achieves the same guarantees on the final error as the boosting algorithms of Kalai et al. (2008) but is substantially simpler and more efficient. When applied to the weak agnostic parity learning algorithm of Goldreich and Levin (1989) our algorithm yields a simple PAC learning algorithm for DNF and an agnostic learning algorithm for decision trees over the uniform distribution using membership queries. These results substantially simplify Jackson’s famous DNF learning algorithm (1994) and the recent result of Gopalan et al. (2008). We also strengthen the connection to hardcore set constructions discovered by Klivans and Servedio (1999) by demonstrating that hardcore set constructions that achieve the optimal hardcore set size (given by Holenstein (2005) and Barak et al. (2009)) imply distributionspecific agnostic boosting algorithms. Conversely, our boosting algorithm gives a simple hardcore set construction with an (almost) optimal hardcore set size. Preview:

Copyright 20092010, Institute for Computer Science, Tsinghua University, All Rights Reserved.