[edit]

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

*Proceedings of the 31st International Conference on Algorithmic Learning Theory*, PMLR 117:583-591, 2020.

#### Abstract

For proper distribution-free learning of linear classifiers in $d$ dimensions from $m$ examples, we prove a lower bound on the optimal expected error of $\frac{d - o(1)}{m}$, improving on the best previous lower bound of $\frac{d/\sqrt{e} - o(1)}{m}$, and nearly matching a $\frac{d+1}{m+1}$ upper bound achieved by the linear support vector machine.