Maximizing Agreements and CoAgnostic Learning

Abstract

This paper studies α-CoAgnostic learnability of classes of boolean formulas. To α-CoAgnostic learn C from H , the learner seeks a hypothesis h ∈; H that agrees (rather than disagrees as in Agnostic learning) within a factor α of the best agreement of any f ∈; C . Although 1-CoAgnostic learning is equivalent to Agnostic learning, this is not true for α-CoAgnostic learning for 1/2 < α < 1. It is known that α-CoAgnostic learning algorithms are equivalent to α- approximation algorithms for maximum agreement problems. Many studies have been done on maximum agreement problems, for classes such as monomials, monotone monomials, antimonotone monomials, halfspaces and balls. We study these problems further and some extensions of them. For the above classes we improve the best previously known factors α for the hardness of α-CoAgnostic learning. We also find the first constant lower bounds for decision lists, exclusive-or, halfspaces (over the boolean domain), 2-term DNF and 2-term multivariate polynomials.