Gradient-Variation Regret Bounds for Unconstrained Online Learning

Abstract

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\Vert \nabla f_t(u)-\nabla f_{t-1}(u){\Vert }^2$. For $L$-smooth convex losses, we provide fully-adaptive algorithms achieving regret of $\tilde{O}(\Vert u\Vert \sqrt{V_T(u)}+L\Vert u{\Vert }^2+G^4)$ without requiring prior knowledge of comparator norm $\Vert u\Vert$, 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 for the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result (Wang et al., 2025).

COLT 2026; The first two authors contributed equally