S. Ben-David,
N. Eiron
and P. M. Long.
On the difficulty of approximately
maximizing agreements.
Journal of Computer and
System Sciences, 66(3):496-514, 2003.
(Available in Postscript and PDF formats.)
Abstract
We address the computational complexity
of learning in the agnostic framework. For a variety of
common concept classes we prove that,
unless P=NP, there is no polynomial time approximation
scheme for finding a member in the
class that approximately maximizes the agreement with a
given training sample. In particular
our results apply to the classes of monomials, axis-aligned
hyper-rectangles, closed balls and
monotone monomials. For each of these classes we prove the
NP-hardness of approximating maximal agreement to within some
fixed constant (independent of
the sample size and of the dimensionality
of the sample space).