Projected online gradient descent

Let $d,T\ge 1$ be integers, let $K\subseteq {\mathbb{R}}^d$ be nonempty, closed, and convex, and let $D,G\ge 0$ be finite real bounds such that $\mathrm{\parallel }u-v{\mathrm{\parallel }}_2\le D$ for all $u,v\in K$ and $\mathrm{\parallel }{g}_t{\mathrm{\parallel }}_2\le G$. Supply an initial point $x_1\in K$. At each round $t=1,\dots ,T$, the learner plays $x_t$ and then receives the full loss function $f_t$ or the prescribed vector $g_t$. The smooth branch takes $f_t:U_t\to \mathbb{R}$ differentiable and convex on an open convex set $U_t\supseteq K$, with $g_t=\mathrm{\nabla }{f}_t(x_t)$. The nonsmooth branch takes a convex function $f_t:C_t\to \mathbb{R}$ on a convex set $C_t\supseteq K$ and a supplied $g_t\in \mathrm{\partial }{f}_t(x_t)$, where $\mathrm{\partial }{f}_t(x_t)$ consists of vectors $g$ satisfying $f_t(y)\ge f_t(x_t)+⟨g,y-x_t⟩$ for every $y\in C_t$; require explicitly that this inequality holds for every $u\in K$.

If $D=0$ or $G=0$, set $x_{t+1}=x_t$ at every round. If $D,G>0$, assume the Axiom of Countable Choice for the metric projection. Set ${\eta }_t=D\mathrm{/}(G\sqrt{t})$, put $y_{t+1}=x_t-{\eta }_t{g}_t$, and set $x_{t+1}=P_K(y_{t+1})$, the unique point of $K$ minimizing Euclidean distance to $y_{t+1}$. Return the decisions $x_1,\dots ,x_T$. Equip ${\mathbb{R}}^d$ with its Euclidean Borel $\sigma$-algebra and $K$ with the relative Borel $\sigma$-algebra. For random inputs, require $x_1$ to be a measurable $K$-valued random element and each $g_t$, whether supplied directly or computed as $\mathrm{\nabla }{f}_t(x_t)$ in the smooth branch, to be a measurable ${\mathbb{R}}^d$-valued random element on the protocol's probability space. The vector update is continuous, and the nonexpansive projection is continuous, so each projected update remains measurable.

Online decision protocol: the learner plays before receiving current-round feedback.

Adversary and feedback models: full-information feedback reveals the current loss function after the choice.

Random elements and real random variables: randomized decisions and gradient inputs are measurable random elements.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: the inner product and norm on ${\mathbb{R}}^d$ are the standard Euclidean ones.

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: open neighborhoods and closed decision sets are taken in the Euclidean metric topology.

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: a convex decision set contains the segment between any two of its points.

Convex and strictly convex functions on Euclidean convex sets: convexity of a loss on its domain.

Differentiable convex functions are characterized by the gradient inequality: on an open convex domain, differentiable convex losses satisfy the gradient inequality.

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $\mathrm{\nabla }{f}_t(x_t)$ is the vector of scalar partial derivatives in the standard Euclidean coordinates.

Subgradients and the subdifferential of a convex function: the nonsmooth subgradient is a vector satisfying the stated supporting inequality on the function's domain.

The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$): Countable Choice is assumed only in the nondegenerate branch that invokes projection existence.

Hilbert space: a real Hilbert space is a complete real inner-product space.

$\mathbb{R}$ and ${\mathbb{R}}^n$ for $n\ge 1$ with the Euclidean metric are complete, componentwise from the Cauchy criterion in $\mathbb{R}$: ${\mathbb{R}}^d$ with its Euclidean metric is complete for $d\ge 1$.

Projection onto a nonempty closed convex set: under Countable Choice, each point of a real Hilbert space has a unique nearest point in a nonempty closed convex set.

The metric projection onto a closed convex set is nonexpansive: the metric projection is nonexpansive and therefore continuous.