TY - GEN

T1 - Improved guarantees for agnostic learning of disjunctions

AU - Awasthi, Pranjal

AU - Blum, Avrim

AU - Sheffet, Or

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84898063061&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84898063061&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84898063061

SN - 9780982252925

T3 - COLT 2010 - The 23rd Conference on Learning Theory

SP - 359

EP - 367

BT - COLT 2010 - The 23rd Conference on Learning Theory

T2 - 23rd Conference on Learning Theory, COLT 2010

Y2 - 27 June 2010 through 29 June 2010

ER -