On the Complexity of Proper Distribution-Free Learning of Linear Classifiers

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.

• Machine Intelligence

• Algorithms and Theory