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 \frac{1}{\epsilon}, or work under the restrictive uniform marginal distribution.