Before revision:  We answer this question in the affirmative by designing a computationally efficient  algorithm with near-optimal label complexity of O\big({s \log ^3 d \cdot \log^3\frac{1{\epsilon}}  } \big) and noise tolerance \eta = \Omega(\epsilon), where \epsilon \in (0, 1) is the target error rate . OurO\big({} \big)  main techniques include attribute-efficient paradigms for instance reweighting and for empirical risk minimization, and a new analysis of uniform concentration for unbounded data ~ -- ~ all of them crucially take the structure of the underlying halfspace into account .
After revision:  We answer this question in the affirmative by designing a computationally efficient algorithm with near-optimal label complexity of O\big({s \log ^3 d \cdot \log^3\frac{1{\epsilon}} } \big) and noise tolerance \eta = \Omega(\epsilon), where \epsilon \in (0, 1) is the target error rate , under the assumption that the distribution over (uncorrupted) unlabeled examples is isotropic log-concave. Our algorithm can be straightforwardly tailored to the passive learning setting, and we show that the sample complexity isO\big({} \big) main techniques include attribute-efficient paradigms for instance reweighting and for empirical risk minimization, and a new analysis of uniform concentration for unbounded data ~ -- ~ all of them crucially take the structure of the underlying halfspace into account .