Strongly Convex Losses and Logarithmic Regret

Why Curvature Changes the Regret Rate

In online convex optimization, a learner chooses $x_t$ before seeing the loss $f_t$, then incurs $f_t(x_t)$. Comparator regret measures the learner’s cumulative loss against one fixed decision chosen with hindsight. For general convex losses, projected online gradient descent balances accumulated gradient error against movement in the decision space. When every loss is strongly convex, each round also penalizes distance from the comparator. A decreasing step size can use that penalty to cancel the movement terms, leaving a harmonic sum and therefore logarithmic regret.

The guarantee is deterministic: it holds for every sequence of losses satisfying the assumptions, including sequences chosen adversarially. It does not require an independent and identically distributed data-generating process.

Setup and Definitions

Work in a finite-dimensional Euclidean space with inner product $\langle\cdot,\cdot\rangle$ and norm $\|\cdot\|$. Let $D$ be a nonempty closed convex set. At round $t$, the learner chooses $x_t\in D$, observes a differentiable loss $f_t:D\to\mathbb R$, and updates using its gradient at $x_t$. The projection $\Pi_D(z)$ is the point of $D$ closest to $z$.

Definition: A differentiable function $f:D\to\mathbb R$ is $\mu$-strongly convex, for $\mu>0$, if for every $x,y\in D$, $$ f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle+\frac{\mu}{2}\|y-x\|^2. $$ The quantity $\mu$ is the strong-convexity parameter, relative to the specified norm.

Assume that each $f_t$ is $\mu$-strongly convex with the same $\mu>0$, and that the gradients used by the algorithm satisfy $\|\nabla f_t(x_t)\|\le G$ for a finite constant $G$. A stronger, convenient sufficient condition is that this bound holds for every $x\in D$ and every round. Fix any comparator $u\in D$. The comparator regret through round $T$ is

R_T(u)=\sum_{t=1}^T\bigl(f_t(x_t)-f_t(u)\bigr).

The projected online gradient update with step size $\eta_t>0$ is

x_{t+1}=\Pi_D\bigl(x_t-\eta_t\nabla f_t(x_t)\bigr).

Because $D$ is nonempty, closed, and convex in finite dimensions, this projection exists and is unique. The update is feasible even when the unconstrained gradient step leaves $D$.

Worked Example: A Strongly Convex Quadratic With a Fixed Target

Take $D=[0,1]$, $f_t(x)=\tfrac12(x-1)^2$ for every $t$, and $x_1=0$. This loss has derivative $f_t'(x)=x-1$, and its second derivative is $1$, so it is $1$-strongly convex. On $D$, $|f_t'(x)|\le1$, hence $G=1$ is valid.

With $\eta_t=1/t$, at round 1 the gradient is $-1$, so $x_2=\Pi_D(0-1\cdot(-1))=1$. At every later round the gradient at $1$ is zero, so $x_t=1$ for all $t\ge2$. The comparator $u=1$ has loss zero at every round, while the learner incurs $f_1(0)=1/2$ and then zero. Thus $R_T(1)=1/2$ for every $T\ge1$. The bound proved below is $\tfrac12 H_T$, where $H_T=\sum_{t=1}^T1/t$; for example, at $T=4$ it is $\tfrac12(1+\tfrac12+\tfrac13+\tfrac14)=25/24$, which indeed exceeds $1/2$.

The One-Step Inequality

Two inequalities drive the regret proof: strong convexity turns loss difference into a gradient term minus a squared distance, and projection controls that gradient term by a change in squared distance.

Lemma: For $x_t,u\in D$, let $g_t=\nabla f_t(x_t)$ and use the projected update with step size $\eta_t>0$. Then $$ \langle g_t,x_t-u\rangle \le \frac{\|x_t-u\|^2-\|x_{t+1}-u\|^2}{2\eta_t} +\frac{\eta_t}{2}\|g_t\|^2. $$

Proof. Set $z=x_t-\eta_tg_t$. The projection characterization gives $\langle z-x_{t+1},u-x_{t+1}\rangle\le0$ for every $u\in D$. Equivalently, $\langle z-x_{t+1},x_{t+1}-u\rangle\ge0$. Expand $\|z-u\|^2$ around $x_{t+1}$:

\|z-u\|^2 =\|z-x_{t+1}\|^2+\|x_{t+1}-u\|^2 +2\langle z-x_{t+1},x_{t+1}-u\rangle \ge \|x_{t+1}-u\|^2.

Also, expanding $z=x_t-\eta_tg_t$ gives

\|z-u\|^2 =\|x_t-u\|^2-2\eta_t\langle g_t,x_t-u\rangle+\eta_t^2\|g_t\|^2.

Combining the last two displays and rearranging proves the inequality. $\square$

Logarithmic Regret for Strongly Convex Losses

Theorem: Suppose $D$ is nonempty, closed, and convex; every $f_t:D\to\mathbb R$ is differentiable and $\mu$-strongly convex for the same $\mu>0$; and $\|\nabla f_t(x_t)\|\le G$ at every round. For projected online gradient descent with $\eta_t=1/(\mu t)$, every $u\in D$ and every integer $T\ge1$ satisfy $$ R_T(u)\le \frac{G^2}{2\mu}H_T \le \frac{G^2}{2\mu}(1+\log T). $$

Proof. Apply strong convexity with $x=x_t$, $y=u$, then apply the lemma:

\begin{aligned} f_t(x_t)-f_t(u) &\le \langle g_t,x_t-u\rangle-\frac{\mu}{2}\|x_t-u\|^2\\ &\le \left(\frac{1}{2\eta_t}-\frac{\mu}{2}\right)\|x_t-u\|^2 -\frac{1}{2\eta_t}\|x_{t+1}-u\|^2 +\frac{\eta_t}{2}\|g_t\|^2. \end{aligned}

For $\eta_t=1/(\mu t)$, the coefficient of $\|x_t-u\|^2$ is $\mu(t-1)/2$, while the coefficient of $-\|x_{t+1}-u\|^2$ is $-\mu t/2$. Sum from $t=1$ to $T$. The positive distance term at round $t$ cancels the negative distance term from round $t-1$, and the first positive distance coefficient is zero. The only remaining distance term is nonpositive:

R_T(u) \le -\frac{\mu T}{2}\|x_{T+1}-u\|^2 +\frac{G^2}{2\mu}\sum_{t=1}^T\frac1t \le \frac{G^2}{2\mu}H_T.

Finally, for $t\ge2$, $1/t\le\int_{t-1}^t dx/x$. Therefore $H_T\le1+\int_1^T dx/x=1+\log T$, including $T=1$. This establishes both inequalities. $\square$

The key mechanism is the exact match between the curvature penalty $\mu\|x_t-u\|^2/2$ and the chosen step size. Strong convexity is not merely an assumption that improves constants: it removes the need to pay a persistent distance term. The remaining contribution at round $t$ is at most $G^2/(2\mu t)$, and adding those contributions produces a logarithm.

Worked Example: A Changing Sequence of Quadratic Losses

Let $D=[0,1]$, $x_1=0$, and consider three losses $f_t(x)=\tfrac12(x-a_t)^2$, with targets $a_1=0$, $a_2=1$, and $a_3=0$. Each loss is $1$-strongly convex, and $|f_t'(x)|=|x-a_t|\le1$ on the domain, so $\mu=G=1$.

At $t=1$, $f_1'(0)=0$, giving $x_2=0$. At $t=2$, $f_2'(0)=-1$ and $\eta_2=1/2$, giving $x_3=\Pi_D(0+1/2)=1/2$. At $t=3$, $f_3'(1/2)=1/2$ and $\eta_3=1/3$, giving $x_4=\Pi_D(1/2-1/6)=1/3$.

The learner’s losses are $f_1(0)=0$, $f_2(0)=1/2$, and $f_3(1/2)=1/8$, totaling $5/8$. The best fixed comparator minimizes $$ \sum_{t=1}^3 f_t(u)=\frac12\bigl(u^2+(u-1)^2+u^2\bigr) =\frac12(3u^2-2u+1). $$

Differentiating this quadratic gives $3u-1=0$, so the minimizer is $u=1/3$, which belongs to $D$. Substitution gives comparator loss $\tfrac12(1/3-2/3+1)=1/3$. Thus the regret against the best fixed comparator is $5/8-1/3=7/24$. The theorem gives $R_3(u)\le H_3/2=11/12$, a valid though not necessarily tight upper bound.

Worked Example: Quadratic Regularization of Linear Terms

Consider $D=[-1,1]$, $x_1=0$, and two losses $f_1(x)=\tfrac12x^2+x$ and $f_2(x)=\tfrac12x^2-x$. Their second derivatives equal $1$, so both are $1$-strongly convex. Their gradients are $x+1$ and $x-1$, respectively, with absolute value at most $2$ on $D$; hence $G=2$.

At the first round $f_1'(0)=1$ and $\eta_1=1$, so $x_2=\Pi_D(-1)=-1$. At the second round $f_2'(-1)=-2$ and $\eta_2=1/2$, so $x_3=\Pi_D(-1+1)=0$. The incurred loss is $f_1(0)+f_2(-1)=0+(1/2+1)=3/2$.

For any fixed $u\in[-1,1]$, the comparator’s total loss is $f_1(u)+f_2(u)=u^2$, minimized at $u=0$ with value zero. The regret is therefore $3/2$. The theorem’s bound is $(4/2)H_2=3$, confirming the guarantee for losses that combine a quadratic curvature term with changing linear terms.

Scope, Interpretation, and a Common Pitfall

The theorem controls regret against every fixed comparator in $D$, and so also against a best fixed comparator if that minimizer exists. Its logarithmic dependence is on $T$; the prefactor depends on the squared gradient bound and inversely on curvature. A larger $\mu$ strengthens the distance penalty, while a larger $G$ allows more variation in the loss across the domain. The guarantee is in terms of these assumptions and the specified norm, so changing the norm or rescaling the losses also changes the constants.

Common mistake: using a constant step size and claiming the same cancellation. With a fixed $\eta$, the coefficient $1/(2\eta)-\mu/2$ does not vary with $t$. The positive and negative squared-distance terms then do not telescope with matching coefficients in the way shown in the proof. A constant step may be useful for other objectives, but this logarithmic-regret derivation specifically relies on $\eta_t=1/(\mu t)$. Another error is to state a finite gradient bound without checking it: if gradients can grow without bound over the played points, the term $\eta_t\|g_t\|^2/2$ cannot be replaced by $\eta_tG^2/2$.

Key takeaway: Uniform strong convexity and a bounded gradient make the decreasing-step projected update satisfy $R_T(u)\le \frac{G^2}{2\mu}H_T$. The logarithm follows from summing $1/t$, after curvature cancels the accumulated squared-distance terms.

Check Your Understanding

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

Which part of the one-step regret inequality comes from strong convexity, and which part comes from projection?
For $\mu=2$ and $G=3$, what bound does the theorem give at horizon $T$, expressed using $H_T$?
Why does the choice $\eta_t=1/(\mu t)$ make the squared-distance terms telescope?
In the changing-target example, calculate the learner’s loss on round 3 and explain why the comparator minimizes a sum of losses rather than each loss separately.
What assumption is missing if the gradients encountered by the algorithm are not uniformly bounded?