Learning Functions of Halfspaces

20260 citationsJournal Articlegreen Open Access

Authors

Josh Alman · Columbia International University

Shyamal Patel · Columbia International University

Rocco A. Servedio · Columbia International University

Abstract

We give an algorithm that learns arbitrary Boolean functions of $k$ arbitrary halfspaces over $\mathbb{R}^n$, in the challenging distribution-free Probably Approximately Correct (PAC) learning model, running in time $2^{\sqrt{n} \cdot (\log n)^{O(k)}}$. This is the first algorithm that can PAC learn even intersections of two halfspaces in time $2^{o(n)}.$

Topics & Keywords

Machine Learning and Algorithms Complexity and Algorithms in Graphs Machine Learning and Data Classification

Publication Details

Published in: arXiv (Cornell University)

Field-Weighted Citation Impact: 0.00

Command Palette

Learning Functions of Halfspaces

Authors

Abstract

Topics & Keywords

Publication Details