While the above plan provides a general recipe for importance sampling, the idea of “sketching the sketches” may not be applied in a black-box manner. First, the alternate distribution \(\)  should admit a sampling sketch. Second, the sketch evaluation algorithm for \((x_{\cdot , j})\)  and \(^{\prime }(\Pr _{}[j])\)  should be robust to the errors introduced by the Count-Min compression. Bounding the errors introduced by the Count-Min data structure, and ensuring that the approximate sketches \(\widehat{_1}\)  and \(\widehat{_2}\)  constitutes the bulk of the technical work. Specifically for us, the plan is executed as follows: when \(\sum _{i=1}^n x_i = 0 \in ^d\) , every \(j\)  satisfies (see Appendix )

cj  i=1n |xij - cj|p x, jpp [2-p, 1]. 

Hence, we will let \(\)  be the distribution supported on \([d]\)  given by setting, for each \(j \in [d]\) ,

[= j ] =  x,jppZ       where       Z = j=1d  x, jpp = i=1n j=1d |xij|p.

Note that (REF ) implies the variance of \(_{}\)  for \(\sim \)  is appropriately bounded. Furthermore, since \(\)  is an \(\ell _p\) -sampling distribution, the \(\ell _p\) -sampling sketches of [1]} are useful for sampling \(\sim \) . Finally, the approach of [1]} is particularly suited for bounding the errors incurred by Count-Min on \(\widehat{_1}\)  and \(\widehat{_2}\) , which we overview below.
