Related papers: Gradient-Variation Regret Bounds for Unconstrained Online Learning

Gradient-Variation Regret Bounds for Unconstrained Online Learning

URL: http://arxiv.org/abs/2604.11151v1
Date: Mon, 13 Apr 2026 08:14:37 GMT
Title: Gradient-Variation Regret Bounds for Unconstrained Online Learning
Abstract summary: We develop parameter-free algorithms for unconstrained online learning with regret.<n>For $L$-smooth convex loss, we provide fully-adaptive algorithms achieving regret of order $widetildeO(|u|sqrtV_T(u) + L|u|2+G4)$ without requiring prior knowledge of norm $|u|$, Lipschitz constant $G$, or smoothness $L$.
Score: 27.020402628254917
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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 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].

Related papers

Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
We introduce UniGrad, a novel approach that achieves both universality and adaptivity, with two distinct realizations: UniGrad.Correct and UniGrad.Bregman.<n>Both methods achieve universal regret guarantees that adapt to gradient variation, simultaneously attaining $mathcalO(log V_T)$ regret for strongly convex functions and $mathcalO(d log V_T)$ regret for exp-concave functions.
arXiv Detail & Related papers (2025-11-25T05:23:10Z)
Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games [60.871651115241406]
A considerable chasm has been looming for decades between theory and practice in zero-sum game solving through first-order methods.<n>We propose a new scale-invariance and parameter-free variant of PRM$+$, which we call IREG-PRM$+$.<n>We show that it achieves $T-1/2$ best-iterate and $T-1$ optimal convergence guarantees, while also being on par with PRM$+$ on benchmark games.
arXiv Detail & Related papers (2025-10-06T00:33:20Z)
Sparsity-Based Interpolation of External, Internal and Swap Regret [4.753557469026313]
This paper focuses on the expert problem in online learning.<n>By recovering the optimal $O(sqrtTlog d)$ external regret bound when $dmathrmunif_phi=d$, the standard $tilde O(sqrtT)$ internal regret bound when $dmathrmself_phi=d-1$ and the optimal $tilde O(sqrtdT)$ swap regret bound in the worst case, we improve upon existing algorithms in the intermediate regimes.
arXiv Detail & Related papers (2025-02-06T22:47:52Z)
Online Linear Regression in Dynamic Environments via Discounting [38.15622843661145]
We develop algorithms for online linear regression which achieve optimal static and dynamic regret guarantees. We show that a discounted variant of the Vovk-Azoury-Warmuth forecaster achieves dynamic regret of the form $R_T(vecu)le Oleft(dlog(T)vee sqrtdP_Tgamma(vecu)$, where $P_Tgamma(vecu)$ is a measure of variability of the comparator sequence, and show that the
arXiv Detail & Related papers (2024-05-29T15:17:53Z)
Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime [74.52487417350221]
We consider online learning problems in the realizable setting, where there is a zero-loss solution. We propose new Differentially Private (DP) algorithms that obtain near-optimal regret bounds.
arXiv Detail & Related papers (2023-02-27T21:19:24Z)
Logarithmic Regret from Sublinear Hints [76.87432703516942]
We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
arXiv Detail & Related papers (2021-11-09T16:50:18Z)
Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
arXiv Detail & Related papers (2021-02-15T08:16:51Z)
Adaptive Online Learning with Varying Norms [45.11667443216861]
We provide an online convex optimization algorithm that outputs points $w_t$ in some domain $W$. We apply this result to obtain new "full-matrix"-style regret bounds.
arXiv Detail & Related papers (2020-02-10T17:22:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.