Before revision:  Prior to this work, existing online algorithms designed for tolerating the adversarial noise are either subject to label complexity polynomial in d or \frac{1}{\epsilon}, or work under the restrictive uniform marginal distribution.
After revision:  Prior to this work, existing online algorithms designed for tolerating the adversarial noise are either subject to label complexity polynomial in d or \frac{1}{\epsilon}, or suboptimal noise tolerance, or restrictive marginal distributions. With the additional prior knowledge that the underlying halfspace is s-sparse, we obtain attribute-efficient label complexity of