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

MaRDI QIDQ4558503zbMATH OpenFDO

Authors Rajen D. Shah, Nicolai Meinshausen

Publication date 22 November 2018

Full work available at URL https://arxiv.org/abs/1308.1269, http://jmlr.csail.mit.edu/papers/v18/16-587.html

zbMATH Keywords

ridge regressionsparse datalarge-scale datamin-wise hashingresemblance kernel

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Ridge regression; shrinkage estimators (Lasso) (62J07)

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

Recommendations

• Bayesian compressed regression
• scientific article; zbMATH DE number 6276198
• High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
• Minimax adaptive dimension reduction for regression
• The coefficient regularized regression with random projection

Cites work

• scientific article; zbMATH DE number 2130678 (Why is no real title available?)
• scientific article; zbMATH DE number 5430929 (Why is no real title available?)
• scientific article; zbMATH DE number 1947403 (Why is no real title available?)
• scientific article; zbMATH DE number 1775418 (Why is no real title available?)
• scientific article; zbMATH DE number 1857652 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 6276198 (Why is no real title available?)
• A proof for the positive definiteness of the Jaccard index matrix
• Boosting for high-dimensional linear models
• Extensions of Lipschitz mappings into a Hilbert space
• Faster least squares approximation
• Greed is Good: Algorithmic Results for Sparse Approximation
• Hash kernels for structured data
• High-dimensional generalized linear models and the lasso
• Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
• Kernel methods in machine learning
• Least angle regression. (With discussion)
• On the equivalence between kernel quadrature rules and random feature expansions
• Predictive learning via rule ensembles
• Random forests
• Random projections for the nonnegative least-squares problem
• Randomized Algorithms for Matrices and Data
• Randomized Sketches of Convex Programs With Sharp Guarantees
• Randomized sketches for kernels: fast and optimal nonparametric regression
• Ridge Regression: Biased Estimation for Nonorthogonal Problems
• Statistics for high-dimensional data. Methods, theory and applications.
• Universal classes of hash functions

Cited in

(1)

• On principal components regression, random projections, and column subsampling

Describes a project that uses

Uses Software

• Vowpal Wabbit

This page was built for publication: On \(b\)-bit min-wise hashing for large-scale regression and classification with sparse data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558503)