Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-032 | 25th February 2006 00:00

Optimal Hardness Results for Maximizing Agreements with Monomials

RSS-Feed




TR06-032
Authors: Vitaly Feldman
Publication: 9th March 2006 04:26
Downloads: 3164
Keywords: 


Abstract:

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was proved to be NP-hard by Kearns and Li . Ben-David et al. gave the first inapproximability result for this problem, proving that the maximum agreement rate is NP-hard to approximate within 770/767-\eps, for any constant \eps>0. The strongest known hardness of approximation result is due to Bshouty and Burroughs, who proved an inapproximability factor of 59/58-\eps. We show that the agreement rate is NP-hard to approximate within 2-\eps for any constant \eps >0. This is optimal up to the second order terms. We extend this result to \eps = 2^{-c \sqrt{\log{n}}} for some constant c>0 under the assumption that NP \not\subseteq RTIME(n^{\log(n)}) , thus also obtaining an inapproximability factor of 2^{c \sqrt{\log{n}}} for the symmetric problem of minimizing disagreements. This improves on the \log{n} hardness of approximation factor due to Kearns et al. and Hoffgen et al.



ISSN 1433-8092 | Imprint