We also provide lower bounds that demonstrate the statistical optimality of our algorithms. Furthermore, we apply our results to noiseless contextual bandits and get a fast algorithm that achieves optimal regret dependence on the horizon, up to logarithmic factors. Finally, we present a complementary approach based on the perceptron algorithm which is robust to adversarial corruptions of the labels \(y_t\) , and enjoys a polynomial regret in a “directional smoothness” parameter which interpolates between the \(\log (1/\sigma )\) -guarantees attained above in the realizable setting, and the \(\mathrm {poly}(1/\sigma )\)  bounds from prior work. We emphasize that, though we adopt the smoothed online learning setting of [1]}, [2]}, [3]}, we use entirely different techniques involving Ville's inequality [4]}, geometric measure theory, and convex geometry. Moreover, in none of these works was the question of adapting to realizability explored; thus, we provide the first regret bounds that are logarithmic in both the horizon and the smoothness parameter. We now discuss some related work:
