1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ It is optimal. Take $h=-g$. $\endgroup$ – Severin Schraven Nov 4 '18 at 20:29
  • $\begingroup$ @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$ $\endgroup$ – mortal Nov 4 '18 at 20:31
  • $\begingroup$ $g(x) = \lambda x$, $h(x) = -\mu x$? $\endgroup$ – LinAlg Nov 4 '18 at 22:52
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ sorry I still could not understand your answer. So you take $h:= f-g$ in your proof means $f:=g-h$ in my case? $\endgroup$ – mortal Nov 12 '18 at 12:05

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.