# Inequality for smooth convex function defined in non Euclidean norm

Let $\mathcal{X}$ be a closed, convex and bounded set. Consider a convex function $f : \mathcal{X} \rightarrow \mathbb{R}$ that is differentiable with $L$ Lipschitz smooth gradient w.r.t a norm $\| \cdot \|$ that is not necessarily the Euclidean norm. Let $\| \cdot \|_*$ be the dual norm of $\|\cdot \|$, i.e., $\|x\|_* = \max \{ \langle x, u \rangle \mid \|u \| = 1\}$. For every $x, y \in \mathcal{X}$, does the following inequality hold?

$$f(x) - f(y) - \langle \nabla f(y), x - y \rangle \ge \frac{1}{2 L} \| \nabla f(x) - \nabla f(y) \|^2_* .$$

The above is true when $\|\cdot\|$ and $\|\cdot\|_*$ are both the Euclidean norm which can be found in many textbooks, however, I can't find any statement regarding the non-Euclidean case. The proof used for the Euclidean case doesn't seem to apply to the more general case.

• What is $\mathcal{X}$? Is it convex? Is it closed? Is it bounded? – uniquesolution Jan 9 '18 at 10:00
• Yes, it is closed, convex, and bounded. – haydn_c Jan 9 '18 at 12:35
• What inner product are you using? – Brian Borchers Jan 10 '18 at 5:27
• An inner product here is a function $\langle \cdot, \cdot \rangle : \mathcal{X}^* \times \mathcal{X} \rightarrow \mathbb{R}$ that satisfies the definitions of inner product, i.e., symmetry, linearity, and positive-definiteness. – haydn_c Jan 10 '18 at 5:51
• So you want the inequality to hold for every inner product? I don't believe that will work even in the 2-norm case. – Brian Borchers Jan 10 '18 at 17:02

After some research, I think the answer is yes. Since LHS is the Bregman divergence of $f$, let $f^*$ be the convex conjugate of $f$, we have $$D_f(x,y) = D_f^*(\nabla f(y), \nabla f(x)) \ge \frac{1}{2L} \| \nabla f(y) - \nabla f(x) \|_*^2,$$ where the first equality is due to the duality property of Bregman divergence (see https://en.wikipedia.org/wiki/Bregman_divergence), and the second inequality is due to the fact that $f$ is $L$-Lipschitz smooth if and only if $f^*$ is $\frac{1}{L}$-strongly convex. (see Theorem 1 of http://ttic.uchicago.edu/~shai/papers/KakadeShalevTewari09.pdf).