Movement budget limits learnability of tracking in online learning
When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret
Machine Learning
Summary
This paper studies situations where an online learning algorithm can’t change its choices too much because it has a strict limit on how far it can move over time. The authors find a sharp threshold: if the allowed total movement is too small compared to the complexity of what it tries to track, the algorithm’s performance is poor no matter what. But if the movement budget is sufficiently large, the algorithm can keep up and achieve better results. They prove this by showing it depends on the total distance the algorithm must cover, not just how complicated the path is.
What this means in practice
- •For online optimization teams: Design online learning algorithms that respect limits on parameter updates and understand when tracking complex targets is fundamentally impossible.
- •For robot motion planners: Plan robot movements factoring in travel distance budgets while learning or adapting to changing goals.
A theory result. No direct application yet.
Authors
Ridham Patel
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.