Testably Learning Polynomial Threshold Functions

Authors: lucas  slot
stefan  tiegel
manuel  wiedmer
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 16:21:43

Abstract: Rubinfeld \& Vasilyan recently introduced the framework of *testable learning* as an extension of the classical agnostic model. It relaxes distributional assumptions which are difficult to verify by conditions that can be checked efficiently by a *tester*. The tester has to accept whenever the data truly satisfies the original assumptions, and the learner has to succeed whenever the tester accepts. We focus on the setting where the tester has to accept standard Gaussian data. There, it is known that basic concept classes such as halfspaces can be learned testably with the same time complexity as in the (distribution-specific) agnostic model. In this work, we ask whether there is a price to pay for testably learning more complex concept classes. In particular, we consider polynomial threshold functions (PTFs), which naturally generalize halfspaces. We show that PTFs of arbitrary constant degree can be testably learned up to excess error $\varepsilon > 0$ in time $n^{\mathrm{poly}(1/\varepsilon)}$. This qualitatively matches the best known guarantees in the agnostic model. Our results build on a connection between testable learning and *fooling*. In particular, we show that distributions that approximately match at least $\mathrm{poly}(1/\varepsilon)$ moments of the standard Gaussian fool constant-degree PTFs (up to error $\varepsilon$). As a secondary result, we prove that a direct approach to show testable learning (without fooling), which was successfully used for halfspaces, cannot work for PTFs.

Main paper: 
 introduction: 
 The PAC learning model of Valiant [30] has long served as a test-bed to study which learning tasks can be performed efficiently and which might be computationally difficult. One drawback of this model is that it is inherently noiseless. In order to capture noisy learning tasks, the following extension, called the agnostic model, has been introduced [19, 24] : Let F be a class of boolean functions and let D joint be an (unknown) distribution over example-label-pairs in X × {±1}. Typically, X = {0, 1} n or R n . As input, we receive iid samples from D joint . For a small ε > 0, our task is to output a classifier f (not necessarily in F) whose loss L( f , D joint ) := P (x,z)∼Djoint ( f (x) ̸ = z) is at most opt + ε, where opt := inf f ∈F L(f, D joint ). The parameter opt thus indicates how "noisy" the instance is. We say that an algorithm agnostically learns F up to error ε if it outputs such an f . This model is appealing since it makes assumptions neither on the distribution of the input, nor on the type and amount of noise. After running an agnostic learning algorithm, we can therefore be certain that the output f achieves error close to that of the best function in F even without knowing what distribution the data came from.Efficient learning and distributional assumptions. We are interested in understanding when agnostic learning can be performed efficiently. Unfortunately, efficient learning is likely impossible without making assumptions on the distribution D joint , even for very simple function classes F. For instance, consider the class F HS of halfspaces, i.e., boolean functions of the form f (x) = sign(⟨v, x⟩ -θ). Then, even if there exists a halfspace achieving arbitrarily small error, it is widely believed that outputting an f that performs better than a random guess in the agnostic model takes at least super-polynomial time if no assumptions are made on D joint [8, 29] . To find efficient algorithms, one therefore has to make such assumptions. Typically, these take the form of assuming that the marginal D X of D joint over the examples X belongs to a specific family of distributions. Definition 1 (Agnostic learning with distributional assumptions). Let ε > 0. A learner A agnostically learns F with respect to D up to error ε if, for any distribution D joint on X × {±1} whose marginal D X on X is equal to D, given sufficient samples from D joint , it outputs with high probability a function f : X → {±1} satisfying L(f, D joint ) ≤ opt(F, D joint ) + ε.For example, under the assumption that D X is standard Gaussian, we can find f such that L( f , D joint ) ≤ opt(F HS , D joint ) + ε in time n O(1/ε 2 ) [20, 11] . This runtime is likely bestpossible [12, 29, 13] . 1 Efficient learning is still possible under weaker assumptions on D X , e.g., log-concavity [20] . Regardless, we cannot know whether a learning algorithm achieves its claimed error without a guarantee that the input actually satisfies our distributional assumptions. Such guarantees are inherently difficult to obtain from a finite (small) sample. Furthermore, approaches like cross-validation (i.e., computing the empirical error of f on a hold-out data set) fail in the noisy agnostic model, since we do not know the noise level opt. This represents a severe limitation of the agnostic learning model with distributional assumptions.To address this limitation, Rubinfeld & Vasilyan [28] recently introduced the following model, which they call testable learning: First, they run a tester on the input data, which attempts to verify a computationally tractable relaxation of the distributional assumptions. If the tester accepts, they then run a (standard) agnostic learning algorithm. The tester is required to accept whenever the data truly satisfies the distributional assumptions, and whenever the tester accepts, the output of the algorithm must achieve error close to opt. More formally, they define: Definition 2 (Testable learning [28] ). Let ε > 0. A tester-learner pair (T , A) testably learns F with respect to a distribution D on X up to error ε if, for any distribution D joint on X × {±1}, the following hold 1. (Soundness). If samples drawn from D joint are accepted by the tester T with high probability, then the learner A must agnostically learn F w.r.t. D joint up to error ε.In this work, we continue to explore testable learning and its relation to the agnostic model. We consider the concept class of polynomial threshold functions (short PTFs). A degree-d PTF is a function of the form f (x) = sign(p(x)), where p is a polynomial of degree at most d. PTFs naturally generalize halfspaces, which correspond to the case d = 1. They form an expressive function class with applications throughout (theoretical) computer science, and have been studied in the context of circuit complexity [5, 26, 27, 3] , and learning [18, 14] . Despite their expressiveness, PTFs can be agnostically learned in time n O(d 2 /ε 4 ) [22] , which is polynomial in n for any fixed degree d ∈ N and error ε > 0. They are thus significantly easier to learn in the agnostic model than convex sets. Our main result is that PTFs can be learned efficiently in the testable model as well. Theorem 3 (Informal version of Theorem 19) . Fix d ∈ N. Then, for any ε > 0, the concept class of degree-d polynomial threshold functions can be testably learned up to error ε w.r.t. the standard Gaussian in time and sample complexity n poly(1/ε) .Theorem 3 is the first result achieving efficient testable learning for PTFs of any fixed degree d (up to constant error ε > 0). Previously, such a result was not even available for learning degree-2 PTFs with respect to the Gaussian distribution. It also sheds new light on the relation between agnostic and testable learning: there is no qualitative computational gap between the two models for the concept class of PTFs, whose complexity lies between that of halfspaces and convex sets in the agnostic model.In addition to Theorem 3, we also show an impossibility result ruling out a certain natural approach to prove testable learning guarantees for PTFs. In particular, we show in Section 2.4 that an approach which has been successful for testably learning halfspaces in [28] provably cannot work for PTFs.Limitations. The dependence of the running time on the degree parameter d and the error ε is (much) worse than in the agnostic model (see Theorem 19) . Moreover, we do not have access to lower bounds on the complexity of testably learning PTFs which might indicate whether these dependencies are inherent to the problem, or an artifact of our analysis. The only lower bounds available apply already in the agnostic model, and show that the time complexity of agnostically (and thus also testably) learning degree-d PTFs is at least n Ω(d 2 /ε 2 ) in the SQ-model [12] , and at least n Ω(d 2-β /ε 2-β ) for any β > 0 under a cryptographic hardness assumption [29] .The two works most closely related to this paper are [28, 15] . Both rely on the following highlevel strategy. A standard result [20] shows that one can agnostically learn a concept class F w.r.t. a distribution D in time n O(k) if all elements of F are well-approximated w.r.t. D by degree-k polynomials. That is, if for all f ∈ F, there exists a degree-k polynomial h such that E X∼D [|h(X) -f (X)|] ≤ ε. This result can be extended to the testable setting, but now one needs a good low-degree L 1 -approximation w.r.t. any distribution D ′ accepted by the tester. Using the moment-matching tester outlined above, one thus needs to exhibit low-degree approximations to all functions in F w.r.t. any distribution which approximately matches the first few moments of D.A direct approach. In [28] , the authors use a direct approach to show that if F = F HS is the class of halfspaces and D = N (0, I n ), these approximators exist for k = O(1/ε 4 ), leading to an overall running time of n O(1/ε 4 ) for their testable learner. Their approach consists of two steps. First, they construct a low-degree approximation q ≈ sign of the sign function in one dimension using standard techniques. Then, for any halfspace f (x) = sign(⟨v, x⟩ -θ), they set h(x) = q(⟨v, x⟩ -θ). By exploiting concentration and anti-concentration properties of the push-forward under linear functions of distributions that match the moments of a Gaussian, they show that h is a good approximation of f . Unfortunately, this kind of approach cannot work for PTFs: We formally rule it out in Theorem 16. This is the aforementioned secondary contribution of our paper, which extends earlier impossibility results for (agnostic) learning of Bun & Steinke [6] . See Section 2.4 for details.An indirect approach using fooling. In order to prove our main theorem we thus need a different approach. Gollakota, Klivans & Kothari [15] establish a connection between testable learning and the notion of fooling, which has played an important role in the study of pseudorandomness [4, 2, 9] . Its connection to learning theory had previously been observed in [23] . We say a distribution D ′ fools a concept class F up to error ε > 0 with respect to D if, for all f ∈ F, it holds that|E X∼D [f (X)] -E X∼D ′ [f (X)]| ≤ ε.Roughly speaking, the work [15] shows that, if any distribution D ′ which approximately matches the moments of D up to degree k fools F with respect to D, then F can be testably learned in time n O(k) (see Theorem 9 below). We remark that (approximately) moment-matching distributions have not been considered much in the existing literature on fooling. Rather, it has focused on distributions D ′ whose marginals on any subset of k variables are equal to those of D, which is a stronger condition a priori. While it coincides with moment-matching in special cases (e.g., when D is the uniform distribution over the hypercube), it does not when D = N (0, I n ). Nevertheless, the authors of [15] show that (approximate) moment matching up to degree k = Õ(1/ε 2 ) fools halfspaces with respect to N (0, I n ), allowing them to obtain the aforementioned result for testably learning F HS . In fact, they show that this continues to hold when F consists of arbitrary boolean functions applied to a constant number of halfspaces. They also use existing results in the fooling literature to show that degree-2 PTFs can be testably learned under the uniform distribution over {0, 1} n (but these do not extend to learning over R n w.r.t. a standard Gaussian).Other previous work on testable learning. In weaker error models than the agnostic model or under less stringent requirements on the error of the learner it is known how to construct tester-learner pairs with runtime poly(n, 1/ε) [16, 10] . These results have been extended to allow for the following stronger completeness condition: The tester has to accept, whenever D joint is an isotropic strongly log-concave distribution [17] . 
(completeness).: 
 If the marginal of D joint on X is equal to D, then the tester must accept samples drawn from D joint with high probability.Soundness tells us that whenever a testable learning algorithm outputs a function f , this function achieves low error (regardless of whether D joint satisfies any distributional assumption). On the other hand, completeness tells us testable learners are no weaker than (distribution-specific) agnostic ones, in the sense that they achieve the same error whenever D joint actually satisfies our assumptions (i.e., whenever this error can in fact be guaranteed for the agnostic learner). The testable model is thus substantially stronger than the agnostic model with distributional assumptions.Which function classes can be learned testably? A natural question is whether testable learning comes at an additional computational cost compared to (distribution-specific) agnostic learning. We focus on the setting where D is the standard Gaussian on X = R n . Following [28, 15] , we consider the following simple tester: Accept if and only if the empirical moments up to degree k of the input distribution (approximately) match those of D. This tester satisfies completeness as the empirical moments of a Gaussian concentrate well. Using this tester, Rubinfeld & Vasilyan [28] show that halfspaces can be testably learned in time n Õ(1/ε 4 ) . Their runtime guarantee was improved to n Õ(1/ε 2 ) in [15] , (nearly) matching the best known non-testable algorithm. This shows that there is no separation between the two models for halfspaces. On the other hand, a separation does exist for more complex function classes. Namely, for fixed accuracy ε > 0, testably learning the class of indicator functions of convex sets requires at least 2 Ω(n) samples (and hence also time) [28] , whereas agnostically learning them only takes subexponential time 2 O( √ n) , see [25] . The relation between agnostic and testable learning is thus non-trivial, depending strongly on the concept class considered.From here, we restrict to the setting X = R n . We let D be a well-behaved distribution on R n ; usually D = N (0, I n ) is the standard Gaussian. For x ∈ R n and a multi-index α ∈ N n , we writex α := n i=1 x αi i . For k ∈ N, we write N n k := {α ∈ N n , n i=1 α i ≤ k}.We say a statement holds 'with high probability' if it holds with probability ≥ 0.99. The notation O d (resp. Ω d , Θ d ) hides factors that only depend on d. We now define the moment-matching tester introduced above. Definition 4 (Moment matching). Let k ∈ N and η ≥ 0. We say a distribution D ′ on R n approximately moment-matches D up to degree k and with slack η if|E X∼D [X α ] -E X∼D ′ [X α ]| ≤ η ∀ α ∈ N n k . Definition 5. Let k ∈ N and η ≥ 0. The approximate moment-matching tester T AMM = T AMM (k, η)for a distribution D accepts the samples (x (1) , z (1) ), . . . , (x (m) , z (m) ) ∈ R n × {±1} if, and only if,E X∼D [X α ] - 1 m m i=1 x (i) α ≤ η ∀ α ∈ N n k .That is, T AMM (k, η) accepts if and only if the moments of the empirical distribution belonging to the samples {x (i) } match the moments of D up to degree k and slack η. Note that T AMM (k, η) requires time at most O(m • n k ) to decide whether to accept a set of m samples.The tester T AMM does not take the labels of the samples into account. In general, for testers T which depend only on the marginal D of D joint on R n , we say that T accepts a distribution D ′ on R n if it accepts samples drawn from D ′ with high probability (regardless of the labels).In this section, we review in more detail the existing techniques to establish guarantees for agnostic and testable learning discussed in Section 1.3. Our goals are twofold. First, we wish to highlight the technical difficulties that arise from proving error guarantees in the testable model versus the agnostic model. Second, we want to introduce the necessary prerequisites for our proof of Theorem 3 in Section 2.3, namely testable learning via fooling (see Theorem 9) .Learning and polynomial approximation. A standard result [20] shows that one can agnostically learn any concept class that is well-approximated by low-degree polynomials in the following sense. Theorem 6 ( [20] ). Let k ∈ N and ε > 0. Suppose that, for any f ∈ F, there exists a polynomial h of degree k such thatE X∼D [|h(X) -f (X)|] ≤ ε.Then, F can be agnostically learned up to error ε in time and sample complexity n O(k) /poly(ε).The underlying algorithm in the theorem above is polynomial regression w.r.t. the absolute loss function. In the testable setting, a similar result holds. The key difference is that one now needs good approximation w.r.t. all distributions accepted by the proposed tester. Theorem 7. Let k ∈ N and ε > 0. Let T be a tester which accepts D and which requires time and sample complexity τ . Suppose that, for any f ∈ F, and for any D ′ accepted by T , there exists a polynomial h of degree k such thatE X∼D ′ [|h(X) -f (X)|] ≤ ε.Then, F can be testably learned up to error ε in time and sample complexity τ + n O(k) /poly(ε).The takeaway is that, in order to devise efficient algorithms for agnostic or testable learning, it suffices to study low-degree polynomial approximations of elements of F. Under the assumption that D is a (standard) Gaussian, one has access to powerful techniques from Fourier analysis to show existence of good polynomial approximators w.r.t. D for various concept classes. Using Theorem 6, this leads to efficient agnostic learning algorithms for a variety of concept classes w.r.t. N (0, I n ) [20, 25, 22] .Testable learning via direct approximation. In the testable setting, it is not sufficient to approximate with respect to D alone, and so one cannot rely directly on any of its special structure. In [28] , the authors overcome this obstacle to get testable learning guarantees for halfspaces w.r.t. D = N (0, I n ) by appealing to more basic properties of the distributions D ′ accepted by their tester. Their approach is roughly as follows. First, they use standard results from polynomial approximation theory to find a (univariate) polynomial q which approximates the sign-function well on the interval [-1, 1]. For a halfspace f (x) = sign(⟨v, x⟩ -θ), they consider the approximator h(x) = q(⟨v, x⟩ -θ), which satisfiesE X∼D ′ [|h(X) -f (X)|] = E Y ∼D ′ v,θ [|q(Y ) -sign(Y )|] . Here, D ′ v,θ is the (shifted) projection of D ′ onto the line span(v) ⊆ R n . That is, Y = ⟨v, X⟩ -θ.Then, for carefully chosen k ∈ N and η > 0, they show that for any D ′ accepted by T AMM (k, η), the distribution D ′ v,θ satisfies certain concentration and anti-concentration properties, meaning essen-tially that D ′ v,θ is distributed somewhat uniformly on [-1, 1]. As q approximates the sign-function on [-1, 1], they may conclude that E Y ∼D ′ v,θ [|q(Y ) -sign(Y )|]is small, and invoke Theorem 7.Testable learning via fooling. It is natural to attempt a generalization of the approach above to PTFs. Indeed, for f (x) = sign(p(x)), one could consider the approximator h(x) = q(p(x)).However, as we show below in Section 2.4, this approach cannot work when deg(p) ≥ 6. Instead, we will rely on a more indirect technique, proposed in [15] . It connects the well-studied notion of fooling to low-degree polynomial approximation, and to testable learning. Definition 8 (Fooling). Let ε > 0. We say a distribution D ′ on R n fools F w.r.t. D up to error ε, if, for all f ∈ F, we have|E Y ∼D [f (Y )] -E X∼D ′ [f (X)]| ≤ ε.The main result of [15] shows that fooling implies testable learning when using approximate momentmatching to test the distributional assumptions. It forms the basis of our proof of Theorem 3.Theorem 9 ([15, Theorem 4.5]). Let k, m ∈ N and ε, η > 0. Suppose that the following hold:1. Any distribution D ′ whose moments up to degree k match those of D with slack η fools F w.r.t. D up to error ε/2.2. With high probability over m samples from D the empirical distribution matches moments of degree at most k with D up to slack η.Then, using the moment-matching tester T = T AMM (k, η), we can learn F testably with respect to D up to error ε in time and sample complexity m + n O(k) . Remark 10. When D = N (0, I n ) is the standard Gaussian, then the second condition in Theorem 9 is satisfied for m = Θ (2kn) k • η -2 , see also Fact 36.The primary technical argument in the proof of Theorem 9 in [15] is an equivalence between fooling and a type of low-degree polynomial approximation called sandwiching. Compared to Theorem 7, the advantage of sandwiching is that one needs to approximate f only w.r.t. D (rather than any distribution accepted by the tester). However, one needs to find not one, but two low degree approximators h 1 , h 2 that satisfy h 1 ≤ f ≤ h 2 pointwise (i.e., 'sandwich' f ). We refer to [15] for details.Fooling PTFs. In light of Theorem 9 and Remark 10, in order to prove our main result Theorem 3, it suffices to show that distributions D ′ which approximately match the moments of N (0, I n ) fool the concept class of PTFs. This is our primary technical contribution (see Proposition 12 below). It can be viewed as a generalization of the following result due to Kane [21] .Theorem 11 (Informal version of [21, Theorem 1] ). Let D ′ be a k-independent standard Gaussian, meaning the restriction of D ′ to any subset of k variables has distribution N (0, I k ). Then, D ′ fools degree-d PTFs w.r.t. N (0, I n ) up to error ε > 0 as long as k = k(d, ε) is large enough.Theorem 11 applies to a class of distributions that is (far) more restrictive than what we need. First, note that k-independent Gaussians match the moments of N (0, I n ) up to degree k exactly, whereas we must allow D ′ whose moments match only approximately. Second, even if D ′ would match the moments of a Gaussian exactly up to degree k, its k-dimensional marginals need not be Gaussian. In fact, we have no information on its moments of high degree even if they depend on at most k variables. These two distinctions cause substantial technical difficulties in our proof of Proposition 12 below.As we have seen, in order to prove Theorem 3, it suffices to show that approximately momentmatching distributions fool PTFs. We obtain the following. Proposition 12. Let ε > 0. Suppose that D ′ approximately matches the moments of N (0, I n ) up to degree k and slack η, k) . Then, D ′ fools the class of degree-d PTFs w.r.t. N (0, I n ) up to error ε/2. That is, for any f ∈ F PTF,d , we then havewhere k ≥ Ω d ε -4d•7 d , and η ≤ n -Ω d (k) k -Ω d (EQUATIONIn the rest of this section, we outline how to obtain Proposition 12. Full details can be found in Appendix A. Structurally, our proof is similar to the proof of Theorem 11 in [21] : First, in Section 2.3.1, we show fooling for the subclass of PTFs defined by multilinear polynomials. Then, in Section 2.3.2, we extend this result to general PTFs by relating arbitrary polynomials to multilinear polynomials in a larger number of variables. Our primary contribution is thus to show that the construction of [21] (which considers k-independent Gaussians) remains valid for the larger class of distributions that approximately match the moments of a Gaussian.Let f (x) = sign(p(x)), where p is a multilinear polynomial. Our goal is to establish (1) for f under the assumptions of Proposition 12. We will follow the proof of Kane [21] for Theorem 11, which proceeds as follows. Let D ′ be a k-independent Gaussian. First, Kane constructs a degree-k polynomial approximation h of f , satisfyingEQUATIONEQUATIONSince the moments of D ′ are exactly equal to those of N (0, I n ) up to degree k, we haveE Y ∼N (0,In) [h(Y )] = E X∼D ′ [h(X)].We may then conclude the fooling property for D ′ (cf. (1) ):E Y ∼N (0,In) [f (Y )] ≈ E Y ∼N (0,In) [h(Y )] = E X∼D ′ [h(X)] ≈ E X∼D ′ [f (X)] . As we see below, Kane relies on a structure theorem (see Lemma 21) for multilinear polynomials to construct his low-degree approximation h. We wish to extend this proof to our setting, where D ′ merely matches the moments of the standard Gaussian up to degree k and slack η. As we will see, the construction of the polynomial h remains valid (although some care is required in bounding the approximation error). A more serious concern is that, for us,E Y ∼N (0,In) [h(Y )] ̸ = E X∼D ′ [h(X)]in general. Our main technical contribution in this section is dealing with the additional error terms that arise from this fact.Constructing a low-degree approximation. We now give details on the construction of the lowdegree approximation h that we use in our proof, which is the same as in [21] . The starting point of the construction is a structure theorem for multilinear polynomials p (see Lemma 21 below) . It tells us that f = sign(p) can be decomposed as f (x) = F (P (x)), where F is again a PTF, and P = (P i ) is a vector of multilinear polynomials of degree P i (Y ) ℓ ≤ O d ( √ ℓ) dℓ ).As in [21] , we approximate F by a smooth function F via mollification (see Appendix A.1.1). That is, F is the convolution F * ρ of F with a carefully chosen smooth function ρ. Then, we set h(x) = T (P (x)), where T is the Taylor approximation of F of appropriate degree (see Appendix A.1.2). Intuitively, taking the Taylor expansion yields a good approximation as the (Gaussian) moments of the P i are not too large, yielding (2), (3) .Error analysis of the approximation. Our goal is now to establish (2), (3) in our setting. Note that, since (2) is only concerned with the Gaussian distribution, there is no difference with [21] . For (3), we have to generalize the proof in [21] . For this, we first bound the probability under D ′ that (at least) one of the P i is large, which we do using Markov's inequality. Then, we need to show a bound on the moments of P i under D ′ (recall that the structure theorem only gives a bound on the Gaussian moments). Using bounds on the coefficients of the P i , we are able to do this under a mild condition on η (see Appendices A.1.2 and A.1.3).Controlling the additional error terms. To conclude the argument, we need to show that, for our low-degree approximation h, we haveE Y ∼N (0,In) [h(Y )] ≈ E X∼D ′ [h(X)].Recall that in [21] , these expectations were simply equal. The main issue lies in the fact that, in our setting, the moment matching is only approximate; equality would still hold if D ′ matched the moments of N (0, I n ) up to degree k exactly. Under η-approximate moment matching, we could say thatEQUATIONwhere ∥h∥ 1 is the 1-norm of the coefficients of h. However, there is no way to control this norm directly. Instead, we rely on the fact that h = T • P and argue as follows. On the one hand, we show a bound on the coefficients in the Taylor approximation T of F . On the other hand, we show bounds on all terms of the formE Y ∼N (0,In) [P (Y ) α ] -E X∼D ′ [P (X) α ] . Combining these bounds yields an estimate on the difference E Y ∼N (0,In) [h(Y )] -E X∼D ′ [h(X)], which lets us conclude (1) .Going into more detail, the LHS of ( 4) is equal to the inner product |⟨t, u⟩| between the vector t = (t α ) of coefficients of T and the vector u = (u α ), whereu α = E Y ∼N (0,In) [P (Y ) α ] -E X∼D ′ [P (X) α ].This can be viewed as a 'change of basis' x → P (x). Then, (4) can bounded by ∥u∥ ∞ • ∥t∥ 1 , where ∥u∥ ∞ = max α |u α |. The coefficients t α of T are related directly to the partial derivatives of F , which in turn depend on the function ρ used in the mollification. After careful inspection of this function, we can bound ∥t∥ 1 ≤ k O d (k) (see Lemma 27) . Finally, for any |α| ≤ k, it holds thatE Y ∼N (0,In) [P (Y ) α ] -E X∼D ′ [P (X) α ] ≤ η • sup i ∥P i ∥ 1 |α| ≤ η • n |α|•d 2 ≤ η • n O d (k) , see Fact 22.Putting things together, we get that k) and k ≫ 1/ε for the last inequality.E Y ∼N (0,In) [h(Y )] -E X∼D ′ [h(X)] ≤ ∥u∥ ∞ • ∥t∥ 1 ≤ η • k O d (k) n O d (k) ≪ ε/2, using the fact that η ≤ n -Ω d (k) k -Ω d (Now, let f (x) = sign(p(x)) be an arbitrary PTF. As before, we want to establish (1) . Following [21] , the idea is to reduce this problem to the multilinear case as follows. Let Y ∼ N (0, I n ) and let X be a random variable that matches the moments of Y up to degree k and with slack η. For N ∈ N to be chosen later, we construct new random variables X and Ŷ , and a multilinear PTF f = sign(p), all in n • N variables, such that Ŷ ∼ N (0, I nN ), X matches moments of Ŷ up to degree k with slack η, and|E Y [f (Y )] -E X [f (X)]| ≈ E Ŷ [ f ( Ŷ )] -E X [ f ( X)] .(5) Assuming η is not much bigger than η, and the approximation above is sufficiently good, we may then apply the result of Section 2.3.1 to f to conclude (1) for f . Our construction of X, Ŷ and f will be the same as in [21] . However, with respect to his proof, we face two difficulties. First, we need to control the slack parameter η in terms η. More seriously, Kane's proof of ( 5) breaks in our setting: He relies on the fact that X is k-independent Gaussian in his setting to bound high degree moments of X which depend on at most k variables. In our setting, we have no information on such moments at all (even if X matched the moments of N (0, I n ) up to degree k exactly).Construction of X and Ŷ . For i ∈ [n], let Z (i) be an N -dimensional Gaussian random variable with mean 0, variances 1 -1/N and covariances -1/N , independent from X and all other Z (i ′ ) . We define Xij := X i / √ N + Z (i)j , and set X = ( Xij ). We define Ŷ analogously. This ensures that Ŷ ∼ N (0, I nN ). Furthermore, given that X matches the moments of Y with slack η, it turns out that X matches the moments of Ŷ with slack η = (2k) k/2 • η. This follows by direct computation after expanding the moments of X in terms of those of X and of the Z (i) , see Lemma 32.Construction of the multilinear PTF. We want to construct a multilinear polynomial p in nN variables so that p(X) ≈ p( X).For x ∈ R nN , write φ(x) := ( N j=1 xij / √ N ) i∈[n] ∈ R n . Since φ(Z (i) ) = 0 holds deterministically, φ( X) = X.So, if we were to set p = p • φ, it would satisfy p( X) = p(X). However, it would clearly not be multilinear. To fix this, we write p(φ(x)) = α λ α xα and replace each non-multilinear term λ α xα by a multilinear one as follows: If the largest entry of α is at least three, we remove the term completely. If the largest entry of α is two, we replace the term by λ α xα ′ , where α ′ ij = 1 if α ij = 1 and 0 otherwise. This is identical to the construction in [21] . Now, to show that p(X) ≈ p( X) we need to bound the effect of these modifications. It turns out that it suffices to control the following expressions in terms of N :a i := N j=1 Xi,j √ N , b i := N j=1 Xi,j √ N 2 -1 , c i,ℓ := N j=1 Xi,j √ N ℓ (i ∈ [n], 3 ≤ ℓ ≤ d).For the b i and c i,ℓ , we can do so using a slight modification of the arguments in [21] . For the a i , however, Kane [21] exploits the fact that in his setting, X i is standard Gaussian for each fixed i ∈ [n], meaning the Xi,j are jointly standard Gaussian over j. This gives him access to strong concentration bounds. To get such concentration bounds in our setting, we would need information on the moments of the X i up to degree roughly log n. However, we only have access to moments up to degree k, which is not allowed to depend on n (as our tester uses time n Ω(k) ). Instead, we use significantly weaker concentration bounds based on moments of constant degree. By imposing stronger conditions on the b i , c i,ℓ , we are able to show that the remainder of the argument in [21] still goes through in our setting, see Appendix A.2.2. Finally, for N sufficiently large, this allows us to conclude (5) for f = sign(p).In this section, we show that the approach of [28] to prove testable learning guarantees for halfspaces w.r.t. the standard Gaussian cannot be generalized to PTFs. Namely, we show that in general, PTFs f (x) = sign(p(x)) with deg(p) ≥ 3 cannot be approximated up to arbitrary error w.r.t. N (0, I n ) by a polynomial of the form h(x) = q(p(x)), regardless of the degree of q. 2 Importantly, we show that this is the case even if one makes certain typical structural assumptions on p which only change the PTF f = sign(p) on a set of negligible Gaussian volume; namely that p is square-free and that {p ≥ 0} ⊆ R n is compact. Our main technical contribution is an extension of a well-known inapproximability result due to Bun & Steinke (Theorem 15 below) to distributions 'with a single heavy tail' (see Theorem 18) .Approximating the sign-function on the real line Let p # N (0, I n ) be the push-forward of the standard Gaussian distribution by p, which is defined byEQUATIONNote that, if h(x) = q(p(x)), we then haveE X∼N (0,In) [|h(X) -f (X)|] = E Y ∼p # N (0,In) [|q(Y ) -sign(Y )|]. Finding a good approximator h ≈ f of the form h = q • p is thus equivalent to finding a (univariate) polynomial q which approximates the sign-function on R well under the push-forward distribution p # N (0, I n ). In light of this observation, we are interested in the following question: Let D be a distribution on the real line. Is it possible to find for each ε > 0 a polynomial q such thatE Y ∼D [|q(Y ) -sign(Y )|] ≤ ε?This question is well-understood for distributions D whose density is of the form w γ (x) := C γ exp(-|x| γ ), γ > 0. Namely, when γ ≥ 1, these distributions are log-concave, and the question can be answered in the affirmative. On the other hand, when γ < 1, they are log-superlinear, and polynomial approximation of the sign function is not possible. Theorem 13 (see, e.g. [20] ). Let D be a log-concave distribution on R. Then, for any ε > 0 there exists a polynomialq such that E Y ∼D [|q(Y ) -sign(Y )|] ≤ ε. Definition 14. Let D be a distribution on R whose density function w satisfies w(x) ≥ C • w γ (x) ∀ x ∈ Rfor some γ < 1 and C > 0. Then we say D is log-superlinear (LSL). Theorem 15 (Bun-Steinke [6] ). Let D be an LSL-distribution on R. Then there exists an ε > 0 such that, for any polynomial q, we haveE Y ∼D [|q(Y ) -sign(Y )|] > ε.When p is of degree 1 (i.e., when f = sign(p) defines a halfspace), the push-forward distribution D = p # N (0, I n ) defined in ( 6) is itself a (shifted) Gaussian. In particular, it is log-concave and by Theorem 13 approximation of the sign-function w.r.t. D is possible. On the other hand, when p is of higher degree, D could be an LSL-distribution, meaning approximation of the sign-function w.r.t. D is not possible by Theorem 15. For instance, consider p(x) = x 3 . The density w of p # N (0, 1) is given by w(x) = C • |x| -2/3 • exp -|x| 2/3, and so p # N (0, 1) is log-superlinear.Choice of description. The example p(x) = x 3 is artificial: We have sign(p(x)) = sign(x), and so the issue is not with the concept f = sign(p), but rather with our choice of description p. In general, one can (and should) assume that p is square-free, meaning it is not of the form p = p 2 1 • p 2 . Indeed, note that for such a polynomial, we have sign(p(x)) = sign(p 2 (x)) almost everywhere. Square-freeness plays an important role in the analysis of learning algorithms for PTFs, see, e.g., [22, Appendix A]. It turns out that even if p is square-free, the distribution p # N (0, I n ) can still be log-superlinear, e.g., when p(x) = x(x -1)(x -2). Note that, for this example, sign(p) describes a non-compact subset of R. This is crucial to find that p # N (0, 1) is LSL. Indeed, if {p ≥ 0} ⊆ R were compact, then p max = sup x∈R p(x) < ∞, and so the density w of p # N (0, 1) would satisfy w(x) = 0 for all x > p max . In particular, w would not be log-superlinear. One could therefore hope that assuming {p ≥ 0} is compact might fix our issues. This assumption is reasonable as {p ≥ 0} can be approximated arbitrarily well by a compact set (in terms of Gaussian volume). On the contrary, we show the following. Theorem 16. There exists a square-free polynomial p, so that {p ≥ 0} ⊆ R is compact, but for which there exists ε > 0 so that, for any polynomial q, E X∼N (0,1) [|q(p(X)) -sign(p(X))|] > ε.To establish Theorem 16, we prove a 'one-sided' analog of Theorem 15 in Appendix B.1, which we believe to be of independent interest. It shows impossibility of approximating the sign-function under a class of distributions related to, but distinct from, those considered by Bun & Steinke [6] . The key difference is that the densities in our result need only to have a single heavy tail. However, this tail must be 'twice as heavy' (γ < 1/2 vs. γ < 1). We emphasize that [6] does not cover compact PTFs. Definition 17. Let D be a distribution on R whose density function w satisfiesw(x) ≥ C • w γ (x) ∀ x ∈ (-∞, 1]for some γ < 1/2 and C > 0. Then we say D is one-sided log-superlinear. Theorem 18. Let D be a one-sided LSL-distribution on R. Then there exists an ε > 0 such that, for any polynomial q, we haveE Y ∼D [|q(Y ) -sign(Y )|] > ε.Proof of Theorem 16. It suffices to find a square-free polynomial p for which {p ≥ 0} is compact, and the push-forward distribution p # N (0, 1) is one-sided LSL. A direct computation shows thatp(x) := -x(x -1)(x -2)(x -3)(x -4)(x -5)meets the criteria, see Appendix B.2 for details.In this section, we give a formal proof of our main result, Theorem 3, that we restate here. Theorem 19 (Formal version of Theorem 3). Let d ∈ N. For any ε > 0, the concept class of degree-d polynomial threshold functions in n variables can be testably learned up to error ε w.r.t. the standard Gaussian N (0, I n ) in time and sample complexityn O d ε -4d•7 d ε -O d ε -4d•7 d ,In particular, if d is constant, the time and sample complexity is n poly(1/ε) .Our goal to show this result is to apply Theorem 9. We first focus on proving the fooling condition in this theorem. Recall that for this we need to show that there are k and η such that if D ′ matches the moments of N (0, I n ) up to degree k and slack η, then we haveE X∼D ′ [f (X)] -E Y ∼N (0,In) [f (Y )] ≤ ε/2.In order to show this, we follow the result of [21] (see Theorem 11) . This paper shows this condition for any distribution D ′ that is a k-independent Gaussian, i.e. for which the marginal of every subset of k coordinates is N (0, I k ).The reason why it is enough to only focus on satisfying the fooling condition is that for any η, we can find m large enough that the first condition of Theorem 9 is satisfied for N (0, I n ) (see Remark 10 and Fact 36). For k we choose the same value as in [21] , namelyEQUATION)We first show how to choose η for the case of multilinear polynomial polynomials in Appendix A.1. In Appendix A.2, we generalize the fooling result to arbitrary PTFs. Finally, in Appendix A.3, we show how to apply Theorem 9 to get testable learning for PTFs.Thus, let f ∈ C and let p be the multilinear polynomial (of degree d) such that f (x) = sign(p(x)).Note that this notation is different than the one used in [21] . There, the roles of f and F are interchanged. We use f for the PTF throughout to be consistent with the previous work on (testable) learning. Without loss of generality, we assume that the sum of the squares of the coefficients of p is 1. We can make this assumption since rescaling does not change the PTF.The main result of this section is the following proposition. Proposition 20 (Fooling for multilinear PTFs). Let ε > 0. Suppose that D ′ approximately matches the moments of N (0, I n ) up to degree k and slack η,where k ≥ Ω d ε -4d•7 d , and η ≤ n -Ω d (k) k -Ω d (k) .Then, we have that, for any multilinear f ∈ F PTF,d ,E X∼D ′ [f (X)] -E Y ∼N (0,In) [f (Y )] ≤ O d (ε).Note that we only show O d (ε) here instead of ε/2, which is needed to apply Theorem 9. This simplifies the notation in our proof of this proposition. We later apply this proposition toε ′ = ε/Ω d (1)to conclude the fooling result we need.As mentioned earlier, the general strategy to do this is based on [21] . We want to find a function f : R n → R that approximates f . We will define this function in Appendix A.1.1. In Appendix A.1.2, we show that the expectation of f is close under D ′ and N (0, I n ). More precisely, in Lemma 25, we show that under the above assumption on η, we have thatE Y ∼N (0,In) [ f (Y )] -E X∼D ′ [ f (X)] ≤ O(ε).In Appendix A.1.3, we then show that under both D ′ and N (0, I n ) the expectation of f and f are close and complete the proof of Proposition 20. More precisely, from [21, Proposition 14] (restated in Lemma 28), we get thatE Y ∼N (0,In) [f (Y )] -E Y ∼N (0,In) [ f (Y )] ≤ O(ε). In Appendix A.1.3, we then also show that this also holds for X ∼ D ′ instead of Y ∼ N (0, I n ). More precisely, we show in Lemma 29 that Lemmas 25 and 28 contain already enough information about the moment-matching distribution D ′ to conclude Proposition 20.In this section, we want to define the function f that should be thought of as a smooth approximation of the PTF f . In order to define this function, we first restate the following structural theorem from [21] .Lemma 21 ([21, Proposition 4]). Let m 1 ≤ m 2 ≤ • • • ≤ m d be integers. Then there exists integers n 1 , n 2 , . . . , n d , where n i ≤ O d (m 1 m 2 . . . m i-1 ) and (non-constant homogeneous multilinear) polynomials h 1 , . . . , h d , P i,j (1 ≤ i ≤ d, 1 ≤ j ≤ n i ) such that:1. The sum of the squares of the coefficients of P i,j is 1.2. If Y ∼ N (0, I n ) and ℓ ≤ m i , then E |P i,j (Y )| ℓ ≤ O d ( √ ℓ) ℓ . 3. p(Y ) = d i=1 h i (P i,1 (Y ), P i,2 (Y ), . . . , P i,ni (Y )).The values of m i we want to choose are as in [21] , i.e. we letm i = Θ d ε -3•7 i d .Given this structure theorem, we introduce now the following notation that we use throughout the remainder of this section, analogous to [21] . As before, we use p : R n → R to be denote the multilinear polynomial and f : R n → [-1, 1] to be the PTF we are interested in, i.e. f (x) = sign(p(x)). Furthermore, the P i,j : R n → R for i ∈ [n] and j ∈ [n i ] are the polynomials in the structure theorem. We denote by P i : R n → R ni for i ∈ [n] the vector (P i,1 , . . . , P i,ni ) and byP : R n → R n1 × • • • × R n d the vector (P 1 , . . . , P d ). Finally, we define F : R n1 × • • • × R n d → R as the function F (y 1 , . . . , y d ) = d i=1 h i (y i ), i.e. we get f (x) = F (P (x)). Similar to Condition 1 in the above lemma, we can also get a bound on the sum of the absolute values of the coefficients of the P i,j . We need this later in the proof of Lemma 25. Fact 22. For any i ∈ [n] and j ∈ [n i ], the sum of the absolute values of the coefficients of P i,j is at most n d/2 . The idea to prove this is to bound the number of coefficients we have and use an inequality between the 1and 2-norm. The detailed argument can be found in Appendix C.1. Furthermore, we have an analogous result to Item 2 for the moment-matching distributions, which is again proved in Appendix C.1. We need this result later for concluding that f is a good approximation under the moment matching distribution D ′ . Fact 23. For any i ∈ [d], j ∈ [n i ] and ℓ ≤ k/d, we have thatE X∼D ′ P i,j (X) ℓ ≤ E Y ∼N (0,In) P i,j (Y ) ℓ + ηn dℓ/2 .As in [21] , we now consider the function ρ C : R n → R defined in the following lemma. Lemma 24 ([21, Lemma 5] ). LetB(ξ) = 1 -∥ξ∥ 2 2 if ∥ξ∥ 2 ≤ 1 0 else and ρ 2 (x) = | B(x)| 2 ∥B∥ 2 L 2, where where B is the Fourier transform of B. Then, the function ρ C defined byρ C (x) = C 2 n ρ 2 Cx 2satisfies the following conditions1. ρ C ≥ 0,R n ρ(x) dx = 1, 3. for any unit vector v and any non-negative integer ℓ we haveR n |D ℓ v ρ(C)(x)| dx ≤ C ℓ , 4. for D > 0, ∥x∥2≥D |ρ C (x)| dx = O n CD 2 .We now define the following three functions ρ, F and in particular f , in the same way as in [21] . We let ρ :R n1 × • • • × R n d → R be defined as ρ(y 1 , . . . , y d ) = ρ C1 (y 1 ) • • • • • ρ C d (y d ),where the C i are the same as in [21] , i.e. we let C i = Θ d ε -7 i d . Using this function, we define an approximationF : R n1 × • • • × R n d → R to F as the convolution F = F * ρ and an approximation f : R n → R to f as f (x) = F (P (x)).The general strategy to prove Proposition 20 is show the following three steps, where as usualEQUATIONA.1.2 Expectations of f under the Gaussian and the moment-matching distribution are closeIn this section, we want to prove the middle approximation of (8) . More precisely, we show the following lemma. Lemma 25. Let ε > 0. Suppose that D ′ approximately matches the moments of N (0, I n ) up to degree k and slack η, k) . Then we have thatwhere k ≥ Ω d ε -4d•7 d , and η ≤ n -Ω d (k) k -Ω d (E Y ∼N (0,In) [ f (Y )] -E X∼D ′ [ f (X)] ≤ O(ε).We want to do this similar to [21, Section 6] . For this, let T be the Taylor approximation of F around 0. We use degree m i for the ith batch of coordinates (recall that F :R n1 × • • • × R n d → R).The strategy to show Lemma 25 is to proceed in the following three steps, where againEQUATIONThe first approximation above only involves the Gaussian Y , so we get directly from [21, Proof of Proposition 8 ] thatE Y ∼N (0,In) [| f (Y ) -T (P (Y ))|] ≤ O(ε). We now want to extend this also to moment-matching distribution, which we do in the following lemma, i.e. show the third approximation in (9) . Lemma 26. Let ε > 0. Suppose that D ′ approximately matches the moments of N (0, I n ) up to degree k and slack η, where k ≥ Ω d ε -4d•7 d and η ≤ 1 kd . Then, we have thatE X∼D ′ [| f (X) -T (P (X))|] ≤ O(ε)This proof follows closely [21, Proof of Proposition 8], which is why we defer the proof to Appendix C.2.Note that the condition on η in this lemma is also satisfied for the η from Lemma 25. Thus, it remains to proveE Y ∼N (0,In) [T (P (Y ))] -E X∼D ′ [T (P (X))] ≤ O(ε) to complete the proof of Lemma 25.Note that in contrast to [21] , this quantity is not 0 in our case since we only have approximate moment matching. This is the main technical difficulty in our proof for the multilinear case. We need to give a different argument here and argue that this is small even if X is only approximately moment matching a Gaussian and not a k-independent Gaussian. We can write the Taylor expansion as followsT (x) = α=(α1,...,α d ): |αi|≤mi 1 α! ∂ α F (0)x α ,where the α i are multi-indices in N ni . We want to prove the following lemma about the coefficients in the Taylor expansion. Proof of Lemma 25. As argued above, we already know thatE Y ∼N (0,In) [| f (Y ) -T (P (Y ))|] ≤ O(ε) and E X∼D ′ [| f (X) -T (P (X))|] ≤ O(ε).It thus remains to argue thatE Y ∼N (0,In) [T (P (Y ))] -E X∼D ′ [T (P (X))] ≤ O(ε).Define the vectors t = (t α ) and u = (u α ) byt α := 1 α! ∂ α F (0) and u α := E Y ∼N (0,In) [P (Y ) α ] -E X∼D ′ [P (X) α ] .We then have thatE Y ∼N (0,In) [T (P (Y ))] -E X∼D ′ [T (P (X))] = |⟨t, u⟩| ≤ ∥t∥ 1 • ∥u∥ ∞ .We now want to bound ∥t∥ 1 and ∥u∥ ∞ separately. For the bound on ∥t∥ 1 , note that, by Lemma 27, we have|t α | = 1 α! ∂ α F (0) ≤ d i=1 C |αi| i .Plugging in the definition ofC i = Θ d ε -7 i d ≤ O d (k) and using |α| = d i=1 |α i | ≤ k, we get that |t α | ≤ k O d (k) .Since we have that n i ≤ k, we can conclude that the number of multi-indices α with k) and thus, we have that k) .|α i | ≤ k is at most (dk) k ≤ k O d (∥t∥ 1 = α |t α | ≤ k O d (We now move on to bound ∥u∥ ∞ . We write P i,j as followsP i,j (x) = β a (β) i,j x β .Here, the β in the sum goes over all multi-indices with |β| being the degree of P i,j , which is at most d. By Fact 22, we have thatβ |a (β) i,j | ≤ n d/2 .Let |α| = ℓ be such that |α i | ≤ m i (i.e. the term appears in the Taylor expansion) and let (i 1 , j 1 ), . . . , (i ℓ , j ℓ ) be such that P (x) α = P i1,j1 (x) . . . P i ℓ ,j ℓ (x).Note that if some (α i ) j > 1, we include the corresponding factor P i,j multiple times. We can now expand P (x) α as followsP (x) α =   β1 a (β1) i1,j1 x β1   . . .   β ℓ a (β ℓ ) i ℓ ,j ℓ x β ℓ   = β1 • • • β ℓ a (β1) i1,j1 . . . a (β ℓ ) i ℓ ,j ℓ x β1+•••+β ℓ . Now, note that k ≥ d(m 1 + • • • + m d ) (this condition is in addition to the conditions on k in [21] but it does not change the asymptotic value of k as stated in (7) ). We get that the degree of the terms appearing in the sum is|β 1 | + • • • + |β ℓ | ≤ d|α| ≤ d(m 1 + . . . m d ) ≤ k and thus that |E Y ∼N (0,In) [P (Y ) α ] -E X∼D ′ [P (X) α ] | ≤ β1 • • • β ℓ |a (β1) i1,j1 | . . . |a (β ℓ ) i ℓ ,j ℓ |η.Here, we used the triangle inequality and the fact that|E Y ∼N (0,In) Y β1+•••+β ℓ -E X∼D ′ X β1+•••+β ℓ | ≤ η.Thus, we can compute|E Y ∼N (0,In) [P (Y ) α ] -E X∼D ′ [P (X) α ] | ≤ β1 • • • β ℓ |a (β1) i1,j1 | . . . |a (β ℓ ) i ℓ ,j ℓ |η =   β1 |a (β1) i1,j1 |   . . .   β ℓ |a (β ℓ ) i ℓ ,j ℓ |   η = ∥a i1,j1 ∥ 1 . . . ∥a i ℓ ,j ℓ ∥ 1 η ≤ n ℓd/2 η = n |α|d/2 η.Thus, we get∥u∥ ∞ ≤ n O d (k) η. Finally, we can conclude that E Y ∼N (0,In) [T (P (Y ))] -E X∼D ′ [T (P (X))] ≤ ∥t∥ 1 • ∥u∥ ∞ ≤ n O d (k) k O d (k) η ≤ O(ε) since we have the conditions η ≤ n -Ω d (k) k -Ω d (k) and k -1 ≤ O(ε).In this section, we want to complete the proof of Proposition 20 that showsE X∼D ′ [f (X)] -E Y ∼N (0,In) [f (Y )] ≤ O d (ε).So far, we already showed in Lemma 25 thatE Y ∼N (0,In) f (Y ) -E X∼D ′ f (X) ≤ O(ε).Thus, it remains to show that under both X ∼ D ′ and Y ∼ N (0, I n ), the expectation of f and f differ by at most O d (ε). For Y , we directly get the following. Note that the approximation f depends on ε via the numbers m i in the structure theorem Lemma 21 and the C i in the definition of ρ. Lemma 28 ([21, Proposition 14] ). Let ε > 0. Then, we have thatE Y ∼N (0,In) [f (Y )] -E Y ∼N (0,In) f (Y ) ≤ O(ε).The reason why we get this directly from [21] is that this lemma only concerns the Gaussian and not the moment matching distribution. Combining this with the above, we have now shown thatE Y ∼N (0,In) [f (Y )] -E X∼D ′ f (X) ≤ O(ε).To conclude Proposition 20 we want to use the following lemma. EQUATION• P X∼D ′ [∃i, j : |P i,j (X)| > B i ] ≤ O(ε).Then, we have that|E Y ∼N (0,In) [f (Y )] -E X∼D ′ [f (X)] | ≤ O d (ε).We are now ready to prove Proposition 20.Proof of Proposition 20. Using Lemmas 25, 28 and 29, it remains to argue thatP X∼D ′ [∃i, j : |P i,j (X)| > B i ] ≤ O(ε).This is true by Markov's inequality and looking at the log(dn i /ε) = ℓ-th moment since this implies that (assuming without loss of generality that ℓ is even)P X∼D ′ [|P i,j (Y )| ≥ B i ] ≤ E X∼D ′ P i,j (X) ℓ B ℓ i ≤ E Y ∼N (0,In) P i,j (Y ) ℓ + ηn dℓ/2 B ℓ i ≤ E Y ∼N (0,In) P i,j (Y ) ℓ + 1 B ℓ i ≤ O d ( √ ℓ) ℓ B ℓ i ≤ e -ℓ = ε dn i .In the second step we used Fact 23. Note that ℓ = log(dn i /ε) ≤ k/d is ensured by the choice of k as in [21] . In the third step we used that since dℓ/2 ≤ k and thus the condition on η in the statement of this proposition ensures η ≤ 1 n dℓ/2 . In the fourth step we used Lemma 21. In the fifth step we used the conditionB i ≥ Ω d ( √ ℓ). This is true by the choice of B i = Θ d ( log(1/ε)) and the fact that log(n i ) ≤ i-1 j=1 log(m j ) ≤ O d (log(1/ε)). In the last step, we then used the definition of ℓ. Taking a union bound over j and then over i givesP X∼D ′ [∃i, j : |P i,j (X)| > B i ] ≤ O(ε),which completes the proof.In this section, we want to prove a result similar to Proposition 20 for arbitrary PTFs and not just multilinear ones. Namely, we show Proposition 12, which we restate with a slight modification below. Namely, we only proveE Y ∼N (0,In) [f (Y )] -E X∼D ′ [f (X)] ≤ O d (ε) instead of ε/2.The reason for this is, as for Proposition 20, this simplifies the proof and we take care of this difference when we apply Theorem 9 in Appendix A. k) . Then, we have that for any f ∈ F PTF,dη ≤ n -Ω d (k) k -Ω d (E Y ∼N (0,In) [f (Y )] -E X∼D ′ [f (X)] ≤ O d (ε).The general strategy for this will be to, given a polynomial p, find another polynomial p δ and reduce to Proposition 20. This strategy and the construction described in what follows are the same as used in [21, Lemma 15] . The following lemma is an analog of this lemma for our case. However, there is one key part of the proof of [21] that breaks in our setting, as explained in Section 2.3.2. Specifically, in [21] all restrictions to coordinates are exactly Gaussian, and in particular we have access to moments of all orders. The proof in [21] exploits this since it considers a number of moments depending on the dimension, whereas we only have access to a constant number of moments.Lemma 31. Let δ > 0. Suppose X ∼ D ′ approximately matches the moments of N (0, I n ) up to degree k and slack η, where η ≤ δ O d (1) n -Ω d (1) k -k and k ≥ Ω d (1) . Let Y ∼ N (0, I n ). Then there are a polynomial p δ and random variables X and Ŷ , all in more variables, such that • Ŷ is a Gaussian with mean 0 and covariance identity,• X is approximately moment-matching Ŷ up to degree k and slack η = η(2k) k/2 ,• P Y, Ŷ |p(Y ) -p δ ( Ŷ )| > δ < δ, and, • P X, X |p(X) -p δ ( X)| > δ < δ.Given this lemma, we can prove Proposition 30. Since this proof follows closely [21, Proof of Theorem 1], we defer it to Appendix C.2It remains to prove Lemma 31 and to explain how we construct p δ as well as X and Ŷ . We do the latter in Appendix A.2.1. Namely, we show there how to construct the random variables X and Ŷ from X and Y . In this section, we also make precise in how many variables the polynomial p δ is (and thus also the random variable X and Ŷ ). The proof that they satisfy the condition required by Lemma 31 can be found in Appendix C.2. In Appendix A.2.2 we then state a lemma about how we want to replace a factor X ℓ i in p by a multilinear polynomial in X (whose proof is in Appendix C.2) and use it construct p δ and prove Lemma 31.To show Lemma 31, we want, given a polynomial p and δ > 0 as well as two random variables X and Y , where Y ∼ N (0, I n ) and X matches the moments of N (0, I n ) up to degree k and slack η, to construct a multilinear polynomial p δ in more variables and two random variables X and Ŷ such that Ŷ is a again Gaussian with mean 0 and covariance identity and X matches the moments of Ŷ up to degree k and slack η. The guarantee we then want to show in Lemma 31 is thatP Y, Ŷ |p(Y ) -p δ ( Ŷ )| > δ < δ and P X, X |p(X) -p δ ( X)| > δ < δ,where the probability is over the joint distribution of Y and Ŷ respectively X and X.Let N be a (large) positive integer that will be chosen later. Then the number of variables of the new polynomial p δ is n • N , i.e. we replace every variable of p by N variables for p δ . We make the following definition. For i ∈ {1, . . . , n} and j ∈ {1, . . . , N }, we defineXi,j := 1 √ N X i + Z (i) j ,where Z (i) is are multivariate Gaussians with mean 0, variance 1 -1 N and covariance -1 N , independent for different i and independent from X. In particular, the choice of the covariance matrix ensures that we deterministically have Z i,1 + . . . Z i,N = 0 and thus X i = N j=1 Xi,j . The construction for Ŷ is the same, i.e.= 1 √ N Y i + Z ′(i) j ,where Z ′(i) are again multivariate Gaussians with mean 0, variance 1 -1 N and covariance -1 N , independent for different i and also independent from Y (as well as X and Z).We now have the following two lemmas that relate X to X and Ŷ to Y . The proofs of these lemmas are in Appendix C.2. Lemma 32. Suppose X approximately matches the moments of N (0, I n ) up to degree k and slack η. Then, X approximately matches the moments of N (0, I nN ) up to degree k and slack η = (2k) k/2 η.Lemma 33. If Y ∼ N (0, I n ), then Ŷ ∼ N (0, I nN ).Lemma 33 is already proven in [21, Lemma 15] , but for completeness we also make it explicit in Appendix C.2.After constructing the random variables X and Ŷ , we now move on to construct the polynomial p δ . As in [21, Proof of Lemma 15], the goal is to replace every factor x ℓ i of p by a multilinear polynomial in variables (x i,j ) j such that X ℓ i is close to this polynomial evaluated in ( Xi,j ) j with large probability. Doing this for all factors x ℓ i appearing in p and combining the new multilinear terms, this then gives a multilinear polynomial p δ of degree d. Note that the polynomial is in fact multilinear since for replacing x i we only use the variables xi ′ ,j where i ′ = i.Note that it is enough to showP |p(X) -p δ ( X)| > δ < δ.The reason for this is that, if Y ∼ N (0, I n ), then Y in particular matches the moments of N (0, I n ) (exactly) and the proof for X applies and we can conclude Lemma 31, using also Lemmas 32 and 33.In order to get the above, we let δ ′ be a small positive number (depending on δ, n, d) to be chosen later. We need the following lemma.Lemma 34. Let δ ′ > 0. Let i ∈ [n] and ℓ ∈ [d].Assume that each of the following conditions holds with probability 1EQUATIONEQUATIONThen, there is a multilinear polynomial in Xi,j that is withinO d (δ ′ ) of X ℓ i with probability 1 -δ ′ .The proof of this lemma is analogous to [21, Proof of Lemma 15] and is deferred to Appendix C.2. However, in contrast to [21] , there is a key difference in this lemma. The bound on the RHS of ( 10) is much weaker than the one used by Kane. The reason for that is that the bounds used there do not hold in our case, since we only have that X (approximately) matches the moments of N (0, I n ). By using stronger bounds for ( 11) and ( 12), we are able to generalize the proof from Kane to our setting. For a more detailed explanation why we need to change the bounds, we refer to Section 2.3.2.We now defineEQUATION)Why we make this choice will become clear in the proof of Lemma 31 below. In Appendix C.2, we prove the following lemma that states that this choice of δ ′ and the condition on η from Lemma 31 ensure that we can apply Lemma 34.Lemma 35. Let δ ′ as in (13) .Assuming η ≤ δ O d (1) n -Ω d (1) k -k, there is a choice of N (independent of i or ℓ) such that (10), ( 11) and (12) hold, each with probability 1 -δ ′ d .Proof of Lemma 31. Lemma 34 (together with Lemma 35) shows that we can replace X ℓ i by a multilinear polynomial in Xi,j that is within O d (δ ′ ) of X ℓ i with probability 1 -δ ′ for our choice of δ ′ as in (13) . Since δ ′ ≤ δ 2dn , we can union bound these events over all i ∈ [n] and ℓ ∈ [d] and get that with probability 1 -δ 2 , we have that for any i ∈ [n] and ℓ ∈ [d], we have that the replacement polynomial for X ℓ i is within O d (δ ′ ) of X ℓ i . Furthermore, for any i ∈ [n], we have that with probability 1 -δ 2n that |X i | ≤ 3 n δ . This is true since we match k ≥ 2 moments (and η ≤ 1 4 ), and thusP |X i | ≥ 3 n δ ≤ E X 2 i 3 n δ 2 ≤ (2 + η)δ 2 9n 2 ≤ δ 4n .Hence, we can again apply the union bound to show that with probability 1 -δ 2 , we have for any i ∈ [n] that |X i | ≤ 3 n δ . Thus, with probability 1 -δ, all the above events holds. Conditioned on that, we have that the replacement polynomial p δ is off by at most 3 n δ d O d (δ ′ ) multiplied by the sum of the coefficients of p. The later is at most n d/2 by Fact 22 applied to p instead of P i,j . Hence, the replacementpolynomial is off by at most O d n 3d/2 δ d δ ′ . Thus, since δ ′ ≤ δ Ω d n 3d/2 δ d, we get that with probability 1 -δ, p δ is off by at most δ, which is what we wanted to show.In this section, we prove Theorem 19. As already mentioned in the beginning of this section, we want to apply Theorem 9 for this. In Proposition 30, we have shown that if we have moment matching up to error η ≤ n -Ω d (k) k -Ω d (k) , then we have the fooling condition of Theorem 9.Y ∼N (0,In) [f (Y )] -E X∼D ′ [f (X)] | ≤ ε 2 butProposition 30 only gives O d (ε). Thus, technically, we apply Proposition 30 for ε ′ = ε Ω d (1) . However, this does not change the asymptotic condition on η described above. In summary, if η satisfies the condition as described above, we get indeed the fooling condition as needed for Theorem 9.The remaining part to prove Theorem 19 is to find an m such that with high probability over m samples from N (0, I n ) we have that the empirical distribution matches the moments up to degree k with error at most η. Then, we get testable learning of PTFs with respect to Gaussian in time and sample complexity m + n O(k) by Theorem 9.To get m, we use the following fact, which we prove in Appendix C.1. Using this, we can then prove Theorem 19. Fact 36. Given m ≥ Ω((2kn) k η -2 ) samples of N (0, I n ), we have that with high probability the empirical distribution matches the moments of N (0, I n ) up to degree k and slack η.Proof of Theorem 19. Using Theorem 9, as noted before, by Proposition 30, we get testable learning of degree d PTFs with respect to Gaussian in time and sample complexity bounded by m + n O(k) , where m is such that with high probability over m samples from N (0, I n ) we have that the empirical distribution matches the moments up to degree k with error at most η. It remains to determine m. By Fact 36, we get that the choice of m = Θ((2kn) k η -2 ) is enough. Now, in order to apply Proposition 30, we need to choose η= n -Θ d (k) k -Θ d (k) . Plugging in the value k = Θ d ε -4d•7 d we get η = ε Θ d ε -4d•7 d n -Θ d ε -4d•7 d and hence m = Θ (2kn) k n Θ d (ε -4d•7 d ) ε -Θ d (ε -4d•7 d ) .Thus, the time and sample complexity for testably learning PTFs isO (2kn) k n O d ε -4d•7 d ε -Ω d ε -4d•7 d n O(k) .Again, by plugging in the value k = Θ d ε -4d•7 d , we can simplify this to get that the sample and time complexity for testably learning PTFs isn O d ε -4d•7 d ε -Ω d ε -4d•7 d, which completes the proof of this theorem.In this section, we provide further details on the results claimed in Section 2.4. Specifically, we prove our impossibility result Theorem 16 below in Appendix B.2. For this, we first need to establish our 'one-sided' analog Theorem 18 of the inapproximability result for LSL-distributions of Bun & Steinke (Theorem 15), which we do in Appendix B.1.Let us begin by restating some important definitions and results from Section 2.4 for convenience. For γ > 0, we write w γ (x) := C γ • exp(-|x| γ ), where C γ is a normalizing constant which ensures w γ is a probability density. A distribution D on R is called log-superlinear (LSL) if its density function 3satisfies w(x) ≥ C • w γ (x) for all x ∈ R, for some γ ∈ (0, 1) and C > 0. Recall the following. Theorem (Restatement of Theorem 15). Let D be an LSL-distribution on R. Then there exists an ε > 0 such that, for any polynomial q, we haveE Y ∼D [|q(Y ) -sign(Y )|] > ε.We defined in Section 2.4 a 'one-sided' analog of LSL-distributions as follows. Definition (Restatement of Definition 17). Let D be a distribution on R whose density function w satisfies w(x) ≥ C • w γ (x) ∀ x ∈ (-∞, 1] for some γ < 1/2 and C > 0. Then we say D is one-sided log-superlinear.In this section, we prove Theorem 18, which is an analog of Theorem 15 for one-sided LSLdistributions, and the basis of our proof of Theorem 16 in Appendix B.2. Theorem (Restatement of Theorem 18). Let D be a one-sided LSL-distribution on R. Then there exists an ε > 0 such that, for any polynomial q, we haveE Y ∼D [|q(Y ) -sign(Y )|] > ε.For our proof, it is useful to first recall the main ingredient of the proof of Theorem 15 in [6] , which is the following inequality. Proposition 37 ([6, Lemma 20] ). Let q be a univariate polynomial, and let γ ∈ (0, 1). Then, there exists a constant M γ > 0, depending only on γ, so thatsup x∈R |q ′ (x)w γ (x)| ≤ M γ • R |q(x)|w γ (x) dx.Given Proposition 37, the intuition for the proof of Theorem 15 is that, if q is a good approximation of the sign-function on R, it must have very large derivative near the origin. On the other hand,E Y ∼D [|q(Y )|] is bounded from above (as E Y ∼D [| sign(Y )|] = 1), leading to a contradiction.The key technical tool in our proof of Theorem 18 is a version of Proposition 37 that applies to onesided LSL distributions. That is, a bound on the derivative of a polynomial in terms of its L 1 -norm on (-∞, 1] w.r.t. the weight w γ (x) = C γ • exp(-|x| γ ), γ < 1/2. We will only be able to obtain such a bound in a small neighborhood of 0 (Proposition 39 below), but this will turn out to be sufficient. We first need the following lemma, which bounds the derivative near 1. One can think of it as a one-sided Bernstein-Nikolskii-type inequality (whereas Proposition 37 is a Markov-Nikolskii-type inequality). Lemma 38. Let q be a univariate polynomial, and let γ < 1/2. Then, there exists a constant M ′ γ > 0, depending only on γ, so thatsup |x-1|≤ 1 4 |q ′ (x)| ≤ M ′ γ • ∞ 0 |q(x)|w γ (x) dx.Proof. By a substitution u 2 = x, and using the fact that w γ (x) := C γ exp(-|x| γ ) is even, we find∞ 0 |q(x)|w γ (x) dx = ∞ 0 |q(u 2 )|w γ (u 2 ) • 2u du = C γ C 2γ • ∞ -∞ |q(u 2 )u|w 2γ (u) du.Now, since 2γ < 1, we may apply Proposition 37 to the polynomial q(u) = q(u 2 )u, yielding an upper bound on its derivative for all u ∈ R; namelyw 2γ (u) • d du q(u) ≤ M 2γ • ∞ -∞ |q(u 2 )u|w 2γ (u) du = M 2γ C 2γ C γ • ∞ 0 |q(x)|w γ (x) dx.As w 2γ is monotonically decreasing, we have w 2γ (x) ≥ w 2γ (5/4) for all x ≤ 5/4, and so we findEQUATION)We wish to transform this bound on the derivative of q into a bound on the derivative of q. Note thatd du q(u) = d du [q(u 2 )u] = 2q ′ (u 2 )u 2 + q(u 2 ).We can bound this as followssup |u 2 -1|≤ 1 4 |2q ′ (u 2 )u 2 + q(u 2 )| ≥ 3 2 • sup |u 2 -1|≤ 1 4 |q ′ (u 2 )| -sup |u 2 -1|≤ 1 4 |q(u 2 )|.Now, switching our notation back to the variable x = u 2 , and using ( 14), we haveEQUATIONIt remains to bound the rightmost term in this inequality. Write c q > 0 for the constant (depending on q) satisfying:EQUATIONIf c q ≤ 2, we are done immediately by (15) , as then3 2 • sup |x-1|≤ 1 4 |q ′ (x)| ≤ Mγ + 2 w γ ( 5 4 ) • ∞ 0 |q(x)|w γ (x) dx.So assume that c q > 2. Note that∞ 0 |q(x)|w γ (x) dx ≥ w γ ( 5 4 ) • 5 4 3 4 |q(x)| dx ≥ w γ ( 5 4 ) • inf |x-1|≤ 1 4 |q(x)|,and so infEQUATION)Applying the mean value theorem to ( 16) and ( 17) on the interval [ 3 4 , 5 4 ], we find thatsup |x-1|≤ 1 4 |q ′ (x)| ≥ 2 • c q -1 w γ ( 5 4 ) • ∞ 0 |q(x)|w γ (x) dx = 2(c q -1) c q • sup |1-x|≤ 1 4 |q(x)|.As c q > 2 by assumption, this yieldssup |x-1|≤ 1 4 |q ′ (x)| ≥ sup |x-1|≤ 1 4 |q(x)|,and we may conclude from (15) that3 2 -1 • sup |x-1|≤ 1 4 |q ′ (x)| ≤ Mγ • ∞ 0 |q(x)|w γ (x) dx.Combining the cases c q ≤ 2, c q > 2 finishes the proof with M ′ γ = max{ Mγ + 2 wγ (5/4) , 2 Mγ }.Proposition 39. Let D be a one-sided LSL distribution on R. Then there exists a constant C D > 0 such that, for any polynomial q, we havesup |x|≤ 1 4 |q ′ (x)| ≤ C D • E X∼D [|q(X)|] .Proof. We wish to use Lemma 38, which gives us a bound on the derivative q ′ (x) of q when x ≈ 1.To transport this bound to the origin, we consider the shifted polynomial q(x) := q(1 -x). Let w be the density function of D. Since D is a one-side LSL-distribution, there exists a constant C > 0 and a γ ∈ (0, 1/2) such that w(x) ≥ C • w γ (x) for all x ∈ (-∞, 1]. As w γ is even, bounded from above and below on [0, 1], and w γ (x -1) ≤ w γ (x) for x ≤ 0, we can find a constant C ′ > 0 such thatw(x) ≥ C ′ • w γ (1 -x) ∀ x ∈ (-∞, 1]. Now, we find that ∞ 0 |q(x)|w γ (x) dx = 1 -∞ |q(1 -x)|w γ (1 -x) dx ≤ 1 C ′ • 1 -∞ |q(x)|w(x) dx ≤ 1 C ′ • E X∼D [|q(X)|] .As γ < 1/2, we may apply Lemma 38 to find thatsup |x-1|≤ 1 4 |(q) ′ (x)| ≤ M ′ γ • ∞ 0 |q(x)|w γ (x) dx ≤ M ′ γ C ′ • E X∼D [|q(X)|] .To finish the proof (withC D = M ′ γ /C ′ ), it remains to note that sup |x-1|≤ 1 4 |(q) ′ (x)| = sup |x|≤ 1 4 |q ′ (x)|.We are now ready to prove Theorem 18. Our approach is similar to the proof of Theorem 15 in [6] .Proof of Theorem 18. Let D be a one-side LSL-distribution, and suppose that q is a univariate polynomial satisfyingE X∼D [| sign(X) -q(X)|] ≤ 1. Since E X∼D [| sign(X)|] = 1,we may use the triangle inequality to find thatE X∼D [|q(X)|] ≤ 1 + 1 = 2.By Proposition 39, this means that, for some constant C D > 1 depending only on D,sup |x|≤ 1 4 |q ′ (x)| ≤ 2 • C D . Set η = (10C D ) -1 . It follows that sup |x|≤η |q(x) -q(0)| ≤ (10C D ) -1 • 2C D = 1 5 .Assuming first that q(0) ≤ 0, this means that|q(x) -sign(x)| ≥ 4 5 ∀ x ∈ [0, η].Let w be the density function D. As D is one-sided LSL, and η < 1, we know there is a constant C > 0, independent of η, such that w(x) ≥ C for x ∈ [0, η]. But, this implies thatE X∼D [| sign(X) -q(X)|] ≥ C η 0 | sign(x) -q(x)| dx ≥ 4 5 η • C,giving a uniform lower bound on E X∼D [| sign(X) -q(X)|] for all polynomials q. If, on the other hand q(0) ≥ 0, the same argument works after replacing [0, η] by [-η, 0].In this section, we complete the proof of Theorem 16 started in Section 2.4. Recall that, in light of Theorem 18, it remained to prove the following. Proposition 40. Let p(x) = -x(x -1)(x -2)(x -3)(x -4)(x -5). Then, p is square-free, {p ≥ 0} ⊆ R is compact, and p # N (0, 1) is one-sided log-superlinear.Proof. The first two properties follow directly. For the third, let w be the density function of p # N (0, 1). Applying the inverse function rule to w 2 (x) = C 2 • exp -|x| 2 , we havew(y) = C 2 • x∈p -1 (y) exp -|x| 2 • 1 |p ′ (x)| ∀ y ∈ R.We need to show that, for some C > 0 and γ ∈ (0, 1/2),EQUATIONQualitatively, the behavior of w can be described as follows. When y ≥ sup x∈R p(x) ≈ 17, then w(y) = 0. When y ≪ 0, then x ∈ p -1 (y) implies |x| ≈ |y| 1/6 , and so w(y) ≈ exp -|y| 1/3 . Finally, for any K > 0, there is a uniform lower bound on w(y) for all y ∈ [-K, 1]. To show (18) , it remains to make this description quantitative.As the leading term of p is -x 6 , there is a K > 0 such that |p -1 (y)| = 2 for all y ≤ -K, andx ∈ p -1 (y) =⇒ |x| ≤ 2|y| 1/6 ∀ y ≤ -K.This means that, for a (possibly larger) constant K ′ > 0, and some γ ∈ (1/3, 1/2), we haveEQUATIONNow, there is an M > 0 so thatx ∈ p -1 (y) =⇒ |x| ≤ M ∀ y ∈ [-K ′ , 1].It follows, as p -1 (y) is non-empty for y ≤ 1, thatEQUATIONCombining ( 19) and ( 20), and choosing C > 0 small enough, yields (18) .In this section, we prove several facts that we used in the proofs in Appendix A about the moments and other properties of a Gaussian random variable Y and a random variable X that matches the moments of a Gaussian up to degree k and slack η.First, we want to prove Fact 22, which we restate below, about the sum of the absolute values of the coefficients of the polynomials P i,j . Recall from Lemma 21 that the sum of the squares of the coefficients of the polynomials P i,j is 1.Fact (Restatement of Fact 22) . For any i ∈ [n] and j ∈ [n i ], the sum of the absolute values of the coefficients of P i,j is at most n d/2 .Proof. Similar to before, we write the P i,j as followsP i,j (x) = β a (β) i,j x β .The β in the sum goes over all multi-indices with |β| being the degree of P i,j , which is at most d. Thus, there are at most n d terms in the sum. By the structure theorem (Lemma 21), we know that∥a i,j ∥ 2 = β (a (β) i,j ) 2 = 1.We can now get a bound on the 1-norm as follows (since the number of coefficients a(β) i,j is at most n d ) β |a (β) i,j | = ∥a i,j ∥ 1 ≤ n d/2 ∥a i,j ∥ 2 ≤ n d/2 .Next, we want to show two facts about the moments of X. On the one hand, we want to show that under very mild assumptions on η, we can bound the moments of X similar as the moments of a Gaussian Y . We also prove Fact 23, which we also restate below, about the expectation of P i,j (X). For the Gaussian, we get a bound by Lemma 21 and we generalize this in this fact to the moment-matching distribution. Fact 41. Let η ≤ 1 and let D ′ be a distribution that matches the moments of N (0, I n ) up to degree k and slack η. Then, we have that for any multi-index α with |α| ≤ k we have|E X∼D ′ [X α ] | ≤ |α| |α| .Proof. We have that|E X∼D ′ [X α ] | ≤ |E Y ∼N (0,In) [Y α ] | + 1 ≤ |E Z∼N (0,1) Z |α| | + 1 ≤ 1 + 0 if |α| is odd (|α| -1)!! otherwise ≤ |α| |α| ,which is what we wanted to proof.i ∈ [d], j ∈ [n i ] and ℓ ≤ k/d, we have that E X∼D ′ P i,j (X) ℓ ≤ E Y ∼N (0,In) P i,j (Y ) ℓ + ηn dℓ/2 .Proof. Writing P i,j as in Fact 22P i,j (x) = β a (β) i,j x β ,we can compute E X∼D ′ P i,j (X) ℓ as followsE X∼D ′ P i,j (X) ℓ = β1,...,β ℓ a (β1) i,j . . . a (β ℓ ) i,j E X∼D ′ X β1+...β ℓ .Now, since X is η-approximately moment matching, we have that (note that P i,j has degree at most d and thus any term in the sum that degree at most dℓ ≤ k and thus the moment matching applies)E X∼D ′ X β1+...β ℓ = E Y ∼N (0,In) Y β1+...β ℓ ± η.Combining this with the above, we getE X∼D ′ P i,j (X) ℓ ≤ E Y ∼N (0,In) P i,j (Y ) ℓ + η   β a (β) i,j   ℓ .By Fact 22, we thus get thatE X∼D ′ P i,j (X) ℓ ≤ E Y ∼N (0,In) P i,j (Y ) ℓ + ηn dℓ/2 as wanted.Finally, we show two facts about the Gaussian distribution. First, we want to give a bound on the moments of a Gaussian random vector that has not necessarily independent entries and for which we only know that the variances are at most 1. If Z were independent, then the bound we show would follow directly by the formulas for the moments of a standard Gaussian. Second, we show Fact 36 that shows how many samples m of N (0, I n ) we need such that the empirical moments up to degree k match the actual moments of N (0, I n ) up to slack η.Fact 42. Let Z be a (multivariate) Gaussian random variable with mean 0 and variances at most 1. Then, for any multi-index β, we have thatE Z β ≤ |β| |β|/2 .Proof. We want to show that for any random variables W 1 , . . . , W ℓ we have  E   ℓ j=1 W j     ℓ ≤ ℓ j=1 E W ℓ j .To prove this, we use induction and Hölder's inequality. The case ℓ = 1 follows directly and for ℓ ≥ 2 we can compute using Hölder's inequality, since1 ℓ ℓ-1 + 1 ℓ = 1, E   ℓ j=1 W j   ≤   E   ℓ-1 j=1 W ℓ ℓ-1 j     ℓ-1 ℓ • E W ℓ ℓ 1 ℓ .Thus, we get, using the induction hypothesis,  E   ℓ j=1 W j     ℓ ≤   E   ℓ-1 j=1 W ℓ ℓ-1 j     ℓ-1 • E W ℓ ℓ ≤ ℓ j=1 E W ℓ j .We now use this result with ℓ = |β| and the W 1 , . . . , W ℓ being the Z j , where every entry Z j occurs β j times. Then we getE Z β ≤   j E Z ℓ j βj   1 ℓ.Since E [Z j ] = 0 and Var [Z j ] ≤ 1, we have that E Z ℓ j ≤ ℓ ℓ/2 and thus we getE Z β ≤ ℓ ℓ/2 = |β| |β|/2 .Fact (Restatement of Fact 36). Given m ≥ Ω((2kn) k η -2 ) samples of N (0, I n ), we have that with high probability the empirical distribution matches the moments of N (0, I n ) up to degree k and slack η.Proof. Given m samples from N (0, I n ), we want to compute the probability that for some α with |α| ≤ k we have that the empirical moment is close to the moment with high probability. We can compute using Chebyshev's inequality, where c α is the α-moment of N (0, I n ) and ĉα is the empirical moment, thatP [|ĉ α -c α | > η] ≤ Var [ĉ α ] η 2 = 1 m Var [Y α ] η 2 ≤ 1 m Var Y |α| 1 η 2 ≤ 1 m (2|α|) |α| η 2 ≤ 1 m (2k) k η 2 .To be able to use a union-bound, we need this to be smaller than O(n -k ), i.e. we needm ≥ Ω (2kn) k η 2 .In this section, we prove several lemmas that follow closely [21] . Some of these lemmas are also proven in [21] , but we include them here for completeness. We first prove Lemmas 26 and 27, which we need in order to show that the expectation of f is close under the moment-matching distribution and the Gaussian distribution.Lemma (Restatement of Lemma 26) . Let ε > 0. Suppose that D ′ approximately matches the moments of N (0, I n ) up to degree k and slack η, where k ≥ Ω d ε -4d•7 d and η ≤ 1 kd . Then, we have thatE X∼D ′ [| f (X) -T (P (X))|] ≤ O(ε)As mentioned earlier, this proof follows closely [21, Proof of Proposition 8] . In particular, we also need the following lemma from [21] .Lemma 43 ([21, Proposition 6] ). We have that, for x ∈ R n ,|T (P (x)) -F (P (x))| ≤ d i=1 1 + C mi i ∥P i (x)∥ mi 2 m i ! -1.The C i and m i are again as in [21] , i.e. we chooseC i = Θ d ε -7 i d and m i = Θ d ε -3•7 i d . Forthe proof, we furthermore need the bound on the expectation of |P i,j (X)| from Fact 23.Proof of Lemma 26. We have by Lemma 43 that|T (P (x)) -F (P (x))| ≤ d i=1 1 + C mi i ∥P i (x)∥ mi 2 m i ! -1.As in [21, Proof of Proposition 8], the RHS of this inequality is the sum over all non-empty subsets S ⊆ {1, 2, . . . , d} of the following term i∈SC mi i ∥P i (x)∥ mi 2 m i ! .Continuing exactly as in [21, Proof of Proposition 8], we want to show that any of these 2 d -1 terms is at most O(ε/2 d ). By the inequality of arithmetic and geometric means, we get that this term is at most1 |S| i∈S C mi i ∥P i (x)∥ mi 2 m i ! |S| .Thus, it remains to bound E X∼D ′ ∥P i (X)∥ ℓi 2 , where ℓ i = m i |S|. We do this as followsE X∼D ′ ∥P i (X)∥ ℓi 2 ≤ E X∼D ′ ∥P i (X)∥ 2ℓi 2 = E X∼D ′      ni j=1 P i,j (X) 2   ℓi   ,where we used the Cauchy-Schwarz inequality in the first step. Continuing further by applying Jensen's inequality to the (convex) function g(a) = a ℓi , we get  ni j=1 P i,j (X) 2   ℓi = n ℓi i   1 n i ni j=1 P i,j (X) 2   ℓi ≤ n ℓi i 1 n i ni j=1 P i,j (X) 2ℓi .Combining these two, we getE X∼D ′ ∥P i (X)∥ ℓi 2 ≤ n ℓi i 1 n i ni j=1 E X∼D ′ [P i,j (X) 2ℓi ].The next step is now different to [21] since we only have an approximately moment-matching distribution. By Fact 23, we get thatE X∼D ′ P i,j (X) 2ℓi ≤ E Y ∼N (0,In) P i,j (Y ) 2ℓi + ηn dℓi assuming that k ≥ 2d 2 m i (this ensures that 2ℓ i = 2m i |S| ≤ 2m i d is at most k/d as required in Fact 23). This condition is slightly different to [21] , but it does not change the (asymptotic) definition of k as in (7) . By Lemma 21, we now have thatE Y ∼N (0,In) P i,j (Y ) 2ℓi ≤ O d 2ℓ i 2ℓi = O d ℓ i 2ℓifor any j. Combining this with the above, we can conclude thatE X∼D ′ ∥P i (X)∥ ℓi 2 ≤ √ n i ℓi O d ℓ i ℓi + n ℓi i ηn dℓi ≤ O d n i m i |S| mi|S| , using that η ≤ 1 n dℓ i . This is true since ℓ i = m i |S| ≤ m i d ≤ k and thus η ≤ 1 n dk implies η ≤ 1 n dℓ i .The rest of this proof is again the same as in [21, Proof of Proposition 8] . We can computeE X∼D ′ |T (P (X)) -F (P (X))| ≤ 2 d max ∅̸ =S⊆[d] E X∼D ′ 1 |S| i∈S C mi i ∥P i (X)∥ mi 2 m i ! |S| ≤ 2 d max ∅̸ =S⊆[d]      max i∈S C mi|S| i O d n i m i |S| mi|S| m mi|S| i      ≤ 2 d max i∈[d],s∈[d] O d C i √ n i √ m i mis .By choice of m i , exactly as in [21] , we can conclude thatE X∼D ′ |T (P (X)) -f (P (X))| ≤ 2 d exp -min i∈[d] m i ≤ O(ε),which completes the proof.Lemma (Restatement of Lemma 27) . For any multi-index α = (α 1 , . . . ,α d ) ∈ N n1 × • • • × N n d , we have ∂ α F (0) ≤ d i=1 C |αi| i .Proof. As mentioned earlier, the ideas of the following proof are based on [21, Proof of Lemmas 5 and 7]. We have that|∂ α (F * ρ)| = |(F * ∂ α ρ)(0)| (property of convolution) ≤ ∥F ∥ L ∞ ∥∂ α ρ∥ L 1 ≤ ∥∂ α ρ∥ L 1 (F maps to [-1, 1]).Thus, it remains to bound ∥∂ α ρ∥ L 1 . Using the product structure of ρ, we have thatEQUATIONFirst, we compute a bound for ∥∂ αi ρ 2 ∥ L 1 . We generalize this afterwards to ρ Ci . Recall thatB(ξ) = 1 -∥ξ∥ 2 2 if ∥ξ∥ 2 ≤ 1 0 else and ρ 2 (x) = | B(x)| 2 ∥B∥ 2 L 2, where B is the Fourier transform of B. We first note thatB(x) • B(x) = | B(x)| 2 .Thus, we can apply the product rule to get the following formula for the derivative∂ αi ρ 2 = 1 ∥B∥ 2 L 2 β≤αi α i β (∂ β B)(∂ αi-β B) = 1 ∥B∥ 2 L 2 β≤αi α i β (∂ β B)(∂ αi-β B),where we used that the conjugate of the derivative is the derivative of the conjugate. We thus get the following by triangle inequality∥(∂ αi ρ 2 )(x)∥ L 1 ≤ 1 ∥B∥ 2 L 2 β≤αi α i β (∂ β B)(x)(∂ αi-β B)(x) L 1 .We now want to analyze (∂ β B)(x). We have(∂ β B)(x) = F(x β B(x)),where F(•) = • stands for the Fourier transform and we used a fact about the derivative of the Fourier transform. Thus, we get furthermore that∥(∂ αi ρ 2 )(x)∥ L 1 ≤ 1 ∥B∥ 2 L 2 β≤αi α i β F(x β B(x))F(x αi-β B(x)) L 1 = 1 ∥B∥ 2 L 2 β≤αi α i β x β B(x)x αi-β B(x) L 1 ≤ 1 ∥B∥ 2 L 2 β≤αi α i β B(x)B(x) L 1 = β≤αi α i β = 2 |αi| .The second step uses the Parseval identity; the third step uses that B(x) ̸ = 0 implies that ∥x∥ ∞ ≤ ∥x∥ 2 ≤ 1; the fourth step uses that ∥B(x)B(x)∥ L 1 = ∥B(x)∥ 2 L 2 . For an arbitrary C i , we can bound ∥∂ αi ρ Ci ∥ L 1 as follows. Recall thatρ Ci (x) = C i 2 n ρ 2 C i 2 x .We can compute, using the chain rule that(∂ α ρ Ci )(x) = C i 2 n (∂ α ρ 2 ) C i 2 x C i 2 |αi| .To illustrate how the chain rule implies this, we can compute∂ ∂x 1 ρ Ci (x) = C i 2 n n j=1 ∂ ∂x j ρ 2 C i 2 x ∂ ∂x 1 x → C i 2 x j (x) = C i 2 n n j=1 ∂ ∂x j ρ 2 C i 2 x • Ci 2 if j = 1 0 if j ̸ = 1 = C i 2 n+1 ∂ ∂x 1 ρ 2 C i 2 x .Doing this iteratively, we get the formula above. Now, we want to compute the L 1 -norm of that function. We get∥∂ αi ρ Ci ∥ 1 = R n (∂ αi ρ Ci )(x) dx = C i 2 n+|αi| R n (∂ αi ρ 2 ) C i 2 x dx = C i 2 |αi| R n (∂ αi ρ 2 )(y) dy y = C i 2 x = C i 2 |αi| ∥∂ αi ρ 2 ∥ 1 .Using the bound from above on ∥∂ αi ρ 2 ∥ 1 , we thus getEQUATIONCombining ( 21) and ( 22) completes the proof.Next, we prove how we can generalize fromE Y ∼N (0,In) [f (Y )] -E X∼D ′ f (X) ≤ O(ε)to the fooling condition we needE Y ∼N (0,In) [f (Y )] -E X∼D ′ [f (X)] ≤ O d (ε).This proof is based on [21, Proof of Proposition 2] . It turns out that this part of [21] does not need that X is k-Gaussian but works on the following, weaker assumptions. Lemma (Restatement of Lemma 29) . Let ε > 0. Suppose that D ′ is a distribution such that the following holdsEQUATION• P X∼D ′ [∃i, j : |P i,j (X)| > B i ] ≤ O(ε).Then, we have that|E Y ∼N (0,In) [f (Y )] -E X∼D ′ [f (X)] | ≤ O d (ε).In the proof of this lemma, we use the following theorem about anti-concentration of a polynomial of a Gaussian random variable. Importantly, it is enough to have this result for the Gaussian random variable Y and we do not need it for the moment-matching distribution.Theorem 44 (Carbery and Wright, see [21, Theorem 13] or [7, Theorem 8] ). Let p be a degree d polynomial. Suppose that E Y ∼N (0,In) p(Y ) 2 = 1. Then, for ε > 0,P Y ∼N (0,In) [|p(Y )| < ε] ≤ O d (dε 1/d ).Proof of Lemma 29. Note that [21, Lemma 12 and proof of Proposition 14] and the second condition in the lemma imply thatE [f (X)] ≥ E f (X) -O(ε) -2P -O d (ε d ) < p(X) < 0 and E [f (X)] ≤ E f (X) + O(ε) + 2P 0 < p(X) < O d (ε d ) .Using these and the first assumption of the lemma we get thatE [f (X)] ≥ E [f (Y )] -O(ε) -2P -O d (ε d ) < p(X) < 0 and E [f (X)] ≤ E [f (Y )] + O(ε) + 2P 0 < p(X) < O d (ε d ) .We have furthermore thatE [sign(p(X))] + 2P -O d (ε d ) < p(X) < 0 = E sign(p(X) + O d (ε d ) and E [sign(p(X))] -2P 0 < p(X) < O d (ε d ) = E sign(p(X) -O d (ε d ) .The reason for this is that adding or subtracting the two probability terms can be interpreted as changing the sign for values of X in (-O d (ε d ), 0) respectively (0, O d (ε d )), which the same as shifting the polynomial. Thus, when combining this with the above we get thatE sign(p(X) + O d (ε d )) ≥ E [sign(p(Y ))] -O(ε) and E sign(p(X) -O d (ε d )) ≤ E [sign(p(Y ))] + O(ε). Now we apply this result not to the polynomial p, but to the polynomial p ∓ O d (ε d ). This shifts the additional factor from the X-side to the Y -side and we getE [sign(p(X))] ≥ E sign(p(Y ) -O d (ε d )) -O(ε) as well as E [sign(p(X))] ≤ E sign(p(Y ) + O d (ε d )) + O(ε).Combining these two inequalities we get thatE sign(p(Y ) -O d (ε d )) -O(ε) ≤ E [f (X)] ≤ E sign(p(Y ) + O d (ε d )) + O(ε).For Y , we have that (since the inequality hold point-wise) k) . Then, we have that for any f ∈ F PTF,dE sign(p(Y ) -O d (ε d )) ≤ E [f (Y )] ≤ E sign(p(Y ) + O d (ε d )) .≤ n -Ω d (k) k -Ω d (E Y ∼N (0,In) [f (Y )] -E X∼D ′ [f (X)] ≤ O d (ε).Proof. As already before, we assume without loss of generality that the polynomial is normalized in the sense that the sum of the squares of the coefficients is 1 (this does not change the PTF). We setδ = ε d d .We first want to show that the condition on η in this lemma ensures that we can apply both Lemma 31 to construct the multilinear polynomial p δ and Proposition 20 to get the fooling condition for p δ .The condition for Lemma 31 is η ≤ δ O d (1) n -Ω d (1) k -k . Note that by our choice of k, we have 1) . Thus, for our choice of δ, the condition on η needed for Lemma 31 is satisfied by our assumption on η in this lemma. For Proposition 20, we need η = (2k k) , which is also satisfied by our condition on η. Note that we need this condition for η (and not η) since the new random variable X is only moment-matching up to slack η.ε O d (1) ≤ k -Ω d () k/2 η ≤ k -Ω d (k) n -Ω d (We now want to show that |P [p(X)> 0] -P [p(Y ) > 0]| ≤ O d (ε). Note that E [sign(p(X))] = P [p(X) ≥ 0] -P [p(X) < 0] = P [p(X) ≥ 0] -(1 -P [p(X) ≥ 0]) = 2P [p(X) ≥ 0] -1 and the same holds for Y . Thus, |P [p(X) ≥ 0] -P [p(Y ) ≥ 0]| ≤ O d (ε) will be enough since then |E [sign(p(Y ))] -E [sign(p(X))]| = 2 |P [p(Y ) ≥ 0] -P [p(X) ≥ 0]| ≤ O d (ε). By Lemma 31, we have thatP [p(X) ≥ 0] ≥ P p δ ( X) ≥ δ -δ.Since p δ is multilinear, we can apply Proposition 20 to p δ -δ to get that We now want to prove Lemmas 32 and 33 that show that the construction of X respectively Ŷ preserve the assumptions on the distribution. The latter lemma is also proved in [21, Lemma 15] , but we include it here for completeness. Lemma (Restatement of Lemma 32). Suppose X approximately matches the moments of N (0, I n ) up to degree k and slack η. Then, X approximately matches the moments of N (0, I nN ) up to degree k and slack η = (2k) k/2 η.P [p(X) ≥ 0] ≥ P p δ ( Ŷ ) ≥ δ -O d (ε)Proof. For a multi-index α, let c α be the α-moment of a Gaussian. We want to show that E Xα -c α ≤ η for any α with |α| ≤ k. We can compute the following, by writing Z i,j = Z(i) j , E Xα -c α = E   n i=1 N j=1 Xαi,j i,j   -c α = E   n i=1 N j=1 1 √ N X i + Z i,j αi,j   -c α = E   n i=1 N j=1 αi,j r=0 α i,j r 1 √ N X i r Z αi,j -r i,j   -c α = E   β≤α α β X √ N β Z α-β   -c α = β≤α α β E X √ N β E Z α-β -c α .In the second step we used the definition of X and in the last step, we used that Z and X are independent. Now,E X √ N β -E Y √ N β ≤ ηsince X matches the moments of N (0, I n ) up to degree k and slack η. Thus, we getE Xα -c α = β≤α α β E X √ N β E Z α-β -c α ≤ β≤α α β E X √ N β -E Y √ N β E Z α-β + β≤α α β E Y √ N β E Z α-β -c α ≤ η β≤α α β E Z α-β + β≤α α β E Y √ N β E Z α-β -c α = η β≤α α β E Z α-β + |E [Y α ] -c α | = η β≤α α β E Z α-β .The second-to-last step is the same computation from above but backwards (note that the moments of Z ′ used for the construction of Ŷ are the same as those of Z used for the construction of X) and the last step used that Y is Gaussian and thus E [Y α ] = c α . We can furthermore computeE Xα -c α = η β≤α α β E Z α-β = η β≤α α β E Z β = η β≤α α β n i=1 E   N j=1 Z βi,j i,j   ,where the third step uses that the Z i,j are independent for different i. We now get that, using Fact 42,E   N j=1 Z βi,j i,j   ≤ |β i,• | |βi,•|/2 ≤ √ k |βi,•| .Thus, continuing with the above, we getE Xα -c α = η β≤α α β n i=1 E N i=1 Z βi,j i,j ≤ η β≤α α β n i=1 √ k |βi,•| = η β≤α β α ( √ k1) β = η( √ k + 1) |α| ≤ (2k) k/2 η = η, where 1 is the all-ones vector. This completes the proof.Lemma (Restatement of Lemma 33). If Y ∼ N (0, I n ), then Ŷ ∼ N (0, I nN ).Proof. Since Ŷ is a linear transformation of the Gaussian vector (Y, Z ′ ), it is jointly Gaussian and thus to show the lemma, it is enough to show that the expectation of Ŷ is 0 and the covariance matrix is the identity.′ i,j = Z ′(i) j , we have for any i ∈ [n], j ∈ [N ] that E Ŷi,j = E 1 √ N Y i + Z ′ ij = 1 √ N • 0 + 0 = 0.Furthermore, for any i ∈ [n], j ∈ [N ] we have that, by independence of Y and Z ′ ,Var Ŷi,j = 1 N Var [Y i ] + Var Z ′ i,j = 1 N • 1 + 1 - 1 N = 1. For any i ∈ [n], j 1 ̸ = j 2 ∈ [N ] we get that Cov Ŷi,j1 , Ŷi,j2 = E 1 √ N Y i + Z ′ i,j1 1 √ N Y i + Z ′ i,j2 = E 1 N Y 2 i + E 1 √ N Y i Z ′ i,j1 + E 1 √ N Y i Z ′ i,j2 + E Z ′ i,j1 Z ′ i,j2 = 1 N + 0 + 0 - 1 N = 0.i 1 ̸ = i 2 ∈ [n], j 1 , j 2 ∈ [N ] we have that Cov Ŷi1,j1 , Ŷi2,j2 = 0 by independence of Ŷi1,j1 = Y i1 + Z ′ i1,j1 and Ŷi2,j2 = Y i2 + Z ′ i2,j2 for i 1 ̸ = i 2 .Thus, as argued in the beginning, this shows that Ŷ ∼ N (0, I nN ) and completes the proof.Finally, we want to provide the details of the missing parts in the proof of Lemma 31 about the existence of the polynomial p δ . For this, it remains to prove Lemmas 34 and 35, which we restate below. First, recall our definition of δ ′ in (13) .δ ′ := min δ 2dn , Θ d δ d+1 n 3d/2 = Θ d δ d+1 n 3d/2 . (restatement of 13)In the proof of Lemma 31, we then used the following lemma that allows to replace a factor X ℓ i by a multilinear polynomial in the new variable X.Lemma (Restatement of Lemma 34). Let δ ′ > 0. Let i ∈ [n] and ℓ ∈ [d]. Assume that each of the following conditions holds with probability 1 -δ ′ d N j=1 Xi,j √ N ≤ 1 δ ′ (restatement of 10) N j=1 Xi,j √ N 2 -1 ≤ δ ′d+1 (restatement of 11) N j=1 Xi,j √ N a ≤ δ ′d+1 ∀ 3 ≤ a ≤ d. (restatement of 12)Then, there is a multilinear polynomial in Xi,j that is within O d (δ ′ ) of X ℓ i with probability 1 -δ ′ .We prove this lemma below. Before that, we want to prove Lemma 35 that states that we can use the above lemma for our choice of δ ′ . Lemma (Restatement of Lemma 35). Let δ ′ as in (13) . Assuming η ≤ δ O d (1) n -Ω d (1) k -k , there is a choice of N (independent of i or ℓ) such that (10), ( 11) and (12) hold, each with probability 1 -δ ′ d .The proof of this lemma is a combination of the following lemmas. Lemma 45. Assumingη ≤ 1 δ ′ d -1 N (2k) k/2 , we have with probability 1 -δ ′ d that N j=1 Xi,j √ N ≤ 1 δ ′ . Lemma 46. Assuming η ≤ δ ′2d+3 d -2 N 3(2k) k/2 , we have with probability 1 -δ ′ d that N j=1 Xi,j √ N 2 -1 ≤ δ ′d+1 .Note that for the above condition on η to be meaningful (we need η > 0), we also need to ensure thatN > 2d δ ′2d+3 . Lemma 47. Assuming η ≤ 1 (2k) k/2 and N ≥ 100d 2 δ ′2d+3we have for any 3 ≤ a ≤ d with probability1 -δ ′ d that N j=1 Xi,j √ N a ≤ δ ′d+1 .Using these three lemmas, we are now able to prove Lemma 35.Proof of Lemma 35. It remains to argue that there is a choice of N such that the condition on η in the lemma statement ensures that the conditions on η in Lemmas 45, 46 and 47 are satisfied. We argue below that the following choice of N is enough, which will complete the proof,EQUATIONFor Lemma 45, we need η ≤1 δ ′ d -1 N (2k) k/2. Plugging in the value of N and δ ′ , it is enough for η to satisfy (note that 1δ ′ d -1 ≥ 1 since δ ′ is small) η ≤ O d δ O d (1)n Ω d (1) (2k) k/2 , which holds since by assumptionη ≤ δ O d (1) n -Ω d (1) k -k . For Lemma 46, we need η ≤ δ ′2d+3 d -2 N 3(2k) k/2and N > 2d δ ′2d+3 . The latter is clearly satisfied by the choice of N as in (23) . For the former, plugging in again the values of N and δ ′ , it is enough for η to satisfyη ≤ O d δ O d (1) n Ω d (1) (2k) k/2 , which again holds since η ≤ δ O d (1) n -Ω d (1) k -k .For Lemma 47, we need N ≥ 100d 2 δ ′2d+3 and η ≤ 1 (2k) k/2 . The former is again directly satisfied by the choice of N . Furthermore, also the latter is true, again since we assume η≤ δ O d (1) n -Ω d (1) k -k .Next, we want to prove Lemmas 45, 46 and 47.Proof of Lemma 45. Using Markov's inequality, we get thatP   N j=1 Xi,j √ N > 1 δ ′   ≤ E 1 N N j=1 Xi,j 2 1 δ ′ 2 .Since, X approximates the moments of N (0, I nN ) up to degree k and error η, we can compute the above expectation as followsE      N j=1 Xi,j   2    = |α|=2 2 α E Xα i,• ≤ ηN (N -1) + (1 + η)N = ηN 2 + N.Here, we used that the expectation E Xα i,• is at most η if some α j = 1 (for such α the expectation of N (0, I nN ) is 0) and at most 1 + η otherwise (since the expectation of N (0, I nN ) is 1 for such α). Thus, we get thatP   N j=1 Xi,j √ N > 1 δ ′   ≤ (ηN + 1)δ ′2 ≤ δ ′ dsince by assumption we have that η = (2k) k/2 η ≤ 1 δ ′ d -1 N .Proof of Lemma 46. We again use Markov's inequality to getP   1 N   N j=1 X2 i,j   -1 > δ ′d+1   ≤ E 1 N N j=1 X2 i,j -1 2 δ ′2d+2 .We are thus interested inEQUATION. We can expand this as followsE      N j=1 X2 i,j -1   2    = |α|=2 2 α E X2 i,• -1 α .If some α j = 1, then the expectation will be, for somej 1 ̸ = j 2 ∈ [N ], E X2 i,j1 -1 X2 i,j2 -1 = E X2 i,j1 X2 i,j2 -E X2 i,j1 -E X2 i,j2 + 1 ≤ 1 + η -(1 -η) -(1 -η) + 1 = 3η.As for the proof of Lemma 45, this is true since the corresponding Gaussian moments are all 1. If no α j = 1, we getE X2 i,j -1 2 = E X4 i,j -2E X2 i,j + 1 ≤ 3 + η -2(1 -η) + 1 = 2 + 2η,since the second and fourth moment of a Gaussian are 1 and 3 respectively. Summarized we get thatE      N j=1 X2 i,j -1   2    ≤ N (2 + 2η) + N (N -1)3η = 2N -N η + 3N 2 η.Together with the above we get thatP   1 N   N j=1 X2 i,j   -1 > δ ′d+1   ≤ 2N -N η + 3N 2 η N 2 δ ′2d+2 ≤ 2 N + 3η δ ′2d+2 ≤ δ ′ d ,since by assumption we have that η = (2k) k/2 η ≤ δ ′2d+3 d -2 N 3 .Proof of Lemma 47. For any 3 ≤ a ≤ d, similar to before, we compute using Markov's inequalityP   1 N a/2 N j=1 Xa i,j > δ ′d+1   ≤ E 1 N a/2 N j=1 Xa i,j 2 δ ′2d+2.We thus need to boundEQUATION. We get E      N j=1 Xa i,j   2    = |α|=2 2 α E Xa•α i,• ≤ N 2 (P   1 N a/2 N j=1 Xa i,j > δ ′d+1   ≤ N 2 (2a) a N a δ ′2d+2 = (2a) a N a-2 δ ′2d+2 .We have for any a ≥ 3 that ((2a) a ) 1 a-2 ≤ 100a and thus we get thatP   1 N a/2 N j=1 Xa i,j > δ ′d+1   ≤ (100a) a-2 N a-2 δ ′2d+2 = 100a N a-2 1 δ ′2d+2 ≤ δ ′2d+3 d a-2 1 δ ′2d+2 ≤ δ ′ dIn the third step we used that by assumption we have that N ≥ 100d 2 δ ′2d+3 and d ≥ a. In the last step, we then used that a -2 ≥ 1, together with δ ′2d+3 d ≤ 1.Finally, it remains to prove Lemma 34.• The factors of variability that the error bars are capturing should be clearly stated (for train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: Since this paper discusses theoretical results only and does not contain experiments, this question does not apply.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The research conducted in this papers conforms with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This paper discussed general theoretical results and algorithms and has as such no immediate societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] .Justification: Since this paper discusses theoretical results only and does not contain experiments, this question does not apply.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] .Justification: Since this paper discusses theoretical results only and does not contain experiments, this question does not apply.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] .Justification: Since this paper discusses theoretical results only and does not contain experiments, this question does not apply.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: Since this paper discusses theoretical results only and does not contain experiments, this question does not apply.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: Since this paper discusses theoretical results only and does not contain experiments, this question does not apply.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.In particular, achieving a runtime in poly(n, 1/ε) is likely not possible. We note that such runtimes can be achieved in the weaker model where one accepts a loss of O(opt) + ε (vs. opt + ε in the model we consider)[1].Note that this even excludes proving an agnostic learning guarantee w.r.t. N (0, In) using this approach.Technically, density functions are defined only up to measure-zero sets. Therefore, one should read statements of the form 'w(x) ≥ . . . for all x ∈ . . .' as only holding a.e. throughout. 
 
 Appendix:  


Decision: Testable learning is a recently proposed learning paradigm where algorithms are required to "check" the assumptions they need to make on data to succeed, instead of taking them on faith. This paper shows how to testably learn a polynomial threshold function that succeeds with high probability when the input data is Gaussian (or passes the check), extending previous results from the agnostic setting. The reviewers generally agreed that this is an interesting and nontrivial theoretical result which goes beyond the prior work in this area. I recommend acceptance.

Reviews: review: paper_summary: paper_summary: This paper investigates testable learning of polynomial threshold functions (PTFs) with respect to the standard Gaussian distribution. The authors extend previous work on testable learning of halfspaces to show that PTFs of arbitrary constant degree can be testably learned up to excess error \epsilon in time n^poly(1/\epsilon),  matching the best known guarantees in the agnostic model. The key technical contribution is showing that distributions which approximately match the moments of a Gaussian up to degree poly(1/\epsilon) fool constant-degree PTFs.
strength_weakness: strength_weakness: - It is not clear how important the problem of testable learning for PTFs is and if the results and/or techniques have applicability to other learning theory problems.
questions: questions: - It seems like the testable learning setting is similar to the samples coming from a distribution close to the distribution D in some sense? Is there any model of learning theory that explicitly studies this?
- Do you see a path to improving the sample complexity to polynomial in both n and 1/\epsilon, rather than n^poly(1/\epsilon)?
- The authors have looked at Gaussian distribution in this work. What other distributions could this result be extended to?
- Can you provide intuition for why the runtime dependence on d is so much worse than in the agnostic model? Do you believe this gap is inherent or an artifact of the analysis?
- Did the authors look into getting any sort of lower bounds for this problem?
limitations: limitations: Yes
paper_summary: paper_summary: The authors study the problem of testing polynomial threshold functions in the agnostic setting in the testable learning paradigm. They present a testable learning algorithm that matches with the asymptotic bound (in terms of n) known for agnostic learning
strength_weakness: strength_weakness: The dependence on epsilon and the degree is very bad. This makes the results completely useless is practice. In fact the degree os the polynomial on the exponent is exponentially dependent on d.
questions: questions: Can you please argue why the dependence on d is so bad and is there possibility of improving it. Can a better bounds be obtained for smaller d, like d=2,3.
limitations: limitations: NA
paper_summary: paper_summary: This paper studied the problem of testably learning polynomial threshold functions (PTFs). The authors aimed to answer the question of whether PTFs are qualitatively harder to learn in the testably learning model, compared to the agnostic learning model. The authors answered the question in the negative, showing that the degree-d PTFs can be testably learned up to $\epsilon$ with respect to the standard gaussian in time and sample complexity $n^{poly(1/\epsilon)}$, which qualitatively matches the $n^{O(d^2/\epsilon^4)}$ sample complexity of agnostic learning degree-d PTFs. To prove the above result, the authors linked testable learning with distribution fooling, building upon previous results on polynomial approximations. The authors also showed that it is impossible to testably learn PTFs with the techniques from [RV23].
strength_weakness: strength_weakness: 1. Though the final sample complexity is $n^{poly(1/\epsilon)}$, the $poly(1/\epsilon)$ is of order $\epsilon^{-7^d}$, in other words, it is substantially worse than agnostic learning in terms of the order of $1/\epsilon$. It might be too harsh to say this is a serious weakness of this paper, as this is the first paper that provided these kinds of complex results; I think it would be an interesting future work to reduce the order of $1/\epsilon$ that is truly comparable to agnostic learning.
questions: questions: see weakness above.
limitations: limitations: the authors have addressed the limitations properly.
paper_summary: paper_summary: Background: Agnostic learning is a well-studied framework that models learning when no function is some hypothesis class F describes the data perfectly. Specifically, the agnostic learning framework requires the learning algorithm to give a hypothesis whose classification error is at most opt+$\epsilon$, where opt is the best prediction error among all hypotheses in the class F. 

Almost all existing agnostic learning algorithms are distribution-specific, i.e. they assume the examples are drawn from some distribution, for example a Gaussian distribution. 

A distribution-specific agnostic learning algorithm lacks in reliability, because it is allowed to output an extremely poor classifier if the examples do not come from e.g. Gaussian (or some other assumed distribution). Yet, fully eliminating such assumptions is shown to be impossible for many basic function classes (based on well-established cryptographic assumptions). 

Testable learning is a framework that aims to mitigate the above mentioned limitation, by allowing the algorithm to abstain on a specific dataset if the examples do not come from the assumed distribution. Overall, this allows a user to be confident that the classifier indeed has error of at most opt+$\epsilon$, as required by the agnostic learning framework. Testable learning has been a focus of many works in recent years (see the paper for references).

The paper studies testable learning of polynomial threshold functions (PTFs) under the Gaussian distribution. I.e. the function class F considered in this work consists of functions of the form sign$(p(x))$, where p is a degree-$d$ polynomial.  The work in n dimensions, with accuracy parameter $\epsilon$, the paper gives an algorithm for testable learning of constant-degree PTFs with a run-time of $n^{poly(1/\epsilon)}$}. 

The paper is based on the moment-matching framework of [Gollakota, Klivans, Kothari ‘23], and shows that the direct approach used in [Vasilyan, Rubinfeld ‘23] to handle linear threshold functions cannot be extended to PTFs.

In order to apply the moment-matching framework of  [Gollakota, Klivans, Kothari ‘23], the paper shows that PTFs are “fooled” by distributions whose low-degree moments are close to Gaussian moments. To do this, the paper expands on the approach of [Kane ‘11] that proves a less general statement that PTFs are “fooled” by distributions for which the marginal of every k coordinates equals to the k-dimensional Gaussian. The proof first first considers multilinear PTFs, and then reduces the case of general PTFs to that of multilinear PTFs.
strength_weakness: strength_weakness: -The run-time dependence of the algorithm on the degree d of the PTF can conceivably be sub-optimal. As explained on page 12, the run-time is $(n \epsilon)^{O_d(\epsilon^{-4d7^d})}$, whereas it is conceivable that this run-time could potentially be improved in the future to $(n \epsilon)^{poly(d/\epsilon)}$
questions: questions: The paper mentions that the analysis does not require to extend the Carbery-Wright inequality to distributions whose low-degree moments match those of the Gaussian. Could you give some more high-level intuitive explanation for why this is the case?
limitations: limitations: I think that the limitations are discussed adequately
paper_summary: paper_summary: This paper studies testably learning an n-dimensional Polynomial Threshold function using a reduction proved in a previous work called fooling. The authors give an analysis of a construction of fooling multilinear PTF and then further for fooling arbitrary PTF.

The paper completes itself with proof that push-forward cannot learn PTF and that fooling is the best they can have.
strength_weakness: strength_weakness: The last part of the paper shows that push-forward cannot learn PTF seems very interesting, but it seems hard for me to determine how significant the contribution is from the analysis of fooling multilinear PTF.
questions: questions: I am wondering what are the original techniques the authors want to emphasize. Like using Taylor expansion to bound additional error terms or reducing PTF to multilinear PTF or anything else? I am wondering if the authors can emphasize a bit more.
limitations: limitations: N/A

Comments: comment: Thanks for your detailed response.
Thank you for your response. I think this paper will be worth reading for people interested in testable learning and more enjoyable if the authors improving their writing in the final version in the way they claimed in this rebuttal. I raised my score to 7.
Thank you for your response.