Gradient-Variation Regret Bounds for Unconstrained Online Learning
For researchers in online learning, this provides fully-adaptive algorithms with tighter regret guarantees that remove the need for hyperparameter tuning, representing an incremental improvement over existing methods.
This work develops parameter-free algorithms for unconstrained online learning that achieve regret bounds scaling with gradient variation, without requiring prior knowledge of comparator norm, Lipschitz constant, or smoothness. The algorithms achieve regret of order O(||u||√V_T(u) + L||u||^2 + G^4) and improve upon previous best-known results in the stochastically-extended adversarial model.
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 \|\nabla f_t(u)-\nabla f_{t-1}(u)\|^2$. For $L$-smooth convex loss, we provide fully-adaptive algorithms achieving regret of order $\widetilde{O}(\|u\|\sqrt{V_T(u)} + L\|u\|^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 to the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result [Wang et al., 2025].