Learning Intersections of Halfspaces with a Margin

Klivans, Adam R.; Servedio, Rocco A.

doi:10.1007/978-3-540-27819-1_24

Learning Intersections of Halfspaces with a Margin

Adam R. Klivans, Rocco A. Servedio

COLT 2004 pp. 348-362

doi:10.1007/978-3-540-27819-1_24 /colt/2004/klivans2004colt-learning/

Abstract

We give a new algorithm for learning intersections of halfspaces with a margin, i.e. under the assumption that no example lies too close to any separating hyperplane. Our algorithm combines random projection techniques for dimensionality reduction, polynomial threshold function constructions, and kernel methods. The algorithm is fast and simple. It learns a broader class of functions and achieves an exponential runtime improvement compared with previous work on learning intersections of halfspaces with a margin.

PDF COLT Semantic Scholar

Cite

Text

Klivans and Servedio. "Learning Intersections of Halfspaces with a Margin." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_24

Markdown

[Klivans and Servedio. "Learning Intersections of Halfspaces with a Margin." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/klivans2004colt-learning/) doi:10.1007/978-3-540-27819-1_24

BibTeX

@inproceedings{klivans2004colt-learning,
  title     = {{Learning Intersections of Halfspaces with a Margin}},
  author    = {Klivans, Adam R. and Servedio, Rocco A.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2004},
  pages     = {348-362},
  doi       = {10.1007/978-3-540-27819-1_24},
  url       = {https://mlanthology.org/colt/2004/klivans2004colt-learning/}
}