CS Paper Radar

On the Relation Between Interval Regret and Dynamic Regret

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

cs.LG math.OCstat.ML ·submitted 2026-09-28 06:40 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Strongly Adaptive Online Learning Achieves Uniform Discounted Regret

cs.LG ·2026-10-29 ·Sifan Yang, Wenhao Yang, Lijun Zhang
similarity 0.75
Abstract

Discounted regret measures the performance of an online learner by assigning exponentially decaying weights to past losses, reflecting the greater importance of recent losses in non-stationary online learning. While previous work obtains uniform discounted regret bounds over a continuous range of discount factors using a specialized meta-algorithm, its results are limited to convex functions. In this paper, we demonstrate that strongly adaptive regret bounds can directly imply uniform discounted regret guarantees for convex, strongly convex, and exp-concave loss functions. Our key observation is that discounted regret against a fixed comparator admits an exact decomposition into a convex combination of interval regrets. For convex functions, this reduction yields an $O(\sqrt{\log T/(1-λ)})$ discounted regret bound for all discount factors $λ\in(0,1)$, matching the previous rate over a broader range of discount factors. For strongly convex and exp-concave functions, we provide regret bounds of $O\left(\log T\left(1+\log\frac{1}{1-λ}\right)\right)$.

0.16

A Simple and Unified Method for Gradient-Variation Regret

cs.LG math.OC ·2026-10-19 ·Hang Yu, Peng Zhao
similarity 0.73
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.

0.14

Strongly Adaptive Online Learning with Time-Varying Movement Costs

cs.LG stat.ML ·2026-10-23 ·Andrew Jacobsen, Emmanuel Esposito, Hao Qiu, Mengxiao Zhang
top venue similarity 0.73
Abstract · v2: NeurIPS 2026 camera-ready

We study online convex optimization (OCO) with time-varying movement costs, where the learner incurs both a loss and a time-dependent penalty for changing its decisions. While previous work has established dynamic regret guarantees for this setting, obtaining strongly adaptive guarantees that hold simultaneously over arbitrary intervals remains an open challenge. We address this by developing a new algorithm which, for every interval $[a,b]\subseteq[T]$ and arbitrary comparator sequence, achieves a data-dependent regret bound of $ \widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+λ_t\|g_t\|)} \right) $, where $D$ is the diameter of the decision domain, $P_{[a,b]}$ is the path length of the comparator sequence over $[a,b]$, $g_t$ is the gradient of the loss, and $λ_t$ is the movement-cost coefficient at round~$t$. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of our development, we further obtain strongly-adaptive dynamic regret guarantees under arbitrary delayed feedback with a refined dependence on interval-restricted cumulative delays. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.

0.41

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

cs.LG ·2026-09-17 ·Yibo Wang, Wenhao Yang, Sifan Yang, Wei Jiang, Yuanyu Wan +1 more
similarity 0.72
Abstract

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.

0.38

Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback

cs.LG ·2026-11-02 ·Tsubasa Harada, Yasushi Kawase, Hanna Sumita
theory similarity 0.69
Abstract · 44 pages, 1 figure

We study stochastic online optimization (SOO) under semi-bandit feedback: in each of $T$ rounds, a policy adaptively observes $n$ independent random variables with unknown distributions, learning only from observed values. First-order stochastic dominance (FSD) monotonicity enables general reductions for learning SOO, but can fail when observations change future feasibility, resource use, or reference points. Our algorithm runs the dynamic program for the optimal policy, replacing each expectation by its most optimistic value over a confidence set of distributions. Its regret depends on the level-set complexity $s_i$ of the computed values as functions of the $i$th variable: the number of intervals needed to describe their superlevel sets. For rewards in $[0,1]$, the regret is $\tilde{O}(\sqrt{ST})$ without this monotonicity, where $S=\sum_{i=1}^n\min\{s_i,k_i\}$ and $k_i$ is the support size of the $i$th distribution, which may be infinite when $s_i$ is finite. For constant level-set complexities, regret is $\tilde{O}(\sqrt{nT})$, even for continuous distributions. The algorithm requires no knowledge of $s_i$, $k_i$, or the supports, and it also achieves regret $\tilde{O}(\sqrt{nkT})$ for supports of size at most $k$ without any level-set condition, which improves the previous bound $\tilde{O}(n(\sqrt{kT}+k))$ for FSD-monotone problems. We also prove a lower bound of $Ω(\min\{T,\sqrt{ST}\})$ for all positive integers $s_1,\ldots,s_n$ with $k_i=2s_i+1$, which holds even under full feedback and matches the upper bound up to logarithmic factors. We obtain $\tilde{O}(\sqrt{nT})$ regret for these problems, all nonmonotone under FSD: stochastic Boolean function evaluation, the full-information secretary problem, optimal stopping with loss aversion, scheduling with deadlines and correlated stochastic knapsack with unimodal rewards, and overbooking with group reservations.

0.16

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

cs.LG ·2026-09-24 ·Naram Mhaisen, George Iosifidis
top venue similarity 0.67
Abstract · To appear in the proceedings of NeurIPS 2026

We study dynamic regret in online convex optimization with an \emph{indicator switching cost}: a fixed penalty incurred whenever two consecutive decisions differ. This captures startup overheads such as server activation, model deployment, and cache updates, and on a bounded domain it recovers norm-based movement costs as a special case. Existing guarantees for indicator costs handle only static comparators. We show that a direct extension of these techniques to dynamic regret provably fails, motivating a different approach. We propose a meta-learning framework: a set of randomized lazy FTRL base learners restarted at dyadic time scales, aggregated by a movement-aware master that mixes their proposal densities and samples actions via maximal coupling of consecutive mixtures. The resulting algorithm satisfies, in expectation, $\mathcal{R}^{\mathbf{1}}_T \le \tilde{\mathcal{O}}(\min\{\sqrt{T(S_T{+}1)},T^{2/3}(P_T+1)^{1/3}\})$, where $\mathcal{R}^{\mathbf{1}}_T$ is the dynamic regret plus the cumulative indicator switching cost, $S_T$ counts comparator switches, and $P_T$ is the comparator path length. The bound holds simultaneously for all sequences and requires no prior knowledge of $S_T$ or $P_T$: it is minimax-optimal (up to logarithmic factors) for tracking piecewise-constant comparators, and also captures frequently moving comparators with small total path length.

0.53

Universal Online Convex Optimization With Delayed Feedback

cs.LG ·2026-10-20 ·Hao Qiu, Andrew Jacobsen, Emmanuel Esposito, Mengxiao Zhang
similarity 0.66
Abstract

We study universal online convex optimization with delayed feedback. We develop a single algorithm that simultaneously adapts to general convex, strongly convex, and exp-concave losses without prior knowledge of the curvature class or parameters. Our regret bounds match the best known dependence on the time horizon $T$ and delays up to doubly logarithmic factors: roughly $\sqrt{T + d_{\mathrm{tot}}}$ for convex losses and $σ_{\max}\log T$ rates with curved losses, where $d_{\mathrm{tot}}$ is the total cumulative delay and $σ_{\max}$ is the maximum number of simultaneously missing observations. Our main technical contribution is a delayed meta-learner with a second-order excess-loss guarantee, which enables curvature-adaptive aggregation of delayed base learners. In addition, our new exp-concave base learner yields a sharper regret bound which improves the state-of-the-art delay dependence by replacing the maximum delay with the potentially much smaller $σ_{\max}$, while retaining the complementary $\sqrt{d_{\mathrm{tot}}}$ dependence.

0.27

Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise

cs.LG cs.ITmath.OC ·2026-09-30 ·Vaneet Aggarwal
theory similarity 0.66
Abstract

We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional $p$th noise moment, $1<p\le2$. For every fixed interval $I$ of length $n$ and comparator path with $Λ_I=1+P_I/D$, one learner achieves \[ E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(Λ_I+\log^2(2T))} +σDn^{1/p}(Λ_I+\log^2(2T))^{(p-1)/p}]). \] The learner uses none of $G,σ,p,I,P_I$, and the constant is universal. Interval adaptation adds to comparator complexity, preserving the distinct mean-gradient and noise exponents. The analysis controls calibration in expectation and limits the cost of observation-scale changes. Its general theorem compares to distributions over predictably available experts with relative-entropy dependence on a nonuniform prior. A common prior favors long windows and long restart lengths. With the statistics supplied, the interval cost becomes $1+\log(T/n)$, including the optimal full-horizon static rate. A change-of-measure lower bound identifies the noise power of this logarithm for learners retaining a full-horizon optimal guarantee, under explicit conditions. Static comparisons and deterministic partitions follow from the same decisions.

0.15