On the Complexity of Proper Distribution-Free Learning of Linear Classifiers
Abstract
For proper distribution-free learning
of linear classifiers in d dimensions,
we prove a lower bound on the optimal
expected error of (d - o(1))/m,
improving on the best previous lower bound of
(d/sqrt(e) - o(1))/m and nearly matching a (d+1)/(m+1) upper
bound achieved by the maximum margin classifier.