# why use 'weighted sampling' instead of 'deterministic selection'

Sampling can provide an unbiased estimator, and calculation and storage on the sampled data entries can be decreased compared with those on the original data. Application on speeding up big data analysis includes sampling-based least regression, or more general research topic as 'randomized algorithms for speeding up machine learning / big data analysis'. Weighted sampling can select more important entries compared with uniform sampling. However, why should we use 'weighted sampling'?

An naive example is: given an vector $x\in R^d$ with the absolute value of its each entry $|x_{i-1}|>|x_i|$. Define the sampling probability as $p_i=|x_i|/\sum_{i=1}^d|x_i|$. Then, we define a new vector $y\in R^d$, and its each entry is defined by $y_i=x_i/(cp_i)$ with probability $cp_i$ and $y_i=0$ with probability $1-cp_i$, assuming $cp_i \leq 1$. Clearly, the expectation $E[y]=x$, and it is very likely that $y$ prefer big entries of $x$. Moreover, the expected number of non-zero entries of $y$ is $c$. The reconstruction error can be measured by any vector norm like $\|x-y\|_2$.

Then, why do not we just keep the first $c$ entries of $x$, because $|x_{i-1}|>|x_i|$ and this strategy also prefers big entries?

• I think this might be more of a machine learning question not as much about mathematics. the reason is usually that your original sample is not balanced i.e. that the ifrst sample is not representative. The random drawing is then an attempt to make it more representative. If you just take the first c terms, you over- compensate. the probability is just to correct the sampling bias you apparently orginally had. – zen Sep 18 '17 at 14:37

## 1 Answer

So the answer to your question lies in the so-called bias-variance tradeoff in Machine Learning. If we called the stochastic estimator $y$ and the deterministic estimator $z$, then notice what we have: $$\mathbb{E}[(y-x)] = 0, \quad \mathbb{E}[\sum_i (y_i - x_i)] = \sum_i x_i^2 ((c p_i)^{-1} - 1)$$ On the other hand: $$\mathbb{E}[(z-x)] = - \sum_{j > c} x_j, \quad \mathbb{E}[(z-x)^2] = \sum_{j > c} x_j^2$$ The generalization error for empericall risk minimization can be shown to be separable to the squared bias plus the variance. You most likely are interested in minimizing that (unless there is some other measure which you have not told us about). Also note that the choice of $c$ compared to the number of entries $d$ can have significant impact on how accurate your estimates are, unless there are further assumptions.

As an example you can make $|x_i| = |x_{i-1}| + \epsilon$ for the first $c+1$ entries and than all others be equal. Then you would be underestimating significantly the actual value of the norm.