On the Relation Between Interval Regret and Dynamic Regret

Yi-Han Wang; Peng Zhao; Zhi-Hua Zhou

cs.LGSep 28, 2026

On the Relation Between Interval Regret and Dynamic Regret

Authors: Yi-Han Wang, Peng Zhao, Zhi-Hua Zhou

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

Abstract

Non-stationary online learning has attracted much attention in recent years, as static regret is insufficient to guide algorithm design in changing environments. To address this limitation, interval regret and dynamic regret have been introduced as two representative performance metrics that strengthen static regret in complementary directions. Interval regret requires an online algorithm to achieve competitive static regret over every local time interval, whereas dynamic regret evaluates performance against an arbitrary sequence of time-varying comparators. Despite their importance, the relation between these metrics has long remained unclear. Prior work has often regarded interval regret as the stronger notion, based on the intuition that local guarantees should naturally induce global guarantees. Consequently, it is widely conjectured that an algorithm with optimal interval regret should automatically attain optimal dynamic regret. In this paper, we first establish a negative result that refutes this intuition of a metric-level implication. Specifically, for both convex and curved functions (including exp-concave and strongly convex functions), we show that there exist instances in which an algorithm with optimal interval regret nevertheless fails to achieve optimal dynamic regret. We then show how to leverage local adaptivity to obtain optimal dynamic regret. In particular, optimal dynamic regret can be attained by invoking an interval regret minimization process over an enlarged Euclidean ball containing the original convex feasible domain and using a suitable domain-converted surrogate loss. This reduction applies to both convex and curved functions. As a byproduct, we obtain the first proper and efficient algorithm with optimal dynamic regret for exp-concave functions, improving prior results while significantly simplifying the analysis.

Figures & tables

Loss class	OIR on $h_{t}$	Surrogate loss	ODR on $f_{t}$
Convex	$\widetilde{\mathcal{O}}(\sqrt{\|I\|})$	Eq. 8	$\widetilde{\mathcal{O}}(\sqrt{T(1+P_{T})})$
Exp-concave	$\widetilde{\mathcal{O}}(d\log\|I\|)$	Eq. 9	$\widetilde{\mathcal{O}}\big(d+d^{\frac{2}{3}}P_{T}^{\frac{2}{3}}T^{\frac{1}{3}}\big)$
Strongly convex	$\widetilde{\mathcal{O}}(\log\|I\|)$	Eq. 10	$\widetilde{\mathcal{O}}\big(1+P_{T}^{\frac{2}{3}}T^{\frac{1}{3}}\big)$

Table 1: OIR requirements on the surrogate losses and resulting ODR guarantees on the original losses. The ODR column bounds

\textrm{{D-Reg}}_{T}(\left\{\mathbf{u}_{t}\right\}_{t=1}^{T})

Parameter	$f_{t}$ on $\mathcal{X}$	$h_{t}$ on $\mathcal{Y}$
Enclosing-ball diameter	$D_{\mathcal{X}}$	$D_{\mathcal{Y}}=2D_{\mathcal{X}}$
Lipschitz coefficient	$G$	$G_{h}=\begin{cases}G,&\text{convex},\\ (1+\gamma D_{\mathcal{Y}}G)G,&\text{exp-concave},\\ G+\lambda(D_{\mathcal{X}}+D_{\mathcal{Y}})/2,&\text{strongly convex}.\end{cases}$
Exp-concavity coefficient	$\alpha$	$\alpha_{h}=\gamma/(1+\gamma D_{\mathcal{Y}}G)^{2}$
Exp-concave curvature	$\gamma$ in Eq. 15	$\gamma_{h}=\alpha_{h}/2$
Strong-convexity coefficient	$\lambda$	$\lambda_{h}=\lambda$
Smoothness coefficient	N/A	$H_{h}=2G_{h}/D_{\mathcal{X}}$ , only in hindsight analyses .

Table 2: Domain and loss parameters before and after domain conversion.

Explore similar work

Sep 17, 2026cs.LG

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, attaining optimal bounds for strongly convex and exp-concave losses often involves intricate analysis. In this paper, we present a \textit{simple} framework that reduces dynamic regret minimization to switching regret minimization. As a result, we can derive dynamic regret bounds by using off-the-shelf algorithms with switching regret guarantees. The key idea of our reduction is to construct, for \textit{any} comparator sequence, an auxiliary random sequence that is unbiased at each round, with the controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we can decompose dynamic regret into the expected switching regret against the random sequence and its controlled variance. Theoretically, for strongly convex and exp-concave losses, we establish the

\widetilde{O}(T^{1/3}P_T^{2/3})

dynamic regret bounds, where

T

denotes the time horizon and

P_T

denotes the path-length of the comparator sequence. Moreover, for general convex losses, the same reduction also recovers the

O(\sqrt{T(1+P_T)})

dynamic regret bound. Notably, all our findings match the minimax optimal results for these three types of losses, highlighting the versatility of our proposed framework.

Yibo Wang, Wenhao Yang, Sifan Yang +3

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

Optimal Regret Learning-Augmented Algorithms Convex Loss Random Simple

Ask PDF

Jun 2, 2026cs.LG

Online Learning with Gradient-Variation Interval Regret

This paper investigates non-stationary online learning using the metric of interval regret, which requires an online algorithm to perform well over every time interval. We propose the first online learning algorithm that achieves an interval regret bound scaling with gradient variation, a fundamental measure of the cumulative change in online function gradients, which relates to various problem-dependent quantities and is closely connected to stochastic optimization and other problems. Our method employs a simple and efficient two-layer online ensemble structure that achieves strong theoretical guarantees. Specifically, it enjoys a regret bound that simultaneously adapts to various problem-dependent quantities while also preserving the minimax-optimal rate in the worst case. Moreover, recognizing the challenge of hyperparameter tuning, we introduce a Lipschitz- and smoothness-agnostic variant that automatically adapts to these potentially unknown constants. This is primarily enabled by a novel Lipschitz-adaptive meta algorithm, which may be of independent interest. Beyond interval regret, our method also yields broader implications: it provides versatile bounds for interval dynamic regret, a stronger measure that competes with changing comparators over any interval, and yields the first piecewise characterization for stochastic extended adversarial optimization. Theoretical findings are validated by experiments.

Yan-Feng Xie, Shuche Wang, Peng Zhao +1

Learning-Augmented Algorithms Interval Regret Stochastic Optimization Gradient Regret

Ask PDF

Jan 20, 2026stat.ML

Small Gradient Norm Regret for Online Convex Optimization

This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the

G^\star

regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight. We show that the

G^\star

regret strictly refines the existing

L^\star

(small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the

G^\star

regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.

Wenzhi Gao, Chang He, Madeleine Udell

ICME, Stanford University · SIME, Shanghai University of Finance and Economics · Department of Management Science and Engineering, Stanford University

Interval Regret Regret

Ask PDF