A Uniform Lower Error Bound for Half-Space Learning
Abstract
We give a lower bound for the error of any unitarily invariant algorithm learning half-spaces against the uniform or related distributions on the unit sphere. The bound is uniform in the choice of the target half-space and has an exponentially decaying deviation probability in the sample. The technique of proof is related to a proof of the Johnson Lindenstrauss Lemma. We argue that, unlike previous lower bounds, our result is well suited to evaluate the benefits of multi-task or transfer learning, or other cases where an expense in the acquisition of domain knowledge has to be justified.
Cite
Text
Maurer and Pontil. "A Uniform Lower Error Bound for Half-Space Learning." International Conference on Algorithmic Learning Theory, 2008. doi:10.1007/978-3-540-87987-9_10Markdown
[Maurer and Pontil. "A Uniform Lower Error Bound for Half-Space Learning." International Conference on Algorithmic Learning Theory, 2008.](https://mlanthology.org/alt/2008/maurer2008alt-uniform/) doi:10.1007/978-3-540-87987-9_10BibTeX
@inproceedings{maurer2008alt-uniform,
title = {{A Uniform Lower Error Bound for Half-Space Learning}},
author = {Maurer, Andreas and Pontil, Massimiliano},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2008},
pages = {70-78},
doi = {10.1007/978-3-540-87987-9_10},
url = {https://mlanthology.org/alt/2008/maurer2008alt-uniform/}
}