ملخص: We give an algorithm to learn an intersection of k halfspaces in Rn 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 (, d)-learns with time and sample complexity bounded by.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.

لغة: إنجليزية