Summary
This work studies the problem of designing tester-learners for halfspaces in the agnostic setting and under Massart noise. In the setting of tester-learners, we do not make distributional assumptions on our samples, but rather require that our algorithm produces an accurate output whenever the input satisfies a sequence of efficiently computable tests. Further, if the samples actually come from a specific target distribution, it is required that the tests pass with high probability.
Previous tester-learners for noisy halfspaces used tests tailored towards a *specific* distribution, e.g., a specific strongly log-concave distribution. As a consequence, these testers might reject samples from a different strongly log-concave distribution although algorithmically it would have been possible to learn the underlying halfspace. The authors propose a tester which simultaneously accepts for all Poincaré distributions that satisfy some natural niceness conditions. This class includes all isotropic strongly log-concave distributions. When their tester accepts, the tester-learner outputs a halfspace achieving error $O(\mathrm{opt}) + \varepsilon$, where $\mathrm{opt}$ is the error of the optimal halfspace on the distribution of the input. For the Massart setting they can handle all isotropic log-concave distributions and achieve error $\mathrm{opt} + \varepsilon$.
The authors argue that previous works were inherently limited to work with only a single distribution since they were matching moments with this specific distribution. In their work, they overcome this issue by only checking the actual properties they need in the proof of accuracy which are not tied to any specific distribution.
Strengths
In my eyes, designing tester learners which simultaneously accept for a large class of distribution is an important step for bringing the framework of testable learning closer to practice. The motivation for testable learning was that designing algorithms that only work under specific distributional assumptions has little value in practice since likely these assumptions will not be met. Thus, we would at least like to know if we can trust the output of our algorithm when we run it on actual data or not. While previous tester-learners did have this benefit, it seems that the proposed testers "overfit" to specific distributions. However, the chances that real world data comes from any specific distribution are rather small. Thus, providing testers which work for larger classes of distributions is an important step.
On a technical level, their tester has a natural explanation that I like: It simply checks the properties that are need in the proof in the non-testable setting. Further, the paper is very well-written (except the point below).
Weaknesses
I feel that the technical overview that the authors provide might be hard to understand if the reader is not familiar with the arguments in previous work or at least the general area. It would be nice if it could be adjusted slightly to make it more accessible to a wider audience.
Also, specifically for the agnostic setting, it would be useful to compare your approximation factor to (a) testable learners that only work for one specific (or a more restricted class of distributions) and (b) non-testable learners for the same distribution class you consider.
Questions
Related to the above: In the agnostic setting, your error bound scales as $\mathrm{poly}(\lambda) (1+\gamma^4) \mathrm{opt} + \varepsilon$, where $\lambda$ is the niceness parameter of the marginal distribution and $\gamma$ the Poincaré constant. How does this compare to the non-testable learning error?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
Limitations were addressed appropriately.