In:
Journal of the ACM, Association for Computing Machinery (ACM), Vol. 57, No. 6 ( 2010-10), p. 1-14
Abstract:
We give an algorithm to learn an intersection of k halfspaces in R n whose normals span an l -dimensional subspace. For any input distribution with a logconcave density such that the bounding hyperplanes of the k halfspaces pass through its mean, the algorithm (ϵ,δ)-learns with time and sample complexity bounded by ( nkl /ϵ) O(l) log 1/ϵ δ. The hypothesis found is an intersection of O(k log (1/ϵ)) 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.
Type of Medium:
Online Resource
ISSN:
0004-5411
,
1557-735X
DOI:
10.1145/1857914.1857916
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2010
detail.hit.zdb_id:
2006500-0
detail.hit.zdb_id:
6759-3
