Bregman distances and variational source rates — Examples and Counterexamples

The function $R$ is finite and nonnegative, hence proper. For $u,v\in \mathbb{R}$ and $t\in [0,1]$, $R((1-t)u+tv)=\max \{(1-t)0+t0,(1-t)(-u)+t(-v)\}\le (1-t)\max \{0,-u\}+t\max \{0,-v\}$, so $R$ is convex. For every $z\in \mathbb{R}$, $R(z)\ge -z=R(0)+(-1)(z-0)$, so [F1] gives ${\xi }^{†}=-1\in \mathrm{\partial }R(0)$. By [F2], $D_R^{-1}(x,0)=R(x)+x$, which equals $x$ for $x\ge 0$ and $0$ for $x<0$. Since $F$ is zero, the source inequality has left side $x$ and right side $D_R^{-1}(x,0)$; it holds for all $x$, hence on $R(x)\le 1$, with boundary coefficient ${\beta }_1=1$.

For every $\delta >0$, $J_{\delta }(x)=\delta R(x)\ge 0$, and it equals zero for every $x\ge 0$. Thus $x_{\delta }=1$ is a global minimizer for every $\delta$, but $D_R^{-1}(1,0)=1$. No fixed constant bounds $1$ by $C\delta$ for all sufficiently small $\delta$, so the claimed rate fails.

For $q>0$, the function $s\mapsto A{s}^{\mu }-qs$ has derivative $A\mu s^{\mu -1}-q$, which decreases from $+\mathrm{\infty }$ to $-q$ and vanishes only at $s_q=(A\mu \mathrm{/}q{)}^{1\mathrm{/}(1-\mu )}$. The function is increasing before $s_q$ and decreasing after it, with value $0$ at $s=0$ and limit $-\mathrm{\infty }$ as $s\to \mathrm{\infty }$, so this point is its global maximizer. Substitution gives $H(q)=(1-\mu )A^{1\mathrm{/}(1-\mu )}{\mu }^{\mu \mathrm{/}(1-\mu )}{q}^{-\mu \mathrm{/}(1-\mu )}$.

With $q=c_p\mathrm{/}\alpha$ this gives $H(c_p\mathrm{/}\alpha )=C_{p,A,\mu }{\alpha }^{\mu \mathrm{/}(1-\mu )}$, so the chosen $\alpha$ yields $H(c_p\mathrm{/}\alpha )\asymp {\delta }^{p\mu }$ and $\alpha H(c_p\mathrm{/}\alpha )\asymp {\delta }^p$. Also $H(c_p\mathrm{/}(2\alpha ))=2^{\mu \mathrm{/}(1-\mu )}H(c_p\mathrm{/}\alpha )$, while $\psi (C_0{\delta }^p)=A{C}_0^{\mu }{\delta }^{p\mu }=O(H(c_p\mathrm{/}\alpha ))$ for every fixed $C_0>0$. Thus the parameter and penalty conditions in [F1] hold, and [F1] gives the stated Bregman and residual rates. Under the additional lower bound with $c_R,s>0$, division by $c_R$ gives $\mathrm{\parallel }{x}_{\alpha }^{\delta ,\epsilon }-x^{†}{\mathrm{\parallel }}_X^s=O({\delta }^{p\mu })$; taking the positive $s$-th root gives the norm rate.

For $0<t<t_0$, put $L=-\log t$. Differentiation gives ${\psi }^{\mathrm{\prime }}(t)=\nu \mathrm{/}(t{L}^{\nu +1})$ and ${\psi }^{\mathrm{\prime }\mathrm{\prime }}(t)=\nu ((\nu +1)-L)\mathrm{/}(t^2{L}^{\nu +2})<0$, since $L\ge -\log t_0>\nu +1$. Thus ${\psi }^{\mathrm{\prime }}$ decreases on $(0,t_0)$ and has positive left limit at $t_0$; after $t_0$ the function is constant, so its derivative drops to zero and remains nonincreasing. Also $\psi (t)\to 0$ as $t\downarrow 0$. Therefore its continuous extension at zero is nondecreasing, concave on $[0,\mathrm{\infty })$, vanishes at zero and is positive for $t>0$, as required by [F1].

For $q>{\psi }^{\mathrm{\prime }}(t_0-)$, the derivative of $s\mapsto \psi (s)-qs$ decreases from $+\mathrm{\infty }$ to a negative value on $(0,t_0)$ and is $-q<0$ for $s>t_0$. Hence the unique global maximizer is $s_q\in (0,t_0)$ satisfying $q=\nu \mathrm{/}(s_q{L}_q^{\nu +1})$, where $L_q=-\log s_q$. This equation gives $\log q=L_q-(\nu +1)\log L_q+\log \nu$, so $L_q\to \mathrm{\infty }$ and $L_q\mathrm{/}\log q\to 1$. At the maximizer, $q{s}_q=\nu L_q^{-\nu -1}$; consequently $H(q)=L_q^{-\nu }(1-\nu \mathrm{/}{L}_q)\sim (\log q{)}^{-\nu }$.

Set ${\mathrm{\ell }}_{\delta }=\log (1\mathrm{/}\delta )$. Then $\alpha (\delta )\to 0$ and $q_{\delta }=c_p\mathrm{/}\alpha (\delta )\to \mathrm{\infty }$, while $\log q_{\delta }=p{\mathrm{\ell }}_{\delta }-\nu \log {\mathrm{\ell }}_{\delta }+\log c_p\sim p{\mathrm{\ell }}_{\delta }$. By step 2.1, ${\rho }_{\delta }=H(q_{\delta })\asymp {\mathrm{\ell }}_{\delta }^{-\nu }$ and $\alpha {\rho }_{\delta }\asymp {\delta }^p$. Replacing $q_{\delta }$ by $q_{\delta }\mathrm{/}2$ changes its logarithm by only $-\log 2$, so $H(c_p\mathrm{/}(2\alpha ))\asymp {\rho }_{\delta }$. For any fixed $C_0>0$, eventually $C_0{\delta }^p<t_0$, and $\psi (C_0{\delta }^p)=(-\log (C_0{\delta }^p){)}^{-\nu }\asymp {\mathrm{\ell }}_{\delta }^{-\nu }\asymp {\rho }_{\delta }$. Thus all coupling and penalty-index hypotheses in [F3] hold; applying [F3] gives the three asserted rates. If the additional Bregman lower bound holds, its combination with the Bregman rate gives $\mathrm{\parallel }{x}_{\alpha }^{\delta ,\epsilon }-x^{†}{\mathrm{\parallel }}_X^s=O({\mathrm{\ell }}_{\delta }^{-\nu })$, and taking the positive $s$-th root proves the stated norm rate.