Suavidad Lipschitz, convexidad fuerte y el hessiano

Question

Estoy trabajando con los siguientes dos conceptos:

• Suavidad Lipschitz - una función $f$ es suave de Lipschitz con constante $L$ si sus derivadas son continuas de Lipschitz con constante $L$ En otras palabras, si para cualquier $x$ y $y$ , $$ \| \nabla f(x) - \nabla f(y) \| \leq L \| x - y \| $$
• Convexidad fuerte - una función $f$ es $\alpha$ -fuertemente convexo si $$ \nabla^2 f(x) \succeq \alpha I $$ para todos $x$ , donde $I$ es la matriz de identidad.

Estas son mis preguntas:

1. Sé que la suavidad de Lipschitz implica que para cualquier $x$ y $y$ es cierto que $$ f(x + y) \leq f(x) + y^\top \nabla f(x) + \frac{L}{2} \| y \|^2 $$ ¿Es también cierto lo contrario? Es decir, ¿es un "si y sólo si"?
2. He leído en alguna parte que $f$ es suave de Lipschitz si y sólo si $$ L I \succeq \nabla^2 f(x) $$ para todos $x$ , donde $I$ es la matriz identidad. ¿Cómo puedo demostrarlo?
3. He leído en alguna parte que $f$ es $\alpha$ -fuertemente convexo si y sólo si para cualquier $x$ y $y$ es cierto que $$ f(x+y) \leq f(x) + y^\top\nabla f(x) - \frac{\alpha}{2} \| x - y \| $$ ¿Cómo puedo probar esto, y es si y sólo si?
4. Los dos puntos anteriores parecen implicar alguna relación entre estos dos conceptos. ¿Se trata de algo más profundo?

Me doy cuenta de que esto es un montón de preguntas - si alguien tiene una buena referencia sobre estos temas, que sería genial también ...

Gracias

Answer 1

Supongo que su pregunta se refiere únicamente a las funciones convexas; sin la convexidad, muchas cosas serían falsas.

Pregunta 2 : en sentido estricto, al ser Lipschitz suave ( $C^{1,1}$ ) no implica $\nabla^2 f$ existe. Pero la afirmación es cierta si interpretamos $\nabla^2 f\preceq LI$ como la celebración de casi todo el mundo. De hecho, $\nabla^2 f$ es una matriz semidefinida positiva, por lo que al tener $\nabla^2 f\preceq LI$ a.e. es equivalente a $\nabla^2 f\in L^\infty$ . Y es bien sabido que tener $L^\infty$ es equivalente a ser Lipschitz; por lo tanto $$\nabla^2 f\in L^\infty \iff \nabla f\in C^{0,1} \iff f\in C^{1,1}$$

Pregunta 3 : Has recordado mal. La desigualdad correcta que caracteriza a $\alpha$ -La convexidad fuerte es $$f(x+y) \ge f(x) + y^\top\nabla f(x) + \frac{\alpha}{2} \| x - y \|^2 \tag{1}$$ En efecto, (1) equivale a decir que la función $g(x)=f(x)-\frac{\alpha}{2} \| x \|^2$ es convexo. Esto último equivale a $\nabla^2 g\succeq 0$ que es $\nabla^2 f\succeq \alpha\, I$ .

Pregunta 4 . Sí, hay una relación directa e importante: una función es fuertemente convexa si y sólo si su conjugado convexo (también conocida como transformación de Legendre-Fenchel) es suave como Lipschitz. En efecto, los mapas de gradientes son inversos entre sí, lo que implica que el hessiano del conjugado convexo de $f$ es la inversa del hessiano de $f$ (en un punto apropiado). Por lo tanto, un límite superior uniforme en $\nabla^2 f$ es equivalente a un límite inferior uniforme en $\nabla^2 (f^{*}) $ y viceversa. También se puede argumentar sin referirse al hessiano (que puede no existir en algunos puntos): la suavidad de Lipschitz de $f$ por su punto 1, nos da en cada $x_0$ una función cuadrática $q$ para que $q(x_0)=f(x_0)$ y $f \le q$ en todas partes. Tomando el conjugado convexo se invierte el orden: $q^*\le f^*$ y esto significa que $f^*$ es fuertemente convexo.

Pregunta 1 . Lo contrario es cierto, pero la única prueba que veo pasa por el conjugado convexo como se describe en Q4. Dado que la convexidad fuerte se caracteriza por la propiedad de comparación (1), tomando el conjugado se obtiene una caracterización coincidente de la suavidad de Lipschitz.

Referencia: Capítulo 5 de Funciones convexas por Jonathan M. Borwein y Jon D. Vanderwerff.

Answer 2

En cuanto a las referencias, el libro de Nesterov "Introductory Lectures on Convex Optimization" (ISBN: 978-1-4613-4691-3) responde al menos a tres de las cuatro preguntas planteadas aquí. Ecuaciones/teoremas específicos:

Pregunta 1 : Véase la ecuación (1.2.12) y sustitúyase "y" por "x+y".

Pregunta 2 : Teorema 2.1.6. con prueba adjunta.

Pregunta 3 : Como se mencionó en la respuesta anterior, la ecuación estaba ligeramente equivocada en la pregunta original. Pero si se corrige, esto se demuestra en el Teorema 2.1.11.