Preliminaries
Maximal Cyclically Monotone Operators and Fitzpatrick Functions
$n$-cyclically monotone operatorsLet \(X\) be a Banach space and \(X^*\) its dual. An operator $A: X \to 2^{X^*}$ is $n$-cyclically monotone if for any $n$ points $(x_1, x_1^*), \ldots, (x_n, x_n^*) \in \text{gra}(A):= \{(x,x^*) \in X \times X^* : x^* \in Ax\}$, we have $$ \sum_{i=1}^n \langle x_{i+1} - x_i,\, x_i^* \rangle \ge 0 $$ where the indices are taken modulo $n$. Further, $A$ is cyclically monotone if it is $n$-cyclically monotone for all $n \ge 2$.
maximal $n$-cyclically monotone operatorsSimilarly, an operator $A: X \to 2^{X^*}$ is maximal $n$-cyclically monotone if it is $n$-cyclically monotone and there is no other $n$-cyclically monotone operator $B: X \to 2^{X^*}$ such that $\text{gra}(A) \subsetneq \text{gra}(B)$. Further, $A$ is maximal cyclically monotone if it is maximal $n$-cyclically monotone for all $n \ge 2$.
Fitzpatrick functionsNow, we can define the Fitzpatrick function for an operator \(A: X \to 2^{X^*}\). The \(n\)-th order Fitzpatrick function of \(A\) is a function $F_{A,n}:X\times X^*\to (-\infty,+\infty]$ defined by: $$F_{A,n}(x_n, x_0^*) := \sup_{\{(x_i,\, x_i^*)\}_{i \in [n-1]} \subseteq \text{gra}(A)} \langle x_1,\, x_0^* \rangle + \sum_{i=1}^{n-1} \langle x_{i+1} - x_i,\, x_i^* \rangle$$ whereas the infinite-order Fitzpatrick function of \(A\) is defined as $F_{A,\infty}(x, x^*) := \sup_{n \ge 2} F_{A,n}(x, x^*)$.
We then have the following results from Bartz et al.[1]Let \(A: X \to 2^{X^*}\) and $n \ge 2$.
- \(F_{A,n}\) is convex and lower semicontinuous.
- $F_{A,n} \ge \langle x, x^* \rangle$ for all $(x, x^*) \in X \times X^*$.
- \(A\) is maximal \(n\)-cyclically monotone if and only if $\operatorname{gra}(A) = \{(x, x^*) \in X \times X^* : F_{A,n}(x, x^*) = \langle x, x^* \rangle\}$
Subdifferentials as a Maximal Cyclically Monotone Operator
The famous result from Rockafellar[2] states that the maximal cyclically monotone operators in $\mathbb{R}$ are precisely the subdifferentials of proper, convex, lower semicontinuous functions. As a consequence, Bartz et al.[1] showed that:Let $f$ be a proper, convex, lower semicontinuous function. Then, for all $(x,x^*) \in X \times X^*$, we have: $$ \langle x,x^*\rangle \le F_{\partial f,2}(x,x^*) \le F_{\partial f,3}(x,x^*) \le \ldots \le F_{\partial f,\infty}(x,x^*)=f(x)+f^*(x^*) $$
Fitzpatrick Functions and Fenchel-Young Gap
Fenchel-Young gapLet $f:X\to(-\infty,+\infty]$ be proper. For $(x,x^*) \in X \times X^*$ define the Fenchel-Young gap \(d_f(x,x^*)\) as \[ d_f(x,x^*)\;:=\;f(x)+f^*(x^*)-\langle x,x^*\rangle . \]
Then, one easily sees that for $f$ proper, convex, and l.s.c., the Fenchel-Young gap is nonnegative and vanishes if and only if $x^*\in\partial f(x)$ (equivalently $x\in\partial f^*(x^*)$).Let $f:X\to(-\infty,+\infty]$ be proper, convex, and l.s.c. Then for every $(x,x^*)$ and every $n\ge 2$, \[ F_{\partial f,n}(x,x^*) \;=\; f(x)+f^*(x^*) \;-\;\inf\;\sum_{i=0}^{n-1} d_f\bigl(x_{i+1},\,x_{i}^*\bigr), \] where the infimum is over the same chains $(x_i,x_i^*)\in\operatorname{gra}(\partial f)$, $i\in [n-1]$, with $x_0^*=x^*$, $x_n=x$.
As we optimize over the chain $(x_i,x_i^*)\in\operatorname{gra}(\partial f)$, $i\in [n-1]$, with $x_0^*=x^*$, $x_n=x$, we can write using the Fenchel-Young inequality: $$ \begin{aligned} F_{\partial f,n}(x_n,x_0^*) &=\sup\langle x_1,x^*_0\rangle+\sum_{i=1}^{n-1}\langle x_{i+1}-x_i,x_i^*\rangle \\&=\sup\sum_{i=0}^{n-1}\langle x_{i+1},x_i^*\rangle - \sum_{i=1}^{n-1}\langle x_i,x_i^*\rangle \\&=\sup\sum_{i=0}^{n-1}[f(x_{i+1})+f^*(x^*_{i})-d_{f}(x_{i+1},x^*_{i})]-\sum_{i=1}^{n-1}[f(x_i)+f^*(x_i^*)] \\&=\sup f(x_n)+f^*(x^*_0)-\sum_{i=0}^{n-1}d_f(x_{i+1},x^*_{i}) \\&=f(x)+f^*(x^*)-\inf\sum_{i=0}^{n-1}d_f(x_{i+1},x^*_{i}) \end{aligned} $$
□
- $d_{f^*}(x^*,x)=d_f(x,x^*)$
- $\Delta_{f^*,n}(x^*,x)=\Delta_{f,n}(x,x^*)$
- $F_{\partial f^*,n}(x^*,x)=F_{\partial f,n}(x,x^*)$
Let $f:X\to \mathbb{R}\cup\{+\infty\}$ be convex, l.s.c., and proper. Then, for any $n\ge 2$, we have: $$ \operatorname{dom} f\times \operatorname{dom} f^*\subseteq \operatorname{dom} F_{\partial f,n}\subseteq \overline{\operatorname{dom} f}\times \overline{\operatorname{dom} f^*} $$
The result for $n=2$ is already shown in Bauschke et al.[3]. Let $(x,x^*)\in \operatorname{dom} F_{\partial f,n}$. Then, for the 2nd-order optimizer $(a,a^*)\in \operatorname{gra}(\partial f)$, by setting $(a_1,a_1^*)=\cdots=(a_{n-1},a_{n-1}^*)=(a,a^*)$, $$ +\infty >F_{\partial f,n}(x,x^*)\ge \langle x-a,a^*\rangle+\langle a,x^*\rangle = F_{\partial f,2}(x,x^*). $$and $(x,x^*)\in \operatorname{dom} F_{\partial f,2}$. Hence, by the result for $n=2$, $(x,x^*)\in \overline{\operatorname{dom} f}\times \overline{\operatorname{dom} f^*}$. For the other inclusion, assume $(x,x^*)\in \operatorname{dom} f\times \operatorname{dom} f^*$. Now, let $\{(a_i,a_i^*)\}_{i\in[n-1]}\subseteq\text{gra}(\partial f)$ be arbitrary. By definition we have that: $$ \langle a_{i+1}-a_i,a_i^*\rangle\le f(a_{i+1}) - f(a_i),\quad \langle x-a_{n-1},a^*_{n-1}\rangle \le f(x)-f(a_{n-1}) $$Summing the chains give us via Fenchel-Young: $$ \langle x-a_{n-1},a^*_{n-1}\rangle +\sum_{i=1}^{n-2}\langle a_{i+1}-a_i,a_i^*\rangle +\langle a_1,x^*\rangle\le f(x)-f(a_1)+\langle a_1,x^*\rangle\le f(x)+f^*(x^*) $$Hence, $F_{\partial f,n}(x,x^*)\le f(x)+f^*(x^*)<+\infty$. This concludes the proof.
□
Fitzpatrick Functions for Entropy Subdifferentials
Negative Entropy
Negative entropy The negative entropy function is defined as: $$f:\mathbb{R}\to (-\infty,+\infty],\quad x\mapsto \begin{cases}+\infty&x<0\\0&x=0\\x \ln(x)-x&x>0\end{cases}$$One can see that $f$ is convex, proper and l.s.c. The subdifferential of negative entropy is given by $\partial f(x) = \{\ln(x)\}$ for $x>0$ and $\partial f(0) = \varnothing$. Further, the convex conjugate $f^*$ is given by $f^*=\exp$. Therefore, we can rewrite the Fitzpatrick function as follows:
$$ F_{\partial f,n}(x_n,x^*_0) = \sup_{x_1,\dots,x_{n-1}>0} \left[ x_1 x^* +\sum_{i=1}^{n-1} (x_{i+1}-x_i) \ln x_i \right] $$ Bartz et al.[1] showed that the 2nd-order Fitzpatrick function for the negative entropy subdifferential can be expressed in closed form as follows:Let $f$ be the negative entropy function. Then: $$ F_{\partial f,2}(x,x^*) =\begin{cases} +\infty & x < 0 \\ \exp(x^*-1) & x = 0 \\ xx^*+x\left(W(\kappa)+\frac{1}{W(\kappa)}-2\right) & x > 0 \end{cases} $$ where $\kappa = x \exp(1-x^*)$ and $W$ is the Lambert W function.
Let $f$ be the negative entropy function and $\Phi(w):=\exp(w-1)$. Then, for $n\ge 2$, we have: $$ F_{\partial f,n}(x,x^*) =\begin{cases} +\infty & x < 0 \\ f(x)+x-H^*_n(x) & x \ge 0 \end{cases} $$ where $H_n(v):=\Phi^n(v)\exp(x^*)$ with $\Phi^n$ denoting the $n$-th iterate of $\Phi$.
By Theorem 2.2, $\operatorname{dom} F_{\partial f,n} = \mathbb{R}_{\ge 0} \times \mathbb{R}$ for all $n \ge 2$.
We first rewrite the Fitzpatrick objective as a one-parameter optimization problem: Let $h$ be the objective function in the Fitzpatrick definition. Then, we have that the FOC's are given as below: $$ \begin{aligned} \frac{\partial h}{\partial x_{i}} &=-\ln x_i+\frac{x_{i+1}}{x_i}-1+\ln x_{i-1}=0, \quad \forall i=2,\dots,n-1 \\ \frac{\partial h}{\partial x_{1}} &=-\ln x_1+\frac{x_2}{x_1}-1+x^*=0 \end{aligned} $$
Then, we define $r_i:= x_{i+1} / x_i$ and we have $\ln r_{i-1}=r_i-1$ and $\ln x_1=r_1-1+x^*$. Therefore, $$ \begin{aligned} F_{\partial f,n}(x_n,x^*)&=\sum_{i=1}^{n-1}(x_{i+1}-x_i)\ln x_i + x_1x^* \\&=\sum_{i=2}^{n}x_{i}\ln x_{i-1}-\sum_{i=1}^{n-1}x_i\ln x_i + x_1x^* \\&=x_n \ln x_{n-1}-\sum_{i=2}^{n-1}x_{i}\ln r_{i-1} - x_1\ln x_1+ x_1x^* \\&=x_n \ln x_{n-1}-\sum_{i=2}^{n-1}x_{i}(r_{i}-1) - x_1(r_1-1+x^*)+ x_1x^* \\&=x_n \ln x_{n-1}-\sum_{i=1}^{n-1}(x_{i+1}-x_i) \\&=x_n \ln x_{n-1}-x_n + x_1 \end{aligned} $$ Let us define $w:= r_{n-1}$. Then, by the FOCs we get that $r_{n-k}=\Phi^{k-1}(w)$. Hence, the original $n-1$ variables collapse into a single parameter $w>0$ with the endpoints linked by: $$ x_{n-1}=\frac{x}{w},\quad x_1=\Phi^{n-1}(w) \exp(x^*) $$ Therefore, we can rewrite the Fitzpatrick objective as a single parameter optimization problem: $$ F_{\partial f,n}(x,x^*) = \inf_{w>0} \left[ x\ln \frac{x}{w}-x+\Phi^{n-1}(w)\exp (x^*)\right] $$ Notice that the objective function in (21) is a strictly convex function. Further, the FOCs from above can be summarized into one equation: $$ \Phi^{n-1}(w)\exp (x^*) = x_1=\frac{x}{r_{n-1}\cdots r_1}=\frac{x}{\prod_{0\le i\le n-2} \Phi^{i}(w)} $$ i.e., $\prod_{0\le i\le n-1} \Phi^{i}(w)=x / \exp (x^*)$. We show that this coincides with the FOC of the single parameter objective function: Indeed, let $g(w):=x\ln \frac{x}{w}-x+\Phi^{n-1}(w)\exp (x^*)$. Then, $$ g'(w)=-\frac{x}{w}+\exp (x^*)\prod_{k=1}^{n-1}\Phi^{k}(w) = 0 $$This shows that the FOCs coincide.Therefore, we have that by substituting $v:=1+\ln w$: $$ \begin{aligned} F_{\partial f,n}(x,x^*) &= \inf_{w>0} \left[ x\ln \frac{x}{w}-x+\Phi^{n-1}(w)\exp (x^*)\right] \\&= f(x)+\inf_{w>0} \left[-x\ln w+\Phi^{n-1}(w)\exp (x^*)\right] \\&= f(x)+x-\sup_{v\in \mathbb{R}} \left[xv-\Phi^{n}(v)\exp(x^*)\right] \\&= f(x)+x-H^*_n(x) \end{aligned} $$
□
- If $n=2$, we have $H_2(v)=\Phi^2(v)\exp(x^*)=\exp(\exp(v-1))/\exp(1-x^*)$. Hence, the convex conjugate is $$H^*_2(x)=\sup_{v\in \mathbb{R}}[xv-\exp(\exp(v-1))/\exp(1-x^*)]$$ with the FOC given by $x=\exp(\exp(v-1))/\exp(1-x^*)\exp(v-1)$. Solving this we get that $e^{v-1}=W(\kappa)$ with $\kappa=x\exp(1-x^*)$. Hence, we have that $$H^*_2(x)=x(1+\ln W(\kappa))-\frac{\exp(W(\kappa))}{\exp(1-x^*)}=x(1+\ln W(\kappa))-\frac{x}{W(\kappa)}$$ This recovers Fact 3.1.
- Note that for $x>0$, we have that $f^*(\nabla f(x))=f^*(\ln x)=x$. Hence, we can rewrite the Fitzpatrick function as follows: $$F_{\partial f,n}(x,x^*) = f(x)+f^*(\nabla f(x))-H^*_n(f^*(\nabla f(x)))$$ We will observe that this form will reappear in the Fitzpatrick functions of other entropy subdifferentials.
Tsallis Entropy
Tsallis entropyFor $p>1$, the $p$-Tsallis entropy function is defined as: $$ f:\mathbb{R}\to (-\infty,+\infty],\quad x\mapsto \begin{cases}+\infty & x<0 \\x^p/ p&x\ge 0\end{cases} $$ with the subdifferential given by $\partial f(x) = \{x^{p-1}\}$ for $x>0$, $\partial f(0) = \mathbb{R}_{\le 0}$ and $\partial f(x) = \varnothing$ for $x<0$. Further, the convex conjugate is given by $f^*(x^*)=(x^*)^q/q$ for $x^*> 0$ where $1/p+1/q=1$ and $f^*(x^*)=0$ for $x^*\le 0$.
$p$-exponentialWe first introduce the following functions: The $p$-exponential and its inverse $p$-logarithm are defined as follows: $$ \exp_p(x):=\begin{cases} \exp (x)&p=1\\ [1+(1-p)x]_+^{1/(1-p)}&p\ne 1 \end{cases}\quad \quad \ln_p(x):=\begin{cases} \ln (x)&p=1\\ \frac{x^{1-p}-1}{1-p}&p\ne 1 \end{cases} $$where $[z]_+:=\max\{0,z\}$. These functions recover the standard exponential and logarithm in the limit $p\to 1$ and are inverses of each other.
Let $p>1$ and$f$ be the $p$-Tsallis entropy function and $\Phi_p(w):=\exp_p(w-1)$. Then, for $n\ge 2$, we have: $$ F_{\partial f,n}(x,x^*) =\begin{cases} +\infty & x < 0 \\ f(x)+f^*(\nabla f(x))-H^*_n(f^*(\nabla f(x))) & x \ge 0, x^*> 0 \end{cases} $$ where $H_n(v):=\Phi^n_p(v)f^*(x^*)$ with $\Phi^n_p$ denoting the $n$-th iterate of $\Phi_p$.
By Theorem 2.2, $\operatorname{dom} F_{\partial f,n} = \mathbb{R}_{\ge 0} \times \mathbb{R}$ for all $n \ge 2$.
Now assume $x\ge 0$ and $x^* > 0$. Assume that $(x_i,x_i^*)=(0,s)$ for some $s \le 0$. Then, the terms in the Fitzpatrick objective function touching $x_i,x_i^*$ are given by: $x_{i+1}s - x_{i-1}x_{i-1}^*$. As $x_{i+1}\ge 0$, we may w.l.o.g. assume that $s=0$. Further, this shows us that if $x^*>0$, the optimal chain lies completely in $\mathbb{R}_{> 0}$.
Now, similarly to the negative entropy case, we can rewrite the Fitzpatrick objective as a one-parameter optimization problem: We have that the FOC's are given as below: $$ \begin{aligned} x_i^{p}-x_ix_{i-1}^{p-1}&=(p-1)(x_{i+1}-x_i)x^{p-1}_{i},\quad i\in\{2,\dots,n-1\} \\ x_1^{p}-x_1x^*&=(p-1)(x_2-x_1)x^{p-1}_1 \end{aligned} $$
Then, we define $r_i:= x_{i+1} / x_i$ and get the following: $$ \begin{aligned} F_{\partial f,n}(x_n,x^*)&=\sum_{i=1}^{n-1}(x_{i+1}-x_i)x_i^{p-1} + x_1x^* \\&=\sum_{i=2}^{n}x_{i} x_{i-1}^{p-1}-\sum_{i=1}^{n-1}x_i^{p} + x_1x^* \\&=x_nx_{n-1}^{p-1}-(p-1)\sum_{i=1}^{n-1}(x_{i+1}-x_i)x_i^{p-1} \\&=x_nx_{n-1}^{p-1}-(p-1)\left[F_{\partial f,n}(x_n,x^*)-x_1x^*\right] \end{aligned} $$ Therefore, $$ \begin{aligned} F_{\partial f,n}(x,x^*) =\frac{x}{p}x_{n-1}^{p-1}+\frac{x^*}{q}x_1 \end{aligned} $$ Let us define $w:= r_{n-1}$. Then, by the FOCs we get that $r_{i-1}^{1-p}=1+(1-p) (r_i-1)$ and $r_{i-1}=\Phi_p(r_i)$, i.e. $r_{n-k}=\Phi_p^{k-1}(w)$. Hence, the original $n-1$ variables collapse into a single parameter $w>0$ with the endpoints linked by: $$ x_{n-1}=\frac{x}{w},\quad x_1=\Phi_p^{n-1}(w) (x^*)^{1/(p-1)} $$ Therefore, we can rewrite the Fitzpatrick objective as a single parameter optimization problem: $$ F_{\partial f,n}(x,x^*) = \inf_{w>0} \left[ \frac{x^p}{p}w^{1-p}+\frac{(x^*)^q}{q}\Phi_p^{n-1}(w)\right]= \inf_{w>0} \left[ f(x)w^{1-p}+f^*(x^*)\Phi_p^{n-1}(w)\right] $$ Notice that the objective function in (35) is a strictly convex function. Further, the FOCs from above can be summarized into one equation: $$ \Phi^{n-1}_p(w)(x^*)^{1/(p-1)} = x_1=\frac{x}{r_{n-1}\cdots r_1}=\frac{x}{\prod_{0\le i\le n-2} \Phi^{i}(w)} $$ i.e., $\prod_{0\le i\le n-1} \Phi^{i}(w)=x(x^*)^{1/(1-p)}$. We show that this coincides with the FOC of the single parameter objective function. Let $g(w):=f(x)w^{1-p}+f^*(x^*)\Phi_p^{n-1}(w)$. Then, we first have that: $$ \Phi'_p(w)=(1+(p-1)(w-1))^{p / (1-p)} =\Phi_p(w)^p $$Therefore, $(\Phi^n_p)'(w) = \prod_{i=1}^{n}\Phi_p^i(w)^p$ and the FOC gives: $$ xw^{-1}=(x^*)^{1/(p-1)}\prod_{i=1}^{n-1}\Phi_p^i(w) $$Lastly, we have that by substituting $v:=1+\ln_p w=1+\frac{w^{1-p}-1}{1-p}$: $$ \begin{aligned} F_{\partial f,n}(x,x^*) &= \inf_{w>0} \left[ f(x)w^{1-p}+f^*(x^*)\Phi_p^{n-1}(w)\right] \\&= \inf_{v} \left[ f(x)(1+(1-p)(v-1))+f^*(x^*)\Phi_p^{n}(v)\right] \\&= \inf_{v} \left[ f(x)-\frac{x^p}{q}(v-1)+f^*(x^*)\Phi_p^{n}(v)\right] \\&= \inf_{v} \left[ f(x)-f^*(\nabla f(x))(v-1)+f^*(x^*)\Phi_p^{n}(v)\right] \\&= f(x)+f^*(\nabla f(x))+\inf_{v} \left[ -f^*(\nabla f(x)) v +f^*(x^*)\Phi_p^{n}(v)\right] \\&= f(x)+f^*(\nabla f(x)) - H^*_n(f^*(\nabla f(x))) \end{aligned} $$
□
Norm
Let $X$ be a real Hilbert space and $f:=\|\cdot\|$. Then, $f$ is proper, convex, and l.s.c. with the subdifferential given by: $$ \partial f(x) =\begin{cases}\{x/\|x\|\} & x\ne 0 \\ B_{\le 1}(0) & x=0\end{cases} $$ where $B_{\le 1}(0)$ is the unit ball. Further, the convex conjugate is given by $f^*=\iota_{B_{\le 1}(0)}$.Let $f:=\|\cdot\|$ be a norm. Then, for $n\ge 2$, we have: $$ F_{\partial f,n}(x,x^*) =f(x)+f^*(x^*)=\|x\|+\iota_{B_{\le 1}(0)}(x^*) $$
Let $h$ be the Fitzpatrick objective function. Let $(x_i,x_i^*)\in \operatorname{gra} \partial f$ for all $i\in[n-1]$. We have the two cases:
- Let $\|x^*\|>1$ Then, let $u:=x^* / \|x^*\|$ and $t>0$. We have that: $$ h((tu,u),...,(tu,u))=\langle x-tu,u\rangle+t\|x^*\|=\langle x,u\rangle+t(\|x^*\|-1) $$Hence, $F_{\partial f,n}(x,x^*) = +\infty$.
- If $\|x^*\|\le 1$, by the definition of subgradient and Cauchy-Schwarz, we have that: $$ \begin{aligned} h((x_1,x_1^*),...,(x_{n-1},x_{n-1}^*))&= \sum_{i=1}^{n-1}\langle x_{i+1}-x_i,x_i^*\rangle +\langle x_1,x^*\rangle \\ &\le \sum_{i=1}^{n-1}\|x_{i+1}\|-\|x_i\| +\|x_1\|\|x^*\| \\& =\|x\|+\|x_1\|(\|x^*\|-1) \\&\le \|x\| \end{aligned} $$ Hence, $F_{\partial f,n}(x,x^*)\le \|x\|$. For the other direction, we can choose $x_1=\cdots =x_{n-1}=0$ and $x_{n-1}^*=x/\|x\|$ and $x_{i}^*=0$ for everything else. Then, indeed: $F_{\partial f,n}(x,x^*)\ge \|x\|$.
□
Negative Logarithm
Negative logarithm Consider the negative logarithm function defined as:$$ f:\mathbb{R}\to (-\infty,\infty],\quad x\mapsto \begin{cases} +\infty &x\le 0 \\-\ln x&x >0\end{cases} $$ Then, $\partial f(x)=\{-1 /x\}$ for $x>0$ and the conjugate is given by: $$ f^*(x^*)=\begin{cases}-1-\ln (-x^*) & x^* < 0 \\ +\infty & x^* \ge 0\end{cases} $$Let $f$ be the negative logarithm function. Then, for $n\ge 2$, we have: $$ F_{\partial f,n}(x,x^*) =\begin{cases}n(1-(-xx^*)^{1/n}) - 1 & x\ge 0, x^*\le 0 \\ +\infty & \text{otherwise}\end{cases} $$
By Theorem 2.2, we have that $\mathbb{R}_{>0}\times \mathbb{R}_{< 0} \subseteq \operatorname{dom} F_{\partial f,n}\subseteq \mathbb{R}_{\ge 0}\times \mathbb{R}_{\le 0}$. Let $x\ge 0$ and $x^*\le 0$. We have the following cases:
- If $x=0$, the Fitzpatrick objective function $h$ simplifies to: $$ h(x_1, \dots, x_{n-1}) = x_1 x^* - \sum_{i=1}^{n-2} \frac{x_{i+1}}{x_i} - \frac{0}{x_{n-1}} + (n-1) = x_1 x^* - \sum_{i=1}^{n-2} \frac{x_{i+1}}{x_i} + (n-1) $$ Since we want the supremum of $h$ subject to $x_1, \dots, x_{n-1} > 0$ and we are given $x^* \le 0$, we can choose $x_1 = \epsilon$ and $x_{i+1}/x_i = \epsilon$ for $i=1, \dots, n-2$. As $\epsilon \to 0^+$, we have $x_1 x^* = \epsilon x^* \to 0$ and $\sum_{i=1}^{n-2} \epsilon = (n-2)\epsilon \to 0$. Because the subtracted terms are strictly positive, the supremum is exactly $n-1$.
- If $x^*=0$, the Fitzpatrick objective function $h$ becomes: $$ h(x_1, \dots, x_{n-1}) = 0 - \sum_{i=1}^{n-1} \frac{x_{i+1}}{x_i} + (n-1) $$ To maximize this, we must minimize the sum $\sum_{i=1}^{n-1} \frac{x_{i+1}}{x_i}$. Let $x_{i+1}/x_i = \epsilon$ for $i=1, \dots, n-1$. Since $x_n = x$, this requires choosing $x_1 = x / \epsilon^{n-1} > 0$. As $\epsilon \to 0^+$, the sum becomes $(n-1)\epsilon \to 0$. Thus, the supremum is again $n-1$.
- Now, assume that $x>0$ and $x^* < 0$. Let $x_n:= x$. Further, let $h$ be the objective function in the Fitzpatrick definition. Then, we have that the FOC's are given as below: $$ \begin{aligned} \frac{x_{i+1}}{x_i}&=\frac{x_i}{x_{i-1}},\quad i=1,\ldots,n-2,\\ -\frac{x_2}{x_1}&=x_1x^* \end{aligned} $$ By defining $r_i:= x_{i+1} / x_i$, we have that $r_i=r_{i-1}$ and $r_1=-x_1x^*$. $$ \begin{aligned} F_{\partial f,n}(x_n,x^*) &=x_1x^*-\sum_{i=1}^{n-1}(r_i -1) =(n-1) - \sum_{i=1}^{n-1} r_i + x_1x^* =(n-1) + nx_1x^* \end{aligned} $$ Then, $(-x_1x^*)^n=(-x_1x^*)\prod_{i=1}^{n-1}r_i=(-x_1x^*)\frac{x}{x_1}=-xx^*$ and: $$ F_{\partial f,n}(x_n,x^*)=(n-1) - n(-xx^*)^{1/n} = n(1-(-xx^*)^{1/n}) - 1 $$
□
Exponential Function
Consider the exponential function $f(x)=\exp(x)$. Then, $\partial f(x)=\{\exp(x)\}$ and the conjugate is given by the negative entropy function.Let $f$ be the exponential function and $\Psi(w):=-\ln(1-w)$. Then, for $n\ge 2$, we have: $$ F_{\partial f,n}(x,x^*) =f(x)+f^*(x^*)-H^*_n(f(x)) $$ where $H_n(v):=\Psi^n(v)x^*$ with $\Psi^n$ denoting the $n$-th iterate of $\Psi$.
By Theorem 2.2, $\operatorname{dom} F_{\partial f,n} = \mathbb{R} \times \mathbb{R}_{\ge 0} $ for all $n \ge 2$.
We first rewrite the Fitzpatrick objective as a one-parameter optimization problem: Let $h$ be the objective function in the Fitzpatrick definition. Then, we have that the FOC's are given as below: $$ \begin{aligned} e^{x_{i-1}-x_i}&=1-(x_{i+1}-x_i),\quad i=2,\ldots,n-1\\ x^*e^{-x_1}&=1-(x_2-x_1) \end{aligned} $$
By defining $r_i:= x_{i+1} - x_i$, we have that $r_{i-1}=\Psi(r_{i})$ and $r_1=1-x^*e^{-x_1}$. Therefore, $$ \begin{aligned} F_{\partial f,n}(x_n,x^*)&=\sum_{i=1}^{n-1}(x_{i+1}-x_i)e^{x_i} + x_1x^* \\&=\sum_{i=2}^{n-1}(1-e^{x_{i-1}-x_i})e^{x_i}+(1-x^*e^{-x_1})e^{x_1}+x_1x^* \\&=\sum_{i=2}^{n-1}(e^{x_i}-e^{x_{i-1}})+(e^{x_1}-x^*)+x_1x^* \\&=e^{x_{n-1}}+(x_1-1)x^* \end{aligned} $$ Let us define $w:= r_{n-1}$. Then, by the FOCs we get that $r_{n-k}=\Psi^{k-1}(w)$. Hence, the original $n-1$ variables collapse into a single parameter $w>0$ with the endpoints linked by: $$ x_{n-1}=x-w,\quad x_1=\Psi^{n-1}(w) +\ln (x^*) $$ Hence, we can rewrite the Fitzpatrick objective as a single parameter optimization problem: $$ \begin{aligned} F_{\partial f,n}(x,x^*) &= \inf_{w>0} \left[ e^{x-w}+x^*\Psi^{n-1}(w) + x^*\ln (x^*) - x^*\right] \\&= \inf_{w>0} \left[ f(x)e^{-w}+f^*(x^*) + x^*\Psi^{n-1}(w)\right] \end{aligned} $$ The FOC of this single parameter optimization problem is given by: $$ e^{x-w}=x^*\exp\left(\sum_{i=1}^{n-1}\Psi^{i}(w)\right) $$ which coincides with the FOCs given by the original $n-1$ parameter optimization problem. Indeed, we have that: $$ \Psi^{n-1}(w) +\ln (x^*) = x_1=x-\sum_{0\le i \le n-2}\Psi^i(w) $$ i.e., $\sum_{0\le i\le n-1} \Psi^{i}(w)=x -\ln (x^*)$.
Therefore, we have that by substituting $v:=1-e^{-w}$: $$ \begin{aligned} F_{\partial f,n}(x,x^*) &= \inf_{w>0} \left[ f(x)e^{-w}+f^*(x^*) + x^*\Psi^{n-1}(w)\right] \\&= \inf_{v\in (0,1)} \left[ f(x)(1-v)+f^*(x^*) + x^*\Psi^{n}(v)\right] \\&= f(x)+f^*(x^*) - \sup_{v\in (0,1)} \left[ f(x)v - x^*\Psi^{n}(v)\right] \\&= f(x)+f^*(x^*) - \sup_{v} \left[ f(x)v - x^*\Psi^{n}(v)\right] \\&= f(x)+f^*(x^*) - H^*_n(f(x)) \end{aligned} $$
□
Let $f$ be the negative entropy and $\Psi(w):=-\ln(1-w)$. Then, for $n\ge 2$, we have: $$ F_{\partial f,n}(x,x^*) =f(x)+f^*(x^*)-H^*_n(f^*(x^*)) $$ where $H_n(v):=\Psi^n(v)x$ with $\Psi^n$ denoting the $n$-th iterate of $\Psi$. In other words, the Fitzpatrick gap is given by: $$ \Delta_{f,n}(x,x^*)=H^*_n(f^*(x^*)) $$
Let $f$ be the negative entropy. Then, $f^* =\exp$ and: $$ F_{\partial f,n}(x,x^*) = F_{\partial f^*,n}(x^*,x)=f(x)+f^*(x^*) -H^*_n(f^*(x^*)) $$where $H_n(v):=\Psi^n(v)x$ and $\Psi(v):=-\ln(1-v)$.
□
Convergence Rate of Fitzpatrick Functions
In this section, we analyze the convergence rate of the Fitzpatrick gap $\Delta_{f,n}(x,x^*)$ as $n\to \infty$.Convergence Rate of Negative Entropy Fitzpatrick Functions
Let $f$ be the negative entropy. Then, for the Fitzpatrick gap $\Delta_{f,n}(x,x^*)$, we have that: $$ \lim_{n\to \infty} n\Delta_{f,n}(x,x^*) = \frac{\rho(x,e^{x^*})^2}{2} $$where $\rho(x,x_0):=\int_{x_0}^x\sqrt{f''(t)}dt$ is the Fisher-Rao distance between $x$ and $x_0$. In other words, the Fitzpatrick functions converge at a rate of $O(1/n)$.
Notice that $\Psi(v):=-\ln(1-v)$ has a fixed point at $v=0$ with $\Psi'(0) = 1$. Then, by Taylor expansion, $\Psi(v)=v+v^2/2+O(v^3)$ and around $0$: $$ \frac{1}{\Psi(v)}=\frac{1}{v(1+v/2+O(v^2))}=\frac{1}{v}\left(1-\frac{v}{2}+O(v^2)\right)=\frac{1}{v}-\frac{1}{2}+O(v) $$Telescoping, we get that $$ \begin{aligned} \frac{1}{\Psi^n(v)}-\frac{1}{v} &=\sum_{i=1}^n\left(\frac{1}{\Psi^i(v)}-\frac{1}{\Psi^{i-1}(v)}\right) \\&=\sum_{i=1}^n\left(\frac{1}{\Psi(\Psi^{i-1}(v))}-\frac{1}{\Psi^{i-1}(v)}\right) \\&=\sum_{i=1}^n\left[-\frac{1}{2}+O(\Psi^{i-1}(v))\right] =\frac{1}{v}-\frac{n}{2}+O(1) \end{aligned} $$ $\frac{1}{\Psi^n(v)}=\frac{1}{v}-\frac{n}{2}+O(1)$. Now, $$ \begin{aligned} n\Delta_{f,n}(x,x^*) &= \sup_{v}\left[ ne^{x^*}v - nx\Psi^n(v)\right] \\&= \sup_{\lambda}\left[\lambda e^{x^*} - nx\Psi^n(\lambda / n)\right] \\&= \sup_{\lambda}\left[\lambda e^{x^*} - x \frac{2\lambda}{(2-\lambda)}\right]+O(n^{-1}) \end{aligned} $$ where $\Psi^n(\lambda / n) = \frac{1}{n( (2-\lambda)/2\lambda)+O(1)}=\frac{2\lambda}{n(2-\lambda)}+O(n^{-2})$. By differentiating, we have: $$ e^{x^*}=x\frac{2(2-\lambda)+2\lambda}{(2-\lambda)^2}=\frac{4x}{(2-\lambda)^2} $$ With $\gamma := \sqrt{x / e^{x^*}}$, we get $\lambda = 2(1-\gamma)$ and plugging back: $$ \begin{aligned} \lim_{n\to \infty} n\Delta _n(x,x^*) &= 2(1-\gamma)e^{x^*} - 2x\left(\frac{1}{\gamma}-1\right) \\&=2(e^{x^*}-\sqrt{xe^{x^*}})-2(\sqrt{xe^{x^*}}-x) \\&=2(x-2\sqrt{xe^{x^*}}+e^{x^*}) \\&=2(\sqrt{x}-\sqrt{e^{x^*}})^2 \\&=\rho (x,e^{x^*})^2 / 2 \end{aligned} $$ where we have that: $$ \rho(x,x_0):=\int_{x_0}^x\sqrt{f''(t)}dt=\int_{x_0}^x \frac{1}{\sqrt{t}}dt=2(\sqrt{x}-\sqrt{x_0}) $$
□
General Convergence Rate
Let $f:\Omega\subseteq \mathbb{R} \to \mathbb{R}$ be a proper, convex, and l.s.c. function with $f\in C^2(\Omega)$. For any two points $x,x_0\in \Omega$ and the interval $I:=[x_0,x]$, if there exists $\mu,L>0$ s.t. $\mu\le f''(t)\le L$ for all $t\in I$, then, for the Fitzpatrick gap $\Delta_{f,n}(x,\nabla f(x_0))$, we have that: $$ \lim_{n\to \infty} n \Delta_{f,n}(x, f'(x_0)) = \frac{\rho(x,x_0)^2}{2} $$ where $\rho(x,x_0):=\int_{x_0}^x\sqrt{f''(t)}dt$ is the Fisher-Rao distance between $x$ and $x_0$.
By Theorem 2.1, we have that $\Delta_{f,n}(x_n,x^*_0)=\inf \sum_{i=0}^{n-1} d_f(x_{i+1},x_i^*)$. Notice that for $0\le i< n$, $x_i^*=f'(x_i)$ and by Fenchel-Young: $$ \begin{aligned} d_f(x_{i+1},x_i^*) &=f(x_{i+1})+f^*(f'(x_i))-x_{i+1}f'(x_i) \\&=f(x_{i+1})+(x_i f'(x_i) - f(x_i))-x_{i+1}f'(x_i) \\&=f(x_{i+1})-f(x_i)- f'(x_i)(x_{i+1}-x_i) \\&=D_f(x_{i+1},x_{i}) \end{aligned} $$also known as the Bregman divergence. Then, by the mean-value form of Taylor's theorem, there exists some $\xi_i$ between $x_i$ and $x_{i+1}$ such that: $$ D_f(x_{i+1},x_i)=\frac{1}{2}f''(\xi_i)(x_{i+1}-x_i)^2 $$ Therefore, by taking the uniform chain $x_i:=x_0+i(x-x_0)/n$, we have: $$ \Delta_{f,n}(x_n,f'(x_0))\le \sum_{i=0}^{n-1} \frac{1}{2}f''(\xi_i)\frac{(x_n-x_0)^2}{n^2}\le \frac{L(x_n-x_0)^2}{2n} $$For the lower bound, for any chain $x_i$, using Cauchy-Schwarz, we have that: $$ \sum_{i=0}^{n-1}D_f(x_{i+1},x_i)\ge \frac{\mu}{2}\sum_{i=0}^{n-1} (x_{i+1}-x_i)^2\ge \frac{\mu}{2n}\left(\sum_{i=0}^{n-1} |x_{i+1}-x_i|\right)^2\ge \frac{\mu(x_n-x_0)^2}{2n} $$ where in the last inequality we used the triangle inequality. Therefore, we have that: $$ \frac{\mu(x_n-x_0)^2}{2n}\le \Delta_{f,n}(x_n,f'(x_0))\le \frac{L(x_n-x_0)^2}{2n} $$
Let $x_1,...,x_{n-1}$ be a chain s.t. $\sum_{i=0}^{n-1} D_f(x_{i+1},x_i)\le \Delta_{f,n}(x_n,f'(x_0))+\varepsilon$ for some $\varepsilon>0$. Then: $$ |x_{i+1}-x_i|\le \sqrt{\frac{L(x_n-x_0)^2}{\mu \cdot n}+\frac{2\varepsilon}{\mu}},\quad \forall i = 0,...,n-1 $$
We have from above that: $$ \begin{aligned} \frac{\mu}{2}|x_{i+1}-x_i|^2\le D_f(x_{i+1},x_i)\le \sum_{j=0}^{n-1} D_f(x_{j+1},x_j)\le \Delta_{f,n}(x_n,f'(x_0))+\varepsilon\le \frac{L(x_n-x_0)^2}{2n}+\varepsilon \end{aligned} $$
□
Now we aim to show Theorem 4.2.
Lower bound: As $f''$ is continuous on the compact interval $I$, by Heine-Cantor, $\sqrt{f''}$ is uniformly continuous on $I$. Let $\omega$ be a modulus of continuity for $\sqrt{f''}$ on $I$, i.e. for any $t_1,t_2\in I$, we have that $|\sqrt{f''(t_1)}-\sqrt{f''(t_2)}|\le \omega(|t_1-t_2|)$ and $\lim_{t\to 0^+}\omega(t)=0$.
Let now $x_1,...,x_{n-1}$ be any near-optimal chain, i.e. the Bregman sum gives $\sum_{i=0}^{n-1}D_f(x_{i+1},x_i)\le \Delta_{f,n}(x_n,f'(x_0))+1$. Let $S_n:=\sum_{i=0}^{n-1} \sqrt{f''(\xi_i)}|x_{i+1}-x_i|=\sum_{i=0}^{n-1} \left|\int_{x_i}^{x_{i+1}}\sqrt{f''(\xi_i)} dt\right|$ and $L_n:=\sum_{i=0}^{n-1} \left|\int_{x_i}^{x_{i+1}}\sqrt{f''(t)}dt\right|$. Then, $$ \begin{aligned} |L_n-S_n| &\le \sum_{i=0}^{n-1}\int_{x_i}^{x_{i+1}}\left|\sqrt{f''(t)}-\sqrt{f''(\xi_i)}\right|dt \le \sum_{i=0}^{n-1}\int_{x_i}^{x_{i+1}}\omega(\delta_n)dt \le \omega(\delta_n)|x_{0}-x_n| \end{aligned} $$where $\delta_n:=\max_i |x_{i+1}-x_i|$. By Corollary 4.3, we have that $\delta_n\le C /\sqrt{n}$ for some constant $C>0$ that doesn't depend on the specific chain. Therefore, by setting $\varepsilon_n=\omega(C/\sqrt{n})|x_n-x_0|$, we have that $|L_n-S_n|\le \varepsilon_n$ and $\lim_{n\to \infty}\varepsilon_n=0$. Then, we have that: $$ S_n\ge L_n-\varepsilon_n\ge \rho(x,x_0)-\varepsilon_n $$Further, using Cauchy-Schwarz, we have that: $$ \frac{(\rho(x,x_0)-\varepsilon_n)^2}{2}\le \frac{S_n^2}{2}\le \frac{\left(\sum_{i=0}^{n-1}\sqrt{f''(\xi_i)}|x_{i+1}-x_{i}|\right)^2}{2}\le {n\left(\sum_{i=0}^{n-1}D_f(x_{i+1},x_i)\right)} $$ As this holds for all near-optimal chains, it holds that $\frac{(\rho(x,x_0)-\varepsilon_n)^2}{2}\le n \Delta_{f,n}(x_n,f'(x_0))$.
Upper bound: Let $s:= \rho(x,x_0)$. We define the following arc $\gamma:[0,s]\to I$ s.t. $\gamma(0)=x_0$, $\gamma(s)=x$ and $\gamma'(t)=1/\sqrt{f''(\gamma(t))}$. This is well-defined as $0 < \mu\le f''(t)$ for all $t\in I$. Then, we define: $$ x_i:=\gamma(i s/n),\quad i=0,...,n $$ Similarly, to above we have that $f''(t)$ and $1/\sqrt{f''(t)}$ are continuous on $I$ and therefore uniformly continuous. Let $\omega$ be a modulus of continuity for $1/\sqrt{f''}$ on $I$. Then, we have that for $i=0,...,n-1$: $$ |x_{i+1}-x_i|=\left|\int_{is/n}^{(i+1)s/n}\frac{1}{\sqrt{f''(\gamma(t))}}dt\right|=\frac{s}{n\sqrt{f''(x_i)}}+\omega(s/n)\frac{s}{n} $$ Similar argument shows that $f''(\xi_i)=f''(x_i)+\varepsilon_n$ for $\varepsilon_n\to 0$ as $n\to \infty$. Therefore, we have that: $$ \begin{aligned} n\Delta_{f,n}(x_n,f'(x_0))&\le n\sum_{i=0}^{n-1}D_f(x_{i+1},x_i) \\&=\frac{n}{2}\sum_{i=0}^{n-1}(f''(x_i)+\varepsilon_n)\left(\frac{s}{n\sqrt{f''(x_i)}}+\omega(s/n)\frac{s}{n}\right)^2 \\&=\frac{n}{2}\sum_{i=0}^{n-1}\left[\frac{s^2}{n^2} + \frac{\varepsilon'_n}{n^2}\right] \\&=\frac{s^2}{2} + \frac{\varepsilon'_n}{2} \end{aligned} $$ for some $\varepsilon'_n\to 0$ as $n\to \infty$. This proves the bound.
Application: Mirror Descent
In this section, we investigate how our result can be applied, especially in mirror descent. The information geometry of mirror descent is well studied[4]. However, we show the connection between mirror descent and Fitzpatrick functions and show how our results above can lead to concrete statements about the algorithm.
Let $\phi$ be the convex objective with minimizer $x^*$. We also have a differentiable convex function $f:\mathbb{R}\to \mathbb{R}$, called a distance-generating function, which is $\alpha$-strongly convex. Then, the gradient $\nabla f$ is known as the mirror map. In the unconstrained case, each step of the mirror descent satisfies the following: $$ \nabla f(x_{k+1})=\nabla f(x_{k})-\eta_k \nabla \phi(x_{k}) $$where $\eta_k$ is the step size.
We now relate it back to Fitzpatrick functions via the following theorem:
Let $\Omega\subseteq \mathbb{R}$ be an open interval and $f\in C^2(\Omega)$ be a Legendre distance-generating function, satisfying $0 < \mu\le f''\le L$ on $\Omega$. Further, let $\phi:\Omega \to \mathbb{R}$ be a convex objective function that is $\ell$-smooth relative to $f$, i.e. $D_\phi\le \ell\cdot D_f$ on $\Omega \times \Omega$.
Let $\{x_k\}_k$ given by the mirror descent algorithm with constant step size $\eta\le 1 / \ell$, i.e. $$ \nabla f(x_{k+1})=\nabla f(x_{k})-\eta \nabla \phi(x_k) $$ Then, for any $m\ge 0$ and $N\ge 2$, we have that: $$ \phi(x_m)-\phi(x_{m+N})\ge \frac{1}{\eta}\Delta_{f,N}(x_m,\nabla f(x_{m+N}))\ge \frac{\rho_f(x_m,x_{m+N})^2}{2\eta N}(1-o(1)) $$
From relative smoothness, we have that: $$ \begin{aligned} \phi(x_{k})-\phi(x_{k+1}) &\ge \langle \nabla \phi(x_k),x_k-x_{k+1} \rangle - \ell \cdot D_f(x_{k+1},x_k) \\&\ge \frac{1}{\eta}\langle \nabla f(x_k)-\nabla f(x_{k+1}),x_k-x_{k+1} \rangle - \ell \cdot D_f(x_{k+1},x_k) \\&\ge \frac{1}{\eta}\left(D_f(x_k,x_{k+1})+D_f(x_{k+1},x_{k})\right) - \ell \cdot D_f(x_{k+1},x_k) \\&\ge \frac{1}{\eta}D_f(x_k,x_{k+1})+\left(\frac{1}{\eta} - \ell\right) D_f(x_{k+1},x_k) \\&\ge \frac{1}{\eta}D_f(x_k,x_{k+1}) \end{aligned} $$where in the last step we use that $\eta \le 1/\ell$ and that Bregman divergence is non-negative. Therefore, we get that: $$ \phi(x_m)+\phi(x_{m+N})\ge \frac{1}{\eta}\sum_{k=m}^{m+N-1} D_f(x_k,x_{k+1}) $$ Let now $w_k:=x_{m+N-k}$ and $w_k^*:=\nabla f(x_{m+N-k})$. Then, we get that: $$ \phi(x_m)+\phi(x_{m+N})\ge \frac{1}{\eta}\sum_{i=0}^{N-1} D_f(w_{i+1},w_{i})\ge \frac{1}{\eta} \Delta_{f,N}(x_m,\nabla f(x_{m+N})) $$ The statement then follows from Theorem 4.2.
□
References
- Bartz, S., Bauschke, H. H., Borwein, J. M., Reich, S., & Wang, X. (2007). Fitzpatrick functions, cyclic monotonicity and Rockafellar's antiderivative. Nonlinear Analysis: Theory, Methods & Applications, 66(5), 1198–1223. doi:10.1016/j.na.2006.01.013
- Rockafellar, R. T. (1970). On the maximal monotonicity of subdifferential mappings. Pacific Journal of Mathematics, 33(1), 209–216.
- Bauschke, H. H., McLaren, D. A., & Sendov, H. S. (2006). Fitzpatrick functions: Inequalities, examples, and remarks on a problem by S. Fitzpatrick. Journal of Convex Analysis, 13, 499–523.
- Raskutti, G., & Mukherjee, S. (2014). The information geometry of mirror descent. arXiv preprint arXiv:1310.7780. arXiv:1310.7780