Testably Learning Polynomial Threshold Functions
Authors: Lucas Slot
Stefan Tiegel
Manuel Wiedmer
Venue: NeurIPS 2024 poster (2024)
Keywords: testable learning
polynomial threshold functions
agnostic learning
fooling using approximate moment matching
Primary area: learning_theory

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.

Testably Learning Polynomial Threshold Functions
Lucas Slot Department of Computer Science ETH Zurich lucas. slot@inf ethz. ch
Stefan Tiegel Department Computer Science ETH Zurich stefan tiw.eleingeennn ethz. ch
Manuel Wiedmer
Department of Computer Science
ETH Zurich
manuel wwwdwerwinf.f..mmmm wtw.f.ethzcccmm ch
Abstract
Rubinfeld & Vasilyan recently introduced the framework of testable learning as an extension of the classical agnostic model. It relaxes distributional assumptions which difficult to verify conditions that
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 ddistributionsspecine whether there 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 arbitrary constant degree can be testably learned up excess errоr > in time pool((1/e), 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 poly(1/e moments of the standard Gaussian fool constant-degree PTFs (up to error e).
agnostic model. In this work, we ask
secondary result, we prove that direct approach to show testable learning (without fooling), which was successfully used for halfspaces, cannot work for PTFs.
Introduction
The PAC learning model of Valiant [30] has long served test-bed study which learning tasks can be performed efficiently and which might be computationally difficult. One drawback of this model is that it inherently noiseless. In order capture noisy learning tasks, the following extension, called the agnostic model, has been introduced [19, 24]: Let F be class of boolean functions and let D Djoint be an (unknown) distribution over example-label-pate in X' {=1} Typically, = {0, 1)" or R=.
As input, we receive iid samples from Djoint- For small O, our task is to output classifier (not necessarily in F) whose loss L(f, Djoim)) = ((r,:))D,.in (f(x) # 2) is at most opt + where opt = inf JEF L(f.Djoinl D. The parameter opt thus indicates how "noisy" the instance is. We say that algorithm agnostically learns F up 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 achieves error close that of the best function in F even without knowing what distribution the data came from.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Efficient learning and distributional assumptions. We are interested in understanding when agnostic learning can be performed efficiently. Unfortunately, efficient learning is likely im- possible without making assumptions on the distribution Pjoint even for very simple function classes F. For instance, consider the class Fis of halfspaces, i.e., boolean functions of the form f(z) Sign((u,20 .) 0). Then, even if there exists a halfspace achieving arbitrarily small error, it is widely believed that outputting an f that performs better than random guess in the agnostic model takes at least super-pol nuper-polynomial time if no assumptions are made on Djoin. [8, 29]. To find efficient algorithms, one therefore has to make such assumptions. Typically, these take the form of assuming that the marginal Dx of joint over the examples X' belongs to a specific family of distributions.
Definition 1 (Agnostic learning with distributional assumptions). Let O. A learner A agnostically learns F with respect to 'D up to error if. for any distribution Pjoint on X' x {+1] whose marginal Dx on X is equal D, given sufficient samples from Djoint. it outputs with high probability function f X + {=1} satisfying L(f, Djoint) S. opt(F, (join))) +
For example, under the assumption that Dx is standard Gaussian, we can find f such that L(f, Pjoint) S opt(FHs, Pjoint) + in time 001/2)) [20, 11]. This runtime is likely best- possible [12, 29, 13].' Efficient learning still possible under weaker assumptions on xx. 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 guar- antees are inherently difficult to obtain from finite (small) sample. Furthermore, approaches like cross-validatin (i.e., computing the empirical error of f on 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.
1.1 Testable learning.
To address this limitation, Rubinfeld & Vasilyan [28] recently introduced the following model, which they call testable learning: First, they run 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 > O. A tester-learner pair (T,A) testably learns F with respect to a distribution 'D on X up to error E if. for any distribution Djoint on X x {+1), the following hold
1. (Soundness). If samples drawn from Djoint are accepted by the tester TT with high probability, then the learner A must agnostically learn F w.r.t. Dyoint up to error e.
2. (Completeness). If the marginal of Djoint on X is equal to D, then the tester must accept samples drawn from D Djoine with high probability.
Soundness tells us that whenever testable learning algorithm outputs a function f. this function achieves low error (regardless of whether Djoine satisfies any distributional assumption). On the other hand, completeness tells us testable learners are no weaker than (distribution-seccit in the sense that they achieve the same error whenever D Pjoint actually satisfies our assumptions (i.e.. whenever this error can in fact be guaranteed for the agnostic Icarner). The testable model is thus substantially stronger than the agnostic model with distributional assumptions.
agnostic ones,
Which function classes can be learned testably? A natural question is whether testable learning agnostic learning.
comes at an additional computational cost compared to (distribution-specine X' RR. Following [28, 15),
We focus the setting where D is the standard Gaussian consider the following simple tester: Accept and only if the empirical moments up to degree & of the input distribution (approximately) match those of D. This tester satisfies completeness as the
In particular, achieving runtime in poly (n, 1/c) is likely not possible. We note that such runtimes can be achieved in the weaker model where one accepts loss of O(opt) +e (vs. opt + e in the model we consider) [1].

---

empirical moments of Gaussian concentrate well. Using this tester, Rubinfeld & Vasilyan [28] show that halfspaces can be testably learned in time n o(0()=))) Their runtime guarantee was improved to (()==") 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 (0(m) samples (and hence also time) [28], whereas agnostically learning them only takes subexponential time 20(v"), see [25]. The relation between agnostic and testable learning is thus non-trivial, depending strongly on the concept class considered.
1.2 Our contributions
In this work, continue to explore testable learning and its relation the agnostic model. We consider the concept class of polynomial threshold functions (short PTFs). degree-d PTF is a function of the form [(x) = sigu(p(æ)), where p polynomial of degree 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 otd /=*) [22]. which is polynomial in for any fixed degree d E N and error > They are thus significantly easier to learn 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 E N. Then, for any > O, 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 pol)y(1/e)
Theorem 3 is the first result achieving efficient testable learning for PTFs of any fixed degree d (up to constant error E >> 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 certain natural approach to prove testable learning guarantees for PTFs. In particular, we show 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 rumning 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 PTFSs 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 (f (x2) in the SQ-model [12], and at least n Mid 9/2² -) for any 3 0 under a cryptographic hardness assumption [29].
1.3 Previous work
The two works most closely related this paper are [28, 15]. Both rely the following high- level strategy. A standard result [20] shows that one can agnostically learn a concept class F w.r.t. a distribution D in time ((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 degree-k polynomial h such that Ex-D [lh(X)= - [()]] < e. This result can be extended to the testable setting, but now one needs good low-degree Li-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 FF 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= FHS is the class of halfspaces and D [O, I,),, these approximators exist for k 0(1/e*), leading an overall running time of n 0(1/=*) for their testable learner. Their approach consists of two steps. First, they construct low-degree approximation q ss sign of the sign function in one dimension using standard
3

---

techniques. Then, for any halfspace f(x) sign( x)) 8), they set h(x) = q 2) exploiting concentration and cotceconnntnatioon properties of the push-forward under linear functions of distributions that match the moments of Gaussian, they show that h is a good approximation of Unfortunately, this kind of approach cannot work for PTFs: We formally rule 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.
0). By
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 emrrr >> 0 with respect to DD if, for all f F, it holds that [R [x()] - Ex-D/ [f(X] S &. Roughly speaking. the work [15] shows that, if any distribu- tion D'' which approximately matches the moments of 'D up to degree k fools F with respect to D, then can be testably learned in time n 0(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 (0, n.) Nevertheless, the authors of [15] show that (approximate) moment matching up to degree k Õ(1/E²) fools halfspaces with respect to (0, In). allowing them to obtain the aforementioned result for testably learning FHs- 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 d 2 PTFs can be testably learned under the uniform distribution over {0, 1)" (but these do not extend to learning over IR" 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 the error of the learner it is known how to construct tester-learner pairs with runtime (nly(n, 1/e) [16, 10]. These results have been extended to allow for the following stronger completeness condition: The tester has to accept, whenever Djoint is an isotropic strongly log-concave distribution [17].
2
Technical overview
2.1
Preliminaries
From here, we restrict the setting X' R" We let D be a well-behaved distribution on R"; usually D= = (0, In) is the standard Gaussian. For x E R." and a multi-index a E N", we write x² = I o. For & E N. we write NE = {a E N". Σi= a k).. We say a statement holds 'with high probability' if it holds with probability 2 0.99. The notation Os (resp. Ωd, 9a) hides factors that only depend on We now define the moment-matchin
tester introduced above.
Definition& 4 (Moment matching). Let k E N and n 2 O. We say distribution D' on Re approxi- mately moment-matcher 'D up to degree and with slack 1 if
EX~D [X*] EXwD [X*]] S " Definition 5. Let k E N and 1) 2 0. The approximate moment mattetnn tester TAMM = TAAM (k. m) for a distribution DD accepts the samples (x(1), ,())...... (x(m), z(m)) E Rn x {+1} if, and only if.
E
E Ex~D [X
1
(x ())
In VaEN-
That is, TAMMa(K, n) accepts if and only if the moments of the empirical distribution belonging to the samples {1) } match the moments D D up to degree k and slack 1. Note that TaMaa requires time at most O(m - n
) to decide whether to accept set of m samples.
The tester TAMA does not take the labels of the samples into account. In general, for testers T which depend only on the marginal D of Djoint on RR,,, we say that T accepts distribution D' on R if accepts samples drawn from D' with high probability (regardless of the labels).

---

2.2 Review of existing techniques for testable learning
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-approximatee by low-degree polynomials in the following sense.
Theorem ((20). Let k E N and > Suppose that, for any I E F, there exists polynomial of degree k such that
EX-D [1(X)- - f(X)I E.
Then, can be agnostically learned up error in time and sample complexity n (())) /poly(E).
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 needs good approximation w.r.t. all distributions accepted by the proposed tester.
Theorem 7. Let sample complexity T. Suppose that, for any f E F, and for any DD' accepted by T, there exists polynomial h of degree l such that
and E > O. Let T be tester which accepts D and which requires time and
EXdD [I((X) - f(x)) S..
Then, FF can be testably learned up to error E in time and sample complexity + ok) /poly(s).
The takeaway 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 (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. AN In)) [20, 25, 22].
Testable learning via direct approximation. In the testable setting, it is not sufficient to approxi- mate with respect to D alone, and so one cannot rely directly on any of its special structure. In [28), the authors overcome this obstacle get testable learning guarantees for halfspaces w.r.t. D = NO, I,) by appealing to more basic properties of the distributions DD' accepted by their tester. Their approach roughly follows. First, they use standard results from polynomial approximation theory to find a (univariate) polynomial which approximates the sign-function well on the interval [-1, 1]. For halfspace fx) sign((r: x) - 0), they consider the approximator h(x) g((v, x) 0), which satisfies
Ex-r [l((X) - [(X)] = -YYDD Il(( - sigu(Y)l]
Here, D the (shifted) projection of DD' onto the line span(v) C R That is, Y (v. X) Then, for carefully chosen N and 1) > O, they show that for any D' accepted by TAMM n). the distribution D', satisfies certain concentration and anti-concentration properties, meaning essen- tially that D' D a is distributed somewhat uniformly on [-1, As q approximates the sign-function on [-1, 1, 1], they may conclude that Ey-D',, [lq(Y) (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(z) = sign(p(æ)), one could consider the approximator h(z) ((((x)). However, as we show below in Section 2.4, this approach cannot work when deg(p) 2 6. Instead, we will rely 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 O. We say distribution D' on R. fools F W.E.. D up to error e, if. for all f E F. we have EY-D [f(Y]] - EX-D [f(x)] S.
The main result of [15] shows that fooling implies testable learning when using approximate moment- matching test the distributional assumptions. It forms the basis of our proof of Theorem 3.
5

---

Theorem 9 ([15, Theorem 4.5)). Let k. m E N and E. > 0. Suppose that the following hold:
1. Any distribution DD' whose moments up to degree k match those of with slack 11 fools F w.r.t. DD up to error e/2.
2. With high probability over mn samples from 'D the empirical distribution matches moments of degree at most l with 'D up to slack 1/.
Then, using the nooent--machiing tester T = TAMM(KK 11), we can learn F. testably with respect to DD up to error e in time and sample complexity m + n n(kk)
Remark 10. When D = -O, In) is the standard Gaussian, then the second condition in Theorem 9 is satisfied for m ((2kn)* 17 ?), see also Fact 36.
The primary technical argument in the proof of Theorem 9 in [15] is an equivalence between fooling and type of low- oewdegree polynomial approximation called sandwiching. Compared Theorem 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 11, l/2 that satisfy hn S ʃ S h2 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, suffices to show that distributions D' which approximately match the moments of /O I,, fool the concept class of PTFs. This is our primary technical contribution (see Proposition 12 below). 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- k-independent standard Gaussian, meaning the restriction of D' to any subset of k variables has distribution (o, Ix). Then, D' fools degree-d PTFs w.r.f. (0, I.) up error 0 long k k(d, s) is large enough.
Theorem 11 applies to class of distributions that is (far) more restrictive than what need. First, note that k-independent Gaussians match the moments of (0, In) up to degree is 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, have no information on its moments of high degree even if they depend on most i variables. These two distinctions cause substantial technical difficulties in our proof of Proposition 12 below.
2.3 Overview of the proof of Theorem 3: testably learning PTFs
As we have seen, in order to prove Theorem 3, it suffices to show that approximately moment- matching distributions fool PTFs. We obtain the following.
Proposition 12. Let > Suppose that D' approximately matches the moments of (0, In) up to degree k and slack n, where l 2 (la(s-AdTT)) and 1 S n-Ba(k) RRa(k)) Then, 'D' fools the class of degree-d PTFs w.r.t (O, In) up to error e/2 That is, for any f E FPTF, we then have
By= [f()] EXnD [f(X]] S e/2.
(1)
In 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 [21] (which considers k-independent Gaussians) remains valid for the larger class of distributions that approximately match the moments of Gaussian.
2.3.1 Fooling multilinear PTFs
Let f(x) sign(p(=)), where is multilinear polynomial. Our goal is to establish (1) for under the assumptions of Proposition 12. We will follow the proof of Kane [21] for Theorem 11, which proceeds as follows. Let D' be k-independent Gaussian. First, Kane constructs degree-k polynomial approximation of f, satisfying
Ey~,(,, [k(Y)] v Ey~N((,L.) [F(),, and,
(2)
E Ex-D [hXX)] = Ex [f(x).
(3)

---

Since the moments of D' are exactly equal to those of (0 I,) up to degree k, we have
E(.,()) [k(Y]] = ExwD [h(X)], We may then conclude the fooling property for D' (cf. (1)):
By~ (S(Y) R Ey-N(O.) [h(Y) = Ex-D [x(x) R Ex-D []()].
As we see below, Kane relies 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 i and slack 17. 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, 1 [N( * Ex [h( [ 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 low- degree approximation l 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 that f sign(p) can be decomposed as f(z) = F(P(x)), where F is again PTF, and P = (P:) is vector of multilinear polynomials of degree d, whose moments Eyto. [P:(Y)) are all at most Oz(ve)s. Note that these bounds are much stronger than what we would get from standard arguments (which would only yield Ey=A(u...) (P(())) I Oa(VE)dt). 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 * p of F with a carefully chosen smooth function p. Then, we set h(x)) = T(P(2)), where T is the Taylor approximation of F of appropriate degree (see Appendix A.1.)). Intuitively, taking the Taylor expansion yields good approximation as the (Gaussian) moments of the P, 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) 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. is large, which we do using Markov's inequality. Then, we need to show bound on the moments of P: under D' (recall that the structure theorem only gives a bound on the Gaussian moments). Using bounds on the coefficients of the P., we are able to do this under a mild condition on v) (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 lew-degree approximation h, we have Ey [h(Y]] ] ~ Ex=> [f(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 W I,) up
to degree i exactly. Under aaapproximate moment matching, we could say that
Ly [h(Y)] Ex-D [h(X]] <7-1//li
where |/hl| is the I-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 form Ey-,,,, [P()) - EX-D= [P(X)=]] Combining these bounds yields an estimate on the difference [By~A((.12) [N(Y]] Ex-D [/(X)]], which lets us conclude (1).
Going into more detail, the LHS of (4) is equal to the inner product (4, u)) between the vector (. = (1x)) of coefficients of T and the vector u = (u.)), where u,, = Ey=,N(o.L.) (P(Y))) - EX~D [P(X)9) This can be viewed as a 'change of basis' x - P(x).. Then, (4) can bounded by ||u||sc - ||t//2, where [| = max. |ua|- The coefficients la of 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]| < kOa(k) (see Lemma 27). Finally, for any |al S k. it holds that
Ey EY [P(Y)*] EX-D [P(X)*]| S n sup (11131)) |al < n lold S v) Oz(k))
see Fact 22. Putting things together, we get that
Ey- [b(Y)] - Ex-DV [h(x)] = || || S n 02(0 0n(M) < e/2.
using the fact that 77 S n -Ra(k) (Ba(A)) and k > 1/E for the last incquality.
7

---

2.3.2 Fooling arbitrary PTFs
Now, let f(x) = sign(p(z)) be an arbitrary PTF. As before, we want to establish (1). Following [21], the idea is reduce this problem to the multilinear case as follows. Let Y NN0 In) and let X be a random variable that matches the moments of Y up to degree k and with slack 1). For N E N to be chosen later, construct new random variables X and Y, and multilinear PTF f = sign(f), all in -V variables, such that Y NO, Lan), & matches moments of Y up to degree k with slack f) and
(5) Assuming f is not much bigger than 1), and the approximation above sufficiently good, we may then apply the result of Section 2. to f to conclude (1) for f. Our construction of X, Y and f will be the same in [21]. However, with respect his proof, face difficulties. First, need to control the slack parameter i in terms y). More seriously, Kane's proof of (5) breaks in our setting: He relies the fact that X is k-independent Gaussian in his setting to bound high degree moments of X which depend on most variables. In our setting, we have no information on such moments at all (even if X matched the moments of VO, I,) up to degree l exactly).
By [S(]] Ex [s()]] |B 1/00) - [x())]]
Construction of X and Y. For i E [nt], let ( be an N-dimensional Gaussian random variable with mean O, variances 1/N and covariances -1/N, independent from X and all other 2('), We define X.3 == /./VN + z and set X (X.)). We define y analogously. This ensures that Y (O, J. Furthermore, given that X matches the moments of Y with slack 77, it turns out that X matches the moments of Y with slack r) = (2k)*/2 1). This follows by direct computation after expanding the moments of X in terms of those of X and of the Z see Lemma 32.
Construction of the multilinear PTE We want to construct a multilinear polynomial ş in n.N variables so that p(X) ~ p()). For å E RON write (p()) = Lig/////VN (ij//VN)iEM)) E IR". Since sp( ()(1)) = O holds deterministically, x(x)= = X. So, if we were to set ý = p sa, would satisfy ((8)= p(X). However, it would clearly not be multilinear. To fix this, we write p(p(()) = E., d, and replace each non-multilinear term An by multilinear one as follows: If the largest entry of a is at least three, we remove the term completely. If the largest entry of a is two, we replace the term by Aa where d,j = if aij = 1 and 0 otherwise. This is identical to the construction in [21]. Now, to show that pXX) v p ()) we need to bound the effect of these modifications. It turns out that it suffices to control the following expressions in terms of N:
X
0:
Σ
1
GEF
Σ
4i VN
e 3
N
For the b, and C,e., we can do so using slight modification of the arguments in [21]. For the a, however, Kane [21] exploits the fact that in his setting, X, is standard Gaussian for each fixed i E [m]. meaning the X 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, 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 moments of constant degree. By imposing stronger conditions on the hy c,e. 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 conclude (5) for f sign(p).
2.4 Impossibility result: learning PTFs via the push-forward
In this section, we show that the approach of [28] to prove testable learning guarantces for halfspaces w.r.t. the standard Gaussian cannot be generalized to PTFs. Namely, we show that in general, PTFs fx) = sign(p(z)) with dog(p) 2 3 cannot be approximated up to arbitrary error w.r.t. (N0, I,) by polynomial of the form h(z) q(p(z)), regardless of the degree of q. Importantly, we show
Note that this excludes proving an agnostic learning guarantee w.r.t. (0 1n) using this approach.
8

---

that this is the case even if one makes certain typical structural assumptions which only change the PTF f sign(p) on set of negligible Gaussian volume; namely that p square-free and that {p 2 0) C Rd 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 standard Gaussian distribution by which is defined by
Let p+, I,) be the push-forward of the
Py "y=pp.N(0...) (Y A] Px-N(o.L.) [X EX (ACR).
(6)
Note that, if h(x) = ()(x))) we then have
Ex~~((o11.) [I f(x)l = -y No (O, ll)(Y) signnY)|]
Finding a good approximator I of the form polynomial y which approximates the sign-function on I well under the push-forward distribution PO,((0, I.). In light of this observation, we are interested the following question: Let D be distribution on the real line. Is it possible to find for each >> 0 polynomial q such that Ey [l{(Y) - -igg [I] S E? This question is well-understood for distributions D whose density is of the form w-, (z) == C. exp(-Iai)
o p is thus equivalent to finding (univariate)
Y > O. Namely, when 7 2 1, these distributions are log-concayy and the question can be answered in the affirmative. On the other hand, when y < 1, they are oog-superlinear, and polynomial approximation of the sign function is not possible.
Theorem 13 (see, e.g. (20]). Let D be a log- log-concave distribution on TR. Then, for any & > 0 there exists a polynomial q such that Ey~D [I sign(Y)
(Y)l I] S E.
Definition 14. Let DD be distribution on I whose density function w satisfies
wi (x) 2 C (x) Vx E TR
for some 7 and C > Then we say D is log- superlerrl (LSL).
Theorem 15 (Bun-Steinke [6]). Let D be an LSL-distribution on R. Then there exists an >> 0 such that, for any polynomial 9, we have ED [Y sign(Y [Y)l >>>>
When p is of degree 1 (i.e., when f sign(p) defines a halfspace), the push-forward distribution D = PO, In) defined (6) is itself a (shifted) Gaussian. particular, 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(z) x². The density of P (0, 1) is -2/3 2/3 cxxp(-la|2//)) and so P0, 1) is log-superlinear.
given by wxx) C [ar]
Choice of description. The example p(z) = = 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 pi P2- Indeed, note that for such a polynomial, we have sign(p(z)) = sign(p2(x)) (x)) almost everywhere. Square-freeness plays
important role in the analysis of learning algorithms for PTFFs, see, e.g., [22, Appendix A]. It turns out that even if is square-free, the distribution P0 In) can still be log-superlinear, e.g., when p(x) = x x( - 1)(x 2). Note that, for this example, sign(p) (p) describes a non-compact subset of IR. This is crucial to find that P 1) is LSL. Indeed, if {p 2 0} C R were compact, then Pmax = supzeR p(x) < co, and so the density w of py, 1) would satisfy w(x) 0 for all x > Pmax- In particular, w would not be logesuper,. One could therefore hope that assuming {p 2 0} is compact might fix our issues. This assumption is reasonable as {p 2 0} can be approximated arbitrarily well by compact set (in terms of Gaussian volume). On the contrary, we show the following.
Theorem 16. There exists square-free polynomial p. so that tp > 03 C R is compact, but for which there exists s > so that, for any polynomial q, E. Ex=N(())) [l((((X) - sigu(p(X)))
To establish Theorem 16, we prove a 'one-sided' analog of Theorem 15 in Appendix B. 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 that the densities in our result need only to have a single heavy tail. However, this tail
must be 'twice as heavy' (y < 1/2 vs. 7 < 1). We emphasize that [6] does not cover compact PTFs.

---

Definition 17. Let 'D be distribution on IR whose density function w satisfies
w(x) 2 C wy (2) Yx E
for some 7 < 1/2 and C O. Then we say D is one-sided log-superlineur,
Theorem 18. Let DD be a one-sided LSL-distribution R. Then there exists an & > 0 such that, for any polynomial 4, we have Ey-D
(y-rD1y(()) [l (Y- - sign(Y)] > 8.
Proof of Theorem 16. suffices find square-free polynomial p for which {p 0} is compact, and the push-forward distribution P (0,, 1) is one-sided LSL. A direct computation shows that
p(z) = = (z (x (x - 4) 5)
meets the criteria, see Appendix B.2 for details.
Acknowledgments
We thank the anonymous reviewers for their valuable comments and suggestions. We thank Arsen Vasilyan for helpful discussions. This work is supported by funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 815464).
References
[1] Pranjal Awasthi, Maria Florina Balcan, and Philip M. Long. "The power of localization for efficiently learning linear separators with noise". In: J. ACM 63.6 (2017), Art. 50, 27. ISSN;
[2] Louay M. J. Bazzi. "Polylogarithmic independence can fool DNF formulas". In: SIAM J. Compur. 38.6 (2009), pp. 2220-2272 ISSN: 0097-5397,1095-7111
[3] Richard Beigel. "The polynomial method in circuit complexity". In: Proceedings of the Eighth Annual Structure Complexity Theory Conference (San Diego, CA, 1993). IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, pp. 82-95. ISBN: 0-8 1-8186-4070-7.
[4] Mark Braverman. "Polylogarithmic independence fools AC circuits". In: J. ACM 57.5 (2008). ISSN: 0004-5411.
[5] Jehoshua Bruck and Roman Smolensky. "Polynomial threshold functions, AC functions, and spectral norms". In: SIAM J. Comput. 21.1 (1992), pp. 33-42. ISSN: 0097-5397.
[6] Mark Bun and Thomas Steinke. "Weighted polynomial approximations: limits for learning and pseudorandomness' In: Approximation, randomization, and combinatorial optimization. Algorithmss and techniques. Vol. 40. LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wademn, 2015, pp. 625-644. ISBN: 978-3-93999 778-3-9398977-8-77
[7] Anthony Carbery and James Wright. "Distributional and 7,9 norm inequalities for polynomials over convex bodies in R In: Math. Res. Lett. 8.3 (2001), pp. 233-248. ISSN: 1073-2780.
[8] Amit Daniely. "Complexity theoretic limitations on learning halfspaces". In: STOC' Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. ACM,
New York, 2016, pp. 105-117. ISBN: 978-1-4503-4132-55
[9] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola. "Bounded independence fools halfspaces".. In: SIAM J. Comput. 39.8 (2010), pp. 3441- 3462. ISSN: 0097-5397,1095-771
[10] Hlaas Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. "Efficient testable learning halfspaces with adversarial label noise". In: Advances in Neural Information Processing Systems. Vol. 36. Curran Associates, Inc., 2023, pp. 39470-39490.
[11] Tlass Diakonikolas, Daniel M. Kane, and Jelani Nelson. "Bounded independence fools degree-2 threshold functions". In: 2010 JEEE 5 Annual Symposium on Foundations of Computer Science-FOCK 2010. IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 11-20. ISBN: 978-0-7699-4244-7.
10

---

[12] Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. "The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model". In: Proceedings of Thirty Fourth Conference on Learning Theory. Vol. 134. PMLR, 2021, pp. 1552-1584.
[13] Ilas Diakonikolas, Daniel M. Kane, and Lisheng Ren. "Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspacces and ReLU Regression under Gaussian Marginals", In: Proceedings of the 40th International Conference on Machine Learning. Vol. 202. PMLR, 2023, pp. 7922-7938.
[14] Ilias Diakonikolas, Ryan O' D'Donnell, Rocco A. Servedio, and Yi Wu. "Hardness results for agnostically learning low-degree polynomial threshold functions". In: Proceedings of the /wenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia,
PA. 2011, pp. 1590-1606.
[15] Aravind Gollakota, Adam R. Klivans, and Pravesh K. Kothari. "A moment-matching approach to testable learning and a new characterization of Rademacher complexity". In: STOC'23- Proceedings of the 55th Anmual ACM Symposium Theory of Computing. ACM, New York, 2023. pp. 1657-1670. ISBN: 978-1 99-1---503-9913-55
[16] Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. "An Efficient Lester- for Halfspaces", In: The Twelfth International Conference Learning Representaaions. 2024.
[17] Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. "Tester- learners for halfspaces: Universal algorithms". In: Advances in Neural Information Processing Systems. Vol. 36. Curran Associates, Inc., 2023, pp. 10145-10169.
[18] Prahladh Harsha, Adam R. Klivans, and Raghu Meka. "Bounding the sensitivity of polynomial threshold functions". In: Theory Comput. 10 (2014), pp. 1-26. ISSN: 1557-2862.
[19] David Haussler. "Decision-theoreti generalizations of the PAC model for neural net and other learning applications". In: Inform. and Comput. 100.1 (1992), pp. 78-150. ISSN: 0890- 5401,1090-2651
[20] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. "Ag- nostically learning halfspaces". In: SIAM J. Comput. 37.6 (2008), pp. 1777-1805. ISSN: 0097-5397, 1095-7111.
[21] Daniel M. Kane, "k-independent Gaussians fool polynomial threshold functions". In: 26th Annual IEEE Conference on Computational Complexity. IEEE Computer Soc., Los Alamitos,
CA, 2011, 1, pp. 252-261. ISBN: 00--6696554111-5
[22] Daniel M. Kane. "The Gaussian surface area and noise sensitivity of degree- D polynomial threshold functions". " In: Comput. Complexity 20.2 1), pp. 489- ISSN: 1016-3328, 8954.
[23] Daniel M. Kane, Adam R. Klivans, and Raghu Meka. "Learning Halfspaces Under Log- Concave Densities: Polynomial Approximations and Moment Matching". In: Proceedings of the 26th Annual Conference on Learning Theory. Vol. 30. PMLR, 2013, pp. 522-545.
[24] Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. "Toward efficient agnostic learning". In: Proceedings of the Fifth Annual Workshop on Computational Learning Theory. Association for Computing Machinery, 1992 pp. 341-352, ISBN: 0897914977
[25] Adam R. Klivans, Ryan O' Donnell, and Rocco A. Servedio. "Learning Geometric Concepts via Gaussian Surface Area". In: 2008 49th Annual IEEE Symposium Foundations of Computer Science. 2008, pp. 541-550.
[26] Matthias Krause and Pavel Pudlák. "Computing Boolean functions by polynomials and thresh- old circuits". In: Comput. Complexity 7.4 (1998), pp. 346-370. ISSN: 8016-3328,1420-9999 1420-8954.
[27] Ryan O' O'Donlell and Rocco A. Servedio. "Extremal properties of polynomial threshold func- tions". In: J. Comput. System Sci. 74.3 (2008), pp- 298-312, ISSN: 0022-0000. 1090-2724.
[28] Ronitt Rubinfeld and Arsen Vasilyan. "Testing distributional assumptions of learning al- gorithms".. In: STOC'23 Proccedddss of the 55th Annual ACM Symposium on Theory of Computing. ACM, New York, 2023, pp. 1643-1656. ISBN: 978-144503-991--5

---

[29] Stefan Tiegel. "Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Prob- lems". In: Proceedings of Thirty Sixth Conference on Learning Theory. Vol, 195. PMLR, 2023,
pp. 3029-3064
[30] Leslie G. Valiant. "A theory of the learnable". In: Commun. ACM 27 (1984), pp. 1134-1142. ISSN: 0001-0782.
12

---

A Testable learning of polynomial threshold functions
In this section, we give formal proof of our main result, Theorem 3, that we restate here. Theorem 19 (Formal version of Theorem 3). Let d N. For any E > O, the concept class of degree-d polynomial threshold functions in variables can be testably learned up to error w.rd. the standard Gaussian N (0, In) in time and sample complexity
Oa(c 44.77 -Oa(e 4d.11)
In particular, if d is constant, the time and sample complexity is nPoly(1/e).
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 1j such that if D' matches the moments of W10,,,, In) up to degree k and slack then we have
EX-D [f(X)] Ey- [f(Y)] S e/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 l coordinates is (0, Tx).
The reason why it is enough to only focus on satisfying the fooling condition is that for any 7) we can find m large enough that the first condition of Theorem is satisfied for (( I,) (see Remark 10 and Fact 36). For we choose the same value as in [21], namely
Oa -4d-7"
We first show how to choose for the case of multílinear polynomial polynomials in Appendix A.I. In Appendix A.2, we generalize the fooling result arbitrary PTFs. Finally, in Appendix A.3, we show how to apply Theorem 9 to get testable learning for PTFs.
A.1 Fooling for multlinear PTFs
Thus, let f E C and let be the multilinear polynomial (of degree d) such that f(x) = f(x)= (ign(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 (testable) learning. Without loss of generality, we assume that the sum the squares 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 (0, Ia) up to degree i and slack 1), where k 2 Da (8 (e- and rj S n (Qa Then, we have that, for any multilinear! FPTF,
EX~D [[(X)] - By [S(Y]| S Oa(e).
Note that we only show Oa(z) here instead of e/2, which is needed to apply Theorem 9. This simplifies the notation in our proof of this proposition. We later apply this proposition to (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 function f: _ + E that approximates f. We will define this function in Appendix A.1.I. In Appendix A. 1.2, show that the expectation of ff is close under D' and (000, I,). More precisely, in Lemma 25, we show that under the above assumption on we have that
By~A((,1.)) [f(Y)] Ex-D [f(X)]| - Oe)).
In Appendix A.1.3, we then show that under both D' and (O, 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 that
By-A(o.1,) [ -rr]--Errrr.. [f(Y]] < O(E).
In Appendix A. we then also show that this also holds for X ~ D' instead of Y ~ ~N(0, I,). More precisely, we show Lemma 29 that Lemmas and 28 contain already enough information about the moment-matching distribution D' to conclude Proposition 20.
13

---

A.1.1 Set up and definition of the function f
In this section, we want define the function f that should be thought of smooth approximation of the PTF f. In order to define this function, we first restate the following structural theorem from [21].
Lemma 21 (121, Proposition 4J). Let mi m1 S m2 .... ma be integers. Then there exists integers n1, A2..... Rd. where n4 S Oa(mimy my m1-1) and (non-constant homogeneous multilinear) polynomials hi...., hd. P., (1 S i S d, 13j n.) such that:
1. The sum of the squares of the coefficients of P.g is 1.
2. I NO, In) and 8 my then [ (Y)1 S Oa(v8)
3. p(Y) Σ (Y) .. P,,,()))
The values of my want to choose are as in [21]. i.c we let m; O₂ (0(3-337)) (=-37'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,
use p R - IR be denote the multilinear
polynomial and f IR" + [-1, to be the PTF we are interested in, i.e. f(x) = sign(p(x)) Furthermore, the P.j IR" IR for i E [n] and j E [ng]
the polynomials in the struc- ture theorem. We denote by P. R + R" for E [n]] the vector (Pr,1, P.n,,) and by P: R" + R X as the function F ((y1.....32) = Ei= (v:),, ie. we get f(z) = F(P(x)).
Rnd the vector (PI...,, Pa). Finally, we define F R"
Rm R
Similar to Condition 1 in the above lemma, we can also get bound on the sum of the absolute values of the coefficients of the Pt.j- We need this later the proof of Lemma 25.
Fact 22. For any [n]] and [n.]. the sum of the absolute values of the coefficients of Pag is at most 4/2
The idea to prove this is to bound the number of coefficients we have and use an inequality between the 1- and 2-norm. The detailed argument be found in Appendix C.1. Furthermore, have an analogous result to Item 2 for the moment-matching distributions, which is again proved in Appendix C.I. We need this result later for concluding that f is a good approximation under the moment matching distribution 'D'.
Fact 23, For any E [d]. E [m:] and e S k/d, we have that
Ex-D [Pas(X)]] < By~NN(.
[Pi)())] (P + mm at/2/2
As in [21], we now consider the function PC IR" - defined in the following lemma. Lemma 24 ([21, Lemma 5)). Let
1 11
1111
[xxx)
B(g)
and P2(x)
0
else
|B2
where where B is the Fourier transform of B. Then, the function PC defined by
C
Cx
pc(x)
P2
2
2
satisfies the following conditions
1. PC 2 O.
2. Jg. p(x) dr =
3. for any unit vector and any non-negative integer l have
f
DD D)(P(C)(z)) C
14

---

4. for D 0. Milla22 PPc ((
We now define the following three functions F and in particular f, in the same way as in [21]. We let p T ..... x Te + be defined as p(y1,..., Ma) = PC; (11) ................................ Pca, (va), where the C;
are the same as in [21], i.c. we let C Oa (5-7'd) dd). Using this function, define an approximation
R x ... x T - IR to F as the convolution F F and an approximation f R R to f as [(x = F(P())).
The general strategy to prove Proposition 20 is show the following three steps, where as usual ~ NO, In) and X D',
Ey [S()]
Lem, 28 ~
By [((Y)
Lem. 25 R
Lem, 29 Ex Ex [f(X]]
Ex [x
(8)
Expectations of f under the Gaussian and the moment-matching distribution are close In this section, we want prove the middle approximation of (8). More precisely, we show the following lemma.
A.1.2
Lemma 25. Let E > O. Suppose that D' approximately matches the moments of (0, In) up to degree and slack where k 2 Qd (=- (==AdTT) and 17 S n - Then we have that
BY-NOO,.. [f(Y)) ExND [f(X)|| O(E).
We want to do this similar to [21, Section 6]. For this, let T be the Taylor approximation F around O. We use degree m; for the ith batch of coordinates (recall that F R" ... X IR - R). The strategy to show Lemma 25 is proceed in the following three steps, where again Y ~ (0, In) and ~ D',
22 Ey [((Y) & By (T(P()))
Pf. of Lem. 25 2
Ex [T(P(X)) Lem. 26 &
Ex Ex [x()].
(9)
The first approximation above only involves the Gaussian Y. so we get directly from [21, Proof of Proposition 8] that Ey~N((, [lf(Y) - T(P(Y)) s O(e). We now want to extend this also to moment moment-matching matching distribution, which we do in the following lemma, i.. show the third approximation in (9).
Lemma 26. Let & > O. Suppose that D' approximutely matches the moments of ( In) up to
degree and slack n7, where l 2 Pd ( (d- and 17 S kd Then, we have that
Ex-Dr [lf(X) - T(P(X)) O(z)
This proof follows closely [21, Proof of Proposition 8], which is why defer the proof Ap- pendix C.2.
Note that the condition 1 in this lemma is also satisfied for the yy from Lemma 25, Thus, it remains to prove
R (T(P())) EX-D [T(P(X))) S O(e)
complete the proof of Lemma 25.
Note that in contrast to [21], this quantity is not 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 different argument here and argue that this small even if X only approximately moment matching Gaussian and not k-independent Gaussian. We can write the Taylor expansion follows
T(x) =
Σ
8th F(0)x",
a!
a=(a)...aaa): la, Smn
where the a are multi-indices in No: We want to prove the following lemma about the coefficients in the Taylor expansion.
15

---

Lemma 27. For any multi- index = (a1......au) E N x x... x No4, we have
8 F() - II lail
The proof of this lemma is Appendix C.2. The ideas of this proof are based on [21, Proof of Lemmas 5 and 7]. We can now prove Lemma 25.
Proof of Lemma 25. As argued above, we already know that
Ev-,(o, - T(P()))
O(s) and EX~D - - O(s).
It thus remains to argue that
Ey~ (T(((Y)) Ex-D (T(P(X))) s O(s).
Define the vectors = (la) and u = (wa) by
ta 8 F(0) and ua = B...)(..,.) Ex-D [P(X)*]
a!
We then have that
LY [T(P(Y))] Ex-D [T(P(X)) = [1,, u>1 S ||4|] 1/w
We now want to bound ||t][] and ||u|lac separately. For the bound on ||+|| note that, by Lemma 27,
we have
Ita
1 00 ((0( $ II
c au
Plugging in the definition C. Od (E-T') I Oa(k) and using |a| = -EE larl I k. we get
that
ttl < (k))
Since have that n, I k, we can conclude that the number of multi-indices a with |ay| S is most (dk) < k(a((k) and thus, we have that
|1||
Σ
Eval |al S kO(R))
We now move on to bound ||u]|oc. We write P.j as follows
(z)(2) Σ
a x.
3
Here, the ] in the goes over all multi- indiiis with |S| being the degree of P.y. which is at most d. By Fact 22, we have that
Ela < 4/2
3
Let |al = l be such that Jas| s m, (i.e the term appears in the Taylor expansion) and let (i1. (ie, be such that
P(x) = Piisi (x)
(r).
Note that some (as); > 1, we include the corresponding factor Ps, multiple times. We can now expand P(x)) as follows
P(x)a =
Σ
(Ba) Cn
Σ (ot) A
B
Dr
(91)
(9c)
Diele
81
Be
16

---

Now, note that h: 2 d(m1 +... + my) (this condition is in addition to the conditions on l in [21] but does not change the asymptotic value of & as stated in (7)). We get that the degree of the terms appearing in the sum is [3| + ................................ 1Bxl I d I d(m + m.) I k and thus that
By-,( [P(Y) Ex-D P( S Σ
(91) 3ich
(P2) se In.
Here, we used the triangle incquality and the fact that
[B--/o, [ys++t*+.0 Ex ExaDY
[XA+ +30] $ n7.
Thus, we can compute
[y (P())) ( EX (P(X)*1
Σ ...
Σ
[a(9) ... [a(0)) Im
(91)
81
Be
(BL)
Σ
(Be) diecde
a
B1
|lasc 11 ..... (aee.tell19
S n 22/22
n lald/22
Thus, we get
11u1l00 S <n O2(k)
Finally, we can conclude that
Ey ((P(V))) - EX-D (T(((X))] S || |/u/lxc S 5n000) 0(s)
since we have the conditions 1) S n - (2((k) - and 1 < O(s).
A.1.3 The functions and ff are close in expectation In this section, we want to complete the proof of Proposition 20 that shows
Ex-D [f(x)] Ev~ [f(Y)] s Oa(e).
So far, we already showed in Lemma 25 that
Ey- [[())] EXnD [(x) & 0(s).
Thus, it remains to show that under both X ~ D' and Y ~ (O, I,,), the expectation of f and differ by at most Oz(E). For Y, we directly get the following. Note that the approximation f depends on E via the numbers my in the structure theorem Lemma 21 and the C, the definition of p.
Lemma 28 ([21, Proposition 14]). Let O. Then, we have that
Ey Ey~ (((0) -Ey-N(o..) [imn]] O(e).
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 that
[[(X]] s O(E).
EY- [f(Y]] - EX-D
To conclude Proposition 20 want to use the following lemma. It is analogous to [21, Proof of Proposition 2] and the same definition of B;, i.e. define B, O (og((1E)) We prove this lemmas in Appendix C.2.
Lemma 29 (analogous to [21, Proof of Proposition 21). Let > Suppose that D' is a distribution such that the following holds
Ey~A((01)) [S(Y) - ExaD [ī(x]] S <(()), and
17

---

PX Bi,j: (X) > B,] - O(E).
Then, we have that
((0... [S(Y] Ex-D [s(X)] 5o(ss)
We are now ready to prove Proposition 20.
Proof of Proposition 20. Using Lemmas 25, 28 and 29, it remains argue that
PX-DV [ii (X) > B:] < O(s).
This is true by Markov's inequality and looking at the log (dn: / = é-th moment since this implies that (assuming without loss of generality that & even)
Ex-D (X)
PXWD (Y) 2 B,] S
B
By (00.1a) [P))( + mm
B
EY-N(O.L)) [Yr,(Y))] +1
BR
OalVe)
B
e
E
dng
In the second step we used Fact 23. Note that f. = log(dn,/e) S k// d is ensured by the choice of l: as and thus the condition on v) in the statement of
in [21]. In the third step we used that since d this proposition ensures y) S nde/z. In the fourth step we used Lemma 21. In the fifth step we used the condition B; 2 la(v)). This is true by the choice of B, O / [og(L/e)) and the fact that log(n:) < Ej=1 (og(m;) I Oa(log(1/e)) In the last step, we then used the definition of Taking a union bound over j and then over gives
PX-D [i, (P) > B:] O(E),
which completes the proof.
A.2 Fooling for arbitrary PTFs
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 slight modification below. Namely, we only prove [Ey~N((o,L)) [f(Y] - EX-D [f(]]] < Oa(s) instead of e/2. The reason for this is, for Proposition 20, this simplifies the proof and we take care of this difference when apply Theorem in Appendix A.3.
Proposition (Restatement of Proposition 12). Let > Suppose that DD' approximately matches the moments of N In) up to degree k and slack where k 2 Qa(s-AdTT*) idTt",, and 1 (2((k) (Qu(()) Then, we have that for any f FPTF,
Ey~N(o.1)) [f(Y)] EX-D [f(x)] & Od(e).
The general strategy for this will be to, given polynomial p, find another polynomial ps and reduce 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 Section 2.3.2. Specifically, in [21] all restrictions to coordinates are exactly Gaussian, and in particular we have access to moments of orders. The proof in [21] exploits this since considers a number of moments depending on the dimension, whereas only have access to constant number of moments.
18

---

Lemma 31. Let 8 > O. Suppose X ~ D' approximately matches the moments of N(0, In) up to degree and slack T,, where S n and k 2 Qd(1). Let Y ~ (0, I.). Then there polynomial ps and random variables X and Y, all in more variables, such that
Y is Gaussian with mean 0 and covariance identity.
X is approximately moment Y up to degree k and slack îj = 1/(22))+/2
Py,8 [I(()) - -ps(Y) 6) < 6, and,
Px,x [D(x) po (x) 6 8.
Given this lemma, we can prove Proposition 30. Since this proof follows closely [21, Proof of Theorem IJ, we defer it to Appendix C.2
remains to prove Lemma 31 and explain how we construct ps as well X and Y. We do the latter in Appendix A.2.1. Namely, we show there how to construct the random variables X and Y from X and Y. In this section, we also make precise in how many variables the polynomial is (and thus also the random variable X and Y). The proof that they satisfy the condition required by Lemma 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 in p by multilinear polynomial in X (whose proof is in Appendix C.2) and use it construct ps and prove Lemma 31.
A.2.1 Construction of the random variables X and Ý
To show Lemma 31, want, given polynomial p and 5 >> 0 well two random variables X and Y, where Y ~~ (0,, (0, I,)) and X matches the moments W I,) up to degree and slack 7,, to construct multilinear polynomial ps in more variables and two random variables X and Y such that Ý is again Gaussian with mean 0 and covariance identity and X matches the moments of Ý up to degree i and slack f). The guarantee we then want to show in Lemma 31 that
Pr. [I0(Y) ((00)-p(())) 8) <
and
P Xx, [I(X) pa (x)) 8) <,
where the probability is over the joint distribution of Y and Ý respectively X and X.
Let N be (large) positive integer that will be chosen later. Then the number of variables of the new polynomial is n N, i.e. we replace every variable of by N variables for ps. We make the following definition. For (I,...,, n) and j E {1. J...... N}. we define
L = X; + /
where 7 is are multivariate Gaussians with mean 0, variance 1 and covariance - indepen- dent for different/ i and independent from X. In particular, the choice of the covariance matrix ensures that we deterministically have Z,,1 +.. ZN = 0 and thus X; = Σi X1,5- The construction for y is the same, i.e.
Y Y, 2,000
where (1() again multivariate Gaussians with mean O, variance x and covariance - independent for different i and also independent from Y (as well as and 2).
now have the following two lemmas that relate X to X and Y Y. The proofs of these lemmas are in Appendix C.2.
Lemma 32. Suppose X approximately matches the moments of N0, Ia) up to degree k and slack Then, & approximately matches the moments of (0, IAN) up to degree k and slack f (²
19

---

Lemma 33. IfY 1 (O,, then Y ~ NO INN).
Lemma 33 already proven in [21, Lemma 15], but for completeness we also make explicit in Appendix C.2.
A.2.2 Proof of Lemma 31
After constructing the random variables X and Y, we now move on to construct the polynomial p6- As in [21, Proof of Lemma 15], the goal is to replace every factor of of p by a multilinear polynomial variables ( such that X is close to this polynomial evaluated in (Xiz); with large probability. Doing this for all factors =. appearing in p and combining the new multilinear terms, this then gives multilinear polynomial ps of degree d. Note that the polynomial is in fact multilinear since for replacing x; we only use the variables u. where =
Note that it is enough to show
PP [I(XX) Ps(X)) > o/ <d.
(((X))ps(X))
The reason for this is that, Y (0, In), then Y in particular matches the moments of (O, In) (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 8' be small positive number (depending on 8, n, d) to be chosen later. We need the following lemma.
Lemma 34. Let 8' > 0. Let i [n]] and E [d]. Assume that each of the following conditions holds with probability d
1
I
(10)
8
< 8 dd+
(11)
N
X
8'441
v
(12)
Then, there is a multilinear polynomial in X1, that is within Oa(8') of X with probability 1 8'.
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) 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 (00 In). By using stronger bounds for (11) and (12), we are able to generalize the proof from Kane our setting, For more detailed explanation why we need to change the bounds, we refer to Section 2.3.2.
We now define
8 2dn
80.t1
)}
8d++1
min
Od
3dd/2
Os
3d/22
(13)
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 5' and the condition n from Lemma 31 ensure that we can apply Lemma 34.
Lemma 35. Let 8' in (13). Assuming v S 802(()) - there is choice of N (independent i or E) such that (10), (11) and (12) hold, each with probability 1 8' d-
Proof of Lemma 31. Lemma 34 (together with Lemma 35) shows that we can replace X by a multilinear polynomial in &.,, that is within Oa(8') of X with probability 1 - 5' for our choice of 8' as in (13). Since 8' < &_
2dn we union bound these events over all e [m]] and é [d] and get
20

---

that with probability 1 1-3 2. we have that for any i E [ra] and & E [d], we have that the replacement polynomial for X is within Oa(8') of X
Furthermore, for any i E [ni], we have that with probability 1 we match k 2 2 moments (and v - 1.) and thus
5. 2n
that [X,]
S 3 This is true since
E [x3]
(2 + 7)82 5
X; 3 8
(3g)
9n²
4n
Hence, we can again apply the union bound to show that with probability 1. we have for any i E [n] that [X,] S 3
Thus, with probability 1 6, all the above events holds. Conditioned on that, we have that the replacement polynomial is off by at most (3%)* Ou (6") multiplied by the sum of the coefficients of p. The later is at most n/42 by Fact 22 applied to p instead of Pi.j- Hence, the replacement
polynomial is off by most Od 1////2 8' Thus, since 8'
Ru(( ( ".25) we get that with probability
1 8, ps is off by most ö, which is what wanted show.
A.3 Proof of testable learning of PTFs
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 S n - then we have the fooling condition of Theorem 9,
Note that the fooling condition requires [By=~((o.L.) [S(Y)] Ex-D [S(X)] S but Proposi- tion 30 only gives Os(s). Thus, technically, we apply Proposition 30 for g = [T( However, this does not change the asymptotic condition on 17 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.)) we have that the empirical distribution matches the moments up to degree with error at most 7). Then, we get testable learning of PTFs with respect to Gaussian in time and sample complexity m + ne ((k) by Theorem 9.
the following fact, which prove in Appendix C.1. Using this, can then prove Theorem 19.
To get m,
Fact 36. Given m 2 ((((km))n1-3) samples of NN, In). we have that with high probability the empirical distribution matches the moments of (0, In) up to degree le and slack 17.
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 + ((k) samples from (O, T,,) we have that the empirical
where such that with high probability distribution matches the moments up to degree k with error at most 7). It remains to determine m. By Fact 36, we get that the choice of m ((22n))*n 2) enough. Now, in order to apply
Proposition 30, need to choose 7 Oa(kk) k Oa(4)) Plugging in the value k O₂ (8 (
we get ea(s 40-7)
-a 417"
and hence
m = θ (2kn)* *n Pa(s 45*t)) -0(e (are))rr))))
Thus, the time and sample complexity for testably learning PTFs is
(2km)*n oa(e= pa(e--arr) -art") - -a((e-1 14.77
(kk)
Again, by plugging in the value & = O2 E ( we can simplify this to get that the sample and time complexity for testably learning PTFs is
Oa (5- 48.7d)
n
which completes the proof of this theorem.
21

---

B Impossibility of approximating PTFs via the push-forward
In this section, we provide further details on the results claimed 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.
B.1 Proof of Theorem 18
Let us begin by restating some important definitions and results from Section 2.4 for convenience. For > 0, we write wyy (z) = Cy (-)=--->)),)))))))))))>>))) where C. is normalizing constant which ensures w.y is a probability density. A distribution D on I is called log-superlinear (LSL) if its density function" satisfies wxx) 2 C (x) for all x E IR, for some 7 (0, 1) and C O. Recall the following.
Theorem (Restatement of Theorem 15). Let D be an LSL-distribution I. Then there exists E > 0 such that, for any polynomial q. we have EywD [lq(Y) - sign(Y)
We defined in Section 2.4 'one-sided' analog of LSL-distributions follows.
Definition (Restatement of Definition 17). Let 'D be distribution on IR whose density function w satisfies
w(x) 2 C. (x) Vx E (-o0, 1]
for some < 1/2 and C > O. Then we say D is one-sided log-superlinear.
In this section, we prove Theorem 18, which distributions, and the basis of our proof of Theorem 16 in Appendix B.2.
analog of Theorem 15 for one-sided LSL-
Theorem (Restatement Theorem 18). Let be a one-sided LSL-distribution on R. Then there exists an 0 such that, for any polynomial q. we have Ey WD IY) sign(Y)]]
For our proof, it is useful to first recall the main ingredient the proof Theorem 15 in [6], which the following inequality.
Proposition 37 (16, Lemma 20]). Let q be univariate polynomial, and let y E (0, 1). Then, there exists a constant My > 0, depending only on ", so that
sup (x))(() My =ERt
(1(x))/,(()) dr.
Given Proposition 37, the intuition for the proof of Theorem 15 is that, if q is good approximation of the sign-function on IR, it must have very large derivative near the origin. On the other hand, Ey<D [[q(Y)]] is bounded from above (as IE siin((
1), leading to a contradiction.
The key technical tool in our proof of Theorem is version of Proposition 37 that applies to one- sided LSL distributions. That is, bound on the derivative of polynomial in terms of its L Lı-norm on (-o0, w.r.t the weight w.y (x) C,, exp(-Iar))) (a|"), < 1/2. We will only be able obtain such 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 one-sided inequality (whereas Proposition 37 is
inequality). Lemma 38. Let be univariate polynomial. and let < 1/2. Then, there exists constant M', > 0, depending only on 7, so that
Bernstein-Nikolskiie
sup ld((z)) S My 1." (a(x))u, dr. 1
Proof. By substitution n² and using the fact that w. wx(xx) Cr exp(-|xr)) is even, we find
(( wy (2) dr |
/ (o(n))ulwzy du. Cz
Cg
2u du
TTechnically, density functions are defined only up to measure-zero sets. Therefore, one should read statements of the form 'w(x) 2 ... for all x E... only holding throughout.
22

---

Now, since 27 < 1, we may apply Proposition 37 to the polynomial ((u) = q(u2)u, yielding an upper bound on its derivative for all E R; namely
d j(u) du
W2n w2,(1)
S M2n
((u))ulwzy()) du
M2yC2y
Or 19(x)|10 dz.
As way is monotonically decreasing, we have (2-(2)) (2/45 for all S 5/4, and so we find
/ ( (x) dx, My = M2n Czn
sup M -
(())
I My
(14)
du
C, 22y (2)
We wish to transform this bound on the derivative q into bound on the derivative of q. Note that
d
((u) du
(g(1²)u) = 24' (2 )u² + q(u²).
du
We can bound this as follows
sup 2q((") + q(x2)) 2 sup 1
|d((x²) - sup
Ig(u²))
2 +
l-2-
Now, switching our notation back to the variable = u² and using (14), we have
3 sup
|d(x)) s My [00 la(x))lo, (x) dx + sup
|a(x))]-
(15)
2 |-11
|--1|<
remains to bound the rightmost term in this inequality. Write eq > 0 for the constant (depending on q) satisfying:
sup [g(x)|
W., 1. lux))) dr.
Co
(16)
1
If Cg S 2, we are done immediately by (15), as then
3 sup
My + w)( {
2
1/00 (0(x))1 dr.
1
2 =
So assume that C2 2. Note that
8
(u(x)) de 2 wey (g) {a (n(t)) do 2 wr) inf la(x),, |x-1|5)
and so
/ l4(x) dr.
inf 1|+
[q(x) <
(17)
(2)
Applying the mean value theorem to (16) and (17) on the interval [3 21. we find that
sup 1x(( 2 2 ( /. (x))))u((x)ddr = 2(cg -1) sup
[q(z)]
1x-1|s
Cq |1-1/
As 0q > 2 by assumption, this yields
sup l (x)x
sup
Ig(x))
- 1
and we may conclude from (15) that
? -11 1
/ (u(x))))(())) dr.
ld((z)
S My
sup
Ja- 1
Combining the cases cy < 2, cu > 2 finishes the proof with MG max My - (5/45/) 2 }.
2
23

---

Proposition 39. Let D be a one-sided LSL distribution on R. Then there exists constant Cp > 0 such that, for any polynomial 9, we have
1d(x)) S CD ExaD [x([)
sup 1
Proof. We wish to Lemma 38, which gives bound the derivative (xx of q when 1. To transport this bound to the origin, we consider the shifted polynomial ((x) = q(1 - z). Let w be the density function of DD Since D is one-side L.L--distributin, there exists constant C > 0 and a y E (0, 1/2) such that w(x)= 2 C wy(a) for all a E (-00, 1]. As W, is even, bounded from above and below on [0, 1]. and wy 1) S w0 (z)) for I 0, we can find constant C' > 0 such that
w(x) 2 C' w.y( x) Va (-x,1). 1].
Now, we find that
(x) do = ["' 1 w1) - x) dæ
1 (/1
1 S lq(x))u(z) do S C
$ C
Ex [l([
As < 1/2, we may apply Lemma 38 to find that
M4 (1)(z) S SM / (x) s C ExxD [[]())])
sup |
To finish the proof (with Cp / C²), it remains to note that
sup --- +
(()(())
sup ld'(x)) |
We are now ready 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 satisfying
Ex-D sign(X) - x(x) 1
Since Ex-D sign(X)) = 1, we may use the triangle inequality find that
Ex-D [X]]] - + 1 1= 2.
By Proposition 39, this means that, for some constant Cp > depending only on D,
sup lg (x(x)) < Cp. |
Set 17 (10Cp)-1 It follows that
sup |
1g(x) - <(0) < (10 .00 = 5'
Assuming first that (()) 0, this means that
4
lg(x) sign(x))
Vx E [ [0,n]
Let be the density function D. As D is one-sided LSL, and n 1, know there is constant
C' > 0, independent of 17. such that w(x) 2 for x E [0, v/]. But, this implies that
Ex-D si) - q(x)ll 2 C l" sign(x) g(x)) dx -..
4
giving a uniform lower bound on Ex-D sign X) - q( (X)l] for polynomials q. If, on the other hand q0) 2 0, the same argument works after replacing [0, n/ by [-n.0] 0j.
D
24

---

B.2 Proof details for Theorem 16
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) - 2) - 3)(x - 4) - 5). Then, p is square-free, {p 2 0} C R is compact. and P+N is one-sided nog-suprrlinear
Proof. The first two properties follow directly. For the third, let w be the density function of Po,N(0 1). Applying the inverse funetion rule to w2((x) C2 exp( (-|==-/))) have
w = C2
Σ exp (-p((1=))))
AyER.
1x'(z))
TEP
We need show that, for some C > and y E (0,1/2),
w(y) 2 C exp(-lul") Vy E (-xx,
(18)
Qualitatively, the behavior of w can be described as follows. When y 2 supser p(x) x 17, then
w(y) = 0. When y < O, then x E p- pv) implies x = lyl'/, and so w(y) exp(-lyl 1/3) Finally, for any K > 0, there is a uniform lower bound on w(y) for all E [-K, 1]. To show (18), remains to make this description quantitative.
As the leading term of p -x6, there is K such that lp (y) for all y S KK, and
x E E (v) = |x| S 2|yl 1/6 Vy K.
This means that, for (possibly larger) constant K' 0, and some 7 E (1/3, 1/2), we have
1
(vy) 2 2 C2 exp (-41g)4/3)
(2(2 2 exp(-1My1) A. -K'
(19)
Now, there is an MM > 0 so that
x E p (1) = | M M VyEl-k',1]
It follows, as p (v) is non-empty for y S 1, that
w(y) 2 inf |
C2 - exp(p1a01))
> o VyEl-K',
(20)
(x)]
Combining (19) and (20), and choosing
small enough, yields (18).
C Technical details on the proof of testable learning
C.1 Facts and computations
In this section, we prove several facts that we used in the proofs in Appendix about the moments and other properties of Gaussian random variable Y and a random variable X that matches the moments of Gaussian up to degree i 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.ç. Recall from Lemma 21 that the sum of the squares of the coefficients of the polynomials Pi.j is 1.
Fact (Restatement of Fact 22). For any i [m]] and j E [n.], the sum of the absolute values of the coefficients of Pr.j is at most 4/2.
Proof. Similar to before, write the P.ù follows
Pa)(x) Σ
9
The 33 in the sum goes over all multi-indices with |.8| being the degree of P.j. which is at most d.
Thus, there are at most nd terms in the sum. By the structure theorem (Lemma 21), we know that
25

---

1. We can now get bound on the 1-norm as follows (since the number of coefficients "ij is at most n
(8)
Σ /
1- 1am, S 22/3 11sssll S n2/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 7), 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 (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 r) S 1 and let 'D' be a distribution that matches the moments of N In) up degree and slack Then, we have that for any multi-inde with |a| S k we have
EXNDY [Xa] vlal jal
Proof. We have that
[x [X S BY-N(( [ +1
Ez-A(0.1)
2/a
|+1
- + (0
if |a| is odd otherwise
[(aa] - 1)!!
$ Vial"
which is what we wanted to proof.
Fact (Restatement of Fact 23). For any i E [d], j E [ms] and l S k/d, we have that
Ex-D [X)s(X)] S BY (X)) + 17 22/2
Proof. Writing P., as in Fact 22
(0) Pa.(x) Σ
2g
8
can compute EXnD [X,)(X)' follows
EX-D (X))
Σ B
(8) 0i
(32) ...ajj
ExnD [x
Now, since X is aapppoximmttely moment matching, we have that (note that P.s has degree at most and thus any term in the sum that degree at most de < k and thus the moment matching applies)
ExwD' [x*++m00]] = Ey~N((..)) ( +
Combining this with the above, we get
EXND (Ps((X)] < Ey~Nio. [Y))( +n
Σ
(9)
a
By Fact 22, we thus get that
EX-D (Pt)(X) S BY-wio.) [Pas mm de/2
as wanted.
Finally, we show two facts about the Gaussian distribution. First, we want to give bound on the moments of Gaussian random vector that has not necessarily independent entries and for which we only know that the variances are at most 1. 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 (0 Jn) we need such that the empirical moments up to degree & match the actual moments of (O, I,) up to slack 1).
26

---

Fact 42. Let Z be (multivariatee) Gaussian random variable with mean 0 and variances at most 1. Then, for any multi-indes 3. we have that
|3] 1//2
Proof. We want to show that for any random variables Wi,..., We we have
W
= B
==1
To prove this, induction and Hölder's inequality, f 2 2 we can compute using Hölder's inequality, since
The case
follows directly and for
+ + =
1)
E-1
W
S
E
I j=1
(B(W)))
Thus, get, using the induction hypothesis,
8-1
8
E
W
-
[W] - II E [
now use this result with |3] and the Wi,... 8j times. Then we get
We being the Zj. where every entry Z₁ occurs
1
E | <
II
TE [2
9,
Since E [Zy] = and Var [2y] I 1, we have that
E [ gt/2
and thus we get
2
< 02/2 101/2
Fact (Restatement of Fact 36), Given 2 Q2 (2km)) 2) samples of (0, we have that with high probability the empirical distribution matches the moments of (0, In) up to degree k and slack n.
Proof. Given m samples from (O0 In), we want to compute the probability that for some with |a| S we have that the empirical moment close the moment with high probability. We can compute using Chebyshev's inequality, where ca is the a-moment of ( I,) and é, is the empirical moment, that
Var Y [c]]
Var [c.] n)2
1 Var Yaa)
1 (2/a)))al
1 (2k)*
P [|c.
cal n)
m
m
1j²
m
17²
m
np
To be able use union- bound, we need this be smaller than O(n *). i.c. we need
(2km)
m 2
112
C.2 Remaining proofs
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.
27

---

Lemma (Restatement of Lemma 26). Let & > O. Suppose that D' approximately matches the moments of NO, In) up to degree k and slack 1,, where &o 2 Otd (e-adT)) and 1j S kd Then, we have that
ExwDr [1f(x) [lf(x) T(P(X)) - O(e)
As mentioned earlier, this proof follows closely [21, Proof of Proposition 8]. In particular, also need the following lemma from [21].
Lemma 43 ([21, Proposition 6]). We have that, for I E R
C P 1.
IT(P(=)) - F(P(2)) S II
1+
mz!
ē=1
The Cj and again in [21]. i.e. we choose C, = Oa (5-T's and mi Ox (5-371)) For the proof, we furthermore need the bound on the expectation of (X)) from Fact 23.
Proof of Lemma 26. We have by Lemma 43 that
C,
IT(P())) F(P(2)) $ II 1+
mz!
f=1
As in [21, Proof of Proposition 8). the RHS of this inequality is the sum over all non-empty subsets S .1, d3 of the following term
C (P())
II SS
mj!
Continuing exactly in [21, Proof of Proposition 8), want show that any of these 2 terms is at most O(E/29). By the inequality of arithmetic and geometric means, we get that this term is at most
IS]
1
S
m
Thus, it remains to bound Ex-Di
[P((X))
where b = m.|S]. We do this as follows
Ex ExnDi
[IR,(2)113
$ sv EXND
VVXWD
4
ns Σ
EXnD
(X)
where used the Mauchy-Schwan inequality in the first step. Continuing further by applying Jensen's inequality to the (convex) function g(a) = a², we get
4
Σ Px)
li =n
1
Σ (L)(X)2
n
1 nl (x)(X)
n
n4 j=l
14
Combining these two, we get
EX-D
[IPA(X)133
<
n
Ex-D (X)
n44
The next step is now different to [21] since we only have an approximately moment-matching distribution. By Fact 23, get that
Ex-D (x) < Ey [Y)s( mld.
28

---

assuming that k 2 2dhm; (this ensures that 26; = 2m; |S| I 2m,d is at most k/d required in Fact 23). This condition is slightly different [21], but it does not change the (asymptotic) definition of l: as in (7). By Lemma 21, we now have that
1y-, Pr))( 5 (V26. 28: = Od (VB) 26
for any j. Combining this with the above, we can conclude that
X [II,(())11]
s vn. Vn."...
OO
(VE.) + V m mma.
S Oa
(0<(vin
(nmmm S
m.
using that 7) < n The rest of this proof is again the same as in [21, Proof of Proposition 8J. We can compute
This true since & mi|S] m,d and thus vj S प implies r) S ,
n
EX-D T(P(X)) - F(P(X))
P((()
1S|
2d
max 6x
Ex-D
S
m,!
YES
Oa
S
2d
049C d]
iES
mi
mils]
Ciyna
m488
2d
max L [d]
Oa
mm
By choice of m,, exactly in [21], we conclude that
(- min m. iE|d
EX-D'
2 exe
-min
< 0(s),
which completes the proof.
Lemma (Restatement of Lemma 27). For any multi-index a = (a1,..., E No1 x ... N we have
8e II cla.l.
Proof. As mentioned earlier, the ideas of the following proof are based on [21, Proof of Lemmas 5 and 7]. We have that
10a (F p)l [(F 0 (0))
(property of convolution)
< |1 110 plu
1100 Pll
(F maps [-1, 1))-
Thus, it remains to bound ||@ m. Using the product structure of we have that
||00 plle
II 1 Pc,lla.
(21)
First, we compute a bound for | palla. We generalize this afterwards to pc, Recall that
[ {1
-E111 if [|ll2 I 1
B(E) =
0
else
and
[B(x))²
P2(x)
B
29

---

where B is the Fourier transform of B. We first note that
B(x) B(x) 1B(x)1
Thus, we can apply the product rule to get the following formula for the derivative
gmh
p2
Σ
ai
(0
B)(80==BB)
BII
B
L
B
B<a.
1
Σ
ai (0 ()
|BBI
BSo;
where we used that the conjugate of the derivative is the derivative of the conjugate. We thus get the following by triangle inequality
p2))) S
Σ
a (8)
|100
()x))(0m
BII
BSa.
We now want to analyze (0 (0²B)(x) We have
F(² 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
11000 (2)(
Σ Bãa,
(1i
F(a F(a2B(x))
Floc
B
B
as B
1 B(xx) ((1))=a:=1 B(x)
B
La
$sa.
Σ
B(x) B(z) x
|B
3
B
Oii
B3a
2/0:1.
The second step uses the Parseval identity; the third step uses that B(x) # 0 implies that || & || S 1; the fourth step uses that (()]l) = |B(x))
For an arbitrary C₁ we can bound ||00 pc, |1 as follows. Recall that
Ci 2
C2
Pc, (x)
P2
2
We can compute, using the chain rule that
(
Ci (0
C2
C2
las|
(0" Pc, (x))
(0)
P2)
x
2
To illustrate how the chain rule implies this, can compute
C2
C
C2 2 2j
)
po.
(x) =
Σ
P2
2 x
x +
(x)
2
Ozy
0x1
j=1
C2
C;
1
ifj=1 if
2
Day P2
2 - r
(0-
j=1
C
n+1
C
P2
2 r
2
dm
30

---

Doing this iteratively, we get the formula above. Now, we want to compute the L -nom of that function. We get
100 pc, pc,
(8
pc,
C
n+|od
[ (2))
(Ci, ( dæ
2
lad
C2
C2
(2p(p2(())
y (U=
2
Joil
C
p2l11-
2
1001p2ll1. we thus get Using the bound from above
100spelll s clo.l.
(22)
Combining (21) and (22) completes the proof.
Next, we prove how we can generalize from
Ey-A(O.1)) [f(Y)] Ex [(xx] ((()
to the fooling condition need
Ey ( -[X)]_Expp ExwDY [s(X]] S Od(e).
This proof is based on [21, Proof of Proposition 2]. It turns out that this part of [21] does not need that is k- E-Gaussian but works on the following, weaker assumptions.
Lemma (Restatement of Lemma 29). Ler > Suppose that D' distribution such that the following holds
Ey [S(Y] Ex-D [ī(x] s SO(e), and
PXnD [i : (Paj( > B.} < O(s).
Then, we have that
Ey BY [S(Y)) Ex-D [S(X)] S Od(s).
In the proof of this lemma, we use the following theorem about anti-concentration of a polynomial of a Gaussian random variable. Importantly, variable y and we do not need it for the moment-matching distribution.
enough to have this result for the Gaussian random
Theorem 44 (Carbery and Wright, see [21, Theorem 13] or [7, Theorem 8)). Let p be degree d polynomial. Suppose that Ey [p Then, for > O,
PY~N(OLL) [I((Y) < < (d)
Proof of Lemma 29. Note that [21, Lemma 12 and proof of Proposition 14] and the second condition in the lemma imply that
E Eff(x) 2 E [(x) - 0(e) - 2IP (-Oa(e)) < < o]
and
B[f(X)] < E [(x) (s) 2P 00 < p(X) Oc(E9) Using these and the first assumption of the lemma get that
[[/(x)) > [[(()) - 0(e) 2PP [-Oa(s < p(X) < o]
and
[ < [[)() O(s) - 2IP [0 p(X) 0a(s")]
31

---

We have furthermore that
[sign(p(X))] + 21P [-Oa(=") < p(X) < 0] = E sign (p(X) + Oa(e")]
and
E [sign(p( (pgg()(())) - 2P [0 < (()) < Oa(e*)] = E [sign(((X) - Oa(e*)]
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 1-,,(E"),0) 0) respectively (0, Oa(e")), which the same as shifting the polynomial. Thus, when combining this with the above we get that
sigu(p(X)) + Oa(E"))] z E (sign(p(Y)) 0(s)
and
E (ign(p(XX) - O2((0)))))))) = [sign(p(()) + O(e).
Now apply this result not the polynomial p, but to the polynomial F Os(=*). This shifts the additional factor from the X-side to the -side and we get
[sign((p (p(X)) 2 [sign(p(Y) -
well
E (sign((( x - E (sign(p(Y) + [2( O(e).
Combining these two inequalities we get that
E (iigu(((Y) 0a(e O(s) s S [sign(p(()) + + +O()).
S
For Y, we have that (since the inequality hold point-wise)
E [sign(p(Y)) - E E [sign(p(Y) + Oa(=9))]
Now, the two function sign(p(Y) Oa(e))) and (ign(p(Y) + (a)))) differ by at most and only when [p(Y)l S Oa(=d). We now use an anti-conncntration result for (the standard Gaussian). Namely, we can use Theorem 44 to conclude that this happens with probability at most Oa(E). Note that we have ((..1. [p(Y)}] = since we assumed that the sum of the squares of the coefficients of which is exactly Ev-N((. [P(Y))] for multilinear p. is 1. Thus,
E sign(p(() (a(e }
E sign(p(Y) Oa(E"))ll s 0a($))=O((t)
Thus, since both E [X]] and E [f(Y) are between the values EE [sign(p(Y) Oa(e4))] and [ 0a(=)) (up to Os)) for E [f))))) we can conclude that also
E [X)]] - E [f({)] Oa(s),
as wanted.
Next, we want prove Proposition 30 that follows closely [21, Proof of Theorem 1]. This proposition shows the fooling condition for arbitrary PTFs. In the proof we need Proposition 20 about the fooling condition for multilinear PTFs and Lemma 31 that, given an arbitrary PTF p, constructs a multilinear PTF pa that is close to p.
Proposition (Restatement Proposition 30). Let > O. Suppose that D' approximately matches the moments of (0, In) up to degree and slack n,, where k 2 Qa(= -dd7") and rj S n -Ra(k) (R)())) Then, we have that for any E FrrF,d
EY~NO. [S(Y)) - [S(X]] < Oa(e).
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 (this does not change the PTF). We set
8 - E
We first want to show that the condition on 7j in this lemma ensures that we can apply both Lemma 31 to construct the multilinear polynomial ps and Proposition 20 to get the fooling condition for ps-
32

---

The condition for Lemma 31 is I 80a())-5a00p- Note that by our choice of k. we have eOu(l) I -R Thus, for our choice of 6, the condition y needed for Lemma 31 is satisfied by our assumption on v) in this lemma. For Proposition 20, we need fj (2k) S k n (a()) which is also satisfied by our condition on 17. Note that need this condition for (and not 17) since the new random variable X is only moment-matching up to slack ij-
We now want to show that IP [p(X) > 0] -P [p(Y) > 0] Σ Oa(e). Note that
E [sign (x)] = P (l((X) 2 0] PP (x(X) ) < 0]
P (p(X) 2 0] (1 TP (x)) 0))
2IP (x()) 0] -1
and the same holds for Y. Thus, [P (p(X ( -] 2 0 - Oa(e) will be enough since then
[E (sign(p(Y))) (sign [ssig(((X))]] = 2PP
( 0j| Oa(s).
By Lemma 31, we have that
F F 2 0] 2 P ps( 2 8 -
Since ps is multilinear,
apply Proposition 20 P5 ó to get that
P (x((X) 2 0J 2 ps Y) 2
Oa(e)
since 8 S O(s). Note that we apply Proposition 20 to IP [p(X) ) 0] instead of I [sign(p(X)) by the relation Gign(p(X))] = 2IP (x() 0] 1 from above. By Carbery-Wright (Theorem 44),
we get that P (ps(Y) ) S S (E), thus we further have that
PP (X) N 0) P
P)( 2 5) Oa(e).
Applying again Lemma 31, we get that
PP (X) 2 2 p Y 2 0] - -aa(e).
By an analogous calculation, we get that the proof.
P p XX 2 0] < P (P)) 2 0] + Oa(s), which completes
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 NO, 1,) up to degree and slack Then, X approximately matches the moments N IuN) ) up to degree and slack f (2
Proof. For multi-indes a, let ca be the a-moment of Gaussian. We want show that a ca s n for any a with |al| s k. We can compute the following, by writing Zs,; -
N
x
Ca
Ca
i=1
1=
n
N
x 7a.ss
Ca
N
Aij
(xxx)))
1
X1x
Z
Co
X
3
E
z
Ca
N
B
X
E
E
- $1
Ca
3
N
3Aa
33

---

In the second step we used the definition of X and in the last step, we used that Z and X are independent. Now.
X
E
E
Sn
VN
since X matches the moments of (00,, Ix) up to degree is and slack 17. Thus, we get
X
E
X
Ca
EI
E 1IZ
Ca
87
37 IE
R
E
[2a00]
8
0
$
a
E
E
2
ca.
8
35a
Y
E
1 +1| +
Σ
E
E
1
3 -
Ca.
3
$
N
350
35a
Σ
a
E
21 +
E [Y
cal
3
35a
Σ
E 7 $1
35a
The second-to-last step the same computation from above but backwards (note that the moments of Z' used for the construction of y 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 Yr] Ca. We can furthermore compute
X
Ca
= 17
Σ
E
Z
8
B
E
[
1
B5a
N
II
2
Bis
B5a
where the third step uses that the Z are independent for different i. We now get that, using Fact 42
NV
< |B,, 18,..112 S vT P..l
E
Thus, continuing with the above, we get
11 E
E
X
Ca
17
a<a
PL
a
S 1
3
3<a
( (V
17 Σ
950
n([k + 1)lol
< //2 = +
where 1 is the all-ones vector. This completes the proof.
34

---

Lemma (Restatement of Lemma 33). IfY ~ (0, In), then Y ~ (n,Nn))
Proof. Since Y is linear transformation of the Gaussian vector (Y, Z"), it is jointly Gaussian and thus show the lemma, it enough to show that the expectation of Y 0 and the covariance matrix is the identity.
Writing above Zin
7/30 we have for any E [n]. j [N] that
1
VN Y, + Zi
-+0
VN
Furthermore, for any i E [n]. j E [NV] we have that, by independence of and Z',
Var Yr,] =
1
Var [Y] +
Var [Z,
1
1+
1 (1 N = 1.
N
N
For any E [n]. 11 * j2 E [N]
we get that
Cov
Prisi Prisa] =
Yi + Ziniia
VN
Y2
+
E
YiZk,z
+
Y: 3.2
+
Z2,z2
N
1
1
+0+0
N
N
Finally, for any i1 # is [n], j1. [N] we have that
Cov Viniir Vin.ta]
by independence of Pi..,. = Y,, + 2 and Vr2.22 Yi, + Zig.j for i1 # iz.
Thus, as argued in the beginning, this shows that Ý N'O,, InN) 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 ps. For this, it remains prove Lemmas 34 and 35, which we restate below. First, recall our definition of 5' in (13).
6 2dn
1/3d/2 } = O. =Oa
jut1
[d++1
8' = min
Oa
(restatement of 13)
323d/2
In the proof of Lemma 31, we then used the following lemma that allows replace factor X by multilinear polynomial in the variable X.
Lemma (Restatement of Lemma 34). Let 8' > 0. Ler E [n] and e [d]. Assume that each of the following conditions holds with probability 4
N
(restatement of 10)
8'
1
g1+1
(restatement of 11)
VN
X VN
81411
V3 S a d.
(restatement of 12)
Then, there is multilinear polynomial in X that is within Oa(6') of X with probability 1 - 8'.
35

---

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 8'.
Lemma (Restatement Lemma 35). Let 8' as in (13), Assuming dt S nn R200) k there is choice of N (independent of i or l) such that (10), (11) and (12) hold, each with probability 1 8'
d-
The proof of this lemma is combination of the following lemmas.
Lemma 45. Assuming
d'd 11 S
N (2k))/22
we have with probability 1 8' that d
1 8
S
Lemma 46. Assuming
8:28+3
2
1
S
N
k/2
we have with probability 1 & that
N
Xis
-
1
S 81411
Note that for the above condition on 1 to be meaningful (we need 17 > 0), we also need to ensure that
2d
822d43
Lemma 47. Assuming
" S
(2k)*/2
and
100d
N > 8/2d43
we have for any with probability
that
N
< 81d+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 7 in the lemma statement ensures that the conditions on 7) in Lemmas 45, 46 and 47 are satisfied. We argue below that the following choice of N is enough, which will complete the proof,
02 (
3d(2443)/22
N Od
g22++
((1++1((24+))
(23)
For Lemma 45, we need (note that 1 - 1 2 since 5' is small) S Oa (28)))))))) which holds since by assumption Øब 77 < -0)(
a (22))/22
Plugging in the value of N and 8', it is enough for to satisfy
36

---

For Lemma 46, we need 1 S
3(2k)*/2 and N gr2433 The latter is clearly satisfied by the choice
2d
of N as in (23). For the former, plugging in again the values of N and 8', it is enough for 7 to satisty 50ata) (2 which again holds since 1) S (0
?) S Od
For Lemma 47, we need N 2 100
322433 and S (26) The former is again directly satisfied by the
choice of N. Furthermore, also the latter is true, again since we assume S (Qu()))-aa(()) k-* D
Next, want to prove Lemmas 45, 46 and 47.
Proof of Lemma 45. Using Markov's inequality, we get that
N j=1 X1.)
PP
I
8
Since, A approximates the moments of (0, INN) up to degree & and error r), we can compute the above expectation follows
)
N
2
E
E
X
S ANNN 1) + (1 N A/22 + N.
1o|=2
Here, we used that the expectation of (0, INN) is 0) and at most + f otherwise (since the expectation of (0,, InN) is 1 for such a:). Thus, we get that
X
most if some a, = 1 (for such a the expectation
(AN 1)82 S 8' d 1/2
P
since by assumption we have that ij (2k)
カタ N
Proof of Lemma 46.
We again use Markov's 's inequality to get
N
E
+
Σg أ== 82,)
-1) 27
P
- 1 >
gid+1
<
N
822d42
(Σn² (XR.,- -1)
We are thus interested in E
We can expand this follows
27
Σ
b.j -1)
Σ
E {
11)
1a
2
some a; 1, then the expectation will be, for some ji + j2 E [N],
E [x?3) -1) (x? 1 1)] = x2 bi
x2 - x2 h1
E
x2
+
= n) - n +1 3r
As for the proof of Lemma 45, this is true since the corresponding Gaussian moments are all 1. If no
Oj = 1, we get
E
{8 - =1
= [xxx - 2E
X3, + 1
53 h 2(1 7) +1
= 2 2n
37

---

since the second and fourth moment of Gaussian are 1 and 3 respectively. Summarized we get that
27
-1)
Σ
S (22 + 2 + N(N -133/
2N NNj + 33
Together with the above we get that
P
N
1
Σ
N
x2 4d
-
>
gid+1
2N
N 8282242
N6 + 3
j=l
2
3/j
N
8r2d+2
8'
d'
since by assumption we have that i) (2k))//2
22
&
Proof of Lemma 47. For any 3 < a < d, similar to before, we compute using Markov's 's inequality
(Nid EØ )イ,)) 2
N
X W
gld+1
Na/2
8r2d42
5=1
(Σi
21 )
We thus need to bound
{3,
We get
27
N
Σ |a|=3 22
a
< (2a)2
since for any a we have E
S (2a)a by Fact 41, since by assumption we have S
(28)272 or
in other words i < 1. Combining this with the above, we get
N
(2(2 Ne822d+2
(2a)a
P
> grd+1
Na/2
Na-28824+2
We have for any a 2 3 that ((2a)a)
< 100a and thus we get that
I
1
X
gid+1
<
(100a)a-2
No/2
2ya-28/2d+2
100a
N
822d+2
82d+3
a-2
VA
d
822d+
VA
In the third step we used that by assumption we have that N then used that a - 2 1, together with 622d a
2
1004
and d 2 a. In the last step, we
524443
< 1.
Finally, it remains to prove Lemma 34.
38

---

Proof of Lemma 34. By the assumptions, the conditions (10), (11) and (12) hold simultaneously
with probability 1 - d 1 8'. We want to construct a multilinear polynomial in Xı such that conditioned on (10), (11) and (12) is within Oz(0') of X This will complete the proof.
The construction follows [21, Proof Lemma 15J. First, note that by construction we have
8
N
x
N-
Σ
X
Expanding the sum and grouping the terms according together according how the power of is partitioned to different Xi,, we get
Xisja
x Σ Σ
da......,a,
a
I
II
VN
Sa La=
[INNJ=E[N]+=) distinet
where the c(a a,) are constants that capture how often the latter terms occur if we multiply the product out. More precisely,
e
a ... (4)
(1.....,,,
a,
is: a, t}
[=1
The strategy is now follows. We want approximate the terms
Xej
Σ
II
J. NN s=1
distinct
separately by multilinear polynomials. If ar = 1, then the terms is already multilinear and there is nothing do. Note that if L = 1, then we only have this case, from now we assume é 2 2. If a, = 2, then we want to show that
L VN
X.J. Oa(8')
Σ
II
Σ
(24)
J. s=1 VN
J.s... E[N s=1
distinet
distinct
where here and also later P is the largest s [r] such that a, 1 (we assume here and throughout this proof that in case no a, = 1, i.c. we have an emply sum and an empty product, the second term on want to make the term multilinear by removing
the LHS is 1; the reason for this is that, intuitively, all powers higher than 1, which leaves in case no a = 1). or 2 3, then we want to show that
Σ
II
00((8)
(25)
E[N ==1
distinet
Once we have shown these, the idea is to remove all terms with a, 2 3 and replace the terms for a, by the multilinear term on the LHS of (24). We get that X within Oz(5") of
c(a..... ................................ a
Σ
II s=1
VN
J
Σ =
distinet
22
which is multilinear.
The O₂ here directly also covers that we need to multiply the Oa(8') from above with the constants c(a1,...,,,, a,) and then sum over the choices of a1,... Or and over r. This then completes the proof.
39

---

Thus, it remains to prove (24) and (25). We do this using the assumptions of the lemma and by induction on r (and technically also over E the base case for was already covered above). We also inductively show that
S Os ((
Σ
(26)
VN
Ji a=1
distinct
This will be needed to prove (24) and (25).
Base 1. If r then
Xij.
a
Xi
Σ
Jr EIM ==1 distinct
In this case, we have = L. If 2, we need to show (24) and this follows directly from (11) (since g'd+1 < (a(6')). If 2 then need show (25), which follows again directly from (12). Also note that (26) holds since - Oa )
Induction step. We now assume that and that we have proven the result for all values smaller than r. The goal is to now show the result for r. We compute
E J. [NN distinct
II
L
VN
Xi.j.
Xis VN
Σ
II
Σ
VN
VN
ji.nor LE[N] s=l distinct
J+=1
J.Eli
17
Σ
II
r-1
Xij
Σ
X
VN
VN
jund E(M] sml distinct
Xis
Xish VN
Σ
II
Σ
(27)
VN
jimdd distinet
[E[N]
J.E
1)
We first want analyze the second term. Note that this term is equal to
Bg ag tame
X
Σ
Σ
II
[=1 JE 1E[N] s=1
distinct
Now, note that all terms in this sum have been considered in the induction hypothesis. Also note that ag + ar 2 (since a, 2, otherwise there is nothing prove) and thus every term in the above sum over is at most Oa(8') in absolute value by (25). Thus, we also get that
)
Σ
II
Xis VN
E
Xije VN
Oa(8").
(28)
fi....h IE[N] distinct
aml
1)
In the following it thus remains to analyze the first term in order to show (24) respectively (25)
&
Σ
II
VN
N
j. [N
J.
distinet
40

---

We now need to distinguish the cases 2 3 (in which case we need to show (25)) and = 2 (in which case we need to show (24)).
Case I: a, 2 3, proof of (25). In this case, we have, by (12), that
N
Nis
er
Σ
S
gd+11
VN
Je=l
To analyze the term
X VN
R2
Σ
II
Ji [o--IE|[]]e
distinct
we want apply the induction hypothesis. We need to again distinguish three cases, namely 0y (in which case we can use (25)), -y = 2 (in which case we can use (24)) and a, (in which case the term on the LHS of (24) are fact equal). We do this in the following.
0y-11 2 3, then, by the induction hypothesis for (25),
Σ
I 00((6")
J Ji...fr- - a=1 distinct
and thus we get, using the decomposition (27) and the bound (28) on the second term,
XiJa
Σ
II
0a( =0a(0')55aa
VN
EE( distinct
If 0,-1 = 2, then, by the induction hypothesis for (24), we have that
Σ
II
Σ
II
S
00(8))
N
Jiredh 1E[N] s=1 distinct
J.....EE
sml
By the induction hypothesis on (26), we get
(11))
11
Σ
II
< Oa
VN
81
J distinct
Combining these two, get
Σ
<0a(0') +0a
1
Jr [N[
s=1
distinct
Thus, we get (note that r < term.
d), using again the decomposition (27) and the bound (28) on the second
a.
(aa00) +0 ((1)
Σ
II
<
gd4 + -0((8) s 0z(8')
VN
Ji ENN amd
distinct
Q,-1 = 1, then r- and thus
Σ
X VN
II
Σ
d 1 s=1
JPEN] #=1
41

---

As above, we get that, by the induction hypothesis on (26),
Σ
S Od
[N
Again by using the decomposition (27) and the bound (28) on the second term, we get
Xiss VN
a,
((1) 8
1
Σ
II
SOa
8d O2((')) Oa(8).
Jirett [N distinct
Thus, for all three cases, we get that (25) still holds for r.
Case I:: ar 2, proof of (24). In this case, we have, by (11), that
ar
Lujn
- 1 S 8'0t1
For the term
Xijj
a
Σ
ju...-r-IE[[N s=1
distinct
we again need to distinguish two cases, namely dy-1 and ay
0,-1 = 2, then we have, as above, by the induction hypothesis for (24),
X
Σ
II
Σ
S Oa(8))
Jineedr-1e [E[]] s=1
E s=1 distinct
distinct
Also above, by the induction hypothesis on (26), we get
((1)
11)
r-
Σ
II
S SOd
Ju....EE(N s=1 distinct
Combining these, we have that
Xijo VN
N
Σ
Σ
VN
VN
jip..fr- E|N]
a=1
fi Me.... s=1
distinct
distinct
X VN
X iij
2r
Σ
Σ
i
Σ
VN
VN
i Je E[N]
J J....fEE N
1+=1
distinct
distinct
a
Σ
1
V
J.EN s=1
distinct
1
< +1 Oa
gid+1
5
42

---

Thus, we get that, using again the decomposition (27) and the bound (28) on the second term,
Σ
Il
E
Jimndd, E distinct
a=
EN s=1 distinet
(())
I O1( 1 Od
8dt+1 + OO((')
(8))
= Oa(0') + 0 1 +Od
8'd-1 + +0d(8)
S Oaa(6')
a, = L, then we get
Σ
X
I
Σ
VN
VN
Je-deet E
distinct
distinct
Again, by the induction hypothesis on (26). we get
Σ A distinct
II
S SOd
VN
As above, we get that
Σ
II
Xisa VN
X
I
Σ
N
VN
Jinnt JE(N] sml
J......EE [ sml
distinct
dislinct
Σ
iiia VN
X
ar
VN
J. distinct
< 0Oa
gdd+1
8'
Thus, conclude that, exactly above by the decomposition (27) and the bound (28) the second term,
X Nij.
Σ
II
Σ
VN
J1 M....rEE EINN a=1 distinct
in E[NN] s=1 distinct
1
S Oa
g1d+1
+ Oa(8')
< Oa(8').
Hence, for both cases, we get that (24) still holds for r.
Proof of (26). We can also analogously show (26). First note that if < r 1, then (26) follows directly from the induction hypothesis since the term
Σ [[ s=1
II
distinct
43

---

already appeared for r 1 by using
d/g
a2 a--1 ar
ff =r
and we can directly apply the induction hypothesis. Thus, we only need show (26) for r and in particular f 2 f then by (10), the term at most 37 S Od (())". Otherwise, f and we can do similar expansion as above to get
II f ==1
Σ
VN
distinct
Xij.
N
X
Xisi VN
Σ E distinct
II s=2
Σ
VN
VN
(x
Σ J. distinet
Σ
Xisn
Σ
We
E ViEltemmeel
X
VN
VN
VN
fa...nfr E[N] distinct
The first term then, by the induction hypothesis and (10), at most O^ (1) value. The second term be expanded as above and is thus equal to
1 in absolute
1+1p-=1
&
Σ II
VN
2=2 [N
x=2
By (24) for 1, we get that this is within Oa(5') of
Σ
VN
J2 1:7
silt
(again if 2, then the above term should be interpreted 1). This term now is, by (26) for Oa ( r-2) Note that for 2 (and thus 2) we cannot apply the induction hypothesis but
the term is and thus the bound still holds.
Combing these result, we get that
Oa(0") + +0a ( 1-
Σ
1
1 8
+
VN
g
E [EE]N
<Od Os
This is exactly (26) for r.
By induction, we have now shown (24) and (25) for all and as argued above, this completes the proof of this lemma.
44

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: For the main claims made in the abstract and introduction give proof overview in Section 2 and complete proofs in the appendices.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work the corresponding part of Section 1.2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
45

---

Justification:
For all the theoretical results, we give proof in the main part of the paper or in the appendices. For the main results, we give a proof overview in Section 2.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: Since this paper discusses theoretical results only and does not contain experi- ments, this question does not apply.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
46

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Since this paper discusses theoretical results only and does not contain experi- ments, this question does not apply.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
wwwssssssoollllaoe onPolicyl icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /ttpp.ccpppblliippppp cooollccggidess.
seabbbmmsssoonPe ssiiisolicyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Since this paper discusses theoretical results only and does not contain experi- ments, this question does not apply.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Since this paper discusses theoretical results only and does not contain experi- ments, this question does not apply.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
47

---

The factors of variability that the error bars are capturing should be clearly stated (for example, 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 the standard error of the mean.
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 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 range (e.g. negative error rates).
If error bars 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Since this paper discusses theoretical results only and does not contain experi- ments, this question does not apply.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurip:: http://nnurrissccppbb/ooel wttppttccccccccccctccccccccccclt htppppllltthiiiieeeeeppppppppptl htt//Ettiiiisiteeeeeeeeeeee csGuidelinest
Answer: [Yes]
Justification: Ethics.
The research conducted in this papers conforms with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 immediate societal impact.
Guidelines:
48

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: Since this paper discusses theoretical results only and does not contain experi- ments, this question does not apply.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make 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 experi- ments, this question does 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 dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
49

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com conddatasess has curated licenses for some datasets. Their licensing guide can help determine the license of 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 available online, the authors encouraged to reach out the asset's s creators.
13. 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 experi- ments, 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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 details about compensation (if any)?
Answer: [NA]
Justification: Since this paper discusses theoretical results only and does not contain experi- ments, 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 the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. 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 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 experi- ments, this question does not apply.
Guidelines:
50

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in 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 expect authors adhere 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.
51


Reviews:
[{"review_id": "FQQ5xIPWLp", "reviewer": "Reviewer_pSUk", "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.", "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?\n- Do you see a path to improving the sample complexity to polynomial in both n and 1/\\epsilon, rather than n^poly(1/\\epsilon)?\n- The authors have looked at Gaussian distribution in this work. What other distributions could this result be extended to?\n- 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?\n- Did the authors look into getting any sort of lower bounds for this problem?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written and easy to follow. \n- The paper makes significant progress on an open problem in learning theory by extending testable learning to PTFs.", "weaknesses": "- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind feedback and insightful questions. We appreciate that the reviewer found our paper easy to follow, and that they believe we make significant progress on an open problem in learning theory.\n\nThe main concerns of the reviewer appear to be the relative importance of the problem we study (testable learning of PTFs), and the potential applicability of our results and techniques to other problems in learning theory.\n\nTo motivate the importance of our main result, we wish to briefly discuss the importance of PTFs and the testable learning model:\n- As reviewer zio4 mentions, PTFs are very well-studied in (theoretical) computer science, and in particular in learning theory. They are a natural extension of linear threshold functions, introducing non-linearity while maintaining some amount of structure. For this reason, they are often used as a test-case to determine the boundaries of efficient learning algorithms, which is also their role in our paper.\n- The testable learning model was introduced relatively recently as an extension of the (standard) agnostic model. It has already attracted significant attention, evidenced by several publications in leading conferences (including NeurIPS) [DKK+23, GKK23, GKSV23, GKSV24, RV23]. A recurring theme in these works is an attempt to determine whether testable learning comes at an additional computational cost with respect to agnostic learning. Our work continues on this theme by proving that, qualitatively speaking, the class of PTFs can be testably learned at no additional cost (for any fixed $d$). No such results were previously available, even for $d=2$.\n\nBeyond the inherent importance of our results, we believe there is potential for future applications of our proof techniques (as mentioned by reviewer 2r1G). We refine an earlier error analysis of [Kan11], thereby translating a fooling result for $k$-independent Gaussians to a testable learning guarantee. Our methods could prove useful in future translations from existing results in approximation theory to testable learning, as well.\n\nFinally, we wish to reply to the questions by reviewer pSUk:\n1. This is the right intuition. In the context of our paper, where we only consider approximate moment-matching to test the data, testable learning corresponds to agnostic learning w.r.t. the class of distributions whose low-degree moments are close to those of a Gaussian. However, the testable model is more general than this, as it makes no assumptions on the type of testing algorithm used. This means we do not have such a correspondence in general. Agnostic learning w.r.t. classes of distributions that contain (but are broader than) the Gaussian has been considered in the literature before. A key distinction is that previous approaches typically focus on a class with nice mathematical properties (e.g., log-concave distributions), whereas in the testable model one considers classes for which membership can be verified efficiently from a small sample.\n2. For this question, we would refer the reviewer to our general rebuttal. In short, there is evidence that this is not possible, even for the easier agnostic learning model with respect to the Gaussian. This is not made sufficiently clear in the paper, and we will improve this in the revision.\n3. This is an interesting direction for potential future work: The most natural generalization that we see, based also on other works on testable learning, e.g., [GKK23], [GKSV24], [GKSV23], is to strongly log-concave distributions. However, the result in our paper does not directly generalize to any other distribution than Gaussian.\n4. For this question, we would again refer to our general rebuttal. In short, it is not clear whether the gap is inherent to the testable model or arises from our proof techniques. We inherit our dependences from [Kan11], and it seems nontrivial to improve them. Intuitively, one expects worse dependences in the testable model as one needs a stronger notion of polynomial approximation than in the (standard) agnostic model for the polynomial regression algorithm to (provably) work (compare Thm. 6 to Thm. 7). In the paper, we work with the notion of 'fooling', which also corresponds to a strong notion of polynomial approximation (namely 'sandwiching', cf. Lines 228-232).\n5. We did not study lower bounds specifically for *testable* learning of PTFs beyond the impossibility result for the approach used by [RV23] (cf. Section 2.4). (As mentioned in our answer to question 2, there is a lower bound for agnostic learning that also applies to the testable setting). However, we think it is an interesting future research direction to either prove a computational gap between agnostic and testable learning (w.r.t. $d$), or prove that no gap exists.\n\n[DKK+23]: Efficient Testable Learning of Halfspaces with Adversarial Label Noise, Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis, Advances in Neural Information Processing Systems 36 (NeurIPS 2023)\n\n[GKK23]: A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity, Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari, Proceedings of the 55th Annual ACM Symposium on Theory of Computing\n\n[GKSV23]: Tester-Learners for Halfspaces: Universal Algorithms, Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan, Advances in Neural Information Processing Systems 36 (NeurIPS 2023)\n\n[GKSV24]: An Efficient Tester-Learner for Halfspaces, Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan, The Twelfth International Conference on Learning Representations\n\n[Kan11]: k-Independent Gaussians Fool Polynomial Threshold Functions, Daniel M. Kane, 2011 IEEE 26th Annual Conference on Computational Complexity\n\n[RV23]: Testing Distributional Assumptions of Learning Algorithms, Ronitt Rubinfeld, Arsen Vasilyan, Proceedings of the 55th Annual ACM Symposium on Theory of Computing", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0DOK0dUsrQ", "reviewer": "Reviewer_2v3u", "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", "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": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Testing of polynomial threshold functions is a very natural problem and the testable learning paradigm is also very natural. The authors present the first such testable learning algorithm in the agnostic learning setting for PTFs.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the anonymous reviewer for their feedback and questions. We are happy that the reviewer finds testable learning, particularly of PTFs, to be a very natural topic.\n\nThe primary concern of the reviewer appears to be the dependence of our results on the error $\\varepsilon$ and the degree $d$ of the PTF. In particular, that this dependence impacts the practical relevance of our results. While this is certainly a fair criticism, we would like to point out that:\n- By considering the testable model (rather than the standard agnostic model), we are actually taking a step *towards* practicality. Indeed, in the standard agnostic model, one makes assumptions on the distribution of the data which cannot be verified algorithmically (neither in theory nor in practice). On the other hand, in the testable model, one relies only on properties of the data which can be verified directly (in our case, via moment matching). The testable model is therefore harder (leading to worse dependences on the problem parameters), but also a better reflection of practical reality.\n- Even in the (easier) agnostic model, the runtime dependence of known algorithms on $\\varepsilon$ and $d$ is quite bad, and moreover, this dependence cannot be improved much under typical hardness assumptions. In particular, under these assumptions, it is not possible to find an algorithm which is polynomial both in $n$ and in $1/\\varepsilon$. For instance, [Kan11a] shows a runtime of $n^{O(d^2/\\varepsilon^4)}$, which is beyond practical computation already when, say, $d=2$ and $\\varepsilon = 0.25$.\n- The primary motivation of our paper is to gain further theoretical understanding of which learning problems might be 'hard' or 'easy' in some asymptotic sense. This follows a long line of papers in learning theory, some of which appeared in earlier editions of NeurIPS. Our main goal was to show that, for any fixed $d$ and $\\varepsilon$, PTFs can be testably learned in polynomial time in $n$, thus qualitatively matching the agnostic setting. We believe that our result, while not immediately applicable in practice, is nonetheless of interest to the audience of NeurIPS.\n\nWe give a more detailed explanation of why our dependence on $d$ is worse than in the agnostic model in our general rebuttal. In short, we inherit our dependence from [Kan11], and it seems nontrivial to improve them. We think determining the best-possible dependence is an interesting direction for future research.\n\nThe reviewer asks specifically whether improvements are possible for small values of $d$. This is as an interesting suggestion. We rely on the 'fooling' result [Kan11] because it applies to PTFs of arbitrary degree. For PTFs of degree $d=2$ an earlier paper [DKN10] achieves a similar result to [Kan11], but with better (and more explicit) dependence on $\\varepsilon$. It would be interesting to see if the result of [DKN10] can be translated to testable learning to achieve better dependence for $d=2$. However, we note that such a translation would likely require substantial additional technical effort. As our focus in this paper was to achieve a result for all choices of $d$ simultaneously, we did not pursue this direction.\n\n[Kan11]: k-Independent Gaussians Fool Polynomial Threshold Functions, Daniel M. Kane, 2011 IEEE 26th Annual Conference on Computational Complexity\n\n[Kan11a]: The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions, Daniel M. Kane, computational complexity vol. 20\n\n[DKN10] Bounded Independence Fools Degree-2 Threshold Functions, Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Iu80U8LURa", "reviewer": "Reviewer_2r1G", "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].", "questions": "see weakness above.", "limitations": "the authors have addressed the limitations properly.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provided the first sample and computational complexity on testably learning PTFs, showing that testably learning PTFs is qualitatively similar in hardness to agnostic learning PTFs. To reach this result, the authors overcome a handful of technical obstacles that arose in adapting the fooling techniques to testable learning. Critically, the authors constructed a new low-degree polynomial to approximate the PTFs based on [Kane11] with refined approximation error bounds. The techniques the authors applied here could be of independent interest.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their kind feedback. We are encouraged by the fact they appreciate that we give the first result on testably learning PTFs.\n\nWe agree with the reviewer that it would be interesting future work to try to improve the runtime, potentially to $n^{\\mathrm{poly}(d/\\varepsilon)}$. We address the dependence of the runtime on $d$ in the general rebuttal. Briefly, our worse runtime dependence on $d$ (w.r.t. the agnostic model) is inherited from the result of [Kan11], which we build on. An improvement of the runtime using our techniques would directly improve the result of [Kan11], which has stood for over 10 years. Furthermore, under widely believed hypotheses, the best runtime we could hope for is $n^{\\mathrm{poly}(d/\\varepsilon)}$. \n\n[Kan11]: k-Independent Gaussians Fool Polynomial Threshold Functions, Daniel M. Kane, 2011 IEEE 26th Annual Conference on Computational Complexity", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RBztZyVfbk", "reviewer": "Reviewer_zio4", "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. \n\nAlmost all existing agnostic learning algorithms are distribution-specific, i.e. they assume the examples are drawn from some distribution, for example a Gaussian distribution. \n\nA 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). \n\nTestable 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).\n\nThe 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)}$}. \n\nThe 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.\n\nIn 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.", "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": "I think that the limitations are discussed adequately", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Polynomial threshold functions are an extremely well-studied class of hypotheses that has been the focus of many works in learning theory (including in works that appeared in NeurIPS). \n- Previously no testable learning algorithms were known even for degree-2 polynomial threshold functions.\n- The run-time of $n^{poly(1/\\epsilon)}$ qualitatively matches the best run-time for the agnostic learning of polynomial threshold functions. For example, existing hardness results preclude run-times such as $poly(n/\\epsilon)$ or $n^{polylog(1/\\epsilon)}$.\n- Studying polynomial threshold functions naturally extends previous works that study linear threshold functions.", "weaknesses": "-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)}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the anonymous reviewer for their kind feedback. We are encouraged that the reviewer believes the problem we study is well-motivated and naturally extends previous work and that the reviewer appreciates that our work qualitatively matches existing lower bounds even for the agnostic setting.\n\nWe agree that it is conceivable (but likely difficult) that the runtime dependence on $d$ could be improved (or potentially lower bounds could be established). We address this in more detail in the general rebuttal and would refer the reviewer there. We think of this as an interesting direction for future research.\n\nRegarding the question raised by the reviewer, we were also somewhat surprised that we do not need an analogue of Carbery-Wright for moment-matching distributions. On a high-level, the reason is as follows. The point in the analysis when we need such an anti-concentration result is once we have shown that $\\mathbb{E}[\\mathrm{sign}(p(X) \\pm O_d(\\varepsilon^d))] \\approx \\mathbb{E}[\\mathrm{sign}(p(Y))] \\pm O(\\varepsilon)$ (where as in our paper $Y$ is Gaussian and $X$ is approximately moment-matching). Now, we would like to say that the left-hand side is roughly the same as $\\mathbb{E}[\\mathrm{sign}(p(X))]$, which would exactly be an analogue of Carbery-Wright for moment-matching distribution (i.e. showing that the probability that $p(X)$ is small is low). However, the trick here (which was already used in [Kan11]) is to apply the above to the polynomial $p \\mp O_d(\\varepsilon^d)$ and thus shift the additional factor to the side with the Gaussian $Y$, where we then can apply Carbery-Wright (for Gaussians).\nThus, once we have a result relating $\\mathrm{sign}(p(Y))$ and $\\mathrm{sign}(p(X) \\pm O_d(\\varepsilon^d))$, by changing the polynomial slightly, we can shift the additional factors to the $Y$ side which allows us to use Carbery-Wright for the Gaussian instead of an extension to approximately moment-matching distributions.\n\n[Kan11]: k-Independent Gaussians Fool Polynomial Threshold Functions, Daniel M. Kane, 2011 IEEE 26th Annual Conference on Computational Complexity", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UJDo3BRKa1", "reviewer": "Reviewer_9MWZ", "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.\n\nThe paper completes itself with proof that push-forward cannot learn PTF and that fooling is the best they can have.", "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": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The topic is very interesting, as there is a line of work on general testable learning and testable learning in specific classes like halfspace. Testable learning PTF is the natural next step.\n\nThough the authors use the technique of reducing testable learning to fooling from previous work, it seems the analysis of the construction of a fooling for multilinear PTF is also an important technique. As the authors mentioned, the previous fooling construction [GKK23] only works for degree 2 PTF, and the construction from [Kane19] needs some careful analysis to work for PTF with more than constant degree.\n\nThe paper is complete as they also show fooling is necessary as another more direct approach cannot testably learn PTF.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for the kind feedback. We appreciate that the reviewer thinks of testable learning of PTFs as a natural problem to consider.\n\nThe primary motivation for including the impossibility result for proving testable learning guarantees via the push-forward is to show that a straightforward approach (which yields reasonable results for halfspaces [RV23]) does not yield anything for PTFs. This in turn motivates our use of the (more complicated) techniques of Kane [Kan11] (i.e., fooling). Thereby, it partially explains the difference in dependence on $d$ between our result and existing results for agnostically learning PTFs.\n\nRegarding the question raised by the reviewer, we think the following are the main technical contributions of our paper, and we plan to emphasize these more in the revision:\n- First, as already alluded to by the reviewer, we bound the size of additional error terms arising from a Taylor expansion (see lines 290-307 of our paper), which do not appear in [Kan11]. We could imagine that our analysis of these terms could also be applied to different testable learning problems in the future.\n- Second, we generalize the arguments given by Kane to move from multilinear to arbitrary PTFs (lines 335-346 of our paper). There, we showed that even under the weaker assumption of approximate moment-matching, we can show that his construction also works in our setting. In particular, we were able to circumvent the use of moments of high degree (i.e., depending on $n$), which would have given us only quasi-polynomial runtime, i.e., $n^{\\log(n)}$. On the contrary, we showed that fooling arbitrary PTFs needs the same degree of moment-matching as fooling multilinear ones, which allowed us to conclude our main result.\n\n[Kan11]: k-Independent Gaussians Fool Polynomial Threshold Functions, Daniel M. Kane, 2011 IEEE 26th Annual Conference on Computational Complexity\n\n[RV23]: Testing Distributional Assumptions of Learning Algorithms, Ronitt Rubinfeld, Arsen Vasilyan, Proceedings of the 55th Annual ACM Symposium on Theory of Computing", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
First and foremost, we would like to thank the reviewers for their time and valuable feedback. We appreciate that many of the reviewers consider testably learning PTFs as a natural and well-motivated problem.

Several reviewers correctly pointed out that the dependence of our runtime on $d$ (the degree of the PTF) is worse than in the (standard) agnostic setting. We inherit this dependence from the result in [Kan11] since we modify their construction. We note that the dependence in our result is no worse than in [Kan11], even though it holds in a strictly more general setting. Any improvement to our dependence would immediately imply an improvement over the results in [Kan11]. While in [Kan11] it was speculated that such a better dependence is conceivable, this was not achieved since the first dissemination of the result over ten years ago. In light of this, achieving a better dependence on $d$ is a great, but likely difficult open question for future work. It is also related to the intriguing question whether a strictly larger runtime is necessary for testable learning over agnostic learning. We would also like to highlight that our impossibility result (Section 2.4) rules out a natural, "simpler" approach to prove guarantees for testably learning PTFs. In some sense, this shows that achieving better runtime dependences for testably learning PTFs is likely difficult without also improving the result of [Kan11].

Furthermore, we would like to stress that even for $d = 2$, our result is the first for testably learning PTFs. Moreover, as pointed out by reviewer zio4, for any fixed $d$, our dependence on $\varepsilon$ is qualitatively optimal in the sense that it matches known lower bounds (which hold even in the simpler agnostic setting). In particular, for a fixed $d$, our runtime scales as $n^{\mathrm{poly}(1/\varepsilon)}$ and known lower bounds (either in the SQ model [DKPZ21] or under standard cryptographic assumptions [Tie23]) imply that this is necessary. For example, these lower bounds rule out runtimes such as $\mathrm{poly}(n, 1/\varepsilon)$.

Kind regards, the Authors




[Kan11]: k-Independent Gaussians Fool Polynomial Threshold Functions, Daniel M. Kane, 2011 IEEE 26th Annual Conference on Computational Complexity

[DKPZ21]: The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model, Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis, Proceedings of Thirty Fourth Conference on Learning Theory

[Tie23]: Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems, Stefan Tiegel, Proceedings of Thirty Sixth Conference on Learning Theory

Meta-review: 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.
Decision: Accept (poster)