Sketching and Neural Networks
  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}/{{\gamma}^2})$ dependence of random projections, on
the margin $\gamma$. We empirically show that our approach leads to more
compact neural networks than related methods such as feature hashing at equal
or better performance.
