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 on its total movement . Our main result is that a movement budget creates a feasibility barrier. On a domain of diameter with -Lipschitz convex losses, for every comparator path length we exhibit a deterministic adversary that forces on every budget-feasible algorithm whenever for a universal constant . This barrier is caused by the budget rather than by a volatile environment: for fixed , it applies when , where the unconstrained minimax rate 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 once . Thus the critical movement scale is : linear regret is unavoidable below a sufficiently small constant multiple of , while sublinear regret is achievable when 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 decay.
Introduction
Dynamic regret in online convex optimization compares a learner’s decisions to a moving comparator [21, 10]. Without movement constraints, the key quantity is the comparator path length : over convex -Lipschitz losses on a set of diameter , the minimax rate is [21, 3], which is sublinear whenever .
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 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 , the square-wave instance forces on every learner with , for a universal constant . Conversely, projected OGD with a budget-aware step size is feasible and achieves once . Thus a hard movement budget can make tracking impossible even when, for fixed and , 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 and a compact convex decision set with diameter . At each round the learner selects , then observes a convex loss that is -Lipschitz, and incurs . All norms are Euclidean.
Comparator and path length. A comparator sequence is any ; we take unless stated otherwise. Its path length is
which measures how far the comparator travels in total. Note 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
We call an algorithm budget-feasible for budget if it guarantees on every loss sequence. Throughout, “linear” regret means and “sublinear” means ; the normalization by is natural because gives the trivial bound for any learner.
Unconstrained benchmark. Without a budget, the minimax dynamic regret is [21, 3], and projected online gradient descent attains it. This is precisely when . For fixed , the regime 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 , we ask for which some budget-feasible algorithm achieves , 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 but range only , so it need not force the learner to travel far. We instead use a deterministic full-range comparator. Let and . For a target , choose endpoint crossings and let alternate between and in long blocks. The realized path length is at most , 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 , a domain of diameter , and a path length with .
Impossibility. There exist universal constants such that for every algorithm with there is a comparator sequence of path length at most and a sequence of convex, -Lipschitz losses on which
In particular whenever for a sufficiently small universal constant .
Achievability. If and , then projected OGD with satisfies and .
Thus the critical movement scale is : below a sufficiently small constant multiple of linear regret is unavoidable, while is sufficient for sublinear regret in the learnable regime. Since the theorem assumes , this identifies 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 , its cumulative tracking error is at least a constant multiple of the block length times . Summing over pairs and using gives (3); Appendix H gives the full proof with floor and ceiling effects. The constructive direction uses the standard OGD bound [21]. With , movement is at most and
which is when and .
For fixed , the theorem is nonvacuous at : the unconstrained rate is then , yet any learner with 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 , 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
keeps and gives
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 [3] still applies, but we do not claim a matching lower bound for the budget-dependent 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 varies, while the right panel fixes 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 decay consistent with the upper bound (5), but we do not treat this as proof that the 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 and dropping near . 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 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 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 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 . 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 is convex and -Lipschitz on . Projected OGD with satisfies and
The usual unconstrained lower bound [3] applies to this setting as well, since adding a movement budget cannot make the problem easier. We do not know whether the additional 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 . The exact rate above the feasibility threshold, and in particular the tightness of the term, is open.
We also note that (6) is informative only when : for smaller the term exceeds the trivial bound , and Theorem 1 shows linear regret is in fact unavoidable there. The two results thus cover complementary ranges of .
Budget-Controlled OGD
The algorithm used for both constructive results is projected OGD with a budget-aware step size:
Proposition 4 (Budget-Controlled OGD). Assume each is convex and -Lipschitz. The update (7) satisfies and . When 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 and there are 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 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 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 for a near-optimal budget-feasible tracker at . The curves for three path lengths collapse onto a single line that vanishes at . 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 : at and it gives 0.364 versus 0.375 at , and 0.242 versus 0.250 at , in units of . Crucially it vanishes only at . 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 , so , and grows from 250 to 8000. The budget-starved learner at has normalized regret flat in , 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 .
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 trade-off for Budget-Controlled OGD, Lazy OGD, and SOCO on a random-walk comparator. All three trace a 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 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 reference and is not evidence of a matched product law; by Remark 3 tightness of the term is unproved.
This is empirical consistency with the upper bound (6) only. By Remark 3, the tightness of the 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 (), the EUR/USD exchange rate (), crude oil via the USO ETF (), Bitcoin (), and mean temperature in New York City ().
Figure 4 shows regret staying elevated for and dropping near 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 the learner barely moves and incurs ; at tracking improves substantially; at the learner tracks near-perfectly with (Appendix § 15).

Figure 4. Transition location on five real series (S&P 500, EUR/USD, crude oil, Bitcoin, NYC temperature). Regret stays elevated for and drops near on all five, placing the transition where Theorem 1 predicts. Finite horizons cannot separate from , so these panels test the location of the transition and the decay, not asymptotic linearity; that claim rests on Figure 2(B).
Finite-horizon caveat. These series have modest path-length ratios: is (S&P 500), (Bitcoin), (EUR/USD), (oil) and (temperature), against of , , , and respectively. Every dataset therefore sits in the regime , where the window spans roughly half a decade in . At a single finite horizon one cannot separate from , so these experiments test the location of the transition and the decay and cannot by themselves establish asymptotic linearity. That claim rests on Figure 2(B).
!Square-wave adversary on bbox=0.17,0.10,0.82,0.28
Figure 2. Square-wave adversary on with . (A) Normalized regret of a near-optimal budget-feasible tracker against . Curves for collapse onto and reach zero at . 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 . The dotted curve is Budget-Controlled OGD, which pays an additional lag penalty on this instance. (B) Fixing and growing : the starved learner () stays flat near 0.5, so its regret is linear, while the unconstrained learner decays as . Both axes logarithmic.
Related Work
Dynamic regret. Dynamic regret against a moving comparator originates with Zinkevich [ [21], who gave the bound for OGD that we use. Besbes et al. [ [3] established minimax rates for non-stationary stochastic optimization and supply the lower bound in Theorem 2. Subsequent work develops adaptive and parameter-free methods that attain path-length-dependent rates without knowing [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, , 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 ; 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.
| Work | Regret | Constraint | Minimax | Threshold |
| Besbes et al. [ [3] | Dyn. | None | Yes | No |
| Baby and Wang [ [2] | Dyn. | None | Yes | No |
| Zhao et al. [ [20] | Dyn. | None | No | No |
| Zhang et al. [ [18] | Dyn. | Soft | Yes | No |
| Dekel et al. [ [8] | Stat. | Switch cost | Yes | No |
| Chen et al. [ [5] | Stat. | Count | Yes | No |
| Sherman and Koren [ [14] | Stat. | Count | Yes | No |
| Wang et al. [ [15] | Stat. | Dist. | Partial | No |
| Chen et al. [ [6] | Dyn. | Soft | No | No |
| This work | Dyn. | Dist. | Open1 | Yes |
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 exceeds the feasibility threshold. Resolving it appears to require understanding whether the 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 , so it certifies nothing above the threshold. A drifting comparator can be followed with additional movement once the observed losses reveal its position, so for increasing 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 .
The result should therefore be read as identifying the asymptotic movement scale , 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 for a universal constant , uniformly over , and Figure 2(B) provides the corresponding empirical demonstration at . The random-walk and real-data experiments show that the transition sits near and that regret decays as ; because they run at fixed finite horizons they cannot distinguish from , 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 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 for a universal constant and every ; projected OGD with a budget-aware step size achieves once ; together these identify as the critical movement scale, with the constant-factor band left open. Above the threshold, budget-controlled OGD gives a concrete upper bound, but its minimax tightness remains open. Experiments support the transition picture, locate it near , and exhibit empirical 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 , take and the losses
which are convex, -Lipschitz, and satisfy . Since these are a special case of the convex -Lipschitz class, a lower bound against them applies to the whole class.
The comparator. Let and . For the first rounds set
and hold the final value for any leftover rounds. Thus the comparator alternates between the endpoints of for blocks. There are exactly switches, each of length , so the realized path length is and the instance is admissible.
Per-block-pair error. Group the first blocks into disjoint consecutive pairs , with on odd-indexed and on even-indexed blocks. Let be the number of complete pairs. For the -th pair put and . The range of a trajectory is at most its total variation, so every in the pair lies in . Hence
and adding gives
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 : at and it gives 0.364 versus 0.375 at , and 0.242 versus 0.250 at , in units of . Crucially it vanishes only at , not at . Sharpening this step would recover the constant without changing the structure of the argument.
Summing. The pairs occupy disjoint sets of rounds, so . Summing (11) over the pairs,
Since and , while whenever , we have . Also, because , we have . Substituting these two estimates,
which is (3) with universal constants. In particular whenever for a sufficiently small universal constant .
Achievability
Run projected OGD with the fixed step size . Each step moves at most , so and the constraint holds by construction. By Lemma 6, $R_d\le D(D+2P_T)/(2\eta)+ , which on substituting gives (4). If the first term is , and if the second is . Hence .
Combining, regret is linear whenever for a universal constant and sublinear whenever with . Because , both sides identify as the asymptotic movement scale, while the exact constant-factor band remains unresolved. □
Remark 5 (Why a deterministic adversary). A random-walk comparator with Rademacher of scale has path length but spatial range only , so a learner that never moves and sits at the centre of the range incurs per round rather than . The resulting bound is , linear only when , 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 have diameter and let each be convex and -Lipschitz. Projected OGD with fixed step size satisfies, for any comparator sequence with path length ,
Upper bound. Run projected OGD with the fixed, time-independent step size . Per-round movement is at most , so .
Case 1 (budget-rich). When we have , and Lemma 6 gives . The dependence on the diameter here is rather than : minimizing yields when . We keep the exact form throughout.
Case 2 (budget-constrained). When we have , and substituting,
so . Taking the minimum with the trivial bound gives (6). □
For comparison: unconstrained lower bound. 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 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 , 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 evolve as for a possibly unknown transition operator and exogenous noise , with losses where is convex and -Lipschitz, and let . If the induced path length satisfies , then any algorithm with has , while 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 .
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 with .
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 with Rademacher is used for the transition-location and 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 against for drift magnitudes at , with the red dashed line at and shading showing standard deviation over 20 seeds. The drop near 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 . The location is flat in because and are measured in the same norm; how the constants and scale with dimension is not resolved here.
Figure 8. Budget–regret trade-off on the five real series. The curves follow 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 the learner barely moves and incurs ; at tracking improves substantially; at the learner tracks near-perfectly with .
References
- [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]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]Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 63(5):1227–1244, 2015.
- [4]Marko Budišić, Ryan Mohr, and Igor Mezić. Applied koopmanism. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(4), 2012.DOI
- [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]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]Daryl J Daley and David Vere-Jones. An introduction to the theory of point processes: volume II: general theory and structure. Springer, 2008.
- [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]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]Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2 (3-4):157–325, 2016.
- [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]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]Igor Mezić. Spectral properties of dynamical systems, model reduction and decompositions. Nonlinear Dynamics, 41(1):309–325, 2005.DOI
- [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]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]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]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]Lijun Zhang, Wei Jiang, Shiyin Lu, and Tianbao Yang. Revisiting smoothed online learning. Advances in Neural Information Processing Systems, 34:13599–13612, 2021.
- [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]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]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.







