PaperlayerView exact revision on arXiv

Source-linked AI summary

Strongly Adaptive Online Learning with Time-Varying Movement Costs

Andrew Jacobsen, Emmanuel Esposito, Hao Qiu, Mengxiao Zhang

arXiv:2610.32740v1cs.LGstat.ML

TL;DR

The paper asks whether OCO with time-varying movement costs can achieve strongly adaptive regret against arbitrary time-varying comparator sequences. It answers affirmatively with a reduction to sleeping experts with movement costs, improving on prior movement-cost guarantees and extending strongly adaptive guarantees to delayed feedback and time-varying memory.

  • Problem

    Can OCO with time-varying movement costs achieve strongly adaptive regret against arbitrary time-varying comparator sequences, when changing decisions can incur costs that vary over time?

    Source: §1 · p. 2

  • Method

    A reduction decomposes mixture-predictor regret into base-expert and sleeping-experts movement-cost regret, combining interval-based specialists with an algorithm for sleeping experts with movement costs.

    Source: §1 · p. 2

  • Results

    The approach improves on prior time-varying movement-cost work that offered only dynamic regret, while providing simultaneous strongly adaptive and dynamic guarantees, including for delayed feedback and time-varying memory.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results establish strongly adaptive guarantees for delayed feedback and time-varying memory, settings where prior studies had mainly focused on dynamic regret.

    Source: §1 · p. 2, §6 · p. 10

    The approach requires prior knowledge of global bounds on movement costs and, for delayed-feedback and memory settings, on delay and memory lengths, rather than interval-local bounds.

    Source: §6 · p. 10

Abstract

from arXiv · show

We study strongly adaptive regret for Online Convex Optimization (OCO) with time-varying movement costs, a setting that evaluates a learner's performance over arbitrary sub-intervals. This framework captures complex sequential decision-making problems where both the environment and the cost of switching decisions fluctuate over time. We propose a novel algorithm which, for any interval $[a,b] \subseteq [T]$, achieves a data-dependent regret bound of $ \widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+\lambda_t\|g_t\|)} \right) $, where $D$ is the diameter of the decision domain, $P_{[a,b]}$ is the path length of the comparator sequence over $[a,b]$, $g_t$ is the gradient of the loss, and $\lambda_t$ is the movement-cost coefficient at round $t$. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of this development, we further establish the first strongly-adaptive guarantees under delayed feedback. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.

1 Introduction

Time-varying movement costs complicate local guarantees in non-stationary online convex optimization, where performance on short intervals can matter alongside full-horizon performance. The paper introduces a sleeping-experts reduction to obtain strongly adaptive guarantees, with extensions to delayed feedback and time-varying memory.

1 Introduction

  • The problem arises because decisions and movement costs can vary over time, while existing movement-cost work rarely provides strongly adaptive guarantees for complex time-varying settings.The introduction asks whether strongly adaptive regret is possible against arbitrary time-varying comparator sequences.Source: §1 · pp. 2–3
  • A reduction decomposes mixture-predictor regret into base-expert and sleeping-experts meta-algorithm movement-cost regret, enabling interval-based specialists.The paper combines these specialists with a new algorithm for sleeping experts with movement costs.Source: §1 · p. 2
  • The work gives strongly adaptive and dynamic regret guarantees for time-varying movement costs, improving on Qiu et al. [2026] and on fixed-cost, fixed-comparator guarantees.The earlier time-varying-cost result provided only dynamic regret guarantees.Source: §1 · p. 2
  • The reduction treats missing gradients as a time-varying movement-cost scale, yielding the first strongly adaptive regret bound for delayed feedback.The resulting guarantees are simultaneously strongly adaptive and dynamic.Source: §1 · p. 2
  • The movement-cost perspective also handles memory-dependent losses with arbitrarily changing memory lengths, giving strongly adaptive and dynamic guarantees.The paper describes these as improvements over the best-known bounds.Source: §1 · p. 2

2 Problem Setting

The problem setting charges the learner for both its loss and movement, and evaluates movement-cost dynamic regret over any interval against a comparator sequence. It assumes bounded domain and losses, and a known global upper bound on movement costs.

2 Problem Setting

  • Each round, the learner chooses a decision, incurs its convex loss plus a movement penalty, then observes a subgradient and the next movement-cost coefficient.The setting uses a bounded, closed, convex decision domain over T rounds.Source: §2 · p. 3
  • Interval regret is measured against an arbitrary comparator sequence, with the learner charged for movement costs rather than charging the comparator.The paper focuses on this stronger one-sided regret because controlling it also guarantees symmetric regret.Source: §2 · p. 3
  • The assumptions bound the domain diameter, movement coefficients, and loss-function Lipschitz constant.The global movement-cost bound is assumed known, though it can be estimated up to a constant factor by doubling.Source: §2 · p. 4

3 Strong Adaptivity with Time-Varying Movement Costs

The section reduces strongly adaptive OCO with time-varying movement costs to a meta-base decomposition, then designs a sleeping-experts algorithm that accounts for movement costs. Interval specialists make the meta-level guarantee apply on each expert’s active interval.

3 Strong Adaptivity with Time-Varying Movement Costs

  • The meta-base decomposition separates a base learner’s movement-cost regret from the meta-algorithm’s regret, including the cost of changing its weights.The decomposition applies to arbitrary base algorithms on constrained convex feasible sets, unlike the iterate-adding approach discussed for Qiu et al. [2026].Source: §3 · p. 4
  • Interval specialists are active only on prescribed intervals, so competing with an expert active on [a, b] yields an interval guarantee for that interval.The decomposition reduces strong adaptivity to designing the sleeping-experts meta-algorithm and robust movement-cost base learners.Source: §3 · pp. 4–5

3.1 Sleeping Experts with Movement Costs

  • The sleeping-experts approach uses a reduction to online linear optimization and FTRL-based arguments rather than the betting arguments used by Jun et al. [2017].The paper identifies this distinction as important for incorporating adaptive movement costs and coordinate-wise Lipschitz hints.Source: §3.1 · p. 5
  • The proposed sleeping-experts guarantee is described as the first second-order regret guarantee for sleeping experts, while adapting to time-varying movement coefficients.The authors relate it to CBCE [Jun et al., 2017], extending the setting to movement costs, Lipschitz-bound hints, and data-adaptive logarithmic penalties.Source: §3.1 · p. 5

4 Main Result

The main result combines interval specialists, a sleeping-experts meta-algorithm, and adaptive blocking to obtain strongly adaptive movement-cost regret guarantees. The bound includes a data-adaptive penalty and supports time-varying movement coefficients on arbitrary intervals.

4 Main Result

  • Adaptive first-order blocking groups consecutive rounds into epochs and passes each completed epoch’s aggregate gradient to the base learner.The blocking condition uses the sum of gradient norms rather than the norm of the summed gradient, helping handle intervals that start or end mid-epoch.Source: §4 · p. 6
  • The algorithm combines geometric-covering interval experts with interval-specific base learners and updates experts only when active and active at the epoch’s start.This avoids contaminating an interval expert’s feedback with information from outside its interval.Source: §4 · pp. 6–7
  • The bound takes the minimum of two similar terms, including a worst-case penalty scaling with interval length and a data-adaptive penalty involving V^λ_[a,b].The data-adaptive quantity includes the interval sum of squared gradient norms and movement coefficients times gradient norms.Source: §4 · p. 7
  • The guarantee is strongly adaptive on every interval and adapts to time-varying movement coefficients, while also providing optimal dynamic regret guarantees on each interval.The paper says the adaptive bound extends Qiu et al. [2026] to every sub-interval, with an additional log(b) penalty over the non-adaptive guarantee.Source: §4 · pp. 6–7

5 Applications

The applications extend the movement-cost reduction to delayed feedback and time-varying memory, yielding strongly adaptive guarantees on arbitrary intervals. The delayed-feedback bound depends on delay within the interval, while the memory results allow memory lengths to vary over time.

5 Applications

  • The applications extend the movement-cost reductions to delayed feedback and time-varying memory, generalizing prior reductions to arbitrary sub-intervals.The paper’s applications are strongly adaptive regret guarantees for both settings.Source: §5 · p. 8

5.1 Strongly Adaptive Regret with Delayed Feedback

  • The delayed-feedback reduction converts outstanding gradients into movement-cost coefficients and batches newly available gradients for the movement-cost problem.The interval guarantee depends only on delay mass relevant to that interval.Source: §5.1 · p. 8
  • The delayed-feedback guarantee provides the first strongly adaptive and dynamic regret guarantees under delayed feedback.Its dominant term depends on interval length and total delay restricted to that interval; without delays, it recovers standard strongly adaptive and dynamic guarantees.Source: §5.1 · p. 8

5.2 Strongly Adaptive Regret with Time-Varying Memory

  • For time-varying memory, the loss depends on the current and preceding decisions, and the memory-length sequence is assumed known to the learner in advance.The reduction maps this setting to OCO with time-varying movement costs plus lower-order terms.Source: §5.2 · p. 9
  • The memory guarantee is strongly adaptive for arbitrary time-varying memory lengths and has refined data-dependent bounds involving unary gradients and interval-clipped memory lengths.The paper also reports recovering optimal memory-length and comparator-path-length dependence up to logarithmic factors and additive lower-order terms.Source: §5.2 · p. 10

6 Discussion

The discussion highlights strongly adaptive guarantees for time-varying movement costs, delayed feedback, and time-varying memory, while identifying bounds and dependencies left for future work. The related-work review traces dynamic and adaptive regret and connects movement costs with memory and delayed-feedback settings.

6 Discussion

  • The approach yields strongly adaptive guarantees for dynamic regret with time-varying movement costs, delayed feedback, and time-varying memory.The authors identify these as the paper's contributions and future-work directions.Source: §6 · p. 10
  • The movement-cost dependency is first-order, but the blocking argument does not straightforwardly extend it to the analogous bound for pure sleeping experts.The stated difficulty is that the reduction does not readily permit separate coordinate-wise movement costs.Source: §6 · p. 10
  • The approach relies on a known global upper bound on movement costs, with corresponding global-parameter requirements in delayed-feedback and memory settings.The discussion identifies interval-local bounds as an open direction.Source: §6 · p. 10

A More Related Works

  • Strongly adaptive regret measures regret as a function of each interval's length, unlike adaptive bounds expressed in terms of the full horizon.The related-work review describes this as addressing the potential uninformative nature of horizon-based bounds on short intervals.Source: A More Related Works · p. 14
  • Movement-cost OCO charges for changing decisions, while work on delayed feedback includes bounds based on total cumulative delay rather than maximum delay.The review also relates memory-dependent losses to movement costs through stability.Source: A More Related Works · p. 14

B.1 Proof of Lemma 3.1

Lemma 3.1 gives a specialists reduction for movement-cost regret over the full horizon. It relates the mixture predictor's regret to a base expert and a meta-algorithm using surrogate losses.

B.1 Proof of Lemma 3.1

  • The reduction applies to a predictor formed by mixing expert decisions with weights output by a meta-algorithm.It compares the mixture against an expert and a comparator sequence.Source: §B.1 · pp. 14–15
  • The meta-algorithm uses a surrogate loss for each expert that incorporates its loss and its movement between consecutive decisions.The displayed prose defines the surrogate loss coordinate-wise and includes the movement-cost coefficient.Source: §B.1 · p. 15
  • The proof uses convexity to compare losses and separately bounds movement costs to obtain the regret decomposition.The section states that these steps bound the movement-cost regret over the horizon.Source: §B.1 · p. 15

B.2 Proof of Lemma 3.2

Lemma 3.2 specializes the specialists reduction to an arbitrary interval by activating an expert only on that interval. The resulting regret comparison is restricted to the interval's comparator sequence and movement costs.

B.2 Proof of Lemma 3.2

  • The proof applies Lemma 3.1 on the expert's active interval to obtain the interval-specific comparison.The section identifies this as a special case of the full-horizon reduction.Source: §B.2 · p. 16
  • Lemma 3.2 considers an expert whose active rounds coincide exactly with an interval [a, b].The comparator sequence is specified over that same interval.Source: §B.2 · p. 16
  • Because the expert is inactive outside [a, b], the meta-regret term reduces to the regret contribution associated with that expert.The proof notes the equivalence for the meta-regret when the expert is active only on the interval.Source: §B.2 · p. 16

C.1 Proof of Theorem 3.3

Theorem 3.3 analyzes the sleeping-experts algorithm under bounded surrogate losses and movement costs. The section relates its guarantee to CBCE in the standard sleeping-experts setting.

C.1 Proof of Theorem 3.3

  • Theorem 3.3 guarantees a result for any u ∈ ∆N−1 when, at every round t, ∥ℓt∥∞ ≤ G∞ and λt ≤ λ, using Algorithm 1 with L = 2G∞ + 5λ.Source: §C.1 · p. 16
  • The proof represents sleeping-expert regret using transformed losses that depend on activity and the meta-algorithm's movement.It then applies a movement-cost result to the transformed losses.Source: §C.1 · pp. 17–18

C.2 Relation to Jun et al. [2017]

  • Theorem 3.3 matches CBCE's regret guarantee up to lower-order terms while incorporating movement costs and Lipschitz adaptivity.The paper states this comparison for the standard sleeping-experts setting.Source: §C.2 · p. 18

D Parameter-free OLO with Movement Costs

This appendix extends parameter-free online linear optimization to movement costs and presents an adaptive-gradient-descent procedure for comparator sequences. The analyses use movement-cost stability and adaptive learning rates.

D Parameter-free OLO with Movement Costs

E Adaptive Gradient Descent with Movement Costs

F Adaptive First-order Reduction

The first-order blocking reduction converts round-level feedback into epoch-level inputs while preserving interval guarantees. Its blocking condition uses cumulative gradient norms, which supports bounds on intervals that need not align with epochs.

F Adaptive First-order Reduction

  • The reduction uses cumulative gradient norms for blocking, rather than the norm of the aggregate gradient, to support bounds on intervals that begin within an epoch.The text identifies partial epochs as a difficulty for strongly adaptive regret and states that the alternative blocking condition preserves the key second-order-to-first-order property.Source: F Adaptive First-order Reduction · pp. 24, 26
  • Lemma 4.1 gives the reduction’s regret guarantee for any interval and comparator sequence, including intervals containing partial epochs.Source: F Adaptive First-order Reduction · pp. 24–25
  • When H_τ exceeds λ_{t+1}, the reduction sends the accumulated gradient and movement coefficient to the base algorithm, then resets the epoch accumulators.Source: F Adaptive First-order Reduction · p. 25

G Proofs for Section 4 (Main Result)

The main-result proof combines the blocking reduction with base and meta algorithms to establish an interval-wise guarantee. It first treats geometric covering intervals, then extends the argument to arbitrary intervals.

G Proofs for Section 4 (Main Result)

  • For geometric covering intervals, Proposition G.1 gives the regret bound with an overhead of Ω_[a,b] = O(log(b + 1)).The proposition states that its bound has the correct general shape for these intervals.Source: G Proofs for Section 4 (Main Result) · p. 28
  • The proof extends the covering-interval result to arbitrary intervals using a partition into O(log(b − a)) intervals.The partition is formed from disjoint intervals with geometrically changing lengths.Source: G Proofs for Section 4 (Main Result) · pp. 30–31

H.1 Details for Delayed Feedback

The delayed-feedback analysis reduces interval regret to a problem with time-varying movement costs. It applies this reduction to obtain strongly adaptive guarantees under a condition on feedback batch sizes.

H.1 Details for Delayed Feedback

  • The protocol distinguishes past rounds whose gradients have arrived from outstanding rounds, and tracks total delay over the horizon.Source: §H.1 · p. 33
  • The delayed-feedback reduction generalizes Qiu et al. [2026] to arbitrary intervals.Source: §H.1 · p. 34
  • Theorem 5.2 feeds batch-aggregated gradients h_t and movement coefficients G|m_t| into Algorithm 2 to guarantee regret on any interval.It requires H ≥ G times the maximum number of gradients arriving in a round.Source: §H.1 · p. 35

H.2 Details for Time-Varying Memory

This appendix section supports the strongly adaptive time-varying-memory guarantee with an interval-local movement-cost reduction and related theoretical materials. It also records the paper’s ethics, safeguards, assets, human-subjects, and core-LLM checklist responses.

H.2 Details for Time-Varying Memory

  • The appendix extends Qiu et al. [2026, Lemma 5.6] to any interval, reducing memory effects to movement costs while bounding contributions from outside the interval.Lemmas H.2 and H.3 control memory dependencies extending beyond the interval.Source: §H.2 · p. 37
  • Theorem 5.7 gives a strongly adaptive regret guarantee for every interval [a,b] by applying Algorithm 2 to memory-derived gradients and movement coefficients.The setup uses Lipschitz constant H, λ ≥ GB^2, gradients h_t = ∇b f_t(w_t), and λ_t = Gξ_t with ξ_t defined by Lemma 5.6.Source: §H.2 · pp. 39, 41

I Supporting Lemmas

  • A greedy partition divides [a,b] into disjoint intervals with path length between D and 2D except possibly the last, with at most 1 + P[a,b]/D intervals.The construction covers the full interval and is adapted from Cutkosky [2020, Theorem 7].Source: I Supporting Lemmas · p. 42
  • Geometric covering intervals yield a partition with a doubling property, and the paper also cites a standard stability-term inequality from Jacobsen and Cutkosky [2022].The geometric-partition lemma is adapted from Daniely et al. [2015, Lemma 1.2].Source: I Supporting Lemmas · p. 42

NeurIPS Paper Checklist

  • The checklist states that theoretical results have explicit assumptions and complete proofs, with specialized assumptions for time-varying memory stated in Section 5.2; the paper includes no experiments.The checklist marks experimental reproducibility as not applicable because the paper has no experiments.Source: NeurIPS Paper Checklist · pp. 43–44
  • The authors report reviewing the NeurIPS Code of Ethics and confirm that the research conforms to it.The checklist answer is Yes.Source: NeurIPS Paper Checklist · p. 46
  • The paper marks societal-impact discussion N/A, describing the work as foundational online optimization theory with no anticipated direct negative societal consequences.The checklist also marks responsible-release safeguards N/A because the paper poses no such risks.Source: NeurIPS Paper Checklist · pp. 46–47
  • The paper marks questions about crediting existing assets and documenting new assets N/A, stating that it uses no existing assets and introduces none.Source: NeurIPS Paper Checklist · pp. 47–48
  • The paper marks questions about crowdsourcing and human-subject research N/A because it involves neither.It also marks LLM-use disclosure N/A, stating that core method development does not use LLMs as important, original, or non-standard components.Source: NeurIPS Paper Checklist · pp. 48–49
Loading 2610.32740v1…