Before revision:  }\big) \tilde{O}\big({\epsilon} \cdot polylog(d) }\big) As an immediate corollary of our main result , we show that under the more challenging agnostic model \mbox{%DIFAUXCMD \cite{kearns1992toward }\hspace{0pt}%DIFAUXCMD }  where no assumption is made on the noise rate  , our active learner achieves an error rate of O(OPT) + \epsilon with the same running time and label and sample complexity, where OPT is the best possible error rate achievable by any homogeneous s-sparse halfspace. Our algorithm builds upon the celebrated Perceptron while leveraging novel localized sampling and semi-random gradient update to tolerate the adversarial noise. We believe that our algorithmic design and analysis are of independent interest, and may shed light on learning halfspaces with broader noise models .
After revision:  }\big) \tilde{O}\big({\epsilon} \cdot polylog(d) }\big) As an immediate corollary of our main result , we show that under the more challenging agnostic model \mbox{%DIFAUXCMD \cite{kearns1992toward }\hspace{0pt}%DIFAUXCMD } where no assumption is made on the noise rate , our active learner achieves an error rate of O(OPT) + \epsilon with the same running time and label and sample complexity, where OPT is the best possible error rate achievable by any homogeneous halfspace .