Proximal three-point identity

Proximal operator

Consider the following optimization problem:

$$\underset{\mathbf{x}\in {\mathbb{R}}^n}{\min }\{F(\mathbf{x}):=f(\mathbf{x})+\omega (\mathbf{x})\},$$

where $f:{\mathbb{R}}^n\to \mathbb{R}$ is a differentiable convex function and $\omega :{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$ is a proper closed convex function as a regularizer, which may be non-differentiable.

At iteration $t$, we have current point ${\mathbf{x}}_t$ and a first-order direction ${\mathbf{g}}_t$. Then the next iterate ${\mathbf{x}}_{t+1}$ is obtained by

$${\mathbf{x}}_{t+1}=\arg \underset{\mathbf{x}\in {\mathbb{R}}^n}{\min }\left\{\underset{\text{1-order direction}}{\underbrace{⟨{\mathbf{g}}_t,\mathbf{x}⟩}}+\underset{\text{regularizer}}{\underbrace{\omega (\mathbf{x})}}+\underset{\text{proximal term}}{\underbrace{\frac{1}{2{\eta }_t}\Vert \mathbf{x}-{\mathbf{x}}_t{\Vert }_2^2}}\right\},{\eta }_t>0,$$

• ${\mathbf{g}}_t$ could be any first-order direction (e.g., gradient, subgradient, stochastic gradient, or even just some arbitrary direction by some first-order oracle).

The three-point identities

The first-order optimality condition of the above problem is $0\in {\mathbf{g}}_t+\partial \omega ({\mathbf{x}}_{t+1})+\frac{1}{{\eta }_t}({\mathbf{x}}_{t+1}-{\mathbf{x}}_t)$, which is equivalent to, for some ${\mathbf{s}}_{t+1}\in \partial \omega ({\mathbf{x}}_{t+1})$,

$${\mathbf{g}}_t+{\mathbf{s}}_{t+1}=-\frac{1}{{\eta }_t}({\mathbf{x}}_{t+1}-{\mathbf{x}}_t).\text{\hspace{1em}(1)}$$

Given any reference point $\bar{\mathbf{x}}\in {\mathbb{R}}^n$, since $\omega$ is convex, we have $\omega (\bar{\mathbf{x}})\ge \omega ({\mathbf{x}}_{t+1})+⟨{\mathbf{s}}_{t+1},\bar{\mathbf{x}}-{\mathbf{x}}_{t+1}⟩$, then adding $⟨{\mathbf{g}}_t,\bar{\mathbf{x}}-{\mathbf{x}}_{t+1}⟩$ to both sides, we have $⟨{\mathbf{g}}_t,{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩+\omega ({\mathbf{x}}_{t+1})-\omega (\bar{\mathbf{x}})\le ⟨{\mathbf{s}}_{t+1}+{\mathbf{g}}_t,{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩$.

$$⟨{\mathbf{g}}_t,{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩+\omega ({\mathbf{x}}_{t+1})-\omega (\bar{\mathbf{x}})\le \frac{1}{{\eta }_t}⟨{\mathbf{x}}_t-{\mathbf{x}}_{t+1},{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩.$$

A useful identity is that for any $\mathbf{a},\mathbf{b},\mathbf{c}\in {\mathbb{R}}^n$,

$$2⟨\mathbf{a}-\mathbf{b},\mathbf{b}-\mathbf{c}⟩=\Vert \mathbf{a}-\mathbf{c}{\Vert }_2^2-\Vert \mathbf{a}-\mathbf{b}{\Vert }_2^2-\Vert \mathbf{b}-\mathbf{c}{\Vert }_2^2.$$

Let $\mathbf{a}={\mathbf{x}}_t,\mathbf{b}={\mathbf{x}}_{t+1},\mathbf{c}=\bar{\mathbf{x}}$, we have $2⟨{\mathbf{x}}_t-{\mathbf{x}}_{t+1},{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩=\Vert {\mathbf{x}}_t-\bar{\mathbf{x}}{\Vert }_2^2-\Vert {\mathbf{x}}_t-{\mathbf{x}}_{t+1}{\Vert }_2^2-\Vert {\mathbf{x}}_{t+1}-\bar{\mathbf{x}}{\Vert }_2^2$. Thus, we have the following three-point identity:

$$⟨{\mathbf{g}}_t,{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩+\omega ({\mathbf{x}}_{t+1})-\omega (\bar{\mathbf{x}})\le \frac{1}{2{\eta }_t}\left(\Vert {\mathbf{x}}_t-\bar{\mathbf{x}}{\Vert }_2^2-\Vert {\mathbf{x}}_t-{\mathbf{x}}_{t+1}{\Vert }_2^2-\Vert {\mathbf{x}}_{t+1}-\bar{\mathbf{x}}{\Vert }_2^2\right).$$

Several notes:

• The inequality is due to the convexity of $\omega$. If $\omega \equiv 0$, then ${\mathbf{s}}_{t+1}=0$ and the inequality becomes an equality.
• The three-point identity transforms the first-order quantity to distance-based quantities, which is useful in convergence analysis, especially $\Vert {\mathbf{x}}_t-\bar{\mathbf{x}}{\Vert }_2^2-\Vert {\mathbf{x}}_{t+1}-\bar{\mathbf{x}}{\Vert }_2^2$ can be telescoped over iterations.

Mirror Descent version of the three-point identity

In a more general sense, we could consider the Mirror Descent method, where the Euclidean distance is replaced by a Bregman divergence $D_h(\mathbf{x},\mathbf{y})=h(\mathbf{x})-h(\mathbf{y})-⟨\nabla h(\mathbf{y}),\mathbf{x}-\mathbf{y}⟩$ for some strongly convex function $h$. Then the mirror step is (we first temporarily ignore the regularizer $\omega$ and ${\eta }_t$ is the step size):

$${\mathbf{x}}_{t+1}=\arg \underset{\mathbf{x}\in {\mathbb{R}}^n}{\min }\left\{{\eta }_t⟨{\mathbf{g}}_t,\mathbf{x}⟩+D_h(\mathbf{x},{\mathbf{x}}_t)\right\},{\eta }_t>0.$$

• It still follows the first-order direction + proximal geometry structure.

Similar to the Euclidean case, we have the following basic equality: for any $\mathbf{a},\mathbf{b},\mathbf{c}\in {\mathbb{R}}^n$,

$$⟨\nabla h(\mathbf{b})-\nabla h(\mathbf{c}),\mathbf{a}-\mathbf{b}⟩=D_h(\mathbf{a},\mathbf{c})-D_h(\mathbf{a},\mathbf{b})-D_h(\mathbf{b},\mathbf{c}).$$

Proof

(Basically directly obtained) by the definition of Bregman divergence, we have

$$\begin{array}{rl}{D}_h(\mathbf{a},\mathbf{c})-D_h(\mathbf{a},\mathbf{b})-D_h(\mathbf{b},\mathbf{c})& =-⟨\nabla h(\mathbf{c}),\mathbf{a}-\mathbf{c}⟩+⟨\nabla h(\mathbf{b}),\mathbf{a}-\mathbf{b}⟩+⟨\nabla h(\mathbf{c}),\mathbf{b}-\mathbf{c}⟩\\ & =⟨\nabla h(\mathbf{b})-\nabla h(\mathbf{c}),\mathbf{a}-\mathbf{b}⟩.\end{array}$$

$\square$

Then, let $\mathbf{a}=\bar{\mathbf{x}},\mathbf{b}={\mathbf{x}}_{t+1},\mathbf{c}={\mathbf{x}}_t$, we have

$$⟨\nabla h({\mathbf{x}}_{t+1})-\nabla h({\mathbf{x}}_t),\bar{\mathbf{x}}-{\mathbf{x}}_{t+1}⟩=D_h(\bar{\mathbf{x}},{\mathbf{x}}_t)-D_h(\bar{\mathbf{x}},{\mathbf{x}}_{t+1})-D_h({\mathbf{x}}_{t+1},{\mathbf{x}}_t).$$

For Mirror Descent, given that ${\nabla }_{\mathbf{x}}{D}_h(\mathbf{x},{\mathbf{x}}_t)=\nabla h(\mathbf{x})-\nabla h({\mathbf{x}}_t)$, the first-order optimality condition is

$$⟨{\eta }_t{\mathbf{g}}_t+\nabla h({\mathbf{x}}_{t+1})-\nabla h({\mathbf{x}}_t),\mathbf{x}-{\mathbf{x}}_{t+1}⟩\ge 0,\forall \mathbf{x}\in \mathcal{X},$$

Then plugging in the three-point equality, we have the following three-point identity for Mirror Descent:

$${\eta }_t⟨{\mathbf{g}}_t,{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩\le D_h(\bar{\mathbf{x}},{\mathbf{x}}_t)-D_h(\bar{\mathbf{x}},{\mathbf{x}}_{t+1})-D_h({\mathbf{x}}_{t+1},{\mathbf{x}}_t).$$

• If let $h(\mathbf{x})=\frac{1}{2}\Vert \mathbf{x}{\Vert }_2^2$, then $D_h(\mathbf{x},\mathbf{y})=\frac{1}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }_2^2$, and the Mirror Descent three-point identity reduces to the Euclidean three-point identity.

We could further consider the Mirror Descent with a regularizer $\omega$, then the composite Mirror Descent step is

$${\mathbf{x}}_{t+1}=\arg \underset{\mathbf{x}\in \mathcal{X}}{\min }\left\{{\eta }_t⟨{\mathbf{g}}_t,\mathbf{x}⟩+D_h(\mathbf{x},{\mathbf{x}}_t)+{\eta }_t\omega (\mathbf{x})\right\},{\eta }_t>0.$$

Let ${\mathbf{s}}_{t+1}\in \partial \omega ({\mathbf{x}}_{t+1})$, then the first-order optimality condition is

$$⟨{\eta }_t{\mathbf{g}}_t+{\eta }_t{\mathbf{s}}_{t+1}+\nabla h({\mathbf{x}}_{t+1})-\nabla h({\mathbf{x}}_t),\mathbf{x}-{\mathbf{x}}_{t+1}⟩\ge 0,\forall \mathbf{x}\in \mathcal{X},$$

which gives

$${\eta }_t⟨{\mathbf{g}}_t+{\mathbf{s}}_{t+1},{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩\le D_h(\bar{\mathbf{x}},{\mathbf{x}}_t)-D_h(\bar{\mathbf{x}},{\mathbf{x}}_{t+1})-D_h({\mathbf{x}}_{t+1},{\mathbf{x}}_t).$$

By the convexity of $\omega$, we have

$$\omega ({\mathbf{x}}_{t+1})-\omega (\bar{\mathbf{x}})\le ⟨{\mathbf{s}}_{t+1},{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩,$$

combining the above two inequalities, we have the three-point identity for composite Mirror Descent:

$${\eta }_t⟨{\mathbf{g}}_t,{\mathbf{x}}_{t+1}-\bar{\mathbf{x}}⟩+{\eta }_t(\omega ({\mathbf{x}}_{t+1})-\omega (\bar{\mathbf{x}}))\le D_h(\bar{\mathbf{x}},{\mathbf{x}}_t)-D_h(\bar{\mathbf{x}},{\mathbf{x}}_{t+1})-D_h({\mathbf{x}}_{t+1},{\mathbf{x}}_t).$$