Complexity Theoretic Limitations on Learning Halfspaces

Amit Daniely

We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution $\mathcal{D}$ on ${\mathbb{Q}}^n\times \{\pm 1\}$. We define $\mathrm{Er…