¿Converge el descenso del gradiente en los problemas de optimización convexa? Si es así, ¿cómo?

Question

Perdone de antemano si esta pregunta suena demasiado amplia o demasiado obvia.

Sé con certeza que el descenso por gradiente, es decir, la ecuación de actualización

$x_{k+1} = x_k - \epsilon_k \nabla f(x_k)$

convergen al minimizador único de $f$ con dominio $\text{dom}(f) = \mathbb{R}^n$ siempre que $f$ es estrictamente o fuertemente convexo .

Sin embargo, no recordaba si converge a un minimizador en funciones convexas, y cómo logra esta convergencia.

Lo que me preocupa es que

1. He visto algunos resultados contradictorios en los que en lugar de $x_k$ una secuencia promediada $\hat x_{k} = \frac{1}{K} \sum_k x_k$ converge.

2. También he visto resultados contradictorios en los que el tamaño del paso disminuye $o(1/k)$ vs es constante.

3. También está la cuestión de la convergencia débil frente a la fuerte. No estoy seguro de lo que esto significa exactamente.

He conocido algunos resultados pero son para funciones cuadráticas, no para funciones convexas en general.

¿Alguien puede opinar sobre cómo es este resultado básico en la optimización?

Answer 1

En https://stanford.edu/~boyd/papers/pdf/monotone_primer.pdf En la sección 5, subsección "Método del gradiente" o "Método del paso adelante" se muestra una prueba para funciones que son fuertemente convexas con gradiente de Lipschitz, utilizando tamaños de paso constantes.

Si la función es convexa con gradiente Lipschitz entonces https://www.stat.cmu.edu/~ryantibs/convexopt-F13/scribes/lec6.pdf muestra una prueba de convergencia con tamaños de paso constantes.

Para funciones estrictamente convexas (no Lipschitz), el descenso del gradiente no convergerá con tamaños de paso constantes. Pruebe este ejemplo muy sencillo, deje que $f(x) = x^{4}$ . Verás que no hay un tamaño de paso constante para el descenso de gradiente que converja a $0$ (para cualquier condición inicial). En este caso, la gente utiliza tamaños de paso decrecientes. Nunca he visto resultados sobre la convergencia de la media, pero podría ser lo que ocurre cuando se utiliza un tamaño de paso constante en funciones que son estrictamente convexas y no tienen gradiente de Lipschitz.

A menos que $x$ vive en un espacio de dimensiones infinitas, la convergencia débil y fuerte es la misma y no me preocuparía por ello. Aquí está la lectura adicional si usted es interesante, https://people.maths.bris.ac.uk/~mazag/fa17/lecture9.pdf