An Efficient Tester-Learner for Halfspaces

In this paper, the authors give the first computationally efficient tester-learner for learning halfspaces where the target distribution is the d-variate Gaussian and the label noise is Massart or adversarial. The tester-learner framework was recently proposed as a generation to the distribution-specific learning setting where the algorithm needs to accept a dataset whenever it comes from a target distribution and needs to achieve the agnostic learning guarantee (error = $opt + \varepsilon$) whenever it accepts. Previous work only gave a sample-optimal tester learner for the same problem which was not computationally efficient. The main technical novelty in this work is tester that looks at the labels as opposed to the label-oblivious testers previously designed. For the adversarial noise setting, the authors achieve the suboptimal risk $O(opt) + \varepsilon$.

The authors build on the non-convex optimization approach of [DKTZ] which uses the a smoothed version of the ramp loss as a surrogate to the zero one loss. Although this is a non-convex function, it was shown that the stationary points are good solution which can be recovered by projected SGD as the first step under the Gaussianity assumption. In the testing-learning framework, we need to additionally check the following assumption: the probability masses of certain regions are proportional to their geometric measures. The tester checks local properties of the distribution in regions described by the stationary points using moment matching techniques. Naively, such a check could only guarantee the empirical mass is additively close to the true mass. However, using a refined moment test conditioned on a band based on the stationary vector (similar to the existing localization-based refinement techniques of Awasti et al. 2017) they could get the stronger multiplicative guarantee. This allows them to argue that if the test passes, the stationary points will indeed be close to the true weight vector in angular distance. This in turn means the returned vectors are good solutions using properties of Gaussian. The later step results in a larger error for the adversarial noise setting as opposed to the Massart noise setting.

This paper proposed a polynomial-time algorithm for learning halfspaces on testable fixed well-behaved distributions under Massart and adversarial noise. Unlike its prior works, it takes the labels into account and checks local properties of the distribution by testing the moments of the conditional distributions around the stationary points.

This paper worked on the problem of learning Gaussian Halfspace (with extension to more general stongly logconcave distributions) with Massart noise and agnostic noise, under the Tester-Learner models. The authors provided the first tester-learner algorithm with polynomial iteration and sample complexity, that achieves $\mathrm{OPT} + \epsilon$ error for the Massart noise and $O(\mathrm{OPT}) + \epsilon$ error for the agnostic noise (under Gaussian marginal). The technical contriutions of this paper are mainly the following: the authors devised more efficient testers using information of labels and exploiting the local geometric structure of the distribution (the condition probability on a band $P[v\cdot x \in [\alpha, \beta] | w\cdot x\in[-\sigma,\sigma]]$); they also showed that for some carefully designed loss function $\mathcal{L}_\sigma$, its stationary points $w$ are also vectors that are close (in angle) to the optimal solution $w^*$, under some distributions that are efficiently testable.

This paper is a further exploration of the testable learning framework proposed by Rubinfeld and Vasilyan. The main feature of this framework is that it requires learning algorithms that learn near-optimal predictors whenever the input training sample passes a test (soundness), and also training samples pass the test whenever the distributional assumptions are met (completeness).

The paper gives polynomial-time testable learning algorithms for halfspaces when the marginal distribution is isotropic log-concave and: (a) under Massart noise, guarantee error at most OPT + \epsilon. [Theorem 4.1] (b). under adversarial noise, guarantee error at most O(OPT) + \epsilon. [Theorem 5.1]

We wish to thank the anonymous reviewers for their constructive feedback.

Since two reviewers (sjRf and Ccgf) have asked about a more detailed comparison with [GKSV '23], we summarize the key value of this paper in this global response as follows:

• While it is true that [GKSV '23] achieves stronger results, this paper is the one that lays the fundamental groundwork for their approach, as they also acknowledge. Specifically, we are referring to the key framework of running SGD on a nonconvex surrogate and then running tests that estimate statistics of the conditional distribution restricted to a strip (where the strip itself is defined in a label-aware way in terms of an SGD stationary point). The contribution of [GKSV '23] is the extension of our tester to have a “universal” property, and the use of certifiable hypercontractivity in order to achieve this.
• In this paper, the tests are based on moment-matching, whereas [GKSV '23] uses a complicated semidefinite program resulting from a sum-of-squares relaxation. While such SDPs do technically run in polynomial time, they are notoriously slow in practice. In contrast, moment-matching is simple and easy to implement.
• From a conceptual point of view, this paper can also be seen as further investigating the power of moment matching as a primitive for testable learning. Since it is a fundamentally different type of test than say a sum-of-squares hypercontractivity test, it is subject to different (and potentially less restrictive) technical barriers. For example, the work of [GKSV '23] is only able to handle the class of general log-concave distributions under the assumption that they are certifiably hypercontractive (which is itself implied by the KLS conjecture). For our method, certifiable hypercontractivity is not a barrier and it is an interesting open question whether it can be extended to accept a target that is a general log-concave distribution without assuming the KLS conjecture.

The authors consider the testable learning model, where (1: soundness) the accuracy of the output hypothesis is near optimal when the training test passes the provided test, and (2: completeness) training sets drawn from a target distribution pass the test. They give the first computationally efficient algorithm for learning halfspaces in this model, achieving OPT$+\epsilon$ under Massart noise and any fixed strongly log-concave distribution and $O(\text{OPT})+\epsilon$ under adversarial noise and Gaussian distribution. The proofs are an interesting combination of techniques from learning theory including non-convex optimization and moment matching.

Reviewers agree the results are significant. The main shortcoming is that many of the results are superseded by a later paper (Gollakota, Klivans, Stavropoulos, Vasilyan, NeurIPS 2023). Given the fast pace of research in the field, I don't treat this as a reason to reject the paper.

Accept (poster)