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.
After revision:  }\big) and sample complexity of\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.