Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy

We use bold-face letters to denote vectors, e.g., $\mathbf{x}=(x_{1},\ldots,x_{d})$. For a vector $\mathbf{x}$ and a sequence $S=(i_{1},\ldots,i_{k})$ of $k$ indices, we let $\mathbf{x}_{S}=(x_{i_{1}},\ldots,x_{i_{k}})$, i.e., the restriction of $\mathbf{x}$ to the indices $S$. We denote by $\mathbbm{1}[\cdot]$ the indicator function, for example $\mathbbm{1}[t\geq 5]$ equals $1$ if $t\geq 5$ and $0$ otherwise. For an integer $d\geq 1$ we denote $[d]=\{1,\ldots,d\}$. We denote by ${\cal N}(0,\sigma^{2})$ the normal distribution with mean $0$ and variance $\sigma^{2}$, and by ${\cal N}({\mathbf{0}},\Sigma)$ the multivariate normal distribution with mean ${\mathbf{0}}$ and covariance matrix $\Sigma$. The identity matrix of size $d$ is denoted by $I_{d}$. For $\mathbf{x}\in{\mathbb{R}}^{d}$ we denote by $\left\|\mathbf{x}\right\|$ the Euclidean norm. We use $\operatorname{poly}(a_{1},\ldots,a_{n})$ to denote a polynomial in $a_{1},\ldots,a_{n}$.

An $(n,m,k)$-hypergraph is a hypergraph over $n$ vertices $[n]$ with $m$ hyperedges $S_{1},\ldots,S_{m}$, each of cardinality $k$. Each hyperedge $S=(i_{1},\ldots,i_{k})$ is ordered, and all the $k$ members of a hyperedge are distinct. We let ${\cal G}_{n,m,k}$ be the distribution over such hypergraphs in which a hypergraph is chosen by picking each hyperedge uniformly and independently at random among all the possible $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ ordered hyperedges. Let $P:\{0,1\}^{k}\rightarrow\{0,1\}$ be a predicate, and let $G$ be a $(n,m,k)$-hypergraph. We call Goldreich’s pseudorandom generator (PRG) (Goldreich, 2000) the function $f_{P,G}:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ such that for $\mathbf{x}\in\{0,1\}^{n}$, we have $f_{P,G}(\mathbf{x})=(P(\mathbf{x}_{S_{1}}),\ldots,P(\mathbf{x}_{S_{m}}))$. The integer $k$ is called the locality of the PRG. If $k$ is a constant then the PRG and the predicate $P$ are called local. We say that the PRG has polynomial stretch if $m=n^{s}$ for some constant $s>1$. We let ${\cal F}_{P,n,m}$ denote the collection of functions $f_{P,G}$ where $G$ is an $(n,m,k)$-hypergraph. We sample a function from ${\cal F}_{P,n,m}$ by choosing a random hypergraph $G$ from ${\cal G}_{n,m,k}$.

We denote by $G\xleftarrow{R}{\cal G}_{n,m,k}$ the operation of sampling a hypergraph $G$ from ${\cal G}_{n,m,k}$, and by $\mathbf{x}\xleftarrow{R}\{0,1\}^{n}$ the operation of sampling $\mathbf{x}$ from the uniform distribution on $\{0,1\}^{n}$. We say that ${\cal F}_{P,n,m}$ is $\varepsilon$-pseudorandom generator ($\varepsilon$-PRG) if for every polynomial-time probabilistic algorithm ${\cal A}$ the distinguishing advantage

is at most $\varepsilon$. Thus, the distinguisher ${\cal A}$ is given a random hypergraph $G$ and a string $\mathbf{y}\in\{0,1\}^{m}$, and its goal is to distinguish between the case where $\mathbf{y}$ is chosen at random, and the case where $\mathbf{y}$ is a random image of $f_{P,G}$.

Our assumption is that local PRGs with polynomial stretch and constant distinguishing advantage exist:

We remark that the same assumption was used by Daniely and Vardi (2021) to show hardness-of-learning results. Local PRGs have been extensively studied in the last two decades. In particular, local PRGs with polynomial stretch have shown to have remarkable applications, such as secure-computation with constant computational overhead (Ishai et al., 2008; Applebaum et al., 2017), and general-purpose obfuscation based on constant degree multilinear maps (cf. Lin (2016); Lin and Vaikuntanathan (2016)). Significant evidence for Assumption 2.1 was shown in Applebaum (2013). Moreover, a concrete candidate for a local PRG, based on the XOR-MAJ predicate, was shown to be secure against all known attacks (Applebaum and Lovett, 2016; Couteau et al., 2018; Méaux et al., 2019; Applebaum and Raykov, 2016). See Daniely and Vardi (2021) for further discussion on the assumption, and on prior work regarding the relation between Goldreich’s PRG and hardness of learning.

We consider feedforward ReLU networks. Starting from an input $\mathbf{x}\in{\mathbb{R}}^{d}$, each layer in the network is of the form $\mathbf{z}\mapsto\sigma(W_{i}\mathbf{z}+\mathbf{b}_{i})$, where $\sigma(a)=[a]_{+}=\max\{0,a\}$ is the ReLU activation which applies to vectors entry-wise, $W_{i}$ is the weight matrix, and $\mathbf{b}_{i}$ are the bias terms. The weights vector of the $j$-th neuron in the $i$-th layer is the $j$-th row of $W_{i}$, and its outgoing-weights vector is the $j$-th column of $W_{i+1}$. We define the depth of the network as the number of layers. Unless stated otherwise, the output neuron also has a ReLU activation function. Note that a depth-$k$ network with activation in the output neuron has $k$ non-linear layers. A neuron which is not an input or output neuron is called a hidden neuron. We sometimes consider neural networks with multiple outputs. The parameters of the neural network is the set of its weight matrices and bias vectors. We often view the parameters as a vector ${\boldsymbol{\theta}}\in{\mathbb{R}}^{p}$ obtained by concatenating these matrices and vectors. For $B\geq 0$, we say that the parameters are $B$-bounded if the absolute values of all weights and biases are at most $B$.

We first define learning neural networks under the standard PAC framework:

We consider learning in the smoothed-analysis framework (Spielman and Teng, 2004), which is a popular paradigm for analyzing non-worst-case computational complexity (Roughgarden, 2021). The smoothed-analysis framework has been successfully applied to many learning problems (e.g., Awasthi et al. (2021); Ge et al. (2018); Kalai et al. (2009); Bhaskara et al. (2014, 2019); Haghtalab et al. (2020); Ge et al. (2015); Kalai and Teng (2008); Brutzkus et al. (2020)). In the smoothed-analysis setting, the target network is not purely controlled by an adversary. Instead, the adversary can first generate an arbitrary network, and the parameters for this network (i.e., the weight matrices and bias terms) will be randomly perturbed to yield a perturbed network. The algorithm only needs to work with high probability on the perturbed network. This limits the power of the adversary and prevents it from creating highly degenerate cases. Formally, we consider the following framework (we note that a similar model was considered in Awasthi et al. (2021) and Ge et al. (2018)):

Finally, we also consider a setting where both the parameters and the input distribution are smoothed:

We emphasize that all of the above definitions consider learning in the distribution-specific setting. Thus, the learning algorithm may depend on the specific input distribution ${\cal D}$.

Since our goal is to use the algorithm ${\cal L}$ for breaking PRGs, in this subsection we define a neural network $\tilde{N}:{\mathbb{R}}^{n^{2}}\to{\mathbb{R}}$ that we will later use as a target network for ${\cal L}$. The network $\tilde{N}$ contains the subnetworks $N_{1},N_{2},N_{3}$ which we define below.

Let $N_{1}$ be a depth-$2$ neural network with input dimension $kn$, at most $n\log(n)$ hidden neurons, at most $\log(n)$ output neurons (with activations in the output neurons), and parameter magnitudes bounded by $n^{3}$ (all bounds are for a sufficiently large $n$), which satisfies the following. We denote the set of output neurons of $N_{1}$ by ${\cal E}_{1}$. Let $\mathbf{z}^{\prime}\in{\mathbb{R}}^{kn}$ be an input to $N_{1}$ such that $\Psi(\mathbf{z}^{\prime})=\mathbf{z}^{S}$ for some hyperedge $S$, and assume that for every $i\in[kn]$ we have $z^{\prime}_{i}\not\in\left(c,c+\frac{1}{n^{2}}\right)$. Fix some $\mathbf{x}\in\{0,1\}^{n}$. Then, for $S$ with $P_{\mathbf{x}}(\mathbf{z}^{S})=0$ the inputs to all output neurons ${\cal E}_{1}$ are at most $-1$, and for $S$ with $P_{\mathbf{x}}(\mathbf{z}^{S})=1$ there exists a neuron in ${\cal E}_{1}$ with input at least $2$. Recall that our definition of a neuron’s input includes the addition of the bias term. The construction of the network $N_{1}$ is given in Lemma A.3. Intuitively, the network $N_{1}$ consists of a layer that transforms w.h.p. the input $\mathbf{z}^{\prime}$ to $\Psi(\mathbf{z}^{\prime})=\mathbf{z}^{S}$, followed by a layer that satisfies the following: Building on a lemma from Daniely and Vardi (2021) which shows that $P_{\mathbf{x}}(\mathbf{z}^{S})$ can be computed by a DNF formula, we define a layer where each output neuron corresponds to a term in the DNF formula, such that if the term evaluates to 0 then the input to the neuron is at most $-1$, and otherwise it is at least $2$. Note that the network $N_{1}$ depends on $\mathbf{x}$. However, only the second layer depends on $\mathbf{x}$, and thus given an input we may compute the first layer even without knowing $\mathbf{x}$. Let $N^{\prime}_{1}:{\mathbb{R}}^{kn}\to{\mathbb{R}}$ be a depth-$3$ neural network with no activation function in the output neuron, obtained from $N_{1}$ by summing the outputs from all neurons ${\cal E}_{1}$.

Let $N_{2}$ be a depth-$2$ neural network with input dimension $kn$, at most $n\log(n)$ hidden neurons, at most $2n$ output neurons, and parameter magnitudes bounded by $n^{3}$ (for a sufficiently large $n$), which satisfies the following. We denote the set of output neurons of $N_{2}$ by ${\cal E}_{2}$. Let $\mathbf{z}^{\prime}\in{\mathbb{R}}^{kn}$ be an input to $N_{2}$ such that for every $i\in[kn]$ we have $z^{\prime}_{i}\not\in\left(c,c+\frac{1}{n^{2}}\right)$. If $\Psi(\mathbf{z}^{\prime})$ is an encoding of a hyperedge then the inputs to all output neurons ${\cal E}_{2}$ are at most $-1$, and otherwise there exists a neuron in ${\cal E}_{2}$ with input at least $2$. The construction of the network $N_{2}$ is given in Lemma A.5. Intuitively, each neuron in ${\cal E}_{2}$ is responsible for checking whether $\Psi(\mathbf{z}^{\prime})$ violates some requirement that must hold in an encoding of a hyperedge. Let $N^{\prime}_{2}:{\mathbb{R}}^{kn}\to{\mathbb{R}}$ be a depth-$3$ neural network with no activation function in the output neuron, obtained from $N_{2}$ by summing the outputs from all neurons ${\cal E}_{2}$.

Let $N_{3}$ be a depth-$2$ neural network with input dimension $kn$, at most $n\log(n)$ hidden neurons, $kn\leq n\log(n)$ output neurons, and parameter magnitudes bounded by $n^{3}$ (for a sufficiently large $n$), which satisfies the following. We denote the set of output neurons of $N_{3}$ by ${\cal E}_{3}$. Let $\mathbf{z}^{\prime}\in{\mathbb{R}}^{kn}$ be an input to $N_{3}$. If there exists $i\in[kn]$ such that $z^{\prime}_{i}\in\left(c,c+\frac{1}{n^{2}}\right)$ then there exists a neuron in ${\cal E}_{3}$ with input at least $2$. Moreover, if for all $i\in[kn]$ we have $z^{\prime}_{i}\not\in\left(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}}\right)$ then the inputs to all neurons in ${\cal E}_{3}$ are at most $-1$. The construction of the network $N_{3}$ is straightforward and given in Lemma A.6. Let $N^{\prime}_{3}:{\mathbb{R}}^{kn}\to{\mathbb{R}}$ be a depth-$3$ neural network with no activation function in the output neuron, obtained from $N_{3}$ by summing the outputs from all neurons ${\cal E}_{3}$.

Let $N^{\prime}:{\mathbb{R}}^{kn}\to{\mathbb{R}}$ be a depth-$3$ network obtained from $N^{\prime}_{1},N^{\prime}_{2},N^{\prime}_{3}$ as follows. For $\mathbf{z}^{\prime}\in{\mathbb{R}}^{kn}$ we have $N^{\prime}(\mathbf{z}^{\prime})=\left[1-N^{\prime}_{1}(\mathbf{z}^{\prime})-N^{\prime}_{2}(\mathbf{z}^{\prime})-N^{\prime}_{3}(\mathbf{z}^{\prime})\right]_{+}$. The network $N^{\prime}$ has at most $n^{2}$ neurons, and parameter magnitudes bounded by $n^{3}$ (all bounds are for a sufficiently large $n$). Finally, let $\tilde{N}:{\mathbb{R}}^{n^{2}}\rightarrow{\mathbb{R}}$ be a depth-$3$ neural network such that $\tilde{N}(\tilde{\mathbf{z}})=N^{\prime}\left(\tilde{\mathbf{z}}_{[kn]}\right)$.

In order to use the algorithm ${\cal L}$ w.r.t. some neural network with parameters ${\boldsymbol{\theta}}$, we need to implement an examples oracle, such that the examples are labeled according to a neural network with parameters ${\boldsymbol{\theta}}+\boldsymbol{\xi}$, where $\boldsymbol{\xi}$ is a random perturbation. Specifically, we use ${\cal L}$ with an examples oracle where the labels correspond to a network $\hat{N}:{\mathbb{R}}^{n^{2}}\to{\mathbb{R}}$, obtained from $\tilde{N}$ (w.r.t. an appropriate $\mathbf{x}\in\{0,1\}^{n}$ in the construction of $N_{1}$) by adding a small perturbation to the parameters. The perturbation is such that we add i.i.d. noise to each parameter in $\tilde{N}$, where the noise is distributed according to ${\cal N}(0,\tau^{2})$, and $\tau=1/\operatorname{poly}(n)$ is small enough such that the following holds. Let $f_{\boldsymbol{\theta}}:{\mathbb{R}}^{n^{2}}\to{\mathbb{R}}$ be any depth-$3$ neural network parameterized by ${\boldsymbol{\theta}}\in{\mathbb{R}}^{r}$ for some $r>0$ with at most $n^{2}$ neurons, and parameter magnitudes bounded by $n^{3}$ (note that $r$ is polynomial in $n$). Then with probability at least $1-\frac{1}{n}$ over $\boldsymbol{\xi}\sim{\cal N}({\mathbf{0}},\tau^{2}I_{r})$, we have $|\xi_{i}|\leq\frac{1}{10}$ for all $i\in[r]$, and the network $f_{{\boldsymbol{\theta}}+\boldsymbol{\xi}}$ is such that for every input $\tilde{\mathbf{z}}\in{\mathbb{R}}^{n^{2}}$ with $\left\|\tilde{\mathbf{z}}\right\|\leq 2n$ and every neuron we have: Let $a,b$ be the inputs to the neuron in the computations $f_{\boldsymbol{\theta}}(\tilde{\mathbf{z}})$ and $f_{{\boldsymbol{\theta}}+\boldsymbol{\xi}}(\tilde{\mathbf{z}})$ (respectively), then $|a-b|\leq\frac{1}{2}$. Thus, $\tau$ is sufficiently small, such that w.h.p. adding i.i.d. noise ${\cal N}(0,\tau^{2})$ to each parameter does not change the inputs to the neurons by more than $\frac{1}{2}$. Note that such an inverse-polynomial $\tau$ exists, since when the network size, parameter magnitudes, and input size are bounded by some $\operatorname{poly}(n)$, then the input to each neuron in $f_{\boldsymbol{\theta}}(\tilde{\mathbf{z}})$ is $\operatorname{poly}(n)$-Lipschitz as a function of ${\boldsymbol{\theta}}$, and thus it suffices to choose $\tau$ that implies with probability at least $1-\frac{1}{n}$ that $\left\|\boldsymbol{\xi}\right\|\leq\frac{1}{q(n)}$ for a sufficiently large polynomial $q(n)$ (see Lemma A.7 for details).

Let $\tilde{{\boldsymbol{\theta}}}\in{\mathbb{R}}^{p}$ be the parameters of the network $\tilde{N}$. Recall that the parameters vector $\tilde{{\boldsymbol{\theta}}}$ is the concatenation of all weight matrices and bias terms. Let $\hat{{\boldsymbol{\theta}}}\in{\mathbb{R}}^{p}$ be the parameters of $\hat{N}$, namely, $\hat{{\boldsymbol{\theta}}}=\tilde{{\boldsymbol{\theta}}}+\boldsymbol{\xi}$ where $\boldsymbol{\xi}\sim{\cal N}({\mathbf{0}},\tau^{2}I_{p})$. By our choice of $\tau$ and the construction of the networks $N_{1},N_{2},N_{3}$, with probability at least $1-\frac{1}{n}$ over $\boldsymbol{\xi}$, for every $\tilde{\mathbf{z}}$ with $\left\|\tilde{\mathbf{z}}\right\|\leq 2n$, the inputs to the neurons ${\cal E}_{1},{\cal E}_{2},{\cal E}_{3}$ in the computation $\hat{N}(\tilde{\mathbf{z}})$ satisfy the following properties, where we denote $\mathbf{z}^{\prime}=\tilde{\mathbf{z}}_{[kn]}$:

1. (P1)

   If $\Psi(\mathbf{z}^{\prime})=\mathbf{z}^{S}$ for some hyperedge $S$, and for every $i\in[kn]$ we have $z^{\prime}_{i}\not\in\left(c,c+\frac{1}{n^{2}}\right)$, then the inputs to ${\cal E}_{1}$ satisfy:

   • •

     If $P_{\mathbf{x}}(\mathbf{z}^{S})=0$ the inputs to all neurons in ${\cal E}_{1}$ are at most $-\frac{1}{2}$.

   • •

     If $P_{\mathbf{x}}(\mathbf{z}^{S})=1$ there exists a neuron in ${\cal E}_{1}$ with input at least $\frac{3}{2}$.

2. (P2)

   If for every $i\in[kn]$ we have $z^{\prime}_{i}\not\in\left(c,c+\frac{1}{n^{2}}\right)$, then the inputs to ${\cal E}_{2}$ satisfy:

   • •

     If $\Psi(\mathbf{z}^{\prime})$ is an encoding of a hyperedge then the inputs to all neurons ${\cal E}_{2}$ are at most $-\frac{1}{2}$.

   • •

     Otherwise, there exists a neuron in ${\cal E}_{2}$ with input at least $\frac{3}{2}$.

3. (P3)

   The inputs to ${\cal E}_{3}$ satisfy:

   • •

     If there exists $i\in[kn]$ such that $z^{\prime}_{i}\in\left(c,c+\frac{1}{n^{2}}\right)$ then there exists a neuron in ${\cal E}_{3}$ with input at least $\frac{3}{2}$.

   • •

     If for all $i\in[kn]$ we have $z^{\prime}_{i}\not\in\left(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}}\right)$ then the inputs to all neurons in ${\cal E}_{3}$ are at most $-\frac{1}{2}$.

Given a sequence $(S_{1},y_{1}),\ldots,(S_{n^{s}},y_{n^{s}})$, where $S_{1},\ldots,S_{n^{s}}$ are i.i.d. random hyperedges, the algorithm ${\cal A}$ needs to distinguish whether $\mathbf{y}=(y_{1},\ldots,y_{n^{s}})$ is random or that $\mathbf{y}=(P(\mathbf{x}_{S_{1}}),\ldots,P(\mathbf{x}_{S_{n^{s}}}))=(P_{\mathbf{x}}(\mathbf{z}^{S_{1}}),\ldots,P_{\mathbf{x}}(\mathbf{z}^{S_{n^{s}}}))$ for a random $\mathbf{x}\in\{0,1\}^{n}$. Let ${\cal S}=((\mathbf{z}^{S_{1}},y_{1}),\ldots,(\mathbf{z}^{S_{n^{s}}},y_{n^{s}}))$.

We use the efficient algorithm ${\cal L}$ in order to obtain distinguishing advantage greater than $\frac{1}{3}$ as follows. Let $\boldsymbol{\xi}$ be a random perturbation, and let $\hat{N}$ be the perturbed network as defined above, w.r.t. the unknown $\mathbf{x}\in\{0,1\}^{n}$. Note that given a perturbation $\boldsymbol{\xi}$, only the weights in the second layer of the subnetwork $N_{1}$ in $\hat{N}$ are unknown, since all other parameters do not depend on $\mathbf{x}$. The algorithm ${\cal A}$ runs ${\cal L}$ with the following examples oracle. In the $i$-th call, the oracle first draws $\mathbf{z}\in\{0,1\}^{kn}$ such that each component is drawn i.i.d. from a Bernoulli distribution which takes the value $0$ with probability $\frac{1}{n}$. If $\mathbf{z}$ is an encoding of a hyperedge then the oracle replaces $\mathbf{z}$ with $\mathbf{z}^{S_{i}}$. Then, the oracle chooses $\mathbf{z}^{\prime}\in{\mathbb{R}}^{kn}$ such that for each component $j$, if $z_{j}=1$ then $z^{\prime}_{j}$ is drawn from $\mu_{+}$, and otherwise $z^{\prime}_{j}$ is drawn from $\mu_{-}$. Let $\tilde{\mathbf{z}}\in{\mathbb{R}}^{n^{2}}$ be such that $\tilde{\mathbf{z}}_{[kn]}=\mathbf{z}^{\prime}$, and the other $n^{2}-kn$ components of $\tilde{\mathbf{z}}$ are drawn i.i.d. from ${\cal N}(0,1)$. Note that the vector $\tilde{\mathbf{z}}$ has the distribution ${\cal D}$, due to the definitions of the densities $\mu_{+}$ and $\mu_{-}$, and since replacing an encoding of a random hyperedge by an encoding of another random hyperedge does not change the distribution of $\mathbf{z}$. Let $\hat{b}\in{\mathbb{R}}$ be the bias term of the output neuron of $\hat{N}$. The oracle returns $(\tilde{\mathbf{z}},\tilde{y})$, where the labels $\tilde{y}$ are chosen as follows:

• •

  If $\Psi(\mathbf{z}^{\prime})$ is not an encoding of a hyperedge, then $\tilde{y}=0$.

• •

  If $\Psi(\mathbf{z}^{\prime})$ is an encoding of a hyperedge:

  • –

    If $\mathbf{z}^{\prime}$ does not have components in the interval $(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}})$, then if $y_{i}=0$ we set $\tilde{y}=\hat{b}$, and if $y_{i}=1$ we set $\tilde{y}=0$.

  • –

    If $\mathbf{z}^{\prime}$ has a component in the interval $(c,c+\frac{1}{n^{2}})$, then $\tilde{y}=0$.

  • –

    If $\mathbf{z}^{\prime}$ does not have components in the interval $(c,c+\frac{1}{n^{2}})$, but has a component in the interval $(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}})$, then the label $\tilde{y}$ is determined as follows:

    • *

      If $y_{i}=1$ then $\tilde{y}=0$.

    • *

      If $y_{i}=0$: Let $\hat{N}_{3}$ be the network $\hat{N}$ after omitting the neurons ${\cal E}_{1},{\cal E}_{2}$ and their incoming and outgoing weights. Then, we set $\tilde{y}=[\hat{b}-\hat{N}_{3}(\tilde{\mathbf{z}})]_{+}$. Note that since only the second layer of $N_{1}$ depends on $\mathbf{x}$, then we can compute $\hat{N}_{3}(\tilde{\mathbf{z}})$ without knowing $\mathbf{x}$.

Let $h$ be the hypothesis returned by ${\cal L}$. Recall that ${\cal L}$ uses at most $m(n)$ examples, and hence ${\cal S}$ contains at least $n^{3}$ examples that ${\cal L}$ cannot view. We denote the indices of these examples by $I=\{m(n)+1,\ldots,m(n)+n^{3}\}$, and the examples by ${\cal S}_{I}=\{(\mathbf{z}^{S_{i}},y_{i})\}_{i\in I}$. By $n^{3}$ additional calls to the oracle, the algorithm ${\cal A}$ obtains the examples $\tilde{{\cal S}}_{I}=\{(\tilde{\mathbf{z}}_{i},\tilde{y}_{i})\}_{i\in I}$ that correspond to ${\cal S}_{I}$. Let $h^{\prime}$ be a hypothesis such that for all $\tilde{\mathbf{z}}\in{\mathbb{R}}^{n^{2}}$ we have $h^{\prime}(\tilde{\mathbf{z}})=\max\{0,\min\{\hat{b},h(\tilde{\mathbf{z}})\}\}$, thus, for $\hat{b}\geq 0$ the hypothesis $h^{\prime}$ is obtained from $h$ by clipping the output to the interval $[0,\hat{b}]$. Let $\ell_{I}(h^{\prime})=\frac{1}{|I|}\sum_{i\in I}(h^{\prime}(\tilde{\mathbf{z}}_{i})-\tilde{y}_{i})^{2}$. Now, if $\ell_{I}(h^{\prime})\leq\frac{2}{n}$, then ${\cal A}$ returns $1$, and otherwise it returns $0$. We remark that the decision of our algorithm is based on $h^{\prime}$ (rather than $h$) since we need the outputs to be bounded, in order to allow using Hoeffding’s inequality in our analysis, which we discuss in the next subsection.

Note that the algorithm ${\cal A}$ runs in $\operatorname{poly}(n)$ time. We now show that if ${\cal S}$ is pseudorandom then ${\cal A}$ returns $1$ with probability greater than $\frac{2}{3}$, and if ${\cal S}$ is random then ${\cal A}$ returns $1$ with probability less than $\frac{1}{3}$.

We start with the case where ${\cal S}$ is pseudorandom. In Lemma A.8, we prove that if ${\cal S}$ is pseudorandom then w.h.p. (over $\boldsymbol{\xi}\sim{\cal N}({\mathbf{0}},\tau^{2}I_{p})$ and the i.i.d. inputs $\tilde{\mathbf{z}}_{i}\sim{\cal D}$) the examples $(\tilde{\mathbf{z}}_{1},\tilde{y}_{1}),\ldots,(\tilde{\mathbf{z}}_{m(n)+n^{3}},\tilde{y}_{m(n)+n^{3}})$ returned by the oracle are realized by $\hat{N}$. Thus, $\tilde{y}_{i}=\hat{N}(\tilde{\mathbf{z}}_{i})$ for all $i$. As we show in the lemma, this claim follows by noting that the following hold w.h.p., where we denote $\mathbf{z}^{\prime}_{i}=(\tilde{\mathbf{z}}_{i})_{[kn]}$:

• •

  If $\Psi(\mathbf{z}^{\prime}_{i})$ is not an encoding of a hyperedge, then the oracle sets $\tilde{y}_{i}=0$, and we have:

  • –

    If $\mathbf{z}^{\prime}_{i}$ does not have components in $\left(c,c+\frac{1}{n}\right)$, then there exists a neuron in ${\cal E}_{2}$ with output at least $\frac{3}{2}$ (by Property (P2)), which implies $\hat{N}(\tilde{\mathbf{z}}_{i})=0$.

  • –

    If $\mathbf{z}^{\prime}$ has a component in $\left(c,c+\frac{1}{n}\right)$, then there exists a neuron in ${\cal E}_{3}$ with output at least $\frac{3}{2}$ (by Property (P3)), which implies $\hat{N}(\tilde{\mathbf{z}}_{i})=0$.

• •

  If $\Psi(\mathbf{z}^{\prime}_{i})$ is an encoding of a hyperedge $S$, then by the definition of the examples oracle we have $S=S_{i}$. Hence:

  • –

    If $\mathbf{z}^{\prime}_{i}$ does not have components in $\left(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}}\right)$, then:

    • *

      If $y_{i}=0$ then the oracle sets $\tilde{y}_{i}=\hat{b}$. Since ${\cal S}$ is pseudorandom, we have $P_{\mathbf{x}}(\mathbf{z}^{S})=P_{\mathbf{x}}(\mathbf{z}^{S_{i}})=y_{i}=0$. Hence, in the computation $\hat{N}(\tilde{\mathbf{z}}_{i})$ the inputs to all neurons in ${\cal E}_{1},{\cal E}_{2},{\cal E}_{3}$ are at most $-\frac{1}{2}$ (by Properties (P1), (P2) and (P3)), and thus their outputs are $0$. Therefore, $\hat{N}(\tilde{\mathbf{z}}_{i})=\hat{b}$.

    • *

      If $y_{i}=1$ then the oracle sets $\tilde{y}_{i}=0$. Since ${\cal S}$ is pseudorandom, we have $P_{\mathbf{x}}(\mathbf{z}^{S})=P_{\mathbf{x}}(\mathbf{z}^{S_{i}})=y_{i}=1$. Hence, in the computation $\hat{N}(\tilde{\mathbf{z}}_{i})$ there exists a neuron in ${\cal E}_{1}$ with output at least $\frac{3}{2}$ (by Property (P1)), which implies $\hat{N}(\tilde{\mathbf{z}}_{i})=0$.

  • –

    If $\mathbf{z}^{\prime}_{i}$ has a component in $\left(c,c+\frac{1}{n^{2}}\right)$, then the oracle sets $\tilde{y}_{i}=0$. Also, in the computation $\hat{N}(\tilde{\mathbf{z}}_{i})$ there exists a neuron in ${\cal E}_{3}$ with output at least $\frac{3}{2}$ (by Property (P3)), which implies $\hat{N}(\tilde{\mathbf{z}}_{i})=0$.

  • –

    If $\mathbf{z}^{\prime}_{i}$ does not have components in the interval $(c,c+\frac{1}{n^{2}})$, but has a component in the interval $(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}})$, then:

    • *

      If $y_{i}=1$ the oracle sets $\tilde{y}_{i}=0$. Since ${\cal S}$ is pseudorandom, we have $P_{\mathbf{x}}(\mathbf{z}^{S})=P_{\mathbf{x}}(\mathbf{z}^{S_{i}})=y_{i}=1$. Hence, in the computation $\hat{N}(\tilde{\mathbf{z}}_{i})$ there exists a neuron in ${\cal E}_{1}$ with output at least $\frac{3}{2}$ (by Property (P1)), which implies $\hat{N}(\tilde{\mathbf{z}}_{i})=0$.

    • *

      If $y_{i}=0$ the oracle sets $\tilde{y}_{i}=[\hat{b}-\hat{N}_{3}(\tilde{\mathbf{z}}_{i})]_{+}$. Since ${\cal S}$ is pseudorandom, we have $P_{\mathbf{x}}(\mathbf{z}^{S})=P_{\mathbf{x}}(\mathbf{z}^{S_{i}})=y_{i}=0$. Therefore, in the computation $\hat{N}(\tilde{\mathbf{z}}_{i})$ all neurons in ${\cal E}_{1},{\cal E}_{2}$ have output $0$ (by Properties (P1) and (P2)), and hence their contribution to the output of $\hat{N}$ is $0$. Thus, by the definition of $\hat{N}_{3}$, we have $\hat{N}(\tilde{\mathbf{z}}_{i})=[\hat{b}-\hat{N}_{3}(\tilde{\mathbf{z}}_{i})]_{+}$.

Recall that the algorithm ${\cal L}$ is such that with probability at least $\frac{3}{4}$ (over $\boldsymbol{\xi}\sim{\cal N}({\mathbf{0}},\tau^{2}I_{p})$, the i.i.d. inputs $\tilde{\mathbf{z}}_{i}\sim{\cal D}$, and its internal randomness), given a size-$m(n)$ dataset labeled by $\hat{N}$, it returns a hypothesis $h$ such that $\operatorname*{\mathbb{E}}_{\tilde{\mathbf{z}}\sim{\cal D}}\left[(h(\tilde{\mathbf{z}})-\hat{N}(\tilde{\mathbf{z}}))^{2}\right]\leq\frac{1}{n}$. By the definition of $h^{\prime}$ and the construction of $\hat{N}$, if $h$ has small error then $h^{\prime}$ also has small error, namely, we have $\operatorname*{\mathbb{E}}_{\tilde{\mathbf{z}}\sim{\cal D}}\left[(h^{\prime}(\tilde{\mathbf{z}})-\hat{N}(\tilde{\mathbf{z}}))^{2}\right]\leq\frac{1}{n}$. In Lemma A.9 we use the above arguments and Hoeffding’s inequality over $\tilde{{\cal S}}_{I}$, and prove that with probability greater than $\frac{2}{3}$ we have $\ell_{I}(h^{\prime})\leq\frac{2}{n}$.

Next, we consider the case where ${\cal S}$ is random. Let $\tilde{{\cal Z}}\subseteq{\mathbb{R}}^{n^{2}}$ be such that $\tilde{\mathbf{z}}\in\tilde{{\cal Z}}$ iff $\tilde{\mathbf{z}}_{[kn]}$ does not have components in the interval $(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}})$, and $\Psi(\tilde{\mathbf{z}}_{[kn]})=\mathbf{z}^{S}$ for a hyperedge $S$. If ${\cal S}$ is random, then by the definition of our examples oracle, for every $i\in[m(n)+n^{3}]$ such that $\tilde{\mathbf{z}}_{i}\in\tilde{{\cal Z}}$, we have $\tilde{y}_{i}=\hat{b}$ with probability $\frac{1}{2}$ and $\tilde{y}_{i}=0$ otherwise. Also, by the definition of the oracle, $\tilde{y}_{i}$ is independent of $S_{i}$ and independent of the choice of the vector $\tilde{\mathbf{z}}_{i}$ that corresponds to $\mathbf{z}^{S_{i}}$. Hence, for such $\tilde{\mathbf{z}}_{i}\in\tilde{{\cal Z}}$ with $i\in I$, any hypothesis cannot predict the label $\tilde{y}_{i}$, and the expected loss for the example is at least $\left(\frac{\hat{b}}{2}\right)^{2}$. Moreover, in Lemma A.11 we show that $\Pr\left[\tilde{\mathbf{z}}_{i}\in\tilde{{\cal Z}}\right]\geq\frac{1}{2\log(n)}$ for a sufficiently large $n$. In Lemma A.12 we use these arguments to prove a lower bound on $\operatorname*{\mathbb{E}}_{\tilde{{\cal S}}_{I}}\left[\ell_{I}(h^{\prime})\right]$, and by Hoeffding’s inequality over $\tilde{{\cal S}}_{I}$ we conclude that with probability greater than $\frac{2}{3}$ we have $\ell_{I}(h^{\prime})>\frac{2}{n}$.