A Lower Bound for Agnostically Learning Disjunctions

摘要

We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of arbitrary real-valued functions. That is, suppose there exist functions φ_l,…, φ_r : {-1,1}~n →R with the property that every disjunction f on n variables has ||f — ∑_I~r=1 α_iφ_i||∞ ≤ 1/3 for some reals α_l,…, α_r. We prove that then r ≥ 2~Ω(n(1/2)). This lower bound is tight. We prove an incomparable lower bound for the concept class of linear-size DNF formulas. For the concept class of majority functions, we obtain a lower bound of Ω(2~n), which almost meets the trivial upper bound of 2~n for any concept class.These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi and show that the regression-based agnostic learning algorithm of Kalai et al. is optimal. Our techniques involve a careful application of results in communication complexity due to Razborov and Buhrman et al.