Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-032 | 25th February 2006 00:00

Optimal Hardness Results for Maximizing Agreements with Monomials


Authors: Vitaly Feldman
Publication: 9th March 2006 04:26
Downloads: 2995


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