Lipschitz constant of difference of convex functions

Let $$\mathcal{H}$$ be a real Hilbert space and $$f:= g-h$$ where $$g, h \colon \mathcal{H} \to \mathbb{R}$$ are continuously differentiable and convex functions with $$\lambda-$$ and $$\mu-$$ Lipschitz continuous gradient, respectively.

It's not hard to show that $$f$$ is $$\left( \lambda + \mu \right) -$$ Lipschitz continuous gradient. I do not think that it is optimal but I'm not sure how to derive a better constant as well. My guess, it could be $$\max \left\lbrace \lambda , \mu \right\rbrace$$.

• It is optimal. Take $h=-g$. – Severin Schraven Nov 4 '18 at 20:29
• @SeverinSchraven thanks for pointing this out. In fact, I forgot the very important property that $g$ and $h$ are convex (as written in the title) that is, we can not take $h = -g$ – mortal Nov 4 '18 at 20:31
• $g(x) = \lambda x$, $h(x) = -\mu x$? – LinAlg Nov 4 '18 at 22:52

I think you can find it from the Hessian Matrix. I change a bit your notation to include the strong convexity as well. The following holds: $$\mu_f I \preceq \nabla^2 f(x) \preceq \lambda_f I, ~ and ~ \mu_g I \preceq \nabla^2 g(x) \preceq \mu_g I,$$ where $$\lambda$$ denotes the Lipschitz gradient constant and $$\mu$$ denotes the strong convexity constant. Thus, the Hessian of $$h=f-g$$ satisfies $$(\mu_f - \lambda_g)I \preceq \nabla^2 h(x) \preceq (\lambda_f - \mu_g) I \preceq \lambda_f I \preceq (\lambda_f+\lambda_g) I.$$ So your bound is too conservative as you said.
• sorry I still could not understand your answer. So you take $h:= f-g$ in your proof means $f:=g-h$ in my case? – mortal Nov 12 '18 at 12:05