A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces

We present an algorithm for learning the intersection of half spaces in n dimensions. Over nearly uniform distributions, it runs in polynomial time for up to O(logn/loglogn) half spaces or, more generally for any number of half spaces whose normal vectors lie in an O(log n/log log n) dimensional subspace. Over less restricted "non-concentrated" distributions it runs in polynomial time for a constant number of half spaces. This generalizes an earlier result of A. Blum and R. Kannan (1993). The algorithm is simple and is based on random sampling.

Authors

• Santosh S. Vempala

Keywords

• Sampling methods
• Polynomials
• Machine learning
• Integrated circuit modeling
• Computer science
• Linear programming
• Neural networks
• Intersection Of Half-spaces
• Normal Vector
• Running Time
• Probability Density
• Unit Vector
• Hyperplane
• Steps Of Algorithm
• Error Parameters
• Unit Sphere
• Polynomial-time Algorithm
• Fraction Distribution
• Unknown Distribution
• Lattice Points
• Convex Objective
• Samples For Example
• Convex Cone
• Target Concept
• Projection Length
• Integer Lattice
• Confidence Parameter