Gradient-Variation Regret Bounds for Unconstrained Online Learning

Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi, Peng Zhao
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7062-7104, 2026.

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-zhao26a, title = {Gradient-Variation Regret Bounds for Unconstrained Online Learning}, author = {Zhao, Yuheng and Jacobsen, Andrew and Cesa-Bianchi, Nicol\`{o} and Zhao, Peng}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {7062--7104}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/zhao26a/zhao26a.pdf}, url = {https://proceedings.mlr.press/v336/zhao26a.html}, 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 \|\nabla f_t(u)-\nabla f_{t-1}(u)\|^2$. For $L$-smooth convex losses, we provide fully-adaptive algorithms achieving regret of $\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 for the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result (Wang et al., 2025).} }
Endnote
%0 Conference Paper %T Gradient-Variation Regret Bounds for Unconstrained Online Learning %A Yuheng Zhao %A Andrew Jacobsen %A Nicolò Cesa-Bianchi %A Peng Zhao %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-zhao26a %I PMLR %P 7062--7104 %U https://proceedings.mlr.press/v336/zhao26a.html %V 336 %X 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 losses, we provide fully-adaptive algorithms achieving regret of $\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 for the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result (Wang et al., 2025).
APA
Zhao, Y., Jacobsen, A., Cesa-Bianchi, N. & Zhao, P.. (2026). Gradient-Variation Regret Bounds for Unconstrained Online Learning. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:7062-7104 Available from https://proceedings.mlr.press/v336/zhao26a.html.

Related Material