Attributeefficient learning of monomials over highlycorrelated variables
[edit]
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:127161, 2019.
Abstract
We study the problem of learning a realvalued 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 highdimensional, sparse monomial model from Gaussian examples with sample complexity that is polylogarithmic 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 nonlinear 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.
Related Material


