{"id":"arxiv/2611.02812","url":"https://arxiv.org/abs/2611.02812","tags":["cs.LG","eess.SY","math.OC","stat.ML"],"score":0,"title":"When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret","domain":"cs.LG","source":"arxiv","authors":["Ridham Patel"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}