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

DevFeed: [When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret](<https://devfeed.tech/articles/when-is-tracking-affordable-a-movement-budget-feasibility-threshold-for-dynamic-regret-114740.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.02812>)

Author: Ridham Patel

Published: 2026-11-03T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [catboost](<https://devfeed.tech/topics/catboost.md>)

Tags: [adversary](<https://devfeed.tech/tags/adversary.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [budget](<https://devfeed.tech/tags/budget.md>), [construction](<https://devfeed.tech/tags/construction.md>), [convex](<https://devfeed.tech/tags/convex.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [cs-sy](<https://devfeed.tech/tags/cs-sy.md>), [diameter](<https://devfeed.tech/tags/diameter.md>), [domain](<https://devfeed.tech/tags/domain.md>), [eess-sy](<https://devfeed.tech/tags/eess-sy.md>), [environment](<https://devfeed.tech/tags/environment.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [gradient](<https://devfeed.tech/tags/gradient.md>), [gradient-descent](<https://devfeed.tech/tags/gradient-descent.md>), [learner](<https://devfeed.tech/tags/learner.md>), [linear](<https://devfeed.tech/tags/linear.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [minimax](<https://devfeed.tech/tags/minimax.md>), [moving](<https://devfeed.tech/tags/moving.md>), [online](<https://devfeed.tech/tags/online.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [tracking](<https://devfeed.tech/tags/tracking.md>)

## AI overview

A hard cap on an online learner's total movement can make tracking a moving comparator incur linear dynamic regret, even when the environment changes slowly. For convex losses on a domain of diameter D, a deterministic adversary forces regret Ω(GDT) when the movement budget S is at most a sufficiently small constant multiple of comparator path length P_T. By contrast, projected online gradient descent with a budget-aware step size achieves sublinear regret when S grows faster than D + P_T, in the learnable regime. The results distinguish the learner's travel forced by the comparator from the comparator's path length alone. Experiments support the predicted threshold and 1/S decay; the tight minimax rate above the threshold remains open.

## Source excerpt

arXiv:2611.02812v1 Announce Type: new 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 = \Omega(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 $\Theta(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 = \omega(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.