La intuición detrás de los métodos acelerados de primer orden

Question

$ \newcommand { \prox }{ \operatorname {prox}}$ $ \newcommand { \argmin }{ \operatorname {argmin}}$

Supongamos que queremos resolver el siguiente problema de optimización convexa:

$ \min_ {x \in \mathbb {R}^n} g(x) + h(x)$

donde asumimos que $g(x)$ es convexo y diferenciable, $h(x)$ es convexo (aquí estoy tratando de ser lo menos específico posible). Entonces recuerde que el descenso de gradiente generalizado puede formularse de la siguiente manera:

Paso $0$ : elegir la inicial $x^{0} \in \mathbb {R}^n$

Paso $k: k \ge 1$ : $x^{(k)} = \prox_h (x^{(k-1)} - t_k \nabla g(x^{(k-1)}), t_k)$

donde $ \prox $ es un operador proximal definido como $ \prox_h (y,t) := \argmin \limits_ {x \in \mathbb {R}^n} h(x) + \frac {1}{2t} \|y-x\|^2$

Se sabe que si $ \nabla g(x)$ es Lipschitz continuo y el operador proximal puede ser evaluado, la tasa de convergencia de será $O(1/k)$ . Este resultado puede ser acelerado para lograr $O(1/k^2)$ .

Propuesto por primera vez por Nesterov en 1983 para las funciones lisas, la idea de la aceleración sigue siendo un tema de investigación activo (para las funciones no lisas, compuestas, etc.). No es fácil leer los trabajos de Nesterov (muy matemáticos), pero para comprender el concepto basta con mirar a ISTA (Algoritmos de retención iterativa) y FISTA (Algoritmos de retención rápida iterativa) aquí http://mechroom.technion.ac.il/~becka/papers/71654.pdf . En particular, mis preguntas a continuación se basarán en el ejemplo de FISTA:

En términos generales, la aceleración se logra introduciendo una secuencia de números más $y_k$ construido como una combinación lineal específica de $x_k$ y $x_{k-1}$ La función proximal opera entonces en $y_{k}$ en lugar de $x_k$ . En el caso de FISTA tenemos:

$t_{k+1} = \frac {1 + \sqrt {1 + 4t^2_k}}{2}$

$y_{k+1} = x_k + \frac {t_k - 1}{t_{k+1}}(x_k - x_{k-1})$

Tenga en cuenta, que la secuencia $t_k$ satisface $t^2_k = t^2_{k+1} - t_{k+1}$ esto se justifica en la prueba de la convergencia de este algoritmo.

¿Existe alguna forma intuitiva de explicar, interpretar tal enfoque? ¿Por qué una combinación tan específica funciona y aporta una mejora tan perceptible a la tasa de convergencia? ¿Podemos encontrar una forma intuitiva de interpretar $t$ ? Probablemente alguien está familiarizado con los trabajos de Nesterov y tiene más conocimiento que yo sobre otras razones por las que $t_k$ se da en esta forma en primer lugar?

Answer 1

Yo mismo me hice esta pregunta mientras trataba de entender los métodos acelerados, pregunté por ahí y un profesor me indicó este documento para que me ayudara a intuirlo: http://statweb.stanford.edu/~candes/papers/NIPS2014.pdf

Para resumir: Su et. al. toman el método del gradiente acelerado de Nesterov y toman el tamaño del paso como infinitesimalmente pequeño para derivar la siguiente EDO $$\ddot{X} + \frac{3}{t} \dot{X} + \nabla f(X) = 0$$ con condiciones iniciales $X(0) = x_0$ y $\dot{X}(0) = 0$ . Analizando esta EDO, podemos tener una mejor idea de lo que hace el método de gradiente acelerado de Nesterov. Espero que este recurso sea útil.

Answer 2

El profesor L. Vandenberghe, de la UCLA, ofrece aquí una breve interpretación http://www.seas.ucla.edu/~vandenbe/236C/lectures/fgrad.pdf

Diapositiva 5; aunque no es muy informativa, dada la falta de respuestas, voy a pensar que es una extrapolación.