1

I encountered the following claim regarding the strong convexity of Bregman divergence. Let $d$ be a sufficiently large integer. Let $p=1+1/\ln d\in (1,2]$ for sufficiently large $d$. For any $x,y\in\mathbb R^d_+$, define $D(x,y)$ as $$ D(x,y) := \frac{1}{p}\sum_{i=1}^d x_i^p - \sum_{i=1}^d x_i y_i^{p-1} + \left(1-\frac{1}{p}\right)\sum_{i=1}^d y_i^p. $$

Claim. There exists an absolute constant $0<c<\infty$ independent of $d$, such that for any $x,y\in\mathbb R_+^d$, $\|x\|_1,\|y\|_1\leq 1$, it holds that $$ D(x,y) \geq \frac{c}{\sqrt{\ln d}}\left[\sum_{i=1}^d |x_i-y_i|\right]^2. $$

Yining Wang
  • 1,279
  • 7
  • 23
  • So, rephrasing, you take $F\colon \mathbb{R}^d \to \mathbb{R}$ defined by $$ F(x) = \frac{1}{p}|x|_p^p $$ and are asking about whether the corresponding Bergman divergence $D_F$ satisfies $$ D_F(x,y) \geq c\sqrt{p-1} |x-y|_1^2 $$? Where did you see this/why do you think this holds? – Clement C. Feb 22 '21 at 04:23
  • 1
    I found this claim on the last page of this lecture note https://ocw.mit.edu/courses/mathematics/18-657-mathematics-of-machine-learning-fall-2015/lecture-notes/MIT18_657F15_L13.pdf – Yining Wang Feb 22 '21 at 21:21
  • Thank you! But doesn't that mean we have to prove the inequality with $\sqrt{\ln d}$, not $1/\sqrt{\ln d}$? – Clement C. Feb 22 '21 at 22:14
  • I see several references to Ball et al. (1994) (https://link.springer.com/article/10.1007/BF01231769) for related things; maybe worth having a look there? – Clement C. Feb 23 '21 at 00:47
  • @ClementC. Thank you for the reference. Yes, the claim in the lecture note is $\sqrt{\ln d }$ instead of $1/\sqrt{\ln d}$. I chose to state the latter which is weaker, and sufficient for my applications. – Yining Wang Feb 23 '21 at 23:33
  • This is a bit risky -- it is a weaker statement, but may throw people off and make paradoxically things harder to prove (since a statement can hint at how to obtain it). – Clement C. Feb 23 '21 at 23:51

1 Answers1

1

In fact, if $f(x) = \frac 1 2\|x\|_p^2$ with $p\in (1,2]$, then we always have that $f$ is $(p-1)$-strongly convex wrt to $\|\cdot\|_p$, that is $$D_f(x,y) \geq (p-1)\|x-y\|_p^2.$$

Proof.

The standard fact from duality says that $\mu$-strong convexity of $f$ wrt the primal norm $\|\cdot\|$ is equivalent to $\frac{1}{\mu}$-smoothness of the conjugate function $f^*$ wrt the dual norm $\|\cdot\|_*$. In other words, the following inequality must hold \begin{equation} f^*(u)\leq f^*(v) + \langle \nabla f^*(v),u-v\rangle + \frac{1}{2\mu}\|u-v\|_*^2. \end{equation} For twice differentiable $f^*$ it is equivalent to \begin{equation}\label{eq:2} \langle \nabla^2f^*(u)(v),v\rangle \leq \frac{1}{\mu} \|v\|_*^2 \end{equation} This equivalence follows from the Taylor formula.

In our case, $f(x) = \frac 12 \|x\|_p^2$ with $p\in (1,2]$. Then $f^*(u) = \frac 1 2\|u\|_q^2$ with $q=\frac{p}{p-1}\geq 2$, and hence $f^*$ is twice differentiable. Thus, in order to establish the desired, we must prove $$\langle \nabla^2f^*(u)v,v\rangle \leq \frac{1}{p-1} \|v\|_q^2.$$ This proof is a bit tedious, but overall it is just an application of the Hölder inequality. I refer to the paper A. Ben-Tal et al. "The ordered subsets mirror descent optimization method with applications to tomography" (see Appendix there).

cheyp
  • 385