Mirror maps, Bregman divergence, and local Hessian norms

Let $d\ge 1$, let $K\subseteq {\mathbb{R}}^d$ be a nonempty bounded closed convex set with nonempty interior, and let $U\subseteq {\mathbb{R}}^d$ be an open convex set such that $\mathrm{int}(K)\subseteq U$ and $K\subseteq \bar{U}$. If a decision set is lower-dimensional in an ambient Euclidean space, take ${\mathbb{R}}^d$ to be orthonormal affine coordinates on its affine hull (the smallest affine subspace containing it); thus interior, gradients, Hessians, and norms are relative to that affine hull. A mirror regularizer on $(K,U)$ is a real-valued function $R$ on $K\cup U$ that is continuous on $K$, twice continuously differentiable on $U$, agrees on $K\cap U$, and has symmetric positive-definite Hessian $H_R(z):={\mathrm{\nabla }}^{2}R(z)$ for every $z\in U$. We call $R$ $m$-strongly convex on $K$ in the Euclidean norm if, for some $m>0$, all $x,y\in K$ and $\lambda \in [0,1]$ satisfy

$R((1-\lambda )x+\lambda y)\le (1-\lambda )R(x)+\lambda R(y)-\frac{m}{2}\lambda (1-\lambda )\mathrm{\parallel }x-y{\mathrm{\parallel }}_2^2\mathrm{.}$

For $x\in K\cup U$ and $y\in U$, the Bregman divergence generated by $R$ is

$B_R(x\mathrm{\parallel }y):=R(x)-R(y)-⟨\mathrm{\nabla }R(y),x-y⟩\mathrm{.}$

For $z\in U$ and vectors $v,h\in {\mathbb{R}}^d$, define the squared local primal norm and local dual norm by

$\mathrm{\parallel }v{\mathrm{\parallel }}_z^2:=v^{\mathrm{\top }}{H}_R(z)v,\mathrm{\parallel }h{\mathrm{\parallel }}_{\ast ,z}^2:=h^{\mathrm{\top }}{H}_R(z{)}^{-1}h\mathrm{.}$

A convex subset of ${\mathbb{R}}^m$ contains every line segment between two of its points: convexity means that every segment between points of the set lies in the set.

Convex and strictly convex functions on Euclidean convex sets: defines ordinary and strict convexity; the displayed quantitative inequality defines strong convexity locally here.

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

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $\mathrm{\nabla }R$ is the vector of first partial derivatives.

The Hessian matrix and critical points of a scalar field: ${\mathrm{\nabla }}^{2}R$ is the Hessian matrix of second partial derivatives.

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 and closed use the Euclidean metric topology.

Interior, closure, boundary, limit point, isolated point and dense subset of a metric space: $\mathrm{int}(K)$ and $\bar{U}$ are the interior and closure in that topology.

Bounded subset, diameter, distance from a point to a set, and distance between two sets in a metric space: boundedness uses the Euclidean metric.