### A random-sampling-based algorithm for learning intersections of halfspacesA random-sampling-based algorithm for learning intersections of halfspaces

Access Restriction
Subscribed

 Author Vempala, Santosh S. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2010 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Intersections of halfspaces ♦ PAC learning ♦ Complexity ♦ Random projection Abstract We give an algorithm to learn an intersection of $\textit{k}$ halfspaces in $R^{n}$ whose normals span an $\textit{l}-dimensional$ subspace. For any input distribution with a $\textit{logconcave}$ density such that the bounding hyperplanes of the $\textit{k}$ halfspaces pass through its mean, the algorithm (&epsis;,Δ)-learns with time and sample complexity bounded by $(nkl/&epsis;)^{O(l)}$ log 1/&epsis; Δ. The hypothesis found is an intersection of $\textit{O(k}$ log (1/&epsis;)) halfspaces. This improves on Blum and Kannan's algorithm for the uniform distribution over a ball, in the time and sample complexity (previously doubly exponential) and in the generality of the input distribution. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2010-11-05 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 57 Issue Number 6 Page Count 14 Starting Page 1 Ending Page 14

#### Open content in new tab

Source: ACM Digital Library