When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret
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 ∑t |xt − xt−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 PT ∈ [D, DT] we exhibit a deterministic adversary that forces Rd = Ω(GDT) on every budget-feasible algorithm whenever S ≤ c PT 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 PT = o(T), where the unconstrained minimax rate Θ(G√(D(D+PT)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 + PT). Thus the critical movement scale is D+PT: linear regret is unavoidable below a sufficiently small constant multiple of PT, while sublinear regret is achievable when S/(D+PT)→∞ 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.
Related
- Movement synchronization in complex and dynamic team coordination
- A Multi-Period MILP Model for Dynamic Index Tracking
- Adaptive relaxed CQ algorithm with dynamic stepsizes for the split feasibility problem
- Fundamental Limits of Dynamic Tracking and Communication: A Stationary Policy Formulation
- Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity
BibTeX
@misc{patel2026when,
title = {{When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret}},
author = {Ridham Patel},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02812},
eprint = {2611.02812},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02812},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret
AU - Ridham Patel
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02812
UR - https://arxiv.org/abs/2611.02812
AB - 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 ∑_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 ∈ [D, DT] we exhibit a deterministic adversary that forces R_d = Ω(GDT) on every budget-feasible algorithm whenever S ≤ 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√(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)→∞ 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.
ER -