On b-bit min-wise hashing for large-scale regression and classification with sparse data

摘要: Large-scale regression problems where both the number of variables, $p$, and observations, $n$, may be large in order millions or more, are becoming increasingly more common. Typically data sparse: only a fraction percent entries design matrix non-zero. Nevertheless, often computationally feasible approach is to perform dimension reduction obtain new with far fewer columns then work this compressed data. $b$-bit min-wise hashing (Li Konig, 2011) promising scheme for sparse matrices which produces set random features such that on resulting approximates kernel resemblance kernel. In work, we derive bounds prediction error regressions. For linear logistic models show average vanishes asymptotically as long $q \|\beta^*\|_2^2 /n \rightarrow 0$, $q$ non-zero each row $\beta^*$ coefficient predictor. We also ordinary least squares ridge applied reduced can fact allow us fit flexible models. We non-asymptotic interaction an unknown normalisation must signal predictors.