Agile online mirror descent

Let $(K,U,R)$ be a mirror regularizer with $R$ $m$-strongly convex on $K$ for some $m>0$. Fix an integer horizon $T\ge 1$ and a step size $\eta >0$. Admissibility requires the unique minimizer of $R$ on $K$ to lie in $U$; initialize $x_1$ at this minimizer. At each round $t=1,\dots ,T$, play $x_t$ before observing the full current loss $f_t$, with losses and gradients written in the same affine coordinates used for $K$. Use either of these feedback cases:

1. $f_t$ is differentiable and convex on an open convex set containing $K$, and $g_t=\mathrm{\nabla }{f}_t(x_t)$.
2. $f_t$ is convex on a convex set containing $K$, and a supplied vector $g_t$ satisfies $f_t(u)\ge f_t(x_t)+⟨g_t,u-x_t⟩$ for every $u\in K$.

For each round require that there is a unique $y_{t+1}\in U$ satisfying

$\mathrm{\nabla }R(y_{t+1})=\mathrm{\nabla }R(x_t)-\eta g_t\mathrm{.}$

Set $x_{t+1}$ to the minimizer of $B_R(x\mathrm{\parallel }{y}_{t+1})$ over $x\in K$, and require this minimizer to lie in $U$ so that the next dual update is defined. The Bregman minimizer exists and is unique under the stated strong-convexity and compactness hypotheses. Output the decisions $x_1,\dots ,x_T$; the final $x_{T+1}$ is the internal post-round iterate.

Mirror maps, Bregman divergence, and local Hessian norms: gives the domains, strong-convexity condition, Bregman divergence, and Hessian notation.

Online decision protocol: the learner chooses using only the previous history before the round's current loss is observed.

Adversary and feedback models: full-information feedback reveals the current loss after the learner's choice.

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: convex domains contain every segment between their points.

Convex and strictly convex functions on Euclidean convex sets: defines convexity of each loss function.

The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: the pairing in the subgradient condition is the Euclidean inner product.

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

Subgradients and the subdifferential of a convex function: a supplied vector satisfying the stated supporting inequality is a subgradient at $x_t$.

Differentiable convex functions are characterized by the gradient inequality: the smooth feedback case supplies the same supporting inequality for every comparator in $K$.