L0 Sampling

Problem

Let $x \in \mathbb{R}^n$ be a vector initialized with all zeros. There is a stream $S$ of updates, each of which is a pair $(t, \Delta) \in [n] \times \mathbb{R}$, causing $x_t \leftarrow x_t + \Delta$.

Define the support $\mathbb{Supp}(x)$ to be the set of all non-zero indexes of $x$:

$\ell_0$ sampling: output an index uniformly at random from the support $\mathbb{Supp}(x)$.

We assume that at any time, $\forall t \in [n], x_t \le M$ for some $M \in \mathbb{R}$.

Naive Solutions

We can uses an array to keep $x$ explicitly. But this has size $O( n \cdot \log M)$ bits.

Goal: design an algorithm for $\ell_0$ sampling with space less than $O( n \cdot \log M)$ bits.

If there are only insertion updates, i.e., $\forall (t, \Delta) \in S$, it holds that $\Delta > 0$, then we can use a hash set to keep the non-zero elements and their frequencies, which has size $O( |\mathbb{Supp}(x) | \cdot \log M)$. If $x$ is dense, i.e., $|\mathbb{Supp}(x)|$ is large, this is still infeasible.

Sampling Game

We discuss one sampling game that illustrates the key ideas used in $\ell_0$-sampling.

In this game, we want to sample one integer uniformly at random from $[k]$. Instead of sampling it directly, we choose some $p \in (0, 1]$ and perform the following two steps:

1. First, we sample each $i \in [k]$ uniformly and independent at random with probability $p$. Denote $B$ the set of sampled elements.
2. If $B \neq \emptyset$, then output one element from $B$ uniformly at random.

Property. $\mathbb{E} [ |B| ] = kp$.

Property. $\Pr[ |B| > 0 ] = (1 - p)^k \le \exp(-kp)$.

Property. By Bernstein's Inequality, $\forall \delta \in (0, 1)$, with probability at least $1 - \delta$, we have

$$|B| - \mathbb{E} [ |B| ] \le \sqrt{2 \cdot k \cdot p \cdot (1 - p) \cdot \ln \frac{1}{\delta} } + \frac{2 \ln \frac{1}{\delta} }{3}.$$

Theorem. Each element in $[k]$ is outputted with equal probability

$$\frac{1 - \left(1 - p \right)^k }{ k }.$$

Remark: when $p = 1$, this reduces to sampling an element uniformly at random from $[k]$.

Proof. The probability that $B = \emptyset$ is given by $(1 - p)^k$. Conditioned on that $B \neq \emptyset$, by symmetry, each element is sampled with equal probability.

$\square$

Remark: We can also have a proof by algebra. For evert $i \in [k]$, the probability that it is sampled is given by

Sampling With Known Support Size

We use the technique developed in the Sampling Game section, to avoid using $O( | \mathbb{Supp}(x) | \log M)$ bits. We have seen that $p$ controls the tradeoff between the size of $B$, and the successful probability of sampling an element ($B \neq \emptyset$).

We begin with the assumption that the size of $\mathbb{Supp}(x)$ is known.

Insertion Only

As before, we consider insertion only model first.

Claim. There is an algorithm such that

1. with probability $1 - \delta$, it returns an element from $\mathbb{Supp}(x)$ uniformly at random;
2. with probability $\delta$, it returns nothing.

Further, the space usage is $O \left( \ln \frac{1}{\delta} \right)$ with probability at least $1 - \delta$.

For simplicity, we assume a perfect hash function $h$ that maps elements in $[n]$ to $\{0, 1\}$ independently with probability $p$ (to be determined). For each update $(t, \Delta)$ in the stream, we process it only if $h(t) = 1$. As we are dealing with insertion only model, we can use a hashset to maintain the elements with hash value 1.

Let $k = | \mathbb{Supp}(x) |$. As analysed before, with probability $(1 - p)^k$, the algorithm fails. To make the failure probability as small as $\delta$, we have that $(1 - p)^k = \delta$, i.e.,

The last inequality holds since the function $y = - \ln x$ is convex, and $y = 1 - x$ is the tangent line of $y = - \ln x$ at the point $(1, 0)$. By previous analysis, with probability at least $1 - \delta$, the size of $B$ is bounded by

Handling Deletion

When deletions are possible, we can't use a hashset to keep the sampled updates. E.g., suppose we have a sequence $(1, 6), (1, -6), (2, 5), (3, 7), (4, 9)$, and that $h(1) = h(2) = 1, h(3) = h(4) = 0$. We need a hashset of size 2 to keep both the frequencies of element 1 and element 2. Even through the frequency of element $1$ is 0 finally, we don't this before we see the entire string.

In general, $h$ maps $np$ elements in $[n]$ to $1$. If we use a hashset, its size can grow to $O(n p)$.

However, there is data structure that can handle deletions while using less than $O(np)$ space.

Sparse Recovery. Given an integer $d$ at the beginning of the stream, if $\mathbb{Supp}(x) \le d$ when the stream stops, there is a data structure that returns

1. indices in $\mathbb{Supp}(x)$;
2. and their values,

using $O(d (\log n + \log M) ) \subset O( d \log (nM) )$ bits. It processes each update $(t, \Delta)$ in the stream in $O(d)$ time and recovers $x$ in $O(d^2 polylog(nM))$ time. Its recovery can be wrong if $\mathbb{Supp}(x) > d$.

It suffices to use such a data structure for the sampled set $B$ with $d \in O( \ln \frac{1}{\delta} )$. We have seen that if we sampled each element in $\mathbb{Supp}(x)$ with probability $p = 1 - \delta^{1 / k}$, then with probability at least $1 - \delta$, we obtain a sampled set $B$ with size at most $d$. Then we return one element from $B$ uniformly at random.

Analyzing the probability of sampling an element is more subtle than the previous section. In previous section, each element is under-sampled with probability $\frac{1 - \left(1 - p \right)^k }{ k }$. Here, conditioned on $|B|\le d$, each element is sampled equally likely. However, $|B| > d$, the recovery of sampled elements fails, some element can be returned more frequently and some can be returned less frequently (the recovery behavior is un-defined). As the failure probability is bounded by $\delta$, each element is returned with probability

Sampling With UnKnown Support Size

Previously, we want to sample each element in $[n]$ with probability $1 - \delta^{ \frac{1}{k} } \le \ln \delta^{ \frac{1}{k} } = \frac{1}{k} \ln \frac{1}{\delta}$, where $k = | \mathbb{Supp}(x) |$. When this information is unavailable, we can guess by trying the values

We don't need to guess the value of $\frac{1}{k} \ln \frac{1}{\delta}$ exactly. In order that the sparse recovery data structure works, any guess within a constant factor suffices.

For simplicity, assume that $n$ is some power of $2$. Now, instead of using one sampling set $B$, we use $\log n + 2$ of them $B_1, B_2, B_3, ...$, each associated with a sparse recovery structure with parameter $d \in \Theta( \ln \frac{1}{\delta} )$. Assume that we have a perfect hash function $h: [n] \rightarrow [\log n + 2]$ such that it holds independently for every $t \in [n]$,

The distribution is well defined, as $\sum_{i \in [\log n + 1] } 1 / 2^i + 1 / 2^{ \log n + 1} = 1 - 1 / 2^{ \log n + 1} + 1 / 2^{ \log n + 1} = 1$.

If $k = 1$, some $B_i$ must recovers $x$ successfully.

Otherwise, $\exists i \in [\log n]$, such that $\frac{1}{2^i} \ge \frac{1}{k} \ln \frac{1}{\delta} > \frac{1}{2^{i + 1} }$. We study the following good events:

Event $E_1:$ for all $j \ge i$, it holds that $|\{ t \in \mathbb{Supp}(x) : h(t) = j \}| \le d$.

Under $E_1$, the sparse recovery structure associated with $B_j$ recovers $B_j$ successfully for all $j \ge i$.

Event $E_2:$ $|\{ t \in \mathbb{Supp}(x) : h(t) \ge i \}| > 0$.

Under $E_2$, there exists at least one element that is mapped to $B_j$ for some $j \ge i$.

Under these two good events, we sample one element as follows:

For $j \leftarrow \log n + 2$ downto $1$ do
$\qquad$ recover $B_j$;
$\qquad$ if $B_j \neq \emptyset$ then
$\qquad\qquad$ return one element from $B_j$ uniformly at random.

Analysis the probability of $E_1$:

For $j \ge i$, it holds that $\mathbb{E} [ |B_j| ] = k / 2^j$. Suppose that $d = 2 \cdot C_d \cdot \ln \frac{1}{\delta}$ for some constant $C_d$ (to be determined). Since $\frac{1}{k} \ln \frac{1}{\delta} \ge 1 / 2^{i + 1}$, we have that

By Chernoff bound,

By union bound, when $C_d \ge e^2$, it holds that

$\square$

Analysis the probability of $E_2$:

For each $t \in \mathbb{Supp}(x)$, we have

Therefore,

$\square$