betaFeedback

WorksComputer Science

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 SS on its total movement ∑t∥xt−xt−1∥\sum_t \|x_t - x_{t-1}\|. Our main result is that a movement budget creates a feasibility barrier. On a domain of diameter DD with GG-Lipschitz convex losses, for every comparator path length PT∈[D,DT]P_T \in [D, DT] we exhibit a deterministic adversary that forces Rd=Ω(GDT)R_d = Ω(GDT) on every budget-feasible algorithm whenever S≤cPTS \le c P_T for a universal constant c>0c>0. This barrier is caused by the budget rather than by a volatile environment: for fixed DD, it applies when PT=o(T)P_T = o(T), where the unconstrained minimax rate Θ(GD(D+PT)T)Θ(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)o(GDT) once S=ω(D+PT)S = ω(D + P_T). Thus the critical movement scale is D+PTD+P_T: linear regret is unavoidable below a sufficiently small constant multiple of PTP_T, while sublinear regret is achievable when S/(D+PT)→∞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/S1/S decay.

Introduction

Dynamic regret in online convex optimization compares a learner’s decisions xtx_t to a moving comparator utu_t [21, 10]. Without movement constraints, the key quantity is the comparator path length PT=∑t≥2∥ut−ut−1∥P_T=\sum_{t\ge2}\lVert u_t-u_{t-1}\rVert: over convex GG-Lipschitz losses on a set of diameter DD, the minimax rate is Θ(GD(D+PT)T)\Theta(G\sqrt{D(D+P_T)T}) [21, 3], which is sublinear whenever PT=o(DT)P_T=o(DT).

These guarantees treat movement as free. In temporal systems, however, adaptation is often an intervention: reconfiguring a controller, changing a served configuration, or rebalancing a portfolio consumes a limited resource. We impose a hard budget S=∑t≥2∥xt−xt−1∥≤SS=\sum_{t\ge2}\lVert x_t-x_{t-1}\rVert\le S and ask when sublinear dynamic regret is feasible at all.

Our main point is that path length alone is not the right hardness measure under a movement budget. A random-walk comparator can have large path length while staying spatially concentrated, so a nearly static learner may still do well. The hard case is different: the comparator must force the learner to travel across the domain. We capture this with a deterministic full-range square wave that alternates between the endpoints of the decision set. The learner knows the sequence; the obstruction is purely whether it can afford to move.

Theorem 1 gives the resulting feasibility statement. For every PT∈[D,DT]P_T \in[D,DT], the square-wave instance forces Rd=Ω(GDT)R_d = \Omega(GDT) on every learner with S≤cPTS \le cP_T, for a universal constant c>0c > 0. Conversely, projected OGD with a budget-aware step size is feasible and achieves o(GDT)o(GDT) once S=ω(D+PT)S = \omega(D + P_T). Thus a hard movement budget can make tracking impossible even when, for fixed DD and PT=o(T)P_T = o(T), the unconstrained problem is learnable. Appendix A gives budget-dependent rates above the threshold, experiments, related work, limitations, and full proofs.

Problem Setup

Protocol. Fix a horizon TT and a compact convex decision set K⊂Rd\mathcal{K} \subset\mathbb{R}^{d} with diameter D=sup⁡x,y∈K∥x−y∥D = \sup_{x,y \in\mathcal{K}} \lVert x-y \rVert. At each round t=1,…,Tt = 1,\ldots,T the learner selects xt∈Kx_t \in\mathcal{K}, then observes a convex loss ft:K→Rf_t:\mathcal{K} \to\mathbb{R} that is GG-Lipschitz, and incurs ft(xt)f_t(x_t). All norms are Euclidean.

Comparator and path length. A comparator sequence is any {ut}t=1T⊂K\{u_t\}_{t=1}^{T} \subset\mathcal{K}; we take ut∈arg⁡min⁡x∈Kft(x)u_t \in\arg\min_{x \in\mathcal{K}} f_t(x) unless stated otherwise. Its path length is

PT=∑t=2T∥ut−ut−1∥,(1)P_T = \sum_{t=2}^{T} \lVert u_t-u_{t-1} \rVert, \tag*{(1)}

which measures how far the comparator travels in total. Note PTP_T can be large while the comparator stays in a small region; this range-versus-path distinction is what motivates the full-range construction below.

Dynamic regret and movement budget. Dynamic regret and switching cost are

Rd=∑t=1T[ft(xt)−ft(ut)],SC=∑t=2T∥xt−xt−1∥.(2)R_d = \sum_{t=1}^{T} [f_t(x_t)-f_t(u_t)], \qquad\mathrm{SC} = \sum_{t=2}^{T} \lVert x_t-x_{t-1} \rVert. \tag*{(2)}

We call an algorithm budget-feasible for budget SS if it guarantees SC≤S\mathrm{SC} \le S on every loss sequence. Throughout, “linear” regret means Rd=Ω(GDT)R_d = \Omega(GDT) and “sublinear” means Rd=o(GDT)R_d = o(GDT); the normalization by GDGD is natural because ∣ft(x)−ft(y)∣≤G∥x−y∥≤GD\lvert f_t(x)-f_t(y)\rvert\le G\lVert x-y\rVert\le GD gives the trivial bound Rd≤GDTR_d \le GDT for any learner.

Unconstrained benchmark. Without a budget, the minimax dynamic regret is Θ(GD(D+PT)T)\Theta(G\sqrt{D(D+P_T)T}) [21, 3], and projected online gradient descent attains it. This is o(GDT)o(GDT) precisely when PT=o(DT)P_T = o(DT). For fixed DD, the regime PT=o(T)P_T = o(T) therefore matters for us: it is where the unconstrained problem is learnable, and hence where any impossibility result can be attributed to the budget rather than to the environment.

The budgeted problem. Given SS, we ask for which SS some budget-feasible algorithm achieves Rd=o(GDT)R_d = o(GDT), and what rate is attainable when one does.

The Movement-Budget Feasibility Threshold

Path length can overstate hardness under a movement budget: a random-walk comparator has path length Θ(Tσ)\Theta(T\sigma) but range only Θ(σT)\Theta(\sigma\sqrt{T}), so it need not force the learner to travel far. We instead use a deterministic full-range comparator. Let K=[0,D]\mathcal{K} = [0,D] and ft(x)=G∣x−ut∣f_t(x) = G\lvert x-u_t\rvert. For a target PT∈[D,DT]P_T \in[D,DT], choose n=min⁡{⌊PT/D⌋,T−1}n = \min\{\lfloor P_T/D \rfloor,T-1\} endpoint crossings and let utu_t alternate between 00 and DD in n+1n+1 long blocks. The realized path length is at most PTP_T, and the learner knows the comparator exactly; the only obstacle is whether it can afford the crossings.

Theorem 1 (Movement-budget feasibility threshold). Fix a horizon TT, a domain of diameter DD, and a path length PTP_T with D≤PT≤DTD \le P_T \le DT.

  1. Impossibility. There exist universal constants c0,c1>0c_0, c_1 > 0 such that for every algorithm with SC≤S\mathrm{SC} \le S there is a comparator sequence of path length at most PTP_T and a sequence of convex, GG-Lipschitz losses on which

Rd≥c0GDT(1−c1SPT).(3)R_d \ge c_0 G D T \left(1 - c_1 \frac{S}{P_T}\right). \tag*{(3)}

In particular Rd=Ω(GDT)R_d = \Omega(GDT) whenever S≤cPTS \le cP_T for a sufficiently small universal constant c>0c > 0.

  1. Achievability. If S=ω(D+PT)S = \omega(D + P_T) and S=o(DT)S = o(DT), then projected OGD with η=S/(GT)\eta= S/(GT) satisfies SC≤S\mathrm{SC} \le S and Rd=o(GDT)R_d = o(GDT).

Thus the critical movement scale is D+PTD + P_T: below a sufficiently small constant multiple of PTP_T linear regret is unavoidable, while S/(D+PT)→∞S/(D + P_T) \to\infty is sufficient for sublinear regret in the learnable regime. Since the theorem assumes PT≥DP_T \ge D, this identifies PTP_T as the asymptotic movement scale, without resolving the exact constant-factor band.

The lower bound is a counting argument over consecutive square-wave block pairs: on each pair, if the learner spends movement MiM_i, its cumulative tracking error is at least a constant multiple of the block length times (D−Mi)(D - M_i). Summing over Θ(PT/D)\Theta(P_T/D) pairs and using ∑iMi≤S\sum_i M_i \le S gives (3); Appendix H gives the full proof with floor and ceiling effects. The constructive direction uses the standard OGD bound Rd≤D(D+2PT)/(2η)+ηG2T/2R_d \le D(D + 2P_T)/(2\eta) + \eta G^2T/2 [21]. With η=S/(GT)\eta= S/(GT), movement is at most TηG=ST\eta G = S and

Rd≤GTD(D+2PT)2S+GS2.(4)R_d \le\frac{GTD(D + 2P_T)}{2S} + \frac{GS}{2}. \tag*{(4)}

which is o(GDT)o(GDT) when S=ω(D+PT)S = \omega(D + P_T) and S=o(DT)S = o(DT).

For fixed DD, the theorem is nonvacuous at PT=o(T)P_T = o(T): the unconstrained rate Θ(GD(D+PT)T)\Theta(G\sqrt{D(D + P_T)T}) is then o(GDT)o(GDT), yet any learner with S≤cPTS \le cP_T suffers linear regret on the same type of instance. Figure 1 illustrates this transition and the sublinear-path regime; additional experiments and the remaining rate gap above the threshold are in Appendix A.

Figure 1. Square-wave adversary. Left: normalized regret drops as the movement budget approaches the comparator path length; the proved lower bound has only constant-factor precision. Right: with PT=T=o(T)P_T = \sqrt{T} = o(T), a budget-starved learner has constant normalized regret while the unconstrained learner decays, showing that the barrier is caused by the movement budget rather than by large path length.

Rates Above the Threshold and Evidence

The feasibility theorem answers when sublinear regret is possible. Above that threshold, the finer rate is only partially characterized. Running projected OGD with

η=min⁡{D(D+2PT)G2T,SGT}\eta= \min\left\{\sqrt{\frac{D(D + 2P_T)}{G^2T}}, \frac{S}{GT}\right\}

keeps SC≤S\mathrm{SC} \le S and gives

Rd≤O(min⁡{GD(D+2PT)T+GTD(D+2PT)S,GDT}).(5)R_d \le O\left(\min\left\{G\sqrt{D(D+2P_T)T}+\frac{GTD(D+2P_T)}{S},GDT\right\}\right). \tag*{(5)}

The first term is the usual unconstrained OGD rate; the second is the price of shrinking the step size to fit the movement budget. The standard unconstrained lower bound Ω(GDPTT)\Omega(G\sqrt{DP_TT}) [3] still applies, but we do not claim a matching lower bound for the budget-dependent 1/S1/S term. Determining the minimax rate above the feasibility threshold remains open.

Our experiments are designed around this separation. Figure 1 tests the theorem itself: the left panel shows the transition as S/PTS/P_T varies, while the right panel fixes PT=T=o(T)P_T=\sqrt{T}=o(T) and separates a budget-induced barrier from ordinary nonstationarity. Appendix D reports two further checks. First, random-walk and rotating-comparator experiments show an empirical 1/S1/S decay consistent with the upper bound (5), but we do not treat this as proof that the 1/S1/S term is minimax tight. Second, five real daily series, S&P 500, EUR/USD, crude oil via USO, Bitcoin, and New York City temperature, show regret remaining high for S≪PTS\ll P_T and dropping near S=PTS=P_T. These finite-horizon experiments test transition location and budget–regret behavior; asymptotic linearity is certified by the square-wave construction, not by the real series.

The closest prior work studies adjacent but different questions. Classical dynamic-regret results characterize adaptation to a moving comparator when movement is free [21, 3], with later work removing prior knowledge of PTP_T or improving constants in richer loss classes [16, 2, 20]. Smoothed online optimization penalizes movement with a Lagrange multiplier rather than imposing a hard budget [12, 1, 6, 9, 18]. Hard switching-budget work is closest in spirit, but existing results focus on static regret or switching count rather than a distance budget for dynamic regret [8, 5, 14, 15]. Our contribution is the feasibility barrier: even when unconstrained dynamic regret is sublinear, a hard movement budget below the scale D+PTD+P_T can make tracking impossible.

This perspective is useful for temporal systems because it separates two roles often conflated under the term “adaptation.” Prediction asks whether the learner can infer where the moving optimum is; intervention asks whether the learner can afford to move there. The square-wave construction removes the prediction issue entirely: the comparator is deterministic and known, yet the learner still fails when its movement budget is too small. Thus the threshold is not a statistical limitation but a physical or operational one.

The remaining gap is also conceptually sharp. Below the threshold, range forces a feasibility barrier. Far above it, standard OGD rates reappear. In between, the known upper bound has a 1/S1/S term, but no matching budget-dependent lower bound is known. Deciding whether this term is an OGD artifact or an unavoidable cost is the main technical question left by the paper.

Additional Rates, Experiments, and Discussion

We state this as a threshold in scale and not as a sharp threshold with a determined constant, and the distinction is real. The impossibility bound (3) has only universal-constant precision, while the experiments in Section D.1 indicate that the empirical transition is close to S=PTS = P_T. Section D.1 reports the empirical constant separately from the proved one, and we do not conflate them.

Dynamic Regret Above the Threshold

Above the threshold the question becomes quantitative. The results in this section refine Theorem 1 and are secondary to it; in particular they do not resolve the rate in the whole range of budgets.

Theorem 2 (Budget-dependent upper bound). Assume each ftf_t is convex and GG-Lipschitz on K\mathcal{K}. Projected OGD with η=min⁡(D(D+2PT)G2T,SGT)\eta= \min\left(\sqrt{\frac{D(D + 2P_T)}{G^2T}}, \frac{S}{GT}\right) satisfies SC≤S\mathrm{SC} \le S and

Rd≤O(min⁡{GD(D+2PT)T+GTD(D+2PT)S, GDT}).(6)R_d \le O\left(\min\left\{G\sqrt{D(D + 2P_T)T} + \frac{GTD(D + 2P_T)}{S}, \, GDT\right\}\right). \tag*{(6)}

The usual unconstrained lower bound Rd≥Ω(GDPTT)R_d \ge\Omega(G\sqrt{DP_TT}) [3] applies to this setting as well, since adding a movement budget cannot make the problem easier. We do not know whether the additional 1/S1/S term in (6) is minimax tight.

Remark 3 (What is and is not established). Theorem 2 is an upper bound, not a minimax characterization. We therefore do not claim a product law Rd⋅S=Θ(GTD(D+PT))R_d \cdot S = \Theta(GTD(D + P_T)). The exact rate above the feasibility threshold, and in particular the tightness of the GTD(D+2PT)/SGTD(D + 2P_T)/S term, is open.

We also note that (6) is informative only when S≳D+PTS \gtrsim D+P_T: for smaller SS the term GTD(D+2PT)/SGTD(D+2P_T)/S exceeds the trivial bound GDTGDT, and Theorem 1 shows linear regret is in fact unavoidable there. The two results thus cover complementary ranges of SS.

Budget-Controlled OGD

The algorithm used for both constructive results is projected OGD with a budget-aware step size:

xt+1=ΠK(xt−η∇ft(xt)),η=min⁡(D(D+2PT)G2T,SGT).(7)x_{t+1} = \Pi_{\mathcal{K}}(x_t - \eta\nabla f_t(x_t)), \qquad\eta= \min\left(\sqrt{\frac{D(D + 2P_T)}{G^2T}}, \frac{S}{GT}\right). \tag*{(7)}

Proposition 4 (Budget-Controlled OGD). Assume each ftf_t is convex and GG-Lipschitz. The update (7) satisfies SC≤S\mathrm{SC} \le S and E[Rd]≤O(GD(D+2PT)T+GTD(D+2PT)/S)\mathbb{E}[R_d] \le O\left(G\sqrt{D(D + 2P_T)T} + GTD(D + 2P_T)/S\right). When PTP_T is unknown, a doubling trick preserves the rate up to constants.

The algorithm is not new: it is the standard OGD of Zinkevich [2003] run at a particular step size. What the analysis contributes is the identification of that step size. The two arguments of the minimum in (7) correspond to the two regimes: the first is the usual unconstrained optimum, the second is the largest step for which the budget is respected without any explicit projection onto the constraint, since per-round movement is bounded by ηG\eta G and there are TT rounds. Budget feasibility is thus enforced by the step size alone. We do not claim (7) is a new optimization method, and by Remark 3 we use it as a constructive upper bound rather than as a fully minimax-optimal method above the threshold.

Experiments

The experiments are organized by which claim they test. Section D.1 uses the square wave, the instance our lower bound is actually proved against. Section D.2 isolates the regime PT=o(T)P_T = o(T) that makes the barrier attributable to the budget. The remaining subsections use a random-walk comparator and real series to examine the transition location and the 1/S1/S decay. A random-walk comparator is spatially concentrated, so it cannot certify a budget-induced barrier, and we do not use it for that purpose.

The budget-induced transition

Figure 2(A) sweeps S/PTS/P_T for a near-optimal budget-feasible tracker at T=4000T=4000. The curves for three path lengths collapse onto a single line Rd/(GDT)=12(1−S/PT)R_d/(GDT)=\frac{1}{2}(1-S/P_T) that vanishes at S=PTS=P_T. The proved lower bound has more conservative constants and lies below this empirical curve.

We report these two constants separately on purpose. An exact dynamic program over discretized position and budget, which lower bounds every algorithm, places the true optimum slightly below 12(1−S/PT)\frac{1}{2}(1-S/P_T): at T=240T=240 and PT=29P_T=29 it gives 0.364 versus 0.375 at S=PT/4S=P_T/4, and 0.242 versus 0.250 at S=PT/2S=P_T/2, in units of GDTGDT. Crucially it vanishes only at S=PTS=P_T. This is empirical evidence that the constants in Theorem 1 are conservative and that some slack sits in inequality (11). It is not a theorem, and we do not upgrade it to one; the proved statement remains (3).

The dotted curve shows Budget-Controlled OGD rising above the frozen-learner value before falling. This is a lag effect specific to this instance: at small step sizes the iterate arrives at one endpoint around the time the comparator leaves it, so part of the horizon is spent in antiphase. It does not contradict Theorem 2, whose upper bound is a worst-case statement and is not tight here, but it does show that the near-optimal tracker and OGD differ by more than a constant on this family.

The sublinear-path-length regime

Figure 2(B) fixes PT=TP_T=\sqrt{T}, so PT=o(T)P_T=o(T), and grows TT from 250 to 8000. The budget-starved learner at S=PT/4S=P_T/4 has normalized regret flat in TT, moving from 0.492 to 0.500, so its regret is linear. The unconstrained learner decays from 0.060 to 0.011 over the same range, consistent with T−1/2T^{-1/2}.

This is the experiment that separates the two hypotheses. Both learners face identical loss sequences drawn from a regime where the unconstrained problem is learnable. One is starved of movement and is not. This is the empirical counterpart of the novacuity statement in Theorem 1: the same regime is learnable without a budget but not with insufficient movement. It is the claim a random-walk comparator cannot support.

Budget–regret trade-off

Figure 3 plots the empirical (SC,Rd)(\mathrm{SC}, R_d) trade-off for Budget-Controlled OGD, Lazy OGD, and SOCO on a random-walk comparator. All three trace a 1/S1/S decay over the mid-range of budgets, with Budget-Controlled OGD attaining the lowest regret at each budget level.

Figure 3. Empirical budget–regret trade-off on a random-walk comparator. All methods trace a 1/S1/S decay over the mid-range of budgets, with Budget-Controlled OGD attaining the lowest regret at each budget. This is consistency with the upper bound (6) only. The dashed guide line is a 1/S1/S reference and is not evidence of a matched product law; by Remark 3 tightness of the 1/S1/S term is unproved.

This is empirical consistency with the upper bound (6) only. By Remark 3, the tightness of the 1/S1/S term is open, so these curves must not be read as confirming a product law.

Algorithm comparison

Across oscillating, rotating, and piecewise stationary synthetic environments, Budget-Controlled OGD matches or outperforms Lazy OGD, SOCO, and Periodic Restart at all budget levels (Appendix § 15, Figure 6); Periodic Restart is included as a standard baseline for non-stationary online optimization [3]. Lazy OGD is handicapped by its threshold update rule, which spends budget on small moves during low-volatility stretches; Periodic Restart suffers when its restart boundaries are misaligned with the environment. On real data the same ordering holds on the S&P 500, Bitcoin, and NYC temperature series.

Figure 6. Budget-Controlled OGD against Lazy OGD, SOCO, and Periodic Restart across oscillating, rotating, and piecewise stationary environments. Periodic Restart follows the standard restarting baseline for non-stationary online optimization [3]. Budget-Controlled OGD matches or outperforms the baselines at all budget levels.

Real-world series

We use five daily series as comparator sequences, each normalized: the S&P 500 index (T=1509T=1509), the EUR/USD exchange rate (T=1564T=1564), crude oil via the USO ETF (T=1509T=1509), Bitcoin (T=2191T=2191), and mean temperature in New York City (T=2192T=2192).

Figure 4 shows regret staying elevated for S≪PTS \ll P_T and dropping near S=PTS = P_T on all five, locating the transition where Theorem 1 places it. The drop is sharpest for Bitcoin and temperature and more gradual for the S&P 500, whose trajectory is smoother. Trajectory-level behaviour matches: at S=0.05PTS = 0.05P_T the learner barely moves and incurs Rd/T≈0.47R_d/T \approx0.47; at S=0.3PTS = 0.3P_T tracking improves substantially; at S=PTS = P_T the learner tracks near-perfectly with Rd/T<0.01R_d/T < 0.01 (Appendix § 15).

Phase Transition on Real-World Data

Figure 4. Transition location on five real series (S&P 500, EUR/USD, crude oil, Bitcoin, NYC temperature). Regret stays elevated for S≪PTS \ll P_T and drops near S=PTS = P_T on all five, placing the transition where Theorem 1 predicts. Finite horizons cannot separate Θ(T)\Theta(T) from o(T)o(T), so these panels test the location of the transition and the 1/S1/S decay, not asymptotic linearity; that claim rests on Figure 2(B).

Finite-horizon caveat. These series have modest path-length ratios: PT/TP_T/T is 0.0330.033 (S&P 500), 0.0320.032 (Bitcoin), 0.0680.068 (EUR/USD), 0.0520.052 (oil) and 0.2500.250 (temperature), against T(1+PT)\sqrt{T}(1 + P_T) of 277277, 397397, 410410, 347347 and 10971097 respectively. Every dataset therefore sits in the regime PT≪T(1+PT)P_T \ll\sqrt{T}(1 + P_T), where the window PT≲S≲D(D+PT)TP_T \lesssim S \lesssim\sqrt{D(D + P_T)T} spans roughly half a decade in SS. At a single finite horizon one cannot separate Θ(T)\Theta(T) from o(T)o(T), so these experiments test the location of the transition and the 1/S1/S decay and cannot by themselves establish asymptotic linearity. That claim rests on Figure 2(B).

Figure 2. Square-wave adversary on K=[0,D]\mathcal{K}=[0,D] with ft(x)=G∣x−ut∣f_t(x)=G\lvert x-u_t\rvert. (A) Normalized regret of a near-optimal budget-feasible tracker against S/PTS/P_T. Curves for PT/T∈{0.05,0.15,0.4}P_T/T\in\{0.05,0.15,0.4\} collapse onto 12(1−S/PT)\frac{1}{2}(1-S/P_T) and reach zero at S=PTS=P_T. The dashed line shows the scale of the proved lower bound in Theorem 1; its constants are conservative, and the empirical transition occurs closer to S=PTS=P_T. The dotted curve is Budget-Controlled OGD, which pays an additional lag penalty on this instance. (B) Fixing PT=T=o(T)P_T=\sqrt{T}=o(T) and growing TT: the starved learner (S=PT/4S=P_T/4) stays flat near 0.5, so its regret is linear, while the unconstrained learner decays as T−1/2T^{-1/2}. Both axes logarithmic.

Related Work

Dynamic regret. Dynamic regret against a moving comparator originates with Zinkevich [ [21], who gave the O(D(D+PT)/η+ηG2T)O(D(D + P_T)/\eta+ \eta G^2T) bound for OGD that we use. Besbes et al. [ [3] established minimax rates for non-stationary stochastic optimization and supply the Ω(GDPTT)\Omega(G\sqrt{DP_TT}) lower bound in Theorem 2. Subsequent work develops adaptive and parameter-free methods that attain path-length-dependent rates without knowing PTP_T [16, 17, 19, 2, 20], and Jacobsen and Orabona [ [11] relates static and dynamic regret through lifted constructions. All of this assumes movement is free.

Switching costs and smoothed online optimization. Smoothed online convex optimization augments the loss with a movement penalty, ∑tft(xt)+λ∑t∥xt−xt−1∥\sum_t f_t(x_t) + \lambda\sum_t \lVert x_t - x_{t-1} \rVert, and yields competitive algorithms such as online balanced descent [12, 1, 6, 9]. Recent work also studies dynamic regret when the switching cost is part of the performance metric [18]. A soft penalty selects a single operating point through λ\lambda; it does not answer whether learning is possible at a prescribed budget, which is the question Theorem 1 addresses.

Hard switching constraints. Closest to our setting are hard constraints on movement. Wang et al. [ [15] study continuous switching distance constraints and Sherman and Koren [ [14] constrain the switching count; both target static regret. Switching-budget lower bounds also appear in bandit and switching-constrained OCO models [8, 5]. Table 1 summarizes the positioning. To our knowledge no prior work identifies a feasibility threshold for dynamic regret under a hard movement-distance budget.

WorkRegretConstraintMinimaxThreshold
Besbes et al. [ [3]Dyn.NoneYesNo
Baby and Wang [ [2]Dyn.NoneYesNo
Zhao et al. [ [20]Dyn.NoneNoNo
Zhang et al. [ [18]Dyn.SoftYesNo
Dekel et al. [ [8]Stat.Switch costYesNo
Chen et al. [ [5]Stat.CountYesNo
Sherman and Koren [ [14]Stat.CountYesNo
Wang et al. [ [15]Stat.Dist.PartialNo
Chen et al. [ [6]Dyn.SoftNoNo
This workDyn.Dist.Open1Yes

Table 1. Positioning. “Dyn.” and “Stat.” denote dynamic and static regret; “Dist.” and “Count” denote switching-distance and switching-count constraints.

Limitations and Open Problems

Rates above the threshold. The main open problem is the minimax rate once SS exceeds the feasibility threshold. Resolving it appears to require understanding whether the 1/S1/S term in Theorem 2 is an OGD artifact or reflects an unavoidable budget-dependent price. The two natural lower-bound constructions each fail on one count. Our square wave is deterministic and becomes exactly trackable once S≥PTS \ge P_T, so it certifies nothing above the threshold. A drifting comparator can be followed with O(PT)O(P_T) additional movement once the observed losses reveal its position, so for S≫PTS \gg P_T increasing PTP_T does not obviously help the adversary. We therefore do not claim minimax optimality for Theorem 2.

The constant in the threshold. Theorem 1 proves the threshold only up to universal constants, while the exact dynamic program of Section D.1 indicates the empirical transition is close to S=PTS = P_T.

The result should therefore be read as identifying the asymptotic movement scale D+PTD + P_T, not as determining the exact constant-factor transition. The slack is localized to inequality (11).

What each piece of evidence supports. We distinguish three levels deliberately. The square-wave construction proves linear regret for S≤cPTS \le cP_T for a universal constant c>0c > 0, uniformly over PT∈[D,DT]P_T \in[D,DT], and Figure 2(B) provides the corresponding empirical demonstration at PT=o(T)P_T = o(T). The random-walk and real-data experiments show that the transition sits near S=PTS = P_T and that regret decays as 1/S1/S; because they run at fixed finite horizons they cannot distinguish Θ(T)\Theta(T) from o(T)o(T), and because the random-walk comparator is spatially concentrated it could not certify a budget-induced barrier even asymptotically. The tight rate above the threshold, and the exact constant at the threshold, remain unknown.

Other limitations. The lower bound is one-dimensional; it lifts to Rd\mathbb{R}^d by embedding, but the dimension dependence of the constants is not resolved. Our synthetic non-square-wave experiments use quadratic losses, while the theory covers all convex Lipschitz losses. We assume full gradient feedback; we note that the square-wave argument is information-free, so it may transfer to bandit feedback directly, though we have not verified this.

Conclusion

A hard movement budget can make dynamic tracking impossible even when the underlying nonstationarity is mild enough that unconstrained dynamic regret is sublinear. Concretely: a deterministic full-range adversary forces linear regret on every budget-feasible algorithm whenever S≤cPTS \le cP_T for a universal constant c>0c > 0 and every PT∈[D,DT]P_T \in[D,DT]; projected OGD with a budget-aware step size achieves o(GDT)o(GDT) once S=ω(D+PT)S = \omega(D + P_T); together these identify D+PTD + P_T as the critical movement scale, with the constant-factor band left open. Above the threshold, budget-controlled OGD gives a concrete 1/S1/S upper bound, but its minimax tightness remains open. Experiments support the transition picture, locate it near S=PTS = P_T, and exhibit empirical 1/S1/S decay.

The construction turns on treating comparator range rather than path length as the relevant measure of difficulty, and we expect that distinction to be useful wherever a learner is charged for the distance it travels.

Proof of Theorem 1

We prove the two directions separately. The construction is deterministic, so no expectations are needed.

Impossibility

Fix D≤PT≤DTD \le P_T \le DT, take K=[0,D]⊂R\mathcal{K} = [0,D] \subset\mathbb{R} and the losses

ft(x)=G∣x−ut∣,(8)f_t(x) = G|x-u_t|, \tag*{(8)}

which are convex, GG-Lipschitz, and satisfy ft(ut)=0f_t(u_t)=0. Since these are a special case of the convex GG-Lipschitz class, a lower bound against them applies to the whole class.

The comparator. Let n=min⁡{⌊PT/D⌋,T−1}≥1n = \min\{\lfloor P_T/D\rfloor,T-1\} \ge1 and τ=⌊T/(n+1)⌋≥1\tau= \lfloor T/(n+1)\rfloor\ge1. For the first (n+1)τ(n+1)\tau rounds set

ut={0⌊(t−1)/τ⌋ even,D⌊(t−1)/τ⌋ odd,(9)u_t = \begin{cases} 0 & \lfloor(t-1)/\tau\rfloor\text{ even},\\ D & \lfloor(t-1)/\tau\rfloor\text{ odd}, \end{cases} \tag*{(9)}

and hold the final value for any leftover rounds. Thus the comparator alternates between the endpoints of K\mathcal{K} for n+1n+1 blocks. There are exactly nn switches, each of length DD, so the realized path length is nD≤PTnD \le P_T and the instance is admissible.

Per-block-pair error. Group the first n+1n+1 blocks into disjoint consecutive pairs (B1,B2),(B3,B4),…(B_1,B_2),(B_3,B_4),\ldots, with u≡0u \equiv0 on odd-indexed and u≡Du \equiv D on even-indexed blocks. Let N=⌊(n+1)/2⌋N=\lfloor(n+1)/2\rfloor be the number of complete pairs. For the ii-th pair put Mi=∑t∈B2i−1∪B2i∥xt−xt−1∥M_i=\sum_{t\in B_{2i-1}\cup B_{2i}}\|x_t-x_{t-1}\| and mi=min⁡t∈B2i−1∪B2ixtm_i=\min_{t\in B_{2i-1}\cup B_{2i}}x_t. The range of a trajectory is at most its total variation, so every xtx_t in the pair lies in [mi,mi+Mi][m_i,m_i+M_i]. Hence

∑t∈B2i−1∣xt−0∣≥τmi,∑t∈B2i∣xt−D∣≥τ(D−mi−Mi),(10)\sum_{t\in B_{2i-1}} |x_t-0| \ge\tau m_i,\qquad \sum_{t\in B_{2i}} |x_t-D| \ge\tau(D-m_i-M_i), \tag*{(10)}

and adding gives

∑t∈B2i−1∪B2i∣xt−ut∣≥τ(D−Mi).(11)\sum_{t\in B_{2i-1}\cup B_{2i}} |x_t-u_t| \ge\tau(D-M_i). \tag*{(11)}

The right-hand side may be negative, in which case the inequality is vacuous but still valid, which is all we use.

Where the constant is lost. Inequality (11) bounds the two blocks by a common worst case, and this is where the factor of two enters. An exact dynamic program over discretized position and budget, which lower bounds every algorithm whether online or not, puts the true optimum slightly below GDT2(1−S/PT)\frac{GDT}{2}(1-S/P_T): at T=240T=240 and PT=29P_T=29 it gives 0.364 versus 0.375 at S=PT/4S=P_T/4, and 0.242 versus 0.250 at S=PT/2S=P_T/2, in units of GDTGDT. Crucially it vanishes only at S=PTS=P_T, not at S=PT/2S=P_T/2. Sharpening this step would recover the constant without changing the structure of the argument.

Summing. The pairs occupy disjoint sets of rounds, so ∑i=1NMi≤SC≤S\sum_{i=1}^{N} M_i \le S_C \le S. Summing (11) over the pairs,

∑t=1T∣xt−ut∣≥τ∑i=1N(D−Mi)≥τ(ND−S).(12)\sum_{t=1}^{T}|x_t-u_t| \ge\tau\sum_{i=1}^{N}(D-M_i) \ge\tau(ND-S). \tag*{(12)}

Since N≥n/2N \ge n/2 and τ≥T/(2(n+1))\tau\ge T/(2(n+1)), while n+1≤2PT/Dn+1 \le2P_T/D whenever PT≥DP_T \ge D, we have τND≥TD/8\tau ND \ge TD/8. Also, because n+1≥PT/Dn+1 \ge P_T/D, we have τ≤TD/PT\tau\le TD/P_T. Substituting these two estimates,

Rd=G∑t=1T∣xt−ut∣≥GDT8−GDTPTS=GDT8(1−8SPT),(13)R_d = G\sum_{t=1}^{T}|x_t-u_t| \ge\frac{GDT}{8}-\frac{GDT}{P_T}S = \frac{GDT}{8}\left(1-\frac{8S}{P_T}\right), \tag*{(13)}

which is (3) with universal constants. In particular Rd=Ω(GDT)R_d=\Omega(GDT) whenever S≤cPTS\le cP_T for a sufficiently small universal constant c>0c>0.

Achievability

Run projected OGD with the fixed step size η=S/(GT)\eta=S/(GT). Each step moves at most η∥∇ft∥≤ηG\eta\|\nabla f_t\|\le\eta G, so SC≤TηG=SS_C\le T\eta G=S and the constraint holds by construction. By Lemma 6, $R_d\le D(D+2P_T)/(2\eta)+ ηG2T/2\eta G^2T/2, which on substituting η\eta gives (4). If S=ω(D+PT)S=\omega(D+P_T) the first term is o(GDT)o(GDT), and if S=o(DT)S=o(DT) the second is o(GDT)o(GDT). Hence Rd=o(GDT)R_d=o(GDT).

Combining, regret is linear whenever S≤cPTS\le cP_T for a universal constant c>0c>0 and sublinear whenever S=ω(D+PT)S=\omega(D+P_T) with S=o(DT)S=o(DT). Because PT≥DP_T\ge D, both sides identify PTP_T as the asymptotic movement scale, while the exact constant-factor band remains unresolved. □

Remark 5 (Why a deterministic adversary). A random-walk comparator ut=ut−1+ξtu_t=u_{t-1}+\xi_t with ξt\xi_t Rademacher of scale σ\sigma has path length TσT\sigma but spatial range only Θ(σT)\Theta(\sigma\sqrt{T}), so a learner that never moves and sits at the centre of the range incurs Θ(σT)\Theta(\sigma\sqrt{T}) per round rather than Θ(D)\Theta(D). The resulting bound is Ω(PT2/T)\Omega(P_T^2/T), linear only when PT=Θ(T)P_T=\Theta(T), a regime in which the unconstrained rate is already linear, so no budget-induced barrier can be concluded from that construction. The square wave forces the comparator to traverse the entire domain, making range and diameter coincide.

Proof of Theorem 2

We first restate the classical bound we build on.

Lemma 6 (Dynamic regret of OGD; Zinkevich, [21]). Let KK have diameter DD and let each ftf_t be convex and GG-Lipschitz. Projected OGD with fixed step size η>0\eta>0 satisfies, for any comparator sequence with path length PTP_T,

∑t=1T[ft(xt)−ft(ut)]≤D(D+2PT)2η+ηG2T2.(14)\sum_{t=1}^{T}\left[f_t(x_t)-f_t(u_t)\right]\le\frac{D(D+2P_T)}{2\eta}+\frac{\eta G^2T}{2}. \tag*{(14)}

Upper bound. Run projected OGD with the fixed, time-independent step size η=min⁡(D(D+2PT)/(G2T),S/(TG))\eta=\min(\sqrt{D(D+2P_T)/(G^2T)},S/(TG)). Per-round movement is at most ηG\eta G, so SC≤TηG≤SS_C\le T\eta G\le S.

Case 1 (budget-rich). When S≥DT(D+2PT)S\ge\sqrt{DT(D+2P_T)} we have η=η∗=D(D+2PT)/(G2T)\eta=\eta^*=\sqrt{D(D+2P_T)/(G^2T)}, and Lemma 6 gives Rd≤GD(D+2PT)TR_d\le G\sqrt{D(D+2P_T)T}. The dependence on the diameter here is D\sqrt{D} rather than DD: minimizing D(D+2PT)/(2η)+ηG2T/2D(D+2P_T)/(2\eta)+\eta G^2T/2 yields GD(D+2PT)T≈G2DPTTG\sqrt{D(D+2P_T)T}\approx G\sqrt{2DP_TT} when PT≥DP_T\ge D. We keep the exact form throughout.

Case 2 (budget-constrained). When S<DT(D+2PT)S<\sqrt{DT(D+2P_T)} we have η=S/(TG)\eta=S/(TG), and substituting,

D(D+2PT)2η=GTD(D+2PT)2S,ηG2T2=GS2,(15)\frac{D(D+2P_T)}{2\eta}=\frac{GTD(D+2P_T)}{2S},\qquad\frac{\eta G^2T}{2}=\frac{GS}{2}, \tag*{(15)}

so Rd≤O(GTD(D+2PT)/S)R_d\le O(GTD(D+2P_T)/S). Taking the minimum with the trivial bound Rd≤GDTR_d\le GDT gives (6). □

For comparison: unconstrained lower bound. Rd≥Ω(GDPTT)R_d\ge\Omega(G\sqrt{DP_TT}) is the unconstrained dynamic regret lower bound of Besbes et al. [2015]. Their construction does not rely on a movement constraint, so it remains a valid lower bound in the budgeted setting whenever the budget is large enough to permit the comparator-scale motion. We do not provide a matching lower bound for the GTD(D+2PT)/SGTD(D+2P_T)/S term in (6); this is the main open rate question left by the paper.

Extensions

The following are corollaries of Theorem 1, obtained by computing an induced path length and invoking the main theorem; they contain no new argument. They are stated under the hypothesis PT=Θ(T)P_T=\Theta(T), which is the regime in which the unconstrained rate is already linear, so on their own they do not certify a budget-induced barrier. Applying the square-wave construction in these settings, which would require exhibiting latent dynamics whose induced comparator traverses the domain, is left to future work. We record them as illustrations of the reduction, not as independent contributions.

Latent dynamical systems. Let {zt}\{z_t\} evolve as zt+1=T(zt,ξt)z_{t+1}=\mathcal{T}(z_t,\xi_t) for a possibly unknown transition operator T\mathcal{T} and exogenous noise {ξt}\{\xi_t\}, with losses ft(x)=ℓ(x,zt)f_t(x)=\ell(x,z_t) where ℓ(⋅,z)\ell(\cdot,z) is convex and LL-Lipschitz, and let ut∈arg⁡min⁡xft(x)u_t\in\arg\min_x f_t(x). If the induced path length satisfies PT=Θ(T)P_T=\Theta(T), then any algorithm with S=o(T)S=o(T) has E[Rd]=Θ(T)\mathbb{E}[R_d]=\Theta(T), while S=Ω(PT)S=\Omega(P_T) makes sublinear dynamic regret achievable.

Event-driven environments. When environment changes arrive as a point process [7], the induced path length is governed by the expected number of events, and the same reduction applies once that quantity is Θ(T)\Theta(T).

Spectral view. For environments generated by a linear evolution operator, the induced path length can be expressed through the operator’s spectrum [13, 4], and the feasibility condition again reduces to comparing SS with PTP_T.

Additional Experimental Results

Setup. Synthetic experiments use two comparators, for two different purposes. The square wave of Appendix H is the instance the lower bound is proved against, and is used in Sections D.1 and D.2. The random walk ut=ut−1+ξtu_t = u_{t-1} + \xi_t with ξt\xi_t Rademacher is used for the transition-location and 1/S1/S plots; as Remark 5 explains it cannot certify a budget-induced barrier and we do not use it for that. Unless stated otherwise, results are averaged over 20 seeds.

Figure 5. Random-walk comparator: normalized regret Rd/TR_d/T against S/PTS/P_T for drift magnitudes σ∈{0.1,0.5,1.0}\sigma\in\{0.1, 0.5, 1.0\} at T=5000T = 5000, with the red dashed line at S=PTS = P_T and shading showing ±1\pm1 standard deviation over 20 seeds. The drop near S=PTS = P_T locates the transition; because this comparator is spatially concentrated, it does not by itself certify a budget-induced barrier (Remark 5).

Figure 7. Transition location for d∈{1,2,5,10,20}d \in\{1, 2, 5, 10, 20\}. The location S/PT≈1S/P_T \approx1 is flat in dd because SS and PTP_T are measured in the same norm; how the constants and DD scale with dimension is not resolved here.

Figure 8. Budget–regret trade-off on the five real series. The curves follow Rd∝1/SCR_d \propto1/\mathrm{SC} over the mid-range of budgets, consistent with the upper bound (6) only.

Figure 9. Algorithm comparison on real series. Budget-Controlled OGD dominates Lazy OGD and Periodic Restart on the S&P 500, Bitcoin, and NYC temperature.

Figure 10. Learner trajectories on Bitcoin and NYC temperature at three budget levels. At S=0.05PTS = 0.05P_T the learner barely moves and incurs Rd/T≈0.47R_d/T \approx0.47; at S=0.3PTS = 0.3P_T tracking improves substantially; at S=PTS = P_T the learner tracks near-perfectly with Rd/T<0.01R_d/T < 0.01.

References

  1. [1]Lachlan Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman. A tale of two metrics: Simultaneous bounds on competitiveness and regret. In Conference on Learning Theory, pages 741–763. PMLR, 2013.
  2. [2]Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Conference on Learning Theory, pages 359–409. PMLR, 2021.arxiv.org/abs/2104.11824
  3. [3]Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 63(5):1227–1244, 2015.
  4. [4]Marko Budišić, Ryan Mohr, and Igor Mezić. Applied koopmanism. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(4), 2012.DOI
  5. [5]Lin Chen, Qian Yu, Hannah Lawrence, and Amin Karbasi. Minimax regret of switching-constrained online convex optimization: No phase transition. Advances in Neural Information Processing Systems, 33:3477–3486, 2020.arxiv.org/abs/1910.10873
  6. [6]Nianɡjun Chen, Gautam Goel, and Adam Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Conference On Learning Theory, pages 1574–1594. PMLR, 2018.arxiv.org/abs/1803.10366
  7. [7]Daryl J Daley and David Vere-Jones. An introduction to the theory of point processes: volume II: general theory and structure. Springer, 2008.
  8. [8]Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T²/³ regret. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 459–467, 2014.
  9. [9]Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Advances in Neural Information Processing Systems, 32, 2019.arxiv.org/abs/1905.12776
  10. [10]Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2 (3-4):157–325, 2016.
  11. [11]Andrew Jacobsen and Francesco Orabona. An equivalence between static and dynamic regret minimization. Advances in Neural Information Processing Systems, 37:9835–98870, 2024.arxiv.org/abs/2406.01577
  12. [12]Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. Dynamic right-sizing for power-proportional data centers. In 2011 Proceedings IEEE INFOCOM, pages 1098–1106, 2011. doi: 10.1109/INFCOM.2011.5934885.DOI
  13. [13]Igor Mezić. Spectral properties of dynamical systems, model reduction and decompositions. Nonlinear Dynamics, 41(1):309–325, 2005.DOI
  14. [14]Uri Sherman and Tomer Koren. Lazy oco: Online convex optimization on a switching budget. In Conference on Learning Theory, pages 3972–3988. PMLR, 2021.arxiv.org/abs/2102.03803
  15. [15]Guanghui Wang, Yuanyu Wan, Tianbao Yang, and Lijun Zhang. Online convex optimization with continuous switching constraint. Advances in Neural Information Processing Systems, 34:28636–28647, 2021.arxiv.org/abs/2103.11370
  16. [16]Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In International Conference on Machine Learning, pages 449–457. PMLR, 2016.arxiv.org/abs/1605.04638
  17. [17]Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. Advances in neural information processing systems, 31, 2018.arxiv.org/abs/1810.10815
  18. [18]Lijun Zhang, Wei Jiang, Shiyin Lu, and Tianbao Yang. Revisiting smoothed online learning. Advances in Neural Information Processing Systems, 34:13599–13612, 2021.
  19. [19]Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. Advances in Neural Information Processing Systems, 33:12510–12520, 2020.arxiv.org/abs/2007.03479
  20. [20]Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1–52, 2024.
  21. [21]Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928–936, 2003.

Paper details

vlnc:W_4wb9qt5n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents