On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities

Alexander Rakhlin, Karthik Sridharan

We study an equivalence of (i) deterministic pathwise statements appearing in the online learning literature (termed \emph{regret bounds}), (ii) high-probability tail bounds for th…