0
$\begingroup$

Let $f: \mathbb{R}^n \mapsto \mathbb{R}$ a convex a continuously differentiable function.

What is the relation between the component Lipschitz constants, i.e. the smallest constants $L_i$ such that for all $x \in \mathbb{R}^n$ and $t \in \mathbb{R}$: \begin{equation} |[\nabla f(x+te_i)]_i-[\nabla f(x)]_i| \leq L_i|t|, \end{equation} and the regular Lipschitz constant, i.e. the smallest constant $L$ such that for all $d \in \mathbb{R}^n$: \begin{equation} \|\nabla f(x+d)-\nabla f(x)\|_2 \leq L\|d\|_2? \end{equation}

It is mentioned it this paper that $1 \leq \frac{L}{L_{\text{max}}} \leq n$ where $L_{\text{max}} = \max_{i=1..n}L_i$, which comes from the "relationships between norm and trace of a symmetric matrix" (p.12). However I do not see where this result comes from, or which "symmetric matrix" the author refers to.

$\endgroup$
  • $\begingroup$ Notice that Lipschitz constants aren't unique. If $L$ is a Lipschitz constant then any $M> L$ is also a Lipschitz constant. So please be more specific about $L$ and $L_i$. $\endgroup$ – user251257 May 18 '18 at 19:09
0
$\begingroup$

Since $M=L\text{I} - \nabla^2 f \succeq 0$, all diagonal entries of $M$ must be non-negative. Thus, $L \geq L_{\max}$. The equality holds when, for example, $f(x)=\sum_{i=1}^n x_i^2.$

The second inequality comes from

$$ L \leq \sum_{i=1}^n \lambda_i = tr(\nabla^2 f) = \sum_{i=1}^n \partial^2 f_i \leq n L_{\max}. $$

When $f(x)= (\sum_{i=1}^n x_i)^2$, the equality holds.

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