A Simple and Unified Method for Gradient-Variation Regret
Abstract
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.
Related
- Multiplicative Gradient Method for Log-Homogeneous Optimization: A Unified Mirror-Descent Framework
- Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs
- Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
- Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
- A unified framework for original energy dissipation of equilibrium-preserving exponential Runge--Kutta methods for L2 gradient flows
BibTeX
@misc{yu2026simple,
title = {{A Simple and Unified Method for Gradient-Variation Regret}},
author = {Hang Yu and Peng Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26473},
eprint = {2610.26473},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26473},
}
RIS
TY - UNPB
TI - A Simple and Unified Method for Gradient-Variation Regret
AU - Hang Yu
AU - Peng Zhao
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26473
UR - https://arxiv.org/abs/2610.26473
AB - 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.
ER -