Before revision:  Our main contribution is a state-of-the-art online active learning algorithm that achieves near-optimal attribute efficiency, label and sample complexity under mild distributional assumptions. In particular, under the conditions that the marginal distribution is isotropic log-concave and \nu = \Omega(\epsilon), where \epsilon \in (0, 1) is the target error rate, we show that our algorithm PAC learns the underlying halfspace in polynomial time with near-optimal label complexity bound of O\big( s \cdot polylog( d, \frac{1}{\epsilon})\big) and sample complexity bound of \tilde{O}\big( \frac{s{\epsilon} \cdot polylog(d)} {\epsilon} } \big).
After revision:  Our main contribution is a state-of-the-art online active learning algorithm that runs in polynomial time, and under the conditions that the marginal distribution is isotropic log-concave and \nu = \Omega(\epsilon), where \epsilon \in (0, 1) is the target error rate, we show that our algorithm PAC learns the underlying halfspace in polynomial time with near-optimal label complexity bound of O\big( s \cdot polylog( d, \frac{1}{\epsilon})\big) and sample complexity bound of \tilde{O}\big( \frac{s{\epsilon} \cdot polylog(d)} {\epsilon} } \big).