Learning Constant-Depth Circuits in
Malicious Noise Models

Suppose, for contradiction, that for all $\tau\in[0,B]$ we have

We may integrate over $\tau\in[0,B]$ both sides of the above inequality, since the corresponding functions of $\tau$ have finite number of discontinuities (at most equal to $|S^{(i)}|+|S_{\mathrm{ref}}|$).

We will now substitute the integrals above with expectations, i.e., $\int_{\tau=0}^{B}\operatorname*{\mathbb{P}}_{\mathbf{x}\sim S^{(i)}}[p^{*}(\mathbf{x})>\tau]\,d\tau=\operatorname*{\mathbb{E}}_{\mathbf{x}\sim S^{(i)}}[p^{*}(\mathbf{x})]$ and $\int_{\tau=0}^{B}\operatorname*{\mathbb{P}}_{\mathbf{x}\sim S_{\mathrm{ref}}}[p^{*}(\mathbf{x})>\tau]\,d\tau=\operatorname*{\mathbb{E}}_{\mathbf{x}\sim S_{\mathrm{ref}}}[p^{*}(\mathbf{x})]$. We use the simple fact that for any non-negative random variable $X$ with values in $[0,B]$, we have $\operatorname*{\mathbb{E}}[X]=\int_{\tau=0}^{B}\operatorname*{\mathbb{P}}[X>\tau]\,d\tau$.

We first set $X=p^{*}(\mathbf{x})$, where $\mathbf{x}\sim S^{(i)}$ and observe that (1) $p^{*}(\mathbf{x})\geq 0$ for all $\mathbf{x}\in S^{(i)}$, and also that (2) $p^{*}(\mathbf{x})\leq\|p\|_{\mathrm{coef}}\leq B$ for all $\mathbf{x}\in\{\pm 1\}^{d}\supseteq S^{(i)}$, since $p^{*}$ satisfies $\|p\|_{\mathrm{coef}}\leq B$ according to the constraints of (P) and $p^{*}(\mathbf{x})=\sum_{\mathcal{I}\subseteq[d]}c_{p^{*}}(\mathcal{I})\mathbf{x}^{\mathcal{I}}\leq\sum_{\mathcal{I}\subseteq[d]}|c_{p^{*}}(\mathcal{I})|\cdot|\mathbf{x}^{\mathcal{I}}|=\sum_{\mathcal{I}\subseteq[d]}|c_{p^{*}}(\mathcal{I})|=\|p^{*}\|_{\mathrm{coef}}$, since $\mathbf{x}\in\{\pm 1\}^{d}$ and therefore $|\mathbf{x}^{\mathcal{I}}|=1$. This shows that $X\in[0,B]$ almost surely over $\mathbf{x}\sim S^{(i)}$. Using an analogous argument for $\mathbf{x}\sim S_{\mathrm{ref}}$, we overall obtain the following.

We may now substitute (3.2) in the inequality (3.1), and use the fact that $\operatorname*{\mathbb{E}}_{\mathbf{x}\sim S_{\mathrm{ref}}}[p^{*}(\mathbf{x})]\leq\epsilon/4$ (by the constraints of (P)) to conclude that

We reached a contradiction, since $\lambda^{*}>\epsilon$, and, therefore, $\tau^{*}$ exists. ∎

By the previous claim, we know that $\tau^{*}$ (which defines the set $S_{r}^{(i)}$) exists and has the property that $\frac{|S^{(i)}|}{N}\operatorname*{\mathbb{P}}_{\mathbf{x}\sim S^{(i)}}[p^{*}(\mathbf{x})>\tau^{*}]\geq 2\operatorname*{\mathbb{P}}_{\mathbf{x}\sim S_{\mathrm{ref}}}[p^{*}(\mathbf{x})>\tau^{*}]+\Delta$.

We first focus on the quantity $\operatorname*{\mathbb{P}}_{\mathbf{x}\sim S_{\mathrm{ref}}}[p^{*}(\mathbf{x})>\tau^{*}]$, which is proportional to the number of reference examples that would be removed by the thresholding operation $p^{*}(\mathbf{x})>\tau^{*}$. However, we are interested in the number of actual clean examples that would be removed. The reference examples can be shown to provide an estimate of the number of removed clean examples, through uniform convergence. In particular, the thresholding operation corresponds to a polynomial threshold function of degree at most $d^{k}$ and, therefore, by standard VC dimension arguments (and uniformly for all iterations) we have that $\operatorname*{\mathbb{P}}_{\mathbf{x}\sim S_{\mathrm{ref}}}[p^{*}(\mathbf{x})>\tau^{*}]\geq\operatorname*{\mathbb{P}}_{\mathbf{x}\sim S_{\mathrm{cln}}}[p^{*}(\mathbf{x})>\tau^{*}]-\Delta/2$, except with probability $\delta$ , as long as the sample size is $N\geq C^{\prime}\frac{d^{k}+\log(1/\delta)}{\Delta^{2}}$. This is because both $S_{\mathrm{ref}}$ and $S_{\mathrm{cln}}$ consist of $N$ i.i.d. samples from the uniform distribution.

Overall, we have that $\frac{|S^{(i)}|}{N}\operatorname*{\mathbb{P}}_{\mathbf{x}\sim S^{(i)}}[p^{*}(\mathbf{x})>\tau^{*}]\geq 2\operatorname*{\mathbb{P}}_{\mathbf{x}\sim S_{\mathrm{cln}}}[p^{*}(\mathbf{x})>\tau^{*}]$. We can write the empirical probabilities in terms of the sizes of the removed sets to obtain the following, where we also use the fact that $|S_{r}^{(i)}|=|S_{r,\mathrm{cln}}^{(i)}|+|S_{r,\mathrm{adv}}^{(i)}|$ and that $|S_{r,\mathrm{cln}}^{(i)}|$ is at most equal to the number of clean examples that would be removed by the $i$-th filtering operation (some clean examples could already have been removed either by the adversary or by some previous iteration and these will not be contained in $S_{r,\mathrm{cln}}^{(i)}$).

This concludes the proof of the claim. ∎

The degree bound and non-negativity are satisfied directly by the definition of $p$. We now need to show that $\|p\|_{\mathrm{coef}}\leq 3^{k}d^{k/2}$. Recall that $p(\mathbf{x})=\sum_{\mathcal{I}\subseteq[d]}c_{p}(\mathcal{I})\mathbf{x}^{S}$, where $c_{p}(\mathcal{I})=0$ for any $|\mathcal{I}|>k$ and $\|p\|_{\mathrm{coef}}=\sum_{\mathcal{I}\subseteq[d]}|c_{p}(\mathcal{I})|$. By viewing $c_{p}$ as a vector with $\sum_{j=0}^{k}\binom{d}{j}\leq d^{k}$ dimensions (assuming $2\leq k\leq d$), we have that $\|p\|_{\mathrm{coef}}=\|c_{p}\|_{1}\leq d^{k/2}\|c_{p}\|_{2}=d^{k/2}(\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\operatorname{Unif}_{d}}[(p(\mathbf{x}))^{2}])^{1/2}$.

Since the uniform distribution is $(2,1)$-hypercontractive (see Theorem 9.22 in [O’D14]), we have

Recall that the polynomial $p$ is non-negative. This implies that $|p(\mathbf{x})|=p(\mathbf{x})$ for all $\mathbf{x}\in\{\pm 1\}^{d}$ and therefore $\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\operatorname{Unif}_{d}}[|p(\mathbf{x})|]=\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\operatorname{Unif}_{d}}[p(\mathbf{x})]\leq\epsilon/8$. Overall, we have

Recall, now, that $\|p\|_{\mathrm{coef}}\leq d^{k/2}(\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\operatorname{Unif}_{d}}[(p(\mathbf{x}))^{2}])^{1/2}$. We obtain the desired bound $\|p\|_{\mathrm{coef}}\leq 3^{k}d^{k/2}$.

It remains to show that with probability at least $1-\delta$, we have $\frac{1}{N}\sum_{\mathbf{x}\in S_{\mathrm{ref}}}p(\mathbf{x})\leq\epsilon/4$. Consider the random variable $X=\frac{1}{N}\sum_{\mathbf{x}\in S_{\mathrm{ref}}}p(\mathbf{x})$, where $S_{\mathrm{ref}}$ is drawn i.i.d. form $\operatorname{Unif}_{d}$. We have that $\operatorname*{\mathbb{E}}[X]=\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\operatorname{Unif}_{d}}[p(\mathbf{x})]\leq\epsilon/8$. Moreover, $p(\mathbf{x})\leq\|p\|_{\mathrm{coef}}\leq 3^{k}d^{k/2}$, for all $\mathbf{x}\in\{\pm 1\}^{d}$ and, from a standard Hoeffding bound on the random variable $X$, we obtain that $\frac{1}{N}\sum_{\mathbf{x}\in S_{\mathrm{ref}}}p(\mathbf{x})\leq\epsilon/4$ with probability at least $1-\exp(-\frac{\epsilon^{2}}{64Nd^{k}9^{k}})$. Due to the choice of $N\geq C^{\prime}\frac{d^{k}9^{k}}{\epsilon^{2}}\log(1/\delta)$, we have that the probability of failure is bounded by $\delta$, as desired. ∎

Consider the polynomial $p=p_{\mathrm{up}}-p_{\mathrm{down}}$, where $p_{\mathrm{up}},p_{\mathrm{down}}$ are the $(\epsilon/8)$-sandwiching polynomials of some circuit $f$ of size $s$ and depth $\ell$. Observe that $p$ is non-negative and $\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\operatorname{Unif}_{d}}[p(\mathbf{x})]\leq\epsilon/8$. Therefore, according to part 2 of Lemma 3.1, we have $\sum_{\mathbf{x}\in S_{\mathrm{filt}}}p(\mathbf{x})\leq\epsilon N$. Since $p_{\mathrm{up}}\geq f\geq p_{\mathrm{down}}$ we also have $\operatorname*{\mathbb{E}}_{\mathbf{x}\sim S_{\mathrm{filt}}}[|f(\mathbf{x})-p_{\mathrm{down}}(\mathbf{x})|]\leq\epsilon N/|\bar{S}_{\mathrm{filt}}|$. By Theorem 4.1, we find $h:\{\pm 1\}^{d}\to\{\pm 1\}$ with $\operatorname*{\mathbb{P}}_{(\mathbf{x},y)\sim\bar{S}_{\mathrm{filt}}}[y\neq h(\mathbf{x})]\leq\min_{f\in\mathcal{C}}\operatorname*{\mathbb{P}}_{(\mathbf{x},y)\sim\bar{S}_{\mathrm{filt}}}[y\neq f(\mathbf{x})]+2\epsilon N/|\bar{S}_{\mathrm{filt}}|$ or equivalently

The error of the hypothesis $h$ on the set $\bar{S}_{\mathrm{cln}}$ gives a bound on its error under the uniform distribution with high probability, due to classical VC theory, as long as $N\geq C^{\prime}\frac{d^{k}+\log(1/\delta)}{\epsilon^{2}}$, because $h$ is a PTF of degree at most $k$. We can provide an upper bound for $\operatorname*{\mathbb{P}}_{(\mathbf{x},y)\sim\bar{S}_{\mathrm{cln}}}[y\neq h(\mathbf{x})]$ in terms of the sizes of the sets depicted in Figure 1. In particular, we give a high-probability upper bound on the number of mistakes that $h$ makes on $\bar{S}_{\mathrm{cln}}$.

1. 1.

   The points in $\bar{S}_{\mathrm{cln}}$ that are removed by the adversary are not taken into account while forming $h$, so, in the worst case, $h$ classifies them incorrectly. This gives at most $|S_{\mathrm{cln}}\setminus S_{\mathrm{inp}}|$ mistakes.

2. 2.

   Similarly, $h$ makes at most $|S_{3}|$ mistakes corresponding to the clean points that are removed during the outlier removal process.

3. 3.

   Finally, $h$ will make at most $|S_{2}|+2\epsilon N$ mistakes on $S_{\mathrm{filt}}$, according to the inequality (4.1), corresponding to the adversarially corrupted points that were not removed during the outlier removal process. In the worst case, all of these mistakes are made in the part of $S_{\mathrm{filt}}$ that intersects $S_{\mathrm{cln}}$.

The overall error is $\frac{1}{N}(|S_{\mathrm{cln}}\setminus S_{\mathrm{inp}}|+|S_{3}|+|S_{2}|)+O(\epsilon)$. According to part 1 of Lemma 3.1, we have $|S_{3}|\leq|S_{1}|$. Moreover, by Definition 1.1, we have that $|S_{\mathrm{cln}}\setminus S_{\mathrm{inp}}|=|S_{\mathrm{inp}}\setminus S_{\mathrm{cln}}|=|S_{1}|+|S_{2}|=\eta N$. The error bound we obtain overall is $2\eta+O(\epsilon)$, as desired. ∎