Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses
Yihan Zhou, Victor Sanches Portella, Mark Schmidt, Nicholas Harvey
In this work, we consider OCO for relative Lipschitz and relative strongly convex functions. We extend the known regret bounds for classical OCO algorithms to the relative setting. Specifically, we show regret bounds for the follow the regularized leader algorithms and a variant of online mirror descent. Due to the generality of these methods, these results yield regret bounds for a wide variety of OCO algorithms. Furthermore, we further extend the results to algorithms with extra regularization such as regularized dual averaging.
