Timezone: »
We prove strong noise-tolerance properties of a potential-based boosting algorithm, similar to MadaBoost (Domingo and Watanabe, 2000) and SmoothBoost (Servedio, 2003). Our analysis is in the agnostic framework of Kearns, Schapire and Sellie (1994), giving polynomial-time guarantees in presence of arbitrary noise. A remarkable feature of our algorithm is that it can be implemented without reweighting examples, by randomly relabeling them instead. Our boosting theorem gives, as easy corollaries, alternative derivations of two recent non-trivial results in computational learning theory: agnostically learning decision trees (Gopalan et al, 2008) and agnostically learning halfspaces (Kalai et al, 2005). Experiments suggest that the algorithm performs similarly to Madaboost.
Author Information
Adam Kalai (Microsoft Research New England (-(-_(-_-)_-)-))
Varun Kanade (UC Berkeley)
More from the Same Authors
-
2021 : Programming Puzzles »
Tal Schuster · Ashwin Kalyan · Alex Polozov · Adam Kalai -
2021 Spotlight: Towards optimally abstaining from prediction with OOD test examples »
Adam Kalai · Varun Kanade -
2022 : Language Models Can Teach Themselves to Program Better »
Patrick Haluptzok · Matthew Bowers · Adam Kalai -
2022 Spotlight: Are GANs overkill for NLP? »
David Alvarez-Melis · Vikas Garg · Adam Kalai -
2022 : A Theory of Unsupervised Translation for Understanding Animal Communication »
Shafi Goldwasser · David Gruber · Adam Kalai · Orr Paradise -
2022 Poster: Are GANs overkill for NLP? »
David Alvarez-Melis · Vikas Garg · Adam Kalai -
2022 Poster: Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms »
Surbhi Goel · Sham Kakade · Adam Kalai · Cyril Zhang -
2021 : Programming Puzzles »
Tal Schuster · Ashwin Kalyan · Alex Polozov · Adam Kalai -
2021 Poster: Towards optimally abstaining from prediction with OOD test examples »
Adam Kalai · Varun Kanade -
2018 Poster: Supervising Unsupervised Learning »
Vikas Garg · Adam Kalai -
2018 Spotlight: Supervising Unsupervised Learning »
Vikas Garg · Adam Kalai -
2013 Poster: Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions »
Yasin Abbasi Yadkori · Peter Bartlett · Varun Kanade · Yevgeny Seldin · Csaba Szepesvari -
2012 Poster: Distributed Non-Stochastic Experts »
Varun Kanade · Zhenming Liu · Bozidar Radunovic -
2011 Poster: Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression »
Sham M Kakade · Adam Kalai · Varun Kanade · Ohad Shamir