Efficient Testable Learning of Halfspaces with Adversarial Label Noise

Summary

This paper studies the problem of learning halfspaces under Gaussian distribution and adversarial label noise in the testable learning framework of Rubinfeld and Vasilyan (STOC'23). In this setup, the learning algorithm, given a few training examples drawn i.i.d. from some unknown distribution $\mathcal{D}$, may either *accept* and returns a hypothesis or *reject*. The goal is to satisfy the following two natural constraints: - Completeness: If the marginal of $\mathcal{D}$ is indeed Gaussian, the algorithm should accept w.h.p. - Soundness: The probability that the learning algorithm accepts and returns an inaccurate hypothesis is small. The main result is a poly-time algorithm that works for the Gaussian distribution against adversarial label noise. In particular, if $\mathsf{opt}$ is the smallest possible testing error achieved by the best halfspace on $\mathcal{D}$, the algorithm guarantees $O(\mathsf{opt}) + \epsilon$ error in time $\mathrm{poly}(d/\epsilon)$. Prior work achieves $\mathsf{opt} + \epsilon$ error but requires $d^{\mathrm{poly}(1/\epsilon)}$ time. A first building block is a weak learner (given in Proposition 2.1) that outputs a weight vector $v$ that is $O(\sqrt{\mathsf{opt} + \eta})$-close in time $d^{\tilde O(1/\eta^2)}$. (This is not sufficient due to the extra square root as well as the exponential dependence on $1/\eta$.) This baseline learner is then boosted by localizing to the decision boundary of $\mathrm{sgn}(v\cdot x)$. In particular, each iteration either makes progress in improving the accuracy of $v$, or obtains a proof of non-Gaussianity in terms of moments.

Strengths

The paper studies a well-motivated and fundamental learning theory problem in the recently proposed model of testable learning. The results are strong, and the solution involves several novel and non-trivial ideas. Despite this complexity, the main paper is nicely written and achieves a great balance between intuition and technical details. I vote for accepting this paper.

Weaknesses

The algorithm only handles the homogeneous halfspaces without a bias term, and cannot achieve the $\mathsf{opt} + \epsilon$ error guarantee as in the prior work of [RV22, GKK22].

Questions

Following up on the weakness part, some discussion on whether/how the current technique could handle non-homogeneous halfspaces and/or the stronger agnostic learning guarantee would be helpful.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and 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.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

This work is purely theoretical and its limitations are in the assumptions (e.g., the concept class is the class of homogeneous halfspaces, and the "reference distribution" is a spherical Gaussian). This has been properly addressed in the paper (clearly stated in the abstract and the main paper).

Summary

Learning halfspaces is a very well studied problem in machine learning. In the agnostic (adversarial label noise) and distribution free setting, this problem has been known to be computationally intractable. As a result, there have been several works of agnostic learning in distribution specific settings (where the marginal distribution belongs to a particular family of distributions, say Gaussian or log-concave). In this scenario, the learner has an error of the form $OPT + \epsilon$, where OPT denotes the optimal 0-1 error. This however has complexity $d^{1/\epsilon^2}$, and the exponential dependency on $1/\eps$ is tight. This motivates the designing of learning algorithms that have better sample complexity with respect to $1/\epsilon$, whereas the error becomes $f(OPT) + \eps$ for some function f. In this work, the authors studied this problem in the newly introduced Testable learning framework by Rubinfeld and Vasilyan (STOC 23). Here the goal is if the tester accepts, then with high probability the output of the learning is close to some function of OPT, and if the data satisfies the distributional assumptions, the algorithm accepts. In this paper, the authors study the class of homogeneous halfspaces over $R^d$ with Gaussian marginals. This work designs a tester-learner with sample complexity $N=poly(d, 1/\epsilon)$ and runtime $poly(dN)$. Additionally, their algorithm also works in the active learning framework where the algorithm only queries the labels of a subset of the samples. The authors first design a weak agnostic learner with respect to Gaussian distribution which checks if the low degree moments of the marginal distribution approximately matches with that of Gaussian distribution (Section 2). The idea is if the moments are close, then the vector corresponding to the degree-1 chow parameters will not be far from v^* (the true vector of the half-space), see Lemma 2.3. They also design an algorithm that either reports if the marginal distribution is not Gaussian or it outputs a unit vector w (Algorithm 2 corresponding to Proposition 2.1) Once they have the weak learner, the authors will try to find a vector that has small 0-1 error with v^* by calling Algorithm 2 (Lemma 2.1) in an iterative manner. After logarithmic many iterations, they show that the probability mass of the disagreement region is bounded (Lemma 3.1). However, this process gives a collection of vectors such that one of them is close to the optimal vector v^*.The authors finally run a tournament among these candidate halfspaces corresponding to these vectors and outputs the winner hypothesis (Lemma 3.6).

Strengths

The paper gives the first algorithm for testable learning of halfspaces that runs in poly(d, epsilon). The algorithm is very nice. With the complexity pulled down drastically, a proper implementation and experimental results for this algorithm would be possible and it would be nice to see the relevance of the concept of testable learning in various applications.

Weaknesses

The usefulness of the testable learning model in real life applications is yet to be understood. The paper can only handle adversarial noise.

Questions

Can this approach be used to design tester-learners for function classes other than halfspaces.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

It is a pure theoretical work in the paradigm of testable learning - a relatively new concept whose importance is not yet fully confirmed.

Summary

This paper considers computationally efficient learning of halfspaces with adversarial noise in a recently proposed "testable" task: with high probability either reports the example distribution is not standard Guaissian, or outputs a halfspace with error of at most O(opt)+epsilon. There are existing works in a similar setting but targets the error of opt+epsilon, so their time and sample complexity is unavoidably $d^{O(1/\epsilon^2)}$. This paper relaxed the error target to O(opt)+epsilon as in previous non-testable works, and shows that the testable task can be achieved with time and sample complexity of around poly(d, 1/epsilon) and label complexity of around d log(1/epsilon). Technically, the results are obtained by (non-trivially) combining known ideas, like moment matching to assist testing, the Chow parameter (roughly speaking, E[yx]), robust mean estimation, and soft localization for learning in a label-efficient way. -- I've read the author's response and I remain positive for this paper.

Strengths

- This paper considers a recently proposed task of efficient testable learning of halfspaces with Gaussian distribution, and shows that, similar to the results in classical non-testable setting, it can be done with poly(d/epsilon) when considering constant-factor approximation. In my opinion, this result is not very surprising, but it is still interesting to know. - Most of the individual ideas used for the proof and algorithm are known to the community. On the other hand, the careful analysis to combine them in this new testable learning setting is still novel and nontrivial. - I briefly checked the proofs and they looked sound to me. - The paper is written very clearly: it clearly explains the problem and how it relates to existing work, and it organizes its technical part well so that one could follow both the high level steps and details.

Weaknesses

There are some weakensses (and I mentioned some of them above already), but I don't think they're really major: - The results are not very surprising to me, and the individual ideas used are mostly known. - It only considers standard Gaussian distributions and adversarial noise.

Questions

I don't really have any questions, but one minor comment is that since this is a relatively new setting, it might help readers understand the difficulty of the problem by explaining that one cannot simply first test if the distribution is Gaussian and then proceed with standard learning algorithms.

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.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

The paper studies the problem of efficient testable learning of half spaces under Gaussian marginals and adversarial noise. The setting of testable learning addresses the issue of restrictive assumptions on the marginal distributions (such as Gaussianity) under learning algorithms are designed. Traditionally, a learning algorithm has no guarantee when the marginal distribution is not the prescribed one. In tester-learner setting, a learning algorithm consists of a tester and a learner. The tester "certifies" that the marginal distribution satisfies certain conditions (ideally this test would be a test of whether the marginal distribution is "close" to the original distribution). Conditioned on the tester passing, the learning algorithm has the desired correctness guarantee. The main idea is that tester does not need to test for distributional closeness but rather just closeness sufficient to "fool" the learning algorithm. A recent line of work has considered the learning of half spaces in this setting. Previous work show that the halfspaces can be agnostically learnt under Gaussian marginals in time $d^{1/\eps^2}$ which is optimal if one insists on algorithms that return hypotheses that have error $OPT + \eps$. The present paper relaxes this notion to require that the hypothesis returned only has error $O(OPT) + \eps$. The paper presents a polynomial (in $d$ and $1/\eps$) time tester-learner algorithm under Gaussian marginals.

Strengths

The paper presents a natural and interesting adaptation of the localization technique for learning half spaces in the testable learning setting. The main idea is that learning algorithms designed to work under Gaussian marginals require significantly less information (for example only rely on moments and anti concentration). The paper analyses a robust version of Chow parameter recovery under the condition that the marginals match Gaussian marginals (this can be tested efficiently). Using this as a weak learner, the paper uses a localization technique to convert a weak learner (from Chow parameter recovery) to a strong learner. Again the paper uses the fact that closeness of parameter and loss for halfspaces can be efficiently tested. In summary, the paper presents a nice analysis of learning algorithm

Weaknesses

As presented the paper is too specific to Gaussian marginals.

Questions

- It would be nice to address which parts of the paper can be generalized to more general distributions? For example, what notions of testable concentration and anti concentrations would suffice for these algorithms to work. For example, would having sufficient moment decay suffice for the Chow parameter recovery?

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

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes