  Empirical evidence suggests that hashing is an effective strategy for
dimensionality reduction and practical nonparametric estimation. In this paper
we provide exponential tail bounds for feature hashing and show that the
interaction between random subspaces is negligible with high probability. We
demonstrate the feasibility of this approach with experimental results for a
new use case -- multitask learning with hundreds of thousands of tasks.
