Improved Guarantees for Agnostic Learning of Disjunctions

Given some arbitrary distribution D over {0, 1}ⁿ 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 · OPT_disj) + ∈ is trivial, and Winnow [12] achieves error O(r ·OPT_disj )+∈, where r is the number of relevant variables in the best disjunction. In recent work, Peleg [13] shows how to achieve a bound of ˜O(√n·OPT_disj )+ ∈ in polynomial time. In this paper we improve on Peleg’s bound, giving a polynomial-time algorithm achieving a bound of

O(n^1/3+α · OPT_disj) + ∈

for any constant α > 0. The heart of the algorithmis amethod forweak-learningwhenOPT_disj = O(1/n^1/3+α ), which can then be fed into existing agnostic boosting procedures to achieve the desired guarantee.