English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present a generalization of the well-known problem of learning k-juntas inR^n, and a novel tensor algorithm for unraveling the structure ofhigh-dimensional distributions. Our algorithm can be viewed as a higher-orderextension of Principal Component Analysis (PCA).  Our motivating problem is learning a labeling function in R^n, which isdetermined by an unknown k-dimensional subspace. This problem of learning ak-subspace junta is a common generalization of learning a k-junta (a functionof k coordinates in R^n) and learning intersections of k halfspaces. In thiscontext, we introduce an irrelevant noisy attributes model where thedistribution over the "relevant" k-dimensional subspace is independent of thedistribution 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 dothis by exploiting the structure of local optima of higher moment tensors overthe unit sphere; PCA finds the global optima of the second moment tensor(covariance matrix). Our main result is that when the distribution in theirrelevant (n-k)-dimensional subspace is any Gaussian, the complexity of ouralgorithm is T(k,\epsilon) + \poly(n), where T is the complexity of learningthe concept in k dimensions, and the polynomial is a function of thek-dimensional concept class being learned. This substantially generalizesexisting results on learning low-dimensional concepts.

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