2011/08/16 by Vempala, Santosh S., Xiao, Ying · 1 citation
#15A69 #68Q32 #90C26 #Computational Complexity (cs.CC) #F.2 #FOS: Computer and information sciences #FOS: Mathematics #G.3 #Optimization and Control (math.OC) #Probability (math.PR)
paper · doi:10.48550/arxiv.1108.3329
We present a generalization of the well-known problem of learning k-juntas in Rn, 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 Rn, 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 Rn) 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,ε) + \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.