Testably Learning Polynomial Threshold Functions

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.

The 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.

Regarding 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:

• 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.
• 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.

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

[RV23]: Testing Distributional Assumptions of Learning Algorithms, Ronitt Rubinfeld, Arsen Vasilyan, Proceedings of the 55th Annual ACM Symposium on Theory of Computing

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.

We 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.

Regarding 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). Thus, 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.

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

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.

We 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)}$.

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

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.

The 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:

• 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.
• 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$.
• 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.

We 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.

The 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.

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

[Kan11a]: The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions, Daniel M. Kane, computational complexity vol. 20

[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

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.

The 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.

To motivate the importance of our main result, we wish to briefly discuss the importance of PTFs and the testable learning model:

• 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.
• 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$.

Beyond 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.

Finally, we wish to reply to the questions by reviewer pSUk:

1. 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.
2. 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.
3. 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.
4. 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).
5. 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.

[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)

[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

[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)

[GKSV24]: An Efficient Tester-Learner for Halfspaces, Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan, The Twelfth International Conference on Learning Representations

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

[RV23]: Testing Distributional Assumptions of Learning Algorithms, Ronitt Rubinfeld, Arsen Vasilyan, Proceedings of the 55th Annual ACM Symposium on Theory of Computing