Cómo mostrar $\frac{1}{L}\|f(y)-f(x)\|_2^2 \leq \langle \nabla f(y) - \nabla f(x) ,y-x \rangle$ fuertemente convexa de la función?

Question

Supongamos $f: \mathbb{R}^n \rightarrow \mathbb{R}$ es fuertemente convexo de la función, es decir,

$$ \langle \nabla f(y) - \nabla f(x) ,y-x \rangle \geq \theta \|y-x\|_2^2 \,\,\,\,\, \forall x,y \in \mathbb{R}^n $$

o

$$ z^T(\nabla^2 f(x) -\theta I)z\geq 0 \,\,\,\,\forall z \neq 0 $$

También, supongamos $\nabla f(x)$ es una de Lipschitz con constante de Lipschitz $L>0$, es decir, $ \|\nabla f(y)- \nabla f(x)\|_2 \leq L \|y-x\|_2$.

Espectáculo $\frac{1}{L}\|\nabla f(y)-\nabla f(x)\|_2^2 \leq \langle \nabla f(y) - \nabla f(x) ,y-x \rangle$

Answer 1

Con el fin de obtener la conclusión de que sólo necesitamos la convexidad de $f(x)$ más que el fuerte convexidad. Es fácil demostrar que si $\nabla f(x)$ es Lipschitz continua con constante $L$ entonces tenemos:$$f(y)-f(x)-\langle\nabla f(x),y-x\rangle\leq\frac{L}{2}\| x-y\|^2$$ Para mostrar esta desigualdad, tenemos:\begin{align} f(y)-f(x)-\langle\nabla f(x),y-x\rangle&=\int_{0}^{1}\langle \nabla f(x+t(y-x)),y-x \rangle dt-\langle\nabla f(x),y-x\rangle \\ &=\int_{0}^{1}\langle \nabla f(x+t(y-x))-\nabla f(x),y-x \rangle dt \\ &\leq\int_0^1\|\nabla f(x+t(y-x))-\nabla f(x)\|\|y-x\| dt\\ &\leq\int_0^1Lt\|y-x \|^2dt=\frac{L}{2}\|y-x\|^2 \end{align}

Con el fin de obtener el resultado que debemos considerar la siguiente función de $$h(x)=f(x)-\langle \nabla f(y),x\rangle$$ Está claro que $h(x)$ es convexo y también a$\nabla h(x)$ es Lipschitz continua con constante $L$, y, por tanto, $y\in\arg\min_{x}h(x)$ porque $\nabla h(y)=0$. Tenemos:$$ h(x-\frac{1}{L}\nabla h(x))\geq h(y) $$ El uso de la primera desigualdad: $$ h(x-\frac{1}{L}\nabla h(x))\leq h(x)-\frac{1}{2L}\|\nabla h(x)\|^2 $$ Tenemos: $$ h(y)\leq h(x)-\frac{1}{2L}\|\nabla h(x) \|^2 $$ $$f(y)+\langle\nabla f(y),x-y\rangle\leq f(x)-\frac{1}{2L}\| \nabla f(x)-\nabla f(y)\|^2 $$ $$f(y)-f(x)+\langle\nabla f(y),x-y\rangle\leq -\frac{1}{2L}\| \nabla f(x)-\nabla f(y)\|^2$$ Exchange $x,y$: $$f(x)-f(y)+\langle\nabla f(x),y-x\rangle\leq -\frac{1}{2L}\| \nabla f(x)-\nabla f(y)\|^2$$ Añadirlos juntos, entonces usted puede obtener la conclusión.

Answer 2

Por definición de fuerte convexidad tenemos las siguientes:

\begin{equation} f(x) \geq f(y) + <\nabla f(y), x-y> + \frac{\sigma}{2} \left\lVert x-y\right\rVert^2 \end{equation}

De forma similar, tenemos:

\begin{equation} f(y) \geq f(x) + <\nabla f(x), y-x> + \frac{\sigma}{2} \left\lVert x-y\right\rVert^2 \end{equation}

Si la suma de estas dos desigualdades y organizarlos usted terminará con el siguiente:

\begin{equation} <\nabla f(y) - \nabla f(x), y-x> \geq \sigma.\left\lVert x-y\right\rVert^2 \end{equation}

Que es lo que tienes. Llamamos a esta función $\sigma$-fuertemente convexo. Para dar un ejemplo, "entropía negativa" es una 1-fuertemente convexa (también conocido como 1-SC) función wrt L1-norma que se utiliza como la regularización de plazo para hacer un no-función suave suave en L1-configuración (en el aprendizaje con expertos en la instalación)--por Favor, tenga en cuenta que en la L1-todo establecimiento es un simplex.

Además, puede utilizar "Hölder la desigualdad" para probar el caso general se muestra a continuación (no sólo de la norma 2):

\begin{equation} \left\lVert \nabla f(y) - \nabla f(x)\right\rVert_{\infty} \left\lVert x-y \right\rVert_{1} \geq <\nabla f(x) - \nabla f(y), x-y> \geq \sigma.\left\lVert x-y\right\rVert_{1}^2 \end{equation}