Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory

AI summary

Overview

• Research area: Online convex optimization (OCO) — specifically dynamic regret with movement (switching) costs, delayed feedback, and memory in unconstrained domains.
• Technical level: Advanced. The paper is a theoretical machine-learning paper built on regret analysis, mirror descent, Bregman divergences, and comparator-adaptive ("parameter-free") bounds; it is written for readers comfortable with online learning notation and proof techniques.
• Scope in one sentence: The paper designs parameter-free algorithms for unconstrained OCO whose regret adapts simultaneously to realized gradients, time-varying movement-cost coefficients, and the path length and norm of the comparator sequence, and then reduces delayed feedback and time-varying memory to this setting.

What This Paper Is About

Online learners usually pay a price for changing their decisions (transaction fees, switching overhead, reconfiguration costs). Existing theory either handles unconstrained decision spaces, or dynamic comparisons against a moving benchmark, or movement costs — but not all three, and prior movement-cost work assumes the penalty coefficient is fixed. This paper asks whether one can achieve near-optimal dynamic regret in unconstrained domains when the movement-cost coefficient λ_t itself changes arbitrarily over time, and answers yes with algorithms that need no prior knowledge of comparator norms, path length, gradient norms, or the coefficients.

Key Contributions

1. First parameter-free dynamic-regret algorithm for unconstrained OCO with time-varying movement costs. The paper introduces a Composite Mirror Descent algorithm (Algorithm 1) using a log-linear regularizer ψ(w) = (2/η) ∫₀^{‖w‖} log(x/α + 1) dx plus a corrective penalty φ_t(w) = (ηβ_t² + γ)‖w‖ with β_t = ‖g_t‖ + λ_{t+1}, where γ = 1/(ηT) and α = ε₀/T. A parallel meta-algorithm over a grid of learning rates 𝒮 = {η_i = 2^i/(L√T) ∧ 1/L} (Algorithm 2) removes the need to tune η.
2. A refined batching algorithm with first-order dependence on movement costs. Algorithm 3 keeps a fixed action within an epoch, buffers gradients into H_τ, and updates only when ‖H_τ‖ > λ_{t+1}, replacing the λ²_{t+1} dependence with a λ_t‖g_t‖ interaction term while retaining granular adaptation to each individual λ_t rather than λ_max.
3. A new reduction from delayed feedback to time-varying movement costs. Lemma 5.1 shows the delayed-feedback dynamic regret is bounded by a linearized term plus a movement penalty weighted by the number of missing gradients, motivating the assignment λ_t = G|m_t|. This reduction is presented as novel and is stated to be of independent interest.
4. A reduction for OCO with time-varying memory. Under coordinate-wise Lipschitz continuity, time-varying memory is translated into the movement-cost framework, delivering a bound that applies to unconstrained domains and improves dependence on the memory length relative to prior fixed-length results.

Main Findings

• Core bound (abstract/main result): The main algorithm guarantees Õ(√((M² + MP_T)(T + ∑_t λ_t))) regret, where P_T is the comparator path length over T rounds and M is the maximal comparator norm. This is described as the first comparator-adaptive dynamic regret bound for this setting, recovering optimal adaptive rates for static and dynamic regret when λ_t = 0 for all rounds.
• Gradient- and comparator-adaptive form: The contribution summary states a bound of Õ(√((M + P_T) ∑_{t=1}^T (‖g_t‖² + λ_t‖g_t‖)‖u_t‖)), where g_t is the realized gradient at round t and u_t is the comparator at round t — adaptivity to comparator complexity, to favorable geometry via realized first-order feedback, and to arbitrary fluctuations in movement penalties.
• Theorem 3.1 (Algorithm 2): For G-Lipschitz convex losses and any L ≥ G + λ_max, the bound is 𝒪((ε log T + M̃_T(ε) + P̃_T(ε))L + √((M̃_T(ε) + P̃_T(ε)) ∑{t=1}^T (‖g_t‖² + λ²{t+1})‖u_t‖)), where M̃_T(ε) = M(1 + log(MT/ε + 1)) and P̃_T(ε) = P_T(1 + log(4MT²/ε + 1)).
• Theorem 4.1 (Algorithm 3): For G-Lipschitz convex losses and any L ≥ G + 2λ_max, the analogous bound holds with the leading term √((M̃_T(ε) + P̃_T(ε)) ∑_{t=1}^T (‖g_t‖² + λ_t‖g_t‖)‖u_t‖), using the same M̃_T(ε) and P̃_T(ε) definitions.
• Why first-order matters: The paper argues full second-order adaptivity is incompatible with movement costs (citing Gofer, 2014; Zhang et al., 2022b), and that the Theorem 4.1 bound vanishes as gradients approach zero even if movement costs stay positive. By AM-GM, the first-order form is never worse than the second-order form up to constants, but can be much sharper when ‖g_t‖ is small relative to λ_t.
• Static-regret improvement: In the one-dimensional static setting with fixed movement costs, the result improves on Zhang et al. (2022b) by replacing G²T + λGT with the adaptive sum ∑_t‖g_t‖² + λ∑_t‖g_t‖.
• Delayed feedback bound: The reduction yields Õ(√((M² + MP_T)(T + d_tot))), where d_tot is the total delay. Compared with Wan et al. (2024), who establish Õ(√((1 + P_T)(T + d_max T))) for bounded domains (d_max = maximum delay) and only improve this to a d_tot dependence under the restrictive assumption of in-order feedback, this result handles unbounded domains and achieves the tighter d_tot dependence without assuming in-order arrival.
• Time-varying memory bound: The reduction yields Õ(√((M² + MP_T)(H²T + GH ∑_t b_t²))), where G is the coordinate-wise Lipschitz constant, H bounds the gradient norm of the unary losses, and b_t is the time-varying memory length. Zhao et al. (2023), who study dynamic regret with fixed memory length B ≥ 1 over bounded domains, establish Õ(√((1 + P_T)(√G H²B + GHB²)T)); the new result applies to unconstrained domains and improves the dependence on the time-varying memory length.
• No experiments reported: The available content describes only theory and reductions; no empirical evaluation, datasets, or benchmarks are reported.
• λ_max is avoidable in principle: Remark 4.2 notes Algorithm 3 requires L ≥ G + 2λ_max, and since λ_max depends on sequentially observed quantities, a standard doubling trick on ‖g_{t−1}‖ + λ_t with initial guess L = G can sidestep this prior knowledge.

Methodology in Plain English

The authors start from a known recipe for parameter-free online learning: use a mirror-descent update with a log-linear regularizer that grows slowly, so the algorithm can operate in unbounded space and automatically adapt its regret to however large the right comparator turns out to be. That regularizer is not strongly convex, so a correction term pulls each iterate gently back toward the origin to keep learning stable.

The new twist is scaling that correction by (‖g_t‖ + λ_{t+1})² — effectively a dynamic friction coefficient. When the next move is expensive or the gradient is steep, updates shrink; when costs are low, the algorithm is free to move quickly. Because the ideal learning rate depends on unknown quantities (gradient norms, movement coefficients, comparator norm M, and path length P_T), they run many copies of the algorithm at different learning rates in parallel and combine their decisions in a meta-algorithm, picking the best rate implicitly. Since the grid has only 𝒪(log T) entries, the other copies contribute only 𝒪(log T) extra regret.

The second algorithm attacks the remaining weakness: the squared dependence on λ_{t+1}, which lets movement costs inflate regret even when gradients are negligible. The fix is to not update on every round. The algorithm groups rounds into epochs, plays one fixed action per epoch, and accumulates gradients; it only consults the base learner once the accumulated gradient norm exceeds the current movement cost. This way, large movement penalties are only paid when the first-order signal is strong enough to justify moving, turning the λ² dependence into a λ‖g‖ term.

Finally, the authors show that delayed feedback looks like movement costs in disguise: when many gradients are still missing, changing your decision is effectively expensive, because you are moving without information. This yields the rule λ_t = G|m_t|, where |m_t| counts the outstanding gradients. A similar translation handles losses that depend on a window of past decisions whose length varies over time.

Why This Matters

This work unifies three threads that prior literature treated separately — unconstrained decisions, dynamic (moving-target) comparators, and movement penalties — and removes the unrealistic assumption that the penalty coefficient is constant. Because the bounds adapt to realized gradients, individual λ_t values, and comparator complexity, they remain meaningful without knowing problem scale in advance, which matters in unbounded decision spaces such as leveraged portfolios. The delayed-feedback reduction is notable because delay and movement costs are not obviously related, yet treating missing feedback as a time-varying movement penalty gives a d_tot dependence without assuming in-order arrival.

Real-world applications cited or implied by the paper:

• Optimal control: rapidly changing control policies incur switching overhead.
• Video streaming: frequent bitrate changes cost rebuffering and overhead.
• Geographical load balancing: shifting workloads between data centers incurs migration cost.
• Portfolio management with leverage and short-selling: rebalancing across assets incurs transaction fees and market impact that fluctuate with liquidity and volatility, matching the time-varying λ_t model.
• Online learning with memory: temporal dependencies in tasks are handled via reductions to movement costs.

Industry relevance: any system that trades tracking accuracy against reconfiguration cost — cloud resource scheduling, adaptive bitrate streaming, algorithmic trading, energy grid balancing, and networked control — faces exactly the tension this framework formalizes, with penalties that drift over time rather than staying fixed.

Future Directions

• Can the batching step be removed or made more efficient? Algorithm 3 improves the movement-cost dependence, but whether the λ² term can be avoided without buffering gradients (or with less bookkeeping) is left open.
• Lower bounds for the time-varying movement-cost setting. The paper establishes upper bounds and cites Gofer (2014) and Zhang et al. (2022b) on the incompatibility of full second-order adaptivity with movement costs; matching lower bounds for arbitrary λ_t sequences would clarify how tight the new rates are.
• Beyond the stated assumptions. The memory reduction relies on coordinate-wise Lipschitz continuity, and the delayed-feedback analysis assumes t + d_t ≤ T so all feedback arrives by the end. Relaxing these assumptions — for example, non-arriving feedback or weaker smoothness — is a natural extension.
• Full analysis of the memory application and empirical validation. The available content truncates in Section 5.1, so the complete memory algorithm and any experimental comparison against Zhang et al. (2021), Zhao et al. (2023), and Wan et al. (2024) are not reported here; empirical study of these bounds is an obvious next step.

Target Audience

Theoretical machine-learning researchers working on online convex optimization, regret analysis, and parameter-free/comparator-adaptive methods; researchers in online learning with delayed feedback, bandits under delay, and online learning with memory; and mathematically trained practitioners in control, streaming, load balancing, or finance who want regret guarantees that hold in unbounded decision spaces with changing switching costs. The paper assumes familiarity with Bregman divergences, mirror descent, and standard dynamic-regret notation.

Authors’ abstract

In this paper, we study dynamic regret in unconstrained online convex optimization (OCO) with movement costs. Specifically, we generalize the standard setting by allowing the movement cost coefficients $λ_t$ to vary arbitrarily over time. Our main contribution is a novel algorithm that establishes the first comparator-adaptive dynamic regret bound for this setting, guaranteeing $\widetilde{\mathcal{O}}(\sqrt{(M^2+MP_T)(T+\sum_t λ_t)})$ regret, where $P_T$ is the path length of the comparator sequence over $T$ rounds and $M$ is the maximal comparator norm. Our result recovers the optimal adaptive rates for both static and dynamic regret in OCO as the special case where $λ_t=0$ for all rounds. To demonstrate the versatility of our results, we consider two applications: OCO with delayed feedback and OCO with time-varying memory. We show that both problems can be translated into time-varying movement costs, establishing a novel reduction specifically for the delayed feedback setting that is of independent interest. A crucial observation is that the first-order dependence on movement costs in our regret bound plays a key role in enabling optimal comparator-adaptive dynamic regret guarantees in both settings.