Sketching and Neural Networks
This work addresses computational and statistical bottlenecks in machine learning for high-dimensional sparse data, offering a more efficient method for dimensionality reduction and classification.
The authors tackled the challenge of high-dimensional sparse data in supervised learning by proposing compact linear sketches to reduce input dimensionality, followed by a single-layer neural network, achieving a sketch size with logarithmic dependence on polynomial degree and improved margin dependence compared to random projections.
High-dimensional sparse data present computational and statistical challenges for supervised learning. We propose compact linear sketches for reducing the dimensionality of the input, followed by a single layer neural network. We show that any sparse polynomial function can be computed, on nearly all sparse binary vectors, by a single layer neural network that takes a compact sketch of the vector as input. Consequently, when a set of sparse binary vectors is approximately separable using a sparse polynomial, there exists a single-layer neural network that takes a short sketch as input and correctly classifies nearly all the points. Previous work has proposed using sketches to reduce dimensionality while preserving the hypothesis class. However, the sketch size has an exponential dependence on the degree in the case of polynomial classifiers. In stark contrast, our approach of using improper learning, using a larger hypothesis class allows the sketch size to have a logarithmic dependence on the degree. Even in the linear case, our approach allows us to improve on the pesky $O({1}/{γ^2})$ dependence of random projections, on the margin $γ$. We empirically show that our approach leads to more compact neural networks than related methods such as feature hashing at equal or better performance.