Metraipolis › archive › dc_ede21df4d728

When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret — arXiv:2611.02812

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02812
License (as archived)
CC0-1.0
Archived
2026-11-03T11:22:55.687Z
SHA-256 of the archived text
2bd16949311a18b5772a9cc6f45e7f007a5c762cf057f9b299102da4b333856c
Stable URL of this page
https://metraipolis.com/documento/dc_ede21df4d728

How to cite

When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret — arXiv:2611.02812 — arXiv (en), https://arxiv.org/abs/2611.02812 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ede21df4d728 (Metraipolis archive dc_ede21df4d728, sha256 2bd16949311a18b5772a9cc6f45e7f007a5c762cf057f9b299102da4b333856c)
BibTeX
@misc{dcede21df4d728,
  title = {When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret — arXiv:2611.02812},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02812},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ede21df4d728; sha256 2bd16949311a18b5772a9cc6f45e7f007a5c762cf057f9b299102da4b333856c},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02812. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Systems and Control (eess.SY); Optimization and Control (math.OC); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2611.02812 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:02:37.643Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).