Google Research

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

ALT (2020)


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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work