$\displaystyle\rho(f,\theta^{\star}({\mathbf{U}}\circ P))<10^{-2}$
$\displaystyle\iff\left(1-\max(0,\lVert{\bm{w}}_{1}\rVert\cos(\alpha_{1}))\right)^{2}<10^{-2},$
(175) $\displaystyle\iff\max(0,\lVert{\bm{w}}_{1}\rVert\cos(\alpha_{1}))>0.9.$
(176)

By the triangle inequality, we can get an upper bound on $\cos(\beta_{1})$ as,

$\displaystyle\sqrt{2(1-\cos(\beta_{1}))}$
$\displaystyle\geq\sqrt{2(1-0.001)}-\sqrt{2(1-\cos(\alpha_{1}))},$ (177)
$\displaystyle\cos(\beta_{i})$ $\displaystyle\leq
1-(\sqrt{(1-0.001)}-\sqrt{(1-0.9)})^{2}\leq 0.7.$ (178)

Therefore, $\max(0,\lVert{\bm{w}}_{t}\rVert\cos(\beta_{t}))\leq 0.7$, which
implies that

$\displaystyle\left(1-\max(\lVert{\bm{w}}_{t}\rVert\cos(\beta_{t}),0)\right)^{2}\geq(0.3)^{2}>10^{-2}.$
(179)

∎

In the following lemma, we prove a sample complexity lower bound of
$\Omega(\sigma^{2}kd)$ for FCNs on the sub-problem $\text{SSD}_{1}$ of DSD.

######  Lemma D.3.

Let ${\mathcal{F}}$ denote the class of functions represented by the set of
locally connected neural network models,
${\mathcal{M}}_{\mathcal{L}}[{\mathcal{W}}],$ as defined in 5. Let
$S^{n}\sim(\text{SSD}_{1})^{n}$ be the $n$ i.i.d. data samples drawn from
$\text{SSD}_{1}$. Consider the group
$\tilde{{\mathcal{U}}}\subseteq{\mathcal{O}}(kd)$, such that for all
${\mathbf{U}}\neq{\mathbf{V}}\in\tilde{{\mathcal{U}}}$,
$({\mathbf{U}}^{(1)}{\bm{w}}^{\star})^{T}({\mathbf{V}}^{(1)}{\bm{w}}^{\star})<10^{-3}$,
and for all ${\mathbf{U}}\in\tilde{{\mathcal{U}}}$, $t\in\\{2,\ldots,k\\}$,
${\mathbf{U}}^{(t)}{\bm{w}}^{\star}=e_{dt}$. Let $\xi\in\Xi$ encapsulate the
randomization, and let $\xi\sim P_{\Xi}$. If $\bar{\theta}(S^{n},\xi)$ is a
$\tilde{{\mathcal{U}}}$-equivariant algorithm then, for large enough $k,d$,

$\displaystyle n_{\delta}(\bar{\theta}_{n})=\Omega\left(\sigma^{2}d\right),$
(180)

where $\delta=0.5\times 10^{-2}$.

###### Proof.

We refer to the distribution $\text{SSD}_{1}$ by $P$. Since the algorithm
$\bar{\theta}_{n}$ is ${\mathcal{U}}$\- equivariant, lemma 5.1 gives us that
for all ${\mathbf{U}}\in\tilde{{\mathcal{U}}}$,

$\displaystyle\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}})$
$\displaystyle\overset{d}{=}\bar{\theta}(\\{{\mathbf{U}}{\bm{x}}_{i},y_{i}\\}_{n})({\mathbf{U}}{\bm{x}}),$
(181)
$\displaystyle\text{err}\left(\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}}),y\right)$
$\displaystyle\overset{d}{=}\text{err}\left(\bar{\theta}(\\{{\mathbf{U}}{\bm{x}}_{i},y_{i}\\}_{n})({\mathbf{U}}{\bm{x}}),y\right),$
(182) $\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\operatorname*{\mathbb{E}}_{({\bm{x}},y)\sim
P}\text{err}\left(\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}}),y\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\operatorname*{\mathbb{E}}_{({\bm{x}},y)\sim
P}\text{err}\left(\bar{\theta}(\\{{\mathbf{U}}{\bm{x}}_{i},y_{i}\\}_{n})({\mathbf{U}}{\bm{x}}),y\right),$
(183) $\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\operatorname*{\mathbb{E}}_{({\bm{x}},y)\sim
P}\left[\text{err}\left(\bar{\theta}_{n}({\bm{x}}),y\right)\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\operatorname*{\mathbb{E}}_{({\bm{x}},y)\sim{\mathbf{U}}\circ
P}\left[\text{err}\left(\bar{\theta}_{n}({\bm{x}}),y\right)\right]$ (184)
$\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\left[R\left(\bar{\theta}_{n},P\right)\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ P\right)\right].$ (185)

Taking $\sup$ on the right-hand side,

$\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\left[R\left(\bar{\theta}_{n},P\right)\right]$
$\displaystyle=\sup_{{\mathbf{U}}\circ P\in\tilde{{\mathcal{U}}}\circ
P}\operatorname*{\mathbb{E}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ
P\right)\right],$ (186)

An application of corollary A.1.1 gives the bound
$\ln(|\bar{{\mathcal{U}}}|)\geq 0.99d$.

In order to apply our variant of Fano’s Theorem 5.1, we set the following
variables: $\mathcal{P}=\tilde{{\mathcal{U}}}\circ P$;
${\mathcal{P}}_{\mathcal{V}}=\tilde{{\mathcal{U}}}\circ P$;
${\mathcal{F}},\>\Xi$, and $P_{\Xi}$ are already defined in the lemma;
$\Theta=\\{{\theta}\mid{\theta}\colon(({\mathcal{X}},{\mathcal{Y}})^{n},\Xi)\rightarrow{\mathcal{F}}\\}$;
$\theta^{\star}({\mathbf{U}}\circ
P)={\mathcal{M}}[[{\mathbf{U}}^{(1)}{\bm{w}}^{\star},..,{\mathbf{U}}^{(k)}{\bm{w}}^{\star},b^{\star}]]$,
where ${\mathbf{U}}\in\tilde{{\mathcal{U}}}$, $b^{\star}$ is some fixed value
in $(0,1)$444The claim and the proof do not depend on the chosen value of
$b^{\star}$.; and $\rho(f,\theta^{\star}({\mathbf{U}}\circ
P))=\left(1-\max(0,\lVert{\bm{w}}_{1}\rVert\cos(\alpha_{1}))\right)^{2}$,
where ${\mathbf{U}}\in\tilde{{\mathcal{U}}}$, and
$\cos(\alpha_{1})=\tfrac{{\bm{w}}_{1}^{T}{\mathbf{U}}^{(1)}{\bm{w}}^{\star}}{\lVert{\bm{w}}_{1}\rVert}$.
Recall from Lemma B.1 that $\text{KL}({\mathbf{U}}\circ
P\parallel{\mathbf{V}}\circ
P)\leq\tfrac{0.999}{\sigma^{2}}<\tfrac{1}{\sigma^{2}}$.

We are now ready to apply Fano’s Theorem 5.1, using the results from Lemmas
D.1,D.2, and 186,

$\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\left[R\left(\bar{\theta}_{n},P\right)\right]$
$\displaystyle\geq\sup_{{\mathbf{U}}\circ P\in\bar{{\mathcal{U}}}\circ
P}\operatorname*{\mathbb{E}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ
P\right)\right],$ (187)
$\displaystyle\geq\inf_{\theta\in\Theta}\sup_{{\mathbf{U}}\circ
P\in\bar{{\mathcal{U}}}\circ
P}\operatorname*{\mathbb{E}}\left[R\left({\theta}_{n},{\mathbf{U}}\circ
P\right)\right],$ (188) $\displaystyle\geq
10^{-2}\left(1-\tfrac{n/\sigma^{2}+\ln(2)}{0.99d}\right).$ (189)

From the above, it is easy to see that with $n=\tfrac{1}{4}\sigma^{2}d$
samples, the algorithm incurs an expected risk greater than
$\tfrac{1}{2}10^{-2}$, proving the result. ∎

We now present the formal statement and the proof of Theorem 7.1, which
establishes the $\Omega(\sigma^{2}kd)$ sample complexity lower bound for LCNs
when trained on DSD.

######  Theorem 7.1 (Formal).

Let ${\mathcal{F}}$ denote the class of functions represented by the set of
locally connected neural network models,
${\mathcal{M}}_{\mathcal{L}}[{\mathcal{W}}],$ as defined in 4. Let
$S^{n}\sim(\text{DSD})^{n}$ be the $n$ i.i.d. data samples drawn from DSD. We
define the following groups,
${\mathcal{U}}_{1}\coloneqq\\{\text{Block}\left({\mathbf{U}}_{1},\ldots,{\mathbf{U}}_{k}\right)\mid{\mathbf{U}}_{i}\in{\mathcal{O}}(d)\\}$,
${\mathcal{U}}_{2}\coloneqq\\{{\mathbf{U}}\in{\mathcal{O}}_{p}(kd)\mid\text{idx}_{kd}({\mathbf{U}}{\bm{e}}_{(i-1)d+1})+j-1=\text{idx}_{kd}({\mathbf{U}}{\bm{e}}_{(i-1)d+j}),\>\forall
i\in[k],j\in[d]\\}$, and
${\mathcal{U}}={\mathcal{U}}_{1}\star{\mathcal{U}}_{2}$. Let $\\{F_{t}\\}_{T}$
be the set of update functions, and let the model parameters be initialized as
${\bm{w}}^{0}\sim W$. If
$\bar{\theta}_{n}(S^{n},{\bm{w}}^{0};{\mathcal{M}}_{F}[{\mathcal{W}}],\\{F_{t}\\}_{T})$
is a ${\mathcal{U}}$-equivariant algorithm, then, for large enough $k,d$, the
sample complexity is given by,

$\displaystyle
n_{\delta}(\bar{\theta}_{n})=\max(\Omega\left(\sigma^{2}kd\right),40k),$ (190)

where $\delta=0.25\times 10^{-2}$.

###### Proof.

For simplicity will refer to the distribution DSD by $P$, and the distribution
$\text{SSD}_{t}$ by $Q_{t}$, for $t\in[k]$. Since the algorithm
$\bar{\theta}_{n}$ is ${\mathcal{U}}$-equivariant, lemma 5.1 gives us that for
all ${\mathbf{U}}\in{\mathcal{U}}$,

$\displaystyle\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}})$
$\displaystyle\overset{d}{=}\bar{\theta}(\\{{\mathbf{U}}{\bm{x}}_{i},y_{i}\\}_{n})({\mathbf{U}}{\bm{x}}),$
(191)
$\displaystyle\text{err}\left(\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}}),y\right)$
$\displaystyle\overset{d}{=}\text{err}\left(\bar{\theta}(\\{{\mathbf{U}}{\bm{x}}_{i},y_{i}\\}_{n})({\mathbf{U}}{\bm{x}}),y\right),$
(192) $\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\operatorname*{\mathbb{E}}_{({\bm{x}},y)\sim
P}\text{err}\left(\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}}),y\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\operatorname*{\mathbb{E}}_{({\bm{x}},y)\sim
P}\text{err}\left(\bar{\theta}(\\{{\mathbf{U}}{\bm{x}}_{i},y_{i}\\}_{n})({\mathbf{U}}{\bm{x}}),y\right),$
(193) $\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\left[R\left(\bar{\theta}_{n},P\right)\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ P\right)\right],$ (194)
$\displaystyle=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\frac{1}{k}\sum_{i=1}^{k}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ
Q_{i}\right)\right],$ (195)
$\displaystyle=\frac{1}{k}\sum_{i=1}^{k}\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ Q_{i}\right)\right].$
(196)

To simplify 196, we begin by showing that the expected risk incurred by the
algorithm is the same for every distribution ${\mathbf{U}}\circ Q_{i}$.
Specifically, for all $i,j\in[k]$,

$\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ
Q_{i}\right)\right]=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ Q_{j}\right)\right].$
(197)

For $i=j$, the result trivially holds. So we can assume that $i\neq j$.
Observe that because of the block structure of ${\mathcal{U}}_{1}$,
${\mathbf{U}}{\bm{\mu}}_{i}\in\text{Span}(\\{{\bm{e}}_{(i-1)d+j}\\}_{j\in[d]})$
$\forall i\in[k]$. Therefore
$\exists{\mathbf{U}}_{1}\in{\mathcal{U}}_{1},{\mathbf{U}}_{2}\in{\mathcal{U}}_{2}$,
such that,
${\mathbf{U}}_{1}{\mathbf{U}}_{2}{\mathbf{U}}{\bm{\mu}}_{l}={\mathbf{U}}{\bm{\mu}}_{l}$
for all $l\notin\\{i,j\\}$, and
${\mathbf{U}}_{1}{\mathbf{U}}_{2}{\mathbf{U}}{\bm{\mu}}_{i}={\mathbf{U}}{\bm{\mu}}_{j}$,
${\mathbf{U}}_{1}{\mathbf{U}}_{2}{\mathbf{U}}{\bm{\mu}}_{j}={\mathbf{U}}{\bm{\mu}}_{i}$.
Since
$\tilde{{\mathbf{U}}}\coloneqq{\mathbf{U}}_{1}{\mathbf{U}}_{2}\in{\mathcal{U}}$
and $\bar{\theta}_{n}$ is a ${\mathcal{U}}$-orthogonally equivariant
algorithm, from lemma 5.1,

$\displaystyle\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}})$
$\displaystyle\overset{d}{=}\bar{\theta}(\\{{\mathbf{U}}_{1}{\bm{x}}_{i},y_{i}\\}_{n})({\mathbf{U}}_{1}{\bm{x}}),$
(198)
$\displaystyle\text{err}\left(\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}}),y\right)$
$\displaystyle\overset{d}{=}\text{err}\left(\bar{\theta}(\\{{\mathbf{U}}_{1}{\bm{x}}_{i},y_{i}\\}_{n})({\mathbf{U}}_{1}{\bm{x}}),y\right),$
(199) $\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\operatorname*{\mathbb{E}}_{{\mathbf{U}}\circ
Q_{i}}\left[\text{err}\left(\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}}),y\right)\right]=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\operatorname*{\mathbb{E}}_{{\mathbf{U}}\circ
Q_{i}}\big{[}\text{err}(\bar{\theta}(\\{{\mathbf{U}}_{1}{\bm{x}}_{i},y_{i}\\}_{n})\\\
({\mathbf{U}}_{1}{\bm{x}}),y)\big{]},$ (200)
$\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\operatorname*{\mathbb{E}}_{{\mathbf{U}}\circ
Q_{i}}\left[\text{err}\left(\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})({\bm{x}}),y\right)\right]=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}_{1}{\mathbf{U}}\circ
P)^{n}}\operatorname*{\mathbb{E}}_{{\mathbf{U}}_{1}{\mathbf{U}}\circ
Q_{i}}\big{[}\text{err}\big{(}\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{n})\\\
({\bm{x}}),y\big{)}\big{]}.$ (201)

From the construction of ${\mathbf{U}}_{1}$, we know that
${\mathbf{U}}_{1}{\mathbf{U}}\circ P\overset{d}{=}{\mathbf{U}}\circ P$, and
${\mathbf{U}}_{1}{\mathbf{U}}\circ Q_{i}\overset{d}{=}{\mathbf{U}}\circ
Q_{j}$,

$\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\operatorname*{\mathbb{E}}_{{\mathbf{U}}\circ
Q_{i}}\left[\text{err}\left(\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{i})({\bm{x}}),y\right)\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\operatorname*{\mathbb{E}}_{{\mathbf{U}}\circ
Q_{j}}\big{[}\text{err}\left(\bar{\theta}(\\{{\bm{x}}_{i},y_{i}\\}_{i})({\bm{x}}),y\right)\big{]},$
(202) $\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ Q_{i}\right)\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ Q_{j}\right)\right].$
(203)

This proves the claim 197. Substituting it back into 196,

$\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\left[R\left(\bar{\theta}_{n},P\right)\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ Q_{1}\right)\right],$
(204)
$\displaystyle=\sup_{{\mathbf{U}}\in\tilde{{\mathcal{U}}}}\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left(\bar{\theta}_{n},{\mathbf{U}}\circ Q_{1}\right)\right],$
(205)

where $\tilde{{\mathcal{U}}}\subseteq{\mathcal{U}}_{1}$ is the set of "hard
instances" such that, for all
${\mathbf{U}}\neq{\mathbf{V}}\in\tilde{{\mathcal{U}}}$,
$({\mathbf{U}}{\bm{\mu}}_{1})^{T}({\mathbf{V}}{\bm{\mu}}_{1})<10^{-3}$, and
for all ${\mathbf{U}}\in\tilde{{\mathcal{U}}}$, and $i\in\\{2,\ldots,k\\}$,
${{\mathbf{U}}}{\bm{\mu}}_{i}={\bm{e}}_{dt}$, Let $\Xi={\mathcal{W}}$,
$P_{\Xi}=W$, and
$\Theta=\\{{\theta}\mid{\theta}\colon(({\mathcal{X}},{\mathcal{Y}})^{n},\Xi)\rightarrow{\mathcal{F}}\\}$.
It is easy to note that $\bar{\theta}_{n}\in\Theta$. Therefore,

$\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\left[R\left(\bar{\theta}_{n},P\right)\right]$
$\displaystyle\geq\inf_{\theta_{n}\in\Theta}\sup_{{\mathbf{U}}\in\tilde{{\mathcal{U}}}}\operatorname*{\mathbb{E}}_{S^{n}\sim({\mathbf{U}}\circ
P)^{n}}\left[R\left({\theta}_{n},{\mathbf{U}}\circ Q_{1}\right)\right],$ (206)

We will now perform a series of reductions to lower bound the above minimax
problem, with the minimax problem of learning $\text{SSD}_{1}$. The main idea
behind these reductions is to demonstrate that a given minimax problem can be
’simulated’ by a more tractable one, and thus the tractable problem serves as
a lower bound on the original problem.

Define the set of algorithms,
$\Theta_{1}=\\{{\theta}\mid{\theta}\colon(([k],{\mathcal{X}},{\mathcal{Y}})^{n},\Xi)\rightarrow{\mathcal{F}}\\}$,
and let ${\mathbf{U}}\circ\tilde{P}$ be the indexed distribution with the
generative story: Sample $j\sim\text{Unif}[k]$, then sample
$({\bm{x}},y)\sim{\mathbf{U}}\circ Q_{j}$, and then return $(j,{\bm{x}},y)$.
We can then lower bound 206 as,

$\displaystyle\geq\inf_{\theta\in\Theta_{1}}\sup_{{\mathbf{U}}\in\tilde{{\mathcal{U}}}}\operatorname*{\mathbb{E}}_{{\bm{w}}\sim
W}\operatorname*{\mathbb{E}}_{(j,{\bm{x}},y)^{n}\sim({\mathbf{U}}\circ\tilde{P})^{n}}\left[R\left(\theta((j,{\bm{x}},y)^{n},{\bm{w}}),{\mathbf{U}}\circ
Q_{1}\right)\right].$ (207)

The inequality follows from the fact that for every $\theta^{a}_{n}\in\Theta$,
there exists $\theta^{b}_{n}\in\Theta_{1}$, that discards the index $j$ and
returns the output of $\theta^{a}_{n}$.

We define $n_{1}$ to be the random variable that corresponds to the number of
samples drawn from ${\mathbf{U}}\circ Q_{1}$. Using Berstein’s inequality, we
get that $\tfrac{n}{2k}\leq n_{1}\leq m\coloneqq\tfrac{3n}{2k}$, holds with
probability $\geq c\coloneqq 1-2\exp(\tfrac{-n}{10k})$. We will refer to this
event as $E$. Then we can lower bound 207,

$\displaystyle\geq
c\inf_{\theta\in\Theta_{1}}\sup_{{\mathbf{U}}\in\tilde{{\mathcal{U}}}}\operatorname*{\mathbb{E}}_{{\bm{w}}\sim
W}\operatorname*{\mathbb{E}}_{(j,{\bm{x}},y)^{n}\sim({\mathbf{U}}\circ\tilde{P})^{n}}\left[R\left(\theta((j,{\bm{x}},y)^{n},{\bm{w}}),{\mathbf{U}}\circ
Q_{1}\right)\mid E\right].$ (208)

For the next reduction, we define $n_{i}$ to be the random variable
corresponding to the number of samples drawn from the distribution
${\mathbf{U}}\circ Q_{i}$, for all $i\in[k]$. Let
${\bm{y}}\sim(\text{Unif}[{\mathcal{Y}}])^{n}$ be a uniform random vector over
$\\{+1,-1\\}$ of size $n$ , and
${\bm{\epsilon}}\sim{\mathcal{N}}(\mathbf{0}_{nkd},\mathbf{I}_{nkd})$ be a
vector of i.i.d. standard Gaussian random variables. Let
$\Theta_{2}=\\{{\theta}\mid{\theta}\colon(({\mathcal{X}},{\mathcal{Y}})^{m}\times({\mathbb{R}}^{kd})^{k-1}\times({\mathbb{N}}\cup\\{0\\})^{k}\times({\mathbb{R}})^{n}\times{\mathbb{R}}^{nkd}\times{\mathcal{W}})\rightarrow{\mathcal{F}}\\}$
be a set of algorithms that take as input the training data,
$\\{{\mathbf{U}}{\bm{\mu}}\\}_{i=2}^{k}$ mean vectors, the number of samples
to be drawn from each mean, pre-sampled values of ${\bm{y}}$ and
${\bm{\epsilon}}$, and the parameter initialization respectively. It
subsequently returns a function within ${\mathcal{F}}$. Then we can lower
bound 208 as,

$\displaystyle\geq
c\inf_{\theta\in\Theta_{2}}\sup_{{\mathbf{U}}\in\tilde{{\mathcal{U}}}}\operatorname*{\mathbb{E}}_{{\bm{w}}\sim
W}\operatorname*{\mathbb{E}}_{\\{n_{i}\\}_{1}^{k}}\operatorname*{\mathbb{E}}_{{\bm{y}},{\bm{\epsilon}}}\operatorname*{\mathbb{E}}_{S^{m}\sim({\mathbf{U}}\circ
Q_{1})^{m}}\left[R\left(\theta(S^{m},\\{{\mathbf{U}}{\bm{\mu}}_{i}\\}_{2}^{k},\\{n_{i}\\}_{1}^{k},{\bm{y}},{\bm{\epsilon}},{\bm{w}}),{\mathbf{U}}\circ
Q_{1}\right)\mid E\right].$ (209)

The last inequality follows from the fact that for every
$\theta^{a}_{n}\in\Theta_{1}$, there exists $\theta^{b}_{n}\in\Theta_{2}$,
that first deterministically creates the indexed dataset using
$S^{m},\\{{\mathbf{U}}{\bm{\mu}}_{i}\\}_{2}^{k},\\{n_{i}\\}_{1}^{k},{\bm{y}},{\bm{\epsilon}}$
and then runs $\theta^{a}_{n}$. For notational brevity, we define
$\Xi_{1}\coloneqq({\mathbb{N}}\cup\\{0\\})^{k}\times({\mathbb{R}})^{n}\times{\mathbb{R}}^{nkd}\times{\mathcal{W}}$,
to encapsulate the randomness in
$\\{n_{i}\\}_{1}^{k},{\bm{y}},{\bm{\epsilon}}$, and ${\bm{w}}$. We denote its
associated product distribution by $P_{\Xi_{1}}$. Rewriting 209,

$\displaystyle=c\inf_{\theta\in\Theta_{2}}\sup_{{\mathbf{U}}\in\tilde{{\mathcal{U}}}}\operatorname*{\mathbb{E}}_{{\mathbf{\xi}}\sim
P_{\Xi_{1}}}\operatorname*{\mathbb{E}}_{S^{m}\sim({\mathbf{U}}\circ
Q_{1})^{m}}\left[R\left(\theta(S^{m},\\{{\mathbf{U}}{\bm{\mu}}_{i}\\}_{2}^{k},{\mathbf{\xi}}),{\mathbf{U}}\circ
Q_{1}\right)\right].$ (210)

From the construction of "hard instances", we know that for all
${\mathbf{U}}\in\tilde{{\mathcal{U}}}$, $t\in\\{2,\ldots,k\\}$,
${\mathbf{U}}{\bm{\mu}}_{t}=e_{dt}$. Substituting this back in 210,

$\displaystyle=c\inf_{\theta\in\Theta_{2}}\sup_{{\mathbf{U}}\in\tilde{{\mathcal{U}}}}\operatorname*{\mathbb{E}}_{{\mathbf{\xi}}\sim
P_{\Xi_{1}}}\operatorname*{\mathbb{E}}_{S^{m}\sim({\mathbf{U}}\circ
Q_{1})^{m}}\left[R\left(\theta(S^{m},\\{e_{di}\\}_{2}^{k},{\mathbf{\xi}}),{\mathbf{U}}\circ
Q_{1}\right)\right].$ (211)

Note that the set $\\{e_{di}\\}_{i=2}^{k}$ is fixed and known. Consider,
$\Theta_{3}\coloneqq\\{{\theta}\mid{\theta}\colon(({\mathcal{X}},{\mathcal{Y}})^{m}\times\Xi_{1})\rightarrow{\mathcal{F}}\\}$,
as the set of algorithms. For every $\theta^{a}_{n}\in\Theta_{2}$, there
exists $\theta^{b}_{n}\in\Theta_{3}$ which runs $\theta^{a}_{n}$ using the
input data, randomization $\xi$, and the known set $\\{e_{di}\\}_{i=2}^{k}$.
Therefore, we can bound 211,

$\displaystyle\geq
c\inf_{\theta\in\Theta_{3}}\sup_{{\mathbf{U}}\in\tilde{{\mathcal{U}}}}\operatorname*{\mathbb{E}}_{{\mathbf{\xi}}\sim
P_{\Xi_{1}}}\operatorname*{\mathbb{E}}_{S^{m}\sim({\mathbf{U}}\circ
Q_{1})^{m}}\left[R\left(\theta(S^{m},{\mathbf{\xi}}),{\mathbf{U}}\circ
Q_{1}\right)\right],$ (212)

We have already proven a lower bound for the above problem in Lemma D.3,
specifically refer to equation 186. Substituting that result,

$\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\left[R\left(\bar{\theta}_{n},P\right)\right]$ $\displaystyle\geq
c10^{-2}\left(1-\tfrac{m/\sigma^{2}+\ln(2)}{0.99d}\right),$ (213)
$\displaystyle\geq
c10^{-2}\left(1-\tfrac{\tfrac{3n}{2k\sigma^{2}}+\ln(2)}{0.99d}\right),$ (214)
$\displaystyle\geq\left(1-2\exp(\tfrac{-n}{10k})\right)10^{-2}\left(1-\tfrac{\tfrac{3n}{2k\sigma^{2}}+\ln(2)}{0.99d}\right).$
(215)

Using $n\geq 40k$, we can bound
$c\geq\left(1-2\exp(-\ln(4))\right)=\tfrac{1}{2}$. And, choosing
$n=\tfrac{1}{6}\sigma^{2}kd$, we can bound
$\left(1-\tfrac{\tfrac{3n}{2k\sigma^{2}}+\ln(2)}{0.99kd}\right)=\left(1-\tfrac{\tfrac{kd}{4}+\ln(2)}{0.99kd}\right)\geq\tfrac{1}{2}$.
Therefore, we have the result,

$\displaystyle\operatorname*{\mathbb{E}}_{S^{n}\sim
P^{n}}\left[R\left(\bar{\theta}_{n},P\right)\right]\geq\tfrac{1}{4}10^{-2}.$
(216)

∎

###  D.2 CNN Upper Bound

######  Theorem 7.2 (Formal).

Let ${\mathcal{F}}$ denote the class of functions represented by the set of
locally connected neural network models,
${\mathcal{M}}_{\mathcal{C}}[{\mathcal{W}}],$ as defined in 4.2. Let the input
data be drawn from the DSD distribution, $S^{n}\sim(\text{DSD})^{n}$, with
$\sigma=\tilde{O}(\tfrac{1}{\sqrt{k}})$. We define the group
${\mathcal{U}}\coloneqq\\{\text{Block}\left({\mathbf{U}}_{1},\ldots,{\mathbf{U}}_{k}\right)\mid{\mathbf{U}}_{i}\in{\mathcal{O}}(d),{\mathbf{U}}_{i}={\mathbf{U}}_{j}\\}$.
Then there exists a weight initialization distribution $W$ and update
functions $\\{F_{t}\\}_{T}$ such that
$\bar{\theta}_{n}({\mathcal{M}}_{C}[{\mathcal{W}}],\\{F_{t}\\}_{T},W,S^{n})$
is an ${\mathcal{U}}$-equivariant algorithm and, if $k,d$ are large enough,
then

$\displaystyle
n_{\delta}(\bar{\theta}_{n})=\max(O\left(\sigma^{2}(d+k)\ln(kd)\right),10),$
(217)

for some constant $\delta=O(1)$.

###### Proof.

The outline of the proof will run parallel to the approach taken in the proof
of Theorem 6.2. We will first present the algorithm $\bar{\theta}_{n}$, then
show it is a ${\mathcal{U}}$-equivariant algorithm and then derive the
required sample complexity bound upper bound.

1\. Algorithm Definition

To define the algorithm $\bar{\theta}_{n}$, we need to specify its components:
the model ${\mathcal{M}}_{C}[{\mathcal{W}}]$, the initialization distribution
$W$, and the update functions $\\{F_{t}\\}_{T}$. At iteration $t=0$, we
initialize the model parameter ${\bm{v}}^{0}=[{\bm{w}}^{0},b^{0}]$ as
${\bm{w}}^{0}\sim{\mathcal{N}}(\mathbf{0},\gamma{\mathbf{I}}_{d})$, where
$\gamma^{-1}=100k^{2}d^{2}$, and bias is set as $b^{0}=0$. The superscript
denotes the iteration number. To specify the update functions, we define the
empirical loss function,

$\displaystyle
l\colon({\mathcal{W}},({\mathcal{X}},{\mathcal{Y}})^{n})\rightarrow{\mathbb{R}}\coloneqq\tfrac{1}{n}\sum_{j=1}^{n}\left(y_{i}-\sum_{i=1}^{k}\phi_{b}({\bm{w}}^{T}{\bm{x}}^{(i)}_{j})\right)^{2}.$
(218)

The algorithm has $T=2$ iterations. For simpler analysis, we divide the
dataset, $S^{n}$, into two equal sized datasets $S^{m}_{1}$, and $S^{m}_{1}$,
with $m\coloneqq\tfrac{n}{2}$ samples each. The update function for each
$t\in\\{1,2\\}$ is,

$\displaystyle F_{t}({\bm{v}},S_{t}^{m})$
$\displaystyle\coloneqq\left[\tfrac{{\bm{w}}-\eta_{t}\nabla_{{\bm{w}}}l({\bm{w}},b;S_{t}^{m})}{\lVert{\bm{w}}-\eta_{t}\nabla_{{\bm{w}}}l({\bm{w}},b;S_{t}^{m})\rVert}\>;\>b_{t}\right],$
(219)

where
$\eta_{1}=1,\eta_{2}=10^{3},b_{1}=\tfrac{1}{100}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}},b_{2}=10^{-4}$.

2\. Algorithm is Equivariant

To establish that $\bar{\theta}_{n}$ is ${\mathcal{U}}$-equivariant, we verify
the three conditions specified in Definition 6. We define the group,
${\mathcal{V}}\coloneqq\\{\text{Block}({\mathbf{V}},{\mathbf{I}}_{1})\mid{\mathbf{V}}\in{\mathcal{O}}(d)\\}$,
where ${\mathbf{I}}_{1}$ is the identity matrix of size $1$.

For ${\bm{x}},y\in({\mathcal{X}},{\mathcal{Y}})$,
${\mathbf{U}}\in{\mathcal{U}}$, ${\bm{w}}\in{\mathbb{R}}^{d}$,
$b\in{\mathbb{R}}_{+}$, choose
${\mathbf{V}}=\text{Block}(\\{{\mathbf{U}}^{(1)},{\mathbf{I}}_{1}\\})\in{\mathcal{V}}$,
without loss of generality, as for all $i,j$,
${\mathbf{U}}^{(i)}={\mathbf{U}}^{(j)}$. Then, the property 1 of equivariance
holds as,

$\displaystyle{\mathcal{M}}_{C}[{\bm{v}}]({\bm{x}})=\sum_{i=1}^{k}\phi_{b}({\bm{w}}^{T}{\bm{x}}^{(i)})=\sum_{i=1}^{k}\phi_{b}({\bm{w}}^{T}({\mathbf{U}}^{(1)})^{T}{\mathbf{U}}^{(i)}{\bm{x}}^{(i)})={\mathcal{M}}_{C}[{\mathbf{V}}{\bm{v}}]({\mathbf{U}}{\bm{x}}).$
(220)

For all $t\in[2]$ and $S_{t}^{m}\in({\mathcal{X}},{\mathcal{Y}})^{m}$ the
second property 2 follows as,

$\displaystyle F_{t}\left({\mathbf{V}}{\bm{v}},{\mathbf{U}}\circ
S_{t}^{m}\right)$
$\displaystyle=\left[\tfrac{{\mathbf{U}}^{(1)}{\bm{w}}-\eta_{t}\nabla_{{\mathbf{U}}^{(1)}{\bm{w}}}l({\mathbf{V}}{\bm{v}};{\mathbf{U}}\circ
S^{m}_{t})}{\lVert{\mathbf{U}}^{(1)}{\bm{w}}-\eta_{t}\nabla_{{\mathbf{U}}^{(1)}{\bm{w}}}l({\mathbf{V}}{\bm{v}};{\mathbf{U}}\circ
S^{m}_{t})\rVert}\>;\>b_{t}\right],$ (221)
$\displaystyle=\left[\tfrac{{\mathbf{U}}^{(1)}\left({\bm{w}}-\eta_{t}\nabla_{{\bm{w}}}l({\bm{v}};S^{m}_{t})\right)}{\lVert{\mathbf{U}}^{(1)}\left({\bm{w}}-\eta_{t}\nabla_{{\bm{w}}}l({\bm{v}};S^{m}_{t})\right)\rVert}\>;\>b_{t}\right],$
(222)
$\displaystyle=\left[\tfrac{{\mathbf{U}}^{(1)}\left({\bm{w}}-\eta_{t}\nabla_{{\bm{w}}}l({\bm{v}};S^{m}_{t})\right)}{\lVert{\bm{w}}-\eta_{t}\nabla_{{\bm{w}}}l({\bm{v}};S^{m}_{t})\rVert}\>;\>b_{t}\right],$
(223) $\displaystyle={\mathbf{V}}F_{t}\left({\bm{v}},S^{m}_{t}\right).$ (224)

And as for property 3, observe that,

$\displaystyle{\mathbf{V}}{\bm{v}}^{0}=[{\mathbf{U}}^{(1)}{\bm{w}}^{0}b^{0}],\overset{d}{=}[{\bm{w}}^{0},b^{0}]={\bm{v}},$
(225)

holds for all ${\mathbf{V}}\in{\mathcal{V}}$.

3\. Algorithm Analysis

We analyze the algorithm, with $n=\max(2\sigma^{2}(k+d)\ln(kd),10)$ samples,
to establish that $\bar{\theta}_{n}$ achieve an expected risk of at most
$\delta=2.5\times 10^{-3}$. We set
$\sigma\leq\tfrac{1}{100\sqrt{k\ln(kd)^{3}}}$. The outline of the proof is as
follows: we first prove that after the first update step, the alignment of
${\bm{w}}^{1}$ with unknown signal vector ${\bm{w}}^{\star}$ is
$\Omega(\sqrt{\tfrac{1}{k}})$. In the second step, we use this alignment is
reliably threshold out the "noise" patches, while letting the "signal" patch
pass through the first hidden layer. We then show that this denoising effect,
enables us to recover the signal with an alignment of $\Omega(1)$, which would
imply that the risk of the CNN on the task $\leq\delta$.

3a. Update Step 1

We define
$\hat{{\bm{w}}}^{1}={\bm{w}}^{0}-\nabla_{{\bm{w}}^{0}}l({\bm{w}}^{0},0;S_{1}^{m})$
to be the unnormalized parameter vector ${\bm{w}}^{1}$, and therefore the
alignment with the signal is given by
$({\bm{w}}^{1})^{T}{\bm{w}}^{\star}=\tfrac{(\hat{{\bm{w}}}^{1})^{T}{\bm{w}}^{\star}}{\lVert\hat{{\bm{w}}}^{1}\rVert}$.
To analyze $\hat{{\bm{w}}}^{1}$, we first evaluate the gradient with respect
to ${\bm{w}}^{0}$, $\nabla_{{\bm{w}}^{0}}l({\bm{w}}^{0},0;S_{1}^{m})$,

$\displaystyle\nabla_{{\bm{w}}^{0}}l({\bm{w}}^{0},0;S_{1}^{m})$
$\displaystyle=\tfrac{1}{m}\sum_{j=1}^{m}\nabla_{{\bm{w}}^{0}}\left(y_{i}-\sum_{i=1}^{k}\phi_{0}(({\bm{w}}^{0})^{T}{\bm{x}}^{(i)}_{j})\right)^{2},$
(226)
$\displaystyle=\tfrac{-2}{m}\sum_{j=1}^{m}\left(y_{j}-\sum_{i=1}^{k}\phi_{0}(({\bm{w}}^{0})^{T}{\bm{x}}^{(i)}_{j}))\right)\left(\sum_{i=1}^{k}{\bm{x}}^{(i)}_{j}\phi^{\prime}_{0}(({\bm{w}}^{0})^{T}{\bm{x}}^{(i)}_{j}))\right),$
(227)
$\displaystyle=\tfrac{-2}{m}\sum_{j=1}^{m}\left(1-\sum_{i=1}^{k}y_{j}({\bm{w}}^{0})^{T}{\bm{x}}^{(i)}_{j})\right)\left(\sum_{i=1}^{k}y_{j}{\bm{x}}^{(i)}_{j}\right),$
(228) $\displaystyle\coloneqq\tfrac{-2}{m}\sum_{j=1}^{m}\alpha_{j}\beta_{j},$
(229)

where $\phi^{\prime}_{0}(x)\coloneqq\tfrac{d}{dx}\phi_{0}(x)$. We have used
the facts that $\phi_{0}$ is the identity function, and $\phi_{0}^{\prime}$ is
the constant function $1$ . And, $\alpha_{j}\coloneqq
1-\sum_{i=1}^{k}y_{j}({\bm{w}}^{0})^{T}{\bm{x}}^{(i)}_{j}$,
$\beta_{j}\coloneqq\sum_{i=1}^{k}y_{j}{\bm{x}}^{(i)}_{j}$.

To further analyze 229, we first prove high probability bounds for
$\alpha_{j}$, $j\in[m]$. From the initialization distribution $W$, we know
that ${\bm{w}}^{0}\overset{d}{=}\gamma{\bm{\epsilon}}$, where
${\bm{\epsilon}}$ is the Gaussian random vector defined as
${\bm{\epsilon}}\sim{\mathcal{N}}(\mathbf{0},{\mathbf{I}}_{d})$. And from the
input distribution DSD, we know that
${\bm{x}}_{j}^{(i)}=y_{j}r_{ij}{\bm{w}}^{\star}+\sigma{\bm{\epsilon}}_{j}^{(i)}$,
for all $i$ in $[k]$. Here,
${\bm{\epsilon}}_{j}^{(i)}\sim{\mathcal{N}}(\mathbf{0},{\mathbf{I}}_{d})$ is
also a Gaussian random vector, and $r_{ij}=1$, if the signal patch appears in
the $j$-th data sample appears in the $i$-th patch, and $0$ otherwise.

$\displaystyle\alpha_{j}$
$\displaystyle=1-\sum_{i=1}^{k}y_{j}({\bm{w}}^{0})^{T}{\bm{x}}^{(i)}_{j},$
(230)
$\displaystyle=1-\sum_{i=1}^{k}r_{ij}y_{j}^{2}\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}-\sum_{i=1}^{k}y_{j}\gamma\sigma{\bm{\epsilon}}^{T}{\bm{\epsilon}}_{j}^{(i)},$
(231)
$\displaystyle=1-\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}-\sum_{i=1}^{k}y_{j}\gamma\sigma{\bm{\epsilon}}^{T}{\bm{\epsilon}}_{j}^{(i)},$
(232)

We can now bound the range of $\alpha_{j}$ as,

$\displaystyle
1+|\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}|+|\sum_{i=1}^{k}\gamma\sigma{\bm{\epsilon}}^{T}{\bm{\epsilon}}_{j}^{(i)}|\geq\alpha_{j}\geq
1-|\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}|-|\sum_{i=1}^{k}\gamma\sigma{\bm{\epsilon}}^{T}{\bm{\epsilon}}_{j}^{(i)}|.$
(233)

We first upper bound $|\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}|$. Since the
norm of the signal is $1$, $\lVert{\bm{w}}^{\star}\rVert=1$,
${\bm{\epsilon}}^{T}{\bm{w}}^{\star}\sim{\mathcal{N}}(0,1)$, and

$\displaystyle|\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}|\leq\tfrac{1}{100k^{2}d^{2}}|{\bm{\epsilon}}^{T}{\bm{w}}^{\star}|\leq\tfrac{1}{8},$
(234)

with probability $\geq 1-2\Phi(-10k^{2}d^{2})\geq 1-10^{-6}$, for large enough
$k,d$. Next, we provide an upper bound for
$|\sum_{i=1}^{k}\gamma\sigma{\bm{\epsilon}}^{T}{\bm{\epsilon}}_{j}^{(i)}|$,
for all $j$. For this we analyze,

$\displaystyle\max_{j\in[m]}|\sum_{i=1}^{k}\gamma\sigma{\bm{\epsilon}}^{T}{\bm{\epsilon}}_{j}^{(i)}|$
$\displaystyle=\gamma\sigma\max_{j\in[m]}|{\bm{\epsilon}}^{T}\sum_{i=1}^{k}{\bm{\epsilon}}_{j}^{(i)}|\overset{d}{=}\gamma\sigma\max_{j\in[m]}|\sqrt{k}{\bm{\epsilon}}^{T}\bar{{\bm{\epsilon}}}_{j}|,$
(235)
$\displaystyle=\gamma\sigma\sqrt{k}\max_{j\in[m]}|\tfrac{\lVert{\bm{\epsilon}}\rVert}{\lVert{\bm{\epsilon}}\rVert}{\bm{\epsilon}}^{T}\bar{{\bm{\epsilon}}}_{j}|\leq
6\gamma\sigma\sqrt{kd}\>\max_{j\in[m]}\big{|}\tfrac{{\bm{\epsilon}}^{T}\bar{{\bm{\epsilon}}}_{j}}{\lVert{\bm{\epsilon}}\rVert}\big{|},$
(236)

with probability $\geq 1-2\times 10^{-6}$. The last inequality 236 follows
from the concentration of the norm of a Gaussian random variable,
$\mathbb{P}[\lVert{\bm{\epsilon}}\rVert\geq 6\sqrt{d}]\leq
2\exp(-\tfrac{36d}{2d})\leq 10^{-6}$. We define
${\bm{u}}=\tfrac{{\bm{\epsilon}}}{\lVert{\bm{\epsilon}}\rVert}$, and
${\epsilon}_{j}={\bm{u}}^{T}\bar{{\bm{\epsilon}}}_{j}$, which is a standard
Gaussian random variable. Then, from the concentration inequality,
$\mathbb{P}[\max_{j\in[m]}|{\epsilon}_{j}|\geq\sqrt{32\ln(m)}]\leq\tfrac{2}{m^{9}}\leq
10^{-6}$. Substituting this in 236,

$\displaystyle\max_{j\in[m]}|\gamma\sigma{\bm{\epsilon}}^{T}\sum_{i=1}^{k}{\bm{\epsilon}}_{j}^{(i)}|$
$\displaystyle\leq 6\gamma\sigma\sqrt{kd}\max_{j\in[m]}|{\epsilon}_{j}|,$
(237) $\displaystyle\leq
6\tfrac{1}{100k^{2}d^{2}}\tfrac{1}{100\sqrt{k\ln(kd)^{3}}}\sqrt{kd}\max_{j\in[m]}|{\epsilon}_{j}|,$
(238) $\displaystyle\leq
6\tfrac{1}{100k^{2}d^{2}}\tfrac{1}{100\sqrt{k\ln(kd)^{3}}}\sqrt{kd}\sqrt{32\ln(m)}\leq\tfrac{1}{8},$
(239)

for large enough $k,d$. Using 234, 239 in 233, we bound $\alpha_{j}$, for all
$j\in[m]$, as,

$\displaystyle
1+|\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}|+|\sum_{i=1}^{k}\gamma\sigma{\bm{\epsilon}}^{T}{\bm{\epsilon}}_{j}^{(i)}|$
$\displaystyle\geq\alpha_{j}\geq
1-|\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}|-|\sum_{i=1}^{k}\gamma\sigma{\bm{\epsilon}}^{T}{\bm{\epsilon}}_{j}^{(i)}|.$
(240) $\displaystyle\tfrac{5}{4}$
$\displaystyle\geq\alpha_{j}\geq\tfrac{3}{4}.$ (241)

Also, note that
$\beta_{j}=\sum_{i=1}^{k}y_{j}{\bm{x}}^{(i)}_{j}\overset{d}{=}{\bm{w}}^{\star}+\sigma\sqrt{k}\bar{{\bm{\epsilon}}}_{j}$.
We are now in the position to analyze $\hat{{\bm{w}}}^{1}$,

$\displaystyle\hat{{\bm{w}}}^{1}$
$\displaystyle={\bm{w}}^{0}-\nabla_{{\bm{w}}}l({\bm{w}}^{0},0;S_{1}^{m}),$
(242)
$\displaystyle={\bm{w}}^{0}+\tfrac{1}{m}\sum_{j=1}^{m}2\alpha_{j}\beta_{j},$
(243)
$\displaystyle\overset{d}{=}{\bm{w}}^{0}+\tfrac{1}{m}\sum_{j=1}^{m}2\alpha_{j}\left({\bm{w}}^{\star}+\sigma\sqrt{k}\bar{{\bm{\epsilon}}}_{j}\right),$
(244)
$\displaystyle\overset{d}{=}{\bm{w}}^{0}+\tfrac{2\sum_{j=1}^{m}\alpha_{j}}{m}{\bm{w}}^{\star}+\tfrac{2\sigma\sqrt{k\sum_{j=1}^{m}\alpha_{j}^{2}}}{m}\bar{{\bm{\epsilon}}},$
(245)

where $\bar{{\bm{\epsilon}}}$ is the Gaussian random vector
$\sim{\mathcal{N}}(\mathbf{0},{\mathbf{I}}_{d})$. Note that from the
concentration of the norm of a Gaussian random variable
$\mathbb{P}[\lVert\bar{{\bm{\epsilon}}}\rVert\geq 6\sqrt{d}]\leq
2\exp(-\tfrac{36d}{2d})\leq 10^{-6}$, and
$\mathbb{P}[\lVert\bar{{\bm{\epsilon}}}\rVert\leq\sqrt{d}/6]\leq 10^{-6}$,

Recall that our aim is to bound
$({\bm{w}}^{1})^{T}{\bm{w}}^{\star}=\tfrac{(\hat{{\bm{w}}}^{1})^{T}{\bm{w}}^{\star}}{\lVert\hat{{\bm{w}}}^{1}\rVert}$.
For this, we first upper bound $\lVert\hat{{\bm{w}}}^{1}\rVert$,

$\displaystyle\lVert\hat{{\bm{w}}}^{1}\rVert$
$\displaystyle=\lVert{\bm{w}}^{0}+\tfrac{2\sum_{j=1}^{m}\alpha_{j}}{m}{\bm{w}}^{\star}+\tfrac{2\sigma\sqrt{k\sum_{j=1}^{m}\alpha_{j}^{2}}}{m}\bar{{\bm{\epsilon}}}\rVert,$
(246)
$\displaystyle\leq\lVert{\bm{w}}^{0}\rVert+\lVert\tfrac{2\sum_{j=1}^{m}\alpha_{j}}{m}{\bm{w}}^{\star}\rVert+\lVert\tfrac{2\sigma\sqrt{k\sum_{j=1}^{m}\alpha_{j}^{2}}}{m}\bar{{\bm{\epsilon}}}\rVert,$
(247)
$\displaystyle\overset{\ref{cnn_itr_1_alpha_bound}}{\leq}\lVert{\bm{w}}^{0}\rVert+\tfrac{5}{2}\lVert{\bm{w}}^{\star}\rVert+\tfrac{5\sigma}{2}\sqrt{\tfrac{k}{m}}\lVert\bar{{\bm{\epsilon}}}\rVert,$
(248)
$\displaystyle=\gamma\lVert{\bm{\epsilon}}\rVert+\tfrac{5}{2}+\tfrac{5\sigma}{2}\sqrt{\tfrac{k}{\sigma^{2}(d+k)\ln(kd)}}\lVert\bar{{\bm{\epsilon}}}\rVert,$
(249)
$\displaystyle\leq\tfrac{6\sqrt{d}}{100k^{2}d^{2}}+\tfrac{5}{2}+\tfrac{5\sigma}{2}\sqrt{\tfrac{6kd}{\sigma^{2}(d+k)\ln(kd)}}\leq
10\sqrt{\tfrac{kd}{(k+d)\ln(kd)}},$ (250)

for large enough $k,d$. Similarly, we lower bound
$\lVert\hat{{\bm{w}}}^{1}\rVert$,

$\displaystyle\lVert\hat{{\bm{w}}}^{1}\rVert$
$\displaystyle\geq\lVert\tfrac{2\sigma\sqrt{k\sum_{j=1}^{m}\alpha_{j}^{2}}}{m}\bar{{\bm{\epsilon}}}\rVert-\lVert{\bm{w}}^{0}\rVert-\lVert\tfrac{2\sum_{j=1}^{m}\alpha_{j}}{m}{\bm{w}}^{\star}\rVert,$
(251)
$\displaystyle\overset{\ref{cnn_itr_1_alpha_bound}}{\geq}\tfrac{3\sigma}{2}\sqrt{\tfrac{k}{m}}\lVert\bar{{\bm{\epsilon}}}\rVert-\lVert{\bm{w}}^{0}\rVert-\tfrac{5}{2}\lVert{\bm{w}}^{\star}\rVert,$
(252)
$\displaystyle\geq\tfrac{3\sigma}{2}\sqrt{\tfrac{kd}{6\sigma^{2}(k+d)\ln(kd)}}-\tfrac{6\sqrt{d}}{100k^{2}d^{2}}-\tfrac{5}{2}\geq\tfrac{1}{4}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}},$
(253)

where the last inequality holds for a large enough $k,d$. Next, we lower bound
$(\hat{{\bm{w}}}^{1})^{T}{\bm{w}}^{\star}$,

$\displaystyle(\hat{{\bm{w}}}^{1})^{T}{\bm{w}}^{\star}$
$\displaystyle=({\bm{w}}^{0})^{T}{\bm{w}}^{\star}+\tfrac{2\sum_{j=1}^{m}\alpha_{j}}{m}({\bm{w}}^{\star})^{T}{\bm{w}}^{\star}+\tfrac{2\sigma\sqrt{k\sum_{j=1}^{m}\alpha_{j}^{2}}}{m}(\bar{{\bm{\epsilon}}})^{T}{\bm{w}}^{\star},$
(254)
$\displaystyle=\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}+\tfrac{2\sum_{j=1}^{m}\alpha_{j}}{m}+\tfrac{2\sigma\sqrt{k\sum_{j=1}^{m}\alpha_{j}^{2}}}{m}(\bar{{\bm{\epsilon}}})^{T}{\bm{w}}^{\star},$
(255)
$\displaystyle\geq-|\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}|+\tfrac{3}{2}-\tfrac{5\sigma\sqrt{k}}{\sqrt{m}}|(\bar{{\bm{\epsilon}}})^{T}{\bm{w}}^{\star}|,$
(256)
$\displaystyle\overset{\ref{obs_1}}{\geq}-\tfrac{1}{8}+\tfrac{3}{2}-\tfrac{5\sigma\sqrt{k}}{\sqrt{\sigma^{2}(k+d)\ln(kd)}}|(\bar{{\bm{\epsilon}}})^{T}{\bm{w}}^{\star}|,$
(257)
$\displaystyle\geq\tfrac{11}{8}-\tfrac{1}{12}|({\bm{\epsilon}}^{1})^{T}{\bm{w}}^{\star}|\geq\tfrac{11}{8}-\tfrac{7}{10}\geq\tfrac{6}{10},$
(258)

with probability $\geq 1-2\Phi(-\tfrac{84}{10})\geq 1-10^{-6}$. And similarly
we upper bound $(\hat{{\bm{w}}}^{1})^{T}{\bm{w}}^{\star}$,

$\displaystyle(\hat{{\bm{w}}}^{1})^{T}{\bm{w}}^{\star}$
$\displaystyle\leq\tfrac{5}{2}+|\gamma{\bm{\epsilon}}^{T}{\bm{w}}^{\star}|+\tfrac{5\sigma\sqrt{k}}{\sqrt{m}}|({\bm{\epsilon}}^{1})^{T}{\bm{w}}^{\star}|,$
(259) $\displaystyle\leq\tfrac{5}{2}+\tfrac{1}{8}+\tfrac{7}{10}\leq 4.$ (260)

Therefore,
$40\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}\geq({\bm{w}}^{1})^{T}{\bm{w}}^{\star}\geq\tfrac{6}{100}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}$,
with probability $\geq 1-10^{-5}$. We can now express ${\bm{w}}^{1}$ as
$\lambda{\bm{w}}^{\star}+\sqrt{1-\lambda^{2}}{\bm{w}}^{\star}_{\perp}$, such
that
$40\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}\geq\lambda\geq\tfrac{6}{100}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}$,
$\lVert{\bm{w}}^{\star}_{\perp}\rVert=1$, and
$({\bm{w}}^{\star})^{T}{\bm{w}}^{\star}_{\perp}=0$.

3b. Update Step 2

In this step, we will now show that the
$\tfrac{6}{100}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}$ alignment achieved in the
first step, enables the network to filter out the noise patches, while letting
from the signal patch pass through. This denoising will enables us to achieve
a stronger a $1-10^{-3}$ alignment with the signal vector.

We begin by analyzing the push forward of all noise patches in $S_{2}^{m}$,
through the CNN model,

$\displaystyle\max_{i\in[k],j\in[n]\setminus[m]}|\sigma({\bm{w}}^{1})^{T}{\bm{\epsilon}}_{j}^{(i)}|$
$\displaystyle\leq\tfrac{1}{100\sqrt{k\ln(kd)^{3}}}\max_{i,j}|({\bm{w}}_{i}^{1})^{T}{\bm{\epsilon}}_{j}^{(i)}|,$
(261)
$\displaystyle\leq\tfrac{1}{100\sqrt{k\ln(kd)^{3}}}\sqrt{32\ln(\sigma^{2}k(k+d)\ln(kd))},$
(262)
$\displaystyle\leq\tfrac{1}{4\sqrt{k}}\leq\tfrac{1}{100}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}$
(263)

To derive inequality 262, we have used the concentration of the maximum of the
absolute value of $mk$ i.i.d. Gaussian random variables,
$\mathbb{P}[\max_{i,j}|({\bm{w}}^{1})^{T}{\bm{\epsilon}}_{j}^{(i)}|\geq\sqrt{32\ln(mk)}]\leq\tfrac{2}{(mk)^{9}}\leq
10^{-6}$. Recall from the analysis of the first update step that,

$\displaystyle
40\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}\geq({\bm{w}}^{1})^{T}{\bm{w}}^{\star}\geq\tfrac{6}{100}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}.$
(264)

From 263, 264, and $b_{1}=\tfrac{1}{100}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}$, we
filter out the noise and let the signal pass for all $j$,

$\displaystyle
40\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}\geq\phi_{b_{1}}(y_{j}({\bm{w}}^{1})^{T}{\bm{x}}_{j}^{(i)})$
$\displaystyle\geq\tfrac{4}{100}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}},\>\>\text{where
}r_{ij}=1,$ (265)
$\displaystyle\phi_{b_{1}}(y_{j}({\bm{w}}^{1})^{T}{\bm{x}}_{j}^{(i)})$
$\displaystyle=0,\>\>\text{where }r_{ij}=0.$ (266)

We will follow in the footsteps of update step $1$ and seek to bound
$({\bm{w}}^{2})^{T}{\bm{w}}^{\star}$. First, we define
$\hat{{\bm{w}}}^{2}={\bm{w}}^{1}-\eta_{2}\nabla_{{\bm{w}}}l({\bm{w}}^{1},b_{1};S_{2}^{m})$,
and therefore
$({\bm{w}}^{2})^{T}{\bm{w}}^{\star}=\tfrac{(\hat{{\bm{w}}}^{2})^{T}{\bm{w}}^{\star}}{\lVert\hat{{\bm{w}}}^{2}\rVert}$.
Now, we begin by evaluate the gradient of the empirical loss function with
respect to ${\bm{w}}^{1}$,

$\displaystyle\nabla_{{\bm{w}}^{1}}l({\bm{w}}^{1},b_{1};S_{2}^{m})$
$\displaystyle=\frac{-1}{m}\sum_{j=1}^{m}2\left(y_{j}-\sum_{i=1}^{k}\phi_{b_{1}}(({\bm{w}}^{1})^{T}{\bm{x}}^{(i)}_{j}))\right)\left(\sum_{i=1}^{k}{\bm{x}}^{(i)}_{j}\phi^{\prime}_{b_{1}}(({\bm{w}}^{1})^{T}{\bm{x}}^{(i)}_{j}))\right),$
(267)
$\displaystyle=\frac{-1}{m}\sum_{j=1}^{m}2\left(1-\sum_{i=1}^{k}\phi_{b_{1}}(y_{j}({\bm{w}}^{1})^{T}{\bm{x}}^{(i)}_{j}))\right)\left(\sum_{i=1}^{k}r_{ij}y_{j}{\bm{x}}^{(i)}_{j}\right)$
(268)

where 268 follows from 265, 266. Define $\alpha_{j}\coloneqq
1-\sum_{i=1}^{k}\phi_{b_{1}}(y_{j}({\bm{w}}^{1})^{T}{\bm{x}}^{(i)}_{j}))$, for
$j\in[n]\setminus[m]$. Then, $1\geq
1-\tfrac{4}{100}\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}\geq\alpha_{j}\geq
1-40\sqrt{\tfrac{kd}{(k+d)\ln(kd)}}$. We also define ${\bm{x}}_{j}^{(t)}$ to
be the patch of the $j$-th data sample that corresponds to the occurrence of
the signal, that is $r_{tj}=1$. From 268,

$\displaystyle\nabla_{{\bm{w}}^{1}}l({\bm{w}}^{1},b_{1};S_{2}^{m})$
$\displaystyle=\tfrac{-1}{m}\sum_{j=1}^{m}2\alpha_{j}y_{j}{\bm{x}}^{(t)}_{j}\overset{d}{=}\tfrac{-1}{m}\sum_{j=1}^{m}2\alpha_{j}\left({\bm{w}}^{\star}+\sigma{\bm{\epsilon}}_{j}^{(t)}\right),$
(269)
$\displaystyle=-\sum_{j=1}^{m}\tfrac{2\alpha_{j}}{m}{\bm{w}}^{\star}-\tfrac{1}{m}\sum_{j=1}^{m}2\sigma\alpha_{j}{\bm{\epsilon}}_{j}^{(t)},$
(270)
$\displaystyle\overset{d}{=}-\sum_{j=1}^{m}\tfrac{2\alpha_{j}}{m}{\bm{w}}^{\star}-\tfrac{2\sigma\sqrt{\sum_{j=1}^{m}\alpha_{j}^{2}}}{m}\hat{{\bm{\epsilon}}},$
(271)

where $\hat{{\bm{\epsilon}}}\sim{\mathcal{N}}(\mathbf{0},{\mathbf{I}}_{d})$.
We define $a\coloneqq\sum_{j=1}^{m}\tfrac{2\alpha_{j}}{m}$. And, observe that
from the concentration of the norm of a Gaussian random variable
$\mathbb{P}[\lVert\hat{{\bm{\epsilon}}}\rVert\geq 6\sqrt{d}]\leq
2\exp(-\tfrac{36d}{2d})\leq 10^{-6}$. With these results, we are now ready to
bound
$({\bm{w}}^{2})^{T}{\bm{w}}^{\star}=\tfrac{(\hat{{\bm{w}}}^{2})^{T}{\bm{w}}^{\star}}{\lVert\hat{{\bm{w}}}^{2}\rVert}$,

$\displaystyle\lVert\hat{{\bm{w}}}^{2}\rVert$
$\displaystyle=\lVert{\bm{w}}^{1}+\eta_{2}\sum_{j=1}^{m}\tfrac{2\alpha_{j}}{m}{\bm{w}}^{\star}+\eta_{2}\tfrac{2\sigma\sqrt{\sum_{j=1}^{m}\alpha_{j}^{2}}}{m}\hat{{\bm{\epsilon}}}\rVert,$
$\displaystyle\leq
1+a\eta_{2}\lVert{\bm{w}}^{\star}\rVert+\tfrac{2\sigma\eta_{2}}{\sqrt{m}}\lVert\hat{{\bm{\epsilon}}}\rVert,$
$\displaystyle\leq
1+a\eta_{2}+\tfrac{12\sigma\eta_{2}\sqrt{d}}{\sqrt{\sigma^{2}(k+d)\ln(kd)}}\leq
1+\eta_{2}(a+10^{-3}),$

for a large enough $k,d$. And now we lower bound
$(\hat{{\bm{w}}}^{2})^{T}{\bm{w}}^{\star}$,

$\displaystyle(\hat{{\bm{w}}}^{2})^{T}{\bm{w}}^{\star}$
$\displaystyle=({\bm{w}}^{1})^{T}{\bm{w}}^{\star}+\eta_{2}\sum_{j=1}^{m}\tfrac{2\alpha_{j}}{m}({\bm{w}}^{\star})^{T}{\bm{w}}^{\star}+\eta_{2}\tfrac{2\sigma\sqrt{\sum_{j=1}^{m}(\alpha_{j}^{2})}}{m}\hat{{\bm{\epsilon}}}^{T}{\bm{w}}^{\star}$
(272)
$\displaystyle\overset{d}{=}-({\bm{w}}^{1})^{T}{\bm{w}}^{\star}+\eta_{2}\tfrac{\sum_{j=1}^{m}2\alpha_{j}}{m}+\eta_{2}\tfrac{2\sigma\sqrt{\sum_{j=1}^{m}(\alpha_{j}^{2})}}{m}\epsilon;\>\>\epsilon\in{\mathcal{N}}(0,1),$
(273)
$\displaystyle\geq-1+\eta_{2}a-\tfrac{2\eta_{2}\sigma\epsilon}{\sqrt{m}}$
(274)
$\displaystyle\geq-1+\eta_{2}a-\eta_{2}\tfrac{2\sigma\epsilon}{\sqrt{\sigma^{2}(k+d)\ln(kd)}}\geq-1+\eta_{2}(a-10^{-3}),$
(275)

where we have used the fact that
${\mathbb{P}}[|\tfrac{2\epsilon}{\sqrt{(k+d)\ln(kd)}}|\geq 10^{-3}]$ holds
with probability $\leq 10^{-6}$, for a large enough $k,d$. Therefore the
alignment can be lower bounded as,

$\displaystyle\tfrac{(\hat{{\bm{w}}}^{2})^{T}{\bm{w}}^{\star}}{\lVert\hat{{\bm{w}}}^{2}\rVert}\geq\tfrac{1+10^{3}(a+10^{-3})}{1+10^{3}(a+10^{-3})}\geq
0.96,$ (276)

as $1\geq a\geq\tfrac{2}{3}$ for large $k,d$, and this occurs with a
probability $\geq 1-2\times 10^{-5}$.

3c. CNN has Low Risk

We now show that this large constant alignment guarantees a low risk. We bound
the push forward of the noise through the CNN,

$\displaystyle|\sigma\max_{j\in[m]}(({\bm{w}}^{2})^{T}{\bm{\epsilon}}_{i})|\leq\tfrac{6\sqrt{\ln(k)}}{100\sqrt{k\ln(kd)^{3}}}\leq
10^{-4}$ (277)

To derive the last inequality, we have used the concentration of the maximum
of the absolute value of $k$ i.i.d. Gaussian random variables,
$\mathbb{P}[\max_{j\in[k]}|({\bm{w}}^{2})^{T}{\bm{\epsilon}}_{j}|\geq\sqrt{32\ln(k)}]\leq\tfrac{2}{m^{9}}\leq
10^{-6}$. For this data sample, let $t\in[k]$ be the index of the signal
patch, then,

$\displaystyle\phi_{b_{2}}(y_{j}({\bm{w}}_{i}^{2})^{T}{\bm{x}}_{j}^{(t)})$
$\displaystyle\geq 0.959,$ (278)
$\displaystyle\phi_{b_{2}}(y_{j}({\bm{w}}_{i}^{2})^{T}{\bm{x}}_{j}^{(i)})$
$\displaystyle=0,\>\>\forall\>i\neq t.$ (279)

To bound the risk in the failure case, we note that for any
${\bm{v}}\in{\mathcal{W}}$,

$\displaystyle\operatorname*{\mathbb{E}}[(y-\sum_{i=1}^{k}\phi_{b}({\bm{w}}^{T}{\bm{x}}^{(i)}))^{2}]$
$\displaystyle=\operatorname*{\mathbb{E}}[(1-\sum_{i=1}^{k}\phi_{b}(y{\bm{w}}^{T}{\bm{x}}^{(i)}))^{2}],$
(280)
$\displaystyle=\tfrac{1}{k}\sum_{j=1}^{k}\operatorname*{\mathbb{E}}_{({\bm{x}},y)\sim\text{SSD}_{j}}[(1-\sum_{i=1}^{k}\phi_{b}(y{\bm{w}}^{T}{\bm{x}}^{(i)}))^{2}],$
(281)
$\displaystyle=\tfrac{1}{k}\sum_{j=1}^{k}\operatorname*{\mathbb{E}}[(1-\sum_{i\neq
j}\phi_{b}(\sigma{\epsilon}_{ij})-\phi_{b}(\cos(\alpha_{j})+\sigma{\epsilon}_{jj}))^{2}],$
(282)

To evaluate the above expression, we observe that the expectation can be
written as,

$\operatorname*{\mathbb{E}}[(1-\sum_{i\neq
j}\phi_{b}(\sigma{\epsilon}_{ij})-\phi_{b}(\cos(\alpha_{j})+\sigma{\epsilon}_{jj}))^{2}]=\text{Var}[(1-\sum_{i\neq
j}\phi_{b}(\sigma{\epsilon}_{ij})-\phi_{b}(\cos(\alpha_{j})+\sigma{\epsilon}_{jj}))]\\\
+\operatorname*{\mathbb{E}}[(1-\sum_{i\neq
j}\phi_{b}(\sigma{\epsilon}_{ij})-\phi_{b}(\cos(\alpha_{j})+\sigma{\epsilon}_{jj}))]^{2},$
(283) $\displaystyle=\sum_{i\neq
j}\text{Var}[\phi_{b}(\sigma{\epsilon}_{ij})]+\text{Var}[\phi_{b}(\cos(\alpha_{j})+\sigma{\epsilon}_{jj})]+\left(\operatorname*{\mathbb{E}}[\phi_{b}(\cos(\alpha_{j})+\sigma{\epsilon}_{jj})]\right)^{2},$
(284) $\displaystyle\leq\sum_{i}\sigma^{2}+\cos^{2}(\alpha_{j})\leq
k\sigma^{2}+1\leq 2.$ (285)

Substituting this back,

$\displaystyle\operatorname*{\mathbb{E}}[(y-\sum_{i=1}^{k}\phi_{b}({\bm{w}}_{i}^{T}{\bm{x}}^{(i)}))^{2}]\leq\tfrac{1}{k}\sum_{j=1}^{k}2=2$
(286)

Finally, the risk of the classifier is,

$\displaystyle\operatorname*{\mathbb{E}}\left[R\left(\bar{\theta}_{n},P\right)\right]\leq(1-0.959)^{2}+4\times
10^{-5}\leq\delta.$ (287)

∎

##  Appendix E Experiments

In this section, we validate our theoretical bounds with empirical results. We
begin by presenting the test-error experiments, where we evaluate the test
error of the three models across various training sample sizes. The results
for these experiments show an order-of-magnitude decrease in the sample
efficiency when comparing CNNs to LCNs, and comparing LCNs to FCNs.

We then present our sample complexity experiments, wherein we explicitly
calculate the sample complexity of CNNs and LCNs for various $(k,d)$ pairs.
However, these experiments are significantly more compute-intensive than the
test error experiments. While the computational demands are manageable for
CNNs, they increase significantly for LCNs and become prohibitively large for
FCNs. This is primarily because FCNs require at least $10\text{-}20$ times
more samples than LCNs. Nonetheless, for both CNNs and LCNs, we successfully
verify that the empirical sample complexity satisfies the respective
theoretical bounds. Specifically, for CNNs, we show a $O(k)$ sample complexity
growth with a fixed $d$ and a $O(d)$ growth with a fixed $k$. For LCNs, we
establish that the sample complexity grows as $O(k^{2}),\Omega(k)$ with a
fixed $d$ and as $\Theta(d)$ with a fixed $k$.

###  E.1 Test Error Experiments

In this experiment, we evaluate the test error of each of the three models
when trained with a sample size of $\\{10,50,100,250,500\\}$ for every $(k,d)$
pair with $k,d\in\\{10,20\\}$. For each training session, we conduct a grid
search over the learning rates for patch parameters being
$\\{10^{-1},10^{-2},10^{-3}\\}$, and for the biases being
$\\{10^{-2},10^{-3},10^{-4}\\}$. We choose the model with the lowest test
error. The experiment is replicated $5$ times, and we report the mean and
standard deviation of the test errors.

Figure 1: Test error incurred by CNNs, LCNs and FCNs for various values of
$(k,d)$

Across all $(k,d)$ pairs we observe that LCNs require an order-of-magnitude
($10\text{-}20$ times) more samples than CNNs to achieve comparable test
errors. This demonstrates the larger sample efficiency of CNNs over LCNs.
Extrapolating the trend line for FCNs, it is evident that they would need even
orders-of-magnitude more samples than LCNs for comparable error levels. These
observations are consistent with our theoretical predictions of sample
complexities: $\Omega(k^{2}d)$ for FCNs, $O(k(k+d))$ and $\Omega(kd)$ for
LCNs, and $O(k+d)$ for CNNs.

###  E.2 Sample Complexity Experiments

In our first experiment, we fix the patch dimension $d$ at 20 and vary the
number of patches $k$ across the range $\\{10,15,20,25,30\\}$. For each
$(k,d)$ pair, we plot the sample complexity for both CNNs and LCNs. We
evaluate the sample complexity via the following steps:

  1. 1.

Target Loss Evaluation: We compute the optimal loss based on the ground truth
and add a fixed tolerance of $0.03$ to establish the target loss.

  2. 2.

Determining Sample Range: Through trial and error, we determine that a maximum
of $1000$ samples is sufficient for any model across all $k$ values.

  3. 3.

Binary Search Method: To find the minimum number of samples required to reach
the target loss, we perform a binary search. In each step, we conduct a grid
search over the learning rates for weights being $[10^{-1},10^{-2},10^{-3}]$
and biases being $[10^{-2},10^{-3},10^{-4}]$, and select the model with the
lowest test error.

  4. 4.

Repetitions for Reliability: We repeat the steps (1-3) five times, plotting
the mean and standard deviation of the sample complexities.

Figure 2: Sample complexity for CNNs (left) and LCNs (right) across various
values of $k$

For a fixed $d$, the sample complexity for CNNs exhibits an $O(k)$ growth as
(Figure 3, left), which is consistent with our CNN upper bound. Similarly, for
LCNs, the complexity growth is consistent with our theoretical results of
$O(k^{2})$ and $\Omega(k)$ (Figure 3, right). Additionally, note that LCNs
require about $10$ to $20$ times more samples than CNNs, which corresponds to
the multiplicative $d$ factor in LCNs’ sample complexity bound.

In our second experiment, we set the number of patches $k$ at 20 and vary the
patch dimension $d$ across the range $[10,15,20,25,30]$. The same steps (1-4)
are repeated for this setup.

Figure 3: Sample complexity for CNNs (left) and LCNs (right) across various
values of $d$

For a fixed $k$, we observe that the CNN sample complexity grows as $O(d)$
(Figure 4, left), and the LCN sample complexity grows as $\Theta(d)$ (Figure
4, right), both in line with our theoretical guarantees. Furthermore, akin to
our findings in the first experiment, LCNs require approximately $20$ times
more samples than CNNs, owing to the multiplicative $k$ factor in their sample
complexity.


# Can Audio Captions Be Evaluated with Image Caption Metrics?

###### Abstract

Automated audio captioning aims at generating textual descriptions for an
audio clip. To evaluate the quality of generated audio captions, previous
works directly adopt image captioning metrics like SPICE and CIDEr, without
justifying their suitability in this new domain, which may mislead the
development of advanced models. This problem is still unstudied due to the
lack of human judgment datasets on caption quality. Therefore, we firstly
construct two evaluation benchmarks, AudioCaps-Eval and Clotho-Eval. They are
established with pairwise comparison instead of absolute rating to achieve
better inter-annotator agreement. Current metrics are found in poor
correlation with human annotations on these datasets. To overcome their
limitations, we propose a metric named FENSE, where we combine the strength of
Sentence-BERT in capturing similarity, and a novel Error Detector to penalize
erroneous sentences for robustness. On the newly established benchmarks, FENSE
outperforms current metrics by 14-25% accuracy. 111Code, data, and web demo
available at: https://github.com/blmoistawinde/fense

Index Terms—  Audio captioning, image captioning, caption evaluation, pre-
trained model

##  1 Introduction

Automated audio captioning [1] is the task of automatically generating human-
like content description of an audio signal using free text. Recent progress
has been focused on the development of caption datasets [2, 3, 4], in which
novel algorithms [5, 6, 7] are cultivated and fostered rapidly. However,
little attention has been addressed on the automatic evaluation metrics.
Current evaluations for audio caption directly adopt the metrics from the
image captioning literature, including those for general Natural Language
Generation (NLG) (e.g. BLEU [8], ROUGE [9], METEOR [10]) or specifically for
image captioning (e.g. CIDEr [11], SPICE [12]), without considering their
generalizability to audio domain.

In this work, we question: “Can audio captions be evaluated with image caption
metrics?”, since a biased evaluation may hinder the improvement of algorithms
or even lead the journey to a skewed direction. In Fig 1, we show that current
metrics cannot properly evaluate audio captioning. On one hand, traditional
metrics like BLEU may fail to capture semantic similarity beyond exact word
matching [13, 14]. Here, Caption A roughly paraphrases reference with all the
sound events aligned, while Caption B partially aligned to reference with a
misprediction. However, all the N-gram overlap based metrics give much higher
scores to Caption B since it has more words in common with reference.

Fig. 1: Column A, B and C shows the corresponding scores of Caption A, B and C
given by different metrics. One cell is colored if the caption is favoured by
a certain metric of this row.

On the other hand, the specificity in vision-focused captions may cause the
failure of image caption specific metrics. In image captioning, attention has
been drawn to the visible attributes of objects, along with their spatial
relationships (e.g. A women in blue blouse sits at a table, with crinkled
paper in her hand). Conversely in audio captioning, importance has been
attached to auditory properties of events as well as their temporal
connections (e.g. Young women speaking with crinkling noise). By this means,
scene graph based metrics (e.g. SPICE [12]) are unlikely applicable to audio
caption evaluation, in that object attributes and relations are seldom
mentioned. It could be seen that SPICE even leaves a zero score on Caption A
for its scene graph disjointness with reference, despite their semantic
affinity.

Moreover, fluency issues like incomplete or inconsistent sentences are quite
common in current generated captions. However, current metrics do not
penalize, and sometimes even favour captions with these errors, so they can be
easily gamed by systems exploiting the weakness. As shown in Fig 1, Caption C
attaches three meaningless words to Caption B, which further increases its
N-gram overlap with reference. Scores indicate that all N-gram overlap based
metrics are cheated by this trick, while the others are indifferent, which is
also incompetence.

Human evaluation is considered the golden standard in NLG tasks. However, by
far there is no benchmark human judgments available for audio captioning. It
has certainly caused difficulty in conducting fair comparisons on evaluation
metrics. Therefore, we annotated the first two human evaluation benchmarks for
audio captioning, based on the widely accepted AudioCaps [4] and Clotho [2]
dataset. We experimented with two annotation protocols adopted from image
captioning [11]: absolute rating and pairwise comparison. We find that
absolute rating leads to poor inter-annotator agreement, and thus establish
our final annotation based on pairwise comparison, resulting in the annotation
of 3,421 pairs. We then benchmark current metrics, and find that metrics like
BLEU1 and SPICE perform no better than random guess on deciding a better
generated caption in a pair.

To perform better audio caption evaluation, we explore the use of pre-trained
model based metrics, including BERTScore [15] and BLEURT [16], and witness
significant advantage over current methods. We also repurpose Sentence-BERT
[17], which produces sentence embedding for similarity calculation and is
mainly utilized for information retrieval, to perform caption evaluation (Fig
1, Last Row), and it surprisingly achieved the best performance. However, even
methods with enhanced capability for capturing semantic relatedness can still
fail to penalize fluency issues properly. We thus further propose Error
Detector to recognize erroneous sentences and penalize them accordingly. We
refer to the combined metric of Sentence-BERT and fluency penalty as Fluency
ENhanced Sentence-bert Evaluation (FENSE), which significantly outperforms
existing metrics.

In summary, our contributions are:

  1. 1.

We establish the first two benchmark datasets, AudioCaps-Eval and Clotho-Eval,
for the comparison of audio caption evaluation metrics.

  2. 2.

We propose FENSE, a metric consists of Sentence-BERT for similarity
calculation and Error Detector to penalize fluency issues for robustness.

  3. 3.

Results on the new benchmarks show that FENSE can outperform previous metrics
in pairwise comparison accuracy by 14-25 points, and ablations suggest a
significant contribution of both Sentence-BERT and Error Detector.

##  2 Benchmark Dataset Construction

###  2.1 Audio Captioning Systems

To generate candidate captions for evaluation, we involve multifaceted audio
captioning systems: 1) Nearest neighbor (NN) retrieval system. For a test
audio, we retrieve its most similar training audio and take its annotation as
a prediction. The similarity between two audio clips are measured by the
cosine similarity of their embeddings, extracted by a pre-trained CNN [18]. 2)
Fully Connected (FC) input system. An architecture similar to [3], where the
input audio is first transformed to a vector and then decoded into a caption.
3) Attention (ATT) input system. The same architecture as [5], where the input
audio is first transformed into an embedding sequence and then decoded into a
caption using temporal attention mechanism. 4) Reinforcement Learning (RL)
system. The same architecture as ATT system while the model is further fine-
tuned using reinforcement learning [5], achieving the second place in the
recent DCASE challenge evaluated by CIDEr and SPICE.

FC, ATT and RL systems are all sequence-to-sequence encoder-decoder
frameworks. They all use a 10-layer CNN as the encoder and a single-layer GRU
as the decoder. The detail structure can be found in [19]. To increase the
diversity of generated captions, for all systems except NN, we employ various
decoding strategies, including greedy decoding, beam search, diverse beam
search [20]. In beam search, different temperatures are utilized.

###  2.2 Data Annotation

Based on captions generated by the aforementioned systems, we build the audio
captioning evaluation dataset by collecting human judgments on captions. We
build our datasets based on two benchmark audio caption datasets: AudioCaps
[4] and Clotho [2]. There are two protocols to collect human judgments in
image captioning: absolute rating and pairwise comparison. We first make a
preliminary exploration on absolute rating protocol. Given an audio clip and a
caption, raters are asked to score the caption from 1 to 4 considering both
its relevance to the audio and its fluency. We randomly sample 100 audio-
caption pairs. Each audio-caption pair is rated by four different human
raters. However, Fleiss Kappa score [21] for different raters is only 0.18 on
Clotho and 0.23 on AudioCaps, indicating poor inter-annotator agreement.
Annotators also report difficulty in rating the caption.

Therefore, the second protocol, pairwise comparison, is adopted. Given an
audio clip and a pair of candidate captions, four raters are asked to choose
which candidate describes the audio better in terms of description accuracy
and fluency. Raters are allowed to choose “I’m not sure” if they cannot
distinguish which candidate is better. Following [11], we generate four pair
groups, namely human-human correct (HC), human-human incorrect (HI), human-
machine (HM) and machine-machine (MM). HC contains two human annotations
describing the same audio. HI also contains two human annotations but one
describes another randomly-picked audio. HM is formed by a human annotation
and a machine generated caption for the same audio. MM is composed of two
machine generated captions describing the same audio. On both Clotho and
AudioCaps, we randomly pick 250 audio clips and generate the four kinds of
pairs. For each audio clip, we form one HC pair, one HI pair, one HM pair and
several MM pairs since the evaluation metrics are usually applied to compare
captions generated by different machine systems. The number of MM pairs for
each audio clip range from one to four.

To avoid indistinguishable cases between similar pairs, we adopt a filtering
strategy for pair generation. We first generate all candidate pairs and
calculate the similarity of each pair using Sentence-BERT embedding. Then we
exclude candidate pairs with a similarity higher than 0.9. We randomly sample
pairs from the remaining captions to obtain the final generated pairs for
comparison. For HC and HM, we randomly sample the pairs. For MM, we randomly
sample four pairs if there are more than four candidate pairs, otherwise we
use all the pairs left. In case of no pairs left after filtering, we select
the pair with the lowest similarity. In this way, we finally obtain human
judgments on 1,750 pairs on Clotho and 1,671 pairs on AudioCaps. Higher inter-
annotator agreement is achieved on both datasets, indicated by a Fleiss Kappa
score of 0.48 and 0.33 respectively. We will refer to them as AudioCaps-Eval
and Clotho-Eval. To our best knowledge, this is the first dataset of human
judgments on the quality of audio captions. We evaluate the effectiveness of
different metrics using this dataset.

##  3 Evaluation Metrics

In this section we briefly introduce the automatic evaluation metrics
investigated in this work. Traditional NLG Metrics and Image Caption Metrics
are the current adopted ones for audio caption. Pre-trained Model Based
Metrics are the existent metrics utilized in other domains and proposed to use
for audio caption. Error Detector is the newly customized metric for
evaluating the vastly present fluency issues in generated captions.

Traditional NLG Metrics Traditional NLG metrics mainly rely on N-gram
matching. BLEU [8] counts the exact N-gram matches between a candidate and its
corresponding reference sentences and calculate the precision, while ROUGE [9]
is the recall-based counterpart of BLEU. A clear limitation for these methods
is that even a subtle difference in the wording for expressing a similar
meaning will be counted as an error. METEOR [10] is proposed to alleviate the
problem by supporting word stems, synonyms and simple paraphrases. However,
similar words beyond such changes are still unhandled, and none of them are
capable of capturing similarity based on contextualized semantics.

Image Caption Metrics For the evaluation of Image captioning models, many
methods have been proposed to further leverage the specific characteristics of
image captions. Since image captions can be diverse even for the same picture,
CIDEr [11] tries to capture the consensus among multiple annotators by rating
a candidate by the mean TF-IDF similarity across reference captions. Moreover,
since image captions usually describe the objects, attributes and relations
depicted in the image, SPICE [12] proposes to utilize the scene graph
representation parsed from caption to capture such key concepts, and rate a
candidate caption by the F1-score over scene graph tuples between a candidate
and its references.

These metrics have shown high correlation with human judgments for image
captioning. However, some specific characteristics of image captions may not
apply to audio captioning. For instance, the difficulty in identifying complex
relations and attributes for an audio may pose challenges for the parse of
scene graphs. They also suffer from the limitations of traditional metrics.

Pre-trained Model Based Metrics Recently, pre-trained language models like
BERT [22] have been utilized for enhancing the evaluation of NLG. Their
ability to produce contextualized word representations can overcome the
limitation of N-gram matching, and the large pre-training corpus may further
facilitate their domain generalizability, which inspired us to investigate
their performance for the evaluation of audio captioning. BERTScore [15]
leverages the contextualized word embeddings from the original BERT to
calculate similarity on word-level, and aggregates them into sentence
similarity with IDF weighting scheme. BLEURT [16] follows the original BERT to
pair the sentences as input and uses a linear layer on top of the [CLS]
embedding to predict the score. They further finetune the BERT backbone
specifically for evaluation.

We also explore a novel use of Sentence-BERT [17]. It is a modification of
BERT that uses siamese network structure to learn sentence embeddings so that
their cosine similarity can reflect the semantic similarity. Although it was
originally proposed for similarity search or clustering, we hypothesize that
its capability of measuring semantic similarity may also benefit the
evaluation of audio captioning. Therefore, we rate a candidate caption by its
average cosine similarity with references according to Sentence-BERT
embeddings.

Error Detector Fluency issues like repeated events and incomplete sentences
are prevalent in current audio captioning systems. However, few of the current
evaluation metrics are able to take them into consideration, resulting in
their overestimation of system quality. To mitigate this problem, we propose
to use a separate error detector to penalize the scores given by other
evaluation metrics when fluency issues are detected. We investigated the
outputs of the captioning systems (§2.1), and found several typical types of
fluency issues. We summarize them and give examples in Table 1.

Type | Example
---|---
Incomplete Sentence |  a woman is giving a speech and a (…)
Repeated Event |  music plays followed by music playing
Repeated Adverb |  sheep bleats nearby several times nearby
Missing Conjunction |  people speaking (and) a train horn blows
Missing Verb |  food sizzles and a pan (verb)
Table 1: Types and examples of fluency issues. We use parentheses to mark the
missing information.

To train a model for detecting such errors, we produce a synthetic training
set by using rules to corrupt the correct captions into erroneous ones with
such issues. Specifically, we use the captions in Clotho and AudioCaps
training set as correct captions. We then tailor modifications for each error
type to apply on the correct captions and label the modified ones as having
the specific error type. For example, to produce incomplete captions, we
append phrases that frequently appears at the tail of observed problematic
examples like “and” , “and a”, “follow by”, etc. We empirically produce one
error per caption 90% of the time, and 2 errors otherwise. Then we mix the
correct captions and corrupted captions into one set, and add an overall Error
label to samples with at least one error. Finally, we train a BERT model on
this set for a multi-label classification of each error type and an overall
Error label.

To include the trained model for penalization, we take the model’s predicted
probability for Error. If it exceeds a predefined threshold (0.9 in this
work), we will divide the original score by 10. We observe improvement when
combining the penalty with any metric, and obtain the best performance with
Sentence-BERT (§4.3). We thus propose FENSE as the combination of them.

##  4 Experiments

Metrics | AudioCaps-Eval | Clotho-Eval
---|---|---
| HC | HI | HM | MM | Total | HC | HI | HM | MM | Total
$\text{BLEU}_{\text{1}}$ | 58.6 | 90.3 | 77.4 | 50.3 | 62.4 | 51.0 | 90.6 | 65.5 | 50.3 | 59.0
$\text{BLEU}_{\text{4}}$ | 54.7 | 85.8 | 78.7 | 50.6 | 61.6 | 52.9 | 88.9 | 65.1 | 53.2 | 60.5
METEOR | 66.0 | 96.4 | 90.0 | 60.1 | 71.7 | 54.8 | 93.0 | 74.6 | 57.8 | 65.4
$\text{ROUGE}_{\text{L}}$ | 61.1 | 91.5 | 82.8 | 52.1 | 64.9 | 56.2 | 90.6 | 69.4 | 50.7 | 60.5
CIDEr | 56.2 | 96.0 | 90.4 | 61.2 | 71.0 | 51.4 | 91.8 | 70.3 | 56.0 | 63.2
SPICE | 50.2 | 83.8 | 77.8 | 49.1 | 59.7 | 44.3 | 84.4 | 65.5 | 48.9 | 56.3
BERTScore | 60.6 | 97.6 | 92.9 | 65.0 | 74.3 | 57.1 | 95.5 | 70.3 | 61.3 | 67.5
BLEURT | 77.3 | 93.9 | 88.7 | 72.4 | 79.3 | 59.0 | 93.9 | 75.4 | 67.4 | 71.6
Sentence-BERT | 64.0 | 99.2 | 92.5 | 73.6 | 79.6 | 60.0 | 95.5 | 75.9 | 66.9 | 71.8
FENSE | 64.5 | 98.4 | 91.6 | 84.6 | 85.3 | 60.5 | 94.7 | 80.2 | 72.8 | 75.7
Table 2: Benchmarking metrics for audio caption evaluation. Results are the correlation with human on pairwise comparisons. | AudioCaps-Eval | Clotho-Eval
---|---|---
| w/o | w | gain | w/o | w | gain
$\text{Bleu}_{\text{1}}$ | 62.4 | 75.3 | 12.9 | 59 | 68.2 | 9.2
SPICE | 59.7 | 62.8 | 3.1 | 56.3 | 62.1 | 5.8
Sentence-BERT | 79.6 | 85.3 | 5.7 | 71.8 | 75.7 | 3.9
Table 3: Ablation results of Error Detector in total accuracy.

###  4.1 Experimental Setup

We conducted experiments on the two established datasets to compare different
metrics’ effectiveness on deciding a better caption out of two candidate
sentences. For each pair of candidates, we compute all the metrics for two
sentences and consider the one with a higher score as better according to the
metric. A decision is considered correct if it agrees with human judgment. We
calculate per-category accuracy by dividing correct predictions with total
predictions within the categories (HC, HI, HM and MM), and merge them as a
total score with micro average. Note that we exclude samples with equal number
of opposite human judgments (excluding “not sure”) so that the chosen samples
can be considered distinguishable.

Since we may also include reference sentences in comparison, we only choose 4
out of 5 sentences from original references in the calculation of metrics. For
an HC pair, we exclude each used reference itself from the five references.
For an HI pair or HM pair, we eliminate the first human correct sentence from
original references as their common new references. For an MM pair, we form
the $C_{5}^{4}$ combinations selecting 4 out of 5 references as their common
new references and calculate metrics on each of the 5 derivatives, then the
five scores are averaged counting for the final score.

To enable a fair comparison across the pre-trained model based metrics, we
choose models of roughly equal size (usually small) and pre-trained on
paraphrase tasks (if possible), which are BERTScore (t5-paraphraser), BLEURT
(BLEURT-tiny) and Sentence-BERT (paraphrase-TinyBERT-L6-v2). Note here
BERTScore (t5-paraphraser) is much larger than the other two models. BLEU1,
BLEU4, ROUGEL, METEOR, CIDEr and SPICE are implemented with tools provided by
DCASE challenge. 222https://github.com/audio-captioning/caption-evaluation-
tools

###  4.2 Standalone Evaluation of Error Detector

To evaluate the performance of the proposed Error Detector, we randomly
sampled 723 machine generated captions, and annotated if the caption has a
fluency issue. We then compare the model’s prediction on the overall Error
class (threshold=0.9) with our annotations. The model achieved a precision of
96.8, recall of 76.4, and F1 of 85.4.

###  4.3 Results on AudioCaps-Eval and Clotho-Eval

Table 2 shows our experimental results on AudioCaps-Eval and Clotho-Eval
across different metrics. The results are consistent on two datasets for a
common explanation. Intuitively, HC and MM pairs pose bigger challenges for
all metrics, as they are either equally good or equally bad on describing the
corresponding audio clip. Nonetheless, pre-trained model based metrics
generally perform much better than other metrics, especially our proposed
FENSE which achieves the best overall accuracy on both datasets. BERTScore
falls 4-5 percent behind other pre-trained model based metrics despite its
biggest model size. On AudioCaps-Eval, N-gram exact match metrics (BLEU,
ROUGE) perform 14-18 points worse than Sentence-BERT, while BLEU1 and BLEU4
struggle to exceed a random guess accuracy on MM pairs, showing their shortage
differentiating two machine generated audio captions. METEOR and CIDEr attain
a moderate performance gain beyond N-gram exact match metrics, however, they
are still far behind Sentence-BERT. Not surprisingly, SPICE performs the
worst, even unable to obtain 50% accuracy on AudioCaps MM and Clotho-Eval HC &
MM, which strongly confirms our hypothesis that image captioning specified
metrics cannot be adopted in audio caption evaluation.

Table 3 shows the overall accuracy of three representative metrics with and
without sentence penalty of our proposed Error Detector (The last row: FENSE).
With Error Detector, all the three metrics achieve extra performance gain,
even for Sentence-BERT. This suggests that metrics leveraging either N-gram
matching or contextual semantic similarity will fail in detecting fluency
issues, and Error Detector can help mitigate such issues, thus setting a new
SOTA.

Fig. 2: Illustration of judgments made by humans, FENSE and SPICE on Clotho-
Eval. y-axis shows the win fractions of 4 audio captioning systems.

Integrating Error Detector into Sentence-BERT metric, we get our proposed
metric FENSE. Since table 2 and 3 have shown that FENSE significantly
outperforms all the above metrics on the two evaluation datasets, we can use
it to evaluate existing audio captioning system mentioned in §2.1. Fig 2
illustrates the judgments over four audio captioning systems made by humans,
FENSE and SPICE on Clotho-Eval. Here we choose ATT, FC and RL whose beam
search temperature equals to 0.5. On the y-axis we show the fraction of times
one system wins another (rated better than another systems under this metric).
We can see that NN is voted as the best system by both humans and FENSE, while
it’s the worst under SPICE. Humans and FENSE ranked ATT, FC and RL accordingly
after NN. However, SPICE fails to reach their consensus again. This indicates
the superiority of FENSE, and further confirms our claim that image captioning
specified metrics like SPICE are inappropriate to be transferred into audio
caption evaluation.

##  5 Conclusion

In this work, we establish the first two human judgment datasets for audio
caption evaluation, AudioCaps-Eval and Clotho-Eval, with pairwise comparison
annotations. We benchmark commonly used metrics adopted from image captioning
literature on the two datasets, and find their performance unsatisfying. We
thus leverage Sentence-BERT for better estimation of semantic similarity and
propose Error Detector to penalize sentences with fluency issues. The metric
combining them two, named as FENSE, exhibits significant advantage.

Our findings suggest that the currently popular metrics for the research and
competitions of audio captioning may not be a reliable measure of system
quality, and better constitutes may be preferred. Although FENSE has achieved
relatively good performance, we think that there is still sufficient room for
improvement. Since semantic similarity does not equal to acoustic relevance
[23], and only the former is covered in FENSE, better utilization of modality-
specific knowledge may facilitate better evaluation as has been witnessed in
image captioning [24].

## References

  * [1] K. Drossos, S. Adavanne, and T. Virtanen, “Automated audio captioning with recurrent neural networks,” in _2017 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA)_. IEEE, 2017, pp. 374–378.

  * [2] K. Drossos, S. Lipping, and T. Virtanen, “Clotho: An audio captioning dataset,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 736–740.
  * [3] M. Wu, H. Dinkel, and K. Yu, “Audio caption: Listen and tell,” in _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2019, pp. 830–834.
  * [4] C. D. Kim, B. Kim, H. Lee, and G. Kim, “Audiocaps: Generating captions for audios in the wild,” in _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , 2019, pp. 119–132.
  * [5] X. Xu, Z. Xie, M. Wu, and K. Yu, “The sjtu system for dcase2021 challenge task 6: Audio captioning based on encoder pre-training and reinforcement learning,” DCASE2021 Challenge, Tech. Rep, Tech. Rep., 2021.
  * [6] X. Mei, Q. Huang, X. Liu, G. Chen, J. Wu, Y. Wu, J. Zhao, S. Li, T. Ko, H. L. Tang _et al._ , “An encoder-decoder based audio captioning system with transfer and reinforcement learning for dcase challenge 2021 task 6,” DCASE2021 Challenge, Tech. Rep, Tech. Rep., 2021.
  * [7] X. Xu, H. Dinkel, M. Wu, and K. Yu, “A crnn-gru based reinforcement learning approach to audio captioning,” in _Proceedings of the Detection and Classification of Acoustic Scenes and Events Workshop (DCASE)_ , 2020, pp. 225–229.
  * [8] K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu, “Bleu: a method for automatic evaluation of machine translation,” in _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , 2002, pp. 311–318.
  * [9] C.-Y. Lin, “Rouge: A package for automatic evaluation of summaries,” in _Text summarization branches out_ , 2004, pp. 74–81.
  * [10] S. Banerjee and A. Lavie, “Meteor: An automatic metric for mt evaluation with improved correlation with human judgments,” in _Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization_ , 2005, pp. 65–72.
  * [11] R. Vedantam, C. Lawrence Zitnick, and D. Parikh, “Cider: Consensus-based image description evaluation,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 4566–4575.
  * [12] P. Anderson, B. Fernando, M. Johnson, and S. Gould, “Spice: Semantic propositional image caption evaluation,” in _European conference on computer vision_. Springer, 2016, pp. 382–398.
  * [13] J. Novikova, O. Dušek, A. C. Curry, and V. Rieser, “Why we need new evaluation metrics for nlg,” in _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , 2017, pp. 2241–2252.
  * [14] A. Chaganty, S. Mussmann, and P. Liang, “The price of debiasing automatic metrics in natural language evalaution,” in _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 2018, pp. 643–653.
  * [15] T. Zhang, V. Kishore, F. Wu, K. Q. Weinberger, and Y. Artzi, “Bertscore: Evaluating text generation with bert,” in _International Conference on Learning Representations_ , 2019.
  * [16] T. Sellam, D. Das, and A. Parikh, “Bleurt: Learning robust metrics for text generation,” in _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 2020, pp. 7881–7892.
  * [17] N. Reimers and I. Gurevych, “Sentence-bert: Sentence embeddings using siamese bert-networks,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , 2019, pp. 3982–3992.
  * [18] Q. Kong, Y. Cao, T. Iqbal, Y. Wang, W. Wang, and M. D. Plumbley, “PANNs: Large-Scale Pretrained Audio Neural Networks for Audio Pattern Recognition,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 28, pp. 2880–2894, 2020.
  * [19] X. Xu, H. Dinkel, M. Wu, Z. Xie, and K. Yu, “Investigating local and global information for automated audio captioning with transfer learning,” in _Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 905–909.
  * [20] A. K. Vijayakumar, M. Cogswell, R. R. Selvaraju, Q. Sun, S. Lee, D. Crandall, and D. Batra, “Diverse beam search for improved description of complex scenes,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2018, pp. 7371–7379.
  * [21] J. L. Fleiss, “Measuring nominal scale agreement among many raters.” _Psychological bulletin_ , vol. 76, no. 5, p. 378, 1971.
  * [22] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , 2019, pp. 4171–4186.
  * [23] Z. Zhang, Z. Zhou, H. Tang, G. Li, M. Wu, and K. Q. Zhu, “Enriching ontology with temporal commonsense for low-resource audio tagging,” _arXiv preprint arXiv:2110.01009_ , 2021.
  * [24] M. Jiang, Q. Huang, L. Zhang, X. Wang, P. Zhang, Z. Gan, J. Diesner, and J. Gao, “Tiger: Text-to-image grounding for image caption evaluation,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , 2019, pp. 2141–2152.