canonical distortion over large sets of distances between vectors as follows:
Corollary 5 If m ≥ Ω( 1 ǫ 2 log(n/δ)) and η =
O(ǫ log(m/δ)
)*. Denote by* X = {x1**, . . . , x**n} *a set of vectors* which satisfy kxi − xjk∞ ≤ η kxi − xjk2 for all pairs **i, j**.

In this case with probability 1 − δ *we have for all* **i, j**

$${\frac{\left|\,\left\|x_{i}-x_{j}\right\|_{\phi}^{2}-\left\|x_{i}-x_{j}\right\|_{2}^{2}\,\right|}{\left\|x_{i}-x_{j}\right\|_{2}^{2}}}\leq\epsilon.$$

This means that the number of observations n (or correspondingly the size of the un-hashed kernel matrix) only enters *logarithmically* in the analysis. Proof We apply the bound of Theorem 3 to each distance individually. Note that each vector xi − xj satisfies the conditions of the theorem, and hence for each vector xi − xj , we preserve the distance upto a factor of (1 ± ǫ) with probability 1 −
δ n2 . Taking the union bound over all pairs gives us the result.

## 3.2. Multiple Hashing

Note that the tightness of the union bound in Corollary 5 depends crucially on the magnitude of η. In other words, for large values of η, that is, whenever some terms in x are very large, even a single collision can already lead to significant distortions of the embedding. This issue can be amended by trading off sparsity with variance. A vector of unit length may be written as (1, 0, 0, 0**, . . .**), or as √
1 2
, √
1 2
, 0**, . . .**, or more generally as a vector with c nonzero terms of magnitude c− 12 . This is relevant, for instance whenever the magnitudes of x follow a known pattern, e.g. when representing documents as bags of words since we may simply hash frequent words several times.

The following corollary gives an intuition as to how the confidence bounds scale in terms of the replications:

  **Lemma 6**: _If we let $x^{\prime}=\frac{1}{\sqrt{c}}(x,\ldots,x)$ then:_
$$1.\,\,\,\,It\,\,\,{\mathrm{is~norm~preserving}}\colon\|x\|_{2}=\|x^{\prime}\|_{2}\,.$$
2. It reduces component magnitude by √
$\left.+\frac{1}{x'}=\frac{||x'||}{||x||}\right|$
c =
kxk∞
.

3. Variance increases to σ 2 x′,x′ =
1 c σ 2x,x+
c−1 c 2 kxk 4 2
.
Applying Lemma 6 to Theorem 3, a large magnitude can be decreased at the cost of an increased variance.

## 3.3. Approximate Orthogonality

For multitask learning, we must learn a different parameter vector for each related task. When mapped into the same hash-feature space we want to ensure that there is little interaction between the different parameter vectors. Let U be a set of different tasks, u ∈ U being a specific one. Let w be a combination of the parameter vectors of tasks in U \ {u}.

We show that for any observation x for task u, the interaction of w with x in the hashed feature space is minimal.

For each x, let the image of x under the hash feature-map for task u be denoted as φu(x) = φ
(ξ,h)((**x, u**)).

Theorem 7 Let w ∈ R
m be a parameter vector for tasks in U \ {u}*. In this case the value of the inner product* h**w, φ**u(x)i *is bounded by*

$\Pr\left\{|\langle w,\phi_{u}(x)\rangle|>\epsilon\right\}\leq2e^{-\frac{\epsilon^{2}/2}{m-1\|w\|_{2}^{2}\|x\|_{2}^{2}+\epsilon\|w\|_{\infty}\|x\|_{\infty}^{2}}}$
kxk22+ǫkwk∞kxk∞/3
Proof We use Bernstein's inequality (Bernstein, 1946),
which states that for independent random variables Xj ,
with E [Xj **] = 0**, if C > 0 is such that |Xj| ≤ C, then

$$\Pr\left[\sum_{j=1}^{n}X_{j}>t\right]\leq\exp\left(-{\frac{t^{2}/2}{\sum_{j=1}^{n}\mathbf{E}\left[X_{j}^{2}\right]+C t/3}}\right).\tag{5}$$

We have to compute the concentration property of h**w, φ**u(x)i =Pj xj ξ(j)wh(j). Let Xj = xj ξ(j)wh(j).

By the definition of h and ξ, Xj are independent. Also, for each j, since w depends only on the hash-functions for U \ {u}, wh(j) is independent of ξ(j). Thus, E[Xj] =
E(ξ,h)
-xj ξ(j)wh(j)
= 0. For each j, we also have |Xj | <
kxk∞ kwk∞ =: C. Finally, Pj E[X2 j
] is given by

$$\mathbf{E}\left[\sum_{j}(x_{j}\xi(j)w_{h(j)})^{2}\right]={\frac{1}{m}}\sum_{j,\ell}x_{j}^{2}w_{\ell}^{2}={\frac{1}{m}}\left\|x\right\|_{2}^{2}\left\|w\right\|_{2}^{2}$$

The claim follows by plugging both terms and C into the Bernstein inequality (5).

Theorem 7 bounds the influence of unrelated tasks with any particular instance. In section 5 we demonstrate the realworld applicability with empirical results on a large-scale multi-task learning problem.

## 4. Applications

The advantage of feature hashing is that it allows for significant storage compression for parameter vectors: storing w in the raw feature space naively requires O(d) numbers, when w ∈ R
d. By hashing, we are able to reduce this to O(m) numbers while avoiding costly matrix-vector multiplications common in Locally Sensitive Hashing. In addition, the sparsity of the resulting vector is preserved.