# Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization

arXiv: https://arxiv.org/abs/2511.19937 · HTML: https://mlsanity.com/paper/2511.19937/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2025.

## Built on by (most cited first, 2 of 2)

- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)

## Abstract (arXiv)

Universal online learning aims to achieve optimal regret guarantees without requiring prior knowledge of the curvature of online functions. Existing methods have established minimax-optimal regret bounds for universal online learning, where a single algorithm can simultaneously attain O(√T) regret for convex functions, O(d log T) for exp-concave functions, and O(log T) for strongly convex functions, where T is the number of rounds and d is the dimension of the feasible domain. However, these methods still lack problem-dependent adaptivity. In particular, no universal method provides regret bounds that scale with the gradient variation VT, a key quantity that plays a crucial role in applications such as stochastic optimization and fast-rate convergence in games. In this work, we introduce UniGrad, a novel approach that achieves both universality and adaptivity, with two distinct realizations: UniGrad.Correct and UniGrad.Bregman. Both methods achieve universal regret guarantees that adapt to gradient variation, simultaneously attaining O(log VT) regret for strongly convex functions and O(d log VT) regret for exp-concave functions. For convex functions, the regret bounds differ: UniGrad.Correct achieves an O(√VT log VT) bound while preserving the RVU property that is crucial for fast convergence in online games, whereas UniGrad.Bregman achieves the optimal O(√VT) regret bound through a novel design. Both methods employ a meta algorithm with O(log T) base learners, which naturally requires O(log T) gradient queries per round. To enhance computational efficiency, we introduce UniGrad++, which retains the regret while reducing the gradient query to just 1 per round via surrogate optimization. We further provide various implications.