Summary
Background: Agnostic learning is a well-studied framework that models learning when no function is some hypothesis class F describes the data perfectly. Specifically, the agnostic learning framework requires the learning algorithm to give a hypothesis whose classification error is at most opt+$\epsilon$, where opt is the best prediction error among all hypotheses in the class F.
Almost all existing agnostic learning algorithms are distribution-specific, i.e. they assume the examples are drawn from some distribution, for example a Gaussian distribution.
A distribution-specific agnostic learning algorithm lacks in reliability, because it is allowed to output an extremely poor classifier if the examples do not come from e.g. Gaussian (or some other assumed distribution). Yet, fully eliminating such assumptions is shown to be impossible for many basic function classes (based on well-established cryptographic assumptions).
Testable learning is a framework that aims to mitigate the above mentioned limitation, by allowing the algorithm to abstain on a specific dataset if the examples do not come from the assumed distribution. Overall, this allows a user to be confident that the classifier indeed has error of at most opt+$\epsilon$, as required by the agnostic learning framework. Testable learning has been a focus of many works in recent years (see the paper for references).
The paper studies testable learning of polynomial threshold functions (PTFs) under the Gaussian distribution. I.e. the function class F considered in this work consists of functions of the form sign$(p(x))$, where p is a degree-$d$ polynomial. The work in n dimensions, with accuracy parameter $\epsilon$, the paper gives an algorithm for testable learning of constant-degree PTFs with a run-time of $n^{poly(1/\epsilon)}$}.
The paper is based on the moment-matching framework of [Gollakota, Klivans, Kothari ‘23], and shows that the direct approach used in [Vasilyan, Rubinfeld ‘23] to handle linear threshold functions cannot be extended to PTFs.
In order to apply the moment-matching framework of [Gollakota, Klivans, Kothari ‘23], the paper shows that PTFs are “fooled” by distributions whose low-degree moments are close to Gaussian moments. To do this, the paper expands on the approach of [Kane ‘11] that proves a less general statement that PTFs are “fooled” by distributions for which the marginal of every k coordinates equals to the k-dimensional Gaussian. The proof first first considers multilinear PTFs, and then reduces the case of general PTFs to that of multilinear PTFs.
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).
- Previously no testable learning algorithms were known even for degree-2 polynomial threshold functions.
- 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)}$.
- 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)}$