$|V_{1}-\mathbb{E}(V_{1})|$ and $|V_{2}|$. We will deal with $V_{2}$ first.
Define $S_{N}$ as the set of permutations on $\\{1,\dots,N\\}$ and
$N^{\prime}:=\lfloor N/2\rfloor$. Also define

$W_{i}(X_{i1},\dots,X_{iN}):=\frac{1}{N^{\prime}}\sum_{m=1}^{N^{\prime}}X_{i,2m-1}(j)X_{i,2m}(l)$

Then by symmetry (note that the inner sum over $m,s$ in the definition of
$V_{2}$ has $N(N-1)$ summands),

$V_{2}=\frac{\sum_{i=1}^{n}\sum_{\pi\in
S_{N}}W_{i}(X_{i,\pi(1)},\dots,X_{i,\pi(N)})}{N!}$

Define, for a given $\pi\in S_{N}$,

$Q_{\pi}:=\sum_{i=1}^{n}N^{\prime}W_{i}(X_{\pi(1)},\dots,X_{\pi(N)})$

so that $N^{\prime}V_{2}=\frac{1}{N!}\sum_{\pi\in S_{N}}Q_{\pi}$. For
arbitrary $t,s>0$, by Markov’s inequality and the convexity of the exponential
function,

$\mathbb{P}(N^{\prime}V_{2}\geq t)\leq
e^{-st}\mathbb{E}(e^{sN^{\prime}V_{2}})\leq e^{-st}\frac{\sum_{\pi\in
S_{N}}\mathbb{E}(e^{sQ_{\pi}})}{N!}$

Also, define $Q=Q_{\pi}$ for $\pi$ being the identity permutation. Observe
that

$Q=\sum_{i=1}^{n}\sum_{m=1}^{N^{\prime}}Q_{im}\quad\text{where
}Q_{im}=X_{i,2m-1}(j)X_{i,2m}(l)$

so $Q$ is a (double) summation of mutually independent variables. We have
$|Q_{im}|\leq 1$, $\mathbb{E}(Q_{im})=0$ and
$\mathbb{E}(Q^{2}_{im})\leq\tilde{h}_{j}\tilde{h}_{l}$. The rest of the proof
for $V_{2}$ is similar to the standard proof for the usual Bernstein’s
inequality and one can skip to the conclusion (51).

If we denote $G(x)=\frac{e^{x}-1-x}{x^{2}}$, observe $G(x)$ is increasing.
Hence,

$\displaystyle\mathbb{E}(e^{sQ_{im}})$
$\displaystyle=\mathbb{E}\left(1+sQ_{im}+\frac{s^{2}Q_{im}^{2}}{2}+\dots\right)$
$\displaystyle=\mathbb{E}[1+s^{2}Q_{im}^{2}G(sQ_{im})]$
$\displaystyle\leq\mathbb{E}[1+s^{2}Q_{im}^{2}G(s)]$ $\displaystyle\leq
1+s^{2}\tilde{h}_{j}\tilde{h}_{l}G(s)\leq
e^{s^{2}\tilde{h}_{j}\tilde{h}_{l}G(s)}$

Hence,

$e^{-st}\mathbb{E}(e^{sQ})=\exp(-st+N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}s^{2}G(s))$

Since this bound is applicable to all the other $Q_{\pi}$ and not just $\pi$
being equal to the identity permutation, we have

$\mathbb{P}(N^{\prime}V_{2}\geq
t)\leq\exp(-st+N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}s^{2}G(s))=\exp\left(-st+N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}(e^{s}-1-s)\right)$

Now we choose
$s=\log\left(1+\frac{t}{N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}}\right)>0$. Then

$\displaystyle\mathbb{P}(N^{\prime}V_{2}\geq t)$
$\displaystyle\leq\exp\left[-t\log\left(1+\frac{t}{N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}}\right)+N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}\left(\frac{t}{N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}}-\log\left(1+\frac{t}{N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}}\right)\right)\right]$
$\displaystyle=\exp\left[-N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}H\left(\frac{t}{N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}}\right)\right]$

where we define the function $H(x)=(1+x)\log(1+x)-x$. Note that we have the
inequality

$H(x)\geq\frac{3x^{2}}{6+2x}$

for all $x>0$. Hence,

$\mathbb{P}\left(N^{\prime}V_{2}\geq
t\right)\leq\exp\left(-\frac{t^{2}/2}{N^{\prime}n\tilde{h}_{j}\tilde{h}_{l}+t/3}\right)$

or by rescaling,

$\mathbb{P}(N^{\prime}V_{2}\geq
N^{\prime}nt)\leq\exp\left(-\frac{N^{\prime}nt^{2}/2}{\tilde{h}_{j}\tilde{h}_{l}+t/3}\right)$
(51)

We can choose $t^{2}=\frac{C^{*}\tilde{h}_{j}\tilde{h}_{l}}{N^{\prime}n}\log
p_{n}$ and note that
$\tilde{h}_{j}\tilde{h}_{l}\geq(\alpha_{+}\alpha)^{2}\frac{\log p_{n}}{nN}$ if
$j,l\in J_{+}$. Hence, with probability $1-o(p_{n}^{-1})$ (even after taking
union bound over $j,l\in J_{+}$),

$|V_{2}|\leq C^{*}\sqrt{\frac{n\tilde{h}_{j}\tilde{h}_{l}\log p_{n}}{N}}$

As for $V_{1}$, we can just apply the usual Bernstein’s inequality. Let
$\mu_{ij}=\mathbb{E}[T_{im}(j)]=[D_{0}]_{ji}$ and define $\mu_{il}$ similarly;
note $\mu_{ij}\leq\tilde{h}_{j}$. Since $X_{im}(j)=T_{im}(j)-\mu_{ij}$,

$X_{im}(j)X_{im}(l)=T_{im}(j)T_{im}(l)-\mu_{ij}T_{im}(l)-\mu_{il}T_{im}(j)+\mu_{ij}\mu_{il}$
(52)

If $j\neq l$ then $T_{im}(j)T_{im}(l)=0$ and so

$\displaystyle\text{Var}[X_{im}(j)X_{im}(l)]$
$\displaystyle=\text{Var}\left[\mu_{ij}T_{im}(l)+\mu_{il}T_{im}(j)\right]$
$\displaystyle\leq\mathbb{E}[\mu_{ij}T_{im}(l)+\mu_{il}T_{im}(j)]^{2}$
$\displaystyle=\mu_{ij}^{2}\mu_{il}+\mu_{il}^{2}\mu_{ij}=\mu_{ij}\mu_{il}(\mu_{ij}+\mu_{il})$
$\displaystyle\leq\mu_{ij}\mu_{il}\leq\tilde{h}_{j}\tilde{h}_{l}$

since $\mu_{ij}+\mu_{il}\leq 1$. Hence, by Bernstein’s inequality,

$\mathbb{P}\left(|V_{1}-\mathbb{E}(V_{1})|\geq t\right)\leq
2\exp\left(-\frac{-nNt^{2}/2}{\tilde{h}_{j}\tilde{h}_{l}+t/3}\right)$

which is similar to (51), so we obtain with probability $1-o(p_{n}^{-1})$ that

$\frac{n}{N}|V_{1}-\mathbb{E}(V_{1})|\leq\frac{C^{*}}{N}\sqrt{\frac{n\tilde{h}_{j}\tilde{h}_{l}\log
p_{n}}{N}}\leq C^{*}\sqrt{\frac{n\tilde{h}_{j}\tilde{h}_{l}\log p_{n}}{N}}$

and (49) is proven.

If $j=l$ then since $T_{im}^{2}(j)=T_{im}(j)$, (52) leads to

$X^{2}_{im}(j)=T_{im}(j)(1-2\mu_{ij})+\mu_{ij}^{2}$

and since $|1-2\mu_{ij}|\leq 1$ and
$\text{Var}(T_{im}(j))=\mu_{ij}(1-\mu_{ij})$,

$\text{Var}[X^{2}_{im}(j)]\leq\mu_{ij}\leq\tilde{h}_{j}$

and so we obtain (50) since with probability $1-o(p_{n}^{-1})$

$\frac{n}{N}|V_{1}-\mathbb{E}(V_{1})|\leq\frac{C^{*}}{N}\sqrt{\frac{n\tilde{h}_{j}\log
p_{n}}{N}}$

###### Corollary C.5

With probability $1-o(p_{n}^{-1})$, the following statements hold:

$\|[ZW_{k}]_{J_{+}}\|_{2}\leq C^{*}\sqrt{\frac{nK\log p_{n}}{N}}\text{ for all
}1\leq k\leq K$ (53) $\|[ZZ^{T}-\mathbb{E}(ZZ^{T})]_{jJ_{+}}\|_{2}\leq
C^{*}\sqrt{\frac{n\tilde{h}_{j}K\log p_{n}}{N}}\text{ for all }j\in J_{+}$
(54) $\|[ZZ^{T}-\mathbb{E}(ZZ^{T})]_{J_{+}J_{+}}\|_{F}\leq
C^{*}K\sqrt{\frac{n\log p_{n}}{N}}$ (55)

Proof  This follows from (47), (49) and (50) after squaring the error bounds
and summing them up. We note that $\sum_{j\in
J_{+}}\tilde{h}_{j}\leq\sum_{j=1}^{p}h_{j}=K$.

##  Appendix D Estimation errors for singular vectors and the point cloud

We will use the following theorem (a row-wise perturbation bound for
eigenvectors) from Ke and Wang (2022).

######  Lemma D.1 (Lemma F.1 of Ke and Wang (2022))

Let $B_{0}$ and $B$ be $m\times m$ symmetric matrices with
$\text{rank}(B_{0})=K$, and assume $B_{0}$ is positive semi-definite. For
$1\leq k\leq K$, let $\delta_{k}^{0}$ and $\delta_{k}$ be the $k^{\text{th}}$
largest eigenvalues of $B_{0}$ and $B$ respectively, and let $u_{k}^{0}$ and
$u_{k}$ be the $k^{\text{th}}$ eigenvectors of $B_{0}$ and $B$. Fix $1\leq
s\leq k\leq K$. If for some $c\in(0,1)$, suppose (by default, if $s=1$ then
$\delta_{s-1}^{0}-\delta_{s}^{0}=\infty$)

$\min(\delta_{s-1}^{0}-\delta_{s}^{0},\delta_{k}^{0}-\delta_{k+1}^{0},\min_{l\in[K]}\delta_{l}^{0})\geq
c\|B_{0}\|_{\text{op}},\quad\|B-B_{0}\|_{\text{op}}\leq(c/3)\|B_{0}\|_{\text{op}}$

Write $U_{0}=[u_{s}^{0},\dots,u_{k}^{0}],U=[u_{s},\dots u_{k}]$ and
$\Xi=[u_{1}^{0},\dots,u_{K}^{0}]$. There exists an orthonormal matrix $O$ such
that for all $1\leq j\leq p$,

$\|(UO-
U_{0})_{j*}\|_{2}\leq\frac{5}{c\|B_{0}\|_{\text{op}}}(\|B-B_{0}\|_{\text{op}}\|\Xi_{j*}\|_{2}+\sqrt{K}\|(B-B_{0})_{j*}\|_{2})$

If we define

$G:=DD^{T}-\frac{n}{N}M$ $G_{0}:=\left(1-\frac{1}{N}\right)D_{0}D_{0}^{T}$

then the above lemma can be applied to the submatrices $G_{JJ}$ and
$[G_{0}]_{JJ}$ (see Lemma D.7).

###### Lemma D.2

With probability $1-o(p_{n}^{-1})$, we have

$\|(G-G_{0})_{J_{+}J_{+}}\|_{\text{op}}\leq C^{*}K\sqrt{\frac{nK\log
p_{n}}{N}}$

and for any $j\in J_{+}$, row $j$ of $(G-G_{0})_{J_{+}J_{+}}$ has $\ell_{2}$
norm satisfying

$\|(G-G_{0})_{jJ_{+}}\|_{2}\leq C^{*}K\sqrt{\frac{nh_{j}\log p_{n}}{N}}$

Proof  From basic properties of the multinomial distribution, we can show that

$\mathbb{E}(ZZ^{T})=\sum_{i=1}^{n}\text{Cov}(Z_{*i})=\sum_{i=1}^{n}\text{Cov}(D_{*i})=\frac{n}{N}M_{0}-\frac{1}{N}D_{0}D_{0}^{T}$

and therefore

$\displaystyle G-G_{0}$
$\displaystyle=DD^{T}-\frac{n}{N}M-\left(1-\frac{1}{N}\right)D_{0}D_{0}^{T}$
$\displaystyle=(D_{0}+Z)(D_{0}+Z)^{T}-\frac{n}{N}M-\left(1-\frac{1}{N}\right)D_{0}D_{0}^{T}$
$\displaystyle=ZD_{0}^{T}+D_{0}Z^{T}+ZZ^{T}-\frac{n}{N}M+\frac{1}{N}D_{0}D_{0}^{T}$
$\displaystyle=ZD_{0}^{T}+D_{0}Z^{T}+(ZZ^{T}-\mathbb{E}[ZZ^{T}])+\frac{n}{N}(M_{0}-M)$

and so we can write $(G-G_{0})_{J_{+}J_{+}}=E_{1}+E_{2}+E_{3}$ where

$E_{1}:=(ZD_{0}^{T}+D_{0}Z^{T})_{J_{+}J_{+}}$
$E_{2}:=(ZZ^{T}-\mathbb{E}[ZZ^{T}])_{J_{+}J_{+}}$
$E_{3}:=\frac{n}{N}(M_{0}-M)_{J_{+}J_{+}}$

We can deal with $E_{3}$ first. From (45), with probability $1-o(p_{n}^{-1})$
we have

$\|E_{3}\|_{\text{op}}\leq\frac{C^{*}n}{N}\sqrt{\frac{(\max_{j\in
J_{+}}\tilde{h}_{j})\log p_{n}}{nN}}\leq\frac{C^{*}}{N}\sqrt{\frac{n\log
p_{n}}{N}}$

and for any $j\in J_{+}$,

$\|[E_{3}]_{j*}\|_{2}=\frac{n}{N}|M(j,j)-M_{0}(j,j)|\leq\frac{C^{*}}{N}\sqrt{\frac{n\tilde{h}_{j}\log
p_{n}}{N}}$

From (54) and (55), with probability $1-o(p_{n}^{-1})$

$\|E_{2}\|_{\text{op}}\leq\|E_{2}\|_{F}\leq C^{*}K\sqrt{\frac{n\log
p_{n}}{N}}$ $\|[E_{2}]_{j*}\|_{2}\leq C^{*}\sqrt{\frac{n\tilde{h}_{j}K\log
p_{n}}{N}}$

If we denote $A_{1},\dots,A_{K}$ as the columns of $A$ and $W_{1},\dots,W_{k}$
as the rows of $W$,

$D_{0}Z^{T}=\sum_{k=1}^{K}A_{k}(ZW_{k})^{T}$

and so from (53) and the fact that
$\sum_{k=1}^{K}\|A_{k}\|_{2}\leq\sum_{k=1}^{K}\|A_{k}\|_{1}\leq K$,

$\|E_{1}\|_{\text{op}}\leq 2\|[D_{0}Z^{T}]_{J_{+}J_{+}}\|_{\text{op}}\leq
2\sum_{k=1}^{K}\|A_{k}\|_{2}\|Z_{J_{+}*}W_{k}\|_{2}\leq
C^{*}K\sqrt{\frac{nK\log p_{n}}{N}}$

Let $Z_{1},\dots,Z_{p}$ denote the rows of $Z$. From (47), (53) and the fact
that $\sum_{k=1}^{K}A_{k}(j)=h_{j}$ and $h_{j}\leq K$, for any $j\in J_{+}$:

$\displaystyle\|[E_{1}]_{j*}\|_{2}$
$\displaystyle\leq\sum_{k=1}^{K}A_{k}(j)\|Z_{J_{+}*}W_{k}\|_{2}+\sum_{k=1}^{K}|Z_{j}^{T}W_{k}|\|A_{k}\|_{2}$
$\displaystyle\leq C^{*}h_{j}\sqrt{\frac{nK\log
p_{n}}{N}}+C^{*}K\sqrt{\frac{n\tilde{h}_{j}\log p_{n}}{N}}$ $\displaystyle\leq
C^{*}K\sqrt{\frac{nh_{j}\log p_{n}}{N}}$

Since the bounds for $\|E_{1}\|_{\text{op}}$ and $\|[E_{1}]_{j*}\|_{2}$
dominate those for $E_{2}$ and $E_{3}$, our result follows.

###### Lemma D.3

With probability $1-o(p_{n}^{-1})$, we also have

$\|(G-G_{0})_{JJ}\|_{\text{op}}\leq C^{*}K\sqrt{\frac{nK\log p_{n}}{N}}$ (56)

and for any $j\in J$,

$\|(G-G_{0})_{jJ}\|_{2}\leq C^{*}K\sqrt{\frac{nh_{j}\log p_{n}}{N}}$ (57)

Proof  This is simply a consequence of the previous lemma and the fact that
$J\subseteq J_{+}$ with probability $1-o(p_{n}^{-1})$, which implies that
$(G-G_{0})_{JJ}$ is a submatrix of $(G-G_{0})_{J_{+}J_{+}}$. Note that we
refrain from applying the argument of the previous lemma directly to
$(G-G_{0})_{JJ}$, since $J$ and $Z$ are not independent (whereas $J_{+}$ is a
non-random index set).

###### Corollary D.4

Let $g_{n}$ be a quantity satisfying

$c\sqrt{\frac{nN}{\log p_{n}}}\geq g_{n}\geq C^{*}K\sqrt{K}$ (58)

where $C^{*}$ in (58) is the constant from (56) and $c$ is another constant to
be determined. If

$\hat{K}:=\max\left\\{k:\lambda_{k}(G_{JJ})>g_{n}\sqrt{\frac{n\log
p_{n}}{N}}\right\\}$

then $\hat{K}=K$ with probability $1-o(p_{n}^{-1})$.

Proof  We have shown in Lemma A.3(e) that $[G_{0}]_{JJ}$ has rank $K$ on
$\mathcal{E}$. By Weyl’s inequality,

$\lambda_{K+1}(G_{JJ})\leq\|(G-G_{0})_{JJ}\|_{\text{op}}\leq
C^{*}K\sqrt{K}\sqrt{\frac{n\log p_{n}}{N}}\leq g_{n}\sqrt{\frac{n\log
p_{n}}{N}}$

This implies $\hat{K}\leq K$. On the other hand, again by Weyl’s inequality,

$|\lambda_{K}(G_{JJ})-\lambda_{K}([G_{0}]_{JJ})|\leq
C^{*}K\sqrt{K}\sqrt{\frac{n\log p_{n}}{N}}\leq g_{n}\sqrt{\frac{n\log
p_{n}}{N}}$

and since $G_{0}:=\left(1-\frac{1}{N}\right)D_{0}D_{0}^{T}$, by our assumption
that $\sigma_{K}(A)\geq c\sqrt{K}$ and $\sigma_{K}(\Sigma_{W})\geq c$,

$\lambda_{K}([G_{0}]_{JJ})\geq\left(1-\frac{1}{N}\right)\sigma_{K}^{2}(A_{J*})\sigma_{K}^{2}(W)\geq
cKn>2g_{n}\sqrt{\frac{n\log p_{n}}{N}}$

when $nN$ is sufficiently large and $c$ in (58) is chosen appropriately.
Hence,

$\lambda_{K}(G_{JJ})\geq\lambda_{K}([G_{0}]_{JJ})-|\lambda_{K}(G_{JJ})-\lambda_{K}([G_{0}]_{JJ})|>g_{n}\sqrt{\frac{n\log
p_{n}}{N}}$

and thus $K\leq\hat{K}$ with probability $1-o(p_{n}^{-1})$.

Recall that $\hat{\Xi}$ contains the first $K$ eigenvectors of $G_{JJ}$ and
$\Xi$ contains the first $K$ left singular vectors of $[D_{0}]_{J*}$, or
equivalently the first $K$ eigenvectors of $[G_{0}]_{JJ}$. We will provide a
coordinate-wise error bound for $\hat{\Xi}$ in Lemma D.7. First we need a few
lemmas.

###### Lemma D.5

For any $j\in J$, $\|\Xi_{j*}\|_{2}\leq Ch_{j}$.

Proof  Note $\Xi=A_{J*}V$ so $\Xi_{j*}=A_{j*}V$. Hence,

$\|\Xi_{j*}\|_{2}\leq\|V\|_{\text{op}}\|A_{j*}\|_{2}\leq\|V\|_{\text{op}}\|A_{j*}\|_{1}\leq\sigma_{K}^{-1}(A)h_{j}\leq
Ch_{j}$

since we have shown before that the singular values of $V$ are just the
inverses of the singular values of $A_{J*}$.
Note that on event $\mathcal{E}$, $[D_{0}]_{J*}$ and hence $[G_{0}]_{JJ}$ has
rank $K$.

###### Lemma D.6

On event $\mathcal{E}$,

$cnK\leq\lambda_{k}([G_{0}]_{JJ})\leq nK\text{ for all }k\in[K]\text{ and
}\lambda_{1}([G_{0}]_{JJ})\geq cn+\max_{2\leq k\leq
K}\lambda_{k}([G_{0}]_{JJ})$

Proof  We note that
$[D_{0}D_{0}^{T}]_{JJ}=A_{J*}WW^{T}A_{J*}^{T}=nA_{J*}\Sigma_{W}A_{J*}^{T}$.
Hence,

$\lambda_{1}([G_{0}]_{JJ})\leq
n\|A\|_{\text{op}}^{2}\|\Sigma_{W}\|_{\text{op}}\leq nK$
$\lambda_{K}([G_{0}]_{JJ})\geq
n[\sigma_{K}(A_{J*})]^{2}\sigma_{K}(\Sigma_{W})\geq
n[\sigma_{K}(A)]^{2}\sigma_{K}(\Sigma_{W})\geq cnK$

We also note that for any two matrices $P$ and $Q$, the nonzero eigenvalues of
$PQ$ are the same as those of $QP$. Thus the nonzero eigenvalues of
$[D_{0}D_{0}^{T}]_{JJ}$ are the same as the nonzero eigenvalues of
$WW^{T}A_{J*}^{T}A_{J*}=:n\Theta$. We have already shown in Lemma B.1(d) that
the gap between the first two eigenvalues of $\Theta$ are at least an absolute
constant on $\mathcal{E}$. Hence, our result follows.

######  Lemma D.7 (Row-wise estimation error for $\hat{\Xi}$)

Denote $\\{\Xi_{j}:j\in J\\}$ as the rows of $\Xi$ and $\\{\hat{\Xi}_{j}:j\in
J\\}$ as the rows of $\hat{\Xi}$. With probability $1-o(p_{n}^{-1})$, there
exist $\omega\in\\{\pm 1\\}$ and an orthonormal matrix
$\Omega^{*}\in\mathbb{R}^{(K-1)\times(K-1)}$ such that, if
$\Omega:=\text{diag}(\omega,\Omega^{*})\in\mathbb{R}^{K\times K}$, we have

$\|\Omega\hat{\Xi}_{j}-\Xi_{j}\|_{2}\leq C\sqrt{\frac{h_{j}\log
p_{n}}{nN}}\quad\text{for all }j\in J$

Proof  Let $\hat{\xi}_{1}$ and $\xi_{1}$ be the first eigenvectors of
$[G]_{JJ}$ and $[G_{0}]_{JJ}$ respectively. The gap between the first two
eigenvalues of $[G_{0}]_{JJ}$ is at least $cn$, which is much greater than
$C^{*}K\sqrt{\frac{nK\log p_{n}}{N}}$ (the high-probability bound on
$\|(G-G_{0})_{JJ}\|_{\text{op}}$). By applying Lemma D.1, there exists
$\omega\in\\{\pm 1\\}$ such that with probability $1-o(p_{n}^{-1})$, for all
$j\in J$,

$\displaystyle|\omega\hat{\xi}_{1}(j)-\xi_{1}(j)|$ $\displaystyle\leq
C\frac{h_{j}\|(G-G_{0})_{JJ}\|_{\text{op}}+\sqrt{K}\|(G-G_{0})_{jJ}\|_{2}}{n}$
$\displaystyle\leq C\frac{h_{j}\sqrt{\frac{n\log
p_{n}}{N}}+\sqrt{\frac{nh_{j}\log p_{n}}{N}}}{n}$ $\displaystyle\leq
C\sqrt{\frac{h_{j}\log p_{n}}{nN}}$

where we applied $h_{j}\leq K$.

Let $\Xi^{*}=[\xi_{2},\dots,\xi_{K}]$ contain the other $(K-1)$ eigenvectors
of $[G_{0}]_{JJ}$, and define $\hat{\Xi}^{*}$ similarly. Again, since the
smallest nonzero eigenvalue of $[G_{0}]_{JJ}$ is at least $cnK$, there exists
an orthonormal matrix $\Omega^{*}\in\mathbb{R}^{(K-1)\times(K-1)}$ such that
for all $j\in J$,

$\|(\hat{\Xi}^{*}\Omega^{*}-\Xi^{*})_{j*}\|_{2}\leq C\sqrt{\frac{h_{j}\log
p_{n}}{nN}}$

We then define $\Omega=\text{diag}(\omega,\Omega^{*})$ and combine the above
results.

######  Lemma D.8 (Estimation error for the point cloud)

With probability $1-o(p_{n}^{-1})$, all entries of $\hat{\xi}_{1}$ have the
same sign and there exists an orthonormal matrix
$\Omega^{*}\in\mathbb{R}^{(K-1)\times(K-1)}$ such that

$\displaystyle\max_{j\in J}\|\Omega^{*}\hat{r}_{j}-r_{j}\|_{2}\leq
C\left(\frac{\log p_{n}}{nN}\right)^{1/4}$

Proof  First, we note that WLOG, we can assume $\omega=1$. This is because
from the previous lemma, for any $j\in J$, since $h_{j}\geq c\sqrt{\frac{\log
p_{n}}{nN}}$,

$|\omega\hat{\xi}_{1}(j)-\xi_{1}(j)|\leq C\sqrt{\frac{h_{j}\log
p_{n}}{nN}}\leq Ch_{j}\left(\frac{\log p_{n}}{nN}\right)^{1/4}$

whereas we also know from Lemma B.1(e) that

$\xi_{1}(j)>ch_{j}>0$

We can see that $|\omega\hat{\xi}_{1}(j)-\xi_{1}(j)|\ll\xi_{1}(j)$ with high
probability as $nN$ is sufficiently large, and this implies
$\omega\hat{\xi}_{1}(j)\geq\xi_{1}(j)/2$. If $\hat{\xi}_{1}$ is defined such
that the majority of its entries are positive (and in fact its entries are all
of the same sign with high probability), we can simply assume $\omega=1$ from
now on.

Denote $\\{\Xi_{j}:j\in J\\}$ as the rows of $\Xi$ and $\\{\hat{\Xi}_{j}:j\in
J\\}$ as the rows of $\hat{\Xi}$. Now, since by definition,

$\begin{pmatrix}1\\\
r_{j}\end{pmatrix}=[\xi_{1}(j)]^{-1}\Xi_{j},\quad\begin{pmatrix}1\\\
\Omega^{*}\hat{r}_{j}\end{pmatrix}=[\hat{\xi}_{1}(j)]^{-1}\Omega\hat{\Xi}_{j}$

it follows that

$\displaystyle\|\Omega^{*}\hat{r}_{j}-r_{j}\|_{2}$
$\displaystyle=\left\|\frac{1}{\hat{\xi}_{1}(j)}\Omega\hat{\Xi}_{j}-\frac{1}{\xi_{1}(j)}\Xi_{j}\right\|_{2}$
$\displaystyle=\left\|\frac{1}{\hat{\xi}_{1}(j)}(\Omega\hat{\Xi}-\Xi_{j})-\frac{\hat{\xi}_{1}(j)-\xi_{1}(j)}{\hat{\xi}_{1}(j)}r_{j}\right\|_{2}$
$\displaystyle\leq|\hat{\xi}_{1}(j)|^{-1}(\|\Omega\hat{\Xi}_{j}-\Xi_{j}\|_{2}+\|r_{j}\|_{2}|\hat{\xi}_{1}(j)-\xi_{1}(j)|)$

We have noted in Lemma B.2 that the point cloud $\\{r_{j}:j\in J\\}$ lies
entirely in the convex hull of $v_{1}^{*},\dots,v_{K}^{*}$, and Lemma B.1(f)
shows that $\max_{k\in[K]}\|v_{k}^{*}\|_{2}\leq C$, so we also have
$\max_{j\in J}\|r_{j}\|_{2}\leq C$. We have also noted before that

$\hat{\xi}_{1}(j)\geq\frac{\xi_{1}(j)}{2}>ch_{j}$

with high probability. Therefore, with probability $1-o(p_{n}^{-1})$, for all
$j\in J$:

$\displaystyle\|\Omega^{*}\hat{r}_{j}-r_{j}\|_{2}$ $\displaystyle\leq
C\sqrt{\frac{\log p_{n}}{h_{j}nN}}$ $\displaystyle\leq C\left(\frac{\log
p_{n}}{nN}\right)^{1/4}$

since $\min_{j\in J}h_{j}\geq c\sqrt{\frac{\log p_{n}}{nN}}$ with probability
$1-o(p_{n}^{-1})$.

###### Lemma D.9

If we denote the rows of $\hat{\Pi}$ from our proposed procedure as
$\\{\hat{\pi}_{j}:j\in J\\}$ and the rows of $\Pi$ from the oracle procedure
as $\\{\pi_{j}:j\in J\\}$, then with probability $1-o(p_{n}^{-1})$,

$\max_{j\in J}\|\hat{\pi}_{j}-\pi_{j}\|_{1}\leq C\left(\frac{\log
p_{n}}{nN}\right)^{1/4}$

Proof  Recall that $\hat{\pi}_{j}^{\diamond}\in\mathbb{R}^{K}$ is the
unnormalized vector solving

$\begin{pmatrix}1&\dots&1\\\
\hat{v}_{1}^{*}&\dots&\hat{v}_{K}^{*}\end{pmatrix}\hat{\pi}_{j}^{\diamond}=\begin{pmatrix}1\\\
\hat{r}_{j}\end{pmatrix}\iff\begin{pmatrix}1&\dots&1\\\
\Omega^{*}\hat{v}_{1}^{*}&\dots&\Omega^{*}\hat{v}_{K}^{*}\end{pmatrix}\hat{\pi}_{j}^{\diamond}=\begin{pmatrix}1\\\
\Omega^{*}\hat{r}_{j}\end{pmatrix}$

Therefore,

$\hat{\pi}_{j}^{\diamond}=\hat{Q}^{-1}\begin{pmatrix}1\\\
\Omega^{*}\hat{r}_{j}\end{pmatrix}\quad\text{where}\quad\hat{Q}:=\begin{pmatrix}1&\dots&1\\\
\Omega^{*}\hat{v}_{1}^{*}&\dots&\Omega^{*}\hat{v}_{K}^{*}\end{pmatrix}$

We also have

$\pi_{j}=Q^{-1}\begin{pmatrix}1\\\ r_{j}\end{pmatrix}\quad\text{where
}Q=\begin{pmatrix}1&\dots&1\\\ v_{1}^{*}&\dots&v_{K}^{*}\end{pmatrix}$

Consequently,

$\|\hat{\pi}_{j}^{\diamond}-\pi_{j}\|_{2}\leq\|\hat{Q}^{-1}\|_{\text{op}}\|\Omega^{*}\hat{r}_{j}-r_{j}\|_{2}+\|\hat{Q}^{-1}-Q^{-1}\|_{\text{op}}\sqrt{\|r_{j}\|_{2}^{2}+1}$

Note that $\max_{j\in J}\|r_{j}\|_{2}\leq C$ since the $r_{j}$’s are in the
convex hull of $v_{1}^{*},\dots,v_{K}^{*}$. Also, since
$Q^{T}=[\text{diag}(V_{1})]^{-1}V$, we have $\|Q^{-1}\|_{\text{op}}\leq C$
since

$\max_{k\in[K]}V_{1}(k)\leq\frac{C}{\sqrt{K}}\quad\text{and}\quad\|V^{-1}\|_{\text{op}}=\sigma_{1}(A)\leq\sqrt{K}$

Now, we note that with probability $1-o(p_{n}^{-1})$,

$\displaystyle\|\hat{Q}-Q\|_{\text{op}}\leq\|\hat{Q}-Q\|_{F}$
$\displaystyle\leq\sqrt{K}\max_{k\in[K]}\|\Omega^{*}\hat{v}_{k}^{*}-v_{k}^{*}\|_{2}$
$\displaystyle\leq\sqrt{K}\max_{j\in J}\|\Omega^{*}\hat{r}_{j}-r_{j}\|_{2}\leq
C\left(\frac{\log p_{n}}{nN}\right)^{1/4}=o(1)$

where we used Assumption 4, since in the oracle procedure the vertex hunting
algorithm correctly returns $v_{1}^{*},\dots,v_{K}^{*}$. Therefore,

$\|\hat{Q}^{-1}-Q^{-1}\|_{\text{op}}=\|\hat{Q}^{-1}(Q-\hat{Q})Q^{-1}\|_{\text{op}}\leq\|\hat{Q}^{-1}\|_{\text{op}}\|\hat{Q}-Q\|_{\text{op}}\|Q\|^{-1}_{\text{op}}\leq
C\left(\frac{\log p_{n}}{nN}\right)^{1/4}$

Here we note
$\sigma_{K}(\hat{Q})\geq\sigma_{K}(Q)-\|\hat{Q}-Q\|_{\text{op}}\geq c-o(1)\geq
c/2$ if $nN$ is large enough, so $\|\hat{Q}^{-1}\|_{\text{op}}\leq C$.
Therefore, we obtain

$\|\hat{\pi}_{j}^{\diamond}-\pi_{j}\|_{2}\leq C\left(\frac{\log
p_{n}}{nN}\right)^{1/4}$

Now if we define
$\hat{\pi}_{j}=\frac{\tilde{\pi}_{j}^{\diamond}}{\|\tilde{\pi}_{j}^{\diamond}\|_{1}}$
where $\tilde{\pi}_{j}^{\diamond}(k)=\max(\hat{\pi}_{j}^{\diamond}(k),0)$,
then since $\|\hat{\pi}_{j}\|_{1}=\|\pi_{j}\|_{1}=1$,

$\displaystyle\|\hat{\pi}_{j}-\pi_{j}\|_{1}$
$\displaystyle\leq\|\hat{\pi}_{j}-\tilde{\pi}_{j}^{\diamond}\|_{1}+\|\tilde{\pi}_{j}^{\diamond}-\pi_{j}\|_{1}$
$\displaystyle=|1-\|\tilde{\pi}_{j}^{\diamond}\|_{1}|\|\hat{\pi}_{j}\|_{1}+\|\tilde{\pi}_{j}^{\diamond}-\pi_{j}\|_{1}$
$\displaystyle=|\|\pi_{j}|_{1}-\|\tilde{\pi}_{j}^{\diamond}\|_{1}|+\|\tilde{\pi}_{j}^{\diamond}-\pi_{j}\|_{1}$
$\displaystyle\leq 2\|\pi_{j}-\tilde{\pi}_{j}^{\diamond}\|_{1}$
$\displaystyle\leq 2\|\pi_{j}-\hat{\pi}_{j}^{\diamond}\|_{1}\leq
2\sqrt{K}\|\hat{\pi}_{j}^{\diamond}-\pi_{j}\|_{2}$ $\displaystyle\leq
C\left(\frac{\log p_{n}}{nN}\right)^{1/4}$

##  Appendix E Estimation error of $\hat{A}$

In this section, we will additionally impose the $\ell_{q}$-sparsity
assumption (19) for $q\in(0,1)$.

###### Lemma E.1

Under Assumption 5, if
$\beta:=\frac{\alpha_{-}\alpha}{\sigma_{K}(\Sigma_{W})}$ and
$\tau_{n}:=\sqrt{\frac{\log p_{n}}{nN}}$, on event $\mathcal{E}$

$\|A_{J^{c}*}\|_{1}\leq\frac{K}{1-q}s(\beta\tau_{n})^{1-q}$ (59)

###### Remark 11

We assume from now on that $s$ does not grow too quickly relative to $nN$ so
that the RHS of (59) is $o(1)$.

Proof  On event $\mathcal{E}$ we have $J_{-}\subseteq J$, so $j\notin J$
implies $M_{0}(j,j)\leq\alpha_{-}\alpha\tau_{n}$ where
$\tau_{n}:=\sqrt{\frac{\log p_{n}}{nN}}$. Since
$\sigma_{K}(\Sigma_{W})h_{j}\leq M_{0}(j,j)$, $j\notin J$ implies $A_{jk}\leq
h_{j}\leq\beta\tau_{n}$ for any $k\in[K]$ on $\mathcal{E}$. Then with
probability $1-o(p_{n}^{-1})$, for any $k\in[K]$,

$\displaystyle\|A_{J^{c}k}\|_{1}$ $\displaystyle=\sum_{j\not\in
J}\min(A_{jk},\beta\tau_{n})\leq\sum_{j=1}^{p}\min(A_{(j)k},\beta\tau_{n})$
$\displaystyle\leq\sum_{j=1}^{p}\min(s^{1/q}j^{-1/q},\beta\tau_{n})\leq\int_{0}^{\infty}\min(s^{1/q}t^{-1/q},\beta\tau_{n})dt$

Now, let $t_{0}:=s(\beta\tau_{n})^{-q}$ so that
$s^{1/q}t_{0}^{-1/q}=\beta\tau_{n}$. Then continuing from the above display,

$\displaystyle\|A_{J^{c}k}\|_{1}$ $\displaystyle\leq
t_{0}\beta\tau_{n}+s^{1/q}\int_{t_{0}}^{\infty}t^{-1/q}dt$
$\displaystyle=t_{0}\beta\tau_{n}+\frac{q}{1-q}s^{1/q}t_{0}^{1-1/q}=\frac{1}{1-q}t_{0}\beta\tau_{n}$
$\displaystyle=\frac{1}{1-q}s(\beta\tau_{n})^{1-q}$

and the result follows by summing up this bound across $k\in[K]$. Note that
the assumption $q\in(0,1)$ ensures the integrals above converge.

###### Lemma E.2

On event $\mathcal{E}$, if $\tilde{A}_{J*}$ is defined as in (41),

$\|\tilde{A}_{J*}-A_{J*}\|_{1}=\|A_{J^{c}*}\|_{1}\leq\frac{K}{1-q}s(\beta\tau_{n})^{1-q}$
(60)

Proof  We note that the columns of $\tilde{A}_{J*}$ sum up to 1, the columns
of $A$ sum up to 1, and as a result of the definition of $\tilde{A}_{J*}$ in
(41),

$\tilde{A}_{J*}-A_{J*}=\tilde{A}_{J*}\cdot\text{diag}(\|A_{J^{c}1}\|_{1},\dots,\|A_{J^{c}K}\|_{1})$

Then $\|\tilde{A}_{J*}-A_{J*}\|_{1}=\|A_{J^{c}*}\|_{1}$ and our result follows
from the previous lemma.

###### Theorem E.3

With probability $1-o(p_{n}^{-1})$, for some constant $C$ that may depend on
$K$ and $q$, we have

$\|\hat{A}-A\|_{1}\leq C\left[\left(\frac{\log
p_{n}}{nN}\right)^{1/4}+s\left(\frac{\log
p_{n}}{nN}\right)^{\frac{1-q}{2}}\right]$

Proof  Consider the unnormalized matrices

$\hat{A}_{J*}^{\diamond}:=\text{diag}(\hat{\xi}_{1})\hat{\Pi}\quad\text{and}\quad\tilde{A}_{J*}^{\diamond}:=\text{diag}(\xi_{1})\Pi$

Then with probability $1-o(p_{n}^{-1})$, for any $j\in J$,

$\displaystyle\|(\hat{A}^{\diamond}-\tilde{A}^{\diamond})_{j*}\|_{1}$
$\displaystyle=\|\hat{\xi}_{1}(j)\hat{\pi}_{j}-\xi_{1}(j)\pi_{j}\|_{1}$
$\displaystyle\leq|\hat{\xi}_{1}(j)|\|\hat{\pi}_{j}-\pi_{j}\|_{1}+|\hat{\xi}_{1}(j)-\xi_{1}(j)|\|\pi_{j}\|_{1}$
$\displaystyle\leq C\left[h_{j}\left(\frac{\log
p_{n}}{nN}\right)^{1/4}+\sqrt{\frac{h_{j}\log p_{n}}{nN}}\right]$
$\displaystyle\leq Ch_{j}\left(\frac{\log p_{n}}{nN}\right)^{1/4}$ (61)

where again we note that on event $\mathcal{E}$,
$h_{j}>\alpha_{+}\alpha\sqrt{\frac{\log p_{n}}{nN}}$ if $j\in J$. Since
$\sum_{j=1}^{p}h_{j}=K$, with probability $1-o(p_{n}^{-1})$,

$\|\hat{A}_{J*}^{\diamond}-\tilde{A}_{J*}^{\diamond}\|_{1}\leq
C\left(\frac{\log p_{n}}{nN}\right)^{1/4}=o(1)$ (62)

Now, $\hat{A}_{J*}$ and $\tilde{A}_{J*}$ are defined by normalizing the
columns of $\hat{A}_{J*}^{\diamond}$ and $\tilde{A}_{J*}^{\diamond}$, so we
have for each $j\in J$ and $k\in[K]$

$\hat{A}_{jk}=\frac{\hat{A}_{jk}^{\diamond}}{\|\hat{A}_{Jk}^{\diamond}\|_{1}}\quad\text{and}\quad\tilde{A}_{jk}=\frac{\tilde{A}_{jk}^{\diamond}}{\|\tilde{A}_{Jk}^{\diamond}\|_{1}}=\frac{A_{jk}}{\|A_{Jk}\|_{1}}$

Therefore, for each $j\in J$ and $k\in[K]$,

$\displaystyle|\hat{A}_{jk}-\tilde{A}_{jk}|$
$\displaystyle=\left|\frac{\hat{A}_{jk}^{\diamond}}{\|\hat{A}_{Jk}^{\diamond}\|_{1}}-\frac{\tilde{A}_{jk}^{\diamond}}{\|\tilde{A}_{Jk}^{\diamond}\|_{1}}\right|$
$\displaystyle\leq\frac{|\hat{A}_{jk}^{\diamond}-\tilde{A}_{jk}^{\diamond}|}{\|\hat{A}_{Jk}^{\diamond}\|_{1}}+\tilde{A}_{jk}^{\diamond}\left|\frac{1}{\|\hat{A}_{Jk}^{\diamond}\|_{1}}-\frac{1}{\|\tilde{A}_{Jk}^{\diamond}\|_{1}}\right|$
$\displaystyle\leq\frac{|\hat{A}_{jk}^{\diamond}-\tilde{A}_{jk}^{\diamond}|+\tilde{A}_{jk}\|\hat{A}_{Jk}^{\diamond}-\tilde{A}_{Jk}^{\diamond}\|_{1}}{\|\hat{A}_{Jk}^{\diamond}\|_{1}}$
$\displaystyle=\frac{|\hat{A}_{jk}^{\diamond}-\tilde{A}_{jk}^{\diamond}|}{\|\hat{A}_{Jk}^{\diamond}\|_{1}}+\frac{A_{jk}\|\hat{A}_{Jk}-\tilde{A}_{Jk}^{\diamond}\|_{1}}{\|A_{Jk}\|_{1}\|\hat{A}_{Jk}^{\diamond}\|_{1}}$
(63)

Now,

$\|A_{Jk}\|_{1}=1-\|A_{J^{c}k}\|_{1}\geq
1-\frac{1}{1-q}s(\beta\tau_{n})^{1-q}\geq c$

for some absolute constant $c\in(0,1)$ as $nN$ becomes sufficiently large.
Furthermore, since by definition of $\Pi$ we have
$\tilde{A}_{Jk}^{\diamond}=\text{diag}(\xi_{1})\Pi=A_{J*}\cdot\text{diag}(V_{1})$
and $\min_{k\in[K]}V_{1}(k)\geq\frac{c}{\sqrt{K}}$, so

$\|\tilde{A}_{Jk}^{\diamond}\|_{1}=V_{1}(k)\|A_{Jk}\|_{1}\geq c$

and thus

$\|\hat{A}_{Jk}^{\diamond}\|_{1}\geq\|\tilde{A}_{Jk}^{\diamond}\|_{1}-\|\tilde{A}_{Jk}^{\diamond}-\hat{A}_{Jk}^{\diamond}\|_{1}\geq
c-C\left(\frac{\log p_{n}}{nN}\right)^{1/4}\geq c/2$

as $nN$ becomes sufficiently large. Hence, we have from (63), (61) and (62)
that

$|\hat{A}_{jk}-\tilde{A}_{jk}|\leq Ch_{j}\left(\frac{\log
p_{n}}{nN}\right)^{1/4}$

and so for any $j\in J$,

$\|\hat{A}_{j*}-\tilde{A}_{j*}\|_{1}\leq Ch_{j}\left(\frac{\log
p_{n}}{nN}\right)^{1/4}$

which, since $\sum_{j=1}^{p}h_{j}=K$, implies

$\|\hat{A}_{J*}-\tilde{A}_{J*}\|_{1}\leq C\left(\frac{\log
p_{n}}{nN}\right)^{1/4}$ (64)

We combine (59), (60) and (64) to obtain what we need to prove.

##  Appendix F Results on Archetype Analysis (Javadi and Montanari, 2020)

To facilitate our discussion on relaxing the separability assumption, we
summarize the results of Javadi and Montanari (2020) in this section.

We first introduce the notations in this paper. For a point
$u\in\mathbb{R}^{d}$ and a matrix $V\in\mathbb{R}^{m\times d}$, let

$\mathscr{D}(u;V):=\min\\{\|u-V^{T}\pi\|_{2}^{2}:\pi\in\Delta^{m}\\},\text{
where}$ $\Delta^{m}:=\\{x\in\mathbb{R}^{m}:x^{T}\mathbf{1}_{m}=1\text{ and
}x_{j}\geq 0\text{ for all }j\in[m]\\}$

In words, $\mathscr{D}(u;V)$ is the square of the distance between $u$ and
$\text{conv}(V)$, where $\text{conv}(V)$ denotes the convex hull of the rows
of $V$. If $U\in\mathbb{R}^{p\times d}$ is a matrix with rows
$u_{1},\dots,u_{p}\in\mathbb{R}^{d}$, we generalized the above definition by
letting

$\mathscr{D}(U;V):=\sum_{l=1}^{p}\mathscr{D}(u_{l};V)$ (65)

Now, consider a factorization of the form $X_{0}=W_{0}H_{0}$, where the rows
of $X_{0}\in\mathbb{R}^{m\times(K-1)}$ form a point cloud,
$W_{0}\in\mathbb{R}^{m\times K}$ is a matrix of weights whose rows are in
$\Delta^{K}$, and the rows of $H_{0}\in\mathbb{R}^{K\times(K-1)}$ are the $K$
simplex vertices.

######  Definition 6 ($\alpha$-uniqueness)

We say that the point cloud $X_{0}=W_{0}H_{0}$ satisfies uniqueness with
parameter $\alpha>0$ (or $\alpha$-uniqueness) if for all
$H\in\mathbb{R}^{K\times(K-1)}$ with
$\text{conv}(X_{0})\subseteq\text{conv}(H)$, we have

$\mathscr{D}(H;X_{0})^{1/2}\geq\mathscr{D}(H_{0};X_{0})^{1/2}+\alpha[\mathscr{D}(H;H_{0})^{1/2}+\mathscr{D}(H_{0};H)^{1/2}]$
(66)

The motivation behind this assumption is quite clear. Any $H$ with
$\text{conv}(X_{0})\subseteq\text{conv}(H)$ is a plausible explanation of the
data. For $H_{0}$ to be identifiable, we want
$\mathscr{D}(H;X_{0})>\mathscr{D}(H_{0};X_{0})$ if $H\neq H_{0}$, and so (66)
is a quantitative formulation of this requirement. Note that if
$X_{0}=W_{0}H_{0}$ is a separable factorization, then it always satisfies
uniqueness with $\alpha=1$. Indeed, whenever
$\text{conv}(H_{0})=\text{conv}(X_{0})$, one has
$\mathscr{D}(H;X_{0})=\mathscr{D}(H;H_{0})$ and
$\mathscr{D}(H_{0};X_{0})=\mathscr{D}(H_{0};H)=0$.

The vertex hunting procedure considered in Javadi and Montanari (2020) is as
follows. Suppose we observe $X$ which is a noisy version of $X_{0}$:

$X=X_{0}+Z=W_{0}H_{0}+Z$ (67)

Let $x_{1},\dots,x_{m}$ be the rows of $X$. We can obtain an estimator
$\hat{H}$ of $H_{0}$ by solving the following optimization problem (Archetype
Analysis):

$\text{minimize }\mathscr{D}(H;X)\text{ s.t.
}\mathscr{D}(x_{i};H)\leq\delta^{2}\text{ for all }i\in[m]$ (68)

where $\delta\geq\max_{i\in[m]}\|Z_{i*}\|_{2}$. In light of Corollary 2.5, we
want to choose $\delta\geq C\left(\frac{\log p_{n}}{nN}\right)^{1/4}$ in our
context, where $C$ is the constant in (21) (replace $X_{0}$ in (67) with the
point cloud matrix $R$ from out oracle procedure, and $X$ with the point cloud
matrix $\hat{R}$ from Definition 5).

The main theoretical result of Javadi and Montanari (2020) is that their
vertex hunting procedure is robust to noise in the point cloud.

######  Theorem F.1 (Theorem 1 of Javadi and Montanari (2020))

Suppose $X_{0}$ satisfies the $\alpha$-uniqueness assumption, and
$\text{conv}(X_{0})$ contains a $(K-1)$-dimensional ball of radius $\mu>0$.
Consider the vertex hunting procedure defined by (68), with
$\delta=\max_{i\in[m]}\|Z_{i*}\|_{2}$. If

$\max_{i\in[m]}\|Z_{i*}\|_{2}\leq\frac{\alpha\mu}{30K^{3/2}}$

then

$\|\hat{H}-H_{0}\|_{F}^{2}\leq\frac{C^{2}K^{5}}{\alpha^{2}}\delta^{2}$ (69)

Here, the constant $C$ may depend on $\mu$ and the maximum/minimum singular
values of $H_{0}$, and we ignore the vertex label permutation (by redefining
$\hat{H}$ if necessary).

Using similar proof techniques as in the above theorem, we can also show the
following robustness result for Archetype Analysis without using the
$\alpha$-uniqueness condition (the proof is omitted for brevity). In (70), we
do not need to assume separability (in which case one has
$\mathscr{D}(H_{0};X_{0})=0$), but we want the distance from the vertices in
$H_{0}$ to the convex hull of the point cloud $X_{0}$ to be no larger than
$\delta$. Again, $\delta\asymp\left(\frac{\log p_{n}}{nN}\right)^{1/4}$ when
applied to our topic modeling setup.

###### Theorem F.2

Using the same assumptions as in Theorem F.1 except the $\alpha$-uniqueness
condition, if $\max_{i\in[m]}\|Z_{i*}\|_{2}\leq\delta\leq\frac{\mu}{2K+2}$,
the vertex hunting procedure (68) satisfies for some constants
$C_{1},C_{2}>0$:

$\|\hat{H}-H_{0}\|_{F}^{2}\leq C_{1}\mathscr{D}(H_{0};X_{0})+C_{2}\delta^{2}$
(70)

In practice, the vertex hunting procedure defined (68) is difficult to use.
When applied on real dataset, one may prefer to work with the Lagrangian form
of (68):

$\hat{H}_{\lambda}=\operatorname*{arg\,min}_{H}[\mathscr{D}(X;H)+\lambda\mathscr{D}(H;X)]$
(71)

Algorithms to solve this non-convex optimization problem are available in
Section 4 of Javadi and Montanari (2020).

##  Appendix G Synthetic experiments: additional results

This appendix supplements the synthetic experiments presented in the main
text. In particular, we discuss and illustrate here in more details the Zipf
Law used in our experiments and provide further plots to assess the impact of
additional model’s parameters (including the intensity of the anchor words,
value of the Zipf Law coefficients, etc).

###  G.1 Zipf’s Law: Illustration and Comparison

Most of the synthetic experiments we use in this paper rely on the generation
of documents where word frequencies follow a Zipf’s law distribution (see
Equation 35). Figure 12(a) illustrates instances of such frequency
distributions for a dictionary of size $p=10,000$ words as we vary the
parameters of this distribution (namely, the values of $\alpha_{zipf}$ and
$\beta_{zipf}$). Figure 12(b) compares the frequency heterogeneity resulting
from sampling frequencies $f_{(j)}$’s from a Zipf law distribution (Equation
35) to frequencies sampled from a Uniform distribution:

$f_{(j)}\propto\text{Uniform}(0,1).$

These two figures illustrate in particular the fast decay in word frequencies
under the Zipf Law. In fact, for the reference Zipf law ( $a_{\text{zipf}}=1$
and $b_{\text{zipf}}=2.7$), only $10\%$ of words have frequencies above
$0.001$ – making the rest of the words extremely rare. As per Figure 12(a),
this decay increases rapidly as the parameter $\alpha_{zipf}$ increases. By
comparison, for the uniform distribution, all word frequencies are of the same
order of magnitude. One of the main assumptions in this paper is the weak
sparsity of the row sums of the topic matrix $A$, described in Assumption 5 of
the main text: $\max_{k\in[K]}\max_{j\in[p]}jA_{(j)K}^{q}\leq s$, which, as
argued in the main text, is best reflected by the Zipf Law.

(a) Examples of word frequency distributions under various Zipf law
parameters. Note the quick decay of the frequencies as the value of $\alpha$
increases.

(b) Comparison of the word frequencies generated under a Uniform distribution
(red) and a Zipf law (blue) with parameter $a_{\text{zipf}}=1$ and
$b_{\text{zipf}}=2.7$.

Figure 12: Comparison of word frequencies in a dictionary of size $p=10,000$
under various generation mechanisms. The $x$ and $y$ axis are presented on a
log-scale.

###  G.2 Synthetic Experiment: Uniform Distribution of non-anchor words

In this paragraph, we describe the results of our synthetic experiments using
a Uniform distribution for the generation of non-anchor words.

Data Generation mechanism. In this setting, the data is generated as follows:

$\begin{split}\forall i\in\\{1,\cdots,n\\},&\quad
W_{i}\sim\text{Dirichlet}(\mathbf{1}_{K})\\\ \forall
j\in\\{1,\cdots,5\\},&\quad A_{j+k(i-1),k}=\delta\\\ \forall j\in\\{5K,\cdots
p\\},&\quad A_{jk}\sim\text{Uniform}(0,1)\\\ \ \end{split}$ (72)

This is thus an identical generation setup as in the main text, but using a
Uniform distribution rather than a Zipf Law to generate the frequencies. As
noted in the previous section, this corresponds to a setting in which all
frequencies have roughly the same amplitude (homogeneous frequencies), which
does not agree (a) with our Assumption 5 (weak-sparsity); and (b) observations
or realistic models of word frequencies in real documents (Corral et al.,
2015). Nonetheless, we run our simulation pipeline in this setting and report
the results in Figure 13(a). Results are averaged over 50 experiments, using
$K=5$, $\alpha_{dirichlet}=1$, and 5 anchor words with intensity
$\delta_{anchor}=0.001$.

(a) Median $\ell_{1}$ error
$\mathcal{L}_{1}(\hat{A},A)=\min_{\Pi\in\mathcal{P}}\frac{1}{K}\|\hat{A}\Pi-A\|_{1}$
for the different methods. Rows indicate the size of the vocabulary $p$, while
columns indicate the document length $N$.

(b) Percentage of thresholded words as a function of corpus length, dictionary
size and document length.

Figure 13: Comparison of the different methods under the uniform frequency
generation mechanism detailed in Equation 72. Results are here shown for a
fixed number of topics $K=5$, averaged over 50 independent trials, and plotted
as a function of corpus size $n$. For low values of $p$, the “Sparse Topic
Estimation” method of Bing et al. (2020b) does not appear as the number of
estimated topics that it estimated was less than the true value $K=5$;
therefore we were unable to evaluate it and do not report it in the plots.
Figure 14: Same experiments as depicted in Figure 13. Results are here
displayed as a function of document length $N$.

Analysis of the results. We note that Topic SCORE (Ke and Wang, 2022) and our
method perform similarly in these conditions. As shown in Figure 13(b), our
method does not threshold much in this regime — as is probably to be expected,
since the frequencies of all the words are of the same order. As highlighted
in the main text, this suggests that, whilst designed to leverage the weak
sparsity of the matrix $A$, our method is robust to various frequency regimes.
Our method is, in fact, able to perform satisfactorily even in homogeneous
(and less sparse) settings. Interestingly, in these regimes, AWR becomes an
alternative approach (in particular, as the number of words $p$ increases).

###  G.3 Varying additional parameters

In this subsection, we propose evaluating the effect of other parameters in
our data generation mechanism detailed in Section 3 a. In particular, we
assess here (a) the effect of the anchor word frequency
$\delta_{\text{anchor}}$ (Figure 15); and (b) the impact of the Zipf law
coefficient $a_{zipf}$.

Figure 15: Effect of the anchor word frequency $\delta_{anchor}$ on the
results. Here the number of topics is fixed to $K=3$ and the dictionary has
size $p=5,000.$ Consistently with the experiments presented in the main text,
each topic has 5 anchor words.

Discussion: Effect of the frequency of the anchor words. As observed in Figure
15, the frequency of the anchor words does not appear to have a great impact
on the results of the SCORE-based methods. Increasing the frequency of anchor
words does seem to improve the performance of the Sparse Topic Estimation
Method of Bing et al. (2020a) and for LDABlei et al. (2003).

Discussion: Effect of the parameter $a_{zipf}$. As observed in Figure 16, our
method offers significant improvement over others as the word frequency
heterogeneity increases. In fact, both the Sparse Topic Estimation of Bing et
al. (2020a) and our method’s $\ell_{1}$ errors decrease significantly as the
heterogeneity of the word frequency (high $a_{zipf}$) increases. This is
reassuring, since both methods are the only out of the 5 actively leveraging
the sparsity of the topic matrix to improve estimation.

Figure 16: Effect of the parameter $a_{zipf}$ (see equation 35) on the
results. The number of topics is fixed to $K=5$ and the dictionary has size
$p=10,000.$ Consistently with the experiments presented in the main text, each
topic has 5 anchor words with frequency $\delta=0.001$.

###  G.4 Semi-synthetic experiments

Data Generation Mechanism. To ensure the realism of our experiments, we now
propose to evaluate the performance of our method on a semi-synthetic dataset.
To this end, we consider the Associated Press Dataset, a dataset of 2,246
documents with 10,473 terms. We fit an LDA model on the induced Document-term
matrix and vary the number of topics to obtain an underlying $A_{0}$ and
$W_{0}$. For each experiment, we select a subset of documents by drawing
without resampling $i\in\\{1,\cdots,n\\}$, and concatenate the selected
columns of $W_{i}$ to construct the topic-to-document matrix $W$. Having
obtained $A$ and $W$, we then sample each column of the matrix $D$ from a
multinomial distribution as before. We note that: (a) this data generation
mechanism matches the one assumed by LDA. It thus comes at no surprise that
LDA performs better in this set of experiments, compared to in the previous
subsection; and (b) this data generation mechanism does not impose as much
sparsity as the Zipf law. Indeed, the $A$s imputed by the LDA and which serve
as ground truth here, and is less heterogeneous than in our other synthetic
experiments. Nonetheless, our method improves slightly over Topic SCORE for
corpora of moderate size, across most data regimes. We also note that both
SCORE methods outperform AWR across all data regimes. Interestingly, LDA
exhibits impressive accuracy in this particular regime.

Figure 17: Semi-synthetic experiment: Comparison of the $\ell_{1}$ error in
the reconstruction of $A$ averaged over 50 independent experiments. The
estimation error is plotted as a function of corpus size $n$ (on the x-axis),
as a function of document length $N$ (one per column) and number of topics $K$
(one per row).

Computational Speed.

Finally, we report here the computational speed measured in our experiments.
All experiments here were performed in the University of Chicago Cluster. We
observe a substantial increase in the time required by Topic SCORE as the
number of documents $n$ increases.

Figure 18: Median computational time for each of the methods as a function of
the dictionary length $p$ over 50 independent synthetic experiments.

##  Appendix H Real-World experiments: additional results

In this section, we provide additional visualization plots in microbiome data
analysis to evaluate the estimated topic representatives by LDA, Topic SCORE,
and our methods. We focus on two microbiome datasets, one is the colon dataset
of Yachida et al. (2019) as before with data regime of low $p$, low $n$, high
$N$, another comes from the vaginal microbiome data of Callahan et al. (2017)
with data regime of mid $p$, mid $n$, and high $N$.

###  H.1 Microbiome dataset from Yachida et al. (2019) (low $p$, low $n$, high
$N$)

As depicted in Figure 11, our approach consistently demonstrates a higher
average topic resolution compared to Topic SCORE. To understand the reasons
for the gap in performance between the Topic SCORE method (Ke and Wang, 2022)
and ours, we compare their respective point clouds in Figure 19. The left plot
in figure 19(b) shows the adverse impact of pre-SVD normalization on the Topic
SCORE’s point cloud. It is evident that the outliers from small $h_{j}$ skew
the point cloud, and thereby compromising quality of its subsequent vertex
hunting. In comparison, our point cloud in Figure 19(a) shows an equilateral
triangle formed by the three estimated vertices. Our method combined the
thresholding phase with the spectral decomposition guarantees a higher signal-
to-noise ratio.

(a) Point Cloud for $K=3$ in Topic Score

(b) Point Cloud for our method

Figure 19: Comparison of the point clouds $R$ obtained by our method (right)
and Topic Score (left). Vertices are colored red. Note in particular how the
point cloud on the left is stretched by a few outliers.

###  H.2 Microbiome dataset from Callahan et al. (2017)(high $N$, mid $p$, mid
$n$)

We also reanalyse the dataset of Callahan et al. (2017), which serves as an
example in Fukuyama et al. (2021) to exemplify their topic refinement
procedure. This dataset comprises ASV counts for 2,699 different bacterial
species from 2,179 longitudinal samples collected throughout pregnancy in 135
individuals (Callahan et al., 2017). In this case, the average sample length
is around $N=157,500$. In Fukuyama et al. (2021), based on the refinement
results of the LDA, the authors conclude that the topic analysis should be
done using $K=7$ topics, or with up to $K=12$ if one allows for the
possibility of spurious topics. We thus fit up to 12 topics and plot the
average resolution (Figure 20) and refinement of the methods in Figure 21. We
find that our method compares favorably to Topic SCORE in terms of its average
resolution and similarly to LDA as a whole. For a low number of topics ($K\leq
7$), our method seems even preferable to LDA in terms of topic resolution,
achieving better resolution at much greater speed. The topics found by The
topic coherence seem a little higher for LDA at $K=7$ (the recommended choice
of $K$ by Fukuyama et al. (2021)) than for the others. For $K\geq 8$, our
method seems to yield topics that are more recombined from one level of the
hierarchy to the next than what is observed in LDA. This concurs with the
choice of $K=7$ by the authors, but seems to highlight the fact that for high
values of $K$, in datasets of moderate sizes, LDA appears a preferable choice.
However, we note that Topic SCORE seems to (1) exhibit more recombination of
topics early on in the hierarchy (see bottom topics in Figure 21(a)); and (2)
put very little mass on topics as $K$ increases (indicated by the small size
of the rectangles in Figure 21(a)): as $K$ increases, most of the dataset’s
mass is distributed along roughly 5 or topics. This could in particular mean
that the method does not really identify more than 6 topics.

Figure 20: Topic Resolution (measured by the average cosine similarity between
halves of the data) of our method (in blue), Topic Score (red), and LDA
(purple).

(a) Coherence between topics for Topic SCORE.

(b) Coherence between topics for TTS (our method).

(c) Coherence between topics for LDA.

Figure 21: Topic Coherence and refinement (as computed by the method of
Fukuyama et al. (2021)) for the different methods in the Vaginal Microbiome of
Callahan et al. (2017). Topics are here colored by coherence.


# Masking Kernel for Learning Energy-Efficient Speech Representation

###### Abstract

Modern smartphones are equipped with powerful audio hardware and processors,
allowing them to acquire and perform on-device speech processing at high
sampling rates. However, energy consumption remains a concern, especially for
resource-intensive DNNs. Prior mobile speech processing reduced computational
complexity by compacting the model or reducing input dimensions via
hyperparameter tuning, which reduced accuracy or required more training
iterations. This paper proposes gradient descent for optimizing energy-
efficient speech recording format (length and sampling rate). The goal is to
reduce the input size, which reduces data collection and inference energy. For
a backward pass, a masking function with non-zero derivatives (Gaussian, Hann,
and Hamming) is used as a windowing function and a lowpass filter. An energy-
efficient penalty is introduced to incentivize the reduction of the input
size. The proposed masking outperformed baselines by 8.7% in speaker
recognition and traumatic brain injury detection using 49% shorter duration,
sampled at a lower frequency.

Index Terms—  window function, energy efficiency, deep learning, speaker
recognition, TBI detection

##  1 Introduction

Speech processing hardware embedded into smartphones facilitates various
speech tasks such as voice authentication, automatic speech recognition, and
health assessment on the device either as a short session or continuously.
Most state-of-the-art speech processing utilizes Deep Neural Networks (DNNs)
for accurate analyses, with inference typically done either on a mobile device
or a remote computing server. While on-device computing protects speaker
privacy more than cloud computing, it utilizes more computing resources.

Although computing resources on smartphones can perform real-time DNN
inference, energy consumption remains an issue for deploying such high-
performance DNNs, especially those that perform continuous processing.
Previous work in mobile speech processing addressed limited energy problems by
using energy-efficient hardware [1] including using a low-power processor with
optimizations done on window size and model complexity [2], or using compact
DNN models as in MobileNet [3]. Instead of the model and hardware-specific
optimizations, our approach is to optimize the size of the speech input, which
in turn reduces the energy consumption of data acquisition and DNN inference.

DNNs for speech processing typically operate on a sequence of discrete signals
referred to as chunks, containing $n\times s$ frames from $n$ seconds of audio
sampled at $s$ Hz. A chunk of speech ranges from 200 milliseconds (ms), in
speech recognition, to 15 seconds, in depression detection [4, 5]. While
longer speech sampled at a higher sampling frequency demonstrates improved
recognition performance [2], its practical application is often bounded by
energy consumption, since recording and processing 1) longer speech durations
at 2) higher sampling rates consume more energy [6]. The size of a chunk is
typically optimized as hyperparameters across multiple trainings [2], usually
over a finite set of values in grid-search or using Bayesian optimization,
which learns an optimal hyper-parameter on an open set of values [7].

To efficiently optimize the shape of the input signal as energy-efficient
parameters, this study minimizes the duration of speech $m$ and sampling rate
$s$ via masking using DNN training while learning other DNN parameters
($\theta$). Additional windowing and down-sampling layers are proposed to be
included at the beginning of the DNN to optimize $m$ and $s$, together with
$\theta$ on a computing server with inference running natively on a mobile
device. Gaussian, Hamming, Hann, and Tukey windows [8] were considered as
masks during back-propagation to facilitate learning of $m$ in the windowing
layer. In contrast to the traditional use of masking (referred to as soft-
masking), we applied a binary step as a hard-masking for constructing a
discrete window. In the down-sampling layer, the binary step is used as a
masking function to learn the appropriate signal bandwidth on discrete Fourier
transform.

A learning approach that discovers DNN architecture as an end-to-end model was
previously proposed in Automated Machine Learning (AutoML). Utilizing only
training data, AutoML transforms the architecture of each DNN layer into
derivable functions, such as masking, which can be back-propagated via
gradient descent. Flexconv [9] proposed using a Gaussian function as a mask on
the convolution weights to learn the kernel size for the image recognition
task. DiffStride [10] proposed masking for back-propagation to learn the scale
factor of the pooling layer. Searching for optimal architectures using AutoML
achieves performance superior to hyper-parameter tuning. The uses of masking
in previous work are similar to ours, but the main distinctions are in the
learning objective and methodology. Our method applies masking to the input to
optimize the input format, and not on the weights to optimize model
architecture as in AutoML.

An energy-efficient penalty is introduced to prevent $m$ and $s$ from
expanding, thereby reducing the amount of energy required for inference and
data recording on a linear scale [6]. Our proposed method is able to reduce
energy utilized for inference while minimizing performance loss. We evaluated
the windowing layer, down-sampling layer, and energy-efficient penalty at the
window-level (a session of one speech chunk) and sentence-level (a session of
multiple speech chunks) for the speaker recognition task, and for the
continuous TBI detection task (continuous processing). The energy used for DNN
inference is significantly improved in all three scenarios whereas energy
expenditure during data acquisition is reduced only in the first scenario.
Moreover, we show that our proposed method outperforms or is competitive with
conventional hyperparameter tuning methods in terms of accuracy on
significantly reduced size of speech input.

##  2 Proposed method

The optimization of window size and the sampling rate is accomplished via
back-propagation through windowing $\mathcal{W}_{m}$ and down-sampling layers
$\mathcal{D}_{s}$. The parameters in these two layers ($m,s$) are learned
jointly with other parameters ($\theta$) in the DNN but are controlled by
energy-efficient penalty $\mathcal{J}$ in order to minimize the size of the
speech sample. Given a speech model $\mathcal{F}_{\theta}(x)$ with a loss
function of $\mathcal{L}(x,y)$, parameters are optimized from dataset
$\\{x_{i},y_{i}\\}_{i=0}^{P}$ by
$\mathrm{argmin}_{\theta,m,s}\sum_{i=0}^{P}\mathcal{L}\big{(}\mathcal{F}_{\theta}(\mathcal{W}_{m}(\mathcal{D}_{s}(x_{i})),y_{i}\big{)}+\mathcal{J}(m,s)$

Windowing layer: Let $x_{i}\in\mathbb{R}^{N}$ be a speech sample, composed of
$N$ frames where $N$ is the upper bound of window length. Windowing should
allow a signal of length $m$ ($\lfloor\frac{N-m}{2}\rfloor\leq
n\leq\lfloor\frac{N+m}{2}\rfloor$) into the DNN. A rectangle window, a
standard method for segmenting the signal for DNN, is defined to have values
of 1 within the length of $m$ and values of 0 everywhere else, resulting in
zero derivatives. To learn $m$ via gradient descent, derivatives of the
masking function must be non-zeros. This study proposes hard-masking, a
learnable rectangle window, that uses functions with a peak at its center
during back-propagation. The functions considered are Gaussian, Hamming, Hann
and Tukey [8], which are well-known functions in signal analysis.

Gaussian window function has a mean value of $\lfloor\frac{N-1}{2}\rfloor$
with a learnable variance $\sigma^{2}$. This study defines $\sigma^{2}$ in
terms of window $m$ at which the function is approaching zero
($m^{2}=-8\log(\epsilon)\sigma^{2},\epsilon=1e^{-5}$) as
$w_{G}(n;m)=exp(4\log(\epsilon)(n-\lfloor\frac{N-1}{2}\rfloor)^{2}/m^{2})$.
Hamming and Hann windows are defined as
$w_{HM}(n;m)=0.54-0.46\cos(2\pi(n-\lfloor\frac{N-m}{2}\rfloor)/(m-1))$ and
$w_{HN}(n;m)=0.5-0.5\cos(2\pi(n-\lfloor\frac{N-m}{2}\rfloor)/(m-1))$,
respectively. Tukey is also included as a tapered cosine function of $w_{HN}$.

A window $w(n;m)$ is applied to $x(n)$ to attenuate values outside the window.
We call the output of this operation soft-masking and consider it a baseline
for hard-masking. To create hard-masking $\mathcal{W}_{m}$, a value of 1 is
assigned to non-zero values of soft-masking. The hard-masking derivative of
$\delta\mathcal{L}/\delta m$ is computed by applying a straight-through
estimator [11] to $w$.

Fig. 1: Windowing layer using hard-masking

Down-sampling layer: The down-sampling layer $\mathcal{D}_{s}$ applies masking
in the frequency domain, resampling $x$ to $2s$ Hz. The discrete Fourier
transform $X(\hat{n})=FFT(x(n))$ is obtained from the Fast Fourier Transform
(FFT) of $x(n)$. Due to Hermitian symmetry, the term with negative frequency
can be disregarded. A rectangle mask is used as a low-pass filter to zero
frequency bins higher than $s$. To reduce artifacts from the rectangle mask
and allow back-propagation, a linear function is applied, which extends the
cutoff frequency by $r$. The mask $w_{r}(n;s,r)$ is defined as
$min(1,max(-\frac{n-s}{r})),0\leq n\leq N$ ,visualized in Fig. 2. After
applying $w_{r}(n;s,r)$ to $X(\hat{n})$, $x(n)$ is downsampled to $s$ Hz using
inverse FFT only on DFT bins between $0$ and $s$ Hz, mathematically explained
by $\mathcal{D}_{s}=iFFT(X(\hat{n})\odot w_{r}(\hat{n};s,r))$, where
$0<\hat{n}\leq s$.

Fig. 2: Masking $w_{r}$ in down-sampling layer

Energy-efficient penalty: A penalty term is introduced to encourage the
minimization of window length and sampling rate, which, in turn, reduces the
amount of energy required for data acquisition and inference. The energy-
efficient penalty
$\mathcal{J}(m,s)=\lambda\big{[}\frac{\max(m-\mu_{m},0)}{\mu_{m}}+\frac{\max(s-\mu_{s},0)}{\mu_{s}}\big{]}\bar{\mathcal{L}}$
is incorporated into the loss function to penalize $\mathcal{L}$ if $m$ or $s$
are increasing from their average values ($\mu_{m}$,$\mu_{s}$) in the previous
epoch. The penalty values are normalized and added proportionally to the value
of $\bar{\mathcal{L}}$ (no gradient). $\lambda$ is adjustable to control the
penalty term. $\mathcal{J}$ is clipped at zero to prevent exploding gradient.

##  3 Evaluation

The proposed method was evaluated using a state-of-the-art DNN previously
proposed for speaker recognition (short) and TBI detection (continuous,
passive health assessment) tasks. Our implementation is publicly available
111https://github.com/aditthapron/windowMasking.

1) Speaker recognition task: The speaker recognition speech processing task
tries to identify a speaker based on their voice characteristics. In
smartphones, speaker identification is frequently performed as a snippet or as
continuous authentication, which consumes significant energy [12].

Dataset: Text-independent speech from the TIMIT corpus was used to train and
evaluate the model. Read speech in English was collected from 462 speakers at
16-bit with a sampling rate of 16kHz. All data preprocessing steps, including
removing non-speech segments at the beginning and end, removing calibration
sentences, and normalizing the amplitude, were performed similarly to [4]. The
space between each window center was fixed to 10ms. $M$ was set to 500ms. The
split between training and testing was the same as in [4].

Evaluation Metric: Classification Error Rate (CER) is reported at both the
window and sentence levels. At the window level, the speaker with the highest
negative log-likelihood is predicted, whereas, the negative log-likelihood
from all windows is summed to make the prediction at the sentence level. The
reduction of $m$ in window-level speaker recognition means that the duration
of speech necessary to collect was reduced. To assess the training’s
consistency, all evaluations were repeated ten times with random seeds of
varying values.

Baseline: SincNet [4] was the baseline for speaker recognition. It replaces
traditional convolutional weights with the Sinc function as the kernel in CNN
layers. The model consists of one CNN layer with Sinc filters and two
conventional CNN layers. After the CNN, the tensor is transformed into a one-
dimensional tensor to classify the speaker.

Experiment: We extended SincNet [4] to learn energy-efficient parameters by
including windowing and $\mathcal{D}_{s}$ layers prior to SincNet layers. As
the input shape changes throughout the learning process, the layers following
the CNN were modified to only apply weights to the signal’s valid length.

2) TBI detection task: Frequently, impaired speech is considered a TBI
biomarker that can be observed using smartphones, preventing fatalities and
facilitating the recovery of TBI [13]. Even though smartphones enable passive,
non-invasive monitoring of TBI, continuous speech assessment using a DNN is
extremely energy-intensive. To enable TBI detection to run on smartphones,
energy-efficient speech representations were learned using the proposed
methods.

Dataset: Speech collected during discourses following TBI from Coelho corpus
[14] was used for evaluation. The Coelho corpus contains speech during story
retelling, story generation, and conversation discourses from 55 subjects with
non-penetrating head injuries and 52 subjects without head injuries. This
evaluation considered speech recorded in the conversation section. The pre-
processing was done following [13], including 1) removing noisy audio from
four subjects, 2) normalizing audio magnitude, and 3) vocal-tract length
normalization. The speech was recorded with a sampling rate of 44.1 kHz, where
[13] down-sampled the signal to 16 kHz. This study initialized $s$ in the
down-sampling layer to 22 kHz.

Metric: Balanced Accuracy ,$(\text{Sensitivity}+\text{Specificity})/2$, is
reported using subject-level split 10-fold cross-validation.

Baseline: The cascading Gated Recurrent Unit (cGRU) previously proposed for
TBI detection from speech [13] was the baseline model. cGRU is a two-step DNN
where the first model extracts TBI features from 200ms of speech using five
CNN layers, and the second model applies GRU on stacked features from the
first model for binary TBI classification. The CNNs were applied on 200ms with
an interval of 25 ms and GRU makes a TBI prediction over 4s of speech.

Experiment:We integrated the proposed method into the cascading Gated
Recurrent Unit (cGRU) model [13] to learn the energy-efficient input for the
TBI detection task. Windowing and down-sampling layers were applied at the
instance level ($M=$ 8s). Due to space constraints, ablation results are only
reported for speaker recognition.

Model optimization Baselines: Grid-search and Bayesian model-based
optimization were used to tune the input format. $m$ and $s$ were searched in
ranges of [100,300] ms and [6000,8000] Hz for speaker recognition, and [2,8] s
and [6000,22050] Hz for TBI detection in grid-search. Ten evenly spaced values
were used for each parameter interval. In Bayesian model-based optimization,
the Tree-structured Parzen Estimator (TPE) [15] was utilized. TPE uses past
evaluations of hyperparameters to construct a probabilistic model over
multiple iterations. We considered a low-pass filter with a learnable Sinc
filter [4] as a baseline for $\mathcal{D}_{s}$ layer.

Energy-efficient metrics: The numbers of parameters and Multiply-Accumulates
(MACs) have previously been shown to be effective estimations of DNN energy
consumption at inference [16]. Our proposed method adds window length
parameters $m$ and sampling rate $s$ to the model, but MACs change
significantly depending on the size of the input ($m\times s$). Energy
consumption at inference can be reduced by lowering the MAC, whereas power
consumption during speech recording can be reduced by lowering $s$. We
reported normalized MAC and training time as measurements of energy used at
inference and time used to obtain energy-efficient parameters. They are
normalized as a ratio to grid-search.

##  4 Result

Speaker recognition: Windowing functions are compared as hard-masking and
soft-masking for speaker recognition in Fig. 3 (top). Only the hard-mask is
able to optimize $m$, approximately at 120-200ms. Window-CER is significantly
lower than the baseline trained on a 200ms speech. From the plot between CER
and window length (Fig. 4), Hamming window shows to be the most efficient at
reducing window length while maintaining the same error range as Gaussian and
Tukey windows. The CER of Hann window is lower than the other windows,
however, using $m$ higher than 200ms.

Fig. 3 (bottom) compares the $\mathcal{D}_{s}$ layer to the Sinc.
$\mathcal{D}_{s}$ is competitive with the Sinc filter but with a significantly
lower sampling rate of 7.2 kHz. Together, the two proposed masking layers can
be optimized using penalty terms as shown in Fig. 5. $\lambda=0.5$ and $1$
provide the most energy-efficient performance, reducing the window length to
118 ms and sampling rate to 7.2 kHz while maintaining a low CER of 0.49.

The comparison between the proposed method, grid-search, and TPE is shown in
Table 1. The proposed method is capable of reducing MAC (an indicator for
energy consumption used for inference) by 49%, with superior performance at
the window-level and comparable performance at sentence-level. The energy used
for data acquisition is also reduced by 40% for window-level speaker
recognition. The improved CRE may be due to the mechanism of optimization in
the windowing layer that allows other parameters in the model to learn on
various receptive fields over the training epochs. This conjecture is
evidenced by the result of the fixed value, which trains the model using fixed
$m$ and $s$ values as in the proposed method, which has inferior results.

Fig. 3: TOP: Window-CER between hard-masking and soft-masing, BOTTOM: Window-
CER using Down-sampling layer (DS) and Sinc filter Fig. 4: Trade-off between
CER and window length Fig. 5: Effect of energy-efficient penalty Table 1:
Speaker recognition and TBI detection results

Speaker |  CER $(\%_{\pm std})$ | Energy-efficient metrics
---|---|---
classification | Window | Sentence |  $m$(ms) |  $s$(Hz) | MAC | Training Time
Hamming | $\textbf{48.6}_{.4}$ | $1.02_{.1}$ | 118 | 8k | 0.58 | 0.96
Hamming + $\mathcal{D}_{s}$ | $\textbf{49.1}_{.3}$ | $1.08_{.1}$ | 120 | 7.2k | 0.51 | 1.05
Grid-search | $53.8_{.1}$ | $\textbf{0.94}_{.1}$ | 200 | 8k | 1 | 1
Fixed values | $56.0_{.1}$ | $1.24_{.2}$ | 120 | 7.2k | 0.51 | 0.64
TPE | $52.80_{.7}$ | $1.29_{.1}$ | 272 | 7.6k | 0.87 | 22
TBI detection |  BA $(\%_{\pm std})$ |  |  |  |
Hamming | $86.53_{1.3}$ | 2.89s | 8k | 0.79 | 1.05
Hamming + $\mathcal{D}_{s}$ | $\textbf{87.12}_{1.4}$ | 3.14s | 6.2k | 0.74 | 1.02
Grid-search | $83.82_{1.4}$ | 4s | 8k | 1 | 1
Fixed values | $82.62_{1.1}$ | 3.14s | 6.2k | 0.74 | 0.78
TPE | $81.90_{1.9}$ | 3.94s | 8k | 1 | 18
MAC and training time are reported as a ratio to Grid-search.

TBI detection: TBI detection result is reported in Table 1. The best TBI BA is
obtained using 3.14s of speech sampled at 12.4 kHz, improving the grid-search
result by 3.9%. The training time used to tune the model is significantly
lower than TPE and is competitive with grid-search that trained DNN in
parallel. Energy consumption at inference is expected to reduce by 26%
compared to baseline. Similar to speaker recognition results, windowing and
$\mathcal{D}_{s}$ layers allow the DNN to learn from different lengths and
sampling of speech, which provides a better detection BA.

##  5 Conclusion

DNN-based speech processing has the potential for impact but currently has
high energy consumption, limiting the mobile deployment of state-of-the-art
results. This study proposed optimizing the length and sampling rate of speech
using a masking function during the back-propagation of DNN, which
consequently reduces the energy consumption of speech acquisition and DNN
inference. Our evaluation demonstrates that learning speech format using an
end-to-end model provides better performances than tuning window length and
sampling rate as hyperparameters. The power consumption used for inference is
reduced as can be estimated from MAC operation, up to 49% and 26% in speaker
recognition and TBI detection tasks, respectively while maintaining high
accuracy.

Our proposed method has the limitation of requiring subsequent DNN layers to
operate on a tensor with a dynamic temporal dimension. This study modified the
DNN fully-connected layer to have a flexible input size, which may create
inconsistent loss across training epochs.

## References

  * [1] Jia-Ching Wang, Li-Xun Lian, Yan-Yu Lin, and Jia-Hao Zhao,  “Vlsi design for svm-based speaker verification system,”  IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 23, no. 7, pp. 1355–1359, 2014.
  * [2] Hong Lu, AJ Bernheim Brush, Bodhi Priyantha, Amy K Karlson, and Jie Liu,  “Speakersense: Energy efficient unobtrusive speaker id. on mobile phones,”  in Int’l Conf. Pervasive Comp. Springer, 2011, pp. 188–205.
  * [3] João Antônio Chagas Nunes, David Macêdo, and Cleber Zanchettin,  “Am-mobilenet1d: A portable model for speaker recognition,”  in 2020 International Joint Conference on Neural Networks (IJCNN). IEEE, 2020, pp. 1–8.
  * [4] Mirco Ravanelli and Yoshua Bengio,  “Speaker recognition from raw waveform with sincnet,”  in IEEE Spoken Language Tech. Workshop (SLT), 2018, pp. 1021–1028.
  * [5] Karol Chlasta, Krzysztof Wołk, and Izabela Krejtz,  “Automated speech-based screening of depression using deep convolutional neural networks,”  Procedia Computer Science, vol. 164, pp. 618–628, 2019.
  * [6] Dinko Oletic and Vedran Bilas,  “System-level power consumption analysis of the wearable asthmatic wheeze quantification,”  Journal of Sensors, 2018.
  * [7] A Helen Victoria and G Maragatham,  “Automatic tuning of hyperparameters using bayesian optimization,”  Evolving Systems, vol. 12, no. 1, pp. 217–223, 2021.
  * [8] Peter Bloomfield,  Fourier analysis of time series: an introduction,  John Wiley & Sons, 2004.
  * [9] David W. Romero, Robert-Jan Bruintjes, Jakub Mikolaj Tomczak, Erik J Bekkers, Mark Hoogendoorn, and Jan van Gemert,  “Flexconv: Continuous kernel convolutions with differentiable kernel sizes,”  in ICLR, 2022.
  * [10] Rachid Riad, Olivier Teboul, David Grangier, and Neil Zeghidour,  “Learning strides in convolutional neural networks,”  in ICLR, 2022.
  * [11] Yoshua Bengio, Nicholas Léonard, and Aaron Courville,  “Estimating or propagating gradients through stochastic neurons for conditional computation,”  arXiv preprint arXiv:1308.3432, 2013.
  * [12] Hasna Bouraoui, Chadlia Jerad, Anupam Chattopadhyay, and Nejib Ben Hadj-Alouane,  “Hardware architectures for embedded speaker recognition applications: a survey,”  ACM Transactions on Embedded Computing Systems (TECS), vol. 16, no. 3, pp. 1–28, 2017.
  * [13] Apiwat Ditthapron, Adam C Lammert, and Emmanuel O Agu,  “Continuous tbi monitoring from spontaneous speech using parametrized sinc filters and a cascading gru,”  J. Biomedical Health Inf., 2022.
  * [14] Carl A Coelho, Kathleen M Youse, and Karen N Le,  “Conversational discourse in closed-head-injured and non-brain-injured adults,”  Aphasiology, vol. 16, no. 4-6, pp. 659–672, 2002.
  * [15] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl,  “Algorithms for hyper-parameter optimization,”  NeurIPS, vol. 24, 2011.
  * [16] Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel S Emer,  “Efficient processing of deep neural networks: A tutorial and survey,”  Proceedings of the IEEE, vol. 105, no. 12, pp. 2295–2329, 2017\.


# One word at a time: adversarial attacks on retrieval models

Nisarg Raval  Linkedin, New York<EMAIL_ADDRESS>and  Manisha Verma
VerizonMedia, Yahoo! Research, New York<EMAIL_ADDRESS>
###### Abstract.

Adversarial examples, generated by applying small perturbations to input
features, are widely used to fool classifiers and measure their robustness to
noisy inputs. However, little work has been done to evaluate the robustness of
ranking models through adversarial examples. In this work, we present a
systematic approach of leveraging adversarial examples to measure the
robustness of popular ranking models. We explore a simple method to generate
adversarial examples that forces a ranker to incorrectly rank the documents.
Using this approach, we analyze the robustness of various ranking models and
the quality of perturbations generated by the adversarial attacker across two
datasets. Our findings suggest that with very few token changes (1-3), the
attacker can yield semantically similar perturbed documents that can fool
different rankers into changing a document’s score, lowering its rank by
several positions.

##  1\. Introduction

Deep learning ranking models increasingly represent the state-of-the art in
ranking documents with respect to a user query. Different neural architectures
(Guo et al., 2016; Mitra et al., 2017; Xiong et al., 2017) are used to model
interaction between query and document text to compute relevance. These models
rely heavily on the tokens and their embeddings for non-linear transformations
for similarity computation. Thus, they capture semantic similarity between
query and document tokens circumventing the exact-match limitation of previous
models such as BM25 (Robertson and Zaragoza, 2009).

The complexity of deep learning models arises from their high dimensional
decision boundaries. The hyperplanes are known to be very sensitive to changes
in feature values. In computer vision literature (Zhou et al., 2020) and text
based classification tasks (Wang et al., 2019), researchers have shown that
deep learning models can change their predictions with slight variations in
inputs. There is a large body of work that investigates adversarial attacks
(Wang et al., 2019) on deep networks to quantify their robustness against
noise. There is, however, lack of such experiments and evaluation in
information retrieval literature. Mitra _et.al._ (Mitra et al., 2016)
demonstrated how word replacement in documents can lead to difference in word
representations which leaves room for more investigation of the robustness of
deep ranking models to adversarial attacks.

Usually, adversarial attackers perturb images to reverse a model’s decision.
Noise addition to images is performed at pixel level such that a human eye
cannot distinguish true image from noisy image. In text classification tasks,
characters or words (Liang et al., 2017; Papernot et al., 2016) are modified
to change the classifier output. The objective of the adversary is to reverse
model’s decision with minimum amount of noise injection. In information
retrieval, however, it remains an open problem as to how does one design an
adversary for a ranking model. We posit that the objective of an adversary in
information retrieval would be to change the position of a document with
respect to the query. We follow a similar approach used in text classification
tasks (Liang et al., 2017; Papernot et al., 2016) and perturb tokens in
documents, replacing them with semantically similar tokens such that the rank
of the document changes.

In this work, we demonstrate by means of false negative adversarial attacks
that three state-of-the-art retrieval models can change a document’s position
with slight changes in its text. We evaluate the robustness of these ranking
models on publicly available datasets by injecting varied length of noisy text
in documents. We propose a black-box adversarial attack model that takes a
(query, document) pair as input and generates a noisy document such that its
pushed lower in the ranked list. Our system does not need access to the
ranker’s internal architecture, only its output given the (query, document)
tuple as input.

Our findings suggest that ranking models can be sensitive to even single token
perturbations. Table 1 shows some examples generated by our model of one word
perturbations along with changes in document position when scored using state-
of-the-art ranking model. Overall, we found that simple attackers could
perturb very few words and still generate semantically similar text that can
fool a model into ranking a relevant document lower than non-relevant
documents.

Query |  Relevant Document | Replaced by |  $\downarrow$Rank
---|---|---|---
what can be powered by wind |  Wind power is the conversion of wind energy into a useful form of energy, such as using wind turbines to make electrical power , windmills for mechanical power, wind pumps for  water pumping or drainage , or sails to propel ships. | wind | 12
what causes heart disease |  The causes of cardiovascular disease are  diverse but atherosclerosis and/or hypertension are the most common. | disorder | 8
how many books are included in the protestant Bible? |  Christian Bibles range from the sixty-six books of the Protestant  canon to the eighty-one books of the Ethiopian Orthodox Tewahedo Church canon. | christian | 5
how many numbers on a credit card |  An ISO/IEC 7812 card number is typically 16 digits in  length, and consists of: | identification | 4
how many amendments in us |  The Constitution has been amended seventeen additional times (for a total of  twenty-seven amendments). | allowing | 4
what is a monarch to a monarchy |  A monarchy is a form of government in which sovereignty is actually or nominally  embodied in a single individual (the monarch ). | throne | 4
Table 1. Examples of our one word adversarial perturbation and change in
document position when ranked by DRMM.

##  2\. Related Work

Adversarial attack on deep neural networks has been extensively explored in
vision (Su et al., 2019) and text classification (Wang et al., 2019; Papernot
et al., 2016). Existing work has proposed adversarial attacks with either
white-box or black-box access to the model. In this work, our focus is on
black-box attacks since access to ranking models is not always available.
Existing work is also limited in that the focus is on changing classifier
decisions and not document positions in ranked list with respect to a query.
In this work we explore utility of (query,doc) pair in adversarial attacks on
ranking models.

##  3\. Our Approach

Our goal is to minimally perturb a document such that the rank of the document
changes. In particular, we target top-ranked documents and attempt to lower
their rank through noise injection. Assuming relevant documents are ranked
higher, the objective is to lower the position of a document with minimal
change in its text.

###  3.1. Problem Statement

Let $\vec{q}$, $\vec{d}$ and $\mathcal{F}$ represent a query, a document and a
ranking model, respectively. Given a query-document pair $(\vec{q},\vec{d})$,
the ranker outputs a score $s=\mathcal{F}(\vec{q},\vec{d})$ indicating the
relevance of the document $\vec{d}$ to the query $\vec{q}$, where higher score
means higher relevance. Given a query and a list of documents, the ranker
computes scores for every document w.r.t the given query and rank documents
based on a descending order of the scores. Given $\vec{q}$ and $\vec{d}$, our
goal is to find a perturbed document $\vec{d^{\prime}}$ such that
$\mathcal{F}(\vec{q},\vec{d^{\prime}})<<\mathcal{F}(\vec{q},\vec{d})$ so that
it ranks lower than its original rank. At the same time we want to minimize
the perturbation in the document.

We assume that both query and document are represented as vectors which could
be either sequence of terms or other suitable representations such as word
embedding. Let $\vec{q}=(q_{1},q_{2},...,q_{p})$ be a p-dimensional query
vector and $\vec{d}=(d_{1},d_{2},...,d_{q})$ be a q-dimensional document
vector. We construct a perturbed document $\vec{d^{\prime}}=(\vec{d}+\vec{n})$
by adding a q-dimensional noise vector $\vec{n}=(n_{1},n_{2},...,n_{q})$. Our
goal is to find a noise vector that reduces a document’s score without
changing many terms in the document. We formulate this problem as an
optimization problem as follows:

(1) $\displaystyle\underset{\vec{n}}{\text{minimize}}$
$\displaystyle\mathcal{F}(\vec{q},\vec{d+n})$ subject to
$\displaystyle||\vec{n}||_{0}\leq c$

Here, $c$ is a sparsity parameter that controls the number of perturbed terms.
Although, the above formulation provides a sparse solution, we do not have any
control over the magnitude of the noise vector. In other words, even though we
change only few terms in a document we may end up changing them significantly.
To address this problem, we modify the objective function as follows:

(2) $\displaystyle\underset{\vec{n}}{\text{minimize}}$
$\displaystyle\mathcal{F}(\vec{q},\vec{d+n})+\sum_{i=1}^{q}{\mathcal{D}}(d_{i},(d_{i}+n_{i}))$
subject to $\displaystyle||\vec{n}||_{0}\leq c$

Here, $\mathcal{D}$ can be any suitable distance function (e.g., cosine
distance) that computes distance between two terms. It ensures that the
modified terms are close to the original terms. We found this formulation too
strict. In particular, it penalizes perturbations of query terms as well non-
query terms in a document. Hence, we modify the objective function to penalize
only query terms since we want to ensure that the perturbed document stays
relevant to the query. The modified objective function is as follows:

(3) $\displaystyle\underset{\vec{n}}{\text{minimize}}$
$\displaystyle\mathcal{F}(\vec{q},\vec{d+n})+\sum_{i=1}^{q}\mathbbm{1}_{d_{i}\in\vec{q}}[{\mathcal{D}}(d_{i},(d_{i}+n_{i}))]$
subject to $\displaystyle||\vec{n}||_{0}\leq c$

Here, $\mathbbm{1}_{x}$ is an indicator function with is $1$ when $x$ is true
and $0$ otherwise. The first term in the objective function ensures that the
ranker gives low score to the perturbed document while the second term incurs
penalty of changing query terms in the document. The constrains limits the
number of changed terms in a document to $c$.

###  3.2. Method

A popular approach to solve the above problem relies on computing gradient of
the model’s output (score) with respect to the input and use this gradient to
find a noise vector that reduces model’s score on noisy input (Goodfellow et
al., 2014). Such gradient based methods do not work well with textual data due
to non-differentiable components such as an embedding layer. A common
workaround is to find perturbation in the embedding space and project the
perturbation vector in the input space through techniques like nearest
neighbour search. In general, gradient based methods are restricted to
differentiable models and require information about the model’s architecture.

To address the shortcomings of gradient based methods, we propose a different
approach that uses Differential Evolution (DE) (Storn and Price, 1997), a
stochastic evolutionary algorithm. It can be applied to a variety of
optimization problems including non-differentiable and multimodal objective
functions. DE is a population-based optimization method which works as
follows: Let’s say we want to optimize over $l$ parameters. Given the
population size $m$, it randomly initializes $m$ candidate solutions
$\vec{X_{t}}=(\vec{x}_{1},\vec{x}_{2},...,\vec{x}_{m})$, each of length $l$.
From these parent solutions it generates candidate children solutions using
the following mutation criteria:

(4) $\vec{x}_{a,t+1}=\vec{x}_{b,t}+F(\vec{x}_{c,t}-\vec{x}_{d,t})$

Here, $a,b,c$ and $d$ are randomly chosen distinct indices in the population,
and $F$ is a mutation factor in $[0,2]$. Next, these children are compared
against their parents using a fitness function and $m$ candidates are selected
that have the highest fitness (i.e., minimizes the fitness function). This
process is repeated until either it converges or reaches the maximum number of
iterations.

Given a query-document pair $(\vec{q},\vec{d})$ and a trained ranker
$\mathcal{F}$ we use DE to find a perturbation vector $\vec{n}$ that changes
the document’s rank without significantly modifying it. In particular, we need
to find what terms to perturb in the document and the magnitude of each
perturbation. Hence, we represent the solution (perturbation vector) as a
sequence of tuples $(i,v)$ where $i\in[0,|\vec{d}|]$ represents an index of
the term to perturb and $v$ represents the perturbation value. The length of
the solution vector is set to $c$ (the sparsity parameter). We use the
objective function proposed earlier as a fitness function for DE and run the
algorithm for a fixed number of iterations. Based on the choice of the fitness
function, we propose three variants of the attack, _A1_ (Equation 1), _A2_
(Equation 2) and _A3_ (Equation 3). The final solution vector is used to
construct the perturbed document $d^{\prime}$. A similar approach has been
used to perturb images in order to fool a classifier (Su et al., 2019).

Dataset | Model | _S@k_ | _A0_ | _A1_ | _A2_ | _A3_
---|---|---|---|---|---|---
WikiQA |  DRMM | 1 | 0.62 | 1.0 | 0.93 | 1.0
5 | 0.01 | 0.26 | 0 | 0.15
Duet | 1 | 0.58 | 1.0 | 0.65 | 1.0
5 | 0.02 | 0.27 | 0 | 0.25
KNRM | 1 | 0.56 | 1.0 | 0.41 | 1.0
5 | 0 | 0.13 | 0.01 | 0.13
MSMarco |  DRMM | 1 | 0.67 | 1.0 | 0.73 | 1.0
5 | 0 | 0.11 | 0.003 | 0.04
Duet | 1 | 0.5 | 1.0 | 0.57 | 1.0
5 | 0 | 0.87 | 0.03 | 0.81
KNRM | 1 | 0.58 | 1.0 | 0.89 | 1.0
5 | 0.01 | 0.89 | 0.45 | 0.89
Table 2. Attackers’ success on changing document’s position.

##  4\. Experimental Setup

In this section, we provide details about the datasets, model training,
perturbation and evaluation metrics.
Data: We use WikiQA (Yang et al., 2015) and MSMarco passage ranking dataset
(Bajaj et al., 2016) for training ranking models and evaluating attacks on
three ranking models. For WikiQA, we use 2K queries for training and 240
queries for evaluation. For MSMarco, we use 20K randomly sampled queries for
training and 220 queries for evaluation. For each test query, we randomly
sample 5 positive documents and 45 negative documents for evaluation.
Model training: We use the following ranking models: DRMM (Guo et al., 2016),
DUET (Mitra et al., 2017) and KNRM (Xiong et al., 2017). We use 300
dimensional Glove embeddings (Jeffrey Pennington and Manning, 2014) to
represent each token.
Perturbation: In our experiments, we perturb _only_ relevant documents111We
found that non-relevant documents can be perturbed easily by adding noisy
text. in top 5 results for each query in the test set. We perturb documents
using all three attackers (_A1_ , _A2_ , and _A3_) and evaluate ranker
performance on the perturbed documents. The number of iterations and
population size are fixed to 100 and 500 respectively.
Evaluation: We explore several metrics for understanding the effectiveness of
perturbations and their impact on ranker performance. The goal of an attacker
is to fool the ranker into lowering the position of the document in the list.
The success of the attacker is measured as the percentage of _relevant_
documents whose position changed by $k$ when perturbed by the attacker. Let
$\mathcal{R}(d)$ denote the rank of a document $d$ and $l_{d}$ denote its
relevance. Then, the attacker’s success at k (_S@k_) is defined as follows:

$\emph{S@k}=\frac{\sum_{d;l_{d}>0}\mathbbm{1}_{(\mathcal{R}(d^{\prime})-\mathcal{R}(d))>=k}}{\sum_{d;l_{d}>0}\mathbbm{1}}$

Here, $d^{\prime}$ is a perturbation of $d$ generated by the attacker. We also
measure the number of non-relevant documents crossed (_NRC_) by perturbing $d$
to $d^{\prime}$ as defined below:

$\emph{NRC}=\sum_{\hat{d};l_{\hat{d}}=0}\mathbbm{1}_{\mathcal{R}(d)<\mathcal{R}(\hat{d})<\mathcal{R}(d^{\prime})}$

We compare the performance of the proposed attacks against a random baseline
_A0_ where the adversary perturbs a word at random from the text and replaces
it with the most similar word (minimum cosine distance in the embedding space)
from the corpus.

Model | Atk | 1 token | 3 tokens | 5 tokens
---|---|---|---|---
DRMM | _A1_ | 0.944$\pm$2.776 | 3.867$\pm$6.334 | 6.814$\pm$7.858
_A2_ | 0.037$\pm$0.623 | 0.304$\pm$1.752 | 0.647$\pm$3.129
_A3_ | 0.404$\pm$1.730 | 1.280$\pm$3.388 | 2.084$\pm$4.496
Duet | _A1_ | 8.110$\pm$4.252 | 13.000$\pm$4.292 | 14.637$\pm$4.043
_A2_ | 0.429$\pm$0.896 | 0.890$\pm$1.479 | 1.670$\pm$3.266
_A3_ | 7.187$\pm$4.284 | 10.440$\pm$4.806 | 12.055$\pm$4.771
KNRM | _A1_ | 11.543$\pm$6.737 | 18.560$\pm$5.659 | 21.360$\pm$s6.459
_A2_ | 6.234$\pm$8.125 | 9.463$\pm$9.408 | 11.211$\pm$10.086
_A3_ | 11.114$\pm$6.611 | 17.783$\pm$5.914 | 20.291$\pm$6.500
Table 3. _NRC_ for MSMarco dataset  Model | Atk | 1 token | 3 tokens | 5 tokens
---|---|---|---|---
DRMM | _A1_ | 2.380$\pm$3.252 | 4.009$\pm$4.499 | 4.403$\pm$4.753
_A2_ | 0.014$\pm$0.118 | 0.464$\pm$1.629 | 1.098$\pm$2.943
_A3_ | 1.403$\pm$2.127 | 2.286$\pm$3.160 | 2.455$\pm$3.300
Duet | _A1_ | 2.175$\pm$2.454 | 3.527$\pm$3.585 | 3.773$\pm$3.857
_A2_ | 0.040$\pm$0.221 | 0.175$\pm$0.506 | 0.366$\pm$0.899
_A3_ | 2.005$\pm$2.270 | 3.175$\pm$3.277 | 3.221$\pm$3.280
KNRM | _A1_ | 1.632$\pm$2.064 | 2.580$\pm$2.873 | 2.849$\pm$3.155
_A2_ | 0.188$\pm$0.577 | 0.853$\pm$1.647 | 1.160$\pm$2.014
_A3_ | 1.575$\pm$1.990 | 2.556$\pm$2.868 | 2.830$\pm$3.084
Table 4. _NRC_ for WikiQA dataset

##  5\. Results and Discussion

We focus on three research questions to investigate the impact of adversarial
attacks on ranking models.
RQ1: _What is the attacker’s success in changing a document’s position without
significantly changing the document?_ To answer this question, we measure an
attacker’s success (_S@k_) when we restrict the number of perturbed words to
one in each document. The results for $k=1$ and $k=5$ are given in Table 2.
Notice that _A0_ can change the rank of almost half of the relevant documents
but not beyond five positions. Both _A1_ and _A3_ can change the rank of all
the relevant documents by just changing _one term_ in the document. In case of
MSMarco, they can lower the rank of ¿81% relevant documents by more than four
positions except for DRMM ranker. Overall, we found that _A1_ has the highest
success rate among all the attackers as it has greater flexibility to change
the terms.

We report mean and variance of _NRC_ on the test sets in Table 3 and 4 for
MSMarco and WikiQA datasets respectively. Increasing the number of perturbed
words increases _NRC_ across all the attackers. On MSMarco dataset, KNRM is
the most vulnerable ranker across all the attackers. On average _A1_ can push
a relevant document beyond 11 non-relevant documents by changing only one
token when evaluated against KNRM ranker. On the other hand, the performance
of attackers across all the models is similar on the WikiQA dataset. Overall,
all the attackers perform better on MSMarco dataset compared to WikiQA. We
argue that the larger length of passages in MSMarco provides more room for
perturbations as opposed to the shorter length of answers in WikiQA.
RQ2: _What is the similarity between perturbed and original text when we
restrict the number of perturbed words to $p_{l}=\\{1,3,5\\}$ in each
document?_ Adversarial perturbations may cause the meaning of document text to
change. Thus, it is important to control this change such that perturbed words
are semantically similar to original text. We measure the semantic similarity
between embeddings of original text and perturbed text using cosine distance
as done in previous work (Wang et al., 2019). Figure 1 shows similarity b/w
perturbed and original text when 1, 3 or 5 tokens are changed in MSMarco
passage text for three different models. We only focus on similarity for _A1_
and _A3_ attackers due to space limitations.

Overall, the cosine similarity between perturbed and original text across
attackers is relatively high ($\sim$0.97), even though the document may be
pushed below $\sim$20 non-relevant documents with only _single_ token
perturbations. As expected, perturbing more tokens leads to lower similarity.
Cosine similarity drops to $\sim$0.90 across models for 5 word perturbations.
Both _A1_ and _A3_ attackers can push documents to relatively lower positions
with 1-3 token perturbations, however, we found that _A1_ tends to perturb
query tokens in passages to change ranker output. We found that _A1_ changed
query tokens in 65% (DRMM), 11% (Duet) and 2% (KNRM) documents in MSMarco and
50%, 17% and 3% documents in WikiQA respectively. However, _A3_ achieves
similar performance in terms of similarity and rank change _without_ changing
any query tokens.

(a) DRMM (_A1_)

(b) DUET (_A1_)

(c) KNRM (_A1_)

(d) DRMM (_A3_)

(e) DUET (_A3_)

(f) KNRM (_A3_)

Figure 1. _NRC_ vs. cosine sim on MSMarco where  blue=1 word,  orange=3 words and  green=5 words perturbations respectively. Model | Atk | WikiQA | MSMarco
---|---|---|---
1 token | 3 tokens | 1 token | 3 tokens
DRMM | _A1_ | 0.31$\pm$0.45 | 0.43$\pm$0.47 | 0.05$\pm$0.14 | 0.11$\pm$0.17
_A2_ | 0.005$\pm$0.06 | 0.005$\pm$0.37 | 0.001$\pm$0.05 | 0.01$\pm$0.11
_A3_ | 0.216$\pm$0.40 | 0.30$\pm$0.44 | 0.02$\pm$0.11 | 0.06$\pm$0.15
Duet | _A1_ | 0.24$\pm$0.41 | 0.37$\pm$0.46 | 0.59$\pm$0.40 | 0.68$\pm$0.35
_A2_ | 0.003$\pm$0.07 | -0.04$\pm$0.23 | 0.02$\pm$0.30 | 0.03$\pm$0.46
_A3_ | 0.226$\pm$0.40 | 0.35$\pm$0.45 | 0.56$\pm$0.40 | 0.61$\pm$0.39
KNRM | _A1_ | 0.22$\pm$0.41 | 0.30$\pm$0.44 | 0.53$\pm$0.37 | 0.59$\pm$0.34
_A2_ | 0.03$\pm$0.16 | 0.09$\pm$0.34 | 0.30$\pm$0.42 | 0.38$\pm$0.43
_A3_ | 0.218$\pm$0.40 | 0.31$\pm$0.44 | 0.52$\pm$0.38 | 0.59$\pm$0.34
Table 5. % drop in $P@5$ due to perturbed text

RQ3: _What is the ranker performance after adversarial attacks?_ We evaluate
model robustness against an adversarial attacker with P@5. We compute
perturbed $P@5$ by replacing the original document’s ($d_{i}$) ranker score
$s_{i}$ with the new score $s^{\prime}_{i}$ given by the ranker on the
perturbed input $d^{\prime}_{i}$. 222Note that ranker output for all other
documents in the list $d_{j\neq i}$ remains the same. So, for every document
the attacker perturbs, its new score replaces the old ranker score and $P@5$
is recomputed. We report the % drop in $P@5$ for both datasets in Table 5. We
find that _A1_ and _A3_ attackers are able to reduce $P@5$ significantly, in
some cases as much as $\sim$20% in WikiQA and $\sim$50% in MSMarco by changing
one token in the text. Although, _A3_ ’s drop in $P@5$ is lower than that of
_A1_ ’s across all datasets since it is penalized for changing query terms.

We also found %drop in $P@5$ to be a function of ranker performance. Models
with higher precision were harder to beat by the attacker, i.e., were more
robust to token changes in document text. For example, in WikiQA original
$P@5$ (mean,std) for DRMM, Duet and KNRM was 0.204$\pm$0.17, 0.207$\pm$0.18
and 0.22$\pm$0.20 respectively. It is interesting to note that all attackers
are able to reduce DRMM $P@5$ by single token perturbations by highest margin.
However, in MSMarco, DRMM $P@5$ is the highest amongst all other models, thus
hardest to fool by all attackers. We observe very little drop in precision for
_A2_ attacker across models in both datasets which indicates that very strict
attackers may not be able to find suitable candidates to perturb documents.
One interesting finding was that in some cases the attacker replaced document
text with _query tokens_ to lower document score as shown in Table 1.

##  6\. Conclusion

Adversarial attacks on classification models both in text and vision have
helped reduce the generalization error of such models. However, there is
limited literature on adversarial attacks on information retrieval models. In
this work, we explored effectiveness and quality of three simple methods of
attacking black box deep learning models. The attackers were designed to
change document text such that an information retrieval model is fooled into
lowering the document position. We found that perturbed text generated by
these attackers by changing few tokens is semantically similar to original
text and _can fool_ the ranker to push a relevant document below $\sim$2-3
non-relevant documents. Our findings can be further used to train rankers with
adversarial examples to reduce their generalization error.

## References

  * (1)
  * Bajaj et al. (2016) Payal Bajaj, Daniel Campos, Nick Craswell, Li Deng, Jianfeng Gao, Xiaodong Liu, Rangan Majumder, Andrew McNamara, Bhaskar Mitra, Tri Nguyen, Mir Rosenberg, Xia Song, Alina Stoica, Saurabh Tiwary, and Tong Wang. 2016.  MS MARCO: A Human Generated MAchine Reading COmprehension Dataset.  arXiv:cs.CL/1611.09268
  * Goodfellow et al. (2014) Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. 2014.  Explaining and Harnessing Adversarial Examples.  arXiv:stat.ML/1412.6572
  * Guo et al. (2016) Jiafeng Guo, Yixing Fan, Qingyao Ai, and W. Bruce Croft. 2016\.  A Deep Relevance Matching Model for Ad-Hoc Retrieval. In _Proc. CIKM_.
  * Jeffrey Pennington and Manning (2014) Richard Socher Jeffrey Pennington and Christopher D. Manning. 2014.  GloVe: Global Vectors for Word Representation. In _Proc. EMNLP_.
  * Liang et al. (2017) Bin Liang, Hongcheng Li, Miaoqiang Su, Pan Bian, Xirong Li, and Wenchang Shi. 2017\.  Deep text classification can be fooled.  _preprint arXiv:1704.08006_ (2017).
  * Mitra et al. (2017) Bhaskar Mitra, Fernando Diaz, and Nick Craswell. 2017\.  Learning to match using local and distributed representations of text for web search. In _Proc. WWW_.
  * Mitra et al. (2016) Bhaskar Mitra, Eric Nalisnick, Nick Craswell, and Rich Caruana. 2016.  A Dual Embedding Space Model for Document Ranking.  arXiv:1602.01137
  * Papernot et al. (2016) Nicolas Papernot, Patrick McDaniel, Ananthram Swami, and Richard Harang. 2016.  Crafting adversarial input sequences for recurrent neural networks. In _MILCOM 2016-2016 IEEE Military Communications Conference_. IEEE.
  * Robertson and Zaragoza (2009) Stephen Robertson and Hugo Zaragoza. 2009.  _The probabilistic relevance framework: BM25 and beyond_.  Now Publishers Inc.
  * Storn and Price (1997) Rainer Storn and Kenneth Price. 1997.  Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces.  _Journal of Global Optimization_ 11 (01 1997).
  * Su et al. (2019) J. Su, D. V. Vargas, and K. Sakurai. 2019.  One Pixel Attack for Fooling Deep Neural Networks.  _IEEE Transactions on Evolutionary Computation_ 23, 5 (2019).
  * Wang et al. (2019) Wenqi Wang, Benxiao Tang, Run Wang, Lina Wang, and Aoshuang Ye. 2019.  A survey on Adversarial Attacks and Defenses in Text.  _arXiv:1902.07285_ (2019).
  * Xiong et al. (2017) Chenyan Xiong, Zhuyun Dai, Jamie Callan, Zhiyuan Liu, and Russell Power. 2017.  End-to-End Neural Ad-Hoc Ranking with Kernel Pooling. In _Proc. SIGIR_.
  * Yang et al. (2015) Yi Yang, Wen tau Yih, and Christopher Meek. 2015.  WikiQA: A Challenge Dataset for Open-Domain Question Answering. In _Proc. EMNLP_.
  * Zhou et al. (2020) Mo Zhou, Zhenxing Niu, Le Wang, Qilin Zhang, and Gang Hua. 2020.  Adversarial Ranking Attack and Defense.