1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is $\mathcal{X}$? Is it convex? Is it closed? Is it bounded? $\endgroup$ – uniquesolution Jan 9 '18 at 10:00
  • $\begingroup$ Yes, it is closed, convex, and bounded. $\endgroup$ – haydn_c Jan 9 '18 at 12:35
  • $\begingroup$ What inner product are you using? $\endgroup$ – Brian Borchers Jan 10 '18 at 5:27
  • $\begingroup$ 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. $\endgroup$ – haydn_c Jan 10 '18 at 5:51
  • $\begingroup$ So you want the inequality to hold for every inner product? I don't believe that will work even in the 2-norm case. $\endgroup$ – Brian Borchers Jan 10 '18 at 17:02
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.