ECCC-Report TR06-032https://eccc.weizmann.ac.il/report/2006/032Comments and Revisions published for TR06-032en-usThu, 09 Mar 2006 04:26:46 +0200
Paper TR06-032
| Optimal Hardness Results for Maximizing Agreements with Monomials |
Vitaly Feldman
https://eccc.weizmann.ac.il/report/2006/032We 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.
Thu, 09 Mar 2006 04:26:46 +0200https://eccc.weizmann.ac.il/report/2006/032