Improved guarantees for agnostic learning of disjunctions

Pranjal Awasthi, Avrim Blum, Or Sheffet

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


Given some arbitrary distribution D over {0, 1}n and arbitrary target function c*, the problem of agnostic learning of disjunctions is to achieve an error rate comparable to the error OPT disj of the best disjunction with respect to (D, c *). Achieving error O(n · OPTdisj) + ε is trivial, and Winnow [13] achieves error O(r · OPTdisj) + ε, where r is the number of relevant variables in the best disjunction. In recent work, Peleg [14] shows how to achieve a bound of Õ (√n · OPTdisj) + ε in polynomial time. In this paper we improve on Peleg's bound, giving a polynomial-time algorithm achieving a bound of O(n1/3+α · OPTdisj) + ε for any constant α > 0. The heart of the algorithm is a method for weak-learning when OPTdisj = O(1/n1/3+α), which can then be fed into existing agnostic boosting procedures to achieve the desired guarantee.

Original languageEnglish (US)
Title of host publicationCOLT 2010 - The 23rd Conference on Learning Theory
Number of pages9
StatePublished - 2010
Externally publishedYes
Event23rd Conference on Learning Theory, COLT 2010 - Haifa, Israel
Duration: Jun 27 2010Jun 29 2010

Publication series

NameCOLT 2010 - The 23rd Conference on Learning Theory


Other23rd Conference on Learning Theory, COLT 2010

All Science Journal Classification (ASJC) codes

  • Education


Dive into the research topics of 'Improved guarantees for agnostic learning of disjunctions'. Together they form a unique fingerprint.

Cite this