Convex Online Optimization and Comparator Regret

Online Decisions With Convex Losses

In online prediction and optimization, a learner makes a decision, incurs a loss, and then proceeds to the next round. The available decisions may be vectors rather than a finite list of experts. Convexity makes this setting especially useful: it lets us compare the loss at the learner’s decision with the loss at any fixed feasible decision using a linear expression involving a gradient or subgradient.

This tutorial establishes that comparison and its regret consequence. It does not specify how a learner should choose its decisions. The resulting inequality is a tool for analyzing many possible strategies, including algorithms introduced later.

Definition: Let $K\subseteq\mathbb{R}^d$ be a nonempty convex decision set and let $T$ be the number of rounds. On round $t$, the learner chooses $x_t\in K$, and incurs loss $\ell_t(x_t)$, where $\ell_t:K\to\mathbb{R}$ is convex. A fixed comparator is any single $u\in K$, used for comparison on every round. The learner’s cumulative regret against $u$ is $$ R_T(u)=\sum_{t=1}^T \bigl(\ell_t(x_t)-\ell_t(u)\bigr). $$

The comparison is fixed across time, but it need not be the same comparator for every analysis: we may study $R_T(u)$ for any chosen $u\in K$. The best fixed comparator in hindsight has cumulative loss $\inf_{u\in K}\sum_{t=1}^T\ell_t(u)$; when the infimum is attained, its regret is the learner’s cumulative loss minus that minimum.

The loss functions may be chosen adversarially or otherwise, provided the stated convexity conditions hold. The basic regret inequality below is deterministic and holds for each realized sequence of decisions and losses. It needs no assumption that the rounds are independent or identically distributed.

Convexity Gives a First-Order Comparison

For a differentiable convex loss, the gradient at the learner’s decision gives a supporting linear approximation: the actual loss at any other feasible point is no smaller than that approximation. More generally, a subgradient can be used even when the loss is not differentiable.

Definition: A vector $g\in\mathbb{R}^d$ is a subgradient of a convex function $\ell$ at $x\in K$, relative to $K$, if $$ \ell(u)\geq \ell(x)+g^\top(u-x)\qquad\text{for every }u\in K. $$ The set of all such vectors is the subdifferential $\partial\ell(x)$. If $\ell$ is differentiable on an open set containing $K$, then $\nabla\ell(x)\in\partial\ell(x)$ for every $x\in K$.

Theorem: If $\ell:K\to\mathbb{R}$ is convex and $g\in\partial\ell(x)$, then, for every $u\in K$, $$ \ell(x)-\ell(u)\leq g^\top(x-u). $$ In particular, if $\ell$ is differentiable on an open set containing $K$, the inequality holds with $g=\nabla\ell(x)$.

Proof. By the definition of subgradient, $\ell(u)\geq\ell(x)+g^\top(u-x)$. Rearranging gives $\ell(x)-\ell(u)\leq g^\top(x-u)$, as claimed.

For completeness, the differentiable case follows directly from convexity. Let $h(s)=\ell(x+s(u-x))$ for $s\in[0,1]$. Convexity of $K$ ensures the segment lies in $K$, and convexity of $\ell$ ensures $h$ is convex. For $0<s\leq1$, convexity gives $h(s)\leq(1-s)h(0)+s h(1)$. Thus $(h(s)-h(0))/s\leq h(1)-h(0)$. Taking $s$ down to zero, differentiability gives $h'(0)=\nabla\ell(x)^\top(u-x)$, so $\nabla\ell(x)^\top(u-x)\leq\ell(u)-\ell(x)$. Rearrangement proves the result. $\square$

The Gradient-Based Regret Bound

Apply the first-order inequality separately to each round’s loss, using a subgradient at the learner’s decision. Adding the inequalities yields an upper bound on cumulative regret against any one fixed comparator.

Theorem: Suppose $K\subseteq\mathbb{R}^d$ is convex, each $\ell_t:K\to\mathbb{R}$ is convex, and $g_t\in\partial\ell_t(x_t)$ for $t=1,\ldots,T$. Then, for every fixed $u\in K$, $$ R_T(u)=\sum_{t=1}^T\bigl(\ell_t(x_t)-\ell_t(u)\bigr) \leq \sum_{t=1}^T g_t^\top(x_t-u). $$

Proof. Fix any $u\in K$. The first-order comparison applied to $\ell_t$, $x_t$, and $g_t$ gives $$ \ell_t(x_t)-\ell_t(u)\leq g_t^\top(x_t-u) $$ for each $t$. Summing these $T$ inequalities preserves their direction and gives $$ \sum_{t=1}^T\bigl(\ell_t(x_t)-\ell_t(u)\bigr) \leq \sum_{t=1}^Tg_t^\top(x_t-u). $$ The left side is $R_T(u)$, which proves the bound. $\square$

The theorem is a pathwise statement: once the decisions, losses, and subgradients are specified, the inequality holds for that sequence. The right side is not automatically small or nonpositive. Its value depends on how the decisions relate to the subgradients and the comparator. Choosing decisions that control this sum is an algorithm-design question.

Worked Example: Squared Loss on the Real Line

Let $K=\mathbb{R}$, and consider $\ell_t(x)=\tfrac12(x-y_t)^2$ with $y_1=2$ and $y_2=0$. Suppose the learner chooses $x_1=0$ and $x_2=1$, and compare with the fixed decision $u=1$.

The learner’s losses are $\ell_1(0)=\tfrac12(0-2)^2=2$ and $\ell_2(1)=\tfrac12(1-0)^2=\tfrac12$, so their total is $2+\tfrac12=\tfrac52$. The comparator’s losses are $\ell_1(1)=\tfrac12(1-2)^2=\tfrac12$ and $\ell_2(1)=\tfrac12$, also totaling $1$. Therefore $R_2(1)=\tfrac52-1=\tfrac32$.

The derivative is $g_t=\ell_t'(x_t)=x_t-y_t$. Hence $g_1=0-2=-2$ and $g_2=1-0=1$. The gradient-based sum is $$ g_1(x_1-u)+g_2(x_2-u)=(-2)(0-1)+(1)(1-1)=2. $$ Thus the theorem gives $\tfrac32\leq2$. Round by round, the loss differences are $2-\tfrac12=\tfrac32\leq2$ and $\tfrac12-\tfrac12=0\leq0$, verifying the bound directly.

Worked Example: Linear Losses on a Simplex

Let $K=\{x\in\mathbb{R}^2:x_1\geq0,\ x_2\geq0,\ x_1+x_2=1\}$. Use linear losses $\ell_t(x)=a_t^\top x$, with $a_1=(1,0)$ and $a_2=(0,2)$. Suppose the learner chooses $x_1=(1,0)$ and $x_2=(0,1)$. Compare with $u=(0,1)$, which is feasible.

On round 1, the learner’s loss is $a_1^\top x_1=1$, while the comparator’s is $a_1^\top u=0$, giving regret $1$. On round 2, the learner and comparator both incur $a_2^\top(0,1)=2$, giving regret $0$. Total regret is $1$.

For a linear function, the constant vector $a_t$ is a subgradient at every point. The bound’s right side is $$ a_1^\top(x_1-u)+a_2^\top(x_2-u) =(1,0)^\top(1,-1)+(0,2)^\top(0,0) =1+0=1. $$ Here the bound holds with equality, because a linear loss has no curvature gap between its value and its first-order approximation.

Worked Example: A Subgradient at a Nondifferentiable Point

Let $K=[-2,2]$ and $\ell(x)=|x-1|$. Take the learner’s decision $x=0$ and comparator $u=1$. The function is not differentiable at $1$, but at $x=0$ it is differentiable with derivative $-1$, so choose $g=-1$.

The learner’s loss is $|0-1|=1$, and the comparator’s loss is $|1-1|=0$. Thus the regret for this one-round comparison is $1$. The linearized upper bound is $g(x-u)=(-1)(0-1)=1$, giving equality.

The subgradient definition also verifies this choice over the whole decision set: for every $v\in[-2,2]$, $|v-1|\geq1-(v-0)$. If $v\leq1$, the left side is $1-v$, equal to the right side. If $v\geq1$, the left side is $v-1$, and $v-1\geq1-v$ because $v\geq1$. So $g=-1$ is indeed a subgradient at $0$.

Interpreting Comparator Regret

A fixed comparator is one feasible decision $u$ evaluated under every round’s loss. It need not be a decision the learner ever played, and the regret can be negative for a particular comparator. If the learner’s cumulative loss is lower than that comparator’s, then $R_T(u)<0$; the definition does not require regret to be nonnegative.

The distinction between a fixed comparator and a changing sequence matters. The theorem above applies to $u$ held constant as the sum runs over rounds. Replacing it by a different $u_t$ each round defines a different comparison and is not the stated fixed-comparator result. Such moving-comparator questions require separate analysis.

Likewise, the gradient sum is an upper bound, not an identity for general convex losses. In the squared-loss example, the regret was $3/2$ while the gradient sum was $2$; for linear losses in the simplex example, they were equal. Convexity guarantees the inequality in the correct direction, but does not force equality.

Key takeaway: For any fixed feasible $u$, convexity gives $\ell_t(x_t)-\ell_t(u)\leq g_t^\top(x_t-u)$ on each round. Summing converts comparator regret into a bound involving the sequence of subgradients and decisions.

Common Pitfall

A tempting but incorrect argument is: “Because each loss is convex, the gradient-based sum must be nonpositive, so regret is always nonpositive.” Convexity does not say that. It only bounds each loss difference by its corresponding inner product; it imposes no general sign on $g_t^\top(x_t-u)$. In the squared-loss example, that sum is $2>0$, and actual regret is $3/2>0$. The correction is to state the inequality as an upper bound and then separately establish whatever controls the gradient sum for the decision rule under study.

Check Your Understanding

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

In the definition of $R_T(u)$, what must remain the same across all rounds: the learner’s decision or the comparator?
For a convex differentiable loss on a convex set, write the first-order inequality comparing $x$ with $u$.
Why does summing the round-by-round first-order inequalities give an upper bound on $R_T(u)$?
Can comparator regret be negative? Explain using its definition.
For the one-round loss $\ell(x)=|x-1|$, $x=0$, and $u=1$, compute the loss difference and the bound using $g=-1$.