Theorem 4.4, p. 305 — mirror prox with η = ρ/β on a convex β-smooth f satisfies f((1/t)Σ_{s=1}^t y_{s+1}) − f(x*) ≤ βR²/(ρt)

Fix an arbitrary norm $\|\cdot\|$ on a finite-dimensional real space, a compact convex set $\mathcal X$, and a convex open set $\mathcal D$ with $\mathcal X\subseteq\overline{\mathcal D}$ and $\mathcal X\cap\mathcal D\ne\emptyset$. Let $\Phi$ be a mirror map on $\mathcal D$ that is $\rho$-strongly convex on $\mathcal X\cap\mathcal D$ with respect to $\|\cdot\|$, with $\rho>0$. Let $f$ be convex and $\beta$-smooth on $\mathcal X$ with respect to $\|\cdot\|$, with $\beta>0$, and let $x^*\in\mathcal X$ minimize $f$ over $\mathcal X$. Run mirror prox with $\eta=\rho/\beta$ from $x_1\in\operatorname{argmin}_{x\in\mathcal X\cap\mathcal D}\Phi(x)$, and let $R$ satisfy

for instance $R^2=\sup_{x\in\mathcal X\cap\mathcal D}\Phi(x)-\Phi(x_1)$. Then for every $t\ge1$,

Mirror prox, introduced by Nemirovski, attains the rate $1/t$ on smooth functions in non-Euclidean geometries, while mirror descent attains $1/\sqrt t$ on Lipschitz functions (Theorem 4.2). The average is over the intermediate points $y_{s+1}$, not over the $x_s$.

Formalization Note The existence of the minimizer $x^*$ is the book's standing assumption (p. 242). The book does not specify $x_1$ in §4.5; it is taken in $\operatorname{argmin}_{\mathcal X\cap\mathcal D}\Phi$ as in mirror descent (§4.2, p. 299), which is what makes $R^2$ bound $D_\Phi(x,x_1)$. $R$ is any real with $\Phi-\Phi(x_1)\le R^2$ on $\mathcal X\cap\mathcal D$; the book's $R^2=\sup$ is the special case where the supremum is finite (when it is $+\infty$ the book's bound is void). $\rho>0$ and $\beta>0$ are the implicit conditions for $\eta=\rho/\beta$ and the division by $\rho t$. The gradient of $f$ is required relative to $\mathcal X$ (HasFDerivWithinAt), matching $f:\mathcal X\to\mathbb R$; $x^*$ may lie on the boundary of $\mathcal D$.