Access Restriction

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

   Open content in new tab
Source: ACM Digital Library