Gradient-Variation Regret Bounds for Unconstrained Online Learning

Yuheng Zhao; Andrew Jacobsen; Nicolò Cesa-Bianchi; Peng Zhao

cs.LGApr 13, 2026

Gradient-Variation Regret Bounds for Unconstrained Online Learning

Authors: Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi, Peng Zhao

Organizations: Università degli Studi di Milano & Politecnico di Milano

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).

Figures & tables

Setting	Reference	Regret in $\widetilde{O}(\cdot)$ -notation	Efficiency
Comparator Adaptive	Jacobsen and Cutkosky (2022)	$\left\\|u\right\\|\sqrt{\sum_{t=2}^{T}\left\\|g_{t}-g_{t-1}\right\\|^{2}}+G\left\\|u\right\\|$	$O(d)$
	Wang et al. (2025)	$\left\\|u\right\\|\sqrt{V_{T}^{\smash{+}}}+L^{2}\left\\|u\right\\|^{2}/G^{2}+G^{2}\left\\|u\right\\|^{2}$	$O(d\log^{2}T)$
	Ours , Theorem 2	$\left\\|u\right\\|\sqrt{V_{T}(u)}+L\left\\|u\right\\|^{2}+G\left\\|u\right\\|$	$O(d)$
Fully Adaptive	Cutkosky and Mhammedi (2024)	$\left\\|u\right\\|\sqrt{\sum_{t=1}^{T}\left\\|g_{t}\right\\|^{2}}+\gamma\left\\|u\right\\|^{2}/\epsilon+\epsilon G^{2}/\gamma$	$O(d)$
	Wang et al. (2025)	$\left\\|u\right\\|^{2}\sqrt{V_{T}^{\smash{+}}}+L^{2}\left\\|u\right\\|^{4}+G\left\\|u\right\\|^{3}+G^{2}\left\\|u\right\\|^{2}+G^{2}\sqrt{\sum_{t=1}^{T}\left\\|g_{t}\right\\|}$	$O(d)$
	Ours , Theorem 3	$\left\\|u\right\\|\sqrt{V_{T}(u)}+L\left\\|u\right\\|^{2}+\gamma\left\\|u\right\\|^{2}/\epsilon+\epsilon G^{2}/\gamma$	$O(d+\log T)$

Table 1: Comparison of parameter-free gradient-adaptive regret, where

g_{t}\in\partial f_{t}(w_{t})

denotes the gradient feedback on round

t

. “Efficiency” denotes the order of per-round computational cost.

Online Convex Optimization

Online Convex Optimization studies sequential decisions under changing convex losses, seeking low regret with limited feedback and constraints.

See all 62 papers

A Simple and Unified Method for Gradient-Variation Regret
Oct 19, 2026Hang Yu, Peng ZhaoOnline Learning Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China
Online Learning with Gradient-Variation Interval Regret
Jun 2, 2026Yan-Feng Xie, Shuche Wang, Peng Zhao +1
State Key Laboratory for Novel Software Technology and the School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · Institute of Operations Research and Analytics, National University of Singapore, Singapore 117602
Small Gradient Norm Regret for Online Convex Optimization
Jan 20, 2026Wenzhi Gao, Chang He, Madeleine UdellOnline Convex Optimization Sequential Decision Making
ICME, Stanford University · SIME, Shanghai University of Finance and Economics · Department of Management Science and Engineering, Stanford University

Oct 19, 2026J/K move · Enter open · S save

A Simple and Unified Method for Gradient-Variation Regret

Hang Yu, Peng Zhao

State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

Online Learning Dynamic Regret Minimization

Open paper AskPDF arXiv

Gradient-variation online learning has attracted increasing attention for its connections to game theory and optimization. It has been studied in both non-stationary online learning, which aims to minimize dynamic regret against time-varying comparator sequences, and universal online learning, which seeks to adapt to unknown loss curvature. Prior work obtained gradient-variation bounds using different techniques tailored to each setting. We propose a simple and unified method based on surrogate losses with a quadratic penalty on decision movement, yielding gradient-variation bounds in both settings. For non-stationary online learning, the method induces an optimistic-to-gradient-variation reduction, enabling a broad class of algorithms to match the rate established by Zhao et al. (2024). For universal online learning, it yields a simple algorithm that matches the optimal universal regret bounds of Yan et al. (2024) while relaxing the extended smoothness assumption. Finally, we apply our method to online games and improve on existing guarantees.

Abstract

Online Convex Optimization

Explore similar work

A Simple and Unified Method for Gradient-Variation Regret

Online Learning with Gradient-Variation Interval Regret

Small Gradient Norm Regret for Online Convex Optimization