d}}[f^{[m]}({\bm{X}})g^{[m]}({\bm{X}})]$ (86)
$\displaystyle=\mathbb{E}_{{\bm{X}}\sim\mathcal{N}^{n\times
d}}[f({\bm{X}})g({\bm{X}})]$ (87)
$\displaystyle=\mathbb{E}_{{\bm{X}}\sim\mathcal{N}^{n\times
2}}[p({\bm{X}}{\bm{U}})p({\bm{X}}{\bm{V}})]$ (88)
$\displaystyle=\sum_{m=0}^{\infty}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}^{n\times
2}}[p^{[m]}({\bm{X}}{\bm{U}})p^{[m]}({\bm{X}}{\bm{V}})]$ (89)
$\displaystyle=\sum_{m=0}^{\infty}\frac{1}{m!}\langle\nabla_{{\bm{X}}}^{m}p^{[m]}({\bm{X}}{\bm{U}}),\nabla_{{\bm{X}}}^{m}p^{[m]}({\bm{X}}{\bm{V}})\rangle.$
(90)

Fix $m\in\mathbb{R}$, for each indices
$v_{1},\ldots,v_{m}\in[n],s_{1},\ldots,s_{m}\in[d]$, in Einstein notation,

$\displaystyle(\partial_{v_{1},s_{1}}\ldots\partial_{v_{m},s_{m}}f^{[m]})({\bm{X}})(\partial_{v_{1},s_{1}}\ldots\partial_{v_{m},s_{m}}g^{[m]})({\bm{X}})$
(91) $\displaystyle=$
$\displaystyle\partial_{v_{1},j_{1}}\ldots\partial_{v_{m},j_{m}}p^{[m]}({\bm{X}}{\bm{U}})\partial_{v_{1},j^{\prime}_{1}}\ldots\partial_{v_{m},j^{\prime}_{m}}p^{[m]}({\bm{X}}{\bm{V}}){\bm{U}}_{s_{1}j_{1}}\ldots{\bm{U}}_{s_{m}j_{m}}{\bm{V}}_{s_{1}j^{\prime}_{1}}\ldots{\bm{V}}_{s_{m}j^{\prime}_{m}}$
(92)

Taking the sum over all $v_{1},\ldots,v_{m}\in[n],s_{1},\ldots,s_{m}\in[d]$,
while still in Einstein notation, to get:

$\displaystyle|\langle\nabla_{{\bm{X}}}^{m}p^{[m]}({\bm{X}}{\bm{U}}),\nabla_{{\bm{X}}}^{m}p^{[m]}({\bm{X}}{\bm{V}})\rangle|$
(94) $\displaystyle=$
$\displaystyle|\partial_{v_{1},j_{1}}\ldots\partial_{v_{m},j_{m}}p^{[m]}({\bm{X}}{\bm{U}})\partial_{v_{1},j^{\prime}_{1}}\ldots\partial_{v_{m},j^{\prime}_{m}}p^{[m]}({\bm{X}}{\bm{V}})({\bm{U}}^{\top}{\bm{V}})_{j_{1}j^{\prime}_{1}}\ldots({\bm{U}}^{\top}{\bm{V}})_{j_{m}j^{\prime}_{m}}|$
(95) $\displaystyle\leq$ $\displaystyle
2^{m}\|\nabla_{{\bm{X}}}^{m}p^{[m]}({\bm{X}}{\bm{U}})\|^{2}_{2}\cdot\sqrt{n^{m}}\|{\bm{U}}^{\top}{\bm{V}}\|_{2}^{m}$
(96) $\displaystyle=$ $\displaystyle
m!\cdot\mathbb{E}_{{\bm{X}}\sim\mathcal{N}^{n\times
d}}[(p^{[m]}({\bm{X}}))^{2}]\cdot\left(2\sqrt{n}\|{\bm{U}}^{\top}{\bm{V}}\|_{2}\right)^{m},$
(97)

where we used $3$-variable Cauchy-Schwarz inequality
$|a_{ijk}b_{ijk}c_{ijk}|\leq\sqrt{a_{i^{\prime}j^{\prime}k^{\prime}}^{2}b_{i^{\prime\prime}j^{\prime\prime}k^{\prime\prime}}^{2}c_{i^{\prime\prime\prime}j^{\prime\prime\prime}k^{\prime\prime\prime}}^{2}}$
to obtain the inequality and Corollary 19 to obtain the last line. ∎

Notice that in the previous derivation, inequality only occurs at the Cauchy-
Schwarz inequality step. We can do a more careful analysis to get:

######  Corollary 25.

In the same setting as Lemma 24, we have:

$\displaystyle\langle
p(\cdot{\bm{U}})p(\cdot{\bm{V}})\rangle_{L^{2}(\mathcal{N})}$ (98)
$\displaystyle=$
$\displaystyle\sum_{m=0}^{\infty}\frac{1}{m!}\sum_{v_{1},\ldots,v_{m}=1}^{n}\sum_{j_{1},j^{\prime}_{1},\ldots,j_{m},j^{\prime}_{m}=1}^{2}\partial_{v_{1},j_{1}}\ldots\partial_{v_{m},j_{m}}p^{[m]}({\bm{X}}{\bm{U}})\partial_{v_{1},j^{\prime}_{1}}\ldots\partial_{v_{m},j^{\prime}_{m}}p^{[m]}({\bm{X}}{\bm{V}})({\bm{U}}^{\top}{\bm{V}})_{j_{1}j^{\prime}_{1}}\ldots({\bm{U}}^{\top}{\bm{V}})_{j_{m}j^{\prime}_{m}}.$
(99)

As the last ingredient, we need the following lemma that connects the family
of hard functions to lower bounds on CSQ algorithms:

######  Lemma 26 (Lemma 15 of Diakonikolas et al. [2020]).

Let $\mathcal{X}$ be the input space and $\mathcal{D}$ some distribution over
$\mathcal{X}$. For a finite set of functions $C=\\{f:X\to\mathbb{R}\\}$,
define:

$\rho(C):=1/|C|^{2}\sum_{f,g\in C}\langle f,g\rangle_{L^{2}(\mathcal{D})}.$
(100)

The correlational statistical query dimension is defined as:

$\rm{SDA}(C,\mathcal{D},\tau):=\max\\{m\mid\rho(C^{\prime})\leq\tau,\forall
C^{\prime}\subset C,|C^{\prime}|/|C|\geq 1/m\\}.$ (101)

Suppose that $\rm{SDA}(C,\mathcal{D},\tau)\geq m$ for some
$C,\mathcal{D},\tau$ and $m$, then there is a small enough $\epsilon$ such
that any CSQ algorithm that queries from an oracle of $f\in C$ and learn a
hypothesis $h\in C$ with $\langle f-h\rangle_{L^{2}(\mathcal{D})}\leq\epsilon$
either requires $\Omega(m)$ queries or at least one query with precision more
than $\sqrt{\tau}$.

We can now proceed to the proof of the main theorem:

######  Theorem 27.

Any correlational SQ algorithm that, for every concept $g\in
C^{\mathcal{B}}_{{\mathcal{G}}}$ learns a hypothesis $h$ such that
$\|g-h\|_{L^{2}(\mathcal{N})}\leq{\epsilon}$ for some small ${\epsilon}>0$
requires either $2^{d^{\Omega(1)}}$ queries or queries of tolerance at most
$d^{-k\Omega(1)}+2^{-d^{\Omega(1)}}$.

###### Proof.

This proof mirrors that in Diakonikolas et al. [2020]. Fix $c\in(0,1/2)$. To
upper bound pairwise correlation between different functions in
$C^{\mathcal{B}}_{{\mathcal{G}}}$, consider for any
${\bm{B}}_{i}\neq{\bm{B}}_{j}\in\mathcal{B}$:

$\displaystyle\left|\langle
f_{{\mathcal{G}}}(\cdot{\bm{B}}_{i}),f_{{\mathcal{G}}}(\cdot{\bm{B}}_{j})\rangle_{L^{2}(\mathcal{N})}\right|$
$\displaystyle\leq\sum_{m=0}^{\infty}(2\sqrt{n}\|{\bm{B}}_{i}^{\top}{\bm{B}}_{j}\|_{2})^{m}\cdot\|f_{{\mathcal{G}}}^{[m]}\|^{2}_{L^{2}(\mathcal{N})}$
(102)
$\displaystyle=\sum_{m>k}^{\infty}(2\sqrt{n}\|{\bm{B}}_{i}^{\top}{\bm{B}}_{j}\|_{2})^{m}\cdot\|f_{{\mathcal{G}}}^{[m]}\|^{2}_{L^{2}(\mathcal{N})}$
(103)
$\displaystyle\leq(2\sqrt{n}\|{\bm{B}}_{i}^{\top}{\bm{B}}_{j}\|_{2})^{k}\sum_{m>k}^{\infty}\|f_{{\mathcal{G}}}^{[m]}\|^{2}_{L^{2}(\mathcal{N})}$
(104) $\displaystyle\leq
O(d^{k(c-1/2)})\|f_{{\mathcal{G}}}\|^{2}_{L^{2}(\mathcal{N})}.$ (105)

In the above derivation, the first line uses Lemma 24; the second line uses
Lemma 21; and the last two lines use Lemma 23 and the fact that we can choose
an appropriate parameter to make $\|{\bm{B}}_{i}^{\top}{\bm{B}}_{j}\|_{2}<1$.
Dividing both sides by $\|f_{{\mathcal{G}}}\|_{L^{2}(\mathcal{N})}$ gives

$\left|\langle
g_{{\mathcal{G}}}^{{\bm{B}}_{i}},g_{{\mathcal{G}}}^{{\bm{B}}_{j}}\rangle_{L^{2}(\mathcal{N})}\right|\leq
O(d^{k(c-1/2)}).$ (106)

Now, since ${\bm{B}}_{i}^{\top}{\bm{B}}_{i}=\mathbf{1}_{2}$, we have
$\|f_{{\mathcal{G}}}(\cdot{\bm{B}}_{i})\|_{L^{2}(\mathcal{N})}=\|f_{{\mathcal{G}}}\|_{L^{2}(\mathcal{N})}$
and therefore $\|g_{{\mathcal{G}}}^{{\bm{B}}_{i}}\|_{L^{2}(\mathcal{N})}=1$.

We are in a position to apply Lemma 26. Let
$\tau:=\max_{{\bm{B}}_{i}\neq{\bm{B}}_{j}}\langle
g_{{\mathcal{G}}}^{{\bm{B}}_{i}},g_{{\mathcal{G}}}^{{\bm{B}}_{j}}\rangle_{L^{2}(\mathcal{N})}$.
Computing average pairwise correlation of $C_{{\mathcal{G}}}^{\mathcal{B}}$
yields:

$\rho(C_{{\mathcal{G}}}^{\mathcal{B}})=1/|\mathcal{B}|+(|\mathcal{B}|-1)\tau/(2|\mathcal{B}|)\leq
1/|\mathcal{B}|+\tau.$ (107)

Finally, setting $\tau^{\prime}:=1/|\mathcal{B}|+\tau$ gives
$\rm{SDA}(C^{\mathcal{B}}_{{\mathcal{G}}},\mathcal{N},\tau^{\prime})=2^{\Omega(d^{c})}$
and an application of Lemma 26 completes the proof for
$F^{d,k}_{{\mathcal{G}}}$.

To get the proof for $F^{d,k}_{n}$, by law of total expectation:

$\displaystyle\left|\mathbb{E}_{({\bm{X}},{\mathcal{G}})\sim\mathcal{N}\times\mathcal{E}}[f_{n}({\bm{X}}{\bm{B}}_{i},{\mathcal{G}})f_{n}({\bm{X}}{\bm{B}}_{j},{\mathcal{G}})]\right|$
(108) $\displaystyle=$
$\displaystyle\left|\mathbb{E}_{\mathcal{E}}\mathbb{E}_{\mathcal{N}\times\mathcal{E}}[f_{n}({\bm{X}}{\bm{B}}_{i},{\mathcal{G}})f_{n}({\bm{X}}{\bm{B}}_{j},{\mathcal{G}})|{\mathcal{G}}]\right|$
(109) $\displaystyle\leq$
$\displaystyle\sum_{{\mathcal{G}}\in\mathbb{G}_{n}}\operatorname{Pr}_{\mathcal{E}}({\mathcal{G}})\left|\mathbb{E}_{\mathcal{N}}[f_{{\mathcal{G}}}({\bm{X}}{\bm{B}}_{i})f_{{\mathcal{G}}}({\bm{X}}{\bm{B}}_{j})]\right|$
(110) $\displaystyle\leq$
$\displaystyle\sum_{{\mathcal{G}}\in\mathbb{G}_{n}}\operatorname{Pr}_{\mathcal{E}}({\mathcal{G}})\cdot\left(\max_{{\bm{B}}_{i}\neq{\bm{B}}_{j}\in\mathcal{B}}(2\sqrt{n}\|{\bm{B}}_{i}^{\top}{\bm{B}}_{j}\|_{2})^{k}\right)\cdot\|f_{{\mathcal{G}}}\|^{2}_{L^{2}(\mathcal{N})}$
(111) $\displaystyle\leq$ $\displaystyle
O(d^{k(c-1/2)})\|f_{n}\|^{2}_{L^{2}(\mathcal{N}\times\mathcal{E})},$ (112)

where in the third line, we use the fact that
$f_{{\mathcal{G}}}({\bm{Z}})=f_{n}({\bm{Z}},{\mathcal{G}})$ and triangle
inequality; in the fourth line, we use Eq. 105 and in the last line, we use
another instance of total expectation to get
$\|f_{n}\|_{L^{2}(\mathcal{N}\times\mathcal{E})}=\mathbb{E}_{{\mathcal{G}}\sim\mathcal{E}}\|f_{{\mathcal{G}}}\|_{L^{2}(\mathcal{N})}$.
It is worth pointing out that the only instance of ${\mathcal{G}}$ for which
we cannot apply Eq. 105 in the fourth line (assuming we use the normalized
Laplacian as ${\bm{A}}({\mathcal{G}})$) is when ${\mathcal{G}}$ is the empty
graph. However, in that case, $\|f_{{\mathcal{G}}}\|_{L^{2}(\mathcal{N})}=0$
since $f_{{\mathcal{G}}}\equiv 0$ and the inequality in the fourth line still
holds.

Lastly, proceed identically to the proof for $F^{d,k}_{{\mathcal{G}}}$ to use
Lemma 26 and get the final bound. ∎

##  Appendix F Frame-Averaging hardness proofs

#### Frame averaging.

Let $G$ be a subgroup of the permutation group $S_{n}$ that acts on
$\mathbb{R}^{n\times d}$ by permuting the rows and $e$ its identity element.
Let $\rho:G\to\textup{GL}(n)$ with $\rho(g)$ the representation of $g$ as a
matrix in $\mathbb{R}^{n\times n}$. For any group element $g\in G$ and
${\bm{X}}\in\mathbb{R}^{n\times d}$, we will write $g{\bm{X}}$ as a shorthand
for $\rho(g){\bm{X}}$ where the product is matrix multiplication. A frame is a
function $\mathcal{F}:\mathbb{R}^{n\times d}\to
2^{G}\backslash\\{\emptyset\\}$ satisfying
$\mathcal{F}(g{\bm{X}})=g\mathcal{F}({\bm{X}})$ set-wise. For given frames
$\mathcal{F}$, we will show a hardness result for the following class of
functions:

$\displaystyle\mathcal{H}_{\mathcal{F}}:=\Bigg{\\{}f:\mathbb{R}^{n\times
d}\to\mathbb{R}\text{ with
}f({\bm{X}})=\frac{1}{\sqrt{|\mathcal{F}({\bm{X}})|}}\sum_{g\in\mathcal{F}({\bm{X}})}{\bm{a}}^{\top}\sigma$
$\displaystyle({\bm{W}}^{\top}(g^{-1}{\bm{X}}))\mathbf{1}_{d}\mid$
$\displaystyle{\bm{W}}\in\mathbb{R}^{n\times
k},{\bm{a}}\in\mathbb{R}^{k}\Bigg{\\}},$ (113)

for given nonlinearity $\sigma$ that is not a polynomial of low degree.

###  F.1 Exponential lower bound for constant frame and Reynolds operator

######  Lemma 28 (Constant frame must be whole group).

If $\mathcal{F}({\bm{X}})$ is a constant function, i.e.
$\mathcal{F}({\bm{X}})$ is independent of ${\bm{X}}$, then
$\mathcal{F}({\bm{X}})=G\>\forall{\bm{X}}$.

###### Proof.

When $\mathcal{F}({\bm{X}})$ is a constant function, say $F\subseteq G$ for
all ${\bm{X}}$, then the frame property mandates that $F\neq\emptyset$ and
there is some $f\in F$. The frame property also tells us that since $f^{-1}\in
G$ (and $G$ is a group), $f^{-1}F=F$ and thus $e\in F$. Pick any element $g\in
G$ and observe that since $e\in F$ and $gF=F$, $g$ must also be in $F$. As
this is true for all elements $g\in G$, $F$ must be the whole group $G$
itself. ∎

In the following, we will therefore assume that $G$ is a polynomial-sized (in
$n$) subgroup of $S_{n}$. We will slightly modify Lemma 17 of [Diakonikolas et
al., 2020] to show:

######  Lemma 29.

For any $0<c<1/2$, and small ${\epsilon}\in(0,1)$, for any polynomial-sized
subset $F\subset S_{n}$, there exists a set $\mathcal{B}^{\prime}$ of at least
$2^{\Omega(n^{c})}/|F|^{2}$ matrices in $\mathbb{R}^{n\times 2}$ such that for
each pair ${\bm{B}},{\bm{B}}^{\prime}\in\mathcal{B}^{\prime}$ and for each
$g,g^{\prime}\in F$, it holds that:

  1. 1.

$(g{\bm{B}})^{\top}(g{\bm{B}})={\bm{I}}$;

  2. 2.

$\|(g{\bm{B}})^{\top}(g^{\prime}{\bm{B}}^{\prime})\|_{2}\leq O(n^{c-1/2})$
when ${\bm{B}}\neq{\bm{B}}^{\prime}$; and

  3. 3.

when $g\neq g^{\prime}$,
$(g{\bm{B}})^{\top}(g^{\prime}{\bm{B}}))_{ij}=:\begin{bmatrix}a_{1}&b_{1}\\\
b_{2}&a_{2}\end{bmatrix}$ where $b_{i}\leq O(n^{c-1/2})$ and,

$\displaystyle a_{i}-\frac{F_{g,g^{\prime}}}{n\sqrt{1-{\epsilon}}}$
$\displaystyle\leq O(n^{c-1/2}),$ (114) $\displaystyle
a_{i}-\sqrt{1-{\epsilon}}\frac{F_{g,g^{\prime}}}{n}$
$\displaystyle\geq-O(n^{c-1/2}),$ (115)

for $i\in[2]$. Here $F_{g,g^{\prime}}$ is the number of fixed points of
$g^{-1}g^{\prime}$ (number of cycles of length one).

The proof is delayed to Sec. F.3 for a more streamlined read.

#### Family of hard functions.

Recall the low-dimensional function from the proof of Theorem 4:

$f^{*}_{\exp}:\mathbb{R}^{2\times d}\to\mathbb{R}\text{ with
}f({\bm{X}})=({\bm{a}}^{*})^{\top}\sigma(({\bm{W}}^{*})^{\top}{\bm{X}})\mathbf{1}_{d}$
(116)

for some special parameter ${\bm{a}}^{*}\in\mathbb{R}^{2k}$ and
${\bm{W}}^{*}\in\mathbb{R}^{2\times 2k}$ in Eq. 11. We now define the family
of hard functions, indexed by a set of matrices
$\mathcal{B}\subset\mathbb{R}^{n\times 2}$ obtained from Lemma 29:

$\displaystyle
C^{\mathcal{B}}_{\mathcal{F}}=\Big{\\{}g_{{\bm{B}}}:\mathbb{R}^{n\times
d}\to\mathbb{R}\text{ with }g_{{\bm{B}}}({\bm{X}})=\frac{\sum_{g\in
G}f^{*}_{\exp}({\bm{B}}^{\top}g^{-1}{\bm{X}})}{\sqrt{|G|\cdot\|f^{*}_{\exp}\|_{\mathcal{N}}}}\mid{\bm{B}}\in\mathcal{B}^{\prime}$
$\displaystyle\subset\mathbb{R}^{n\times 2}\Big{\\}}.$ (117)

######  Theorem 30.

For any feature dimension $d=\Theta(1)$ and width parameter $k=\Theta(n)$. Let
$G$ be a subgroup of $S_{n}$ with $|G|=\Theta(\textup{poly}(n))$. Pick a set
$\mathcal{B}^{\prime}\subset\mathbb{R}^{n\times 2}$444The different notation
highlights the fact that we are using a slightly different set of matrices
from Lemma 23 and [Diakonikolas et al., 2020]. of size at least
$2^{\Omega(d^{\Omega(1)})}/|G|^{2}$ according to Lemma 29 and normalize each
function in the hard function family $C^{\mathcal{B}^{\prime}}_{\mathcal{F}}$
to have $\|\cdot\|_{\mathcal{N}}$ norm $1$. Let $\epsilon^{\prime}>0$ be a
sufficiently small error constant. Then for any $g\in
C^{\mathcal{B}^{\prime}}_{\mathcal{F}}$, any CSQ algorithm that queries from
oracles of concept $f\in C^{\mathcal{B}^{\prime}}_{\mathcal{F}}$ and outputs a
hypothesis $h$ with $\|f-h\|_{\mathcal{N}}\leq\epsilon^{\prime}$ requires
either $2^{n^{\Omega(1)}}/|G|^{2}$ queries or at least one query with
precision $|G|2^{-n^{\Omega(1)}}+\sqrt{|G|}n^{-\Omega(k)}$.

###### Proof.

First we review properties of the constructed objects. By Lemma 29,
$g{\bm{B}}$ and $g^{\prime}{\bm{B}}^{\prime}$ are almost orthogonal for any
${\bm{B}}\neq{\bm{B}}^{\prime}\in\mathcal{B}^{\prime}$ and $g,g^{\prime}\in
G$.

Then by Theorem 27 with matrix ${\bm{A}}={\bm{I}}_{d}$, for any
${\bm{B}}\neq{\bm{B}}^{\prime}\in\mathcal{B}^{\prime}$ and any
$g,g^{\prime}\in G$, noting that
${\bm{B}}^{\top}(g^{-1}{\bm{X}})=(g{\bm{B}})^{\top}{\bm{X}}$ since a
permutation matrix is orthonormal, we have

$\displaystyle|\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}[f^{*}_{\exp}((g{\bm{B}})^{\top}{\bm{X}})f^{*}_{\exp}((g^{\prime}{\bm{B}}^{\prime})^{\top}{\bm{X}})]|\leq
O(n^{k(c-1/2)})\|f^{*}_{\exp}\|^{2}_{\mathcal{N}},$ (118)

for the same $c$ that was chosen in the statement of Lemma 29.

Now we verify that $\|g_{\bm{B}}\|_{\mathcal{N}}=\Omega(1)$ for each
$g_{{\bm{B}}}\in C^{\mathcal{B}^{\prime}}_{FA(G)}$. Let
${\bm{B}}=\begin{bmatrix}{\bm{x}}&{\bm{y}}\end{bmatrix}$ and
${\bm{B}}_{g}:=g{\bm{B}},{\bm{B}}_{g^{\prime}}:=(g^{\prime}){\bm{B}}$.

$\displaystyle\|g_{\bm{B}}\|_{\mathcal{N}}^{2}$ (119) $\displaystyle=$
$\displaystyle\frac{1}{\|f^{*}_{\exp}\|^{2}_{\mathcal{N}}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\sum_{g\in
G}\frac{(f^{*}_{\exp}({\bm{B}}_{g}^{\top}{\bm{X}}))^{2}}{|G|}+\sum_{g\neq
g^{\prime}\in
G}\frac{f^{*}_{\exp}(({\bm{B}}_{g}^{\top}{\bm{X}})f^{*}_{\exp}({\bm{B}}_{g^{\prime}}^{\top}{\bm{X}})}{|G|}\right]$
(120) $\displaystyle=$ $\displaystyle
1+\frac{1}{|G|\|f^{*}_{\exp}\|^{2}_{\mathcal{N}}}\sum_{g\neq g^{\prime}\in
G}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[f^{*}_{\exp}({\bm{B}}_{g}^{\top}{\bm{X}})f^{*}_{\exp}({\bm{B}}_{g^{\prime}}^{\top}{\bm{X}})\right]$
(121)

Now we split the sum into two parts. In the first part, we examine $g\neq
g^{\prime}$ such that $\max(|\langle
g{\bm{x}},g^{\prime}{\bm{x}}\rangle|,|\langle
g{\bm{y}},g^{\prime}{\bm{y}}\rangle|)<c_{1}$ for some constant
$0<c_{1}<1/\sqrt{3}$, and leave the remaining cases for the other part.
Collect the pairs $g,g^{\prime}$ in the first part into a set $G_{1}$. Then

$\displaystyle\left|\frac{1}{|G|\|f^{*}_{\exp}\|^{2}_{\mathcal{N}}}\sum_{g\neq
g^{\prime}\in
G_{1}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[f^{*}_{\exp}({\bm{B}}_{g}^{\top}{\bm{X}})f^{*}_{\exp}({\bm{B}}_{g^{\prime}}^{\top}{\bm{X}})\right]\right|$
(122) $\displaystyle\leq$
$\displaystyle\frac{1}{|G|\|f^{*}_{\exp}\|^{2}_{\mathcal{N}}}\sum_{g\neq
g^{\prime}\in
G_{1}}\left|\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[f^{*}_{\exp}({\bm{B}}_{g}^{\top}{\bm{X}})f^{*}_{\exp}({\bm{B}}_{g^{\prime}}^{\top}{\bm{X}})\right]\right|$
(123) $\displaystyle\leq$ $\displaystyle\frac{1}{|G|}\sum_{g\neq g^{\prime}\in
G}\|{\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}}\|_{2}^{k},$ (124)

where $k$ is the number of neurons in the hidden layer of $f_{\exp}^{*}$. The
second line comes from the triangle inequality and the last line comes from
Theorem 27.

We have,

$\displaystyle\|{\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}}\|_{2}^{k}$
$\displaystyle\leq\|{\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}}\|_{F}^{k}$ (125)
$\displaystyle=\left(2z^{2}+\langle
g{\bm{x}},(g^{\prime}){\bm{x}}\rangle^{2}+\langle
g{\bm{y}},(g^{\prime}){\bm{y}}\rangle^{2}\right)^{k/2}$ (126)
$\displaystyle\leq 3^{k/2-1}\left((2z)^{k}+|\langle
g{\bm{x}},(g^{\prime}){\bm{x}}\rangle|^{k}+|\langle
g{\bm{y}},(g^{\prime}){\bm{y}}\rangle|^{k}\right).$ (127)

The last line uses power mean inequality. By our assumptions,

$\displaystyle 3^{k/2-1}\sum_{g\neq g^{\prime}\in G}|\langle
g{\bm{x}},(g^{\prime}){\bm{x}}\rangle|^{k}<|G|(|G|-1)\frac{(c_{1}\sqrt{3})^{k}}{3}<|G|(|G|-1)(c_{1}\sqrt{3})^{k}$
(128)

and similarly $3^{k/2-1}\sum_{g\neq g^{\prime}\in G}|\langle
g{\bm{y}},(g^{\prime}){\bm{y}}\rangle|^{k}\leq|G|(|G|-1)(c_{1}\sqrt{3})^{k}$.

Plugging back,

$\displaystyle\frac{1}{|G|\|f^{*}_{\exp}\|^{2}_{\mathcal{N}}}\left|\sum_{g\neq
g^{\prime}\in
G_{1}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[f^{*}_{\exp}({\bm{B}}_{g}^{\top}{\bm{X}})f^{*}_{\exp}({\bm{B}}_{g^{\prime}}^{\top}{\bm{X}})\right]\right|\leq(|G|-1)(c_{1}\sqrt{3})^{k}.$
(129)

Since $|G|=\textup{poly}(n)$ and $k=\Theta(n)$, the final expression is $o(1)$
in $n$.

We now consider the remaining part which is reproduced here:

$\displaystyle\frac{1}{|G|\|f^{*}_{\exp}\|^{2}_{\mathcal{N}}}\sum_{g\neq
g^{\prime}\in G^{2}\backslash
G_{1}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[f^{*}_{\exp}((g{\bm{B}})^{\top}{\bm{X}})f^{*}_{\exp}((g^{\prime}{\bm{B}})^{\top}{\bm{X}})\right]$
(130)

Zooming in, we have:

$\displaystyle\sum_{g\neq g^{\prime}\in G^{2}\backslash
G_{1}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[f^{*}_{\exp}({\bm{B}}_{g}^{\top}{\bm{X}})f^{*}_{\exp}({\bm{B}}_{g^{\prime}}^{\top}{\bm{X}})\right]$
(131) $\displaystyle=$ $\displaystyle\sum_{g\neq g^{\prime}\in G^{2}\backslash
G_{1}}\sum_{m=0}^{\infty}\frac{1}{m!}\sum_{v_{1},\ldots,v_{m}=1}^{d}\sum_{j_{1},j^{\prime}_{1},\ldots,j_{m},j^{\prime}_{m}=1}^{2}$
$\displaystyle\qquad\qquad\partial_{v_{1},j_{1}}\ldots\partial_{v_{m},j_{m}}(f^{*}_{\exp})^{[m]}(\cdot)\partial_{v_{1},j^{\prime}_{1}}\ldots\partial_{v_{m},j^{\prime}_{m}}(f^{*}_{\exp})^{[m]}(\cdot)({\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}})_{j_{1}j^{\prime}_{1}}\ldots({\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}})_{j_{m}j^{\prime}_{m}}$
(132) $\displaystyle=$ $\displaystyle\sum_{g\neq g^{\prime}\in G^{2}\backslash
G_{1}}\sum_{m=k}^{\infty}\frac{1}{m!}\sum_{v_{1},\ldots,v_{m}=1}^{d}\sum_{j_{1},j^{\prime}_{1},\ldots,j_{m},j^{\prime}_{m}=1}^{2}$
$\displaystyle\qquad\qquad\partial_{v_{1},j_{1}}\ldots\partial_{v_{m},j_{m}}(f^{*}_{\exp})^{[m]}(\cdot)\partial_{v_{1},j^{\prime}_{1}}\ldots\partial_{v_{m},j^{\prime}_{m}}(f^{*}_{\exp})^{[m]}(\cdot)({\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}})_{j_{1}j^{\prime}_{1}}\ldots({\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}})_{j_{m}j^{\prime}_{m}},$
(133)

where the second line comes from Corollary 25 and the last line is because all
low-degree moment of $f^{*}_{\exp}$ vanishes.

Further zooming in, for each $g\neq g^{\prime}\in G^{2}\backslash G_{1}$, each
$m\geq k$ and each $v_{1},\ldots,v_{m}\in[2]$, denote ${\bm{p}}_{J}$ as
$\partial_{v_{1},J_{1}}\ldots\partial_{v_{m},J_{m}}(f^{*}_{\exp})^{[m]}(\cdot)$
for each $J\in[2]^{m}$, and the corresponding vector
${\bm{p}}\in\mathbb{R}^{2^{m}}$. We have, using Einstein notation to sum over
$j_{1},\ldots j_{m},j^{\prime}_{1},\ldots,j^{\prime}_{m}$:

$\displaystyle\partial_{v_{1},j_{1}}\ldots\partial_{v_{m},j_{m}}(f^{*}_{\exp})^{[m]}(\cdot)\partial_{v_{1},j^{\prime}_{1}}\ldots\partial_{v_{m},j^{\prime}_{m}}(f^{*}_{\exp})^{[m]}(\cdot)({\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}})_{j_{1}j^{\prime}_{1}}\ldots({\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}})_{j_{m}j^{\prime}_{m}},={\bm{p}}^{\top}({\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}})^{\otimes
m}{\bm{p}}$ (134)

By Corollary 43, it suffices to show that
${\bm{C}}:={\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}}$ satisfies
${\bm{z}}^{\top}{\bm{C}}{\bm{z}}\geq 0$ for all ${\bm{z}}\in\mathbb{R}^{2}$.
However, note that by concentration results of Lemma 29, for any small
${\epsilon}\in(0,1)$,

$\displaystyle\langle g{\bm{x}},g^{\prime}{\bm{x}}\rangle$
$\displaystyle\in\left[\sqrt{1-{\epsilon}}\bar{F}_{g,g^{\prime}}-\delta_{{\bm{x}}},\frac{\bar{F}_{g,g^{\prime}}}{\sqrt{1-{\epsilon}}}+\delta_{\bm{x}}\right]$
(135) $\displaystyle\langle g{\bm{y}},g^{\prime}{\bm{y}}\rangle$
$\displaystyle\in\left[\sqrt{1-{\epsilon}}\bar{F}_{g,g^{\prime}}-\delta_{{\bm{y}}},\frac{\bar{F}_{g,g^{\prime}}}{\sqrt{1-{\epsilon}}}+\delta_{\bm{y}}\right]$
(136) $\displaystyle\langle g{\bm{x}},g^{\prime}{\bm{y}}\rangle$
$\displaystyle={\epsilon}_{1}$ (137) $\displaystyle\langle
g{\bm{y}},g^{\prime}{\bm{x}}\rangle$ $\displaystyle={\epsilon}_{2},$ (138)

for $\delta_{\bm{x}},\delta_{\bm{y}}\geq
0,\max(\delta_{\bm{x}},\delta_{\bm{y}},|{\epsilon}_{1}|,|{\epsilon}_{2}|)<O(n^{c-1/2})$
and $\bar{F}_{g,g^{\prime}}=F_{g,g^{\prime}}/n$ with $F_{g,g^{\prime}}$
denotes the number of fixed points of $g^{-1}g^{\prime}$ as in Lemma 29. Note
that $1\geq\bar{F}_{g,g^{\prime}}>c_{1}$ is bounded away from $0$ (by
definition of $G_{1}$ and concentration result in Lemma 29). Choose
${\epsilon}$ small enough that
$\sqrt{1-{\epsilon}}\bar{F}_{g,g^{\prime}}=:c_{2},c_{2}-\delta_{\bm{x}},c_{2}-\delta_{\bm{y}}$
are all bounded away from $0$ when $n$ is large enough. Thus, for any
${\bm{z}}\in\mathbb{R}^{2}$,

$\displaystyle{\bm{z}}^{\top}{\bm{C}}{\bm{z}}$
$\displaystyle\geq{\bm{z}}_{1}^{2}(c_{2}-\delta_{\bm{x}})+{\bm{z}}_{2}^{2}(c_{2}-\delta_{\bm{y}})+{\bm{z}}_{1}{\bm{z}}_{2}({\epsilon}_{1}+{\epsilon}_{2})$
(139)
$\displaystyle=(c_{2}-\delta_{\bm{x}})\left({\bm{z}}_{1}-\frac{{\epsilon}_{1}+{\epsilon}_{2}}{c_{2}-\delta_{\bm{x}}}{\bm{z}}_{2}\right)^{2}+{\bm{z}}^{2}_{2}\left(c_{2}-\delta_{\bm{y}}-\frac{({\epsilon}_{1}+{\epsilon}_{2})^{2}}{c_{2}-\delta_{\bm{x}}}\right),$
(140)

which is clearly nonnegative for large enough $n$ as $c_{2}$ is bounded away
from $0$. We conclude that
${\bm{p}}^{\top}({\bm{B}}_{g}^{\top}{\bm{B}}_{g^{\prime}})^{\otimes
m}{\bm{p}}$ is nonnegative and thus removing these terms leads to a lower
bound on $\|g_{{\bm{B}}}\|_{\mathcal{N}}^{2}$.

For pairwise correlation, we have:

$\displaystyle|\langle g_{\bm{B}},g_{{\bm{B}}^{\prime}}\rangle_{\mathcal{N}}|$
$\displaystyle\leq\frac{1}{|G|\cdot\|f^{*}_{\exp}\|^{2}_{\mathcal{N}}}\left|\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\sum_{g,g^{\prime}\in
G}f^{*}_{\exp}((g{\bm{B}})^{\top}{\bm{X}})f^{*}_{\exp}((g^{\prime}{\bm{B}}^{\prime})^{\top}{\bm{X}})\right|$
(141)
$\displaystyle\leq\frac{1}{|G|\cdot\|f^{*}_{\exp}\|^{2}_{\mathcal{N}}}\sum_{g,g^{\prime}\in
G}\left|\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}f^{*}_{\exp}((g{\bm{B}})^{\top}{\bm{X}})f^{*}_{\exp}((g^{\prime}{\bm{B}}^{\prime})^{\top}{\bm{X}})\right|$
(142) $\displaystyle\leq O(n^{k(c-1/2)})|G|.$ (143)

Now we replace each $g_{{\bm{B}}}$ by its normalization to make
$\|g_{{\bm{B}}}\|_{\mathcal{N}}^{2}=1$. Note that this only decreases (or
increases by at most a constant factor) the correlation between different hard
functions since $\|g_{{\bm{B}}}\|_{\mathcal{N}}^{2}=\Omega(1)$. We are in
position to apply Lemma 26. Let
$\tau:=\max_{{\bm{B}}_{i}\neq{\bm{B}}_{j}}|\langle
g_{{\bm{B}}_{i}},g_{{\bm{B}}_{j}}\rangle_{L^{2}(\mathcal{N})}|$. Computing
average pairwise correlation of $C_{{\mathcal{G}}}^{\mathcal{B}^{\prime}}$
yields:

$\rho(C_{{\mathcal{G}}}^{\mathcal{B}^{\prime}})=1/|\mathcal{B}^{\prime}|+(1-1/|\mathcal{B}^{\prime}|)\tau\leq
2/|\mathcal{B}^{\prime}|+\tau.$ (144)

Finally, setting $\tau^{\prime}:=2/|\mathcal{B}^{\prime}|+\tau$ gives
$\rm{SDA}(C^{\mathcal{B}^{\prime}}_{{\mathcal{G}}},\mathcal{N},\tau^{\prime})=2^{\Omega(n^{c})}/|G|^{2}$
and an application of Lemma 26 completes the proof.

∎

###  F.2 Superpolynomial lower bounds

Throughout, we will use the notation $\subseteq_{k}$ to denote a subset of
size $k$. The technique from this part comes mainly from [Goel et al., 2020].
Define:

$f_{S}:\mathbb{R}^{n\times d}\to\mathbb{R},\text{ where
}f_{S}({\bm{X}})=\mathbf{1}_{d}^{\top}\left(\sum_{{\bm{w}}\in\\{-1,1\\}^{k}}\chi({\bm{w}})\sigma(\langle{\bm{w}},{\bm{X}}_{S}\rangle/\sqrt{k})\right),\qquad
S\subseteq_{k}[n].$ (145)

where $\chi$ is the parity function $\chi({\bm{w}})=\prod_{i}w_{i}$, and
${\bm{X}}_{S}\in\mathcal{X}^{k}$, or alternatively
${\bm{X}}_{S}\in\mathbb{R}^{k\times d}$, denotes the rows of ${\bm{X}}$
indexed by $S$. Here,
$\langle{\bm{w}},{\bm{X}}_{S}\rangle:=\sum_{i=1}^{k}w_{i}({\bm{X}}_{S})_{i,:}=w\cdot{\bm{X}}_{S}$
and $\sigma:\mathbb{R}^{d}\to\mathbb{R}^{d}$ is an activation function.
Throughout, we will set $k\leq\log_{2}n$ so that the above network has at most
$O(n)$ hidden nodes. For any ${\bm{z}}\in\\{-1,1\\}^{n}$, let
${\bm{X}}\circ{\bm{z}}$ be the matrix in $\mathbb{R}^{n\times d}$ whose $v$-th
row is ${\bm{z}}_{v}{\bm{X}}_{v,:}$. We will use the following lemma, which is
a basic consequence of properties proven in Goel et al. [2020], but include
the proofs here to be self-contained.

######  Lemma 31.

For all $S\neq T\subseteq_{k}[n]$, $g\in G$, and ${\bm{z}}\in\\{-1,1\\}^{n}$,
we have:

  1. 1.

$f_{S}(g\cdot({\bm{X}}\circ{\bm{z}}))=\chi_{g^{-1}\cdot
S}({\bm{z}})f_{S}(g\cdot{\bm{X}})=\chi_{g^{-1}\cdot S}({\bm{z}})f_{g^{-1}\cdot
S}({\bm{X}})$.

  2. 2.

$\|f_{S}\|_{L^{2}(\mathcal{N})}\geq\Omega(e^{-\Theta(k)})$ and $\langle
f_{S},f_{T}\rangle_{L^{2}(\mathcal{N})}=0$.

###### Proof.

Fix $S\neq T\subseteq_{k}[n]$.

  1. 1.

By definition:

$\displaystyle
f_{S}({\bm{X}})=\sum_{j=1}^{d}\sum_{{\bm{w}}\in\\{-1,1\\}^{k}}\chi({\bm{w}})\sigma(\langle{\bm{w}},({\bm{X}}_{;,j})_{S}\rangle/\sqrt{k})$
(146)

where ${\bm{X}}_{:,j}$ is the $j$-th column of ${\bm{X}}$. $G$ acts on the
rows of ${\bm{X}}$, i.e. $(g{\bm{X}})_{i,:}={\bm{X}}_{g^{-1}i,:}$. Therefore,
letting the order of $S$ be fixed, we have
$(g{\bm{X}})_{S}={\bm{X}}_{g^{-1}S,:}$.

We have, for any $g\in G$ and any ${\bm{z}}\in\\{-1,1\\}^{n}$:

$\displaystyle f_{S}(g\cdot({\bm{X}}\circ{\bm{z}}))$
$\displaystyle=\sum_{j=1}^{d}\sum_{{\bm{w}}\in\\{-1,1\\}^{k}}\chi({\bm{w}})\sigma(\langle{\bm{w}},((g\cdot({\bm{X}}\circ{\bm{z}}))_{;,j})_{S}\rangle/\sqrt{k})$
(147)
$\displaystyle=\sum_{j=1}^{d}\sum_{{\bm{w}}\in\\{-1,1\\}^{k}}\chi({\bm{w}})\sigma(\langle{\bm{w}},(({\bm{X}}\circ{\bm{z}})_{;,j})_{g^{-1}\cdot
S}\rangle/\sqrt{k})$ (148)
$\displaystyle=\sum_{j=1}^{d}\sum_{{\bm{w}}\in\\{-1,1\\}^{k}}\chi({\bm{w}})\sigma(\langle{\bm{w}},({\bm{X}}_{;,j})_{g^{-1}\cdot
S}\circ{\bm{z}}_{g^{-1}\cdot S}\rangle/\sqrt{k})$ (149)
$\displaystyle=\chi_{g^{-1}\cdot
S}({\bm{z}})\sum_{j=1}^{d}\sum_{{\bm{w}}\in\\{-1,1\\}^{k}}\chi({\bm{w}}\circ{\bm{z}}_{g^{-1}\cdot
S})\sigma(\langle{\bm{w}}\circ{\bm{z}}_{g^{-1}\cdot
S},({\bm{X}}_{;,j})_{g^{-1}\cdot S}\rangle/\sqrt{k})$ (150)
$\displaystyle=\chi_{g^{-1}\cdot
S}({\bm{z}})\sum_{j=1}^{d}\sum_{{\bm{w}}\in\\{-1,1\\}^{k}}\chi({\bm{w}})\sigma(\langle{\bm{w}},({\bm{X}}_{;,j})_{g^{-1}\cdot
S}\rangle/\sqrt{k})$ (151) $\displaystyle=\chi_{g^{-1}\cdot
S}({\bm{z}})f_{g^{-1}\cdot S}({\bm{X}})$ (152)
$\displaystyle=\chi_{g^{-1}\cdot S}({\bm{z}})f_{S}(g\cdot{\bm{X}}).$ (153)

In the above derivation, we use the definition of $f_{S}$ to get the first
line. The second line comes from the fact that permuting by $g$, then taking
the subset $S$ is equivalent to taking the subset $g^{-1}\cdot S$. The third
line comes from the fact that each element of ${\bm{z}}$ is a scalar. The
fourth line comes from the fact that $\chi({\bm{w}})=\chi_{g^{-1}\cdot
S}({\bm{z}})\cdot\chi_{g^{-1}\cdot S}({\bm{w}}\circ{\bm{z}}_{g^{-1}\cdot S})$.
The fifth line is a change of variable
${\bm{w}}\mapsto{\bm{w}}\circ{\bm{z}}_{g^{-1}\cdot S}$. Finally, the last line
comes from the definition of $f_{S}$, and noting that the dependence of
$f_{S}$ on $S$ only comes from which row of ${\bm{X}}$ is selected by $S$;
thus, $f_{g^{-1}\cdot S}({\bm{X}})=f_{S}(g\cdot{\bm{X}})$.

  2. 2.

We have, for any $S\neq T$:

$\displaystyle\langle f_{S},f_{T}\rangle_{\mathcal{L}^{2}(\mathcal{N})}$
$\displaystyle=\mathbb{E}_{{\bm{X}}\sim\mathcal{L}^{2}(\mathcal{N})}[f_{S}({\bm{X}})f_{T}({\bm{X}})]$
(154)
$\displaystyle=\mathbb{E}_{{\bm{z}}\sim\rm{Unif}(\\{-1,1\\}^{n})}\mathbb{E}_{{\bm{X}}}[f_{S}({\bm{X}}\circ{\bm{z}})f_{T}({\bm{X}}\circ{\bm{z}})]$
(155)
$\displaystyle=\mathbb{E}_{{\bm{z}}\sim\rm{Unif}(\\{-1,1\\}^{n})}\mathbb{E}_{{\bm{X}}}[f_{S}({\bm{X}})f_{T}({\bm{X}})\chi_{S}({\bm{z}})\chi_{T}({\bm{z}})]$
(156)
$\displaystyle=\mathbb{E}_{\bm{X}}[f_{S}({\bm{X}})f_{T}({\bm{X}})]\mathbb{E}_{{\bm{z}}\sim\rm{Unif(\\{-1,1\\}^{n})}}[\chi_{S}({\bm{z}})\chi_{T}({\bm{z}})]$
(157) $\displaystyle=0$ (158)

by sign-invariance of $\mathcal{N}$ and orthogonality of parity functions
under $\rm{Unif}(\\{-1,1\\}^{n})$. When $S=T$, the same argument as Goel et
al. [2020] Theorem 3.8 shows that $f_{S}$ does not vanish.

∎

Now, define the family of hard functions as:

$\mathcal{H}_{\mathcal{S},\mathcal{F}}:=\left\\{\tilde{f}_{S}:{\bm{X}}\mapsto\frac{1}{\sqrt{|\mathcal{F}({\bm{X}})|}}\sum_{g\in\mathcal{F}({\bm{X}})}f_{S}(g\cdot{\bm{X}})\mid[n]\supseteq_{k}S\in\mathcal{S}\right\\},$
(159)

for some set $\mathcal{S}$ depending on $\mathcal{F}$ and $G$. The subsets in
$\mathcal{S}$ such that these hard functions are orthogonal will determine the
size of the family of hard functions, and therefore the CSQ dimension lower
bound.

######  Definition 32 (Sign-invariant frame).

A frame $\mathcal{F}$ is sign-invariant if
$\mathcal{F}({\bm{X}})=\mathcal{F}({\bm{X}}\circ{\bm{z}})$ for almost all
${\bm{X}}$ (under the given data distribution) and for all
${\bm{z}}\in\\{-1,1\\}^{n}$.

######  Lemma 33.

If $\mathcal{F}$ is any sign-invariant frame, then there exists $\mathcal{S}$
with $|\mathcal{S}|\geq\Omega(n^{\Omega(\log n)})/M(n)$ such that the
functions in $\mathcal{H}_{\mathcal{S},\mathcal{F}}$ are pairwise orthogonal,
where $M(n)$ is the size of the largest orbit of $\binom{[n]}{m}$ where
$m=\Omega(\log n)$ under $G$. If moreover $|\mathcal{F}({\bm{X}})|=1$ for
almost all $x$, then $|\mathcal{S}|=\Omega(n^{\Omega(\log n)})$.

###### Proof.

We have for any $S\neq T$:

$\displaystyle\langle\tilde{f}_{S},\tilde{f}_{T}\rangle_{L^{2}(\mathcal{N})}$
$\displaystyle=\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\frac{1}{|\mathcal{F}({\bm{X}})|}\sum_{g,g^{\prime}\in\mathcal{F}({\bm{X}})}f_{S}(g\cdot{\bm{X}})f_{T}(g^{\prime}\cdot{\bm{X}})$
(160)
$\displaystyle=\mathbb{E}_{{\bm{z}}\sim\rm{Unif}\\{-1,1\\}^{n}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\frac{1}{|\mathcal{F}({\bm{X}}\circ{\bm{z}})|}\sum_{g,g^{\prime}\in\mathcal{F}({\bm{X}}\circ{\bm{z}})}f_{S}(g\cdot({\bm{X}}\circ{\bm{z}}))f_{T}(g^{\prime}\cdot({\bm{X}}\circ{\bm{z}}))$
(161)
$\displaystyle=\mathbb{E}_{{\bm{z}}\sim\rm{Unif}\\{-1,1\\}^{n}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\frac{1}{|\mathcal{F}({\bm{X}}\circ{\bm{z}})|}$
$\displaystyle\qquad\qquad\sum_{g,g^{\prime}\in\mathcal{F}({\bm{X}}\circ{\bm{z}})}\chi_{g^{-1}\cdot
S}({\bm{z}})f_{g^{-1}\cdot S}({\bm{X}})\chi_{(g^{\prime})^{-1}\cdot
T}({\bm{z}})f_{(g^{\prime})^{-1}\cdot T}({\bm{X}})$ (162)
$\displaystyle=\mathbb{E}_{{\bm{z}}\sim\rm{Unif}\\{-1,1\\}^{n}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\frac{1}{|\mathcal{F}({\bm{X}})|}$
$\displaystyle\qquad\qquad\sum_{g,g^{\prime}\in\mathcal{F}({\bm{X}})}\chi_{g^{-1}\cdot
S}({\bm{z}})f_{g^{-1}\cdot S}({\bm{X}})\chi_{(g^{\prime})^{-1}\cdot
T}({\bm{z}})f_{(g^{\prime})^{-1}\cdot T}({\bm{X}})$ (163)
$\displaystyle=\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\frac{1}{|\mathcal{F}({\bm{X}})|}$
$\displaystyle\qquad\qquad f_{g^{-1}\cdot
S}({\bm{X}})f_{(g^{\prime})^{-1}\cdot
T}({\bm{X}})\sum_{g,g^{\prime}\in\mathcal{F}({\bm{X}})}\mathbb{E}_{{\bm{z}}\sim\rm{Unif}\\{-1,1\\}^{n}}\chi_{g^{-1}\cdot
S}({\bm{z}})\chi_{(g^{\prime})^{-1}\cdot T}({\bm{z}})$ (164)

Here, we have used that the frame is sign-invariant to replace
$\mathcal{F}({\bm{X}}\circ{\bm{z}})$ with simply $\mathcal{F}({\bm{X}})$, and
rearrange the expectations accordingly. Now, if we have no further assumptions
on $\mathcal{F}$, then we require $S$ and $T$ to be $m=\Omega(\log n)$-sized
subsets in different orbits (in other words, $S\neq gT$ for all $g\in G$).
Then, by Lemma 31, $g^{-1}S\neq(g^{\prime})^{-1}T$ for any $g$ and
$g^{\prime}$, and the inner expectation over ${\bm{z}}$ (and therefore the
entire expression) is 0. This yields a lower bound on $|\mathcal{S}|$ of
$\Omega(n^{\Omega(\log n)}))/M(n)$, from choosing one $\log n$-sized subset
from each orbit.

If we moreover have that $\mathcal{F}$ has size one almost everywhere, then
$S\neq T$ suffices to ensure orthogonality, and we can set
$|\mathcal{S}|=n^{m}$ where $m=\Theta(\log n)$ by letting $\mathcal{S}$ be all
$\Theta(\log n)$-sized subsets of $[n]$. Note that if subsets are size
$\Theta(\log n)$, the hidden width of the network is polynomial and
furthermore, if $m\leq\log_{2}n$ then the width is $O(n)$. ∎

######  Remark 34.

Note that the definition of frame always allows one to choose a singleton
frame $\mathcal{F}({\bm{X}})$ for any ${\bm{X}}$ whose stabilizer is trivial
under the action of $G$ on $\mathcal{R}^{n\times d}$. For any other ${\bm{X}}$
with nontrivial stabilizer, since $G$ is a subgroup of the permutation group,
${\bm{X}}$ must have at least $2$ equal entries and thus lies in a manifold of
dimensions strictly smaller than $n\times d$. Density of $\mathcal{N}$ thus
ensures that $\Pr_{{\bm{X}}\sim\mathcal{N}}[|\mathcal{F}({\bm{X}})|=1]=1$ as
long as we choose the singleton frame at every ${\bm{X}}$ without self-
symmetry. A practical choice of frame in this case, which is also sign-
invariant, is the frame $\mathcal{F}({\bm{X}})$ which is the set of all
permutations that lexicographically sort ${\bm{X}}$ by absolute value. It is
not hard to see that with probability $1$ under $\mathcal{N}$, there is only
$1$ permutation that sorts ${\bm{X}}$.

######  Remark 35.

The case of sign-invariant frames includes $\mathcal{F}({\bm{X}})=G$, the
Reynolds operator.

######  Corollary 36.

Let $\mathcal{F}$ be a sign-invariant frame. For any $c>0$, any CSQ algorithm
that queries from an oracle of concept
$f\in\mathcal{H}_{\mathcal{S},\mathcal{F}}$ and outputs a hypothesis $h$ with
$\|f-h\|_{\mathcal{N}}\leq\Theta(1)$ needs at least $\Omega(n^{\Omega(\log
n)})/M(n))$ queries or at least one query with precision $o(n^{-c/2})$.

######  Corollary 37.

Let $\mathcal{F}$ be a sign-invariant singleton frame. For any $c>0$, any CSQ
algorithm that queries from an oracle of concept
$f\in\mathcal{H}_{\mathcal{S},\mathcal{F}}$ and outputs a hypothesis $h$ with
$\|f-h\|_{\mathcal{N}}\leq\Theta(1)$ needs at least $\Omega(n^{\Omega(\log
n)})$ queries or at least one query with precision $o(n^{-c/2})$.

###### Proof.

These corollaries are immediate applications of Theorem 4.1 and Lemma 2.6 from
Goel et al. [2020] to Lemma 33. ∎

It remains to show that the norms of the hard functions in
$\mathcal{H}_{\mathcal{S},\mathcal{F}}$ do not vanish. We show this below for
sign-invariance, almost surely polynomial frames.

######  Lemma 38.

Let $\mathcal{H}_{\mathcal{S},\mathcal{F}}$ be the hard functions derived in
Lemma 33 from the class of hard functions $\mathcal{H}_{\mathcal{S}}$ in Eq.
145 (which comes from Goel et al. [2020], but with an extra input dimension).
Let
$\left\langle\mathbb{E}[f_{S}^{2}]\right\rangle_{\operatorname{Unif}(\mathcal{H}_{\mathcal{S}})}$
denote the average squared norm of functions uniformly drawn from
$\mathcal{H}_{\mathcal{S}}$ and let
$M_{\mathcal{H}_{\mathcal{S},\mathcal{F}}}=\max_{\tilde{f}_{S}\in\mathcal{H}_{\mathcal{S},\mathcal{F}}}\mathbb{E}[\tilde{f}_{S}({\bm{X}})^{2}]$
denote the maximum squared norm of the hard functions in
$\mathcal{H}_{\mathcal{S},\mathcal{F}}$. If
$M_{\mathcal{H}_{\mathcal{S},\mathcal{F}}}/\left\langle\mathbb{E}[f_{S}^{2}]\right\rangle_{\operatorname{Unif}(\mathcal{H}_{\mathcal{S}})}=O(\operatorname{poly}(n))$,
then there exists a constant $c>0$ and subset
$\mathcal{C}\subset\mathcal{H}_{\mathcal{S},\mathcal{F}}$ of size
$|\mathcal{C}|=\Omega(|\mathcal{H}_{\mathcal{S},\mathcal{F}}|/\operatorname{poly}(n))$
many functions whose norms are at least
$c\left\langle\mathbb{E}[f_{S}^{2}]\right\rangle_{\operatorname{Unif}(\mathcal{H}_{\mathcal{S}})}$.

###### Proof.

We use a second moment method argument to prove the above statement. Let the
random variable $Z$ denote the squared norm
$\mathbb{E}[(\tilde{f}_{S}({\bm{X}}))^{2}]$ of a function drawn from the
distribution $\operatorname{Unif}(\mathcal{H}_{\mathcal{S},\mathcal{F}})$
which is uniform over all functions in
$\mathcal{H}_{\mathcal{S},\mathcal{F}}$. The Paley-Zygmund inequality states
that for any given $\theta\in[0,1]$

$\mathbb{P}(Z>\theta\mathbb{E}[Z])\geq(1-\theta)^{2}\frac{\mathbb{E}[Z]^{2}}{\mathbb{E}[Z^{2}]}.$
(165)

The probability above calculates the portion of functions in
$\operatorname{Unif}(\mathcal{H}_{\mathcal{S},\mathcal{F}})$ which have non-
vanishing norm.

Now, we calculate the first two moments of $Z$ over the
$|\mathcal{H}_{\mathcal{S},\mathcal{F}}|={n\choose k}$ functions in the class
where $k=\Theta(\log n)$ as in the construction in Goel et al. [2020]. For the
first moment,

$\displaystyle\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}[Z]$
$\displaystyle=\frac{1}{|\mathcal{H}_{\mathcal{S},\mathcal{F}}|}\sum_{\tilde{f}_{S}\in\mathcal{H}_{\mathcal{S},\mathcal{F}}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}[\tilde{f}_{S}({\bm{X}})^{2}]$
(166) $\displaystyle={n\choose
k}^{-1}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\sum_{S\subseteq_{k}[n]}\frac{1}{|\mathcal{F}({\bm{X}})|}\sum_{g,g^{\prime}\in\mathcal{F}({\bm{X}})}f_{S}(g\cdot{\bm{X}})f_{S}(g^{\prime}\cdot{\bm{X}})\right]$
(167) $\displaystyle={n\choose
k}^{-1}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\frac{1}{|\mathcal{F}({\bm{X}})|}\sum_{S\subseteq_{k}[n]}\left(\sum_{g\in\mathcal{F}({\bm{X}})}f_{S}({\bm{X}})^{2}+\sum_{g\neq
g^{\prime}\in\mathcal{F}({\bm{X}})}f_{S}(g\cdot{\bm{X}})f_{S}(g^{\prime}\cdot{\bm{X}})\right)\right]$
(168) $\displaystyle\geq{n\choose
k}^{-1}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\frac{1}{|\mathcal{F}({\bm{X}})|}\sum_{g\in\mathcal{F}({\bm{X}})}\sum_{S\subseteq_{k}[n]}f_{S}(g\cdot{\bm{X}})^{2}\right]$
$\displaystyle\qquad\qquad-{n\choose
k}^{-1}\left|\sum_{S\subseteq_{k}[n]}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\frac{1}{|\mathcal{F}({\bm{X}})|}\sum_{\begin{subarray}{c}g,g^{\prime}\in\mathcal{F}({\bm{X}})\\\
g^{-1}S\neq(g^{\prime})^{-1}S\end{subarray}}f_{g^{-1}S}({\bm{X}})f_{(g^{\prime})^{-1}S}({\bm{X}})\right]\right|$
(169) $\displaystyle={n\choose
k}^{-1}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\frac{1}{|\mathcal{F}({\bm{X}})|}\sum_{g\in\mathcal{F}({\bm{X}})}\sum_{S\subseteq_{k}[n]}f_{S}(g\cdot{\bm{X}})^{2}\right]$
$\displaystyle\qquad\qquad-{n\choose
k}^{-1}\left|\sum_{S\subseteq_{k}[n]}\sum_{\begin{subarray}{c}g,g^{\prime}\in
G\\\
g^{-1}S\neq(g^{\prime})^{-1}S\end{subarray}}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\frac{\delta_{g,g^{\prime}\in\mathcal{F}({\bm{X}})}}{|\mathcal{F}({\bm{X}})|}f_{g^{-1}S}({\bm{X}})f_{(g^{\prime})^{-1}S}({\bm{X}})\right]\right|,$
(170)

where in the third line, we had the inequality $\geq$ since we ignore $g\neq
g^{\prime}$ such that $g^{-1}S=(g^{\prime})^{-1}S$ (the summands in this case
is $f_{g^{-1}S}({\bm{X}})^{2}\geq 0$ so ignoring them gives a lower bound) and
then use reverse triangle inequality $|a+b|\geq|a|-|b|$.

The first term is

${n\choose
k}^{-1}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\frac{1}{|\mathcal{F}({\bm{X}})|}\sum_{g\in\mathcal{F}({\bm{X}})}\sum_{S\subseteq_{k}[n]}f_{S}(g\cdot{\bm{X}})^{2}\right]={n\choose
k}^{-1}\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\sum_{S\subseteq_{k}[n]}f_{S}({\bm{X}})^{2}\right]=\left\langle\mathbb{E}[f_{S}^{2}]\right\rangle_{\operatorname{Unif}(\mathcal{H}_{\mathcal{S}})}.$
(171)

Now we show that the second term is $0$. For a fix
$S\subset_{k}[n],g,g^{\prime}\in G$ such that $g^{-1}S\neq(g^{\prime})^{-1}S$,
we have:

$\displaystyle\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\frac{\delta_{g,g^{\prime}\in\mathcal{F}({\bm{X}})}}{|\mathcal{F}({\bm{X}})|}f_{g^{-1}S}({\bm{X}})f_{(g^{\prime})^{-1}S}({\bm{X}})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{{\bm{z}}\sim\textup{Unif}(\\{-1,1\\}^{n})}\left[\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\frac{\delta_{g,g^{\prime}\in\mathcal{F}({\bm{X}}\circ{\bm{z}})}}{|\mathcal{F}({\bm{X}}\circ{\bm{z}})|}f_{g^{-1}S}({\bm{X}}\circ{\bm{z}})f_{(g^{\prime})^{-1}S}({\bm{X}}\circ{\bm{z}})\right]\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\frac{\delta_{g,g^{\prime}\in\mathcal{F}({\bm{X}})}}{|\mathcal{F}({\bm{X}})|}f_{g^{-1}S}({\bm{X}})f_{(g^{\prime})^{-1}S}({\bm{X}})\mathbb{E}_{{\bm{z}}}\left[\chi_{g^{-1}S}({\bm{z}})\chi_{(g^{\prime})^{-1}S}({\bm{z}})\right]\right]$
$\displaystyle=$ $\displaystyle 0,$

where we have used the fact that the frame $\mathcal{F}$ is sign-invariant and
the decomposition result from Equation (1) of [Goel et al., 2020]. Thus the
second term is $0$.

For the second moment, we have

$\begin{split}\mathbb{E}[Z^{2}]&=\frac{1}{|\mathcal{H}_{\mathcal{S},\mathcal{F}}|}\sum_{\tilde{f}_{S}\in\mathcal{H}_{\mathcal{S},\mathcal{F}}}\mathbb{E}[\tilde{f}_{S}({\bm{X}})^{2}]^{2}\\\
&\leq\frac{1}{|\mathcal{H}_{\mathcal{S},\mathcal{F}}|}\sum_{\tilde{f}_{S}\in\mathcal{H}_{\mathcal{S},\mathcal{F}}}\max_{\tilde{f}_{S}\in\mathcal{H}_{\mathcal{S},\mathcal{F}}}\mathbb{E}[\tilde{f}_{S}({\bm{X}})^{2}]^{2}\\\
&=M_{\mathcal{H}_{\mathcal{S},\mathcal{F}}}^{2}.\end{split}$ (172)

Thus, applying Paley-Zygmund, we have

$\mathbb{P}\left(Z>\theta\left\langle\mathbb{E}[f_{S}^{2}]\right\rangle_{\operatorname{Unif}(\mathcal{H}_{\mathcal{S}})}\right)\geq(1-\theta)^{2}\frac{\mathbb{E}[Z]^{2}}{\mathbb{E}[Z^{2}]}\geq(1-\theta)^{2}\left\langle\mathbb{E}[f_{S}^{2}]\right\rangle_{\operatorname{Unif}(\mathcal{H}_{\mathcal{S}})}^{2}M_{\mathcal{H}_{\mathcal{S},\mathcal{F}}}^{-2}.$
(173)

Setting $c=(1-\theta)^{2}$ completes the proof. ∎

######  Corollary 39.

Assuming that the activation is ReLU or sigmoid, the subset of non-vanishing
functions in $\mathcal{H}_{\mathcal{S},\mathcal{F}}$ is superpolynomial in
$n$.

###### Proof.

It suffices to show that
$M_{\mathcal{H}_{\mathcal{S},\mathcal{F}}}/\left\langle\mathbb{E}[f_{S}^{2}]\right\rangle_{\operatorname{Unif}(\mathcal{H}_{\mathcal{S}})}$
is $O(\textup{poly}(n))$.

Theorem 3.8 of Goel et al. [2020] guarantees that
$\left\langle\mathbb{E}[f_{S}^{2}]\right\rangle_{\operatorname{Unif}(\mathcal{H}_{\mathcal{S}})}\geq\Omega\left(e^{-\Theta(k)}\right)=\Omega\left(\operatorname{poly}(n)^{-1}\right)$
(since $k=\Theta(\log n)$).

To upper bound $M_{\mathcal{H}_{\mathcal{S},\mathcal{F}}}$, we uniformly
bound, for each $\tilde{f}_{S}\in\mathcal{H}_{\mathcal{S},\mathcal{F}}$,

$\displaystyle\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}[\tilde{f}_{S}({\bm{X}})^{2}]$
$\displaystyle=\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\left(\frac{1}{\sqrt{|\mathcal{F}({\bm{X}})|}}\sum_{g\in\mathcal{F}({\bm{x}})}\sum_{j=1}^{d}\sum_{w\in\\{-1,1\\}^{k}}\chi(w)\sigma\left(\frac{\langle
w,(g\cdot{\bm{X}}_{:,j})_{S}\rangle}{\sqrt{k}}\right)\right)^{2}\right]$ (174)
$\displaystyle\leq\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\sqrt{|\mathcal{F}({\bm{X}})|}2^{k}\sum_{g\in\mathcal{F}({\bm{X}})}\sum_{j=1}^{d}\sum_{w\in\\{-1,1\\}^{k}}\left(\chi(w)\sigma\left(\frac{\langle
w,(g\cdot{\bm{X}}_{:,j})_{S}\rangle}{\sqrt{k}}\right)\right)^{2}\right]$ (175)
$\displaystyle\leq\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\sqrt{|\mathcal{F}({\bm{X}})|}2^{k}\sum_{g\in\mathcal{F}({\bm{X}})}\sum_{j=1}^{d}\sum_{w\in\\{-1,1\\}^{k}}\frac{\left(\langle
w,(g\cdot{\bm{X}}_{:,j})_{S}\rangle\right)^{2}}{k}\right]$ (176)
$\displaystyle\leq\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[\sqrt{|\mathcal{F}({\bm{X}})|}2^{k}\sum_{g\in\mathcal{F}({\bm{X}})}\sum_{j=1}^{d}\sum_{w\in\\{-1,1\\}^{k}}\sum_{s\in
S}(g\cdot{\bm{X}}_{:,j})_{s}^{2}\right]$ (177)
$\displaystyle\leq\mathbb{E}_{{\bm{X}}\sim\mathcal{N}}\left[|\mathcal{F}({\bm{X}})|^{3/2}2^{2k}dk{\bm{x}}_{[1]}^{2}\right]\leq\textup{poly}(n)\mathbb{E}_{{\bm{X}}}[{\bm{x}}_{[1]}^{2}]$
(178)

where ${\bm{x}}_{[1]}$ is the largest entry in absolute value of ${\bm{X}}$.
In the above, we use Cauchy-Schwarz inequality for the second and fourth line,
while the third line uses the fact that $\textup{ReLU}(x)^{2}\leq x^{2}$ for
all $x\in\mathbb{R}$. Since with probability $1$, $|\mathcal{F}({\bm{X}})|$ is
at most polynomial in $n$ by our assumption, it suffices to show that the
order (either largest or smallest) statistic ${\bm{x}}_{[1]}$ has small moment
when ${\bm{X}}$ is a iid Gaussian random vector of length $n\times d$.

Bounding this moment is a classical study in concentration inequalities. By an
inequality of Talagrand [Chatterjee, 2014, Talagrand, 1994], we know that
$\mathbb{E}_{{\bm{x}}}[{\bm{x}}_{[1]}^{2}]-(\mathbb{E}_{{\bm{x}}}[{\bm{x}}_{[1]}])^{2}\leq
C/\log(nd)$ for some constant $C$. The first moment is also bounded by
$O(\sqrt{\log(nd)})$ and thus $\mathbb{E}_{{\bm{x}}}[{\bm{x}}_{[1]}^{2}]\leq
O(\log(nd))$.

Thus $M_{\mathcal{H}_{\mathcal{S},\mathcal{F}}}=O(\operatorname{poly}(n))$ and
our conclusions follow. ∎

###  F.3 Proof of extra tools

######  Lemma 40 (Sub-Gaussian concentration for inner-product with permuted
vector).

Let $G\leq S_{n}$ with at least $2$ elements and fix arbitrary $g\neq
g^{\prime}\in G$. Then for any $c\in(0,1/2)$:

$\Pr_{{\bm{x}}}\left[\left|\frac{\langle
g{\bm{x}},g^{\prime}{\bm{x}}\rangle}{\|{\bm{x}}\|}-\mu_{g,g^{\prime}}\right|\geq\Omega(n^{c})\right]\leq\exp(-\Omega(n^{2c})),$
(179)

for some
$\mu_{g,g^{\prime}}\in\left[\frac{F_{g,g^{\prime}}}{\sqrt{n+1}},\frac{F_{g,g^{\prime}}}{\sqrt{n}}\right]$,
i.e. $\mu_{g,g^{\prime}}=\Theta(F_{g,g^{\prime}}n^{-1/2})$, and where
$F_{g,g^{\prime}}$ is the number of fixed points in $g^{-1}g^{\prime}$ (i.e.
the number of cycles of length $1$ in its cycle representation).

###### Proof.

Let

$f({\bm{x}})=\frac{\langle
g{\bm{x}},g^{\prime}{\bm{x}}\rangle}{\|{\bm{x}}\|},$ (180)

where ${\bm{x}}\sim\mathcal{N}(0,{\bm{I}}_{n})$.

Note that

$\nabla
f({\bm{x}})=\frac{1}{\|{\bm{x}}\|}({\bm{x}}_{h}+{\bm{x}}_{h^{-1}})-\frac{1}{\|{\bm{x}}\|}\frac{\langle
g{\bm{x}},g^{\prime}{\bm{x}}\rangle}{\langle{\bm{x}},{\bm{x}}\rangle}{\bm{x}},$
(181)

where ${\bm{x}}_{h}$ consists of ${\bm{x}}$ with entries reordered by
$h=g^{-1}g^{\prime}$, i.e. $[{\bm{x}}_{h}]_{i}=[{\bm{x}}]_{h^{-1}(i)}$. Via
triangle inequality,

$\|\nabla f({\bm{x}})\|\leq\frac{3}{\|{\bm{x}}\|}\|{\bm{x}}\|\leq 3.$ (182)

Thus, by Gaussian Lipschitz concentration (Lemma 2.2 of [Pisier, 1986]), we
have that:

$\Pr_{{\bm{x}}}\left[\left|\frac{\langle
g{\bm{x}},g^{\prime}{\bm{x}}\rangle}{\|{\bm{x}}\|}-\mathbb{E}f({\bm{x}})\right|\geq\Omega(n^{c})\right]\leq\exp(-\Omega(n^{2c})).$
(183)

Finally, we compute $\mu:=\mathbb{E}_{{\bm{x}}}f({\bm{x}})$. To do this, note
that for every $i\neq j\in[n]$,

$\mathbb{E}_{{\bm{x}}}\frac{{\bm{x}}_{i}{\bm{x}}_{j}}{\|{\bm{x}}\|_{2}}=\mathbb{E}_{{\bm{x}}}\frac{(-{\bm{x}}_{i}){\bm{x}}_{j}}{\|{\bm{x}}\|_{2}}=0,$
(184)

by a change of variable formula
${\bm{x}}\mapsto({\bm{x}}_{1},\ldots,{\bm{x}}_{i-1},-{\bm{x}}_{i},{\bm{x}}_{i+1},\ldots,{\bm{x}}_{n})$.
∎

At the same time, for every $i\neq j\in[n]$,

$\mathbb{E}_{{\bm{x}}}\frac{{\bm{x}}_{i}^{2}}{\|{\bm{x}}\|_{2}}=\mathbb{E}_{{\bm{x}}}\frac{{\bm{x}}_{j}^{2}}{\|{\bm{x}}\|_{2}}=\frac{1}{n}\sum_{k=1}^{n}\mathbb{E}_{{\bm{x}}}\frac{{\bm{x}}_{k}^{2}}{\|{\bm{x}}\|_{2}}=\frac{1}{n}\mathbb{E}_{{\bm{x}}}\|{\bm{x}}\|_{2},$
(185)

by a change of variable that swaps ${\bm{x}}_{i}$ and ${\bm{x}}_{j}$ using a
permutation Jacobian matrix with determinant $\pm 1$.

Thus $\mu=\frac{F_{g,g^{\prime}}}{n}\mathbb{E}_{{\bm{x}}}\|{\bm{x}}\|_{2}$,
where $F_{g,g^{\prime}}$ is the number of fixed points of $g^{-1}g^{\prime}$.
We appeal to elementary analysis of Gaussian vectors (for instance,
Chandrasekaran et al. [2012]) to obtain:

$\mathbb{E}_{{\bm{x}}}\|{\bm{x}}\|_{2}=\sqrt{2}\frac{\Gamma((n+1)/2)}{\Gamma(n/2)}\in[n/\sqrt{n+1},\sqrt{n}],$
(186)

where $\Gamma$ is Euler’s Gamma function. Thus, we have

$\mu\in\left[\frac{F_{g,g^{\prime}}}{\sqrt{n+1}},\frac{F_{g,g^{\prime}}}{\sqrt{n}}\right]$
(187)

######  Lemma 41.

Let ${\bm{x}}\in\mathbb{R}^{n}$ be a unit vector iid uniformly distributed
over the $n$-dimensional unit sphere. Let $G\leq S_{n}$ and $g\neq
g^{\prime}\in G$. Let $F_{g,g}$ be the number of fixed points of
$h:=g^{-1}g^{\prime}$’s action on $[n]$. Then for all $c\in(0,1/2)$ and small
${\epsilon}\in(0,1)$:

$\displaystyle\Pr_{{\bm{x}}}\left[\langle
g{\bm{x}},g^{\prime}{\bm{x}}\rangle-\frac{F_{g,g^{\prime}}}{n\sqrt{1-{\epsilon}}}\geq\Omega(n^{c-1/2})\right]\leq\exp(-\Omega(n^{2c})),$
(188) $\displaystyle\Pr_{{\bm{x}}}\left[\langle
g{\bm{x}},g^{\prime}{\bm{x}}\rangle-\sqrt{1-{\epsilon}}\frac{F_{g,g^{\prime}}}{n}\leq-\Omega(n^{c-1/2})\right]\leq\exp(-\Omega(n^{2c})).$
(189)

###### Proof.

Recall that an alternative way to sample unit vectors i.i.d. uniformly from
the hypersphere is to first sample ${\bm{z}}\sim\mathcal{N}(0,I_{n})$ and then
set ${\bm{x}}:=\frac{{\bm{z}}}{\|{\bm{z}}\|_{2}}$. Thus, we study
$\frac{\langle g{\bm{z}},g^{\prime}{\bm{z}}\rangle}{\|{\bm{z}}\|_{2}^{2}}$.

To do this, note that concentration of $\|{\bm{z}}\|_{2}$ is well studied
(Proposition 2.2 and Corollary 2.3 of Barvinok [2005]), for any
$0<{\epsilon}<1$:

$\displaystyle\max\left(\Pr_{{\bm{z}}}\left(\|{\bm{z}}\|_{2}\geq\sqrt{\frac{n}{1-{\epsilon}}}\right),\Pr_{{\bm{z}}}\left(\|{\bm{z}}\|_{2}\leq\sqrt{(1-{\epsilon})n}\right)\right)$
$\displaystyle\leq\exp(-{\epsilon}^{2}n/4).$ (190)

Concentration of the random variable $\langle
g{\bm{z}},g^{\prime}{\bm{z}}\rangle/\|{\bm{z}}\|_{2}$ was studied in Lemma 40
as:

$\Pr_{{\bm{z}}\sim\mathcal{N}^{n}}\left[|\langle
g{\bm{z}},g^{\prime}{\bm{z}}\rangle/\|{\bm{z}}\|_{2}-\mu_{g,g^{\prime}}|\geq\Omega(n^{c+1/2})\right]\leq\exp(-\Omega(n^{2c})),$
(191)

for some
$\mu_{g,g^{\prime}}\in[F_{g,g^{\prime}}/\sqrt{n+1},F_{g,g^{\prime}}/\sqrt{n}]$.
Since $\frac{1}{\sqrt{n}}-\frac{1}{\sqrt{n+1}}\in O(n^{-3/2})$ and
$F_{g,g^{\prime}}\leq n$, we can also write:

$\Pr_{{\bm{x}}}\left[\frac{\langle
g{\bm{x}},g^{\prime}{\bm{x}}\rangle}{\|{\bm{x}}\|}-\frac{F_{g,g^{\prime}}}{\sqrt{n}}\geq\Omega(n^{c})\right]\leq\exp(-\Omega(n^{2c})),$
(192)

and

$\Pr_{{\bm{x}}}\left[\frac{\langle
g{\bm{x}},g^{\prime}{\bm{x}}\rangle}{\|{\bm{x}}\|}-\frac{F_{g,g^{\prime}}}{\sqrt{n}}\leq-\Omega(n^{c})\right]\leq\exp(-\Omega(n^{2c})).$
(193)

We have by union bound:

$\displaystyle\Pr\left[\frac{\langle
g{\bm{z}},g^{\prime}{\bm{z}}\rangle}{\|{\bm{z}}\|_{2}^{2}}-\frac{F_{g,g^{\prime}}}{n\sqrt{1-{\epsilon}}}>\Omega(n^{c-1/2})\right]$
$\displaystyle\leq\Pr\left[\frac{\langle
g{\bm{z}},g^{\prime}{\bm{z}}\rangle}{\|{\bm{z}}\|_{2}}>\frac{F_{g,g^{\prime}}}{\sqrt{n}}+\Omega(n^{c})\right]+\Pr[\|{\bm{z}}\|_{2}<\sqrt{(1-{\epsilon})n}]$
(194) $\displaystyle\leq\exp(-\Omega(n^{2c}))+\exp(-{\epsilon}^{2}n/4)$ (195)
$\displaystyle\leq\exp(-\Omega(n^{2c})).$ (196)

On the other side,

$\displaystyle\Pr\left[\frac{\langle
g{\bm{z}},g^{\prime}{\bm{z}}\rangle}{\|{\bm{z}}\|_{2}^{2}}-\sqrt{1-{\epsilon}}\frac{F_{g,g^{\prime}}}{n}<-\Omega(n^{c-1/2})\right]$
$\displaystyle\leq\Pr\left[\frac{\langle
g{\bm{z}},g^{\prime}{\bm{z}}\rangle}{\|{\bm{z}}\|_{2}}<\frac{F_{g,g^{\prime}}}{\sqrt{n}}-\Omega(n^{c})\right]+\Pr\left[\|{\bm{z}}\|_{2}>\sqrt{\frac{n}{1-{\epsilon}}}\right]$
(197) $\displaystyle\leq\exp(-\Omega(n^{2c}))+\exp(-{\epsilon}^{2}n/4)$ (198)
$\displaystyle\leq\exp(-\Omega(n^{2c})).$ (199)

∎

######  Lemma 42 (Kronecker product of PSD matrices is PSD).

For some $m,n\in\mathbb{N}$. Fix ${\bm{A}}\in\mathbb{R}^{m\times m}$ and
${\bm{B}}\in\mathbb{R}^{n\times n}$ not necessarily symmetric. If for all
${\bm{x}}\in\mathbb{R}^{m},{\bm{x}}^{\top}{\bm{A}}{\bm{x}}\geq 0$ and for all
${\bm{y}}\in\mathbb{R}^{n},{\bm{y}}^{\top}{\bm{B}}{\bm{y}}\geq 0$ then for all
${\bm{z}}\in\mathbb{R}^{mn},{\bm{z}}^{\top}({\bm{A}}\otimes{\bm{B}}){\bm{z}}\geq
0$, where $\otimes$ is the Kronecker product.

###### Proof.

Write ${\bm{z}}=({\bm{z}}^{[1]},\ldots,{\bm{z}}^{[m]})$ where
${\bm{z}}^{[i]}\in\mathbb{R}^{n}$ for each $i\in[m]$, then we have:

$\displaystyle{\bm{z}}^{\top}({\bm{A}}\otimes{\bm{B}}){\bm{z}}$
$\displaystyle=\sum_{i,i^{\prime}=1}^{m}\sum_{j,j^{\prime}=1}^{n}{\bm{z}}^{[i]}_{j}({\bm{A}}_{i,i^{\prime}}{\bm{B}}_{j,j^{\prime}}){\bm{z}}^{[i^{\prime}]}_{j^{\prime}}$
(200)
$\displaystyle=\sum_{i,i^{\prime}=1}^{m}{\bm{A}}_{i,i^{\prime}}\sum_{j,j^{\prime}=1}^{n}{\bm{z}}^{[i]}_{j}{\bm{B}}_{j,j^{\prime}}{\bm{z}}^{[i^{\prime}]}_{j^{\prime}}$
(201)
$\displaystyle=\sum_{i,i^{\prime}=1}^{m}{\bm{A}}_{i,i^{\prime}}{\bm{C}}_{i,i^{\prime}},$
(202)

where
${\bm{C}}_{i,i^{\prime}}=\sum_{j,j^{\prime}=1}^{n}{\bm{z}}^{[i]}_{j}{\bm{B}}_{j,j^{\prime}}{\bm{z}}^{[i^{\prime}]}_{j^{\prime}}$.
Now it is not hard to see that ${\bm{C}}$ is symmetric. At the same time, for
any ${\bm{w}}\in\mathbb{R}^{m}$,

$\displaystyle{\bm{w}}^{\top}{\bm{C}}{\bm{w}}$
$\displaystyle=\sum_{i,i^{\prime}=1}^{n}{\bm{w}}_{i}{\bm{w}}_{i^{\prime}}\sum_{j,j^{\prime}=1}^{n}{\bm{z}}^{[i]}_{j}{\bm{B}}_{j,j^{\prime}}{\bm{z}}^{[i^{\prime}]}_{j^{\prime}}=\sum_{i,i^{\prime}=1}^{n}\sum_{j,j^{\prime}=1}^{n}({\bm{w}}_{i}{\bm{z}}^{[i]}_{j}){\bm{B}}_{j,j^{\prime}}({\bm{w}}_{i^{\prime}}{\bm{z}}^{[i^{\prime}]}_{j^{\prime}}).$
(203)

By property of ${\bm{B}}$, the inner sum is nonnegative and thus
${\bm{w}}^{\top}{\bm{C}}{\bm{w}}$ is nonnegative. Therefore we conclude that
${\bm{C}}$ is symmetric positive semi-definite and thus admits a spectral
decomposition:

${\bm{C}}=\sum_{k=1}^{r}\lambda_{k}{\bm{v}}^{[k]}({\bm{v}}^{[k]})^{\top},$
(204)

for some set of vectors ${\bm{v}}^{[k]}$ and nonnegative $\lambda_{k}\geq 0$,
$k\in[r]$ for some $r$.

Thus,

$\displaystyle\sum_{i,i^{\prime}=1}^{m}{\bm{A}}_{i,i^{\prime}}{\bm{C}}_{i,i^{\prime}}=\sum_{i,i^{\prime}=1}^{m}{\bm{A}}_{i,i^{\prime}}\sum_{k=1}^{r}\lambda_{k}{\bm{v}}^{[k]}_{i}{\bm{v}}^{[k]}_{i^{\prime}}=\sum_{i,i^{\prime}=1}^{m}\sum_{k=1}^{r}\lambda_{k}{\bm{v}}^{[k]}_{i}{\bm{A}}_{i,i^{\prime}}{\bm{v}}^{[k]}_{i^{\prime}}.$
(205)

By property of ${\bm{A}}$ and the fact that $\lambda_{k}$ are nonnegative, the
inner sum is nonnegative and we get our conclusion. ∎

######  Corollary 43 (PSD of tensor power).

For any $m,n\in\mathbb{N}$, if ${\bm{A}}\in\mathbb{R}^{m\times m}$ is such
that ${\bm{x}}^{\top}{\bm{A}}{\bm{x}}>0$ for all ${\bm{x}}\in\mathbb{R}^{m}$,
then ${\bm{A}}^{\otimes n}$ satisfies: ${\bm{z}}^{\top}{\bm{A}}^{\otimes
n}{\bm{z}}>0$ for all ${\bm{z}}\in\mathbb{R}^{m^{n}}$

###### Proof.

Apply Lemma 42 $n-1$ times. ∎

###### Proof of Lemma 29.

We use Corollary D.3 from [Diakonikolas et al., 2017] copied below:

######  Lemma 44 (Corollary D.3 from [Diakonikolas et al., 2017]).

Let ${\bm{x}},{\bm{y}}\in\mathbb{R}^{n}$ be two unit vectors iid uniformly
distributed over the $n$-dimensional unit sphere. Then:

$\Pr_{{\bm{x}},{\bm{y}}}[|\langle{\bm{x}},{\bm{y}}\rangle|\geq\Omega(n^{c-1/2})]\leq\exp(-\Omega(n^{2c})),$
(206)

for any $c\in(0,1/2)$.

Let $g,g^{\prime}\in F$ be two arbitrary permutations that act on
$\mathbb{R}^{n}$ by permuting the vector. Since the uniform distribution over
the $n$-dimenional unit sphere is invariant to permutation of the indices, its
pushforward via $g$ and $g^{\prime}$ is still uniform. Therefore, we have, for
any $g,g^{\prime}\in F$:

$\Pr_{{\bm{x}},{\bm{y}}}[|\langle
g{\bm{x}},g^{\prime}{\bm{y}}\rangle|\geq\Omega(n^{c-1/2})]\leq\exp(-\Omega(n^{2c})).$
(207)

Draw $T=2^{\Omega(n^{c})}/|F|^{2}$ such iid vectors to form a set
$S\subset\mathbb{R}^{n}$. We have, by union bound:

$\displaystyle\Pr_{{\bm{x}}_{1},\ldots,{\bm{x}}_{T}}[\exists i\neq
j\in[T],\exists g,g^{\prime}\in F,|\langle
g{\bm{x}}_{i},g^{\prime}{\bm{x}}_{j}\rangle|\geq\Omega(n^{c-1/2})]$ (208)
$\displaystyle\leq$ $\displaystyle\sum_{i,j\in[T]}\sum_{g,g^{\prime}\in
F}\Pr_{{\bm{x}}_{i},{\bm{x}}_{j}}[|\langle
g{\bm{x}}_{i},g^{\prime}{\bm{x}}_{j}\rangle|\geq\Omega(n^{c-1/2})]$ (209)
$\displaystyle\leq$ $\displaystyle 2^{\Omega(n^{c})}\exp(-\Omega(n^{2c}))$
(210) $\displaystyle\leq$ $\displaystyle\exp(-\Omega(n^{2c})).$ (211)

On the other hand, let $F_{g,g^{\prime}}$ be the number of fixed points of
$g^{-1}g^{\prime}$ for some $g\neq g^{\prime}\in F$, we also want to union
bound using Lemma 41, for any small constant ${\epsilon}\in(0,1)$:

$\displaystyle\Pr_{{\bm{x}}_{1},\ldots,{\bm{x}}_{T}}\left[\exists
i\in[T],\exists g\neq g^{\prime}\in F,\langle
g{\bm{x}}_{i},g^{\prime}{\bm{x}}_{i}\rangle-\frac{F_{g,g^{\prime}}}{n\sqrt{1-{\epsilon}}}\geq\Omega(n^{c-1/2})\right]$
(212) $\displaystyle\leq$ $\displaystyle\sum_{i\in[T]}\sum_{g\neq
g^{\prime}\in F}\Pr_{{\bm{x}}_{i}}\left[\langle
g{\bm{x}}_{i},g^{\prime}{\bm{x}}_{i}\rangle-\frac{F_{g,g^{\prime}}}{n\sqrt{1-{\epsilon}}}\geq\Omega(n^{c-1/2})\right]\geq\Omega(n^{c-1/2})]$
(213) $\displaystyle\leq$ $\displaystyle 3\cdot
2^{\Omega(n^{c})}\exp(-\Omega(n^{2c}))$ (214) $\displaystyle\leq$
$\displaystyle\exp(-\Omega(n^{2c})).$ (215)

Similarly,

$\displaystyle\Pr_{{\bm{x}}_{1},\ldots,{\bm{x}}_{T}}\left[\exists
i\in[T],\exists g\neq g^{\prime}\in F,\langle
g{\bm{x}}_{i},g^{\prime}{\bm{x}}_{i}\rangle-\sqrt{1-{\epsilon}}\frac{F_{g,g^{\prime}}}{n}\leq-\Omega(n^{c-1/2})\right]\leq\exp(-\Omega(n^{2c}))$
(216)

Therefore, for every small ${\epsilon}\in(0,1)$, there exists a set
$S\subset\mathbb{R}^{n}$ of size $T=2^{\Omega(n^{c})}/|F|^{2}$ such that for
every ${\bm{x}}\neq{\bm{y}}\in S$, for every $g\neq g^{\prime}\in F$, we have:

$\displaystyle\|g{\bm{x}}\|_{2}$ $\displaystyle=1$ (217)
$\displaystyle\max(|\langle g{\bm{x}},g{\bm{y}}\rangle|,|\langle
g{\bm{x}},g^{\prime}{\bm{y}}\rangle|)$ $\displaystyle\leq O(n^{c-1/2}),$ (218)
$\displaystyle\langle
g{\bm{x}}_{i},g^{\prime}{\bm{x}}_{i}\rangle-\frac{F_{g,g^{\prime}}}{n\sqrt{1-{\epsilon}}}$
$\displaystyle\leq O(n^{c-1/2}),$ (219) $\displaystyle\langle
g{\bm{x}}_{i},g^{\prime}{\bm{x}}_{i}\rangle-\sqrt{1-{\epsilon}}\frac{F_{g,g^{\prime}}}{n}$
$\displaystyle\geq-O(n^{c-1/2}).$ (220)

Pair elements of $S$ (as column vectors) together arbitrarily to obtain a set
$\mathcal{B}^{\prime}$ of matrices in $\mathbb{R}^{n\times 2}$ of size $T/2$.
Each element of $\mathcal{B}^{\prime}$ has two columns, each one of these
columns is a _distinct_ vector in $S$. We have, for any
${\bm{B}}=:({\bm{x}}_{1,1},{\bm{x}}_{1,2}),{\bm{B}}^{\prime}=:({\bm{x}}_{2,1},{\bm{x}}_{2,2})\in\mathcal{B}^{\prime}$,
and for any $g,g^{\prime}\in F$,

$\|(g{\bm{B}})^{\top}(g^{\prime}{\bm{B}}^{\prime})\|_{2}\leq\|(g{\bm{B}})(g^{\prime}{\bm{B}}^{\prime})^{\top}\|_{F}=\sqrt{\sum_{i,j\in[2]}(\langle
g{\bm{x}}_{1i},g^{\prime}{\bm{x}}_{2j}\rangle)^{2}}\leq O(n^{c-1/2}).$ (221)

The remaining conditions in Lemma 29 are also straightforward to check. ∎

##  Appendix G Learning invariant polynomials

Here, we aim to extend the algorithm of Andoni et al. [2014] to the setting of
invariant polynomials. This algorithm is an SQ algorithm, but not a CSQ
algorithm.

First, let us review the GROWING-BASIS algorithm. Assume inputs
${\bm{x}}\in\mathbb{R}^{n}$ are distributed according to some product
distribution $\mathcal{D}=\mu_{1}\times\cdots\times\mu_{n}$. The goal of the
algorithm is to learn the coefficients of some polynomial
$f^{*}({\bm{x}})=\sum_{S}a_{S}H_{S}({\bm{x}})$ where
$S=(S_{1},S_{2},\dots,S_{n})$ is a tuple of positive integers which indicate
the degree of the polynomial in the $i$-th variable. The monomials in the
polynomial take the form

$f^{*}({\bm{x}})=\sum_{S}a_{S}H_{S}({\bm{x}}),\text{ where
}H_{S}({\bm{x}})=\prod_{i=1}^{n}H_{S_{i}}({\bm{x}}_{i}),$ (222)

where $H_{S_{i}}$ is the $S_{i}$-th degree polynomial in an class of
polynomials orthogonal under the distribution $\mathcal{D}$: $\langle
H_{i},H_{j}\rangle=\int H_{i}(x)H_{j}(x)\mu_{i}(x)dx=0$ for all $i\neq j$. An
example of such an orthogonal set of polynomials are the Legendre polynomials
which are orthogonal under the uniform distribution over $[-1,1]$.

Next, to rigorously obtain a separation on invariant function classes, we need
to define a few objects. We will often simplify notation or definitions for
ease of readability; the presentation of this material in its full
mathematical rigor can be found in various textbooks, e.g. Derksen and Kemper
[2015].

#### Independent generators

Let $g_{1},\ldots,g_{r}$ be invariant functions and K a field, either
$\mathbb{R}$ or $\mathbb{C}$. The ring of polynomial
$\textup{K}[g_{1},\ldots,g_{r}]$ is the set of all sums
$\sum_{\alpha\in\mathbb{N}^{r}}c_{\alpha}g^{\alpha}$ where
$g^{\alpha}=\prod_{i=1}^{r}g_{i}^{\alpha_{i}}$. Assume that
$\\{g_{i}\\}_{i=1}^{r}$ are independent in the sense that for all $i\in[r]$,
there is no polynomial
$P\in\textup{K}[g_{1},\ldots,g_{i-1},g_{i+1},\ldots,g_{r}]$ that agrees with
$g_{i}$ as a function $\textup{K}^{n}\to\textup{K}$. It is not hard to see
that if a member of $\textup{K}[g_{1},\ldots,g_{r}]$ can be evaluated as a
function $\textup{K}^{n}\to\textup{K}$ then they are also invariant functions.
The converse is not true, in general, as some invariant functions may not be
written as polynomials over certain generators. However, some special groups
have nice, finitely many generators whose polynomial ring spans almost the
whole space of invariant functions. Denote by
$\mathcal{F}^{d,r}:=\textup{K}[g_{1},\ldots,g_{r}]^{\leq d}$ the set of all
polynomials in $g_{i}$’s with degree at most $d$, i.e.,
$\sum_{\alpha\in\mathbb{N}^{r}|\sum_{i}\alpha_{i}\leq d}c_{\alpha}g^{\alpha}$.

#### Vector space of bounded degree polynomials generated by a finite set

A different way of thinking about $\mathcal{F}^{d,r}$ is as a vector space.
Let $V^{d}(g_{1},\ldots,g_{r})$ be the $(r+1)^{d}$-dimensional vector space
over the field $k$, whose canonical basis is the set
$\\{e_{I}\\}_{I\in(\\{0\\}\cup[r])^{d}}$. It is not hard to show that
$V^{d}(g_{1},\ldots,g_{r})$ is isomorphic to
$\textup{K}[g_{1},\ldots,g_{r}]^{\leq d}$ by identifying $e_{I}$ to the
monomial $\prod_{i=1}^{d}g_{I_{i}}$ where $g_{0}\equiv 1$. This perspective as
a vector space allows for a nice calculus tool: let $\mathbb{P}$ be a product
distribution over $\textup{K}^{r}$ (tuples of length $r$, with each entry an
element in K) and $\langle f,g\rangle_{\mathbb{P}}:=\int
f\bar{g}\textup{d}\mathbb{P}$. Here, we once again think of $g_{i}$’s as
functions $\textup{K}^{n}\to\textup{K}$ and so are elements in
$\mathcal{F}^{d,r}$. Applying Gram-Schmidt orthogonalization to basis elements
of $V^{d}(g_{1},\ldots,g_{r})$ generates another set of orthogonal (in
$\langle\cdot,\cdot\rangle_{\mathbb{P}}$) elements $H_{1},\ldots
H_{(r+1)^{d}}$.555We also note that it is technically more efficient to apply
this procedure to each of the generators individually. That is, apply Gram-
Schmidt to the space $[1,g_{i},\dots,g_{i}^{d}]$. Since there is a product
distribution, this procedure constructs orthogonal polynomials in each basis
which can then be combined to construct orthogonal polynomials in
$\textup{K}[g_{1},\ldots,g_{r}]$. Note that there are still $(r+1)^{d}$ such
orthogonal functions since Gram-Schmidt preserves dimensionality of the input
and ouput vector spaces. This process in analogous to that constructing the
Hermite and Legendre polynomials for Gaussian in uniform distributions
respectively. When $\mathbb{P}$ is a product distribution, we can reindex this
basis as $\\{H_{{\bm{v}}}\\}_{{\bm{v}}\in(\\{0\\}\cup[r])^{d}}$.

#### Sparse polynomial

Before giving any formal results, we must state some technical preliminary
restrictions that must be set for learning to be possible. Our learning
setting restricts $\mathcal{F}^{d,r}$ to only contain polynomials in
$g_{1},\ldots,g_{r}$ with at most $k$ terms in the expansion using
$\\{H_{{\bm{v}}}\\}_{{\bm{v}}\in(\\{0\\}\cup[r])^{d}}$. In other words, when
viewed as vectors in $V^{d}(g_{1},\ldots,g_{r})$ under the basis
$\\{H_{{\bm{v}}}\\}_{{\bm{v}}\in(\\{0\\}\cup[r])^{d}}$, only $k$ elements are
non-zero. Call this new set $\mathcal{F}^{d,r,k}$.

We should also note that for technical reasons, we restrict the outputs of the
polynomials to be normalized within some bounded range to properly normalize
the function with respect to the error metric and allow for the SQ query
bounds to also properly query such functions. In the GROWING-BASIS algorithm,
one must make queries to estimate $\langle H_{{\bm{v}}},f^{*}\rangle$ and
$\langle H_{{\bm{v}}},(f^{*})^{2}\rangle$. Given any statistical query
function has output bounded in the range $[-1,+1]$, to measure the
correlations, we must choose a query function that divides by the maximum
value of $|H_{{\bm{v}}}(f^{*})^{2}|$ in some high probability region
$D\subseteq\textup{K}^{r}$ with measure $\mathbb{{P}}(D)\geq 1-o(1)$ and
outputs zero elsewhere. This way, statistical query functions whose outputs
are bounded in the range $[-1,+1]$ can effectively calculate the proper
correlations needed in the algorithm.666We note that there are likely more
effective means of handling this normalization requirement, by e.g., composing
multiple queries together to calculate the relevant quantities. However, we do
not consider this strengthening here for sake of simplicity. Thus, we
introduce a normalization term $\hat{M}_{d,k}=\max_{{\bm{x}}\in
D,{\bm{v}}\in(\\{0\\}\cup[r])^{d}}|H_{{\bm{v}}}(f^{*})^{2}|$ and introduce
this quantity into the query tolerance to allow for proper estimation of
relevant variables. This normalization plays a similar role to the quantity
$M_{d,k}$ in Andoni et al. [2014] for their guarantees of sampling complexity.
When the target function $f^{*}$ is properly bounded, it is not too hard to
see that this quantity is also easily bounded. For example, when
$|f^{*}|=O(1)$ in the range $[-1,+1]^{n}$, $\hat{M}_{d,k}$ is at most a
constant for inputs drawn from the uniform distribution over the interval
$[-1,+1]$ since the Legendre polynomials are also appropriately bounded. In
general, functions can always be normalized by dividing by an appropriate
constant.

Finally, the GROWING-BASIS algorithm depends on a parameter $\tau_{d}$ that
controls how much higher order terms show up in the square of a polynomial.
More formally, let $H_{i}:\textup{K}\to\textup{K}$ denote the $i$-th
orthogonal polynomial for some given distribution on K. For any such
orthogonal polynomial, we have the decomposition (see equation 2.1 of Andoni
et al. [2014])

$H_{t}(x)=1+\sum_{j=1}^{2t}c_{t,j}H_{j}(x).$ (223)

Let $c_{t}=c_{t,2t}$, then $\tau_{d}=\min_{t\leq d}c_{t}$. This quantity is
generally bounded for common distributions, e.g., when $H_{t}$ are the Hermite
or Legendre polynomials then $\tau_{d}=\Omega(1)$ [Andoni et al., 2014].

With this set up, we are ready to state and prove our main result for this
section:

######  Theorem 45 (Adapted from theorems 2.1 and 2.2 of Andoni et al.
[2014]).

Let K be a field, $g_{1},\ldots,g_{r}$ be independent functions
$\textup{K}^{n}\to\textup{K}$ that are invariant to a group $G$ acting
algebraically on $\textup{K}[g_{1},\ldots,g_{r}]$ as defined above. Let
$\mathbb{P}$ be a product distribution and define the inner product $\langle
p,q\rangle_{\mathbb{P}}:=\mathbb{E}_{{\bm{g}}:=(g_{1},\ldots,g_{r})\sim\mathbb{P}}[p({\bm{g}})\overline{q({\bm{g}})}]$.
Let $\\{H_{{\bm{v}}}\\}_{{\bm{v}}\in(\\{0\\}\cup[r])^{d}}$ be the output of
Gram-Schmidt on $\mathcal{F}^{d,r}$ with respect to this inner product.
Further assume that the polynomial quotient
$H_{2m,0,\ldots,0}/(H_{m,0,\ldots,0})^{2}$ (ignoring remainders) is $\tau_{d}$
for every $m\in[\lfloor d/2\rfloor]$. Let $\mathcal{F}^{d,r,k}$ be the space
of polynomials in $\mathcal{F}^{d,r}$ that is k sparse in $H_{i}$ basis. Then
any CSQ algorithm with oracle access to
$\langle\cdot,f^{*}\rangle_{\mathbb{P}}$ for some
$f^{*}\in\mathcal{F}^{d,r,k}$ that outputs a hypothesis
$h\in\mathcal{F}^{d,r,k}$ while achieving mean square error
$\|h-f^{*}\|_{\mathbb{P}}<O(1)$ must make either at least $(r+1)^{d}$ calls to
the oracle or require precision less than $O(r^{-c})$ for any $c>0$. However,
GROWING-BASIS can learn $h$ with error $\|h-f^{*}\|_{\mathbb{P}}<O(1)$ using
only $O(krd(1/\tau_{d})^{d})$ calls to oracles
$\langle\cdot,f^{*}\rangle_{\mathbb{P}}$ and
$\langle\cdot,(f^{*})^{2}\rangle_{\mathbb{P}}$ with precision
$\Omega(\tau_{d}^{d}/(krd\hat{M}_{d,k}))$.

###### Proof.

The CSQ lower bound can be obtained by invoking standard correlational
statistical queries dimension bound form orthogonal polynomials [Diakonikolas
et al., 2020, Goel et al., 2020, Reyzin, 2020, Szörényi, 2009]. Specifically,
by correctness of Gram-Schmidt orthonormalization, the set of basis elements
$\\{H_{{\bm{v}}}\\}_{{\bm{v}}\in(\\{0\\}\cup[r])^{d}}$ also form a pairwise
orthogonal set, which each themselves have norm $1$ under $\langle
p,q\rangle_{\mathbb{P}}$. thus CSQ dimension of $f^{*}\in\mathcal{F}^{d,r,k}$
is immediately lower bounded by $\Omega(r^{d})$ and the conclusion for CSQ
algorithms follow.

The SQ upper bound via GROWING-BASIS can be obtained by observing that Andoni
et al. [2014]’s proof still works verbatim when the main ingredients are
there: a product distribution, an inner product with an orthornormal basis,
and access to oracle $\langle\cdot,(f^{*})^{2}\rangle_{\mathbb{P}}$. Note that
although the GROWING-BASIS algorithm is presented error free, we allow small
errors, by making a thresholding in Step 2 and 8 of Andoni et al. [2014] equal
to the error tolerance ${\epsilon}$. This way, we are guaranteed to miss only
terms with low correlation and thus bounded effect on the final mean square
error. To be more precise, every time we made an error on the cutoff of step
8, we lose as most a fraction of the precision that amounts to $\tau_{d}^{d}$
where as stated before $\tau_{d}$ is the coefficient of $H_{2n,0,\ldots,0}$ in
$(H_{n,0,\ldots,0})^{2}$. Intuitively, when losing a monomial in the final
product, the norm of the monomial can multiplicatively compound over each
variable. $\tau_{d}$ is the lowest possible amount each variable can
contribute to this loss (See [Andoni et al., 2014], Lemma 2.3). Finally, we
also must divide the query tolerance by a factor $\hat{M}_{d,k}$ to account
for the normalization of the target function as discussed earlier. ∎

######  Corollary 46.

In the same setting as Theorem 45, if instead, we are interested in
polynomials that are $k$-sparse in the canonical basis
$\\{\prod_{i=1}^{r}g_{i}^{\alpha_{i}}|\sum_{i}\alpha_{i}=1\\}$ (recall that
$\mathcal{F}^{d,r,k}$ was sparse in the orthogonal basis
$\\{H_{{\bm{v}}}\\}_{{\bm{v}}\in(\\{0\\}\cup[r])^{d}}$). Then the query
complexity of GROWING-BASIS becomes at most $O(krd2^{d})$ with precision
$\Omega(1/(krd2^{d}))$ whenever $\tau_{d}=\Omega(1)$ and targets are
normalized so that $\hat{M}_{d,k}=O(1)$.

###### Proof.

By the same argument as Lemma 2.1 of [Andoni et al., 2014], any change of
basis in the vector space of polynomials of bounded degree incur at worst a
multiplicative factor $2^{d}$ in the sparsity parameter. Since the new
function class is $k$-sparse in the canonical basis, it is $k2^{d}$-sparse in
the orthogonal basis. Apply Theorem 45 to this new sparsity level to get the
desired result. ∎

This separation is weaker than when there is sparsity in the orthogonal basis.
However, there is still a polynomial (in $r$) separation between CSQ and SQ if
$d$ and $k$ are set to be constant independent of $r$ and a superpolynomial
separation when $d=\Theta(\log(n))$.

Finally, for the above theorem to give a meaningful separation, we list some
example groups for which there is a simple distribution $\mathcal{D}$ over
inputs such that the push-forward distribution
$\mathbb{P}=\phi_{\\#}\mathcal{D}$ via the map
$\phi:{\bm{x}}:=(x_{1},\ldots,x_{n})\mapsto(g_{1}({\bm{x}}),\ldots
g_{r}({\bm{x}}))$ is a product distribution.

######  Example 5.

Consider inputs ${\bm{X}}\in\mathbb{R}^{n\times 3}$ which correspond to $n$
points in $\mathbb{R}^{3}$. Ordered point clouds are symmetric under the
action ${\bm{X}}\cdot{\bm{U}}$ for matrix ${\bm{U}}\in O(3)$ in the orthogonal
group. Let inputs ${\bm{X}}$ have entries drawn i.i.d. Gaussian. Consider
generators $g_{1},\dots,g_{n}$ where $g_{i}({\bm{x}})=\|{\bm{X}}_{i,:}\|^{2}$,
which is the sum of the squares of the $i$-th row of ${\bm{X}}$ and clearly
invariant to orthogonal transformations. The pushforward distribution after
the mapping ${\bm{X}}\mapsto[g_{1}({\bm{X}}),\dots,g_{n}({\bm{X}})]$ is a
product distribution over Chi-squared random variables $\chi^{2}(3)^{n}$.

######  Example 6.

Consider inputs ${\bm{x}}\in\mathbb{C}^{n}$ drawn from
$U[\mathbb{C}\cap\\{|z|=1\\}]^{n}$ uniformly from unit norm complex numbers in
each entry. The power sum symmetric polynomials consist of a generating basis
$\left[\sum_{i}{\bm{x}}_{i},...,\sum_{i}{\bm{x}}_{i}^{d}\right]$. Another way
to parameterize each ${\bm{x}}_{j}$ is as ${\bm{x}}_{j}=e^{i\theta}$ where
$\theta$ is distributed $U[0,2\pi]$, for all $j\in[n]$. Thus
${\bm{x}}_{j}^{t}$ can also be parameterized by $e^{i\theta}$ with the exact
same distribution of $\theta\sim U[0,2\pi]$, for all $j\in[n],t\in[d]$. The
distribution of
$\left[\sum_{i}{\bm{x}}_{i},...,\sum_{i}{\bm{x}}_{i}^{d}\right]$ is therefore
a product distribution $(\textup{Law}(\sum_{i=1}^{n}Z_{i}))^{d}$ where
$Z_{i}\sim U[\mathbb{C}\cap\\{|z|=1\\}]$. These generators and input
distributions come from the classical text of Macdonald [1979]. Here, as long
as $r\leq n$, $r$ only depends on $d$ and not $n$. Plugging this $r$ into
Theorem 45 gives straightforward bounds that are independent of $n$-the
original number of variables, but does not give meaningful separation in
Corollary 46.

As a reminder, we also have an example in the main text for the sign group
[Lim et al., 2022].

##  Appendix H Experimental Details

(a) GNN learning $\mathcal{H}_{ER,n}$

(b) CNN learning $C^{\mathcal{B}}_{\mathcal{F}}$

Figure 3: Replication of experiments as in Fig. 1, except here, we consider a
minimal architecture consisting of a single layer of graph or cyclic
convolution followed by a single hidden layer MLP. This is the minimal number
of layers needed to learn the desired function classes for the architectures
considered. For the CNN plot, the jumps in the train set MSE are due to
perturbations in the loss at very low values near computer precision.  Figure
4: Replication of experiments in Fig. 1(a) with different optimizers show that
the performance of the GNN is virtually the same across the various
optimizers. Performance is averaged over 10 runs. For each run, the learning
rate is chosen by perturbing the default learning rate by a random
multiplicative factor in the range $[0.1,10]$.

GNN experiments were performed using the Pytorch Geometric library for
implementing geometric architectures [Fey and Lenssen, 2019]. The hard
functions were drawn from $\mathcal{H}_{ER,n}$ (see Eq. 7) where subset
$S\subseteq[n]$ was drawn uniformly from all the possible subsets of size
$\lfloor n/2\rfloor$ and $b$ was either $0$ or $1$ with equal probability. For
our experiments, we set $n=15$ and trained on $n^{2}=225$ datapoints. The
overparameterized GNN used during training consisted of $3$ layers of graph
convolution followed by a node aggregation average pooling layer and a two
layer ReLU MLP with width $64$. The graph convolution layers used $32$
channels.

For the CNN experiments, we constructed the hard functions in Eq. 17 setting
$n=50$ and $k=10$. Here, matrices $B\in\mathcal{B}$ were drawn randomly from
all possible $n\times 2$ orthogonal matrices by taking a QR decomposition of a
random $n\times 2$ matrix with Gaussian i.i.d. elements. For sake of
convenience, we did not divide by the norm of the function. The CNN
architecture implemented consisted of three layers of fully parameterized
cyclic convolution each with $100$ output channels. This was followed by a
global average pooling layer and and a two layer ReLU MLP of width $100$. The
network was given $10n=500$ training samples and was trained with the Adam
optimizer with batch size $32$.

Experiments in the main text considered architectures which were
overparameterized in terms of the number of layers with respect to the target
function. For sake of completeness, we include in Fig. 3 results for merely
sufficiently parameterized networks which consist of a single convolution
layer, pooling and single hidden layer MLP. The results in Fig. 3 are
consistent with those observed in Fig. 1. Additionally, to further confirm
that these results are robust to hyperparameter choices for the optimizer, we
repeated the GNN learning experiments with the choice of optimizer varying
between Adam, SGD, and RMSprop [Paszke et al., 2019]. Fig. 4 shows the results
for these different optimizers. For each optimizer, $10$ simulations were
performed where for each simulation, the learning rate was chosen by
multiplying the default learning rate by a random number in the range
$[0.1,10]$.

All experiments were run using Pytorch on a single GPU [Paszke et al., 2019].
Default initialization schemes were used for the initial network weights. In
our experiments, we used the Adam optimizer and tuned the learning rate in the
range $[0.0001,0.003]$. For CNN experiments, to increase stability of training
in later stages, we added a scheduler that divided the learning rate by two
every $200$ epochs. Plots are created by combining and averaging five random
realizations of each experiment.