Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces
It has been a long-standing problem to efficiently learn a halfspace using as few labels as possible in the presence of noise. In this work, we propose an efficient Perceptron-based algorithm for actively learning homogeneous halfspaces under the uniform distribution over the unit sphere. Under the bounded noise condition [49], where each label is flipped with probability at most η < 1 2 , our algorithm achieves a near-optimal label complexity ofÕ
the adversarial noise condition [6,45,42], where at most aΩ(�) fraction of labels can be flipped, our algorithm achieves a near-optimal label complexity ofÕ
. Furthermore, we show that our active learning algorithm can be converted to an efficient passive learning algorithm that has near-optimal sample complexities with respect to � and d.
This paper analyzes a variant of the Perceptron algorithm for active learing of 
origin-centered halfspaces under the uniform distribution on the unit sphere. It 
shows that their algorithm learns using a nearly tight number of samples in the 
random independent noise of bounded rate. Previous work had exponentially worse 
dependence on the noise rate. In addition, it shows that this algorithm can deal 
with adversarial noise of sufficiently low rate. The latter result improves 
polynomially on the sample complexity but requires a stronger condtion on the noise 
rate. 
The assumptions in this setting are very strong and as a result are highly unlikely to 
hold in any realistic problem. At the same time there has been a significant amount 
of prior theoretical work on this and related settings since it is essentially the only 
setting where active learning gives an exponential improvement over passive 
learning in high dimensions. This work improves on some aspects of several of 
these works (although it is somewhat more restrictive in some other aspects). 
Another nice feature of this work is that it relies on a simple variant of the classical 
Perceptron algorithm and hence can be seen as analyzing a practically relevant 
algorithm in a simplified scenario.   
So overall this is solid theoretical contribution to a line of work that aims to better 
understand the power of active learning (albeit in a very restricted setting). A 
weakness of this work is that beyond the technical analysis it does not have much 
of an algorithmic or conceptual message. So while interesting to several experts it's 
unlikely to be of broader interest at NIPS. 
---response to rebuttal ---
>> "This label query strategy is different from uncertainty sampling methods in practice, which always query for the point that is closest to the boundary. We believe that our novel sampling strategy sheds lights on the design of other practical active learning algorithms as well."
This is an interesting claim, but I do not see any support for this in the paper. The strategy might be just an artifact of the analysis even in your restricted setting (let alone a more practical one). So my evaluation remains positive about the technical achievement but skeptical about this work making a step toward more realistic scenarios.