Linear Regression with Self-Selection Bias in Polynomial Time
The algorithm removes the exponential dependence on the number of regressors in the unknown-index setting.
Felix Zhou gives an algorithm whose running time is polynomial in the dimension, number of regressors and inverse error tolerance under the maximum self-selection criterion. It also handles correlated noise between regressors, yielding what the paper identifies as the first polynomial-time algorithm for max-affine regression. The method uses high-order moments of the input variables among observations with large responses to recover regressor directions. A variant of ordinary least squares then estimates the regressors themselves.
ArXiv · AI/CL/LG's note
Felix Zhou gives an algorithm whose running time is polynomial in the dimension, number of regressors and inverse error tolerance under the maximum self-selection criterion. It also handles correlated noise between regressors, yielding what the paper identifies as the first polynomial-time algorithm for max-affine regression. The method uses high-order moments of the input variables among observations with large responses to recover regressor directions. A variant of ordinary least squares then estimates the regressors themselves.
ArXiv · AI/CL/LG's note
score 5