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) = ∑_t=2^T ∇ f_t(u)-∇ f_t-1(u)^2. For L-smooth convex losses, we provide fully-adaptive algorithms achieving regret of O(u√(V_T(u)) + Lu^2+G^4) without requiring prior knowledge of comparator norm u, 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).