Extensions of classical learning theory to the online setting have proliferated due to the scope of application. Several works [1]}, [2]}, [3]}, [4]} have explored the gap in statistical rates between classical and online learning settings, with [1]}, [2]} showing that the class of one dimensional thresholds, which is easy to learn in the batch setting, is not learnable with adversarial data. Other works, such as [4]}, [8]}, [9]}, [10]}, [11]} have provided sequential analogues of classical notions of complexity that characterize minimax regret, as well as providing computational separation between classical and online learning [12]}. Due to the statistical and computational hardness results presented in the aforementioned work, there has been great interest in finding realistic, robust assumptions, such as smoothness, that allow for efficient learning.
