Learning Geometric Concepts with Nasty Noise

Introduction

Polynomial Threshold Functions (PTFs) and intersections of Linear Threshold Functions (LTFs) are two fundamental classes of Boolean functions that have been extensively studied in many contexts for at least the past five decades [Der65, MP68, Mur71]. In the noiseless setting, low-degree PTFs are known to be efficiently PAC learnable under arbitrary distributions via linear programming [MT94]. The current state-of-the-art for PAC learning intersections of LTFs is as follows: Even without noise, distribution-independent PAC learning for intersections of $2$ LTFs is one of the most challenging open problems in computational learning theory. Efficient algorithms are known for PAC learning intersections of any constant number of LTFs under well-behaved distributions, e.g., under the standard Gaussian distribution [Vem10b, Vem10a]. Dealing with (adversarial) noisy data turns out to be significantly more challenging in general. Recent results (see, e.g., [DLS14, Dan16]) provide strong evidence that learning with adversarial noise is computationally intractable under arbitrary distributions, even for simple concept classes.

In this paper, we focus on the efficient learnability of low-degree PTFs and intersections of (any constant number of) LTFs in the presence of nasty noise. In the nasty noise model [BEK02], an omniscient adversary can arbitrarily corrupt a small fraction of both the unlabeled data points and their labels. The nasty model generalizes a number of well-studied noise models, including the malicious noise model [Val85, KL93]In the malicious model, an adversary can corrupt a small fraction of both the unlabeled examples and their labels. This model is qualitatively similar to (but somewhat weaker than) the nasty noise model. We define these models and explain the relation between them in Section 1.2. and the agnostic (adversarial label noise) model [Hau92, KSS94]. While these noise models were originally defined with respect to arbitrary distributions, it has been recently shown [Dan16] (modulo plausible complexity assumptions) that, even for the class of LTFs, no computationally efficient algorithm can achieve dimension-independent error guarantees. Hence, research in this area has focused on noise-tolerant learning under a number of “tame” distributions. Our goal in this paper is to design polynomial-time robust learning algorithms that can tolerate nasty noise of constant rate, i.e., we want to achieve error guarantees that are independent of the dimension.

Perhaps surprisingly, the concept class of origin-centered LTFs is the only family of Boolean functions for which polynomial-time algorithms are known in the malicious model. This motivates the following broad question that was posed as an open problem in previous work [KLS09, ABL17]:

Are there computationally efficient learning algorithms in the malicious noise model – with dimension-independent error guarantees – for more general classes of Boolean functions?

In this paper, we study this question with a focus on more general geometric concept classes, namely low-degree PTFs and intersections of a constant number of LTFs. We provide new algorithmic and analytic techniques that yield the first polynomial-time PAC learning algorithms for these concept classes in the nasty noise model (hence, in the malicious model as well) with dimension-independent error guarantees.

Specifically, we give a robust learning algorithm for low-degree PTFs in the nasty model that succeeds under a number of well-behaved distributions – including the Gaussian distribution and, more generally, any log-concave distribution with (approximately) known low-degree moments. Prior to our work, no non-trivial efficient learning algorithm was known (even) for degree-$2$ PTFs in the (weaker) malicious noise model. (As an implication of our techniques, we also obtain the first efficient learning algorithm with dimension-independent error in the nasty model for LTFs under the uniform distribution on the hypercube.)

For LTFs under the Gaussian distribution, using additional ideas, we give a polynomial-time algorithm that achieves error $O(\epsilon)$, where $\epsilon$ is the noise rate, i.e., it matches the information-theoretically optimal error, up to a constant factor. This is the first malicious/nasty learning algorithm for the class of arbitrary LTFs that achieves error $O(\epsilon)$ in polynomial time. Our result improves on prior work by Awasthi et al. [ABL17] in two respects: First, [ABL17] achieved an $O(\epsilon)$ error bound for the special case of origin-centered LTFs, and second their algorithm applies to the weaker malicious/agnostic models. On the other hand, the $O(\epsilon)$ bound of [ABL17] holds for the more general family of isotropic log-concave distributions.

Our third result is a polynomial-time learning algorithm with dimension-independent error guarantees for intersections of (any constant number of) LTFs in the nasty model under the Gaussian distribution. To the best of our knowledge, no efficient algorithm (with non-trivial error guarantees) was previously known even for intersections of $2$ LTFs in the (weaker) malicious noise model.

At the core of our results is an efficient algorithm to approximate the low-degree Chow parameters of any bounded function in the presence of nasty noise. Roughly speaking, the low-degree Chow parameters of a function $f$ under a distribution $D$ are the “correlations” of $f$ (with respect to $D$) with all low-degree monomials (see Section 1.4 for the formal definition). Our algorithm succeeds for a range of reasonable distributions $D$ satisfying mild concentration bounds and moment assumptions. At a high-level, our robust (low-degree Chow parameter estimation) algorithm employs an iterative spectral technique for outlier detection and removal, inspired by recent work in robust unsupervised learning [DKK+16]. Our technique filters out corrupted points relying on the concentration of carefully chosen low-degree polynomials.

Our robust learning algorithms for PTFs and intersections of LTFs use our Chow-parameters estimation algorithm as a basic subroutine. That is, for both concept classes, our algorithms proceed in two steps: (1) We start by approximating the “low-degree” Chow parameters of our function, and (2) We use our approximate Chow parameters from Step (1) to find a proper hypothesis that is close to the target concept.

The algorithm for Step (2) differs for PTFs and intersections of LTFs. For degree-$d$ PTFs, we use the fact that approximations to the degree-$d$ Chow parameters information-theoretically approximately determines our function. Given this fact, we leverage known algorithmic techniques [TTV08, DDFS14] that allow us to efficiently find an accurate proper hypothesis with approximately these Chow parameters. For intersections of $k$ LTFs, we rely on approximations to the degree-$2$ Chow parameters. In this case, these parameters allow us to reduce our $n$-dimensional learning problem to a $(k+1)$-dimensional problem that we can efficiently solve by a simple net-based method. The correctness of this scheme crucially relies on a novel structural result about intersections of LTFs under the Gaussian distribution that may be of broader interest.

2 Noise Models

3 Previous Work

We now summarize the prior work that is most relevant to the results of this paper.

As mentioned in the preceding discussion, the malicious noise model with respect to arbitrary distributions is known to be very challenging computationally. Even for the class of $n$-dimensional LTFs, the only known efficient algorithm [KL93] achieves an error of $\Omega(\epsilon n)$, where $\epsilon$ is the noise rate. Improving on this bound has remained a challenge for a long time, and it was recently shown [Dan16] that this holds for a reason: under plausible complexity assumptions, no efficient algorithm can achieve error at most $1/2-1/n^{c}$, for some constant $c>0$, even if $\epsilon$ is an arbitrarily small constant.

At the technical level, the algorithm of [KLS09] uses a simple outlier removal method to approximate the degree-$1$ Chow parameters, and then finds an LTF with approximately these Chow parameters. (That is, the high-level approach of our work for learning degree-$d$ PTFs is a broad generalization of the [KLS09] approach.) It is worth noting that the outlier removal procedure of [KLS09] is a weaker version of the filtering technique from [DKK+16]. On the other hand, the algorithm of [ABL17] uses a soft outlier removal procedure together with localization. Instead of using degree-$1$ Chow parameters, [ABL17] uses hinge-loss minimization, which can be solved via a convex program.

Finally, we remark that our work is related to a sequence of recent results on robust estimation in the unsupervised setting [DKK+16, DKK+17a, DKK+17b]. Specifically, our general algorithm to approximate the low-degree Chow parameters with nasty noise is inspired by the outlier removal technique of [DKK+16]. We emphasize however that the setting considered here is vastly more general than that of [DKK+16]. As a result, a number of new conceptual and technical ideas are required, that we introduce in this paper.

4 Preliminaries

We say that a set of labeled samples $S$ is $\epsilon$-corrupted if it is generated in the nasty model at noise rate $\epsilon$, i.e., the adversary is allowed to corrupt an $\epsilon$-fraction of samples.

5 Our Results

We start by stating our core efficient procedure that approximates the low-degree Chow parameters of any bounded function under tame distributions in the presence of nasty noise:

Our first PAC learning result is an efficient algorithm for low-degree PTFs in the nasty noise model:

This is the first polynomial-time algorithm for learning degree-$d$ PTFs, for any $d>1$, in the malicious/nasty noise model with dimension-independent error guarantees. The algorithm of Theorem 1.2 starts by approximating the degree-$d$ Chow parameters of our PTF $f$ using Theorem 1.1, and then employs known techniques [TTV08, DDFS14] to find a PTF $h$ with approximately these Chow parameters. The fact that $\Pr_{X\sim D}[h(X)\neq f(X)]$ will be small follows from the simple fact that, for the considered distributions, approximation in Chow distance implies approximation in $L_{1}$-distance. (This holds for distributions $D$ such that $p(D)$ has non-trivial concentration and anticoncentration properties for all degree-$d$ polynomials $p$.)

Note that the special case of Theorem 1.2 for $d=1$ (LTFs) is a generalization of [ABL17], as our result applies to all LTFs (not necessarily origin-centered). We only require knowledge of the first $2$ moments of the underlying log-concave distribution in this case, which is equivalent to assuming isotropic position as is done in [ABL17]. For $d=1$ under isotropic log-concave distributions, the final accuracy of our algorithm will be $O(\sqrt{\epsilon})$, while [ABL17] obtains an $O(\epsilon)$ error bound for origin-centered LTFs. Finally, we note that for $d=1$, Theorem 1.2 also holds under the uniform distribution on the hypercube, with a quantitatively worse – but still dimension-independent – error of $2^{-\Omega(\sqrt{\log(1/\epsilon)})}.$ This follows by using the structural result of [DDFS14] relating closeness in Chow distance and $L_{1}$-distance in the Boolean domain.

We note that, for the case of LTFs under the Gaussian distribution, the algorithm of Theorem 1.2 has final $L_{1}$-error of $O(\epsilon\sqrt{\log(1/\epsilon)})$ (see Corollary 4.5). For this setting, we can in fact obtain an efficient algorithm with near-optimal error guarantee:

Our algorithm for Theorem 1.3 starts from the $O(\epsilon\sqrt{\log(1/\epsilon)})$ approximate LTF of Theorem 1.2 and uses a new twist of the localization technique of [ABL17] to reduce the error down to $O(\epsilon)$. We note that a number of new ideas are required here to make this approach work for all LTFs, as opposed to only origin-centered ones, and to be able to handle nasty noise.

Our third algorithmic result gives the first efficient learning algorithm for intersections of LTFs in the malicious/nasty noise model:

For Theorem 1.4, after approximating the degree-$2$ Chow parameters of $f$, we give a relatively simple method to reduce the problem down to $k$ dimensions. The correctness of this dimension-reduction scheme makes essential use of the following new structural result, that we believe is of broader interest:

6 Our Techniques

In this section, we give a detailed outline of our techniques in tandem with a comparison to previous work.

All our robust PAC learning results hinge on a new algorithm to approximate the degree-$d$ Chow parameters of any bounded function with respect to a sufficiently nice distribution $D$, even under noise in the nasty model (see Proposition 2.2). Before we explain the ideas underlying this algorithm, we elaborate on the metric in which these approximations are guaranteed to be “close”. To motivate our choice of metric, we will first discuss another interpretation of the degree-$d$ Chow parameters of a function $f$. In particular, these parameters encode a linear functional mapping degree at most $d$ polynomials $p$ to the expectation $\mathbf{E}_{X\sim D}[p(X)f(X)]$. It is natural to put a norm on Chow parameters that is the dual of the $L_{2}$ norm on polynomials $p$ (with respect to $D$). In particular, when we say that we have approximated the degree-$d$ Chow parameters of $f$ to within error $\delta$, we will mean that we have found a linear functional $L$ mapping degree at most $d$ polynomials to real numbers so that for any normalized degree-$d$ polynomial $p$, we have that $|L(p)-\mathbf{E}_{X\sim D}[p(X)f(X)]|\leq\delta$.

We start by noting that if we had access to noiseless samples, the desired approximation would be easy to perform. In particular, we could take $L(p)$ to be the empirical expectation of $p(x)f(x)$, and then – so long as $D$ satisfies even mild concentration bounds – with sufficiently many samples it is straightforward to show that this will be a good approximation with high probability. It turns out that so long as we have reasonably good tail bounds for $p(D)$, this empirical approximation also works well even against noise in the adversarial label (agnostic) noise model. This holds essentially because changing the value of $f$ on a small number of samples can only have a large impact on the expectation of $p(x)f(x)$ if $p$ is especially large a decent fraction of the time.

The situation becomes substantially more challenging when the noise can adversarially corrupt the unlabeled examples as well, and in particular in the nasty noise model. The essential problem here is that the error in the values allows an adversary to produce many sample values where $p(x)$ is unusually large for some particular $p$, and this will – almost regardless of the labels of these points – cause substantial errors in the empirical expectation of $p(x)f(x)$. In order to circumvent this obstacle, we will need a technique for detecting and removing these outliers, and for this we will make use of a “filter” technique inspired by recent work on robust distribution learning [DKK+16].

The basic idea here is that if the algorithm knew which polynomials $p$ the adversary was trying to corrupt, it could simply remove all of the sample points for which $p(x)$ was too large, thus removing these errors. Unfortunately, every sample $x$ will have $p(x)$ be abnormally large for some polynomials $p$, so our algorithm will need to find a way to identify particular polynomials for which our expectation may have been substantially corrupted. In order to achieve this, we note that since there must be many erroneous points for which $|p(x)|$ is large, this will cause the empirical expectation of $p^{2}(x)$ to be substantially larger than it should be. This anomaly can be detected (assuming that the algorithm knows good approximations to the true $2d^{th}$ moments of $D$) by a spectral technique, namely an eigenvalue computation. If such a $p$ is found then, assuming good tail bounds on the distribution of $p(D)$, the fact that we have many data points with much larger values of $p(x)$ than should be likely, will allow us to find a large set of samples most of which are corrupted. This step essentially produces a strictly cleaner version of our original corrupted sample set, and by iterating this algorithm we eventually reach a point where there are no longer any bad polynomials. At this point, we can show that the empirical approximation of the Chow parameters will be accurate.

Although the basic intuition outlined above is well in line with recent works [DKK+16, DKK+17b] making use of the filter technique, there are a few crucial technical differences in our setting. The first of these is that we are now working in a much more general context. Previous works tended to make very specific assumptions about the underlying distribution (e.g., Gaussian or balanced product distribution). Here, we are only making assumptions about tail bounds of higher-degree polynomials. Importantly, existing works typically only needed to ensure that the expectations of degree-$1$ and $2$ polynomials were correct, while in our setting we will inherently need to use filters dealing with polynomials of larger degrees. We also run into a new technical complication in the initial steps of the algorithm. In order to get the filter technique to work, we need to begin by throwing away all of the “extreme” outliers. This is required for somewhat technical reasons involving showing that a number of necessary concentration bounds hold. In previous works, the criteria for identifying these extreme outliers were generally fairly simple (e.g., throwing away a point being too far from the mean in some appropriate metric). However, in our case, we have less structure to deal with, and therefore need a somewhat more general criterion. In particular, we throw away outliers where $|p(x)|$ is too large for any normalized degree-$d$ polynomial $p$.

Our robust algorithm for low-degree Chow parameter estimation has immediate applications for robustly learning the Chow parameters over a distribution $D$, if $D$ is a Gaussian, Bernoulli, or log-concave distribution (where in the latter case, the algorithm must also know the low-degree moments of $D$). In the following paragraphs, we explain how to apply this algorithm as a core subroutine to robustly PAC learn geometric concept classes.

Robust Learning for Low-Degree PTFs.

We note that, for large constant $d$, one cannot expect to do substantially better than this bound using only an approximation of the degree-$d$ Chow parameters. This is because there are pairs of degree-$d$ PTFs for which this $\epsilon$ vs. $\epsilon^{1/d}$ type relation is nearly tight. This suggests some sort of “integrality gap” getting in the way: No generic algorithm will be able to learn the low-degree Chow parameters of an $\epsilon$-noisy PTF to error better than $\epsilon$, and no generic algorithm will be able to learn a degree-$d$ PTF to error better than $\epsilon^{1/d}$ from its degree-$d$ Chow parameters. However, this is not the case for the special case of linear threshold functions, where $L_{1}$-distance and Chow distance are indeed proportional.

Optimally Robust Learning of LTFs.

For the case of LTFs, the relation between Chow distance and $L_{1}$-distance allows for the possibility of a much better algorithm: that of learning LTFs to an optimal $O(\epsilon)$ error. In fact, we give such an algorithm over the Gaussian distribution. We note that a naive application of the ideas of the previous paragraph is already sufficient to obtain an error of only $O(\epsilon\sqrt{\log(1/\epsilon)})$. Removing the final logarithmic term requires several new ideas. The overarching principle in our new algorithm is to use the localization technique of [ABL17], though with slightly different technical backing.

Our algorithm will run an initial first pass to obtain an $O(\epsilon\sqrt{\log(1/\epsilon)})$ approximation to $f$. This step approximates $f$ by an LTF with separator given by some hyperplane $H$. We will then perform rejection sampling on our inputs in order to simulate samples from another Gaussian distribution centered around $H$. Learning $f$ with respect to this new input distribution will allow us to refine our original guess.

There are two major impacts of our restriction procedure. The first is that if most of the erroneous samples are near $H$, they might survive the rejection sampling process with higher probability than other points. This means that the fraction of errors in our simulated sample set may be much larger. To compensate for this though, this restriction will amplify the effect of small errors in $f$, as moving away from $H$ now much more quickly moves one away from the center of the distribution. This means that learning even rough information about the restriction of $f$ will give us useful information about the original problem. These two effects, as it turns out nearly cancel each other out, with the exception that the $\sqrt{\log(1/\epsilon)}$ term in the error becomes a $\sqrt{\log(1/\delta)}$, where $\delta$ is the (now much larger) error rate for the restricted distribution. By iterating this technique with thinner and thinner restrictions, we can eventually converge on $f$ to an error of only $O(\epsilon)$.

Robust Learning of Intersections of LTFs.

As a final application, we give a robust algorithm for learning intersections of LTFs with respect to the Gaussian distribution. This algorithm is very different than the one for PTFs, as it is not possible to recover such a function from its low-degree Chow parameters directly. For this problem, we will need to make use of a somewhat different idea.

The key insight is that if $f$ is the indicator function of an intersection of $k$ halfspaces, then $f$ only depends on $k$ linear functions of the input. If we could identify these directions, we could project our inputs down to a $k$-dimensional subspace and proceed by applying even relatively inefficient algorithms to learn a function on this low-dimensional space. In order to learn this subspace, we note that for any $v$ perpendicular to all directions of interest, $f(G)$ is uncorrelated with $p(v\cdot G)$ for any function (and in particular polynomial function) $p$. If we knew the degree-$2$ Chow parameters of $f$, this would imply that $v$ was a null-vector of the associated matrix. This would allow us to easily identify such vectors $v$.

In order to turn this into an algorithm, we will first need an inverse version of this theorem. Namely, that if for some vector $v$ that $f$ is uncorrelated with $p(v\cdot G)$ for all degree-$2$ polynomials $p$, we will need to know that $f$ is in fact independent of the $v$-direction. In fact, since we only know approximations to the Chow parameters, we will need a robust version of this statement. Namely if for all degree-$2$ polynomials $p$, we have that $f$ is nearly uncorrelated to $p(v\cdot G)$, that $f$ will be nearly constant in the $v$-direction. See Theorem 5.2 for the technical statement of this result.

The aforementioned robust structural result allows a very natural algorithm: We start by learning approximations of the degree-$1$ and $2$ Chow parameters of $f$. We then let $V$ be the subspace spanned by the vector of degree-$1$ Chow parameters and the largest $k$ eigenvalues of the matrix corresponding to the degree-$2$ Chow parameters. It is not hard to see that $f$ is nearly uncorrelated to $p(v\cdot G)$ for any $v\perp V$. This along with the above structural result allows us to approximate $f(x)$ by a function that depends only on the projection $\pi_{V}(x)$, which as described above, can be learned by brute-force methods.

We note that the algorithm of [Vem10a] for finding the $k$-dimensional invariant subspace is similar to ours. Instead of considering the largest eigenvalues of the degree-$2$ Chow parameters, the algorithm of [Vem10a] relies on the smallest eigenvalues of the covariance of the positive samples, which is roughly equivalent. The correctness of this algorithm uses the following lemma: in the $k$-dimensional subspace in which the intersection is non-trivial, the variance of the positive samples is less than one, which has some similarities with our structural result. The major difference is that our structural lemma is robust, and as a result our algorithm can tolerate nasty noise (using our approximations to the Chow parameters).

7 Organization

The structure of this paper is as follows: In Section 2, we give our algorithm to robustly estimate the low-degree Chow parameters of a bounded function, thereby establishing Theorem 1.1. In Section 3, we describe the required machinery to prove Theorem 1.2. Section 4 proves our robust learning algorithm for LTFs with near-optimal accuracy (Theorem 1.3). Finally, in Section 5, we give our algorithm for robustly learning intersections of LTFs (Theorem 1.4) and the associated structural result (Theorem 1.5).

Robust Estimation of Low-Degree Chow Parameters

Specifically, we introduce the following definition:

(Concentration) A tail bound for all degree at most $d$ polynomials: that is, a function $Q_{d}(T)$ such that for all polynomials $p(x)$ with $\|p\|_{2}\leq 1$, $\Pr_{X\sim D}[|p(X)|\geq T]\leq Q_{d}(T)$.

(Known Approximations of Low-Degree Moments) A matrix $\Sigma$ such that $(1-\gamma)\mathbf{E}_{X\sim D}[m(X)m(X)^{T}]\preceq\Sigma\preceq(1+\gamma)\mathbf{E}_{X\sim D}[m(X)m(X)^{T}]$, for some relative error $\gamma>0$ that is smaller than a sufficiently small constant.

A parameter $\delta>0$ that satisfies $\delta\geq\int_{0}^{\infty}T\min\{\epsilon,Q_{d}(T)\}dT$. Intuitively, the parameter $\delta$ is the maximum amount by which an $\epsilon$-probability mass can contribute to the $\mathbf{E}_{X\sim D}[p^{2}(X)]$.

We will see in the next section that many common distributions satisfy this definition (for appropriate parameters), including the Gaussian distribution, log-concave distributions, the uniform distribution over the hypercube, etc.

Now we can state the main proposition from which our main algorithmic applications will follow:

At a high-level, the algorithm works as follows: First, we pre-process our corrupted set of samples $S^{\prime}$ using a basic pruning step. Specifically, we remove samples $x\in S^{\prime}$ such that there is a polynomial of degree at most $d$ with $\|p\|_{2}=1$ and $|p(x)|\geq T_{\max}$. Our main algorithm is an iterative filtering procedure: Using the largest eigenvalue and eigenvector of an appropriate matrix, we can detect whether there is such a polynomial $p$ whose variance is bigger in $S^{\prime}$ than $D$. If there is, we can use the tail bound $Q_{d}(T)$ to find a filter that throws out points where $|p(x)|$ is too large. If there is no such polynomial, then we show that the empirical Chow parameters suffice, so we output those. Formally, the algorithm is the following:

The algorithm as written assumes that $\Sigma$ is non-singular. If it is singular, we can find its null vectors. Each of these corresponds to a non-constant polynomial $p(x)$ with $\mathbf{E}_{X\sim D}[p(X)^{2}]=0$ and so with probability $1$, $p(x)=0$. If we pre-process by removing all points with $p(x)\neq 0$ for all such polynomials, then we can ignore these null-vectors. We can then replace all the inverses in the algorithm with Moore-Penrose pseudo-inverses and still get the same guarantee.

For all $T>0$, we have that $\left|\Pr_{X\in_{u}S}\left[p(X)>T\right]-\Pr_{X\sim D}\left[p(X)>T\right]\right|\leq\epsilon/(10T_{\max}^{2})$.

A set $S$ that satisfies conditions (i) and (ii) is called $\epsilon$-good.

Before showing that a set of random samples is good, we need a couple of lemmas about our pruning process. Firstly, we show that our pruning indeed implies a bound on the value of the polynomials we consider:

We next need to show that the pruning step does not throw away too many points:

We have that: $\Pr_{X\sim D}\left[m(X)^{T}\Sigma^{-1}m(X)\geq T_{\max}^{2}/2\right]\leq\epsilon/10$. If $S$ is any set of points satisfying Condition (i) of Definition 2.4, then $\Pr_{X\in_{u}S}\left[m(X)^{T}\Sigma^{-1}m(X)\geq T_{\max}^{2}/2\right]\leq\epsilon/5$.

Then we have that $p(x)=\|\Sigma^{-1/2}m(x)\|_{2}\geq T_{\max}/\sqrt{2}$, and that

Recall that, by our assumption on $\Sigma$, we have $(1+\gamma)^{-1}\Sigma\preceq\mathbf{E}_{X\sim D}[m(X)m(X)^{T}]\preceq(1-\gamma)^{-1}\Sigma$, and thus we have

Since $p(x)\geq T_{\max}/\sqrt{2}$, one of these conditions must fail. However, we argued that this event happens with appropriately bounded probabilities under both $S$ and $D$. This completes the proof. ∎

Now we can show that a large enough set of samples drawn from $D$ is $(\epsilon,f)$-good with high probability.

With probability $9/10$, if $S$ is a set of $\Omega(n^{d}T_{\max}^{4}/\epsilon^{2})$ samples from $D$, then $S$ is $(\epsilon,f)$-good.

To establish condition (i), we note that the VC-dimension of the set of degree-$d$ PTFs is $O(n^{d})$. So, by the VC-inequality [DL01], with probability $99/100$, we have that

By a union bound, all the above $99/100$-probability events hold with probability at least $9/10$. This completes the proof. ∎

Now we can analyze the main loop of the algorithm. We either have that the empirical distribution has moments that well approximate those of $D$ or else the algorithm produces a filter that improves $S^{\prime}$. Let $\Delta(G,S^{\prime})$ be the size of the symmetric difference between $G$ and $S^{\prime}$. Then, it suffices to show that a single iteration satisfies the following:

If we run the main loop of the algorithm above on a set $S^{\prime}$ of samples such that $\Delta(G,S^{\prime})\leq 3\epsilon$ for some $\epsilon$-good set $G$, then either (a) we have that $\mathbf{E}_{X\in_{u}S^{\prime}}[p(X)^{2}]\leq 1+O(\gamma+\delta+\epsilon)$, for all polynomials $p(x)$ with degree at most $d$ that have $\|p\|_{2}=1$, or else (b) the loop gives a set $S^{\prime\prime}\subset S^{\prime}$ with $\Delta(G,S^{\prime\prime})\leq\Delta(G,S^{\prime})-\epsilon/(10T_{\max}^{2})$.

The case when we exit the loop is simple. For every polynomial $p(x)$ with degree at most $d$ that has $\|p\|_{2}=1$, there is a vector $v$ such that $p(x)=v^{T}\Sigma^{-1/2}m(x)$. Thus, we have

we deduce that $\|v\|_{2}^{2}\leq 1+\gamma$.

For any polynomial $p(x)=v^{T}\Sigma^{-1/2}m(x)$, we can write:

So, when ${\lambda^{\ast}}\leq O(\gamma+\delta+\epsilon)$, we have $\mathbf{E}_{X\in_{u}S^{\prime}}[p(X)^{2}]\leq 1+O(\gamma+\delta+\epsilon)$ for all such $p(x)$.

It remains to show that the algorithm produces a filter with the desired properties when ${\lambda^{\ast}}\geq\Omega(\gamma+\delta+\epsilon).$ Note that

and so $(1+\gamma)^{-1}\leq\|p^{\ast}\|_{2}^{2}\leq(1-\gamma)^{-1}$. On the other hand, we have $\mathbf{E}_{X\sim_{u}S^{\prime}}[p^{\ast}(x)^{2}]=1+O(\gamma+\lambda^{\ast})$. We show that this is only possible when $\mathbf{E}_{X}[p^{\ast}(X)^{2}]$ is bigger under $S^{\prime}$ than under $D$, and that under these circumstances, we there exists a valid threshold for our filter.

Let $S$ be the subset of $G$ that contains the points $x$ satisfying $m(x)^{T}\Sigma^{-1}m(x)\leq T_{\max}^{2}/2$. Then, we write $S^{\prime}=S\cup E\setminus L$ for disjoint $E$ and $L$. Thus, we have

We start with the following simple lemma:

For all polynomials $p(x)$ with degree at most $d$ and $\|p\|_{2}=1$, we have $|\mathbf{E}_{X\in_{u}S}[p(X)^{2}]-1|\leq O(\epsilon+\delta)$.

On pruned samples $x$, we have that $|p(x)|\leq T_{\max}$ by Lemma 2.5, and therefore

where we used that the set $S$ is the pruned set satisfying Condition (ii) of Definition 2.4. The triangle inequality now gives that

We now show that the contribution of the set $L$ to the expectation of $p^{2}$ is small:

For all polynomials $p$ of degree at most $d$ with $\|p\|_{2}=1$, we have $|L|\cdot\mathbf{E}_{X\in_{u}L}[p(X)^{2}]\leq O(\delta+\epsilon)\cdot|S|$.

Since $L\subset S$, for any event $A$, we have that $|L|\cdot\Pr_{L}[A]\leq|S|\cdot\Pr_{S}[A]$, and therefore

Thus, we have the following sequence of inequalities:

For all polynomials $p$ of degree at most $d$ with $\|p\|_{2}=1$, we have that $\mathbf{E}_{X\in_{u}S^{\prime}}[p(X)^{2}]\geq 1-O(\epsilon+\delta)$.

This follows from the equation for $\mathbf{E}_{X\in_{u}S^{\prime}}[p(X)^{2}]$ similar to (1), using Lemmas 2.10 and 2.9, and the fact that $|E|\cdot\mathbf{E}_{X\in_{u}E}[p(X)^{2}]>0$. ∎

Our goal is to show that our algorithm will indeed find a filter in this case, i.e, there exists $T>0$ such that $\Pr_{X\in_{u}S^{\prime}}\left[|p^{\ast}(X)|\geq T\right]\geq 4Q_{d}(T)+3\epsilon/T_{\max}^{2}$. We will show this by contradiction using the following intermediate lemma:

If for all $T>0$, we have that $\Pr_{X\in_{u}S^{\prime}}\left[|p^{\ast}(X)|\geq T\right]\leq 4Q_{d}(T)+3\epsilon/T_{\max}^{2}$, then we have $|E|\cdot\mathbf{E}_{X\in_{u}E}[p^{\ast}(X)^{2}]\leq O(\gamma+\delta+\epsilon)\cdot|S^{\prime}|$.

Since $E\subset S^{\prime}$, it follows that

Since $\|p^{\ast}\|_{2}^{2}\leq 1+O(\gamma)$, by a similar proof to that in Lemma 2.10 above, we have that

Now we are ready to show that we do find a filter:

If $\lambda^{\ast}\geq\Omega(\gamma+\delta+\epsilon)$, then there exists a $T>0$ with $\Pr_{X\in_{u}S^{\prime}}[|p^{\ast}(X)|\geq T]\geq 4Q_{d}(T)+3\epsilon/T_{\max}^{2}$.

We show the contrapositive. Suppose that there is no such $T$, then by Lemma 2.12 we get that

Now recall that $\|p^{\ast}\|_{2}^{2}\leq 1+O(\gamma)$. We can apply Lemma 2.9 to $p^{\ast}(x)/\|p^{\ast}\|_{2}$ to obtain

Using equation (1) and the fact that $|L|\cdot\mathbf{E}_{X\in_{u}L}[p^{\ast}(X)^{2}]\geq 0$, we have

However, this implies that $\lambda^{\ast}=\mathbf{E}_{X\in_{u}S^{\prime}}[p^{\ast}(X)^{2}]-1=O(\gamma+\delta+\epsilon)$, yielding the desired contradiction. ∎

The algorithm thus finds a filter in this case. We next show that it rejects more points from $E$ than $S$, thus reducing $\Delta(S,S^{\prime})$:

We have that $\Delta(S^{\prime\prime},S)\leq\Delta(S^{\prime},S)-\epsilon/(10T_{\max}^{2})$.

Using the tail bound and the goodness of $S$, we obtain that

On the other hand, the filter rejects samples $x$ with $|p^{\ast}(x)|\geq T$ of which there are at least $(4Q_{d}(T)+3\epsilon/T_{\max}^{2})|S^{\prime}|$ many in $S^{\prime}$. With appropriate choice of constant, we obtain that at least $2/3$ of the rejected samples are from $E$ and not $S^{\prime}$. A similar analysis to Claim 8.12 of [DKK+16] gives the lemma. ∎

Since neither $S^{\prime\prime}$ nor $S^{\prime}$ contain any points $x$ with $m(x)^{T}\Sigma^{-1}m(x)\geq T_{\max}^{2}/2$, we also have $\Delta(S^{\prime\prime},G)\leq\Delta(S^{\prime},G)-\epsilon/(10T_{\max}^{2})$. This completes the proof of Proposition 2.8. ∎

Now we analyze the case that we exit the loop. Our aim is to show the following lemma:

For any polynomial $p$ of degree at most $d$ with $\|p\|_{2}\leq 1$, we have that

Since the expectations the algorithm outputs are those over $S^{\prime}$, Lemma 2.15 implies that the linear combinations that give an approximation to $\mathbf{E}_{X\sim D}[f(X)p(X)]$ have this error, and so the algorithm is correct.

To prove Lemma 2.15, we will need to show a number of intermediate statements. Firstly, we note that the pruning step does not affect this expectation under $D$ much:

We need a bound on this last term, which we obtain as follows:

Finally, we can bound from above the contribution of the set $E$ to the expectation of $p^{2}$ when the algorithm terminates

If $S^{\prime}=S\cup E\setminus L$ is the final set of samples when the algorithm terminates, then for all polynomials $p$ of degree at most $d$ and $\|p\|_{2}=1$, we have $|E|\cdot\mathbf{E}_{X\in_{u}E}[p(X)^{2}]\leq O(\gamma+\delta+\epsilon)\cdot|S^{\prime}|$.

Proposition 2.8 gives that $\left|\mathbf{E}_{X\in_{u}S^{\prime}}[p(X)^{2}]-1\right|\leq O(\gamma+\delta+\epsilon)$, Lemma 2.10 gives that $|L|\cdot\mathbf{E}_{X\in_{u}L}[p(X)^{2}]\leq O(\delta+\epsilon)\cdot|S|$, and Lemma 2.9 gives $\mathbf{E}_{X\in_{u}S}[p(X)^{2}]\geq 1-O(\epsilon+\delta)$. Thus, we have

recalling that $\Delta(S^{\prime},S)\leq 2\epsilon$. ∎

We have the following sequence of inequalities:

where the penultimate line uses Lemmas 2.9, 2.10, and 2.17. ∎

2 Application of Generic Result to Tame Distributions

For the standard $n$-dimensional Gaussian distribution $N(0,I)$ and the uniform distribution $U_{n}$ over $\{\pm 1\}^{n}$, we obtain the following corollary:

Theorem 2.18 follows immediately from Proposition 2.2 via the following standard concentration inequality:

Finally, we note that similar bounds can be obtained for balanced product distributions over the hypercube, i.e., product distributions in which each coordinate is not too-biased towards $-1$ or $1$.

Log-concave Probability Distributions with Approximately Known Moments.

Theorem 2.20 can be deduced from Proposition 2.2 via the following standard concentration inequality (see, e.g., Theorem 7 of [CW01]).

We now provide the details. Note that $N(0,I)$ and $U_{n}$ satisfy Definition 2.1 with $Q_{d}(T)=\exp(-\Omega(T^{2/d}))$ and $\gamma=0$. Indeed, for $D=N(0,I)$ we can calculate $\Sigma=\mathbf{E}_{X\sim D}[m(X)m^{T}(X)]$ exactly.

Similarly, log-concave distributions with known degree at most $2d$ moments satisfy Definition 2.1 with $Q_{d}(T)=\exp(-\Omega(T^{1/d}))$ and $\gamma=0$.

If $Q_{d}(T)=\exp(-\Omega(T^{2/d}))$, we can take $\delta=O(d(d+\ln(1/\epsilon)^{d})\epsilon)$, $T_{\max}=O(nd\ln({n/\epsilon}))^{d/2}$.

If instead $Q_{d}(T)=\exp(-\Omega(T^{1/d}))$, we can take $\delta=O((d+\ln(1/\epsilon)^{2d})\epsilon)$, $T_{\max}=O(nd^{2}\ln^{2}({n/\epsilon}))^{d/2}$.

Next, we obtain the bound on $\delta$ for (i). To get a bound on $\delta$, we will need the following technical claim:

Thus, we can take $\delta=O(d(d+\ln(1/\epsilon)^{d})\epsilon)$.

The case when $Q_{d}(T)=\exp(-\Omega(T^{1/d}))$ is similar. ∎

Robust Learning of Polynomial Threshold Functions under Tame Distributions

In this section, we show the following theorem, which is a detailed version of Theorem 1.2:

To prove our theorem, we need an efficient algorithm that starts with approximations to the low-degree Chow parameters and computes approximations to the coefficients of the polynomial. This can be done by known techniques, as is implicit in prior work [TTV08, DDFS14] (see also [DDS12b]).

For LTFs under the Gaussian distribution, there is a much simpler algorithm to post-process the approximate Chow parameters obtained from Theorem 2.18 that gives a final $L_{1}$-error of $O(\epsilon\sqrt{\log(1/\epsilon)})$. See Corollary 4.5.

We note that the above theorem is not explicitly stated in the above form in previous work, but it follows easily from their proofs.

We have that $f(x)$ and $h(x)$ have Chow distance at most $\sqrt{d}\epsilon\cdot O(d+\log(1/\epsilon))^{d/2}$ or $\epsilon\cdot O(d+\log(1/\epsilon))^{d}$. We need to prove a bound on the $L_{1}$-distance.

For log-concave distributions, including the Gaussian, we will use:

Suppose for a contradiction, that this probability is smaller than $\delta/4$. Then, for any $t$, if $\Pr[|f(x)-g(x)|\geq t]>\delta/4$, then by a union bound with probability at least $\Pr[|f(x)-g(x)|\geq t]-\delta/4$, we have both $|f(x)-g(x)|\geq t$ and $|p(x)|>3\epsilon\|p\|_{2}/\delta$, and so $|f(x)-g(x)||p(x)|\geq 3\epsilon\|p\|_{2}t/\delta$. In summary, for any $t>0$, we have

Rearranging gives $3\epsilon/\delta=\Omega(\delta/d)^{d}$ and $\delta=O(d\epsilon^{1/(d+1)})$, which completes the proof. ∎

Now we note that if a PBF is close then so is the corresponding PTF.

For the uniform distribution on $\{-1,1\}^{n}$, we obtain $L_{1}$-distance $2^{-\Omega(\sqrt{\log(1/\epsilon)})}$ for the case $d=1$ by using a similar argument except using Theorem 7 of [DDFS14] in place of Lemma 3.4.

Optimally Robust Learning of LTFs under the Gaussian Distribution

In this section, we prove the following theorem, a restatement of Theorem 1.3:

In the subsequent discussion, all probabilities and expectations are with respect to the standard $n$-dimensional Gaussian distribution, $N(0,I)$, unless otherwise specified. We use $G(x)$ to denote the pdf of the standard one-dimensional Gaussian distribution.

for some unit vector $v$ and real number $\theta$. We call $v$ the defining vector and we call $\theta$ the threshold.

Next, in order learn our threshold up to a given error, we will need to have a better idea of how much an error in our parameters contributes to an error in our function. We prove the following:

Notice that the derivative of $P$ at is given by

Therefore, $P(\gamma)=2G(\theta)\gamma+o(\gamma)$ as $\gamma\rightarrow 0$, and thus for sufficiently small $\gamma$, $\|f-g\|_{1}=O(\gamma G(\theta))$. This completes our proof. ∎

As our main technique is to learn via the Chow parameters, we will want to know the relationship between our threshold function and its Chow parameters. In particular, we have:

It is clear that $\mathbf{E}[f(G)(w\cdot G)]=0$ for all $w\perp v$. Thus, we only need to evaluate $\mathbf{E}[f(G)(v\cdot G)]$. It is easy to see that this is

Combining this with Lemma 4.2 and Theorem 2.18, we easily obtain the following pair of corollaries:

There is an algorithm that given an $\epsilon$-approximation to the degree-$1$ Chow parameters of an LTF along with an $\epsilon$-approximation of its expectation, yields an $O(\epsilon)$-approximation of the function.

Take $O(1/\epsilon^{2})$ samples to obtain an $\epsilon$-approximation, $m$, of $\mathbf{E}[f]$.

Using Theorem 2.18, compute $u$, an $O(\epsilon\sqrt{\log(1/\epsilon)})$-approximation to the degree-$1$ Chow parameters of $f$.

Although this algorithm only learns to error $O(\epsilon\sqrt{\log(1/\epsilon)})$, it can be improved using boosting. The basic idea will be to refocus our attention towards the samples close to the boundary between the $+1$ and $-1$ regions of our function. A very convenient way to do this restriction is to do rejection sampling in such a way that we end up with another Gaussian centered around the separating hyperplane. For this, we need to define an appropriate method of rejection sampling.

This definition will be useful to us because of the following property:

If elements $x$ taken from the standard Gaussian $N(0,I)$ are fed into the $(v,\theta,\sigma)$-rejection procedure, a point is accepted with probability $\sigma\exp(-\theta^{2}/(2(1-\sigma^{2})))$. Moreover, the distribution on $x$ conditional on acceptance is that of $N(-\theta v,A_{v,\sigma})$, where $A_{v\sigma}=I-(1-\sigma^{2})vv^{T}$ is the matrix with eigenvalue $\sigma^{2}$ in the $v$-direction and eigenvalue $1$ in all orthogonal directions.

First, we note that the distribution of $x$ in directions orthogonal to $v$ is Gaussian distributed and independent on both the $v$-component and the rejection probability. Therefore, it suffices to consider the one-dimensional problem of a Gaussian just along the line parallel to $v$. In this case, the probability that $x=tv$ and is accepted by our rejection procedure is to

Since the latter term is the probability density function of $N(-\theta,\sigma^{2})$, this proves the second statement. This also implies that the integral over $t$ must be $\sigma\exp(-\theta^{2}/(2(1-\sigma^{2})))$, which proves the first statement. ∎

Furthermore, given $\theta,v,\sigma$, and a $\delta$-approximation to the degree-$1$ Chow parameters of $g$, one can obtain an $O(\delta\sigma e^{-\theta^{2}/2})$-approximation to the Chow parameters of $f$.

The last part of this lemma is particularly relevant, as if we can $\delta$-approximate the degree-$1$ Chow parameters of $g$ for $\delta=O(\epsilon e^{-\theta^{2}/2}/\sigma)$ (the error to which we can compute $g$), this allows us to $O(\epsilon)$-approximate our original $f$. Of course, this may still not be possible to do with Corollary 4.5 alone. However, we will only be off by a $\sqrt{\log(1/\delta)}$-factor, rather than a $\sqrt{\log(1/\epsilon)}$ factor. This is particularly useful if we can pick $\sigma$ to be very small.

If all of our samples were exactly coming from $(X,f(X))$, then by Lemma 4.7, the distribution conditional on acceptance would be $(Z,f(Z))$ where $Z$ is distributed as $N(-\theta v,A_{v,\sigma})$. Letting $Z=A_{v,\sigma}^{1/2}Y-\theta v$, we have that $Y$ is distributed as the standard normal, and our distribution is equivalent to $(A_{v,\sigma}^{1/2}Y-\theta v,g(Y))$, where

By Lemma 4.7, the probability of a sample being accepted is at least

Therefore, the variation distance between the conditional distribution and $(A_{v,\sigma}^{1/2}Y-\theta v,g(Y))$ is at most the distance between our original distribution and $(X,f(X))$ divided by our probability of accepting, or $O(\epsilon e^{\theta^{2}/2}/\sigma)$.

For the last statement, note that $\|av+bw/\sigma\|_{2}^{2}\geq{a^{2}+b^{2}}=1$, and $\|av+bw/\sigma\|_{2}^{2}\leq a^{2}+(b/\sigma)^{2}=O(1)$. This means that $\|av+bw/\sigma\|_{2}=\Theta(1)$. Hence, $g$ is an LTF with threshold

Therefore, by Lemma 4.3, the degree-$1$ Chow parameters of $g$ are a constant multiple of $av+bw/\sigma$. Thus, if $u$ is a $\delta$-approximation of the degree-$1$ Chow parameters, we have that $\|u/\|u\|_{2}-(av+bw/\sigma)/\|(av+bw/\sigma)\|_{2}\|_{2}=O(\delta)$. Taking the component perpendicular to $v$, we find that

Noting that $C$ is bounded away from $1$, this allows us to compute $b$ to error $O(\sigma\delta)$. We can then compute $a$ to error $O(\sigma\delta)^{2}$ as $a=\sqrt{1-b^{2}}$.

Considering the part of $\frac{u\sqrt{a^{2}+(b/\sigma)^{2}}}{|u|_{2}}$ orthogonal to $v$, we obtain an $O(\delta)$-approximation of $bw/\sigma$. This gives us an $O(\delta\sigma)$-approximation of $bw$, and combined with an $O(\delta\sigma)$-approximation to $a$, we can obtain an $O(\delta\sigma)$-approximation to $av+bw$, the defining vector for $f$. By Lemma 4.3, this is sufficient to obtain an $O(\delta\sigma e^{-\theta^{2}/2})$-approximation to the degree-$1$ Chow parameters $f$. This completes our proof. ∎

This allows us to iteratively improve our approximations to the Chow parameters of an LTF.

Let $f$ be an LTF with threshold $\theta$. Suppose that we are given $\theta$, a $\delta$-approximation to the degree-$1$ Chow parameters of $f$, and sample access to an $\epsilon$-corrupted version of $(G,f(G))$. Then, if $\epsilon\ll\delta\ll 1$ and $\delta\theta e^{\theta^{2}/2}=O(1)$, there is an algorithm that takes polynomial time and samples, and returns an $O(\epsilon\sqrt{\log(\delta/\epsilon)}$-approximation to the degree-$1$ Chow parameters of $f$.

Let $\sigma=\delta e^{\theta^{2}/2}$ and $v$ be the normalization of our approximation of the degree-$1$ Chow parameters of $f$. We note that $\theta\sigma=O(1)$. We also note that if $f$ is defined by the unit vector $v^{\prime}$, then the degree-$1$ Chow parameters of $f$ are $2G(\theta)v^{\prime}$, which is within $O(\sigma G(\theta))$ of $2G(\theta)v$. Therefore, $\|v-v^{\prime}\|_{2}\leq O(\sigma).$ This means that $v^{\prime}=av+bw$ for some $w\perp v$ and $a^{2}+b^{2}=1$ with $b=O(\sigma)$. Now taking our samples from $(X,f(X))$ and $(v,\theta,\sigma)$-rejection sampling based on the first coordinate, by Lemma 4.8 we obtain $O(\epsilon e^{\theta^{2}/2}/\sigma)=O(\epsilon/\delta)$-noisy samples to $(A_{v\sigma}^{1/2}Y-\theta v,g(Y))$. Inverting the linear transformation in the first coordinate and applying the algorithm from Theorem 2.18, we obtain an $O(\epsilon/\delta\sqrt{\log(\epsilon/\delta)})$-approximation to the degree-$1$ Chow parameters of $g$. Applying Lemma 4.8 again, this gives us an $O(\epsilon/\delta\sqrt{\log(\epsilon/\delta)}e^{\theta^{2}/2}/\sigma)$-approximation to the degree-$1$ Chow parameters of $g$. But this is simply an $O(\epsilon\sqrt{\log(\delta/\epsilon)})$-approximation, as desired. ∎

Iterating this result, we immediately obtain the following corollary:

Let $f$ be an LTF with threshold $\theta$ such that $\theta e^{\theta^{2}/2}=O(\epsilon^{-1}/\sqrt{\log(1/\epsilon)})$. Then there is an algorithm that given $\theta$ and sample access to an $\epsilon$-corrupted version of $(G,f(G))$, takes polynomial time and samples and returns and $O(\epsilon)$-approximation to the degree-$1$ Chow parameters of $f$.

Using Theorem 2.18, we obtain a $\delta_{0}=O(\epsilon\sqrt{\log(1/\epsilon)})$-approximation to the degree-$1$ Chow parameters of $f$.

Let $i\leftarrow i+1$, and use Lemma 4.9 to obtain a $\delta_{i}=C(\epsilon\sqrt{\log(\delta_{i-1}/\epsilon)})$-approximation to the degree-$1$ Chow parameters of $f$, for some sufficiently large $C$.

If $\delta_{i}<\delta_{i-1}/2$, return to Step 3.

To prove correctness, note that $\delta_{i}>\epsilon$ for all $i$, and therefore $\delta_{i}\theta e^{\theta^{2}/2}=O(1)$ for all $i$, so the hypotheses of Lemma 4.9 are always satisfied in Step 3. Next note that $\delta_{i}/\epsilon=C\sqrt{\log(\delta_{i}/\epsilon)}$, so the $\delta_{i}$ are decreasing and always shrinking by a factor of at least $2$, unless $\delta_{i-1}=O(\epsilon)$. Therefore, we reach Step 5 in at most $\log(\delta_{0}/\epsilon)$ iterations, and when we do $\delta_{i}=O(\epsilon)$. This completes the proof. ∎

Unfortunately, this algorithm only works when $\theta e^{\theta^{2}/2}=O(\epsilon^{-1}/\sqrt{\log(1/\epsilon)})$, while we would need to deal with $\theta e^{\theta^{2}/2}$ as large as $\epsilon^{-1}$ to make our algorithm work in general. This is for somewhat technical reasons. Essentially, if we have very extreme thresholds, our rejection sampling procedure will fail. This happens because the Gaussian we need after restriction is too wide. This will mean that we need a reasonable chance of selecting points even further than $\theta$ from the origin in the $v$-direction, and this will in turn force our acceptance probability to be too small. To correct this issue, we will want to restrict to an even narrower Gaussian. Of course, this will make our acceptance probability even smaller, and thus the fraction of accepted points that are in error will become much larger. However, we will also allow ourselves to vary the exact threshold at which we perform our cutoff, this will mean that on average the fraction of accepted points that are in error will not be too big.

We can use these ideas to prove an improved version of Lemma 4.9 that gets around the $\theta e^{\theta^{2}/2}=O(\epsilon^{-1})$ condition, in exchange for producing a poly-logarithmic number of outputs.

Let $v=u/\|u\|_{2}.$ We note that $v$ is a $\delta/G(\theta)$-approximation to the defining vector of $f$. We can write this defining vector uniquely as $av+bw$ for non-negative real numbers $a,b$ with $a^{2}+b^{2}=1$, and a vector $w\perp v$. We note that $b=O(\delta/G(\theta))=O(\delta/(C\epsilon\sqrt{\log(1/\epsilon)}))=O(1/C)$. Thus, we may assume that $b$ is less than a sufficiently small constant. However, rounding $b$ to the nearest multiple of $1/\log(1/\epsilon)$ introduces a variation distance error of at most $\epsilon$, and an $O(\epsilon)$ error in the degree-$1$ Chow parameters. Therefore, up to introducing another $O(\epsilon)$ error in our sampling, we may assume that $b$ is a multiple of $1/\log(1/\epsilon)$. Guessing the value of $b$, we note that we are correct with probability $1/\log(1/\epsilon)$. The remainder of this algorithm is conditional on this correctness. Thus, henceforth, we will assume that the algorithm knows the value of $b$, and hence also knows the value of $a$.

Next, pick a random threshold $s\in[a\theta,a\theta+b]$. This will be the threshold that we will try to restrict to.

We will then apply the $(v,s,\sigma)$-rejection procedure with $\sigma=1/\theta$ to samples from our noisy version of $(G,f(G))$ rejecting based on the first coordinate. If there were no errors, our acceptance probability would be $\sigma e^{-s^{2}/(2(1-\sigma^{2}))}=\Omega(\sigma e^{-s^{2}/2}).$ However, it will be important to know that it is impossible to have our errors be too likely to be accepted by this procedure. Now it is possible that, for certain values of $s$, we will accept too many errors. However, we wish to show that on average it is not too many. In particular, for a point $x$ we consider $\mathbf{E}_{s}[\Pr(x\textrm{ is accepted})].$ In particular,

This means that, for most $s$, the sum of the fraction of samples that are either bad and accepted or would have been accepted if they were not corrupted is $O(\epsilon\sigma/b)$. For such $s$, the fraction of accepted samples that come from corrupted samples is at most $O(\epsilon e^{s^{2}/2}/b)$. We assume in the following that the algorithm found such an $s$.

We will now need to mimic the latter half of Lemma 4.7. In particular, were there no corruptions, the accepted samples would be from the distribution $(Z,f(Z))$ with $Z\sim N(-sv,A_{v,\sigma})$, though as it stands we have instead an $\eta:=O(\epsilon e^{s^{2}/2}/b)$-noisy version of this. Letting $Z=A_{v,\sigma}^{1/2}Y-sv$, we find that $Y$ is distributed as a standard Gaussian and our distribution is close to $(A_{v,\sigma}^{1/2}Y-sv,g(Y))$, where $g$ is the LTF

which has absolute value at most $(\theta-as)/b$.

Now employing Theorem 2.18, we can learn the degree-$1$ Chow parameters of $g$ to error $O(\epsilon e^{s^{2}/2}/b\sqrt{\log(1/\epsilon)})$. By Lemma 4.3, this allows us to learn the defining vector of $g$ to error