论文标题
学习几乎相关维度的多项式
Learning Polynomials of Few Relevant Dimensions
论文作者
论文摘要
多项式回归是学习和统计的基本原始性。在其最基本的形式中，目标是将$ d $多项式的学位拟合到响应变量$ y $方面，就$ n $二维输入向量$ x $而言。这在许多应用程序中进行了非常好的研究，并且具有样本和运行时复杂性$θ（n^d）$。如果数据的固有维度比环境尺寸$ n $小得多，可以实现更好的运行时间吗？具体而言，我们获得了样品$（x，y）$，其中$ y $最多是$ d $ doletemial的$ d $ r $ r $维投影（相关尺寸）的$ x $。这既可以看作是相位检索的概括，也可以看作是学习多指数模型的特殊情况，其中链接函数是未知的低度多项式。请注意，没有分布假设，这至少与政府学习一样难。 在这项工作中，我们考虑了协变量是高斯的重要情况。我们给出了一种算法，该算法在精度$ε$中学习了多项式的样品复杂性，该样品复杂性大约为$ n = o_ {r，d，d}（n \ log^2（1/ε）（\ log n）^d）$和Runtime $ o_ {r，d}（n^2）$。在我们工作之前，即使对于$ r = 1 $的情况，也不知道这种结果。我们引入了一种新的过滤PCA方法，以获得真实子空间的温暖起点，并使用Geodesic SGD提高了任意准确性；我们的技术可能具有独立的兴趣，尤其是对于处理子空间恢复或分析流形的SGD的问题。
Polynomial regression is a basic primitive in learning and statistics. In its most basic form the goal is to fit a degree $d$ polynomial to a response variable $y$ in terms of an $n$-dimensional input vector $x$. This is extremely well-studied with many applications and has sample and runtime complexity $Θ(n^d)$. Can one achieve better runtime if the intrinsic dimension of the data is much smaller than the ambient dimension $n$? Concretely, we are given samples $(x,y)$ where $y$ is a degree at most $d$ polynomial in an unknown $r$-dimensional projection (the relevant dimensions) of $x$. This can be seen both as a generalization of phase retrieval and as a special case of learning multi-index models where the link function is an unknown low-degree polynomial. Note that without distributional assumptions, this is at least as hard as junta learning. In this work we consider the important case where the covariates are Gaussian. We give an algorithm that learns the polynomial within accuracy $ε$ with sample complexity that is roughly $N = O_{r,d}(n \log^2(1/ε) (\log n)^d)$ and runtime $O_{r,d}(N n^2)$. Prior to our work, no such results were known even for the case of $r=1$. We introduce a new filtered PCA approach to get a warm start for the true subspace and use geodesic SGD to boost to arbitrary accuracy; our techniques may be of independent interest, especially for problems dealing with subspace recovery or analyzing SGD on manifolds.
