Active Learning of General Halfspaces: Label Queries vs Membership Queries

Summary

This paper studies the problem of actively learning non-homogeneous half-spaces under Gaussian distribution. It shows that in the pool based model, any active learner cannot do better than the passive learner in terms of label complexity, unless exponentially many unlabelled examples are drawn. On the other hand, it shows that in the membership query model, there exists active learner that can outperform the passive learner, thus demonstrating a separation between these two models.

Strengths

1. This paper settled down the open problem whether it is possible to learn non-homogeneous half-spaces using $O(d\log(1/\epsilon)+\min(1/p,\epsilon))$ labelled data and $O(d/\epsilon)$ unlabelled data under the Gaussian distribution in the pool-based active learning setting. It then shows that this label complexity is achievable under the membership query model, thus there's a separation of the two models. This result and technique used is complete and novel. 2. This paper is well-organized. It gives enough motivation and background information to the problem and discussed related work. 3. The writing is very clearly for most of the part. Notations are well-defined and the math is rigorous.

Weaknesses

1. (I would adjust my rating based on the response of this point). The only real issue I have here is that I'm not fully convinced by your conclusion that "in the pool-based model, active learning has no improvements over passive unless the pool size is exponential". The passive bound has an explicit dependence on $\epsilon$ while your Theorem 1.1 doesn't. It only has a dependence on $1/p$. If $p$ is constant, your conclusion is not correct. So your conclusion only holds for some regime of $p$. This also makes me wonder how tight this lower bound is, is it possible to have a lower bound with $\epsilon$ appearing explicitly here? 2. The lower bound holds for the realizable case while the upper bound holds for the upper bound is for the agnostic setting. This leaves a gap in the realizable upper bound and potentially easier algorithms. 3. The paper is getting a bit too technical at the end. All the writings are extremely well, especially the lower bound part, but it gets more technical in section 3 and it's hard to follow for me. i) I think it's better to give some examples in section 3, explaining the intuition more and moving some of the lemmas to appendix. ii) It feels like your MQ algorithm isn't completely new but used the framework/idea/techniques (like the localization) from previous works. It's better to start with a simpler algorithm and explain what's new in your paper. iii) It might be better to have a conclusion section to discuss some future directions. 4. There're some very tiny typos. i) In the abstract, your lower bound is $\Omega(d/\log(m)\epsilon)$ while in your theorem it is $\Omega(d/\log(m)p)$. ii) In algorithm 1, what's the subroutine TEST C? In the appendix you have a subroutine named ANGLE TEST. iii) Line 337, you typed "the length of" twice.

Questions

1. As I mentioned, is there a better MQ bound or simpler algorithm in the realizable case? In the realizable case is it possible to get $\text{OPT}+\epsilon$ exactly? 2. Is there some distribution that is natural and actively can have an advantage over passive learning? I still believe active learning would have some advantages in many instances over passive for learning non-homogenous half-space in the pool-based setting. 3. On the other hand, is it easy to extend your result to more general distributions? Like log-concave distributions?

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

It's better to have a conclusion section to talk about future directions.

Summary

This paper first provides a lower bound on active learning using label queries. This lowerbound is nearly tight compared with upperbound for label queries. To get around the lowerbound, the authors study active learning using membership query, which means the algorithm can directly access the random function that gives the label y to x. The membership query is clearly stronger than label queries and hence, the authors manage to prove an upperbound. The authors also mentioned lowerbounds in membership query from other work.

Strengths

The settings of active learning using label query and membership query are very natural and well-studied. The authors manage to provide a nearly-tight lowerbound and an interesting upperbound for general halfspace. The strategy they use in both proofs like considering negative examples in samples for lowerbound and finding a subclass using good initialization and fine-tuning seems to be intuitive and interesting.

Weaknesses

I think the results are very interesting but the paper writing can be improved.

Questions

How do you know whether to use initialization for an extremely large threshold(section F) or not (section E)? I think it would make the paper easier to read if the authors could describe what 3.1 is doing at high level. I think there is a small notation error in A.2(sample (x,y)\sim D instead of N(0, I)).

Rating

7

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

N/A

Summary

The paper studies the question of active learning halfspaces over $\mathbb{R}^d$, under the Gaussian distribution in two different models: Label queries and membership queries. In the label queries model, the authors prove a lower bound implying that the learner must have a pool of size $exp(d)$ in order to do better (in terms of samples/queries) than a passive learner. In the membership queries model, the authors prove that the above lower bound can be circumvented by using the strength of membership queries, and provide an upper bound which is better than the optimal sample complexity bound of passive learners. The upper bound is given by an efficient semi agnostic learner (a learner with risk guarantee of the form $O(opt + \epsilon)$).

Strengths

1. The studied problem is of a fundamental nature. 2. The lower bound and its circumvention via membership queries are interesting. 3. The upper bound algorithm is efficient.

Weaknesses

1. I find the introduction not clear enough. For example, I do not understand how the upper bound in line 56 settles with the lower bound in line 54. The upper bound has no dependence on $1/\epsilon$. Also, how does Theorem 1.1 relate to those bounds? The bounds relate to the uniform distribution while the theorem relates to the Gaussian distribution. 2. Line 93 says: "The overhead term cannot be avoided in the agnostic setting...". It is not discussed whether it can be avoided in the realizable setting. 3. While the results are potentially interesting, I think that the presentation of the paper needs to be improved. High level ideas and technical details are mixed, which makes the paper hard to follow. 4. No discussion on possible future research. 5. The results are applicable to a relatively limited setting of halfspaces under the Gaussian distribution. 6. While the upper bound algorithm is efficient, it only gives a "semi-agnostic" guarantee in the form of $O(opt + \epsilon)$. However, the constant hidden in the $O$ notation is not specified (at least not in the theorem), and it can sometimes be important. In some scenarios it might be perfectly reasonable that $opt = 1/1000$. So, if the hidden constant is at least $500$, the guarantee is no better than random guessing in those cases. It could be interesting to design an inefficient learner with better risk guarantees.

Questions

Questions: 1. In line 157, I don't understand what does it mean that an argument is "hard to formalize". Do you mean that it is counter-intuitive? 3. In line 205, do you mean that an upper bound $\epsilon$ on the noise level is *given* to the learner beforehand? Suggestions: 1. I would recommend writing a "technical overview" section that separates the high-level novel ideas from known techniques and technical details. 2. Add a discussion on future research. For example, in Theorem 1.2: can we do better in the realizable setting? Can we do better by using an inefficient learner? Typos: 1. Line 337: "the length of the length of" 2. Line 389: "unfortinately:

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

Yes.

Summary

This paper considers active learning of general (non-homogeneous) halfspaces under Gaussian distribution. Define p=P(Y=-1). On the one hand, it proves that, roughly speaking, with standard label queries, one cannot learn a classifier with O(opt+epsilon) error that requires polynomially many unlabeled samples and $O(d\log\frac{1}{\epsilon}+\text{min}(1/p, 1/\epsilon))$ labels. On the other hand, with membership queries, it gives a computationally efficient algorithm that achieves $O(d\text{poly}\log(\frac{1}{\epsilon})+\text{min}(1/p, 1/\epsilon))$.

Strengths

- This paper considers an interesting open problem learning theory: a lot of research has considered learning homogeneous halfspaces, but what is the limit for non-homogeneous halfspaces? It gives an interesting result that it can't be very efficiently learned under the standard label query paradigm, even assuming gaussian distribution and noise-free, while membership query could help. - The proposed method is sound and technically non-trivial, though I have not checked proofs in Appendix. - The paper is written clearly in general, and explains high-level intuitions well.

Weaknesses

- For the upper bound / algorithmic result, it looks to me it is highly depended on the Gaussian (or "nearly" symmetric) assumption. Does that mean that membership queries may not even be enough if the data distribution is more general? - Also for the upper bound / algorithmic result, it aims at achieving O(opt+epsilon) instead of opt+epsilon error. I understand that in general the latter is proven to be hard, but it would be nice if there is a discussion about if the latter can be achieved with some assumptions about noise.

Questions

N/A

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This paper studies the classical problem of distribution-dependent---here standard normal disitrbution---active learning of non-homogeneous halfspaces using label and membership queries in the realizable and agnostic setting. There are two main contributions. 1. A strong lower bound in the label query setting essentially showing that no significant improvement against (passive) supervised learning is possible (as long as no exponential number of unlabeled samples are used). 2. An upper bound in the membership query setting achieved by an efficient (poly-time) algorithm. The achieved bounds depend on the bias $p$ (of the target halfspace $w^Tx+p\geq 0$), which make these results target/hypothesis dependent. These results extends previous ones on the simpler problem of learning homogeneous halfspaces, where exact rates have been known and fit into similar line sof work, e.g., results under the uniform distribution on the sphere, instead of Gaussian.

Strengths

* Strong near-optimal bounds for a well studied setting of actively learning halfspaces * Devise a near-optimal poly-time algorithm in the membership query setting, while most previous work ignore computational aspects or provide only exponential time algorithms.

Weaknesses

While interesting, technically deep and novel, the results are somewhat limited, due to the quite strong standard normal assumption, see question below. Comments: * Maybe consider changing adding something like "under the Gaussian distribution" to the title. Otherwise it might seem a bit too general. ---rebuttal--- raised score from 5 to 6.

Questions

While interesting, the standard normal assumption is rather strong and limiting. Are there any possibilities to extend your results to broader families of distributions, e.g., sub-Gaussian, log-concave, ... ? Even just more general Gaussians ($\mathcal{N}(\mu,\Sigma)$)?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

See question.