Non-Gaussian Component Analysis (NGCA) is the following distribution learning problem: Given i.i.d. samples from a distribution on $\mathbb{R}^d$ that is non-gaussian in a hidden direction $v$ and an independent standard Gaussian in the orthogonal directions, the goal is to approximate the hidden direction $v$. Prior work \cite{DKS17-sq} provided formal evidence for the existence of an information-computation tradeoff for NGCA under appropriate moment-matching conditions on the univariate non-gaussian distribution $A$. The latter result does not apply when the distribution $A$ is discrete. A natural question is whether information-computation tradeoffs persist in this setting. In this paper, we answer this question in the negative by obtaining a sample and computationally efficient algorithm for NGCA in the regime that $A$ is discrete or nearly discrete, in a well-defined technical sense. The key tool leveraged in our algorithm is the LLL method \cite{LLL82} for lattice basis reduction.
翻译:非加西语成分分析(NGCA)存在信息交换交易的正式证据如下:鉴于美元(mathbb{R ⁇ d$)的分布样本在隐藏方向上是非加西语的,在隐藏方向上是一美元,在正方方向上是一个独立的标准戈西亚语,目标是接近隐藏方向一美元。先前的工作\cite{DKS17-sq}提供了正式证据,证明NGCA在非加西语分布的适当时间匹配条件下在非加西语分配美元上存在信息交换交易。当分配值为美元时,后一种结果不适用。一个自然的问题是,信息计算交易交易是否持续在这一设置中。在本文中,我们从否定的角度回答这个问题,在制度下,$A是离散的或几乎离散的技术意义上的。在我们算法中使用的关键工具是用于减压的LLL方法{CLL82}。