Relation between local Lipschitz continuity constant and Lipschitz smoothness constant of a function.

18 Views Asked by At

Using local Lipschitz continuity of $f(\cdot)$:

\begin{align} f(\mathbf{a}) &\leq f(\mathbf{b})+ L_0 \lVert{\mathbf{a}-\mathbf{b}}\rVert \end{align}

In the FedProx Paper (https://arxiv.org/pdf/1812.06127.pdf, Equation 9 of the Theorem 4 proof (page no. 13), the authors have used a relation between local Lipschitz constant $L_0$ and the global L-smoothness constant L of f which satisfies the following inequality:

$$ L_0\leq \lVert{\nabla f(\mathbf{c})\rVert} + L* max( \lVert{(\mathbf{b} - \mathbf{c})}\rVert , \lVert{(\mathbf{a} - \mathbf{c})}\rVert)$$

To prove the same, I started out as following:

We start by considering the following result based on the Lipschitz smoothness assumption,

$$f(\mathbf{b}) \leq f(\mathbf{c}) + \langle \nabla f(\mathbf{c}), \mathbf{b} - \mathbf{c} \rangle + \frac{L}{2} \lVert{\mathbf{b} - \mathbf{c}}\rVert^2$$

Using the local Lipschitz continuity of $f(\cdot)$ at $\mathbf{b}$, $$f(\mathbf{a}) \leq f(\mathbf{b})+ L_0 \lVert{\mathbf{b}-\mathbf{c}\rVert} $$

Adding the above inequalities and applying local Lipschitz continuity again at $\mathbf{a}$, we get,

$$ f(\mathbf{c}) -f(\mathbf{a}) + \langle \nabla f(\mathbf{c}), \mathbf{a} - \mathbf{c} \rangle + \frac{L}{2} \lVert{\mathbf{b} - \mathbf{c}}\rVert^2 + L_0 \lVert{\mathbf{a}-\mathbf{b}}\rVert \geq 0 $$ $$ L_0 \lVert{\mathbf{c} - \mathbf{a}}\rVert + \langle \nabla f(\mathbf{c}), \mathbf{a} - \mathbf{c} \rangle + \frac{L}{2} \lVert{\mathbf{b} - \mathbf{c}}\rVert^2 + L_0 \lVert{\mathbf{a}-\mathbf{b}}\rVert \geq 0 $$

I am stuck after this. Is my approach correct or is there any other way to prove the same? Any help would be appreciated. Thanks in advance.