Projected Online Gradient Descent

Why Projection Enters Online Gradient Descent

In convex online optimization, the learner chooses a feasible point, observes the round’s loss, and then uses information about that loss to choose the next point. A gradient step is a natural way to respond: move against the gradient of the loss just incurred. But an unconstrained step can leave the allowed decision set. Projected online gradient descent makes the step and then projects back to the feasible set.

The key to its regret guarantee is not that projection makes each round’s loss smaller. It need not. Rather, projection controls the squared distance from the next decision to any fixed feasible comparator. Convexity turns the gradient information into a loss comparison, and the distance terms then telescope across rounds.

Definition and Setup

Definition: Let $K$ be a nonempty, closed, bounded, convex subset of $\mathbb{R}^d$. Its Euclidean diameter is $$ D = \sup_{x,u\in K}\|x-u\|_2. $$ For $y\in\mathbb{R}^d$, the Euclidean projection onto $K$ is $$ \Pi_K(y)=\operatorname*{arg\,min}_{z\in K}\|y-z\|_2. $$ Given an initial point $x_1\in K$, a learning rate $\eta>0$, and a convex loss $f_t$ on round $t$, projected online gradient descent chooses $x_t$, observes the loss, selects a subgradient $g_t$ at $x_t$, and updates $$ x_{t+1}=\Pi_K(x_t-\eta g_t). $$

The assumptions on $K$ ensure that the projection exists and is unique: closedness and boundedness give existence in finite dimensions, and convexity gives uniqueness. For a possibly nondifferentiable loss, a subgradient $g_t$ here means a vector satisfying the supporting inequality $f_t(u)\geq f_t(x_t)+\langle g_t,u-x_t\rangle$ for every $u\in K$. In particular, $f_t(x_t)-f_t(u)\leq\langle g_t,x_t-u\rangle$.

The fixed-comparator regret over $T$ rounds is $\sum_{t=1}^T [f_t(x_t)-f_t(u)]$, where $u\in K$ is chosen for comparison. The bound below holds for every such $u$. It is deterministic and applies to each realized sequence of losses and subgradients satisfying the assumptions; no stochastic assumption is needed.

The Projection Inequality

The geometric fact used in the regret proof is that projecting a point cannot increase its distance to any point in the convex set. We first establish this fact from the definition of projection.

Proposition: If $K$ is nonempty, closed, and convex, $y\in\mathbb{R}^d$, and $z=\Pi_K(y)$, then for every $u\in K$, $$ \|z-u\|_2^2\leq \|y-u\|_2^2. $$

Proof. The minimizing property of $z$ implies the variational inequality $\langle y-z,v-z\rangle\leq 0$ for every $v\in K$. To see this, the segment $z+s(v-z)$, $0\leq s\leq 1$, lies in $K$. The function $\|y-z-s(v-z)\|_2^2$ is minimized over this segment at $s=0$, so its right derivative at zero is nonnegative: $-2\langle y-z,v-z\rangle\geq 0$. Taking $v=u$, expand $$ \|y-u\|_2^2 =\|y-z\|_2^2+\|z-u\|_2^2+2\langle y-z,z-u\rangle. $$ The variational inequality gives $\langle y-z,z-u\rangle\geq 0$, and $\|y-z\|_2^2\geq 0$. Therefore $\|y-u\|_2^2\geq\|z-u\|_2^2$, as claimed. $\square$

This proposition applies even when the unprojected point $y$ lies far outside $K$. It is the comparison point $u$, not necessarily the previous iterate, whose distance is controlled.

Regret Bound from the Squared-Distance Potential

Theorem: Suppose $x_1\in K$, and on each round $t=1,\ldots,T$, the loss $f_t$ is convex and the selected subgradient $g_t$ at $x_t$ satisfies the supporting inequality on $K$. For the projected update with a fixed $\eta>0$, every $u\in K$ satisfies $$ \sum_{t=1}^T [f_t(x_t)-f_t(u)] \leq \frac{\|x_1-u\|_2^2}{2\eta} +\frac{\eta}{2}\sum_{t=1}^T\|g_t\|_2^2. $$ In particular, since $\|x_1-u\|_2\leq D$, the first term is at most $D^2/(2\eta)$.

Proof. On round $t$, apply the projection inequality with $y=x_t-\eta g_t$, $z=x_{t+1}$, and comparator $u\in K$. Expanding the squared norm gives $$ \|x_{t+1}-u\|_2^2 \leq \|x_t-\eta g_t-u\|_2^2 =\|x_t-u\|_2^2-2\eta\langle g_t,x_t-u\rangle+\eta^2\|g_t\|_2^2. $$ The subgradient inequality implies $f_t(x_t)-f_t(u)\leq\langle g_t,x_t-u\rangle$. Rearranging the preceding distance inequality and applying this loss comparison yields $$ 2\eta [f_t(x_t)-f_t(u)] \leq \|x_t-u\|_2^2-\|x_{t+1}-u\|_2^2+\eta^2\|g_t\|_2^2. $$ Sum this inequality from $t=1$ to $T$. The distance terms telescope: $$ 2\eta\sum_{t=1}^T[f_t(x_t)-f_t(u)] \leq \|x_1-u\|_2^2-\|x_{T+1}-u\|_2^2 +\eta^2\sum_{t=1}^T\|g_t\|_2^2. $$ Since the final squared distance is nonnegative, discard its negative contribution and divide by $2\eta>0$. This proves the stated bound. $\square$

The bound separates two costs. A smaller learning rate reduces the accumulated gradient term, but increases the initial-distance term. If $\|g_t\|_2\leq G$ on every round, then $\sum_{t=1}^T\|g_t\|_2^2\leq TG^2$, so $$ \sum_{t=1}^T[f_t(x_t)-f_t(u)] \leq \frac{D^2}{2\eta}+\frac{\eta TG^2}{2}. $$ For positive $D$, $G$, and $T$, the right-hand side is minimized at $\eta=D/(G\sqrt{T})$, giving the familiar $DG\sqrt{T}$ guarantee. If the sum of squared gradient norms is known instead, write it as $S$; for $S>0$ the bound is minimized at $\eta=D/\sqrt{S}$, giving $D\sqrt{S}$. These choices require the relevant quantities to be available when setting the learning rate; the theorem itself holds for any positive fixed rate.

Worked Updates and Bounds

Worked Example: Updates on a Bounded Interval

Let $K=[0,1]$, $x_1=1/2$, and $\eta=1/4$. Use two linear losses $f_1(x)=x$ and $f_2(x)=-x$, whose gradients are $g_1=1$ and $g_2=-1$.

On round 1, the unprojected point is $x_1-\eta g_1=1/2-1/4=1/4$, already in $K$. Thus $x_2=1/4$. On round 2, the unprojected point is $x_2-\eta g_2=1/4+1/4=1/2$, so $x_3=1/2$.

The learner’s losses are $f_1(x_1)=1/2$ and $f_2(x_2)=-1/4$, for a total of $1/4$. Against comparator $u=0$, the comparator’s total loss is $0$, so regret is $1/4$. Against $u=1$, the comparator’s losses are $1$ and $-1$, again totaling $0$, so regret is also $1/4$.

Here $D=1$ and $\sum_t\|g_t\|_2^2=2$. The theorem’s bound at the chosen rate is $1/(2(1/4))+(1/4)(2)/2=2+1/4=9/4$, which is valid but not tight. This example makes clear that the theorem is a worst-case guarantee, not an exact prediction of realized regret.

Worked Example: A Projection onto the Unit Ball

Let $K=\{x\in\mathbb{R}^2:\|x\|_2\leq 1\}$, start at $x_1=(0,0)$, and take $\eta=1$. On round 1 use $f_1(x)=-2x_1$, with gradient $g_1=(-2,0)$. The raw update is $(0,0)-(-2,0)=(2,0)$, whose projection onto the unit ball is $x_2=(1,0)$.

On round 2 use $f_2(x)=-x_2$, with gradient $g_2=(0,-1)$. The raw update from $(1,0)$ is $(1,1)$, with norm $\sqrt{2}$. Its projection is $x_3=(1,1)/\sqrt{2}$, since this point lies on the unit circle in the same direction as $(1,1)$.

The learner’s two losses are $f_1(x_1)=0$ and $f_2(x_2)=0$. For comparator $u=(1,0)$, both losses are $-2$ and $0$, respectively, so the comparator’s total is $-2$ and the learner’s regret is $2$. The ball has diameter $D=2$, and the squared gradient norms sum to $4+1=5$. The theorem gives $2^2/(2\cdot 1)+1\cdot5/2=4.5$, which bounds the regret $2$.

Worked Example: Choosing a Rate from Diameter and Gradient Bounds

Suppose $K=[0,3]$, so $D=3$, and consider $T=9$ losses $f_t(x)=2x$. Each gradient is $g_t=2$, hence $G=2$. The diameter-and-gradient choice is $\eta=D/(G\sqrt{T})=3/(2\cdot3)=1/2$.

Starting at $x_1=3/2$, the first raw update is $3/2-(1/2)2=1/2$, so $x_2=1/2$. The next raw update is $1/2-1=-1/2$, which projects to $x_3=0$. All later iterates remain at zero. The learner’s nine losses therefore total $2(3/2)+2(1/2)+7(0)=4$. Comparator $u=0$ has total loss $0$, so the regret is $4$.

The uniform bound is $D^2/(2\eta)+\eta TG^2/2=9/1+ (1/2)(9)(4)/2=9+9=18$, equivalently $DG\sqrt{T}=18$. For comparison, choosing $\eta=1$ would give $9/2+18=22.5$ in the same bound. The optimized rate balances the two terms; it does not make every sequence attain the bound.

What the Bound Does and Does Not Say

The diameter enters because the initial distance to any fixed feasible comparator is at most $D$. The gradient bound enters through the sum of squared step directions: a larger $G$ increases the cost of taking a given learning rate. If the gradients along the realized path are known only through their individual norms, the theorem still gives the more informative pathwise expression involving $\sum_t\|g_t\|_2^2$.

A frequent mistake is to write the unconstrained update $x_{t+1}=x_t-\eta g_t$ while claiming a guarantee over $K$, without checking that the iterates remain feasible. The update can leave $K$, and then the next decision may violate the protocol. The correction is to project each raw step onto $K$; the projection inequality is precisely what makes the distance-based regret proof work for constrained decisions. Another mistake is to infer a finite $DG\sqrt{T}$ bound without a finite diameter and a gradient bound. The theorem’s pathwise form remains valid under its stated assumptions, but a uniform rate requires controlling those quantities.

Key takeaway: Projected online gradient descent combines a feasible update with a squared-distance potential. Convexity converts each round’s regret to a gradient inner product; projection bounds that product by a telescoping distance change and a squared-gradient term.

Check Your Understanding

Work through these questions using the definitions and proof above.

Which step in the regret proof uses convexity of the loss, and which step uses convexity of the feasible set?
If the gradient norms satisfy $\|g_t\|_2\leq G$, write the regret bound for a fixed $\eta$ in terms of $D$, $G$, and $T$.
For what positive learning rate is that uniform bound minimized when $D$, $G$, and $T$ are positive?
Why does the projection inequality compare the projected point to a feasible comparator, rather than assert that projection reduces the loss?
What can be concluded from the theorem if the gradient norms are not uniformly bounded but their squared norms along the realized sequence have a finite sum?