Repository

StochasticWeightedSums.jl

Given (potentially scalar-sized) vectors $\mathbf{a}_{1},\ldots,\mathbf{a}_{I}$ and non-negative weights $w_{1},\ldots,w_{I}$, we want to compute the sum

\[\sum_{i = 1}^{I}w_{i}\mathbf{a}_{i}\]

stochasticly with much less than $I$ summands.

We pick a batch size $B$ and a maximum selection probability $\eta$. Let $W = \sum_{i}w_{i}$ be the sum of the weights. We then, for every $i = 1,\ldots,I$, draw a random number $r_{i} \sim \mathcal{U}\lbrack 0,1\rbrack$ and set

\[c_{i} = \begin{cases} \frac{W}{B} & \text{ if }B\frac{w_{i}}{W} \leq \eta\text{ and }r_{i} \leq B\frac{w_{i}}{W} \\ \frac{w_{i}}{\eta} & \text{ if }B\frac{w_{i}}{W} > \eta\text{ and }r_{i} \leq \eta \\ 0 & \text{ else. } \end{cases}\]

This implies

\[\begin{aligned} {{\mathbb{E}}_{r}}_{i}\left( c_{i} \right) & = \begin{cases} \frac{W}{B} \cdot B\frac{w_{i}}{W} + 0 \cdot \left( 1 - B\frac{w_{i}}{W} \right) & \text{ if }B\frac{w_{i}}{W} \leq \eta \\ \frac{w_{i}}{\eta} \cdot \eta + 0 \cdot \left( 1 - \frac{w_{i}}{\eta} \right) & \text{ if }B\frac{w_{i}}{W} > \eta \end{cases} \\ & = w_{i}. \end{aligned}\]

Therefore, we can compute

\[\sum_{i = 1}^{I}c_{i}\mathbf{a}_{i}\]

where we drop the summands with $c_{i} = 0$ and have

\[{\mathbb{E}}(\sum_{i = 1}^{I}c_{i}\mathbf{a}_{i}) = \sum_{i = 1}^{I}{\mathbb{E}}(c_{i})\mathbf{a}_{i} = \sum_{i = 1}^{I}w_{i}\mathbf{a}_{i}.\]

For every $i$ we have ${\mathbb{P}}(c_{i} > 0) \leq B\frac{w_{i}}{W}$ and thus

\[{\mathbb{E}}(\sum_{i}\mathbb{1}\left\lbrack c_{i} > 0 \right\rbrack) \leq \sum_{i}B\frac{w_{i}}{W} = \frac{B}{W}\sum_{i}w_{i} = B,\]

i.e. we expect to have at most $B$ summands (hence calling it the batch size).

Unfortunately, the actual expected batch size can be very small in adversary cases. Consider $w_{1} = 1 - \varepsilon$ and $W = 1$ for an arbitrary small $\varepsilon > 0$. We can then assume $Bw_{1} \gg \eta$ and $Bw_{i} \ll \eta$ for $i > 1$. This means ${\mathbb{P}}(c_{1} > 0) = \eta$ and $\sum_{i = 2}^{I}{\mathbb{P}}(c_{i} > 0) = \varepsilon B$, so

\[{\mathbb{E}}(\sum_{i}\mathbb{1}\left\lbrack c_{i} > 0 \right\rbrack) = \eta + \varepsilon B\]

StochasticWeightedSums.stochastic_sum — Function
stochastic_sum([f, ] batch, items, weights)

Sum the items in items weighted by weights over a batch controlled by batch (FullBatch or StochasticBatch). Optionally apply f to each element of items first.

In expected value, this is equivalent to:

mapreduce((item, weight) -> weight * f(item), +, items, weights)
source
StochasticWeightedSums.StochasticBatch — Type
StochasticBatch(count, [rng = Random.default_rng()]; [maxprob = 9//10])

Only iterate over a random subset of items, determined using the random number generator rng. Items are chosen with a probability proportional to their weight but not higher than maxprob. The actual size of this subset is random as well but is upper-bounded by count in terms of the expected value. If most of the weight is concentrated on very few items, the size of this subset can be drastically lower.

In case there are less than count items in the first place, count will be set to the number of items.

You can make the batching fully deterministic by specifying a random number generator with fixed seed, i.e.

using Random

StochasticBatch(50, Xoshiro(123))
source