Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA

Details Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA

2011-08-16

arxiv.org/abs/1108.3329v3

Computer Science

Computational Complexity

Scientific paper

We present a generalization of the well-known problem of learning k-juntas in R^n, and a novel tensor algorithm for unraveling the structure of high-dimensional distributions. Our algorithm can be viewed as a higher-order extension of Principal Component Analysis (PCA). Our motivating problem is learning a labeling function in R^n, which is determined by an unknown k-dimensional subspace. This problem of learning a k-subspace junta is a common generalization of learning a k-junta (a function of k coordinates in R^n) and learning intersections of k halfspaces. In this context, we introduce an irrelevant noisy attributes model where the distribution over the "relevant" k-dimensional subspace is independent of the distribution over the (n-k)-dimensional "irrelevant" subspace orthogonal to it. We give a spectral tensor algorithm which identifies the relevant subspace, and thereby learns k-subspace juntas under some additional assumptions. We do this by exploiting the structure of local optima of higher moment tensors over the unit sphere; PCA finds the global optima of the second moment tensor (covariance matrix). Our main result is that when the distribution in the irrelevant (n-k)-dimensional subspace is any Gaussian, the complexity of our algorithm is T(k,\epsilon) + \poly(n), where T is the complexity of learning the concept in k dimensions, and the polynomial is a function of the k-dimensional concept class being learned. This substantially generalizes existing results on learning low-dimensional concepts.

Affiliated with

Also associated with

No associations

Rating

Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-196562