Dynamic Regret Against Moving Comparators

Why Compare Against a Moving Decision?

External regret compares a learner’s cumulative loss with the loss of one fixed decision. That comparison can be uninformative when the best decision changes over time: a fixed decision may be a poor benchmark even if the learner tracks the changing conditions well. Dynamic regret instead compares the learner’s decision on each round with a comparator that may change from round to round. The price of allowing the comparator to move will appear explicitly in the guarantee.

Consider a decision set $K$, a nonempty closed convex subset of $\mathbb{R}^d$. On round $t$, the learner selects $x_t\in K$, then incurs a convex loss $\ell_t(x_t)$. Assume each $\ell_t$ is differentiable on a neighborhood of $K$. The projected gradient update, with fixed step size $\eta>0$, is

x_{t+1}=\Pi_K\!\left(x_t-\eta\nabla\ell_t(x_t)\right),

where $\Pi_K(z)$ is the Euclidean projection of $z$ onto $K$, that is, the point in $K$ minimizing $\|z-y\|_2$ over $y\in K$. Write $g_t=\nabla\ell_t(x_t)$. The result below also holds with $g_t$ replaced by any subgradient of $\ell_t$ at $x_t$.

Definition: For a comparator sequence $u_1,\ldots,u_T\in K$, the dynamic regret of decisions $x_1,\ldots,x_T$ is $$ R_T^{\mathrm{dyn}}(u_{1:T})=\sum_{t=1}^T\bigl(\ell_t(x_t)-\ell_t(u_t)\bigr). $$ The comparator path length is $$ V_T=\sum_{t=2}^T\|u_t-u_{t-1}\|_2. $$

The path length measures the total movement of the benchmark, not the movement of the learner. It does not include a term from $x_1$ to $u_1$; the initial mismatch will instead be controlled by the diameter of $K$. Dynamic regret can be negative for a particular sequence, so an upper bound on it is a guarantee, not a claim about its absolute value.

Worked Examples

Worked Example: A Comparator Switches Between Two Endpoints

Let $K=[0,1]$, $\eta=1/4$, and $x_1=1/2$. Use the linear losses $\ell_1(x)=x$, $\ell_2(x)=-x$, and $\ell_3(x)=x$. Compare with $u_1=0,u_2=1,u_3=0$.

The gradients are $1,-1,1$. Projecting each gradient step onto $[0,1]$ gives $x_2=1/2-1/4=1/4$, $x_3=1/4+1/4=1/2$, and $x_4=1/2-1/4=1/4$. The learner’s losses are $1/2,-1/4,1/2$, which sum to $3/4$. The comparator’s losses are $0,-1,0$, which sum to $-1$. Thus dynamic regret is $3/4-(-1)=7/4$.

The comparator moves twice by one unit, so $V_3=2$. The diameter of $K$ is $D=1$, and $\sum_t\|g_t\|_2^2=3$. The bound proved below is $(D^2+2DV_T)/(2\eta)+(\eta/2)\sum_t\|g_t\|_2^2 =5/(1/2)+3/8=83/8$. It is conservative here, but it accounts for both comparator movement and the gradients actually encountered.

Worked Example: Computing Regret and the Path-Length Bound

Let $K=[-1,1]$, $x_1=0$, and $\eta=1/2$. Take $\ell_t(x)=g_tx$ with gradient sequence $(g_1,g_2,g_3,g_4)=(1,-2,1,-2)$. Use the comparator sequence $(-1,-1,1,1)$.

The updates are $x_2=-1/2$, $x_3=1/2$, $x_4=0$, and $x_5=1$; each follows from $x_{t+1}=\Pi_{[-1,1]}(x_t-g_t/2)$. The learner’s losses are $0,1,1/2,0$, for a total of $3/2$. The comparator’s losses are $-1,2,1,-2$, for a total of $0$. Dynamic regret is therefore $3/2$.

Here $D=2$, $V_4=|1-(-1)|=2$, and the squared gradient magnitudes sum to $1+4+1+4=10$. The guarantee evaluates to $(4+2\cdot2\cdot2)/(2\cdot(1/2))+(1/2)\cdot10/2=12+5/2=29/2$. The bound holds for this comparator even though the comparator sequence is not required to be generated by an online procedure.

Worked Example: A Quadratic Loss Sequence

Let $K=[0,2]$, $x_1=0$, and $\eta=1/2$. On round $t$, take $\ell_t(x)=(x-y_t)^2/2$, where $(y_1,y_2,y_3)=(0,2,2)$. Compare with $(u_1,u_2,u_3)=(0,2,2)$.

The gradient is $g_t=x_t-y_t$. Thus $g_1=0$ and $x_2=0$. Next $g_2=-2$, so $x_3=\Pi_{[0,2]}(0-(-2)/2)=1$. Then $g_3=-1$, so $x_4=\Pi_{[0,2]}(1-(-1)/2)=3/2$. The learner’s losses are $0$, $(0-2)^2/2=2$, and $(1-2)^2/2=1/2$, totaling $5/2$. Each comparator loss is zero, so dynamic regret is $5/2$.

The comparator path length is $V_3=2$; the set diameter is $D=2$; and the squared gradient magnitudes sum to $0+4+1=5$. With $\eta=1/2$, the bound is $4/(1)+8+5/4=53/4$. In particular, the gradients in this calculation are evaluated at the learner’s decisions, not at the comparator’s decisions.

The One-Step Inequality

The key fact is that projection cannot increase the distance to any point in $K$ relative to the unprojected point. Here is the precise inequality needed for the regret proof.

Lemma: For any $x_t,u\in K$, the projected gradient update satisfies $$ g_t^\top(x_t-u)\leq \frac{\|x_t-u\|_2^2-\|x_{t+1}-u\|_2^2}{2\eta} +\frac{\eta}{2}\|g_t\|_2^2. $$

Proof. The Euclidean projection $p=\Pi_K(z)$ onto a closed convex set satisfies $(z-p)^\top(u-p)\leq0$ for every $u\in K$. To see this, the segment $p+s(u-p)$, $0\leq s\leq1$, lies in $K$; since $p$ minimizes squared distance to $z$, the right derivative at $s=0$ of $\|z-p-s(u-p)\|_2^2$ is nonnegative. That derivative is $-2(z-p)^\top(u-p)$, giving the stated inequality. Apply it with $z=x_t-\eta g_t$ and $p=x_{t+1}$. Expanding the resulting squared-distance comparison, or using $\|x_{t+1}-u\|_2^2\leq\|x_t-\eta g_t-u\|_2^2$, gives

\begin{aligned} \|x_{t+1}-u\|_2^2 &\leq \|x_t-u\|_2^2 -2\eta g_t^\top(x_t-u)+\eta^2\|g_t\|_2^2. \end{aligned}

Rearranging and dividing by $2\eta>0$ proves the lemma. $\square$

By convexity, $\ell_t(x_t)-\ell_t(u_t)\leq g_t^\top(x_t-u_t)$. Substituting $u=u_t$ into the lemma therefore bounds the round-$t$ loss difference by a difference of squared distances plus a gradient term. The moving comparator requires care when those distance differences are summed.

Dynamic-Regret Bound for Projected Gradient Updates

Theorem: Suppose $K\subset\mathbb{R}^d$ is nonempty, closed, convex, and has finite diameter $D=\sup_{x,y\in K}\|x-y\|_2$. Suppose $\ell_1,\ldots,\ell_T$ are convex and differentiable on a neighborhood of $K$. For projected gradient updates with any fixed $\eta>0$, and any comparator sequence $u_1,\ldots,u_T\in K$, $$ R_T^{\mathrm{dyn}}(u_{1:T}) \leq \frac{D^2+2D V_T}{2\eta} +\frac{\eta}{2}\sum_{t=1}^T\|g_t\|_2^2. $$

Proof. Apply the one-step inequality with $u=u_t$, then sum over $t$. The squared-distance terms sum to

\|x_1-u_1\|_2^2 +\sum_{t=2}^T\left(\|x_t-u_t\|_2^2-\|x_t-u_{t-1}\|_2^2\right) -\|x_{T+1}-u_T\|_2^2.

For each $t\geq2$, the reverse triangle inequality gives $\big|\|x_t-u_t\|_2-\|x_t-u_{t-1}\|_2\big|\leq\|u_t-u_{t-1}\|_2$. Both distances are at most $D$, since $x_t,u_t,u_{t-1}\in K$. Factoring a difference of squares therefore yields

\begin{aligned} \|x_t-u_t\|_2^2-\|x_t-u_{t-1}\|_2^2 &\leq \left|\|x_t-u_t\|_2-\|x_t-u_{t-1}\|_2\right|\\ &\quad{}\times\left(\|x_t-u_t\|_2+\|x_t-u_{t-1}\|_2\right)\\ &\leq 2D\|u_t-u_{t-1}\|_2. \end{aligned}

Also $\|x_1-u_1\|_2^2\leq D^2$, and the final term $-\|x_{T+1}-u_T\|_2^2$ is nonpositive, so it can be discarded in an upper bound. The total squared-distance contribution is at most $D^2+2DV_T$. The remaining terms from the one-step inequalities sum to $(\eta/2)\sum_{t=1}^T\|g_t\|_2^2$. Combining these facts with convexity’s loss inequality proves the theorem. $\square$

Interpreting and Tuning the Bound

The bound separates two sources of difficulty. The term involving $V_T$ grows when the comparator moves substantially; the gradient term grows when the learner encounters large gradients. If the comparator is fixed, $V_T=0$, and the result reduces to the usual projected-gradient guarantee against one decision. If $K$ has large diameter, both the initial-distance allowance and the cost assigned to comparator movement can be large.

For a fixed comparator sequence and realized gradients, set $A=D^2+2DV_T$ and $S=\sum_{t=1}^T\|g_t\|_2^2$. When $A>0$ and $S>0$, the right side is minimized over $\eta>0$ at $\eta=\sqrt{A/S}$: differentiating $A/(2\eta)+\eta S/2$ gives $-A/(2\eta^2)+S/2=0$. Substitution gives the value $\sqrt{AS}$. This is an algebraic tuning calculation, not by itself an online step-size strategy: the comparator path length and total gradient magnitude may not be known in advance. The theorem remains valid for every fixed positive $\eta$, whether or not it is chosen this way.

Common Pitfall

A common mistake is to telescope as if the comparator were fixed and simply cancel every intermediate squared-distance term. That cancellation is invalid: the distance at round $t$ to $u_t$ is not generally the distance at that same iterate to $u_{t-1}$. The missing terms are precisely $\|x_t-u_t\|_2^2-\|x_t-u_{t-1}\|_2^2$. The reverse triangle inequality bounds each one by $2D\|u_t-u_{t-1}\|_2$, producing the path-length contribution. Ignoring these terms incorrectly gives a static-comparator guarantee for a moving comparator.

A second interpretive error is to use gradient magnitudes evaluated at the comparator. The projected-gradient proof uses $g_t=\nabla\ell_t(x_t)$, because the update is made from the gradient at the learner’s current decision. The theorem’s gradient term must therefore be computed along the learner’s trajectory.

Check Your Understanding

Use the definitions and bound above to answer the following questions.

For a comparator sequence that never changes, what is $V_T$, and which part of the bound disappears?
Why does the proof need a finite diameter for $K$ in its stated form?
In the telescoping argument, what quantity is controlled by the movement from $u_{t-1}$ to $u_t$?
For $D=1$, $V_T=3$, $\eta=1/2$, and $\sum_t\|g_t\|_2^2=8$, evaluate the theorem’s upper bound.
Why does the theorem not justify replacing gradients at the learner’s decisions by gradients at the comparator decisions?