Learning Convex Concepts from Gaussian Distributions with PCA
Author:
- Santosh S. VempalaSVSantosh S. Vempala
- 1 October 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 124-130
Abstract
We present a new algorithm for learning a convex set in n-dimensional space given labeled examples drawn from any Gaussian distribution. The complexity of the algorithm is bounded by a fixed polynomial in n times a function of k and ϵ where k is the dimension of the normal subspace (the span of normal vectors to supporting hyperplanes of the convex set) and the output is a hypothesis that correctly classifies at least 1 - ϵ of the unknown Gaussian distribution. For the important case when the convex set is the intersection of k halfspaces, the complexity is poly(n, k, 1/ϵ) + n · min k(O(log k/ϵ 4 )), (k/ϵ) O(k) , improving substantially on the state of the art [Vem04], [KOS08] for Gaussian distributions. The key step of the algorithm is a Singular Value Decomposition after applying a normalization. The proof is based on a monotonicity property of Gaussian space under convex restrictions.Keywords
This publication has 1 reference indexed in Scilit:
- Random Vectors in the Isotropic PositionJournal of Functional Analysis, 1999