📊 statistics

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

This paper proposes a novel parameter-free algorithm for unconstrained online convex optimization with time-varying movement costs that achieves the first comparator-adaptive dynamic regret bound, which is then applied to establish optimal guarantees for problems involving delayed feedback and time-varying memory.

Original authors: Hao Qiu, Andrew Jacobsen, Emmanuel Esposito, Mengxiao Zhang

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hao Qiu, Andrew Jacobsen, Emmanuel Esposito, Mengxiao Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to navigate a ship through a foggy ocean, trying to reach a destination that keeps moving. This is the essence of Online Convex Optimization (OCO): making a series of decisions one by one, learning from mistakes, and trying to stay as close as possible to the "perfect" path that you could only see in hindsight.

This paper introduces a new, smarter way to steer that ship, specifically dealing with two tricky problems: changing costs and delayed information.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Moving Target" and the "Heavy Backpack"

In standard navigation, you just want to minimize how far off course you are from the best possible route. But in the real world, changing your course isn't free.

Movement Costs: Imagine your ship has a heavy backpack. Every time you turn the wheel to change direction, the backpack gets heavier, burning more fuel. In the past, researchers assumed this "fuel cost" was always the same.
Time-Varying Costs: The authors realized that in real life, the cost of turning changes. Sometimes the water is calm (cheap to turn), and sometimes it's stormy (expensive to turn). They wanted an algorithm that could handle these fluctuating fuel costs without needing to know the weather forecast in advance.
The "Moving Target": They also wanted to track a target that moves around (Dynamic Regret), rather than just aiming for a single fixed point.

2. The Solution: A "Smart, Self-Adjusting Captain"

The authors built a new algorithm (a "Captain") that is parameter-free.

What does that mean? Usually, a captain needs to know exactly how heavy the backpack is or how fast the wind is blowing to set the right speed. This new Captain doesn't need those numbers beforehand. It learns on the fly.
The "Leash" Metaphor: The algorithm uses a special "leash" (a mathematical regularizer). If the cost of turning is high (stormy weather), the leash tightens, telling the ship to be conservative and not turn too wildly. If the cost is low, the leash loosens, allowing the ship to zip around and catch up to the moving target quickly.
The Result: This Captain guarantees that the ship won't drift too far from the perfect path, even if the fuel costs change unpredictably every second.

3. The "Batching" Trick: Waiting for the Signal

The authors noticed something clever: If the cost of turning is very high, it's not worth making a tiny adjustment based on a small piece of new information.

The Analogy: Imagine you are waiting for a bus. If the bus is late, you don't run to the next stop every 10 seconds. You wait until you have enough information to know it's actually time to move.
The Innovation: Their improved algorithm (Algorithm 3) waits and accumulates small pieces of information (gradients) until the total "signal" is strong enough to justify the "cost" of moving. This prevents the ship from wasting fuel on tiny, unnecessary turns. This makes the algorithm much more efficient when movement costs are high.

4. Two Real-World Applications

The authors showed that their "Smart Captain" can solve two other difficult navigation problems by translating them into the "changing fuel cost" problem:

A. The "Late Mail" Problem (Delayed Feedback)

The Scenario: Imagine you make a decision today, but you don't get the result (the feedback) until three days later.
The Translation: The authors realized that waiting for late feedback is mathematically the same as having a high movement cost. Why? Because if you don't know the result of your last move, you should be very careful about making a new one.
The Win: Their algorithm handles this "late mail" perfectly, even if the delays are random and the decision space is huge (unbounded). It beats previous methods that only worked if the delays were predictable or the decision space was small.

B. The "Short-Term Memory" Problem (Time-Varying Memory)

The Scenario: Imagine your decision today depends not just on today, but on the last few days' decisions (like a stock portfolio that depends on recent trends). Sometimes you need to look back 2 days; other times, 10 days.
The Translation: They showed that having a "memory" that changes length is also like having changing movement costs. If your memory is long, changing your mind is "expensive" because it ripples through a long history.
The Win: Their algorithm adapts to these changing memory lengths automatically, providing better performance guarantees than previous methods that assumed the memory length was fixed.

Summary

In short, this paper gives us a universal navigation tool for decision-making.

It works when the cost of changing your mind fluctuates wildly.
It doesn't need you to guess the parameters in advance.
It uses a smart waiting strategy to avoid wasting energy.
It solves delayed feedback and changing memory problems by treating them as "costly movement" problems.

The authors claim this is the first time such a flexible, "parameter-free" solution has been found for these specific, complex scenarios.

Technical Summary: Parameter-free Dynamic Regret with Time-varying Movement Costs

1. Problem Setting

This paper addresses Unconstrained Online Convex Optimization (OCO) in non-stationary environments where the learner incurs time-varying movement costs.

In the standard OCO setting, a learner selects a decision $w_t$ from a convex space $\mathcal{W}$ (specifically $\mathbb{R}^n$ in this work) and suffers a convex loss $f_t(w_t)$ . The goal is to minimize dynamic regret against a sequence of comparators $(u_1, \dots, u_T)$ :
$R_T(u_{1:T}) = \sum_{t=1}^T f_t(w_t) - \sum_{t=1}^T f_t(u_t)$

This work extends the problem by adding a movement cost penalty proportional to the distance between consecutive decisions. Crucially, the coefficient $\lambda_t$ governing this cost is time-varying and arbitrary. The learner's objective is to minimize the asymmetric dynamic regret:
$R_T(u_{1:T}, \lambda_{1:T}) = \sum_{t=1}^T \left( f_t(w_t) - f_t(u_t) + \lambda_t \|w_t - w_{t-1}\| \right)$
Note that the comparator sequence $(u_t)$ does not incur the movement cost penalty in this asymmetric formulation, making the problem harder than the symmetric variant.

The primary challenge is to design parameter-free (comparator-adaptive) algorithms that do not require prior knowledge of:

The comparator norm bound $M = \max_t \|u_t\|$ .
The comparator path length $P_T = \sum_{t=2}^T \|u_t - u_{t-1}\|$ .
The sequence of gradient norms $\|g_t\|$ .
The sequence of movement cost coefficients $\lambda_t$ .

2. Methodology

The authors propose a hierarchical algorithmic framework consisting of three main components:

A. Composite Mirror Descent with Time-Varying Regularization (Algorithm 1)

The base algorithm utilizes a Composite Mirror Descent update. At each round $t$ , after observing the gradient $g_t$ and the next movement cost $\lambda_{t+1}$ , the learner updates $w_{t+1}$ by minimizing:
$w_{t+1} = \arg\min_{w} \left( \langle g_t, w \rangle + D_\psi(w | w_t) + \phi_t(w) \right)$

Regularizer $\psi(w)$ : A log-linear function designed to handle unbounded domains.
Correction Term $\phi_t(w)$ : A time-varying quadratic term scaled by $\beta_t^2 = (\|g_t\| + \lambda_{t+1})^2$ . This term acts as a "dynamic friction," stabilizing the iterates. When movement costs or gradients are high, the penalty increases, restricting updates; when they are low, the penalty relaxes.

B. Parameter-Free Meta-Algorithm (Algorithm 2)

To eliminate the need for prior knowledge of $M$ , $P_T$ , and the gradient/movement scales, the authors employ a meta-algorithm that maintains a grid of parallel instances of Algorithm 1, each with a different learning rate $\eta_i$ .

The learner plays the sum of decisions from all instances.
The total regret is decomposed into the regret of the "best" instance (approximating the optimal $\eta$ ) plus a small additive cost from the other instances.
Result: This yields a regret bound of $\tilde{O}\left( \sqrt{(M + P_T) \sum_{t} (\|g_t\|^2 + \lambda_{t+1}^2) \|u_t\|} \right)$ .
Limitation: This bound depends quadratically on the movement costs ( $\lambda_{t+1}^2$ ), which is suboptimal when gradients are small but movement costs are high.

C. Adaptive First-Order Reduction (Algorithm 3)

To improve the dependence on movement costs from quadratic to linear, the authors introduce an adaptive batching mechanism.

Mechanism: The algorithm accumulates gradients into a buffer $H_\tau$ over an epoch. It only triggers an update to the base learner when the accumulated gradient norm $\|H_\tau\|$ exceeds the current movement cost $\lambda_{t+1}$ .
Logic: If the movement cost is high, the algorithm waits until the "signal" (gradient) is strong enough to justify the "cost" of moving.
Result: This reduces the regret dependence on movement costs from $\lambda^2$ to $\lambda \|g\|$ .

3. Key Contributions

First Parameter-Free Dynamic Regret with Time-Varying Costs: The paper establishes the first comparator-adaptive dynamic regret bounds for unconstrained OCO with arbitrary, time-varying movement costs.
Optimal Adaptivity: The proposed algorithms adapt simultaneously to:
- The comparator complexity ( $M$ and $P_T$ ).
- The realized gradient sequence ( $\|g_t\|$ ).
- The time-varying movement coefficients ( $\lambda_t$ ).
Improved Movement Cost Dependence: By introducing the adaptive batching strategy (Algorithm 3), the authors achieve a regret bound scaling with $\sum (\|g_t\|^2 + \lambda_t \|g_t\|) \|u_t\|$ . This is a significant improvement over previous second-order bounds scaling with $\lambda_t^2$ , particularly in regimes where gradients are small.
Novel Reductions to Other Problems: The framework is shown to be a primitive for solving other online learning problems by translating them into time-varying movement cost settings:
- OCO with Delayed Feedback: The number of missing gradients is treated as the movement cost scale.
- OCO with Time-Varying Memory: The memory length fluctuations are mapped to time-varying movement costs.

4. Main Results

Theoretical Guarantees

For Algorithm 3 (the improved version), the paper guarantees a dynamic regret of:
$\tilde{O}\left( (M + P_T)L + \sqrt{(M + P_T) \sum_{t=1}^T (\|g_t\|^2 + \lambda_t \|g_t\|) \|u_t\|} \right)$
where $L$ is a Lipschitz-like constant related to $G + \lambda_{\max}$ .

Application 1: Delayed Feedback

The authors reduce OCO with delayed feedback to their setting by setting $\lambda_t = G |m_t|$ , where $|m_t|$ is the number of missing gradients at time $t$ .

Result: They achieve a parameter-free dynamic regret of $\tilde{O}\left( (M + P_T)L + G\sqrt{(M^2 + MP_T)(T + d_{\text{tot}})} \right)$ .
Advantage: This improves upon prior work (e.g., Wan et al., 2024) by handling unbounded domains and achieving a tighter dependence on the total delay $d_{\text{tot}}$ rather than the maximum delay $d_{\max}$ , without requiring the restrictive "in-order" feedback assumption.

Application 2: Time-Varying Memory

The authors reduce OCO with time-varying memory (where loss depends on the last $b_t$ decisions) to their setting.

Result: They obtain a regret bound of $\tilde{O}\left( (M + P_T)L + \sqrt{M(M + P_T)(H^2 T + GH \sum b_t^2)} \right)$ .
Advantage: This is the first dynamic regret guarantee for unconstrained OCO with time-varying memory lengths. It improves upon Zhao et al. (2023) by removing the bounded domain assumption and refining the dependence on the memory length sequence.

5. Significance and Claims

The paper claims that its results represent a unification of several challenging directions in online learning:

Unification: It bridges the gap between unconstrained optimization, dynamic regret, and movement costs, a combination previously unexplored.
Versatility: The framework demonstrates that OCO with movement costs is a powerful primitive. By simply interpreting "missing information" (in delayed feedback) or "memory dependencies" as movement penalties, optimal dynamic regret bounds can be derived for these complex settings.
Optimality: The authors assert that their dependence on the path length $P_T$ and comparator norms is minimax optimal (up to logarithmic factors) and that the first-order dependence on movement costs is a necessary refinement to achieve optimality in settings with fluctuating penalties.
Practicality: The algorithms are efficient, requiring $O(d \log T)$ computation per round, matching the complexity of standard parameter-free OCO algorithms.

The work does not claim to solve problems outside the scope of convex optimization or to provide experimental validation on real-world datasets, focusing instead on theoretical guarantees and reductions.