reconstruction algorithm and obtain a hypothesis approximates $f$ with non-
trivial advantage over a random guess.

The agnostic learner $\mathcal{B}$ is described as follows. For any input
function $f$, $\mathcal{B}$ just runs the $\poly(L)$-time weak learner
$\mathcal{A}$ from Lemma 5.3 using query access to $\mathsf{Amp}^{f}_{k}$ and
the distinguisher circuit $D$ that computes $\mathcal{R}_{L}$, based on the
NW-generator $G^{\mathsf{Amp}^{f}_{k}}$. The oracle access by $\mathcal{A}$ to
$\mathsf{Amp}^{f}_{k}$ is simulated using the oracle to the input $f$.
$\mathcal{A}$ outputs a circuit on $n$ inputs that agrees with
$\mathsf{Amp}^{f}_{k}$ on at least $1/2+\Omega(1/L)$ fraction.

The uniform reconstruction algorithms that accompany hardness amplification
techniques using the Hadamard code (i.e., the Goldreich-Levin theorem) and the
Direct Product code [IJKW10], ensure that with high probability over its
randomness, $\mathcal{B}$ constructs a circuit $h$ on $n$ inputs that computes
$f$ on at least $1-O(\ell/k)$-fraction of the inputs, in $\poly(n,L,k)\leq
2^{O(\log^{2d+1}(n/\beta))}$ time.161616We can use standard error
amplification techniques to make the learner output this hypothesis with
probability at least $1-\delta$, where $\delta>0$ is the confidence parameter
[KV94]. From Lemma 5.3, we also see that the query complexity is at most
$\poly(L)\leq 2^{O(\log^{2d+1}(n/\beta))}$. Finally, the output hypothesis $h$
computes $f$ on at least $1-O(\beta\ell/\tau(\ell))$ fraction of the inputs,
i.e., $\mathsf{err}(h,f)\leq O(\log^{8d+4}(n/\beta))\cdot\beta$.

∎

The following corollary follows from Theorem 5.2 when the input function is
not too close to $\mathsf{AC}^{0}[2]$, i.e.,
$\mathsf{dist}(f,\mathsf{AC}^{0}[2])\geq 1/n^{\frac{\log(n)}{2}}$.

######  Corollary 5.7.

Let $\beta^{*}\geq 1/n^{\frac{\log(n)}{2}}$ and let $f$ be a Boolean function
such that $\mathsf{dist}(f,\mathsf{AC}^{0}_{d}[2][\poly(n)])=\beta^{*}$, for
constant $d\in\mathbb{N}$. Then, for input $\beta$ such that
$\beta^{*}\leq\beta\leq 1/2$, the agnostic learning algorithm $\mathcal{B}$
uses membership queries to $f$ and outputs a hypothesis that has error at most
$O(\log^{16d+8}(n))\cdot\beta$ with probability at least $0.9$, having running
time and query complexity at most $2^{O(\log^{4d+2}(n))}$.

###### Proof.

The proof is obtained by setting the right parameters in Theorem 5.2. In
particular, since the smallest value of $\beta$ is $1/n^{\log(n)}$, setting
$\ell$ to be $O(\log^{2d+1}(n\cdot n^{\log(n)}))=O(\log^{4d+2}(n))$, ensures
that for every $\beta\geq 1/n^{\log(n)}$, when the value of $k$ is
$\frac{1}{8\ell^{3}\beta}$, for any $g\in\mathsf{AC}^{0}[2][\poly(n)]$, the
output of $G^{\mathsf{Amp}_{k}^{g}}$ on every seed is computable by a circuit
of size $\poly(n,k)=\poly(n/\beta)\leq u(\ell)=\mathsf{exp}(O(\ell^{1/2d}))$,
where $u(\ell)$ is the usefulness parameter of the natural property
$\\{\mathcal{R}_{n}\\}$ against $\mathsf{AC}^{0}[2]$.

Thus, the running time and query complexities of the algorithm are at most
$\poly(n,L,k)=2^{O(\log^{4d+2}(n))}$, where $L=2^{\ell}$. Moreover, for every
$\beta$, the guarantees of the learner $\mathcal{B}$ ensures that it outputs a
hypothesis that has error at most
$\ell^{4}\beta=O(\log^{16d+8}(n))\cdot\beta$, with probability at least $0.9$.
∎

##### Agnostic learning of $\mathsf{AC}^{0}[p]$, for every prime $p>2$

The learner follows from the general strategy as $\mathsf{AC}^{0}[2]$, however
[CIKK17] extend the class $\mathsf{AC}^{0}[p]$ to include functions of the
form $f:\\{0,1\\}^{n}\rightarrow\mathbb{F}_{p}$, e.g., by having $p$ output
gates and the true output selects the field element (constant inputs from
$\mathbb{F}_{p}$ to the circuit can also be coded this way). Following this,
they show the existence of a $(0.15)$-tolerant natural property useful against
$\mathsf{AC}^{0}[p]$ circuits of depth $d$ and size $\exp(\Omega(n^{1/2d}))$
under this extended notion. Finally, they use this natural property to
construct an agnostic learner for $\mathsf{AC}^{0}[p]$, where the input
distribution is still Boolean, i.e., the distribution is
$(\mathcal{U}_{n},f(\mathcal{U}_{n}))$ for
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$.

######  Lemma 5.8 (Agnostic Learners for $\mathsf{AC}^{0}$$[p]$).

For any prime $p>2$, let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be such that
$\mathsf{dist}(f,\mathsf{AC}^{0}_{d}[p][\poly(n)])=\beta^{*}$, where
$\beta^{*}\geq 1/n^{\frac{\log(n)}{2}}$ and $d$ is a constant in $\mathbb{N}$.

Then, there exists a randomised algorithm $\mathcal{B}$, that, given as inputs
any $\beta$ such that $\beta^{*}\leq\beta\leq 1/2$, and membership query
access to $f$, outputs a hypothesis that has error at most
$O(\log^{16pd+8p}(n))\cdot\beta$ with probability at least $0.9$, that has
running time and query complexity at most $2^{O(\log^{4pd+2p}(n))}$.

The learning algorithm is the same as that of the case $\mathsf{AC}^{0}[2]$
with some minor modifications. Firstly, the amplified function
$\mathsf{Amp}^{f}_{k}:\\{0,1\\}^{nk}\times\mathbb{F}_{p}^{k}\rightarrow\mathbb{F}_{p}$
is different here and is given by
$\mathsf{Amp}^{f}_{k}(x_{1},\dots,x_{k},b_{1},\dots,b_{k})=\sum_{i=1}^{k}f(x_{i})\cdot
b_{i}\pmod{p}$, where $x_{1},\dots,x_{k}\in\\{0,1\\}^{n}$ and
$b_{1},\dots,b_{k}\in\mathbb{F}_{p}$. As can be seen, the output of the
$\mathsf{Amp}^{f}_{k}$ is an element in $\mathbb{F}_{p}$, and thus combined
with the set design (that is also constructible using polynomials over
$\mathbb{F}_{p}$), the resulting truth table output by
$G^{\mathsf{Amp}^{f}_{k}}$ would be a vector in $\mathbb{F}_{p}^{L}$. Since
the tolerant natural property can now deal with such truth tables, the
framework from Theorem 5.2 can now be applied here. In particular, the weak
learner from Algorithm 5 is still used here, where oracle access to the non-
Boolean function $\mathsf{Amp}^{f}_{k}$ is in fact simulated by making
membership queries to the Boolean function $f$.

Moreover, the stretch $L$ of the generator is set to
$2^{O(\log^{4pd+2p}(n))}$, where $p$ comes up in the exponent because of the
overhead of the Goldreich-Levin reconstruction in producing a binary string in
$\\{0,1\\}^{k}$ as output (to represent the $f(x_{1}),\dots,f(x_{k})$).

##### Agnostic learning of a general circuit class $\mathcal{C}$

We end this section by stating the following general result for agnostically
learning any circuit class $\mathcal{C}$ that contains $\mathsf{AC}^{0}[2]$,
given any suitable strong tolerant natural property useful against
$\mathcal{C}$.

######  Lemma 5.9 (Tolerant natural properties imply agnostic learners).

Let $\mathcal{R}$ be a $(1/2-1/\poly(n))$-tolerant natural property useful
against $\mathcal{C}[\poly(n)]$, where $\mathcal{C}$ is any circuit class that
contains $\mathsf{AC}^{0}[2]$.

Then, for every $a\geq 1$ and $\gamma>0$, there exists a randomised algorithm
$\mathcal{B}$, that given as input $\beta$ such that
$\frac{1}{n^{2a\gamma}}\leq\beta^{*}\leq\beta\leq 1/2$, and membership query
access to $f$, such that $\mathsf{dist}(f,\mathcal{C}[n^{a}])=\beta^{*}$,
outputs a hypothesis with error at most $O(n^{\gamma}/\log(n))\cdot\beta$ over
the uniform distribution, with probability at least 0.9. Moreover,
$\mathcal{B}$ runs in time $2^{O(n^{\gamma})}$ and makes at most
$2^{O(n^{\gamma})}$ membership queries to $f$.

###### Proof Sketch.

The general outline is the same as before, however, the learner uses a variant
of the NW-generator in order to use the stronger tolerance of $1/2-1/\poly(n)$
more fruitfully. Indeed, adding a pairwise-independent string generator to the
NW-generator, helps us in using a stronger concentration bounds, and allows us
to show that with high probability over the choice of the seed, the functions
output by this modified generator have distance at most $1/2-1/\poly(\ell))$
from $\mathcal{C}[n^{a}]$.

In more detail, let
$\mathsf{PI}:\\{0,1\\}^{\ell}\times\\{0,1\\}^{m^{\prime}}\rightarrow\\{0,1\\}^{n}$,
be a pairwise independent generator. Then the modified NW generator $G^{\prime
f}:\\{0,1\\}^{m}\times\\{0,1\\}^{m^{\prime}}\rightarrow\\{0,1\\}^{L}$, is
defined as $G^{\prime
f}(z_{1},z_{2})=f(z|_{S_{1}}\oplus\mathsf{PI}(1,z_{2})),\dots,f(z|_{S_{L}}\oplus\mathsf{PI}(L,z_{2}))$.
Following this, the rest of the algorithm follows in a similar fashion as
Theorem 5.2. ∎

######  Remark 5.10.

While we state Theorem 5.9 for tolerance $\tau(n)=1/2-1/\poly(n)$ and
usefulness $\poly(n)$ as an example, [CIKK17] provide a more generalised form
for any varying parameters of usefulness $u(n)$ and tolerance
$1/2-\tau^{\prime}(n)$; the larger the value of $u(n)$, the smaller the
running time and the smaller the value of $\tau^{\prime}(n)$, the better the
multiplicative factors in the hypothesis approximation. In the best case, with
exponential usefulness $u$ and inverse exponential tolerance $\tau^{\prime}$,
the agnostic learner runs in $\poly(n)$ time and outputs a hypothesis with
error $\Theta(\beta^{*})$.

###  5.3 PAC-Verifiers for Circuit Classes

######  Proof of Theorem 5.1.

For the agnostic interactive proof, we first state the following randomised
query construction algorithm $\hat{\mathcal{A}}_{\mathsf{query}}$ that takes a
string $w\in\\{0,1\\}^{n}$ as input and outputs a set of queries for
$\mathsf{Amp}_{k}^{f}$, that has $w$ “embedded” at a uniformly random query
index. $\hat{\mathcal{A}}_{\mathsf{query}}$ builds on the query construction
step in Algorithm 5. Following this, we present the agnostic interactive proof
for $\mathsf{AC}^{0}[2]$ in Protocol 7, and finally prove its correctness.

Input: A string $w\in\\{0,1\\}^{n}$.

The Algorithm:

Let $S_{1},\dots,S_{L}$ be an $(nk+k,L,\log L)$-NW set design over the
universe $[m]$, where $m=O((nk)^{2})$. Each $S_{i}$ is of size $nk+k$ that
represents a query to $\mathsf{Amp}_{k}^{f}$, that in turn can be computed by
making $k$ queries to $f$ on the first $nk$ bits. Thus, each $S_{i}$ can be
partitioned into disjoint sets $S_{i1},\dots,S_{ik}$ of size $n$ and the set
$b(S_{i})$ of size $k$. By the promise of the set design, for any $i\neq j$,
and any $1\leq k^{\prime}\leq k,|S_{ik^{\prime}}\cap S_{j}|\leq\log L$ (since
$|S_{i}\cap S_{j}|\leq\log L$).

  1. 1.

Pick $i$ uniformly at random from $[L]$.

  2. 2.

Let $Q=\sum_{u=1}^{i-1}\sum_{v=1}^{k}2^{|S_{uv}\cap S_{i}|}$. Pick index
$(u^{*},v^{*})$ with probability $\frac{2^{|S_{u^{*}v^{*}}\cap S_{i}|}}{Q}$,
where $u^{*}\leq i-1$ and $v^{*}\leq k$.

  3. 3.

For each $1\leq j\leq m$, with $j\notin S_{i}\cup S_{u^{*}v^{*}}$, pick a
random bit $z_{j}$. For any $j\in S_{u^{*}v^{*}}\setminus S_{i}$, set $z_{j}$
to correspond with the respective bits from the input $w$.

  4. 4.

For each $1\leq u<i$ and $1\leq v\leq k$, generate all the $2^{|S_{uv}\cap
S_{i}|}$ strings that are consistent with the partial assignment to
$z|_{S_{uv}}$ made in the Step 3. Call each such set of strings as
$\hat{Q}_{uv}$.

Let $\hat{Q}=\bigcup_{u,v}\hat{Q}_{uv}\subset\\{0,1\\}^{n}$ be the set of all
queries to $f$.

  5. 5.

For each $1\leq u<i$, generate all the strings in $b(S_{u})$ that are
consistent with the partial assignment to $z|_{b(S_{u})\setminus S_{i}}$ in
Step 3. Call these strings as $\hat{\mathcal{Q}}_{b(S_{u})}$.

Let
$\hat{P}=\bigcup_{u}\left(\hat{Q}_{u1}\times\dots\times\hat{Q}_{uk}\times\hat{\mathcal{Q}}_{b(S_{u})}\right)$
be the set of all queries to $\mathsf{Amp}^{f}_{k}$.

Repeat these steps $\poly(L)$ many times using fresh randomness (similar to
the final step of Algorithm 5). Finally, output the union
$\mathcal{Q}\subset\\{0,1\\}^{n}$ of all the $\hat{Q}$’s that are queries to
$f$, as well as the union $\mathcal{P}\subset\\{0,1\\}^{nk+k}$ of all the
$\hat{P}$’s that are queries to $\mathsf{Amp}^{f}_{k}$.

Algorithm 6 Embedded NW-query construction algorithm
$\hat{\mathcal{A}}_{\mathsf{query}}$ for $\mathsf{Amp}_{k}^{f}$, where $f$ is
some $n$-variate Boolean function.

Function input. For function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, the
verifier has access to a random example oracle $\mathsf{Ex}(U_{n},f)$ that
returns samples from $(U_{n},f(U_{n}))$. The prover has query access to $f$.

Explicit inputs. $\delta>0$ and an encoding (as a circuit) of the tolerant
natural property $\mathcal{R}$ that is useful against
$\mathsf{AC}^{0}[2]$-circuits of depth $d$ and size
$u(n)=\mathsf{exp}(\Omega(n^{1/2d}))$ with tolerance $\tau(n)=1/n^{3}$.

Promise on the functional input.
$\mathsf{dist}(f,\mathsf{AC}^{0}[2])=\beta^{*}$, for some
$1/n^{\frac{\log(n)}{2}}<\beta^{*}<1/2$. The Interactive Proof:

  * •

Let $M=\log^{2}(n)/2$. For each $r$, where $2\leq r\leq M$, the interactive
proof does the following.

    1. 1.

Set $\beta_{r}(n)=1/2^{r}$. Let $G^{\mathsf{Amp}^{f}_{k}}$ be the NW-generator
with stretch $L=2^{O(\log^{4d+2}n)}$ and the amplification parameter
$k=\tau(\ell)/4\beta_{r}$, where $\ell=\log(L)$. Note that
$\tau(\ell)=1/\ell^{3}=1/O(\log^{12d+6}(n))$. Finally, let $q_{\max}$ be the
worst-case upper bound on the query complexity of the learning algorithm
$\mathcal{B}$ from Theorem 5.2, for any value of $\beta_{r}$.

    2. 2.

The verifier draws fresh labeled samples
$\\{(x_{r1},f(x_{r1})),\dots,(x_{rt},f(x_{rt}))\\}$ from the random example
oracle distributed according to $(U_{n},f(U_{n}))$, where $t$ is set to
$40/\delta\cdot q_{\max}\cdot\ln(M/\delta)$.

    3. 3.

For each $x_{rj}$ such that $j\in[t]$, the verifier does the following.

       * –

Runs $\hat{\mathcal{A}}_{\mathsf{query}}(x_{rj})$ to get a set of queries
$\mathcal{Q}_{rj}\subset\\{0,1\\}^{n}$ that has $x_{rj}$ embedded at a
randomly chosen point and another set of queries
$\mathcal{P}_{rj}\subset\\{0,1\\}^{nk+k}$.

       * –

Sends $\mathcal{Q}_{rj}$ to the Prover and receives the set
$\tilde{f}(\mathcal{Q}_{rj})$ consisting answers $\\{\tilde{f}(w)\mid
w\in\mathcal{Q}_{rj}\\}$.

       * –

Next, the verifier checks if $f(x_{rj})=\tilde{f}(x_{rj})$. If yes, the
verifier runs the rest of the learner $\mathcal{B}$ (or $\hat{\mathcal{B}}$)
using the natural property $\mathcal{R}$, the query set $\mathcal{P}_{rj}$ and
its answers on $\mathsf{Amp}^{f}_{k}$ computed using
$\tilde{f}(\mathcal{Q}_{rj})$. Let $h^{rj}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$
be the output of the learner. If not, the verifier rejects and outputs
‘$\bot$’.

    4. 4.

The verifier picks a hypothesis $h^{r}$ uniformly at random from the set
$\\{h^{rj}\\}_{j\in[t]}$ and adds it to the set of candidate hypothesis
$H_{\mathsf{final}}$.

  * •

The verifier picks
$W_{\mathsf{test}}=O\left(\frac{1}{\ell^{4}\beta_{M}^{2}}\cdot\ln\left(\frac{2M}{\delta}\right)\right)=n^{O(\log(n))}\log\left(\frac{2M}{\delta}\right)$
fresh labeled samples from the random example oracle. Next, for each candidate
hypothesis circuit $h^{r}$ in $H_{\mathsf{final}}$, the verifier estimates the
distance between $f$ and $h^{r}$ using these $W_{\mathsf{test}}$ samples,
i.e., number of samples $x_{j}$, for $j\in[W_{\mathsf{test}}]$, such that
$f(x_{j})\neq h^{r}(x_{j})$.

Finally, the verifier outputs the hypothesis
$h^{*}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ in $H_{\mathsf{final}}$ with the
smallest estimated distance amongst all the candidate hypotheses.

Protocol 7 Agnostic interactive proof for $\mathsf{AC}^{0}[2]$.

##### Completeness.

Firstly, observe that for every $\beta_{r}$ and every $j\in[t]$, the honest
prover answers each query in each set $\mathcal{Q}_{rj}$ correctly, i.e.,
$\tilde{f}(\mathcal{Q}_{rj})=f(\mathcal{Q}_{rj})$. In particular, for each
$x_{j}$, the verifier gets the correct value $f(x_{j})$ and thus, never
rejects any query set. We first state the following lemma about the size of
the query sets generated by the algorithm.

Now, suppose that for some $\mathcal{T}$, the true distance parameter
$\beta^{*}$ lies in the interval between
$\left(1/2^{\mathcal{T}+1},1/2^{\mathcal{T}}\right]$. Then we have,

######  Lemma 5.11.

With probability at least $1-\delta/2$, the hypothesis $h^{\mathcal{T}}\in
H_{\mathsf{final}}$ has error at most $2\ell^{4}\beta^{*}$, where the
probability is over the internal randomness of the verifier and samples taken
from the random example oracle in the $\mathcal{T}^{\text{th}}$ round (i.e.,
when the generator is instantiated using distance parameter
$1/2^{\mathcal{T}}$.

###### Proof.

Let $\mathcal{B}$ be the quasi-polynomial time agnostic learner using
membership queries for $\mathsf{AC}^{0}[2]$ over the uniform distribution from
Theorem 5.2. Moreover, let $\hat{\mathcal{B}}$ be the learner obtained by
sampling a uniformly random $w\in\\{0,1\\}^{n}$ and running
$\hat{\mathcal{A}}_{\mathsf{query}}(w)$ to generate the membership queries
made to $\mathsf{Amp}^{f}_{k}$ in $\mathcal{B}$, instead of
$\mathcal{A}_{\mathsf{query}}$. First, we observe that $\hat{\mathcal{B}}$
also satisfies the guarantees of the learner $\mathcal{B}$, because $w$ itself
is now being used as a source of randomness in the query construction.

From Corollary 5.7, since every $\beta_{r}\geq 1/n^{\log(n)}$, we see that
when $\ell=O(\log^{2d+1}(n\cdot n^{\log(n)})=O(\log^{4d+2}(n)$ , for every
$\beta_{r}\geq\beta^{*}$, $\hat{\mathcal{B}}$ outputs a hypothesis whose error
is at most $\ell^{4}\beta_{r}$. In other words, for every $j\in[t]$, given the
correct answers to the queries in the set $\mathcal{Q}_{\mathcal{T}j}$, it
outputs a hypothesis $h^{\mathcal{T}j}$ that errs on at most
$\ell^{4}\beta_{\mathcal{T}}$ fraction of the inputs, with probability at
least $1-\delta/20$ over its internal randomness.

From our choice of $t$ that is larger than $O(1/\delta^{2}\log(1/\delta))$,
using a Hoeffding concentration bound, at least $(1-\delta/5)t$ of the
hypotheses in $\\{h_{\mathcal{T}j}\\}_{j\in[t]}$ have error at most
$\ell^{4}\beta_{\mathcal{T}}$, with probability all but $\delta/4$. In other
words, with probability at least $1-\delta/5$, a hypothesis that is chosen
uniformly at random from the set $\\{h_{\mathcal{T},j}\\}_{j\in[t]}$ has error
at most $\ell^{4}\beta_{\mathcal{T}}$. Thus, the total failure probability
that $h_{\mathcal{T}}$ is not a good hypothesis is at most
$\delta/4+\delta/5<\delta/2$. Combined with the fact that
$\beta_{\mathcal{T}}\leq 2\beta^{*}$, $h^{\mathcal{T}}$ has error at most
$2\ell^{4}\beta^{*}$ and the claim follows. ∎

To summarise, using Lemma 5.11, we have established that with probability at
least $1-\delta/2$, there exists a hypothesis in $H_{\mathsf{final}}$ that has
error at most $2\ell^{4}\beta^{*}$.

Finally, we show that with probability at least $1-\delta/2$ over the choice
of $W_{\mathsf{test}}$ fresh samples in the final step, either
$h^{\mathcal{T}}$ or another hypothesis with error at most
$4\ell^{4}\beta^{*}$ is output by the verifier. Overall, this shows that our
agnostic interactive proof satisfies the completeness requirement, by showing
that with probability at least $1-\delta$ over its internal randomness and the
samples received during the interactive proof, the verifier outputs $h^{*}$
that has error at most $4\ell^{4}\beta^{*}$.

For this, observe that the verifier outputs $h^{*}$ such that
$\mathsf{dist}(h^{*},f)>4\ell^{4}\beta^{*}$, when either $h^{\mathcal{T}}$ has
a large error estimate on the $W_{\mathsf{test}}$ samples, or there exists a
hypothesis $h^{r}\in H_{\mathsf{final}}$ such that
$\mathsf{dist}(f,h^{r})>4\ell^{4}\beta$ but still has a smaller error estimate
on the $W_{\mathsf{test}}$ samples than $h^{\mathcal{T}}$.

In more detail, using Hoeffding’s concentration bound, the estimated error
between $h^{\mathcal{T}}$ and $f$ is larger than $3\ell^{4}\beta^{*}$, only
with probability at most $\delta/2M$, since our choice of $W_{\mathsf{test}}$
ensures that the estimate is made over at least
$O\left(\frac{1}{\ell^{4}\beta_{\mathcal{T}}^{2}}\cdot\ln\left(\frac{2M}{\delta}\right)\right)$
many samples. Next, for any hypothesis $h^{r}$ and $f$ such that
$\mathsf{dist}(f,h^{r})>4\ell^{4}\beta^{*}$, again using Hoeffding’s bound,
the estimated error of $h^{r}$ over the $W_{\mathsf{test}}$ samples is less
than $3\ell^{4}\beta^{*}$, with probability at most $\delta/2M$. Since the
number of such hypotheses is at most $M-1$, using a union bound, we see that
the probability that the verifier outputs $h^{*}$ such that
$\mathsf{dist}(h^{*},f)>4\ell^{4}\beta^{*}$ is at most
$\delta/2M+(M-1)\cdot\delta/2M\leq\delta/2$.

##### Soundness.

Recall that the generator $G^{\mathsf{Amp}^{f}_{k}}$ is constructed using an
$(nk+k,L,\log(L))$-NW set design $S_{1},\dots,S_{L}$, over the universe $[m]$.
Further, each $S_{i}$ can be partitioned into disjoint sets
$S_{i1},\dots,S_{ik}$ of size $n$ and $B_{i}$ of size $k$ (since the queries
are made to $\mathsf{Amp}^{f}_{k}$). By the promise of the set design, for any
$i\neq j$, and any $1\leq k^{\prime}\leq k,|b(S_{i})\cap S_{j}|\leq\log(L)$
and moreover, $|S_{ik^{\prime}}\cap S_{j}|\leq\log(L)$ (since $|S_{i}\cap
S_{j}|\leq\log(L)$).

Consider a run of the query construction algorithm
$\mathcal{A}_{\mathsf{query}}$ from Algorithm 5 for $\mathsf{Amp}^{f}_{k}$. An
important observation here is that for $i$ picked uniformly randomly from
$[L]$, $\mathcal{A}_{\mathsf{query}}$ generates random (possibly non-disjoint)
subcubes
$\mathcal{E}_{1,1},\dots,\mathcal{E}_{1,k},\dots,\mathcal{E}_{(i-1),1},\dots,\mathcal{E}_{(i-1),k}$
and only makes subcube membership queries over them (i.e., queries each
subcube completely in lexicographic order). Indeed, each $\mathcal{E}_{u,v}$
is the subcube obtained by generating all strings of length $n$ that are
consistent with the partial assignment obtained from the random bits set in
Step 2. Clearly, $\mathcal{A}_{\mathsf{query}}$ generates non-adaptive queries
to $\mathsf{Amp}^{f}_{k}$, which in turn also results in non-adaptive queries
to $f$.

We first prove the following result that characterizes the marginal
distribution of the $p^{\text{th}}$ query to $f$ generated by
$\mathcal{A}_{\mathsf{query}}$.

######  Lemma 5.12 (The reconstruction query distribution lemma).

Suppose that $\mathcal{A}_{\mathsf{query}}$ makes membership queries over
subcubes $\mathcal{E}_{1,1},\dots,\mathcal{E}_{(i-1),k}$ to
$\mathsf{Amp}^{f}_{k}$, for some $i\leq L$, using an $(nk+k,L,\log(L))$-set
design $(S_{1},\dots,S_{L})$.

Let $\mathcal{Q}$ be the query set for $f$ generated by
$\mathcal{A}_{\mathsf{query}}$ and
$\sum_{u=1}^{i-1}\sum_{v=1}^{k}2^{|S_{u,v}\cap S_{i}|}$ be its size. Then, for
any query index $p\in\left[\sum_{u=1}^{i-1}\sum_{v=1}^{k}2^{|S_{u,v}\cap
S_{i}|}\right]$, where $p\in\mathcal{E}_{u,v}$ for some $u\leq i-1$ and $v\leq
k$, and for any $w\in\\{0,1\\}^{n}$, the marginal distribution of
$\mathcal{Q}[p]$, the $p^{\text{th}}$-query, satisfies one of the two
properties.

  * •

$\Pr_{\mathcal{A}_{\mathsf{query}}}[\mathcal{Q}[p]=w]=0$, or

  * •

$\Pr_{\mathcal{A}_{\mathsf{query}}}[\mathcal{Q}[p]=w]=\frac{1}{2^{n-|S_{u,v}\cap
S_{i}|}}$.

Notation for the proof of Lemma 5.12: For any variables $x_{1},\dots,x_{n}$,
let $\rho:[n]\rightarrow\\{0,1,*\\}$ be a restriction over the variables
obtained by setting $x_{i}=\rho(i),\forall i\in[n]$, where “$\rho(i)=*$”
denotes that $x_{i}$ is left free (i.e., unset).

For any restriction $\rho$ and subcube $\mathcal{E}\subseteq\\{0,1\\}^{n}$, we
say that $\mathcal{E}$ is generated by the restriction $\rho$, if it is the
subcube given by the set of all $n$-length binary strings consistent with
$\rho$ on the indices in $\rho^{-1}(\\{0,1\\})$. Note that the size of
$|\mathcal{E}|=2^{|\rho^{-1}(*)|}$. For notational simplicity, for the rest of
the proof we index the subcubes queried over by
$\mathcal{A}_{\mathsf{query}}$, with a single value from $1\leq j\leq N$ in a
natural way, where $N=(i-1)k$.

Let $z$ be the random bits used by $\mathcal{A}_{\mathsf{query}}$ to generate
the queries (i.e., the seed of the NW-generator). For any $1\leq j\leq N$,
define $\widehat{S_{j}}$ as the set $S_{j}\setminus S_{i}$. For any $1\leq
j\leq N$, the subcube $\mathcal{E}_{j}$ is generated by the random restriction
$\rho_{j}:[n]\rightarrow\\{0,1,*\\}$, such that $\rho_{j}[a]=z_{a}$, if
$a\in\widehat{S_{j}}$ and $\rho_{j}[a]=*$, if $a\in S_{j}\cap S_{i}$. In other
words, the random bits in $\rho_{j}^{-1}(\\{0,1\\})$ generate a random subcube
$\mathcal{E}_{j}$. From the properties of the set design, we see that
$|\rho_{j}^{-1}(*)|\leq\log(L)$ (in the degenerate case,
$|\rho_{j}^{-1}(*)|=0$ and the size of $\mathcal{E}_{j}$ is just $1$).

For any restriction $\rho$ and any string $r\in\\{0,1\\}^{n-|\rho^{-1}(*)|}$,
we abuse notation by using $\rho=r$ to denote the variables in
$\rho^{-1}(\\{0,1\\})$ being set to $r$ in the natural way. For every $1\leq
j\leq N$, denote by $\vec{\rho}^{(j)}$ as the tuple of restrictions
$(\rho_{j},\dots,\rho_{N})$. In particular, the tuple of all restrictions
$(\rho_{1},\dots,\rho_{N})$ is given by $\vec{\rho}^{(1)}$. For any tuple of
strings $\vec{r}^{(j)}=(r_{j},\dots,r_{N})$, where each
$r_{a}\in\\{0,1\\}^{n-|\rho_{a}^{-1}(*)|}$, we say that
$\vec{\rho}^{(j)}=\vec{r}^{(j)}$, if $\rho_{a}=r_{a}$ for every $j\leq a\leq
N$.

In a similar vein, for every $1\leq j\leq i-1$, let
$\sigma_{j}:[k]\rightarrow\\{0,1,*\\}$ be random restriction generated by
projecting $z$ over the set $B_{j}$ ($\sigma_{j}$ is set to ‘$*$’ on every
element in $B_{j}\setminus S_{i}$). It is worth recalling that the membership
queries to $f$ are only made on the subcubes induced by
$\rho_{1},\dots,\rho_{N}$. For any tuple of strings
$\vec{u}^{(j)}=(u_{j},\dots,u_{i-1})$, where each
$u_{a}\in\\{0,1\\}^{k-|\sigma_{a}^{-1}(*)|}$, we say that
$\vec{\sigma}^{(j)}=\vec{u}^{(j)}$, if $\sigma_{a}=r_{a}$ for every $j\leq
a\leq i-1$.

###### Proof of Lemma 5.12.

Let $\mathcal{E}_{j^{*}}\in[N]$ be the subcube that contains the
$p^{\text{th}}$ query and let $\mathcal{E}_{j^{*}}$ be generated by the
restriction $\rho_{j^{*}}:[n]\rightarrow\\{0,1*\\}$ (this is the same as
$\mathcal{E}_{uv}$ in the other scheme of indexing).

Recall that for each $1\leq j\leq N$, $\mathcal{A}_{\mathsf{query}}$ only
makes subcube queries, by going over all possible assignments to
$\rho_{j}^{-1}(*)$ in lexicographic order. Suppose that the variables in
$\rho_{j^{*}}^{-1}(*)$ are fixed with the string
$\alpha\in\\{0,1\\}^{|\rho_{j^{*}}^{-1}(*)|}$, corresponding to the location
of $p$ within the lexicographic ordering of the elements in
$\mathcal{E}_{j^{*}}$.

Now, if $w$ restricted to $\rho_{j^{*}}^{-1}(*)$ is not $\alpha$, then the
$p^{\text{th}}$ query can never be $w$, i.e.,
$\Pr_{\mathcal{A}_{\mathsf{query}}}[\mathcal{Q}[p]=w]=0$. Thus, for the rest
of this proof, we assume that $w$ restricted to $\rho_{j^{*}}^{-1}(*)$ is
$\alpha$, and refer to $w$ with the tuple
$\left(w|_{\hat{S}_{j^{*}}},\alpha\right)$, since $\rho_{j^{*}}^{-1}(*)$
contains the indices in $\hat{S_{j^{*}}}=S_{j^{*}}\cap S_{i}$.

Let $\mathcal{Q}^{-p}$ be the set of queries
$\mathcal{Q}\setminus\mathcal{Q}[p]$. We have

$\begin{split}\Pr_{\mathcal{A}_{\mathsf{query}}}[\mathcal{Q}[p]=w]=\sum_{\mathcal{Y}\in\left(\\{0,1\\}^{n}\right)^{Q-1}}&\Pr_{z}[\mathcal{Q}[p]=w\text{
and }\mathcal{Q}^{-p}=\mathcal{Y}]\\\
=\sum_{\vec{r}^{(1)},\vec{u}^{(1)}}\Pr_{z}&\left[w=\left(z|_{\hat{S}_{j^{*}}},\alpha\right)\big{|}\vec{\rho}^{(1)}=\vec{r}^{(1)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\right]\cdot\Pr_{z}\left[\vec{\rho}^{(1)}=\vec{r}^{(1)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\right]\\\
=\sum_{\vec{r}^{(1)},\vec{u}^{(1)}}\Pr_{z}&\left[w=\left(z|_{\hat{S}_{j^{*}}},\alpha\right)\big{|}\vec{\rho}^{(1)}=\vec{r}^{(1)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\right]\\\
&\cdot\Pr_{z}\left[\vec{\rho}^{(2)}=\vec{r}^{(2)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\big{|}\rho_{1}=r_{1}\right]\cdot\Pr_{z}\left[\rho_{1}=r_{1}\right]\\\
=\sum_{r_{1}\in\\{0,1\\}^{n-m_{1}}}&\frac{1}{2^{n-m_{1}}}\cdot\sum_{\vec{r}^{(2)},\vec{u}^{(1)}}\Pr_{z}\left[w=\left(z|_{\hat{S}_{j^{*}}},\alpha\right)\big{|}\vec{\rho}^{(1)}=\vec{r}^{(1)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\right]\\\
&\cdot\Pr_{z}\left[\vec{\rho}^{(2)}=\vec{r}^{(2)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\big{|}\rho_{1}=r_{1}\right]\\\
\end{split}$

The second expression holds because the query algorithm only makes subcube
queries, each of which is represented by a restrictions
$\rho_{1},\dots,\rho_{N}$, and is possibly dependent on
$\sigma_{1},\dots,\sigma_{i-1}$ by virtue of the set design. On the other
hand, the final expression comes by noting that the restriction $\rho_{1}$ is
the random string $z|_{\hat{S_{1}}}$ by definition, and thus,
$m_{1}=|S_{1}\cap S_{i}|$.

Next, observe that by setting $\rho_{1}$ to $r_{1}$, in turn we fix
$z|_{\hat{S_{1}}}$ to be $r_{1}$. Let $\mathsf{cons}(r_{1})$ be the set of
strings $r_{2}$ of length $n-|\hat{S_{2}}|$ such that when $\rho_{1}=r_{1}$,
$r_{2}$ is consistent with the values in $z$ fixed previously by $r_{1}$ with
respect to the underlying set design. In other words, the projection of
$r_{2}$ onto the indices in $\widehat{S_{1}\cap S_{2}}=(S_{1}\cap
S_{2})\setminus S_{i}$ is equal to $z|_{\widehat{S_{1}\cap S_{2}}}$.

Let $m_{2}=|S_{2}\cap S_{i}|+|\widehat{S_{1}\cap S_{2}}|$. We have

$\begin{split}\sum_{r_{1}\in\\{0,1\\}^{n-m_{1}}}\frac{1}{2^{n-m_{1}}}\cdot\sum_{\vec{r}^{(2)},\vec{u}^{(1)}}&\Pr_{z}\left[w=\left(z|_{\hat{S}_{j^{*}}},\alpha\right)\big{|}\vec{\rho}^{(1)}=\vec{r}^{(1)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\right]\\\
&\cdot\Pr_{z}\left[\vec{\rho}^{(2)}=\vec{r}^{(2)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\big{|}\rho_{1}=r_{1}\right]\\\
=\sum_{r_{1}\in\\{0,1\\}^{n-m_{1}}}\frac{1}{2^{n-m_{1}}}\cdot\sum_{\vec{r}^{(2)},\vec{u}^{(1)}}&\Pr_{z}\left[w=\left(z|_{\hat{S}_{j^{*}}},\alpha\right)\big{|}\vec{\rho}^{(1)}=\vec{r}^{(1)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\right]\\\
&\cdot\Pr_{z}\left[\vec{\rho}^{(3)}=\vec{r}^{(3)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\big{|}\rho_{1}=r_{1}\land\rho_{2}=r_{2}\right]\cdot\Pr_{z}\left[\rho_{2}=r_{2}|\rho_{1}=r_{1}\right]\\\
\end{split}$

$\begin{split}=\sum_{r_{1}\in\\{0,1\\}^{n-m_{1}}}\frac{1}{2^{n-m_{1}}}\cdot\sum_{r_{2}\in\mathsf{cons}(r_{1})}\frac{1}{2^{n-m_{2}}}\cdot\sum_{\vec{r}^{(3)}}&\Pr_{z}\left[w=\left(z|_{\hat{S}_{j^{*}}},\alpha\right)\big{|}\vec{\rho}^{(1)}=\vec{r}^{(1)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\right]\\\
&\cdot\Pr_{z}\left[\vec{\rho}^{(3)}=\vec{r}^{(3)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\big{|}\rho_{1}=r_{1}\land\rho_{2}=r_{2}\right]\\\
\end{split}$

The last expression follows from the fact that for any
$r_{2}\in\mathsf{cons}(r_{1})$,
$\Pr_{z}\left[\rho_{2}=r_{2}|\rho_{1}=r_{1}\right]$ is just the probability
that the random bits in $z|_{\hat{S_{2}}}=r_{2}$, given that the
$z|_{\hat{S_{1}}\cap\hat{S_{2}}}$ is already fixed using the corresponding
bits from $r_{1}$. Given this, we see that
$\Pr_{z}\left[\rho_{2}=r_{2}|\rho_{1}=r_{1}\right]=1/2^{n-m_{2}}$.171717Note
that since $S_{1},\dots,S_{k}$ are all mutually disjoint, none of the
$r_{j}$’s have any bits fixed by $r_{1},\dots,r_{j-1}$. The same argument
holds for $B_{1}$ with respect to $S_{1},\dots,S_{k}$ too. We maintain full
generality in the expressions above for ease of exposition. Indeed, for any
$0\leq a\leq i-2$ any string amongst $r_{ak+1},\dots,r_{(a+1)k)}$ may have
some bits fixed by any of the previous $r_{j}$’s or the $u_{j}$’s.

We proceed in this iterative fashion, where for any $j\leq N$, we look at the
effect of the restrictions
$\rho_{1},\dots,\rho_{k},\sigma_{1},\rho_{k+1},\dots,\rho_{2k},\sigma_{2},\rho_{2k+1},\dots,\rho_{\lfloor
j/k\rfloor\cdot k},\sigma_{\lfloor j/k\rfloor},\rho_{\lfloor j/k\rfloor\cdot
k+1},\dots,\rho_{j-1}$ on the $p^{\text{th}}$ query. The reason for this comes
from the nature of the set design for $\mathsf{Amp}^{f}_{k}$ \- any set
amongst $S_{ak+1}\dots,S_{(a+1)k},B_{a}$ could have an overlap with any of the
sets $S_{1},\dots,S_{ak}$ or $B_{1},\dots,B_{a-1}$.

Thus, we define for any $j$, $\mathsf{cons}(r_{1},\dots,r_{j-1})$ as the set
of strings $r_{j}$ such that the bits fixed in $z$ by $r_{1},\dots,r_{j-1}$
and $u_{1},\dots,u_{\lfloor j/k\rfloor}$ are consistent with the projection of
$r_{j}$ onto the indices in
$\hat{S}_{j}\cap\left(\left(\bigcup_{a=1}^{j-1}\hat{S}_{a}\right)\cup\left(\bigcup_{a=1}^{\lfloor
j/k\rfloor}\hat{B}_{a}\right)\right)$.

Moreover, define $m_{j}=|S_{j}\cap
S_{i}|+\bigg{|}\left(\bigcup_{a=1}^{j-1}\hat{S}_{a}\right)\cap\hat{S}_{j}\bigg{|}+\bigg{|}\left(\bigcup_{a=1}^{\lfloor
j/k\rfloor}\hat{B}_{a}\right)\cap\hat{S}_{j}\bigg{|}$, as the number of bits
in $\hat{S_{j}}$ that overlap with the indices previously fixed in each
$\hat{S}_{a}$. Similarly, we define $m^{\prime}_{j}=|B_{j}\cap
S_{i}|+\bigg{|}\left(\bigcup_{a=1}^{jk}\hat{S}_{a}\right)\cap\hat{B}_{j}\bigg{|}+\bigg{|}\left(\bigcup_{a=1}^{j-1}\hat{B}_{a}\right)\cap\hat{B}_{j}\bigg{|}$,
as the number bits in $B_{j}$ that overlap with the indices previously fixed
in each $\hat{B}_{a}$. Of course, in the scenario that all the bits in
$z|_{\hat{S}_{j}}$ are fixed by $\rho_{1},\dots,\rho_{j-1}$ and
$\sigma_{1},\dots,\sigma_{\lfloor j/k\rfloor}$, then $m_{j}=n$, and
$\mathsf{cons}(r_{1},\dots,r_{j-1})$ contains only one string.

We repeat the above calculations $N-1$ times and finally, count over all
mutually consistent ways $z$ can be fixed by $r_{1},\dots,r_{N-1}$ and
$u_{1},\dots,u_{i-1}$. We have

$\begin{split}\Pr_{\mathcal{A}_{\mathsf{query}}}[\mathcal{Q}[p]=w]=\prod_{a=1}^{N-1}\left(\frac{1}{2^{n-m_{a}}}\right)\cdot&\prod_{a=1}^{i-1}\left(\frac{1}{2^{k-m^{\prime}_{a}}}\right)\sum_{\begin{subarray}{c}r_{1}\in\\{0,1\\}^{n-m_{1}}\\\
r_{2}\in\mathsf{cons}(r_{1})\\\ \cdots\\\
r_{N}\in\mathsf{cons}(r_{1},\dots,r_{N-1},\\\
u_{1},\dots,u_{i-1})\end{subarray}}\Pr_{z}\left[w=\left(z|_{\hat{S}_{j^{*}}},\alpha\right)\big{|}\vec{\rho}^{(1)}=\vec{r}^{(1)}\land\vec{\sigma}^{(1)}=\vec{u}^{(1)}\right]\\\
=\prod_{a=1}^{N-1}\left(\frac{1}{2^{n-m_{a}}}\right)\cdot&\prod_{a=1}^{i-1}\left(\frac{1}{2^{k-m^{\prime}_{a}}}\right)\cdot\sum_{\begin{subarray}{c}r_{1}\in\\{0,1\\}^{n-m_{1}}\\\
r_{2}\in\mathsf{cons}(r_{1})\\\ \cdots\\\
r_{N}\in\mathsf{cons}(r_{1},\dots,r_{N-1},u_{1},\dots,u_{i-1})\end{subarray}}\frac{1}{2^{|\hat{S}_{j^{*}}|}}\\\
\end{split}$

The last line follows from the fact that for each
$r_{j^{*}}\in\\{0,1\\}^{n-m_{j^{*}}}$, the entirety of $z|_{S_{j}^{*}\setminus
S_{i}}$ is fixed by $r_{1},\dots,r_{j^{*}}$ and the probability that
$w=z|_{S_{j^{*}}\setminus S_{i}}$ is uniform over
$\\{0,1\\}^{|{S_{j^{*}}\setminus S_{i}}|}$.

Since for each $j$, the size of the set $\mathsf{cons}(r_{1},\dots,r_{j})$ is
$2^{n-m_{j}}$, we have that the probability the $p^{\text{th}}$-query is the
string $w$ is just $\frac{1}{2^{|S_{j^{*}}\setminus S_{i}|}}$, which is
nothing but $\frac{1}{2^{n-|S_{j^{*}}\cap S_{i}|}}$. ∎

We have the following observation about the restrictions on strings sampled
from the uniform distribution.

######  Proposition 5.13.

For any restriction $\rho:[n]\rightarrow\\{0,1,*\\}$ and any
$w\in\\{0,1\\}^{n}$ sampled from $\mathcal{U}_{n}$, the marginal distribution
of $w|_{\rho}$ is the uniform distribution over strings of length
$n-|\rho^{-1}(*)|$.

We now prove that Protocol 7 satisfies the soundness requirements. To this
end, consider round $r$ and uniform random example $x_{rj}\in\\{0,1\\}^{n}$,
such that $\hat{\mathcal{A}}_{\mathsf{query}}$ constructs query set
$\mathcal{Q}_{rj}$ of size $|\mathcal{Q}_{rj}|$, that has $x_{rj}$ embedded at
a uniformly random query index. The malicious prover can look at the query
distribution of any $q^{\text{th}}$-query in $\mathcal{Q}_{rj}$, where $q$
corresponds to a query in some subcube $\mathcal{E}_{u,v}$ generated by the
restriction $\rho_{u,v}$ and try to infer if this was the example embedded by
the verifier in $\mathcal{Q}_{rj}$.

From Lemma 5.12 and Proposition 5.13, for every query index $q$ that
corresponds to a query in the subcube $\mathcal{E}_{u,v}$, the marginal
distribution of the $q^{\text{th}}$-query made by
$\mathcal{A}_{\mathsf{query}}$ (the true query construction algorithm from
Theorem 5.2) is the same as that of the uniform distribution (i.e., the
distribution over the samples) over $n$-length strings restricted on to
$\rho_{u,v}$. This means that the malicious prover cannot distinguish whether
the $q^{\text{th}}$-query came from a subcube induced by a restriction
obtained from $\mathcal{A}_{\mathsf{query}}$’s internal randomness, or came
from a subcube induced by a restriction obtained by embedding $x_{rj}$. Thus,
the prover has no advantage in picking a particular query with respect to
which it cheats.181818By cheating, we mean that the malicious prover answers
correctly only on the query it believes to be as the embedded random example
and lies on any other query which the verifier does not check. In other words,
the best the malicious prover can do is pick a subcube $\mathcal{E}_{u,v}$ at
random with probability $|\mathcal{E}_{u,v}|/|\mathcal{Q}_{rj}|$.

Furthermore, any point in $\mathcal{E}_{u,v}$ has equal likelihood of being
the embedded random example and thus, the malicious prover has no advantage
over randomly guessing an element of $\mathcal{E}_{u,v}$. Put together, the
malicious prover gains no advantage over picking a query uniformly at random
from $[|\mathcal{Q}_{rj}|]$ and cheating with respect to it.

For any $r\leq M$, define $\mathcal{W}_{r}$ as the number of query sets
$\mathcal{Q}_{r,j}$ over which the prover responds dishonestly on at least one
query in the set, i.e., let

$\mathcal{W}_{r}=\\{j\in[t]\mid\exists w\in\mathcal{Q}_{rj}\text{ such that
}\tilde{f}(w)\neq f(w)\\}$

We finish our analysis by considering the following 2 cases based on the value
of $\mathcal{W}_{r}$.

  * •

Case 1: There exists $r$ such that $|\mathcal{W}_{r}|>\ln(M/\delta)q_{\max}$.
Then, for the $r^{\text{th}}$ round, we have

$\begin{split}\Pr\left[\forall\mathcal{Q}_{r,j}\in\mathcal{W}_{r},\text{verifier
accepts
}\tilde{f}(\mathcal{Q}_{r,j})\right]&=\Pi_{j\in\mathcal{W}_{r}}\left(1-\frac{1}{|\mathcal{Q}_{rj}|}\right)\\\
&\leq\left(1-\frac{1}{q_{\max}}\right)^{|\mathcal{W}_{r}|}\leq
e^{-|\mathcal{W}_{r}|/q_{\max}}\leq\delta/M\\\ \end{split}$

The first inequality follows from Corollary 5.7 as $|\mathcal{Q}_{rj}|\leq
q_{\max}$, for all $r\leq M$ and $j\in[t]$. Using a union bound over the $M$
rounds, we see that with probability $1-\delta$, any prover gets caught by the
verifier if it lies on at least $\ln(M/\delta)q_{\max}$ of the query sets in
some round.

  * •

Case 2: For every $r\leq M$, $|\mathcal{W}_{r}|\leq\ln(M/\delta)q_{\max}$.
Again, let $\mathcal{T}$ be the value such that $\beta^{*}$ lies in the
interval $\left(1/2^{\mathcal{T}+1},1/2^{\mathcal{T}}\right]$. In particular,
$|\mathcal{W}_{\mathcal{T}}|\leq\ln(M/\delta)q_{\max}$ and the fraction of
query sets over which the prover cheats is at most
$|\mathcal{W}_{\mathcal{T}}|/t\leq\delta/40$.

For each query set $\mathcal{Q}_{\mathcal{T}j}$ such that
$j\in[t]\setminus\mathcal{W}_{\mathcal{T}}$, the prover answers correctly on
every query in the set, and in turn the verifier computes a hypothesis
$h^{\mathcal{T}j}$ that errs on at most $\ell^{4}\beta_{\mathcal{T}}$ fraction
of the inputs, with probability at least $1-\delta/20$ over its internal
randomness. Let $\mathcal{Y}$ be the number of hypotheses in
$\\{h_{\mathcal{T}j}\\}_{j\in[t]\setminus\mathcal{W}_{\mathcal{T}}}$ that have
error at most $\ell^{4}\beta_{\mathcal{T}}$ (i.e., are “good” hypotheses).
Again, since the number of faithful query sets (i.e.,
$t-|\mathcal{W}_{\mathcal{T}}|$) is larger than
$O(1/\delta^{2}\log(1/\delta))$, using a Hoeffding concentration bound, the
event $\mathcal{Y}>(1-\delta/5)(t-|\mathcal{W}_{\mathcal{T}}|)$ occurs with
probability all but $\delta/4$.

In such a case, the probability that a uniformly randomly chosen hypothesis
$h_{\mathcal{T},j^{*}}$ from the set $\\{h_{\mathcal{T},j}\\}_{j\in[t]}$ is
good is given by

$\begin{split}\Pr_{\stackrel{{\scriptstyle
j^{*}\sim[t]}}{{V}}}[h_{\mathcal{T}j^{*}}\text{ is
bad}]\leq&\Pr_{V}[h_{\mathcal{T}j^{*}}\text{ is bad}\mid
j^{*}\in\mathcal{W}_{\mathcal{T}}]\cdot\Pr_{j^{*}\sim[t]}[j^{*}\in\mathcal{W}_{\mathcal{T}}]+\Pr_{V}[h_{\mathcal{T}j^{*}}\text{
is bad}\mid j^{*}\notin\mathcal{W}_{\mathcal{T}}]\\\
\leq&\Pr_{V}[h_{\mathcal{T}j^{*}}\text{ is bad}\mid
j^{*}\in\mathcal{W}_{\mathcal{T}}]\cdot\Pr_{j^{*}\sim[t]}[j^{*}\in\mathcal{W}_{\mathcal{T}}]\\\
&+\Pr_{V}[h_{\mathcal{T}j^{*}}\text{ is bad}\mid
j^{*}\notin\mathcal{W}_{\mathcal{T}}\land\mathcal{Y}>(1-\delta/5)(t-|\mathcal{W}_{r}|)]\cdot\Pr_{V}[\mathcal{Y}>(1-\delta/5)(t-|\mathcal{W}_{r}|)]\\\
&+\Pr_{V}[h_{\mathcal{T}j^{*}}\text{ is bad}\mid
j^{*}\notin\mathcal{W}_{\mathcal{T}}\land\mathcal{Y}\leq(1-\delta/5)(t-|\mathcal{W}_{r}|)]\cdot\Pr_{V}[\mathcal{Y}\leq(1-\delta/5)(t-|\mathcal{W}_{r}|)]\\\
\leq&\delta/40+\delta/5+\delta/4\\\ <&\delta/2\end{split}$

The third inequality comes from the fact that if
$\mathcal{Y}>(1-\delta/5)(t-|\mathcal{W}_{\mathcal{T}}|)$, then the number of
bad hypotheses in
$\\{h_{\mathcal{T}j}\\}_{j\in[t]\setminus\mathcal{W}_{\mathcal{T}}}$ is given
by the random variable
$t-\mathcal{W}_{\mathcal{T}}-\mathcal{Y}\leq(t-\mathcal{W}_{\mathcal{T}})\delta/5$,
and that the probability of the event
$\mathcal{Y}\leq(1-\delta/5)(t-|\mathcal{W}_{r}|)$ is at most $\delta/4$.

Combined with the fact that $\beta_{\mathcal{T}}\leq 2\beta^{*}$, with
probability at least $1-\delta/2$, there exists a hypothesis in
$H_{\mathsf{final}}$ that has error at most $2\ell^{4}\beta^{*}$. The rest of
the analysis is identical to that of the completeness case, and we conclude
that the verifier outputs a hypothesis that has error at most
$4\ell\beta^{*}$, with probability $1-\delta$ over its internal randomness.

##### Complexity of the interactive proof.

From Corollary 5.7, we see that $q_{\max}=\poly(L)\leq 2^{O(\log^{4d+2}n)}$.
Thus, the proof complexity and the query complexity of the PAC-verification
protocol are both at most $n\cdot q_{\max}\cdot q_{\max}\cdot M\leq
2^{O(\log^{4d+2}n)}$. Similarly, the verifier running time is also given by
$\poly(L)\cdot q_{\max}\cdot M+O(W_{\mathsf{test}}\cdot\poly(L))\leq
2^{O(\log^{4d+2}n)}$. Finally, the honest prover just answers the queries to
$f$ it is asked for, and thus runs in time at most $t\cdot q_{\max}\cdot M\leq
2^{O(\log^{4d+2}n)}$.

∎

##### The case of $\mathsf{AC}^{0}[p]$, for every prime $p>2$

We construct an interactive proof for agnostic learning $\mathsf{AC}^{0}[p]$,
for any prime $p>2$, follows an identical strategy as the case of
$\mathsf{AC}^{0}[2]$, by building off Theorem 5.8. We omit the proof details
here.

######  Theorem 5.3.

For prime $p>2$, let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be any function
such that $\mathsf{opt}(f,\mathsf{AC}^{0}[p])>1/n^{\frac{\log(n)}{2}}$. Then,
$\mathsf{AC}^{0}[p][\poly(n)]$ is $(O(\log^{16pd+8p}(n)),1/10)$-agnostic
verifiable over the uniform distribution with the following parameters.

${\left[{\small\begin{array}[]{r l}\textsf{input access
type:}&\enspace{\textsf{random examples}}\\\ \textsf{sample/query
complexity:}&\enspace{\exp{(O(\log^{4pd+2p}(n)))}}\\\ \textsf{communication
complexity:}&\enspace{\exp{(O(\log^{4pd+2p}(n)))}}\\\ \textsf{round
complexity:}&\enspace{\textsf{proof only}}\\\ \textsf{verifier's running
time:}&\enspace{\exp{(O(\log^{4pd+2p}(n)))}}\\\ \textsf{prover's running
time:}&\enspace{\exp{(O(\log^{4pd+2p}(n)))}}\\\ \end{array}}\right]}$

##### Tolerant Natural Properties Imply PAC-verification

We finally show that for any typical circuit classes $\mathcal{C}$,
$(1/2-1/\poly(n))$-tolerant natural properties against $\mathcal{C}$ imply
PAC-verification protocols for $\mathcal{C}$, that use sub-exponentially many
random examples. This builds off the learner from Lemma 5.9.

######  Theorem 5.4.

Let $\mathcal{R}$ be a $(1/2-1/\poly(n))$-tolerant natural property useful
against $\mathcal{C}[\poly(n)]$, where $\mathcal{C}$ is any circuit class that
contains $\mathsf{AC}^{0}[2]$.

Then, for any $a\geq 1$ and $\gamma>0$, such that
$\mathsf{dist}(f,\mathcal{C}[n^{a}])=\beta^{*}\geq\frac{1}{n^{2a\gamma}}$,
$\mathcal{C}[\poly(n)]$ is $(O(n^{\gamma}),1/10)$-agnostic verifiable over the
uniform distribution with the following parameters.

${\left[{\small\begin{array}[]{r l}\textsf{input access
type:}&\enspace{\textsf{random examples}}\\\ \textsf{sample/query
complexity:}&\enspace{2^{O(n^{\gamma})}}\\\ \textsf{communication
complexity:}&\enspace{2^{O(n^{\gamma})}}\\\ \textsf{round
complexity:}&\enspace{\textsf{proof only}}\\\ \textsf{verifier's running
time:}&\enspace{2^{O(n^{\gamma})}}\\\ \textsf{prover's running
time:}&\enspace{2^{O(n^{\gamma})}}\\\ \end{array}}\right]}$

###### Proof sketch.

This interactive proof also follows a similar strategy as above. Worth
highlighting here is that the query construction still generates all strings
in a set of subcubes based on the NW-set design. However, each of the
$2^{|\mathcal{E}_{u,v}|}$ vectors in a subcube $\mathcal{E}_{u,v}$, where
$1\leq u\leq i-1$ and $1\leq v\leq k$, are added to the same output of
$[\mathsf{PI}(u,z_{2})]_{v}$ (i.e., the $v^{\text{th}}$ block of
$\mathsf{PI}(u,z_{2})$ of length $n$) to generate the actual set of queries to
$\mathsf{Amp}^{f}_{k}$.

The completeness analysis remains unchanged. On the other hand, even if the
malicious prover looks at each query and finds the output of
$\mathsf{PI}(u,z_{2})$ that is added to it, by Lemma 5.12, the query marginal
of each query is still indistinguishable from the distribution of the embedded
random example projected onto the indices of the subcube corresponding to the
query. Thus, the analysis extends to this case and shows that the interactive
proof satisfies the soundness requirement. ∎

##  6 PAC-Verification for Juntas

In this section we will use our general agnostic verification techniques from
Section 3 to obtain IPs for the class of juntas. We start by presenting an
interactive protocol in Section 6.1 for learning juntas with membership
queries. Following that, in Section 6.2, we prove the formal version of
Theorem 1.3:

######  Theorem 6.1 (Formal version of Theorem 1.3).

The class of $k$-juntas $\Junta_{n,k}$ is $(\epsilon,\delta)$-PAC Verifiable
with respect to the uniform distribution with random examples with the
following parameters:

${\left[{\small\begin{array}[]{r l}\textsf{input access
type:}&\enspace{\textsf{random examples}}\\\ \textsf{sample/query
complexity:}&\enspace{2^{k}\cdot\poly(k,1/\epsilon)\cdot\log^{2}(1/\delta)}\\\
\textsf{communication
complexity:}&\enspace{n\cdot\poly(2^{k},1/\epsilon,\log(1/\delta))}\\\
\textsf{round complexity:}&\enspace{3}\\\ \textsf{verifier's running
time:}&\enspace{\poly(n,2^{k^{2}},1/\epsilon^{k},1/\delta^{k})}\\\
\textsf{prover's running
time:}&\enspace{\poly(n^{k},2^{k},1/\epsilon,\log(1/\delta))}\\\
\end{array}}\right]}\enspace.$

###  6.1 PAC-Verification of Juntas with Membership Queries

Our basic plan for proving Theorem 6.2 will be to show the existence of a
distance estimator for the class $\Junta_{n,k}$, and then apply our general IP
from Theorem 3.1.

######  Theorem 6.2.

The class of $k$-juntas $\Junta_{n,k}$ is $(\epsilon,\delta)$-PAC Verifiable
with respect to the uniform distribution with membership queries with the
following parameters:

${\left[{\small\begin{array}[]{r l}\textsf{input access
type:}&\enspace{\textsf{membership queries}}\\\ \textsf{sample/query
complexity:}&\enspace{2^{k}\cdot\poly(k,1/\epsilon)\cdot\log(1/\delta)}\\\
\textsf{communication complexity:}&\enspace{k\log(n)+2^{k}}\\\ \textsf{round
complexity:}&\enspace{\textsf{proof only}}\\\ \textsf{verifier's running
time:}&\enspace{\poly(n,2^{k^{2}},1/\epsilon^{k},1/\delta^{k})}\\\
\textsf{prover's running
time:}&\enspace{\poly(n^{k},2^{k},1/\epsilon,\log(1/\delta))}\\\
\end{array}}\right]}\enspace.$

######  Proof of Theorem 6.2.

[DMN19] show the existence of $(c_{u},c_{\ell})$-noise tolerant test with
query complexity $2^{k}\cdot\poly(k,1/\left|c_{u}-c_{\ell}\right|)$ for every
$1/2>c_{u}>c_{\ell}\geq 0$. From 2.6 it immediately follows that the class of
$k$-juntas $\Junta_{n,k}$ has an $(\epsilon,\delta)$-distance estimator with
query complexity
$q(\epsilon,\delta)=2^{k}\cdot\poly(k,1/\epsilon)\cdot\log(1/\delta)$. Indeed
the constraint $c_{u}<1/2$ is not an issue for transforming this test into a
distance estimator since $\Junta_{n,k}$ is closed under complement and any
function $f$ has distance at most $1/2$ from this class.

Now that we have an $(\epsilon,\delta)$-distance estimator for $k$-juntas,
applying Theorem 3.1 will give an IP for the class $\Junta_{n,k}$ with the
same query complexity $q(\epsilon/6,\delta/2)$, with additional
$q_{\mathsf{CB}}(\epsilon/6,\delta/2)$ random samples. The verifier’s running
time is inherited from the distance estimator of [DMN19], and the honest
prover’s running time is determined by running a learning algorithm as
discussed in [HS23]. ∎

###  6.2 PAC-Verification of Juntas with Random Examples

Our IP construction for agnostically verifying class of juntas uses the
tolerant test for this class introduced in [DMN19]. Our goal is to transform
this protocol into a protocol where verifier uses only random examples. Thus
we need to argue that the queries of the tolerant test admit the property of
“constructing query set around a random query point” (in the sense of Theorem
3.2).

In this section we define two types of query patterns for which it is possible
to construct membership query sets, and we further argue that all the queries
of the junta’s tolerant test are of these form.

######  Definition 6.1 (Linear Query Pattern).

Let $A\sim\mathbb{F}_{2}^{n\times k}$ be a uniformly random matrix, and let
$B\in\mathbb{F}_{2}^{n\times t}$. Then, we say query set
$Q=\\{q_{1},\dots,q_{m}\\}$ is _linear_ if for each $i\in[m]$ there exists
$\alpha_{i}\neq 0\in\mathbb{F}_{2}^{k}$ and $\beta_{i}\in\mathbb{F}_{2}^{t}$
such that $q_{i}=A\alpha_{i}+B\beta_{i}$.

It is easy to see that individual queries in a linear query pattern are
uniformly distributed. Next, we want to show that we can hide a known sample
inside a linear query pattern while preserving the linear dependence between
the queries. Note that union of such query patterns also maintains this hiding
property.

######  Lemma 6.2.

For any linear query pattern, it is possible to construct a query set around a
random query.

###### Proof.

Let $Q=\\{q_{1},\dots,q_{m}\\}$ be a linear query pattern such that
$q_{i}=A\alpha_{i}+B\beta_{i}$ for all $i$ where
$\alpha_{i}\in\mathbb{F}_{2}^{k}$, $\beta_{i}\in\mathbb{F}_{2}^{t}$ are the
corresponding values as in Definition 6.1. We follow our general template
(described in Theorem 3.2) for constructing such a query set. Pick a uniformly
random $j\sim[m]$ and a uniformly random vector $r\sim\mathbb{F}_{2}^{n}$
which corresponds to the $j$-th query; that is $q_{j}=r$.

Let $L\subseteq[k]$ be the coordinates of $\alpha_{j}$ that are non-zero. $L$
must be non-empty since $\alpha_{j}\neq 0$. Choose an arbitrary element
$\ell\in L$. To construct $A$, sample all of its columns uniformly at random
except the $\ell$-th column. Set the $\ell$-th column of $A$ as the following

$a_{\ell}=r+B\beta_{j}+\sum_{i\in L\setminus\\{\ell\\}}a_{i}.$

It is easy to check that $q_{j}=r=A\alpha_{j}+B\beta_{j}$. Notice that
$a_{\ell}$ is a uniformly random vector. Hence $A$ is a uniformly random
matrix and the query set $Q$ is valid. ∎

We define one more query pattern used for dictator testing (Chapter 7 of
[O’D14]). The $i^{\text{th}}$ dictator is a Boolean function which simply
outputs the $i^{\text{th}}$ bit and ignores the rest of the input. This is
needed in our conversion from membership queries to random for the class of
juntas.

######  Definition 6.3 (NAE Query Pattern).

The query set consisting of three vectors $x,y,z\in\\{0,1\\}^{n}$ is called
NAE if for all $i\in[n]$ the bits $(x_{i},y_{i},z_{i})$ are drawn uniformly at
random from $\\{0,1\\}^{3}\setminus\\{(0,0,0),(1,1,1)\\}$.

######  Lemma 6.4.

It is possible to construct a membership query set for a NAE query pattern.

###### Proof.

First, notice that each of the three query points is uniformly distributed. To
construct a membership query set, pick one of the $x,y$ or $z$ at random
(w.l.o.g. assume it is $z$) and assign a uniformly random string to it; in our
constructions this will be the point we will hide in the query set. Then
assign a uniformly random string to $y$.

Then for each $i\in[n]$ assign $x_{i}=1-y_{i}$ or $x_{i}=1-z_{i}$ each with
probability $1/2$. This set of values for $x,y,z$ will be a NAE query pattern
where each query point is uniformly distributed. ∎

Next, we prove our theorem about agnostic verification of juntas with random
examples only.

######  Proof of Theorem 6.1.

Apply the general query-to-sample reduction of Theorem 3.2 to Theorem 6.2. We
show this is possible by showing the query pattern of the latter protocol
admits the property of “constructing membership query set”. In [DMN19], the
tolerant test for the class of juntas $\Junta_{n,k}$ is a straightforward use
of Maximum-correlation-junta where, given $k\in\mathbb{N}$, $\epsilon$, and
oracle access to $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$, outputs a number
$\widehat{\mathsf{Corr}}_{f,k}$ that is an estimation of the correlation of
$f$ with the closest junta from $\Junta_{n,k}$. At some point in this
algorithm, we need to use a dictator test on the function
$g(x)=\operatorname{sgn}(\mathsf{Has}_{\eta}f|_{\rho}(x)-\mathop{\mathbf{E}}[f|_{\rho}]^{3})$,
where $\rho$ is some random restriction and

$\mathsf{Has}_{\eta}f(x)=\mathop{\mathbf{E}}_{y_{1},y_{2}\sim\\{-1,1\\}^{n},y_{3}\sim
Z_{\eta}}[f(y_{1})f(y_{2})f(x\oplus y_{1}\oplus y_{2}\oplus y_{3})].$

Here, $Z_{\eta}$ denotes the product distribution on $\\{-1,1\\}^{n}$ with the
$i$-th bit having expectation $\eta_{i}$ for $\eta\in[-1,1]$. To evaluate
$g(x)$ it is enough to estimate $\mathsf{Has}_{\eta}f|_{\rho}(x)$ and
$\mathop{\mathbf{E}}[f|_{\rho}]^{3}$. The queries used for these estimations
have linear query pattern (assuming we treat the domain as
$\mathbb{F}_{2}^{n}$). Moreover, the dictator test uses NAE query pattern.
Other components of this algorithm also rely on queries chosen uniformly at
random. Therefore, overall, the query pattern for this algorithm is the union
of query patterns for which we know how to construct query sets and hide known
samples in. Thus, applying the transformation from Theorem 3.2 to Theorem 6.2
we get a protocol that only uses the random example oracle. ∎

##  7 Degeneracy of PAC-Verification with Unbounded Provers

In this section we obtain a general framework for learning hypothesis classes
with few random examples, given the honest prover is unbounded. First we show
any hypothesis class $\mathcal{H}$ is PAC-verfiable with
$O(\mathsf{VC}(\mathcal{H}))$ random examples in Section 7.1. Then we show how
to decrease the number of labeled samples if the verifier is allowed to draw
unlabeled samples from the underlying distribution to obtain the following
result.

######  Theorem 7.1.

For any finite hypothesis class $\mathcal{H}_{n}$ of circuits, there exists an
$(\epsilon,\delta)$-PAC-verification with verifier $V$ and prover $P$ with
respect to an unknown distribution $\mathcal{D}$, where the verifier has
random example access $\mathsf{Ex}(\mathcal{D},f)$ as well as access to
unlabeled samples from $\mathcal{D}$. Let
$m=\mathsf{m}_{\mathcal{H}}(\frac{\epsilon}{2},\frac{\delta}{2})=O((\mathsf{VC}(\mathcal{H}_{n})+\log(1/\delta))/\epsilon^{2})$.
This IP has the following parameters

${\left[{\small\begin{array}[]{r l}\textsf{input access
type:}&\enspace{\textsf{random examples}}\\\ \textsf{sample/query
complexity:}&\enspace{\log(1/\delta)/\epsilon}\\\ \textsf{communication
complexity:}&\enspace{\log(|\mathcal{H}|)+mn+\log(1/\delta)\cdot\poly(\log
m,\log|\mathcal{H}|)}\\\ \textsf{round
complexity:}&\enspace{\log(1/\delta)\cdot\poly(\log m,\log|\mathcal{H}|)}\\\
\textsf{verifier's running time:}&\enspace{\log(1/\delta)\cdot m\cdot
n\cdot\poly(\log m,\log|\mathcal{H}|)}\\\ \textsf{prover's running
time:}&\enspace{\log(1/\delta)\cdot\poly(m,|\mathcal{H}|)}\\\
\end{array}}\right]}.$

The interaction ${\langle P,V\rangle}$ outputs $h$, which is either $\bot$
(reject) or a hypothesis in $\mathcal{H}_{n}$ with the following guarantees

  * •

Completeness: There exists an honest prover $P^{*}$ such that the output of
interaction ${\langle P^{*},V\rangle}=h$ satisfies
$\Pr[\mathsf{dist}_{\mathcal{D}}(h,f)\leq\mathsf{dist}_{\mathcal{D}}(\mathcal{H},f)+\epsilon]\geq
1-\delta$.

  * •

Soundness: For any (possibly unbounded) prover $P$ the output of interaction
${\langle P,V\rangle}=h$ satisfies
$\Pr[(h\neq\bot)\land(\mathsf{dist}_{\mathcal{D}}(h,f)>\mathsf{dist}_{\mathcal{D}}(\mathcal{H},f)+\epsilon)]\leq\delta.$

For perspective, this construction is very powerful; we get an interactive
proof for proper agnostic learners in the distribution-free setting, using a
polynomial time verifier and $O(1/\varepsilon)$ many labeled examples. In more
detail, our interactive proof outputs a good hypothesis over any unknown, but
fixed marginal distribution $\mathcal{D}$ over the input examples, using a
random example oracle over $\mathcal{D}$, and further, the hypothesis is from
the same class as the target. The implication here is that, if we allow the
honest prover to have unbounded computational power, then any target class
$\mathcal{C}$ having a bounded description length for each input length has an
efficient proof system, for a very general agnostic learning task.

As applications of this general framework, we consider hypothesis classes
widely explored in learning theory, like $k$-juntas or functions computable by
polynomial-sized circuit families, i.e., $\Ppoly$, and construct interactive
proofs that can learn such classes using $O(1/\varepsilon)$ many random
labeled examples using polynomial-time verifiers.

Regarding the notation for this section, the hypothesis (or the target) class
$\mathcal{H}$ is given by a family $\\{\mathcal{H}_{n}\\}_{n\in\mathbb{N}}$,
where each $\mathcal{H}_{n}$ can be thought of as a class of circuits defined
over $n$ input bits. Thus, for most natural circuit classes $\mathcal{H}_{n}$
(like $\mathsf{AC}^{0}[p],\mathsf{TC}^{0},\mathsf{NC}^{1}$, or $\Ppoly$), the
size and (for $\Ppoly$) the depth of the circuits that compute the functions
are bounded by $\log(|\mathcal{H}_{n}|)$. Furthermore, we consider the class
of $k$-juntas, which can be implemented as small circuits.

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be the input function. The _empirical error_
of a hypothesis $h$ w.r.t. a labeled sample set
$S=\\{(x_{i},y_{i})\\}_{i=1}^{m}$ is defined to be
$\mathsf{err}_{S}(h)=\Pr_{(x,y)\sim S}[h(x)\neq y]$. Note that the labels in a
set of samples need not come from the input function $f$ (useful when a
possibly misleading prover labels the samples). The _true error_ of a
hypothesis $h$ w.r.t. the input function $f$ is
$\mathsf{dist}_{\mathcal{D}}(h,f)=\Pr_{x\sim\mathcal{D}}[h(x)\neq f(x)]$. For
simplicity of notation we define
$\mathsf{opt}_{S}(\mathcal{H})=\min_{h\in\mathcal{H}}\mathsf{err}_{S}(h)$ and
$\mathsf{dist}_{\mathcal{D}}(\mathcal{H},f)=\min_{h\in\mathcal{H}}\mathsf{dist}_{\mathcal{D}}(h,f)$.

##### Empirical Risk Minimization (ERM):

An ERM algorithm finds a hypothesis with minimal empirical error. The main
idea of ERM is that minimizing empirical error leads to minimizing true error.
The learner does not know the underlying distribution, but it can measure the
performance of a given hypothesis on random examples. Thus, instead of
minimizing the true error, the learner tries to minimize the empirical error.
It is well-known that for any hypothesis class that is not too complicated
(i.e. has finite VC dimension), an ERM learner over large enough samples
outputs a hypothesis with small true error as well (with high probability).

We start with the following definitions on representative samples from
$\mathcal{D}$.

######  Definition 7.1 ($\epsilon$-Representative Samples [SSBD14]).

A set of samples $S$ is _$\epsilon$ -representative_ w.r.t. hypothesis class
$\mathcal{H}$, distribution $\mathcal{D}$, and function $f$ if for all
$h\in\mathcal{H}$ it holds that
$|\mathsf{err}_{S}(h)-\mathsf{dist}_{\mathcal{D}}(h,f)|\leq\epsilon$.

Learning via uniform convergence says that if $|S|$ is sufficiently large then
a hypothesis $h$ with the minimum empirical error also has a small true error
with high probability. In fact, it states something stronger: the empirical
error of all hypotheses is close to their true error with high probability. We
recall the following well-known fact from learning theory.

######  Fact 7.2 (ERM for Hypothesis Classes of Finite VC Dimension [SSBD14]).

For any $n$, let $\mathcal{H}=\mathcal{H}_{n}$ be any hypothesis class of
finite VC-dimension, and let $S$ be a set of
$\mathsf{m}_{\mathcal{H}}(\epsilon,\delta)=\frac{C}{\epsilon^{2}}\cdot\left(\mathsf{VC}(\mathcal{H})+\log\frac{1}{\delta}\right)$
i.i.d. labeled samples from some unknown distribution
$\mathsf{Ex}(\mathcal{D},f)$, where $C$ is a universal constant. Then $S$ is
$\frac{\epsilon}{2}$-representative with probability at least $1-\delta$.
Moreover, an ERM algorithm minimizing $\mathsf{err}_{S}$ achieves agnostic
$(\epsilon,\delta)$-PAC learning.

We will show for an ERM algorithm to be a successful agnostic PAC learner, an
almost empirically optimal hypothesis suffices, hence the following
definition.

######  Definition 7.3.

For a fixed $n$, let $\mathcal{H}=\mathcal{H}_{n}$ be a hypothesis class of
finite size, and $S$ a finite set of labeled samples. We define the language
$L^{\epsilon}_{S}\subseteq\mathcal{H}$ as the set of empirically optimal
hypotheses with respect to $S$ up to $\epsilon$ error. That is
$L_{S}^{\epsilon}=\\{h\in\mathcal{H}:\mathsf{err}_{S}(h)\leq\mathsf{opt}_{S}(\mathcal{H})+\epsilon\\}$.
We informally refer to elements of $L_{S}^{\epsilon}$ as almost empirically
optimal.

In Section 7.1, we present the main idea of using ERM for distribution free
PAC-verification of general circuit classes, where the verifier has only
random example access. In Section 7.2 we further improve the query complexity
of the verifier and apply the resulting generic protocol to polynomial sized
circuits and juntas.

###  7.1 PAC-Verification for $\mathcal{H}_{n}$ Using
$O(\mathsf{VC}(\mathcal{H}_{n}))$ Random Examples

The high level idea is that verifier and prover agree on a sample set $S$ with
i.i.d. samples. The prover provides an almost empirically optimal hypothesis
$h$ with respect to the samples (Definition 7.3). Then it only remains for the
verifier to check that $h$ is, in fact, almost empirically optimal; i.e.,
$h\in L_{S}^{\epsilon}$ for some error parameter $\epsilon$. Next we show that
this statement reduces to an instance of Circuit Value Problem (CVP), and that
we can apply an existing interactive proof for this statement. Alas, the
prover is not efficient, and the resulting protocol is not doubly-efficient.

We start by observing that an almost empirically optimal hypothesis can be
verified by a low-depth parallelised computation, in the following lemma.

######  Lemma 7.4 (Reducing $h\in L_{S}^{\epsilon}$ to an Instance of CVP).

Fix a hypothesis class $\mathcal{H}=\mathcal{H}_{n}$, a sample set
$S=\\{(x_{i},y_{i})\\}_{i=1}^{m}\subseteq\\{0,1\\}^{n}\times\\{0,1\\}$, and a
parameter $\epsilon>0$. Then, there exists a log-space uniform circuit
$C_{\mathsf{ERM}}^{h}:\\{0,1\\}^{mn+m}\to\\{0,1\\}$ of size
$\poly(m,|\mathcal{H}|)$ and depth $\poly(\log(m),\log(|\mathcal{H}|))$ such
that $h\in L_{S}^{\epsilon}$ if and only if
$C_{\mathsf{ERM}}^{h}(x_{1},y_{1},\dots,x_{m},y_{m})=1$.

###### Proof.

The inputs to $C_{\mathsf{ERM}}^{h}$ are the samples $x_{i}\in\\{0,1\\}^{n}$
along with $y_{i}\in\\{0,1\\}$. Give as input each $x_{i}$ to each circuit in
$\mathcal{H}_{n}$. In other words, test all samples on all hypotheses in
parallel. For any $h^{\prime}\in\mathcal{H}$, define its agreement with
samples to be
$\mathsf{agr}(h^{\prime})=|\\{i\in[m]:h^{\prime}(x_{i})=y_{i}\\}|$. Then, take
the outputs of the circuit $h^{\star}\in\mathcal{H}$ that maximizes the
agreement and compare this number to the number of accepting samples from $h$
and output $1$ if and only if $\mathsf{agr}(h)+\epsilon
m\geq\mathsf{agr}(h^{\star})$. Observe that the circuit outputs $1$ if and
only if $h\in L^{\epsilon}_{S}$. Therefore, the statement $h\in
L^{\epsilon}_{S}$ reduces to an instance of Circuit Value Problem, namely the
value of $C_{\mathsf{ERM}}^{h}$ on input $S$.

The circuit as described above needs $\poly(m,|\mathcal{H}|)$ size as we run
$m$ samples on each hypothesis in $\mathcal{H}$. Note that the rest of the
circuit is not any larger. The depth of the circuit is bounded by
$\poly(\log(m),\log(|\mathcal{H}|))$; each circuit in $\mathcal{H}$ can be
implemented in depth $\log(|\mathcal{H}|)$, and we need no more than
$\poly(\log m,\log|\mathcal{H}|)$ to compute the agreement and find the
maximum.

We can argue the circuit is log-space uniform since each level of the circuit
is tasked with the same computation; in other words, this circuit has a highly
regular wiring pattern. ∎

Following this, we state the following doubly-efficient interactive proof that
verifies the result of the computation of any language computable by a low-
depth circuit by an untrusted prover. In our case, the largeness of the
circuit $C_{\mathsf{ERM}}$ leads to inefficient prover time.

######  Lemma 7.5 (GKR Protocol [GKR15]).

Let $L$ be a language that can be computed by a family of
$O(\log(S(n)))$-space uniform Boolean circuits of size $S(n)$ and depth
$d(n)$. Then $L$ has an interactive proof with perfect completeness, and
soundness $1/2$, where the prover’s running time is $\poly(S(n))$ and the
verifier runs in time $(n+d(n))\cdot\polylog(S(n))$. Moreover, the
communication complexity of the interactive proof is
$d(n)\cdot\polylog(S(n))$.

######  Remark 7.6.

The round complexity of the GKR protocol is $d(n)\cdot\polylog(S(n))$.

######  Remark 7.7.

We can set the soundness of the GKR protocol to any $\delta>0$ by repeating
the interaction for $\log(1/\delta)$ times and rejecting if at least one of
the iterations rejects.

Denote by ${\langle P_{\mathsf{GKR}},V_{\mathsf{GKR}}\rangle}[\delta]$ the
interactive protocol of GKR with soundness error boosted to $\delta$. The
output of this interaction on circuit $C^{h}_{\mathsf{ERM}}$ constructed based
on Lemma 7.4 for the statement $h\in L_{S}^{\epsilon}$ is denoted by ${\langle
P_{\mathsf{GKR}},V_{\mathsf{GKR}}\rangle}[\delta](C^{h}_{\mathsf{ERM}},S)$;
note that the hidden parameters like $\mathcal{H}$, $\epsilon$, etc. are
captured by the construction of our circuit. We now describe the general PAC-
verification proof system for any circuit class $\mathcal{H}$ using
$O(\mathsf{VC}(\mathcal{H}))$ random examples.

1

Function input : A function $f:\\{0,1\\}^{n}\to\\{0,1\\}$, where the verifier
has access to the random example oracle $\mathsf{Ex}(\mathcal{D},f)$

Explicit inputs : Parameters $\epsilon,\delta>0$

2

3The verifier takes a set $S=\\{(x_{i},f(x_{i}))\\}_{i=1}^{m}$ of
$m=\mathsf{m}_{\mathcal{H}}(\frac{\epsilon}{2},\delta)=O((\mathsf{VC}(\mathcal{H})+\log(1/\delta))/\epsilon^{2})$
labeled samples from the random example oracle $\mathsf{Ex}(\mathcal{D},f)$
and sends them to prover.

4The prover sends $\tilde{h}\in\mathcal{H}$, which is purported to be
empirically optimal up to error $\epsilon/2$. That is $\tilde{h}\in
L_{S}^{\epsilon/2}$.

5Let $C^{\tilde{h}}_{\mathsf{ERM}}$ denote the circuit from Lemma 7.4 for the
statement $\tilde{h}\in L_{S}^{\epsilon/2}$. The verifier and the prover run
the protocol ${\langle
P_{\mathsf{GKR}},V_{\mathsf{GKR}}\rangle}[\delta](C_{\mathsf{ERM}}^{\tilde{h}},S)$.

The verifier outputs $\tilde{h}$ iff the GKR protocol does not reject and
outputs $1$.

Protocol 8 A general $(\epsilon,\delta)$-PAC-Verification protocol for class
$\mathcal{H}$

######  Lemma 7.8.

Let $S=\\{(x_{i},f(x_{i}))\\}_{i=1}^{m}$ be a set of samples of size
$m=\mathsf{m}_{\mathcal{H}}(\frac{\epsilon}{2},\delta)=O((\mathsf{VC}(\mathcal{H})+\log(1/\delta))/\epsilon^{2})$
drawn i.i.d. from $\mathsf{Ex}(\mathcal{D},f)$. Then for any $h\in
L_{S}^{\epsilon/2}$,
$\mathsf{dist}_{\mathcal{D}}(h,f)\leq\mathsf{dist}_{\mathcal{D}}(\mathcal{H},f)+\epsilon$
with probability at least $1-\delta$.

###### Proof.

Let $h_{\mathsf{emp}}$ be an empirically optimal hypothesis w.r.t. samples
$S$, and let $h_{\mathsf{true}}$ be an optimal hypothesis w.r.t. the
underlying distribution $\mathcal{D}$. By 7.2 with probability at least
$1-\delta$, the sample set $S$ is $\frac{\epsilon}{4}$-representative, and
thus for any $h\in L_{S}^{\epsilon/2}$

$\mathsf{dist}_{\mathcal{D}}(h,f)\leq\mathsf{err}_{S}(h)+\frac{\epsilon}{4}\leq\mathsf{err}_{S}(h_{\mathsf{emp}})+\frac{\epsilon}{2}+\frac{\epsilon}{4}\leq\mathsf{err}_{S}(h_{\mathsf{true}})+\frac{\epsilon}{2}+\frac{\epsilon}{4}\leq\mathsf{dist}_{\mathcal{D}}(h_{\mathsf{true}},f)+\epsilon.$

The first and last inequalities follow from $S$ being
$\frac{\epsilon}{4}$-representative. The second one follows from $h\in
L^{\epsilon/2}_{S}$. The third one follows from $h_{\mathsf{emp}}$ being
optimal with respect to $\mathsf{err}_{S}$. ∎

######  Lemma 7.9.

Let $h\in\mathcal{H}\cup\\{\bot\text{ (reject)}\\}$ denote the output of
Protocol 8. Then this protocol satisfies the following conditions.

  * •

Completeness: There exists an honest prover $P^{*}$ such that the output of
interaction ${\langle P^{*},V\rangle}=h$ satisfies
$\Pr[\mathsf{dist}_{\mathcal{D}}(h,f)\leq\mathsf{dist}_{\mathcal{D}}(\mathcal{H},f)+\epsilon]\geq
1-\delta$.

  * •

Soundness: For any (possibly unbounded) prover $P$, the output of interaction
${\langle P,V\rangle}=h$ satisfies
$\Pr[(h\neq\bot)\land(\mathsf{dist}_{\mathcal{D}}(h,f)>\mathsf{dist}_{\mathcal{D}}(\mathcal{H},f)+\epsilon)]\leq\delta$.

###### Proof.

We start with completeness. Assuming the prover is honest, he sends a
hypothesis $\tilde{h}$ that is in $L^{\epsilon/2}_{S}$. Then by Lemma 7.8,
with probability at least $1-\delta$, we have
$\mathsf{dist}_{\mathcal{D}}(\tilde{h},f)\leq\mathsf{dist}_{\mathcal{D}}(\mathcal{H},f)+\epsilon$.
Since $\tilde{h}\in L^{\epsilon/2}_{S}$ and since ${\langle
P_{\mathsf{GKR}},V_{\mathsf{GKR}}\rangle}[\delta]$ has perfect completeness,
the verifier accepts the interaction and outputs $h=\tilde{h}$ with
probability $1$. Therefore, with probability at least $1-\delta$,
$\mathsf{dist}_{\mathcal{D}}(h,f)\leq\mathsf{dist}_{\mathcal{D}}(\mathcal{H},f)+\epsilon$.

Now to prove soundness there are two scenarios. First, suppose that the prover
sends $\tilde{h}$ such that $\tilde{h}\notin L^{\epsilon/2}_{S}$. Then by
guarantee of ${\langle P_{\mathsf{GKR}},V_{\mathsf{GKR}}\rangle}[\delta]$ the
verifier accepts with probability no more than $\delta$. In the second
scenario, the sample set $S$ is not $(\epsilon/4)$-representative, and the
prover sends $\tilde{h}\in L^{\epsilon/2}_{S}$. This will be accepted by the
verifier, but the probability of $S$ not being representative is at most
$\delta$. ∎

###  7.2 Sample-Efficient PAC-Verification for $\mathcal{H}_{n}$

Now that we have a protocol for PAC-verifying general circuit classes, we
obtain a protocol from it, where the verifier uses much fewer labeled samples,
alongside unlabeled samples. The idea is to delegate the task of labeling
unlabeled samples to the prover, where prover is forced to send an almost
correct labeling of samples for otherwise the verifier catches him with
overwhelming probability. Following this, we argue that an almost correct
labeling is as good as a correct labeling, as far as the ERM algorithm is
concerned.

For additional perspective, this setting of learning using unlabeled samples
is referred to as _semi-supervised learning_ in literature. This is motivated
by real-world scenarios where we are required to train models using a limited
number of labeled samples, while unlabeled samples are available for _free_ or
very low cost. The protocol in this section thus gives us a general
interactive proof for verifying agnostic learning of finite191919While the
size of $\mathcal{H}_{n}$ could grow with $n$, for any fixed $n$ it is finite.
target classes in the semi-supervised setting, with the help of a prover that
is computationally unbounded. While [GRSY21] (Claim 5.2) show that any class
of finite VC-dimension has $(\epsilon,\delta)$-PAC-verification where the
verifier uses only $O(\log(1/\delta)/\epsilon)$ labeled samples, the verifier
runs an ERM algorithm, potentially in exponential time, while the honest
prover is efficient in the number of samples used by the ERM algorithm. On the
other hand, we focus on the scenario of understanding the necessity of doubly-
efficient proof systems for PAC-verification - and obtain a highly efficient
verifier (polynomial in the logarithm of VC-dimension, as well as the size of
the hypothesis class), which delegates the task to an inefficient prover.

The protocol is as follows.

1

Function input : A function $f:\\{0,1\\}^{n}\to\\{0,1\\}$, where the verifier
has access to the random example oracle $\mathsf{Ex}(\mathcal{D},f)$ and a
source for unlabeled samples $\mathcal{D}$

Explicit inputs : Parameters $\epsilon,\delta>0$

2

3Let
$m=\mathsf{m}_{\mathcal{H}}(\frac{\epsilon}{2},\frac{\delta}{2})=O((\mathsf{VC}(\mathcal{H})+\log\frac{2}{\delta})/\epsilon^{2})$
and $q=\frac{8}{\epsilon}\cdot\log(\frac{2}{\delta})$. The verifier takes $q$
labeled samples $\\{(x_{i},f(x_{i}))\\}_{i=1}^{q}$ from
$\mathsf{Ex}(\mathcal{D},f)$ and $m-q$ unlabeled samples
$\\{x_{i}\\}_{i=q+1}^{m}$ from $\mathcal{D}$. Then, the verifier sends
$\\{x_{\pi(i)}\\}_{i=1}^{m}$ to the prover, where $\pi$ is a uniformly random
permutation.

4The prover sends
$\tilde{S}=\\{(x_{\pi(i)},\tilde{f}(x_{\pi(i)}))\\}_{i=1}^{m}$ along with a
hypothesis $\tilde{h}\in\mathcal{H}$, where $\tilde{f}$ is prover’s labeling
strategy.202020The prover only needs to send labels $\tilde{f}(x_{\pi(i)})$.
For simplicity, we say the prover sends $x_{\pi(i)}$’s as well.

5The verifier checks if the labels of $q$ known samples are correct, if not
she rejects. More precisely, she asserts $f(x_{i})=\tilde{f}(x_{i})$ for all
$i\in[q]$.

6Let $C^{\tilde{h}}_{\mathsf{ERM}}$ denote the circuit from Lemma 7.4 for the
statement $\tilde{h}\in L_{\tilde{S}}^{\epsilon/4}$. The verifier and the
prover run ${\langle
P_{\mathsf{GKR}},V_{\mathsf{GKR}}\rangle}[\frac{\delta}{2}](C_{\mathsf{ERM}}^{\tilde{h}},\tilde{S})$.

The verifier outputs $\tilde{h}$ iff the GKR protocol does not reject and
outputs $1$.

Protocol 9 Sample-efficient $(\epsilon,\delta)$-PAC-verification Protocol for
class $\mathcal{H}$

######  Lemma 7.10.

Let $S=\\{(x_{i},f(x_{i}))\\}_{i=1}^{m}$ be the set of correct labeling of
samples in Protocol 9, and let
$\tilde{S}=\\{(x_{i},\tilde{f}(x_{i}))\\}_{i=1}^{m}$ be the set of samples
labeled by the prover. If the verifier does not reject the samples $\tilde{S}$
labeled by the prover, it holds with probability at least $1-\frac{\delta}{2}$
that $L^{\epsilon/4}_{\tilde{S}}\subseteq L^{\epsilon/2}_{S}$.

###### Proof.

First, observe that prover has no way to distinguish between the samples that
are drawn from the labeled example oracle $\mathsf{Ex}(\mathcal{D},f)$ and the
unlabeled samples that are drawn from $\mathcal{D}$, as the samples are all
independent and identically distributed.

Let $p=\frac{1}{m}\cdot|\\{i\in[m]:f(x_{i})\neq\tilde{f}(x_{i})\\}|$ be the
fraction of mislabeled samples. If $p>\frac{\epsilon}{8}$ then the verifier
will catch at least one of them with probability $1-(1-p)^{q}\geq
1-\exp({-\frac{\epsilon}{8}\cdot\frac{8}{\epsilon}\cdot\log(\frac{2}{\delta})})=1-\frac{\delta}{2}$.
Thus, if the verifier does not reject the labeling $\tilde{S}$ provided by the
prover, with probability at least $1-\frac{\delta}{2}$, for every hypothesis
$h$ we have
$|\mathsf{err}_{S}(h)-\mathsf{err}_{\tilde{S}}(h)|\leq\frac{\epsilon}{8}$.
$(\ast)$

Let $h_{\mathsf{\widetilde{emp}}}$ and $h_{\mathsf{emp}}$ be empirically
optimal hypotheses with respect to $\tilde{S}$ and $S$ respectively. That is,
$\mathsf{err}_{\tilde{S}}(h_{\mathsf{\widetilde{emp}}})=\mathsf{opt}_{\tilde{S}}(\mathcal{H})$
and $\mathsf{err}_{S}(h_{\mathsf{emp}})=\mathsf{opt}_{S}(\mathcal{H})$. Then,
using a similar argument as Lemma 7.8, for any $h\in
L^{\epsilon/4}_{\tilde{S}}$, we have

$\mathsf{err}_{S}(h)\leq\mathsf{err}_{\tilde{S}}(h)+\frac{\epsilon}{8}\leq\mathsf{err}_{\tilde{S}}(h_{\mathsf{\widetilde{emp}}})+\frac{\epsilon}{4}+\frac{\epsilon}{8}\leq\mathsf{err}_{\tilde{S}}(h_{\mathsf{emp}})+\frac{\epsilon}{4}+\frac{\epsilon}{8}\leq\mathsf{err}_{S}(h_{\mathsf{emp}})+\frac{\epsilon}{2}.$

The first and last inequalities hold because of $(\ast)$. The second one
follows from $h\in L^{\epsilon/4}_{\tilde{S}}$. The third one follows from the
fact that $h_{\mathsf{\widetilde{emp}}}$ is empirically optimal with respect
to $\tilde{S}$. ∎

Intuitively, the above lemma states that cheating on a small fraction of
samples does not give any advantage to the dishonest prover. On the other
hand, a dishonest prover that cheats on a large fraction of samples is
rejected with high probability.

######  Proof of Theorem 7.1.

Lemma 7.10 shows with probability at least $1-\delta/2$,
$L_{\tilde{S}}^{\epsilon/4}\subseteq L_{S}^{\epsilon/2}$. Therefore, the
argument from Lemma 7.9 can be used verbatim to prove similar guarantees.

The multiplicative factor of $\log(1/\delta)$ in communication complexity,
round complexity and running time is a result of repeating the GKR protocol
for $O(\log(1/\delta))$ times to improve the soundness. The verifier sends $m$
unlabeled samples following which the prover sends a hypothesis and $m$
labels. This needs $\log(|\mathcal{H}|)+m(n+1)$ bits of communication. To run
${\langle P_{\mathsf{GKR}},V_{\mathsf{GKR}}\rangle}[\frac{\delta}{2}]$, we
need $\log(2/\delta)\cdot\poly(\log m,\log|\mathcal{H}|)$ communication
complexity. The verifer’s and prover’s running time are a direct result of
running GKR as well. Note that an honest prover finds a correct hypothesis by
running ERM, in a similar way to our $C_{\mathsf{ERM}}$ circuit. ∎

We next show applications of Theorem 7.1 to get interactive proofs for PAC-
verifying specific classes of interest.

##### Polynomial-sized circuits:

To instantiate Theorem 7.1 for $\Ppoly$, fix any polynomial $s=s(n)$. We will
consider learning the class $\mathsf{SIZE}[s]$; polynomial sized circuits over
$n$ inputs of size at most $s$. Note that there are at most $s^{O(s)}$
circuits of this size.

######  Corollary 7.11 (Formal version of Theorem 1.4).

For any $c\in\mathbb{N}$, the class $\mathsf{SIZE}[n^{c}]$ is distribution-
free $(\epsilon,\delta)$-PAC-verifiable with verifier $V$ and prover $P$,
where for an unknown, but fixed underlying distribution $\mathcal{D}$, the
verifier has random example access via $\mathsf{Ex}(\mathcal{D},f)$, as well
as access to unlabeled samples from $\mathcal{D}$. This interactive proof has
the following parameters.

${\left[{\small\begin{array}[]{r l}\textsf{input access
type:}&\enspace{\textsf{random examples}}\\\ \textsf{sample/query
complexity:}&\enspace{\log(1/\delta)/\epsilon}\\\ \textsf{communication
complexity:}&\enspace{\poly(n,1/\epsilon,\log(1/\delta))}\\\ \textsf{round
complexity:}&\enspace{\poly(n,1/\epsilon,\log(1/\delta))}\\\
\textsf{verifier's running
time:}&\enspace{\poly(n,1/\epsilon,\log(1/\delta))}\\\ \textsf{prover's
running time:}&\enspace{n^{\poly(n)}\poly(1/\epsilon,\log(1/\delta))}\\\
\end{array}}\right]}.$

The interaction ${\langle P,V\rangle}$ outputs $h$, which is either $\bot$
(reject) or a circuit of size at most $s$ with the following guarantees

  * •

Completeness: There exists an honest prover $P^{*}$ such that the output of
interaction ${\langle P^{*},V\rangle}=h$ satisfies
$\Pr[\mathsf{dist}_{\mathcal{D}}(h,f)\leq\mathsf{dist}_{\mathcal{D}}(\mathsf{SIZE}[n^{c}],f)+\epsilon]\geq
1-\delta$.

  * •

Soundness: For any (possibly unbounded) prover $P$, the output of interaction
${\langle P,V\rangle}=h$ satisfies
$\Pr[(h\neq\bot)\land(\mathsf{dist}_{\mathcal{D}}(h,f)>\mathsf{dist}_{\mathcal{D}}(\mathsf{SIZE}[n^{c}],f)+\epsilon)]\leq\delta.$

###### Proof.

Apply the general protocol discussed in Theorem 7.1. Observe that the VC
dimension of any hypothesis class is bounded by the logarithm of its size.
Thus, we have

$\mathsf{VC}(\mathsf{SIZE}[n^{c}])\leq\log_{2}(|\mathsf{SIZE}[n^{c}]|)=O(n^{c}\log(n)).$

Here the number of samples is
$m=\mathsf{m}_{\mathsf{SIZE}[n^{c}]}(\epsilon/2,\delta/2)=O((n^{c}\log(n)+\log(1/\delta))\cdot
1/\epsilon^{2})$. The depth of the circuit $C_{\mathsf{ERM}}$ is bounded by
$\poly(n^{c},1/\epsilon,\log(1/\delta))$ and its size is
$n^{cn^{c}}\cdot\poly(m)$. Thus, by substituting these values in the
complexity parameters from Theorem 7.1, we see that the verifier runs in
$\poly(n,1/\epsilon,\log(1/\delta))$, and the honest prover runs in time
$n^{\poly(n)}\poly(1/\epsilon,\log(1/\delta))$. ∎

##### Class of $k$-juntas:

Next, we instantiate Theorem 7.1 for the class of $k$-juntas, $\Junta_{n,k}$.
This IP unlike Theorem 6.2 and Theorem 6.1 works for any underlying
distribution. The verifier’s running time is more efficient than known
learning algorithms for $k$-juntas (e.g., [MOS03]).

######  Corollary 7.12.

The class $\Junta_{n,k}$ is $(\epsilon,\delta)$-PAC-verifiable with verifier
$V$ and prover $P$ in the distribution-free setting, where for an unknown, but
fixed underlying distribution $\mathcal{D}$, the verifier has random example
access via $\mathsf{Ex}(\mathcal{D},f)$ as well as access to unlabeled samples
from $\mathcal{D}$. This protocol has the following parameters.

${\left[{\small\begin{array}[]{r l}\textsf{input access
type:}&\enspace{\textsf{random examples}}\\\ \textsf{sample/query
complexity:}&\enspace{\log(1/\delta)/\epsilon}\\\ \textsf{communication
complexity:}&\enspace{n\cdot\poly(\log(n),2^{k},1/\epsilon,\log(1/\delta))}\\\
\textsf{round
complexity:}&\enspace{\poly(\log(n),2^{k},\log(1/\epsilon),\log(1/\delta)))}\\\
\textsf{verifier's running
time:}&\enspace{n\cdot\poly(\log(n),2^{k},1/\epsilon,\log(1/\delta))}\\\
\textsf{prover's running
time:}&\enspace{\poly(n^{k},2^{2^{k}},1/\epsilon,\log(1/\delta))}\\\
\end{array}}\right]}.$

The interaction ${\langle P,V\rangle}$ outputs $h$, which is either $\bot$
(reject) or a $k$-junta with the following guarantees

  * •

Completeness: There exists an honest prover $P^{*}$ such that the output of
interaction ${\langle P^{*},V\rangle}=h$ satisfies
$\Pr[\mathsf{dist}_{\mathcal{D}}(h,f)\leq\mathsf{dist}_{\mathcal{D}}(\Junta_{n,k},f)+\epsilon]\geq
1-\delta$.

  * •

Soundness: For any (possibly unbounded) prover $P$ the output of interaction
${\langle P,V\rangle}=h$ satisfies
$\Pr[(h\neq\bot)\land(\mathsf{dist}_{\mathcal{D}}(h,f)>\mathsf{dist}_{\mathcal{D}}(\Junta_{n,k},f)+\epsilon)]\leq\delta.$

###### Proof.

Apply the general protocol discussed in Theorem 7.1. First, note that
$|\Junta_{n,k}|=\binom{n}{k}2^{2^{k}}\leq(ne/k)^{k}2^{2^{k}}$. Therefore,
$\mathsf{VC}(\Junta_{n,k})\leq k\log(ne)+2^{k}$ and we need
$m=\mathsf{m}_{\Junta_{n,k}}(\epsilon/2,\delta/2)=O((k\log(n)+2^{k}+\log(1/\delta))/\epsilon^{2})=\poly(\log(n),2^{k},1/\epsilon,\log(1/\delta))$
samples. By parameters of Theorem 7.1 we see that the prover’s running time is
$\poly(n^{k},2^{2^{k}},1/\epsilon,\log(1/\delta))$, and the verifier’s running
time is $n\cdot\poly(\log(n),2^{k},1/\epsilon,\log(1/\delta))$. ∎

## References

  * [AB09] Sanjeev Arora and Boaz Barak.  Computational complexity: a modern approach.  Cambridge University Press, 2009.
  * [CG18] Alessandro Chiesa and Tom Gur.  Proofs of proximity for distribution testing.  In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 53:1–53:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [CHI+23] Matthias C Caro, Marcel Hinsche, Marios Ioannou, Alexander Nietner, and Ryan Sweke.  Classical verification of quantum learning.  arXiv preprint arXiv:2306.04843, 2023.
  * [CIKK16] Marco L Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova.  Learning algorithms from natural proofs.  In 31st Conference on Computational Complexity (CCC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
  * [CIKK17] Marco L Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova.  Agnostic learning from tolerant natural proofs.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [CK21] Ran Canetti and Ari Karchmer.  Covert learning: How to learn with an untrusted intermediary.  In Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part III 19, pages 1–31. Springer, 2021.
  * [CNY23] Thomas Chen, Shivam Nadimpalli, and Henry Yuen.  Testing and learning quantum juntas nearly optimally.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1163–1185. SIAM, 2023.
  * [DMN19] Anindya De, Elchanan Mossel, and Joe Neeman.  Junta correlation is testable.  In David Zuckerman, editor, Proceedings pf the 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 19, pages 1549–1563, 2019.
  * [Fel09] Vitaly Feldman.  On the power of membership queries in agnostic learning.  The Journal of Machine Learning Research, 10:163–182, 2009.
  * [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali.  How to construct random functions.  Journal of the ACM (JACM), 33(4):792–807, 1986.
  * [GK23] Halley Goldberg and Valentine Kabanets.  Improved learning from kolmogorov complexity.  In 38th Computational Complexity Conference (CCC 2023). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023.
  * [GKR15] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum.  Delegating computation: Interactive proofs for muggles.  J. ACM, 62(4):1–64, 2015.
  * [GL89] O. Goldreich and L. A. Levin.  A hard-core predicate for all one-way functions.  In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC ’89, page 25–32, New York, NY, USA, 1989. Association for Computing Machinery.
  * [GOS+11] Parikshit Gopalan, Ryan O’Donnell, Rocco A Servedio, Amir Shpilka, and Karl Wimmer.  Testing fourier dimensionality and sparsity.  SIAM Journal on Computing, 40(4):1075–1100, 2011.
  * [GR22] Guy Goldberg and Guy N Rothblum.  Sample-based proofs of proximity.  In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [GRSY21] Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff.  Interactive proofs for verifying machine learning.  In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, 2021.
  * [HR22] Tal Herman and Guy N Rothblum.  Verifying the unseen: interactive proofs for label-invariant distribution properties.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1208–1219, 2022.
  * [HS23] Mohsen Heidari and Wojciech Szpankowski.  Agnostic pac learning of $k$-juntas using $l\\_2$-polynomial regression.  In International Conference on Artificial Intelligence and Statistics, pages 2922–2938. PMLR, 2023.
  * [IJKW10] Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson.  Uniform direct product theorems: Simplified, optimized, and derandomized.  SIAM J. Comput., 39(4):1637–1665, 2010.
  * [IW01] Russell Impagliazzo and Avi Wigderson.  Randomness vs time: Derandomization under a uniform assumption.  Journal of Computer and System Sciences, 63(4):672–688, 2001.
  * [KM93] Eyal Kushilevitz and Yishay Mansour.  Learning decision trees using the Fourier spectrum.  SIAM J. Comput., 22(6):1331–1348, 1993.
  * [KV94] Michael J Kearns and Umesh Vazirani.  An introduction to computational learning theory.  MIT press, 1994.
  * [LMN93] Nathan Linial, Yishay Mansour, and Noam Nisan.  Constant depth circuits, fourier transform, and learnability.  Journal of the ACM (JACM), 40(3):607–620, 1993.
  * [MOS03] Elchanan Mossel, Ryan O’Donnell, and Rocco P. Servedio.  Learning juntas.  In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC 03, page 206–212, 2003.
  * [MS23] Saachi Mutreja and Jonathan Shafer.  Pac verification of statistical algorithms.  In The Thirty Sixth Annual Conference on Learning Theory, pages 5021–5043. PMLR, 2023.
  * [NW94] Noam Nisan and Avi Wigderson.  Hardness vs randomness.  Journal of computer and System Sciences, 49(2):149–167, 1994.
  * [O’D14] Ryan O’Donnell.  Analysis of boolean functions.  Cambridge University Press, 2014.
  * [PRR06] Michal Parnas, Dana Ron, and Ronitt Rubinfeld.  Tolerant property testing and distance approximation.  Journal of Computer and System Sciences, 72(6):1012–1042, 2006\.
  * [Raz87] Alexander A. Razborov.  Lower bounds on the size of constant-depth networks over a complete basis with logical addition.  Mathematicheskie Zametki, 41(4):598–607, 1987.
  * [RR97] Alexander A. Razborov and Steven Rudich.  Natural proofs.  J. Comput. Syst. Sci., 55(1):24–35, 1997.
  * [RVW13] Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson.  Interactive proofs of proximity: delegating computation in sublinear time.  In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 793–802. ACM, 2013.
  * [Smo87] Roman Smolensky.  Algebraic methods in the theory of lower bounds for Boolean circuit complexity.  In Symposium on Theory of Computing _(STOC)_ , pages 77–82, 1987.
  * [SSBD14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding machine learning: From theory to algorithms.  Cambridge university press, 2014.
  * [Val84] Leslie G. Valiant.  A theory of the learnable.  Commun. ACM, 27(11):1134–1142, 1984.

##  Appendix A Embeddability

In this section we present a general definition of the notion of embeddability
of a random query in a query sets obtained from membership samples, described
in Section 3.2. Recall, when transforming a protocol with membership queries
into a protocol that works with random examples, we try to hide a single
random example in non-adaptively generated query sets for the following
definition.

######  Definition A.1 (Embeddable non-adaptive query set).

Let $\mathcal{D}$ be a distribution over $\\{0,1\\}^{n}$, and let
$V_{\mathsf{query}}$ be an algorithm that given randomness $r$ returns a
sequence of $Q$ queries, $y_{1},\dots,y_{Q}\in\\{0,1\\}^{n}$.

We say that a random query from $\mathcal{D}$ can be embedded into the
distribution defined by $V_{\mathsf{query}}$, if there exists an algorithm
$\hat{V}_{\mathsf{query}}$ that takes as input $w\sim\mathcal{D}$ and
randomness $r^{\prime}$, and outputs a query set
$\hat{y}_{1},\dots,\hat{y}_{Q}\in\\{0,1\\}^{n}$ such that the following hold.

  1. 1.

There exists $i\in[Q]$ such that $\hat{y}_{i}=w$, i.e., $w$ is in the output
of $\hat{V}_{\mathsf{query}}$.

  2. 2.

For every $\hat{y}_{1},\dots,\hat{y}_{Q}$ that is generated by
$V_{\mathsf{query}}$ with non-zero probability it holds that

$\Pr_{r^{\prime}}\left[\hat{y}_{i}=w\mid\hat{V}_{\mathsf{query}}(w;r^{\prime})\text{
outputs }\hat{y}_{1},\dots,\hat{y}_{Q}\right]=\frac{1}{Q}.$

In other words, the query index into which $w$ is embedded has a uniform
distribution, where the probability is over the randomness $r^{\prime}$ and
the sample access to $\mathcal{D}$.

  3. 3.

For all $\hat{y}_{1},\dots,\hat{y}_{Q}$ it holds that

$\Pr_{r^{\prime}}\left[\hat{V}_{\mathsf{query}}(w;r^{\prime})\text{ outputs
}\hat{y}_{1},\dots,\hat{y}_{Q}\right]=\Pr_{r}\left[V_{\mathsf{query}}(r)\text{
outputs }\hat{y}_{1},\dots,\hat{y}_{Q}\right].$

In other words, the joint distribution of the queries generated by
$\hat{V}_{\mathsf{query}}$ and $V_{\mathsf{query}}$ coincide.

In particular, the third condition implies that any (possibly unbounded)
prover $P$ can gain no information about the location of the embedded query
$w$ by looking at the joint query distributions of the output of
$\hat{V}_{\mathsf{query}}$, and the second condition implies that $P$ can
guess the location of $w$ with probability no more than $1/Q$.

######  Proposition A.2 (Embeddability is closed under independent
unions212121This argument can be easily extended to any finite number of
unions.).

Let $V_{\mathsf{query}}$ and $U_{\mathsf{query}}$ be two Embeddable query
generation algorithms. Then the query set generated by the algorithm
$T_{\mathsf{query}}(r_{1},r_{2})=V_{\mathsf{query}}(r_{1})\cup
U_{\mathsf{query}}(r_{2})$ that outputs the concatenation of the independent
outputs of $V_{\mathsf{query}}$ and $U_{\mathsf{query}}$ is Embeddable.

###### Proof.

Let $Q_{1}$ and $Q_{2}$ be the number of queries outputted by
$V_{\mathsf{query}}$ and $U_{\mathsf{query}}$ respectively. The algorithm
$\hat{T}_{\mathsf{query}}$ works as follows: on input
$(w;r_{1}^{\prime},r_{2}^{\prime})$ with probability $Q_{1}/(Q_{1}+Q_{2})$
outputs $\hat{V}_{\mathsf{query}}(w;r^{\prime}_{1})\cup
U_{\mathsf{query}}(r^{\prime}_{2})$ and with probability $Q_{2}/(Q_{1}+Q_{2})$
outputs
$V_{\mathsf{query}}(r^{\prime}_{1})\cup\hat{U}_{\mathsf{query}}(w;r^{\prime}_{2})$.
It is easily observed that $\hat{T}_{\mathsf{query}}$ satisfies the three
items in Definition A.1. ∎

For more context, we sketch how the transformations from our PAC-verification
protocols fall into this framework.

  1. 1.

Heavy Fourier coefficients (Theorem 4.1) The transformation is presented in
Theorem 3.2. Item 2 of the definition is trivially satisfied by picking
$i\in[Q]$ uniformly at random and embedding a random example $w$ (drawn from
the uniform distribution) in $\hat{y}_{i}$. For Item 3, first observe from 4.6
that all the “small” query sets are independent of each other. By Proposition
A.2 it suffices to embed $w$ into a small query set as the overall query set
is an independent union of embeddable query sets. In turn, Item 3 holds for
the small query set since it has a linear query pattern (see Definition 6.1),
from Lemma 6.2, coupled with the fact that the marginal distribution of each
query and underlying distribution over $w$ are both uniform distributions.

  2. 2.

$\mathsf{AC}^{0}[2]$ (Theorem 5.1) The transformation is presented in the
proof of Theorem 5.1. Observe from Algorithm 6, that a random example $w$
(drawn from the uniform distribution) is placed by sampling a subcube to embed
in, with probability given by its density. Item 2 follows by coupling this
with the fact that since $w$ is a uniformly random string, the probability of
it being any particular element within a subcube query is also uniform.

Item 3 follows, since the restriction of $w$ (based on its embedded subcube),
that is also a uniformly random substring, is used to fix the seed $z$ by the
embedded NW-query construction algorithm from Algorithm 6 to generate all its
subcube queries.

We leave the study of potentially embedding multiple random examples in query
sets that are adaptive (based on past prover messages and/or verifier
queries), and their applicability in query to sample transformations for PAC-
verification for future work.