We defer the proof to the appendix A. R (x, y) be the difference between the exact kernel (2) and the random approximation (3) with R samples, we have uniform convergence where d is the dimension of word embedding and L is a bound on the document length.
to guarantee | R (x, y)|  ✏ with probability at least 1 , it suffices to have We conduct an extensive set of experiments to demonstrate the effectiveness and efficiency of the proposed method.