Gradient-Variation Regret Bounds for Unconstrained Online Learning

We develop parameter-free algorithms for unconstrained online learning with regret guarantees that scale with the gradient variation $V_T(u)={\sum }_{t=2}^T\mathrm{\parallel }\mathrm{\nabla }{f}_t(u)-\mathrm{\nabla }{f}_{t-1}(u){\mathrm{\parallel }}^2$. For $L$-smooth convex loss, we provide fully-adaptive algorithms achieving regret of order $\tilde{O}(\mathrm{\parallel }u\mathrm{\parallel }\sqrt{V_T(u)}+L\mathrm{\parallel }u{\mathrm{\parallel }}^2+G^4)$ without requiring prior knowledge of comparator norm $\mathrm{\parallel }u\mathrm{\parallel }$, Lipschitz constant $G$, or smoothness $L$. The update in each round can be computed efficiently via a closed-form expression. Our results extend to dynamic regret and find immediate implications to the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result [Wang et al., 2025].