Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning

Yanyi Li; Wendao Wu; Haihan Zhang; Qinshi Wang; Chenheng Zhang; Chunyuan Zheng; Cong Fang; Haoxuan Li

cs.LGOct 14, 2026

Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning

Authors: Yanyi Li, Wendao Wu, Haihan Zhang, Qinshi Wang, Chenheng Zhang, Chunyuan Zheng, Cong Fang, Haoxuan Li,

Organizations: Peking University

Abstract

Tracking changing comparators is a central problem in online learning. For exp-concave losses, previous work established the $T^{1/3}P_T^{2/3}$ dependence on the horizon $T$ and Euclidean path length $P_T$ for fixed dimension, while the optimal cost of dimension remained unresolved. We resolve this question by establishing a sharp $d^{1/3}$ curved dimension factor, improving the $d^{2/3}$ factor of recent switching and interval reductions [1, 2]. To achieve this improvement, we develop a proper, full-information learner on compact convex subsets of $\mathbb{R}^d$ that adapts to the unknown path length and, under fixed dimension-independent diameter, gradient, and curvature parameters, guarantees $\operatorname{Reg}_T(u_{1:T}) \le \widetilde{O}\left(d+\min\left\{d^{1/3}T^{1/3}P_T^{2/3},\sqrt{TP_T},T\right\}\right).$ A matching lower bound on a diameter-one Euclidean ball establishes the minimax frontier up to logarithmic factors when $T\gtrsim d^2$ , including the transition from the curved rate to larger path budgets. The lower bound already holds for losses that depend on only one coordinate per round, isolating an unavoidable cost of learning across directions. Our upper bound follows from square-root Gaussian KL control of comparator movement and a cancellation argument that pays for history restarts. The curved learner maintains $O(\log^2 T)$ Gaussian states, uses one gradient per round, and runs in time near-linear in $T$ under a Mahalanobis-projection oracle.

Figures & tables

Work	Upper bound	Lower bound	Mechanism
Zhang et al. [ 11 ]	$\widetilde{O}(d+dT^{1/3}P_{T}^{2/3})$	—	Gaussian fixed share; KL projection
Wang et al. [ 1 ]	$\widetilde{O}(d+d^{2/3}T^{1/3}P_{T}^{2/3})$	—	Switching reduction with IRESET/ONS
Wang et al. [ 2 ]	$\widetilde{O}(d+d^{2/3}T^{1/3}P_{T}^{2/3})$	—	Interval-to-dynamic reduction
This Paper ( Corollary 5.2 )	$\bm{\widetilde{\Theta}(d+d^{1/3}T^{1/3}P_{T}^{2/3})}$		Sparse Gaussian histories; drawdown cancellation

Table 1: Dynamic regret for proper exp-concave OCO on arbitrary compact convex domains, with Euclidean path length

P_{T}

. Diameter, gradient bounds, and curvature are fixed independently of

d

; logarithmic factors are suppressed. The displayed curved regime is

T\gtrsim d^{2}

and

0\leq P_{T}\lesssim T/d^{2}

. The matching lower bound is attained on a diameter-one ball.

Dynamic Regret Minimization

Dynamic regret minimization studies how online learners can track changing decision-makers while limiting cumulative loss.

See all 46 papers

Sep 30, 2026

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

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.

Vaneet Aggarwal

Purdue University, West Lafayette, IN, USA

Online Convex Optimization Dynamic Regret Minimization Heavy-Tailed Stochastic Optimization

Ask PDF

Sep 24, 2026

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

We study dynamic regret in online convex optimization with an 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

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.

Naram Mhaisen, George Iosifidis

Faculty of Electrical Engineering, Mathematics and Computer Science TU Delft, Netherlands

Online Convex Optimization Dynamic Regret Minimization

Ask PDF

Sep 17, 2026

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 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 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

Online Convex Optimization Dynamic Regret Minimization Regret Minimization

Ask PDF

Abstract

Dynamic Regret Minimization

Explore similar work

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

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

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