Attribute-efficient learning of monomials over highly-correlated variables
Attribute-efficient learning of monomials over highly-correlated variables
复制标题
DOI：
--
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Alexandr Andoni;Rishabh Dudeja;Daniel J. Hsu;Kiran Vodrahalli
中科院分区：
文献类型：
--
作者：
Alexandr Andoni;Rishabh Dudeja;Daniel J. Hsu;Kiran Vodrahalli
我们研究学习相关变量的实值函数这一问题。解决这个问题是有意义的，因为许多经典的学习结果仅适用于学习独立随机变量的函数的情况。我们展示了如何从高斯样本中恢复一个高维、稀疏的单项式模型，其样本复杂度在变量总数上是多项对数的，在相关变量数量上是多项式的。我们的算法基于对变量的一种变换——取它们的对数，然后是一个稀疏线性回归过程，该过程在统计和计算上是高效的。虽然这种变换在应用非线性回归中经常被使用，但其统计保证从未被严格分析过。我们证明，即使在原始特征高度相关且不满足稀疏线性回归所需的标准假设的情况下，稀疏回归过程也能成功。
We study the problem of learning a real-valued function of correlated variables. Solving this problem is of interest since many classical learning results apply only in the case of learning functions of random variables that are independent. We show how to recover a high-dimensional, sparse monomial model from Gaussian examples with sample complexity that is poly-logarithmic in the total number of variables and polynomial in the number of relevant variables. Our algorithm is based on a transformation of the variables—taking their logarithm—followed by a sparse linear regression procedure, which is statistically and computationally efficient. While this transformation is commonly used in applied non-linear regression, its statistical guarantees have never been rigorously analyzed. We prove that the sparse regression procedure succeeds even in cases where the original features are highly correlated and fail to satisfy the standard assumptions required for sparse linear regression.