Robust Streaming, Sampling, and a Perspective on Online Learning

Consider the following two-player game strategy between Adversary and algorithm. algorithm samples a matrix $A$ from a distribution $\mathcal{M}$. At each round, adversary submits $x_{t}\in\mathbb{R}^{n}$, and algorithm responds with evaluation function $F(A,Ax_{t})$. Adversary aims to learn the row space $R(A)$ of algorithm. If adversary can successfully learn $R(A)$, the following strategy will force algorithm to make mistakes on sufficiently many queries:

With $1/2$ probability, adversary submits the zero vector in $\mathbb{R}^{n}$. With $1/2$ probability, adversary submits a vector $x_{t}$ in the kernel space of $A$.

To learn the row space $R(A)$, Adversary’s initial element $x_{1}$ is drawn from $N(0,\tau I_{n})$, a mutivariate Gaussian distribution where $\tau I_{n}$ is the covariance matrix. From the properties of Gaussian variables, the projection of $x_{1}$ on Algorithm’s sketch matrix $A$ is spherically symmetric, and therefore the output will only depend on the the norm of projection $P_{A}(x_{1})$. If $x_{1}$ happens to have a high correlation with $R(A)$, algorithm will be tricked to calculate a larger estimation of $||P_{A}(x_{1})||_{2}$. [9] proved the existence of a $\tau$ to make the aforementioned difference sufficiently large.

Therefore, adversary can first submit multiple elements $x_{t}$ drawn from $N(0,\tau I_{n})$, and aggregate them into a vector $v_{1}\in\mathbb{R}^{n}$ that is almost entirely contained in $R(A)$. This is accomplished by aggregating $m=poly(n)$ positively-labeled vectors $x_{t}$ from the repeated trials into a matrix $G\in\mathbb{R}^{m\times n}$, and obtain $v_{1}$ as the top right singular vector of $G$. Then $||P_{A}(v_{1})||_{2}\geq 1-\frac{1}{poly(n)}$, and with a sufficiently large $m$ we can say $v_{1}$ is almost entirely contained in $R(A)$.

At each iteration of the previously attached scheme, after finding $v_{1}$ adversary draws $x_{t}$ from $N(0,\tau I_{n})$ within the subspace orthogonal to $\{v_{1},v_{2}\dots\}$ and runs the attack. This effectively reduces one ”unknown” dimension in $R(A)$ every time a new $v$ is found. Repeat the iterations until only a constant number of such unknown dimensions remain, and remaining attacks following the aforementioned strategy of switching between zero and kernel space vectors will trick algorithm to make a sufficiently large number of mistakes.

Assume a fixed, randomized algorithm following the robusification framework in Algorithm 1 with static streaming copies $A_{1},A_{2}\dots A_{\lambda}$, each with its own randomness. Assume a deterministic adversary for simplicity. By Yao’s minimax principle [20], this assumption can easily be relaxed to apply to randomized adversary. With this assumption, Adversary’s choice of $(a_{t},\Delta_{t})$ is deterministically defined by $((a_{1},\Delta_{1})\dots(a_{t-1},\Delta_{t_{1}})$ and responses $R_{1},R_{2}\dots R_{t-1}$.

The skeleton of the proof goes as follows: we first show that up until algorithm switches a copy of sketch, its return sequence $Y$ satisfies $(1+\epsilon)$-approximation of $g(f)$ at each time step, and inductively apply the same line of reasoning to each switching to $A_{\rho},\;\rho\in[\lambda]$. Union bounding the $\lambda$ copies of $(\epsilon/8,\delta/\lambda)$-strong $g$-tracking copies gives us the $1-\delta$ probability of success. And the remaining proof shows that $\lambda$ copies are indeed sufficient to handle adversarial input stream of length $m$.

Robustness of the first sketch. First fix the randomness of $A_{1}$. Let $u_{1}^{1},u_{2}^{1}\dots u_{k}^{1}$ be the $(a,\Delta)$ updates adversary would make if algorithm were to output $y_{0}=g(\textbf{0})$ to every $u$. That is, $u_{1}^{1},u_{2}^{1}\dots u_{k}^{1}$ is the sequence such that algorithm does not switch copy. Let $k+1$ be the time step that $y_{0}\notin(1\pm\epsilon/2)A_{1}(u_{k+1})$ (i.e. where $y_{0}$ falls out of range for the first time). Here algorithm returns $R_{1},R_{2}\dots R_{k}=y_{0}$ and $R_{k+1}=y_{1}$. By the definition of $(\epsilon/8,\delta/\lambda)$-strong g-tracking, we know that $A_{1}(u_{t})\in(1\pm\epsilon/8)g(f^{(t)})$ for $t\leq k$, and by design of Algorithm 1 $R_{t}=y_{0}\in(1\pm\epsilon/2)A_{1}(u_{t})$. By Lemma 2.2, we have

Induction on $A_{2}$. Following the definition above, algorithm switches to copy $A_{2}$ at time $t=k+1$. Here $R_{k+1}$, the output of algorithm, is updated to be $y_{1}=A_{1}(u_{k+1})$. Recall that by strong tracking, the switching point output $R_{k+1}=y_{1}\in(1\pm\epsilon/8)g(f^{(k+1)})$ by Definition 1.8. Consider $\hat{X}=\{u_{1}^{1},u_{2}^{1}\dots u_{k}^{1},u_{1}^{2},u_{2}^{2}\dots u_{k_{2}}^{2}\}$ be the concatenation between the aforementioned inputs and the stream of inputs such that algorithm will keep outputing $y_{1}$. Here $k_{2}$ is the index where $y_{1}$ starts to fall out of range. Given that the $\epsilon/8$-strong $g$-tracking guarantee should hold on this fixed size of input and, similar to above reasoning, have

Noted that this line of reasoning extends to any $A_{\rho}$ for $\rho\in[\lambda]$. Then at any time $t$, algorithm outputs $y_{\rho}\in(1\pm\epsilon)g(f^{(t)})$ except for probability $\frac{\delta}{\lambda}$. Taking a union bound over all copies of $A_{\rho}$, this gives us the desired $1-\delta$ probability in Theorem 2.3.

Consider the set system $(\mathcal{U},\mathcal{R})$ where $\mathcal{U}$ is a well-ordered set $\{1,2,\dots N\},\;\;N\in[n^{6ln\,n},2^{n/2}]$. Here $n$ is the size of adversarial input stream. Define $\mathcal{R}=\{[1,b]:\,b\in\mathcal{U}\}$ to be the set of inclusive intervals from 1 to each element of $\mathcal{U}$.

Observe that $(\mathcal{U},\mathcal{R})$ has VC-dimension $1$ (recall Definition 1.4 for definitions of VC-dimension and shattering). To see this, note that any subset $C\subset\mathcal{U}$ of size 1 can clearly be shattered (if $C=\{c\}$, $[1,c]$ describes $C$ for a positive label and $[1,c-1]$ describes $C$ for a negative label of $c$). So, the VC-dimension is certainly at least 1. However, consider any arbitrary set $C=\{c_{1},c_{2}\}\subset\mathcal{U}$ of size 2, and suppose without loss of generality that $c_{1}<c_{2}$. There exists a labeling of $C$ (namely, $c_{1}$ has a negative label but $c_{2}$ has a positive label) that no interval in $\mathcal{R}$ can describe (any interval not containing $c_{1}$ and satisfying its negative label cannot contain $c_{2}$). Similar logic shows that $\mathcal{R}$ cannot shatter any subset of $\mathcal{U}$ of size at least 2. Therefore, we must have $VCdim(\mathcal{R})<2\implies VCdim(\mathcal{R})=1$.

Here we consider a Bernoulli sampler $Ber(n,p)$ for the following adversarial scheme. It could be easily extended to the other aforementioned types of oblivious random sampling algorithms (e.g. the Reservoir sampler). Assume $p\leq\frac{1}{4}$, a reasonable assumption if the sampler is to obtain a sample size sublinear of a large input stream $X$.

A major difference in the analysis between the static setting and the adversarial setting here is the assumption of independence between elements in the input stream. Since adversary submits elements based on the history of elements submitted and the sample maintained, concentration inequalities like the Chernoff bound can not be applied in the adversarial setting. This motivates the formulation of random variables as a martingale. Given $R\subseteq\mathcal{U}$, for each round $i$ define $X_{i}$ and $R_{i}$ to be the input stream and sample maintained up until round $i$. Define the following random variables: