When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret

Ridham Patel

cs.LGNov 2, 2026

When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret

Authors: Ridham Patel

Organizations: Computer Science & Engineering, Indian Institute of Technology Gandhinagar, Gandhinagar, India

Abstract

Dynamic regret measures an online learner against a moving comparator, and standard analyses assume the learner may move freely at every round. We study what happens when it may not: the learner is given a hard budget $S$ on its total movement $\sum_t \|x_t - x_{t-1}\|$ . Our main result is that a movement budget creates a feasibility barrier. On a domain of diameter $D$ with $G$ -Lipschitz convex losses, for every comparator path length $P_T \in [D, DT]$ we exhibit a deterministic adversary that forces $R_d = Ω(GDT)$ on every budget-feasible algorithm whenever $S \le c P_T$ for a universal constant $c>0$ . This barrier is caused by the budget rather than by a volatile environment: for fixed $D$ , it applies when $P_T = o(T)$ , where the unconstrained minimax rate $Θ(G\sqrt{D(D+P_T)T})$ is sublinear, so the same instances are learnable with an unbounded budget and unlearnable without one. Conversely, projected online gradient descent with a budget-aware step size is budget-feasible and attains $o(GDT)$ once $S = ω(D + P_T)$ . Thus the critical movement scale is $D+P_T$ : linear regret is unavoidable below a sufficiently small constant multiple of $P_T$ , while sublinear regret is achievable when $S/(D+P_T)\to\infty$ in the learnable regime. The construction rests on a distinction we make explicit: what makes a comparator expensive to track under a movement budget is the distance it forces the learner to travel, not its path length. Above the threshold we give a budget-dependent upper bound and identify the tight minimax rate in this region as an open problem rather than claiming a product law. Experiments support the predicted transition location and the $1/S$ decay.

Figures & tables

Figure 1: Square-wave adversary. Left: normalized regret drops as the movement budget approaches the comparator path length; the proved lower bound has only constant-factor precision. Right: with

P_{T}=\sqrt{T}=o(T)

, a budget-starved learner has constant normalized regret while the unconstrained learner decays, showing that the barrier is caused by the movement budget rather than by large path length.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Square-wave adversary on

\mathcal{K}=[0,D]

with

f_{t}(x)=G|x-u_{t}|

. (A) Normalized regret of a near-optimal budget-feasible tracker against

S/P_{T}

. Curves for

P_{T}/T\in\{0.05,0.15,0.4\}

collapse onto

\tfrac{1}{2}(1-S/P_{T})

and reach zero at

S=P_{T}

. The dashed line shows the scale of the proved lower bound in Theorem 1 ; its constants are conservative, and the empirical transition occurs closer to

S=P_{T}

. The dotted curve is Budget-Controlled OGD, which pays an additional lag penalty on this instance. (B) Fixing

P_{T}=\sqrt{T}=o(T)

and growing

T

: the starved learner (

S=P_{T}/4

) stays flat near

0.5

, so its regret is linear, while the unconstrained learner decays as

T^{-1/2}

. Both axes logarithmic.

Figure 3: Empirical budget–regret trade-off on a random-walk comparator. All methods trace a

1/S

decay over the mid-range of budgets, with Budget-Controlled OGD attaining the lowest regret at each budget. This is consistency with the upper bound ( 6 ) only. The dashed guide line is a

1/S

reference and is not evidence of a matched product law; by Remark 3 tightness of the

1/S

term is unproved.

Figure 4: Transition location on five real series (S&P 500, EUR/USD, crude oil, Bitcoin, NYC temperature). Regret stays elevated for

S\ll P_{T}

and drops near

S=P_{T}

on all five, placing the transition where Theorem 1 predicts. Finite horizons cannot separate

\Theta(T)

from

o(T)

, so these panels test the location of the transition and the

1/S

decay, not asymptotic linearity; that claim rests on Figure 2 (B).

Work	Regret	Constraint	Minimax	Threshold
Besbes et al. [2015]	Dyn.	None	Yes	No
Baby and Wang [2021]	Dyn.	None	Yes	No
Zhao et al. [2024]	Dyn.	None	No	No
Zhang et al. [2021]	Dyn.	Soft	Yes	No
Dekel et al. [2014]	Stat.	Switch cost	Yes	No
Chen et al. [2020]	Stat.	Count	Yes	No

Appendix

Table 1: Positioning. “Dyn.” and “Stat.” denote dynamic and static regret; “Dist.” and “Count” denote switching-distance and switching-count constraints.

Figure 5: Random-walk comparator: normalized regret

R_{d}/T

against

S/P_{T}

for drift magnitudes

\sigma\in\{0.1,0.5,1.0\}

T=5000

, with the red dashed line at

S=P_{T}

and shading showing

\pm 1

standard deviation over 20 seeds. The drop near

S=P_{T}

locates the transition; because this comparator is spatially concentrated, it does not by itself certify a budget-induced barrier (Remark 5 ).

Figure 10: Learner trajectories on Bitcoin and NYC temperature at three budget levels. At

S=0.05P_{T}

the learner barely moves and incurs

R_{d}/T\approx 0.47

; at

S=0.3P_{T}

tracking improves substantially; at

S=P_{T}

the learner tracks near-perfectly with

R_{d}/T<0.01

Dynamic Regret Minimization

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

See all 52 papers

Oct 8, 2026

Optimally Pacing Budget Spending and Learning

We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given any class of

F

experts and a candidate budget pacing schedule, we provide a full-information algorithm which obtains regret

O(D \sqrt{\log F}+ \sqrt{T\log F})

against all experts whose cumulative spending stays within distance

D

of this schedule, matching lower bounds established by Braverman et al. (2025). We additionally show that our technique extends to various problems in online resource allocation, where the learner gets to see the rewards and costs of the current options available to them, and establish

O(D\sqrt{\log F})

regret bounds when fractional allocation is allowed. This is the first algorithm we are aware of which can achieve

o(\sqrt{T})

guarantees for such tasks.

Mark Braverman, Jingyi Liu, Jieming Mao +2

Department of Computer Science, Princeton University · Google Research

Online Learning Online Resource Allocation Minimax Regret

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

Oct 14, 2026

Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning

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.

Yanyi Li, Wendao Wu, Haihan Zhang +6

Peking University

Dynamic Regret Minimization Online Convex Optimization Minimax Regret

Ask PDF

Abstract

Dynamic Regret Minimization

Explore similar work

Optimally Pacing Budget Spending and Learning

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning