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

AI summary

Overview

Research area: Machine learning theory — specifically online convex optimization, dynamic regret, and non-stationary online learning, framed for temporal/sequential decision systems.

Technical level: Intermediate. The core message (a hard movement budget can make tracking impossible) is stated in plain terms and supported by an intuitive adversary, but the surrounding minimax-rate analysis and the proof appendices are advanced.

Scope (one sentence): The paper identifies a sharp scale — the decision domain's diameter plus the comparator's path length — below which no movement-budgeted learner can achieve sublinear dynamic regret, and above which a simple budget-aware projected gradient method can.

What This Paper Is About

Standard dynamic-regret theory measures an online learner against a comparator that moves over time, and assumes the learner may move freely every round. This paper asks what changes when movement itself is a scarce resource: the learner has a hard cap S on its total travel SC = Σ‖x_t − x_{t−1}‖. The goal is to determine, as a function of the comparator's path length P_T, the domain diameter D, and the budget S, when sublinear dynamic regret is achievable at all — and what rate is attainable when it is.

Key Contributions

1. A feasibility barrier for budgeted dynamic regret. The paper exhibits a deterministic adversary (a full-range square wave on K = [0, D] with losses f_t(x) = G|x − u_t|) that forces R_d = Ω(GDT) on every budget-feasible algorithm whenever S ≤ cP_T for a universal constant c > 0, uniformly over P_T ∈ [D, DT].

2. A matching achievability result at the scale D + P_T. Projected online gradient descent with the budget-aware step size η = S/(GT) is budget-feasible (SC ≤ S) and attains R_d = o(GDT) once S = ω(D + P_T) and S = o(DT). Together the two directions single out D + P_T as the critical movement scale.

3. A reframing of what makes a comparator hard. The paper argues explicitly that under a movement budget the relevant difficulty measure is the range a comparator forces the learner to traverse, not its path length — a random-walk comparator has path length Θ(Tσ) but spatial range only Θ(σ√T), so it cannot certify a budget-induced barrier.

4. A budget-dependent upper bound above the threshold, with the tight rate left open. Budget-controlled OGD gives R_d ≤ O(min{G√(D(D+2P_T)T) + GTD(D+2P_T)/S, GDT}), but the authors state plainly that tightness of the 1/S term is unresolved and do not claim a product law.

Main Findings

• The barrier is caused by the budget, not by volatility. For fixed D and P_T = o(T), the unconstrained minimax rate Θ(G√(D(D+P_T)T)) is sublinear — so the same instances are learnable with an unbounded budget and unlearnable (Ω(GDT)) without one. The comparator is deterministic and fully known to the learner, so the obstruction is purely whether it can afford to move.

• Explicit lower bound with stated constants. The proved inequality is R_d ≥ c₀·GDT·(1 − c₁·S/P_T); the proof in Appendix H arrives at R_d ≥ (GDT/8)(1 − 8S/P_T). The authors describe these constants as conservative.

• The constructive rate. With η = S/(GT), movement is at most TηG = S by construction (no explicit projection onto the budget constraint), and R_d ≤ GTD(D+2P_T)/(2S) + GS/2, which is o(GDT) under the stated conditions on S.

• Above the threshold the guarantee is an upper bound only. Budget-controlled OGD with η = min{√(D(D+2P_T)/(G²T)), S/(GT)} yields the two-term bound in equation (6). The first term is the usual unconstrained OGD rate; the second is the price of shrinking the step size. The classical unconstrained lower bound Ω(G√(DP_T T)) (Besbes et al., 2015) still applies, but no matching lower bound for the 1/S term is given — the paper calls this the main open question and explicitly declines to claim a product law R_d · S = Θ(GTD(D+P_T)).

• Square-wave experiment confirms a collapse onto a simple curve. At T = 4000, curves for P_T/T ∈ {0.05, 0.15, 0.4} collapse onto R_d/(GDT) = ½(1 − S/P_T), vanishing at S = P_T.

• An exact dynamic program nudges the constant down slightly. At T = 240 and P_T = 29, the DP gives 0.364 versus 0.375 at S = P_T/4, and 0.242 versus 0.250 at S = P_T/2, in units of GDT. It vanishes only at S = P_T, not at S = P_T/2.

• The sublinear-path regime separates the two hypotheses. With P_T = √T and T grown from 250 to 8000, the budget-starved learner at S = P_T/4 moves from 0.492 to 0.500 normalized regret (flat, i.e. linear), while the unconstrained learner decays from 0.060 to 0.011, consistent with T^{−1/2}.

• Real-series transition location. On five daily series — S&P 500 (T = 1509), EUR/USD (T = 1564), crude oil via USO (T = 1509), Bitcoin (T = 2191), NYC mean temperature (T = 2192) — regret stays elevated for S ≪ P_T and drops near S = P_T. At S = 0.05P_T the learner barely moves with R_d/T ≈ 0.47; at S = P_T it tracks near-perfectly with R_d/T < 0.01. The authors caution that finite horizons cannot separate Θ(T) from o(T) and that these panels test transition location, not asymptotic linearity.

• Algorithm comparison. Budget-controlled OGD matches or outperforms Lazy OGD, SOCO, and Periodic Restart at all budget levels across oscillating, rotating, and piecewise stationary synthetic environments (Appendix K, Figure 7), and the same ordering holds on the S&P 500, Bitcoin, and NYC temperature series.

• A lag effect is reported honestly. On the square-wave instance, budget-controlled OGD can rise above the frozen-learner value before falling, because at small step sizes the iterate reaches an endpoint roughly when the comparator leaves it. The authors note this does not contradict Theorem 2 (a worst-case bound that is not tight here) but shows the near-optimal tracker and OGD differ by more than a constant on this family.

Methodology in Plain English

The argument is built from a deliberately simple adversarial world. Restrict the decision set to the interval [0, D] and let the loss at each round be G|x − u_t|, so the best point in hindsight is exactly u_t. Now make u_t a square wave that alternates between the two endpoints 0 and D in n + 1 equal-length blocks, with the number of crossings set to n = min{⌊P_T/D⌋, T − 1} so the realized path length is at most the target P_T.

Because the learner is told this sequence in advance, prediction is not the issue. The only question is whether it can pay to travel. Group the blocks into consecutive pairs. Within a pair, if the learner spends movement M_i, then its whole trajectory is trapped in an interval of width M_i, so against the two opposite endpoints it must accumulate error on the order of block-length times (D − M_i). Summing over roughly P_T/D pairs and using the global constraint Σ M_i ≤ S produces the linear lower bound.

For the positive direction, the authors use ordinary projected gradient descent and choose the step size so that per-round motion ηG times T rounds equals the budget exactly. The step size enforces feasibility without any extra projection, and the standard OGD regret bound then trades off the two terms.

Experiments are organized by which claim they test: the square wave validates the theorem's own instance, the P_T = √T sweep isolates the regime where the unconstrained problem is learnable, and random-walk and real-series runs probe the transition location and the empirical 1/S decay — which the authors are explicit cannot certify a barrier.

Why This Matters

Impact on research. The paper draws a line between two things usually conflated: prediction (can the learner infer where the moving optimum is?) and intervention (can it afford to go there?). It shows a regime where prediction is trivially solved, the environment is mild (P_T = o(T)), and yet tracking is provably impossible — a failure mode invisible to path-length-only analyses. It also poses a clean open problem: whether the 1/S term in the budget-dependent upper bound is an artifact of OGD or an unavoidable price.

Real-world applications (as framed by the paper):

• Controller reconfiguration in temporal systems, where changing a control policy consumes a limited actuation or energy resource.
• Changing a served configuration in a deployed system, where each switch has an operational cost.
• Portfolio rebalancing, where trades consume a bounded budget of transaction capacity.
• Any setting where adaptation is an intervention — the paper's general framing for learners charged for the distance they travel.

Industry relevance. The threshold D + P_T gives practitioners a concrete sizing rule: budgets set as a small multiple of the comparator's path length are, in the worst case, insufficient, while budgets that grow faster than D + P_T restore sublinear regret. That is directly actionable for capacity planning in systems where adaptation is metered.

Future Directions

1. Determine the minimax rate above the feasibility threshold. The key question is whether the GTD(D+2P_T)/S term is an OGD artifact or an unavoidable budget-dependent cost. The authors report that both natural lower-bound constructions fail: the square wave becomes exactly trackable once S ≥ P_T, and a drifting comparator can be followed with O(P_T) extra movement once losses reveal its position.

2. Sharpen the constant in the threshold. The result identifies the asymptotic scale D + P_T but not the exact constant-factor transition; the slack is localized to inequality (11), and the exact dynamic program suggests the empirical transition sits close to S = P_T.

3. Resolve dimension dependence. The lower bound is one-dimensional and lifts to ℝ^d by embedding, but the dependence of the constants on dimension is not resolved.

4. Extend beyond full-gradient feedback. The authors note the square-wave argument is information-free and may transfer to bandit feedback directly, though they have not verified this. They also note their synthetic non-square-wave experiments use quadratic losses while the theory covers all convex Lipschitz losses.

Target Audience

Researchers and graduate students in online learning and online convex optimization who work on dynamic regret, non-stationary optimization, or switching-cost models; theoretically inclined engineers designing systems where adaptation consumes a metered resource (control, portfolio management, infrastructure reconfiguration); and readers who want a crisp, well-scoped example of how an operational constraint — not a statistical one — can dominate learnability.

Authors’ 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.