Existence and Uniqueness of Bregman Projection

convex optimizationconvex-analysis

I am trying to work through a book which covers the Bregman Divergence. The authors adopt the following definitions:

We call Legendre any function $F: \mathcal{A} \rightarrow \mathbb{R}$
such that

  1. $\mathcal{A} \subseteq \mathbb{R}^{n}$ and its interior point $\text{int}(\mathcal{A})$ is convex.
  2. $F$ is strictly convex with continuous first partial derivatives throughout $\text{int}(\mathcal{A})$.
  3. If $x_{1}, x_{2}, \dots \in \mathcal{A}$ is a sequence converging to a boundary point of $\mathcal{A}$ then $\|\nabla F(x_{n})\| \to
    \infty$     as $n \to \infty$

The Bregman Divergence induced by a Legendre function $F: \mathcal{A}
\to \mathbb{R}$ is a nonnegative function $D_{F}: \mathcal{A} \times
\text{int}(\mathcal{A}) \to \mathbb{R}$ defined by $$ D_{F}(u, v) = F(u) – F(v) – (u – v) \cdot \nabla F(v) $$

The Bregman projection of $w \in \text{int}(\mathcal{A})$ onto
$\mathcal{S}$ is $$ \text{argmin}_{u \in \mathcal{S} \cap
\mathcal{A}}D_{F}(u, w) $$

The authors then state the following result, saying that it relies on "standard calculus":

For all Legendre function $F: \mathcal{A} \rightarrow \mathbb{R}$, for
all closed convex sets $\mathcal{S} \subseteq \mathbb{R}^{d}$ such
that $\mathcal{A}\cap\mathcal{S} \neq \emptyset$, and for all $w \in
\text{int}(\mathcal{A})$, the Bregman projection of $w$ onto
$\mathcal{S}$ exists and is unique.

How would I go about proving this? I am aware that strictly convex functions on closed convex sets have unique minimizers, and that existence is guaranteed if the function has compact sublevel sets. But in this case $\mathcal{A}\cap\mathcal{S}$ may not be closed (nor convex?).

EDIT: For those curious, this is Lemma 11.1 from the book "Prediction Learning and Games", page 295.

Best Answer

So this problem seems to be far from "standard calculus" and involves quite deep theory from convex analysis. I have found that this question in the literature is referred to as "zone consistency" of the Legendre function $F$. That is a function $F$ is zone-consistent if its Bregman projection is unique and always exists at every point. A proof that Legendre functions are zone consistent in reflexive Banach spaces can be found at the end of the following paper by Bauschke at al. Similarly, a proof for Euclidean spaces is listed as Theorem 3.12 in the following paper by Bauschke and Borwein.

Related Question