¿Por qué los métodos de convergencia SGD de segundo orden son impopulares para el aprendizaje profundo?

Question

Parece que, especialmente para el aprendizaje profundo, están dominando métodos muy simples para optimizar la convergencia SGD como ADAM - buena visión general: http://ruder.io/optimizing-gradient-descent/

En trazar sólo una dirección - descartando la información sobre los restantes, se no intente estimar la distancia desde un extremo cercano - que sugiere la evolución del gradiente ( $\rightarrow 0$ en extremum), y podría ayudar en la elección crucial del tamaño del paso.

Ambas oportunidades perdidas podrían ser explotadas por métodos de segundo orden - tratando de modelar localmente la parábola en múltiples direcciones simultáneamente (no todas, sólo unas pocas), por ejemplo, cerca de la silla de montar atrayendo en algunas direcciones, repulsando en las otras. He aquí algunos:

• L-BFGS: http://aria42.com/blog/2014/12/understanding-lbfgs
• TONGA: https://papers.nips.cc/paper/3234-topmoumoute-online-natural-gradient-algorithm
• K-FAC: https://arxiv.org/pdf/1503.05671.pdf
• Newton sin silla: https://arxiv.org/pdf/1406.2572
• mi parametrización local de segundo orden: https://arxiv.org/pdf/1901.11457

Pero siguen dominando los métodos de primer orden (?), he oído opiniones de que los de segundo orden no funcionan para el aprendizaje profundo (?)

Existen principalmente 3 retos (¿alguno más?): Hessiano inverso , estocasticidad de gradientes, y el manejo sillines . Todos ellos deben resolverse si localmente modelado parametrización como parábolas en algunas direcciones prometedoras (me gustaría usar): actualizar esta parametrización basada en gradientes calculados, y realizar paso adecuado basado en esta parametrización. De esta manera los extremos pueden estar en los parámetros actualizados - no hay inversión Hessiana, la evolución lenta de la parametrización permite acumular tendencias estadísticas de los gradientes, podemos modelar ambas curvaturas cerca de los sillines: correspondientemente atraer o repeler, con fuerza dependiendo de la distancia modelada.

¿Deberíamos ir hacia métodos de segundo orden para el aprendizaje profundo?

¿Por qué es tan difícil hacer que tengan más éxito que los simples métodos de primer orden? identificar estos retos ... resolverlos?

Como hay muchas formas de realizar métodos de segundo orden, ¿cuál parece la más prometedora?

Puesta al día: Visión general de los métodos de convergencia SGD, incluido el 2º orden: https://www.dropbox.com/s/54v8cwqyp7uvddk/SGD.pdf

Actualización: Se critican los grandes métodos de 2º orden, pero podemos trabajar en el extremo opuesto del espectro de costes: dar pequeños pasos a partir de métodos de 1er orden que han tenido éxito, como el simplemente barato modelo de parábola en línea en una sola dirección, por ejemplo, del método del momento para una elección más inteligente del tamaño del paso - ¿existen enfoques interesantes para esta mejora de 2º orden de los métodos de 1er orden?

Answer 1

¿Deberíamos ir hacia métodos de segundo orden para el aprendizaje profundo?

TL;DR: No, especialmente ahora que el ritmo de la innovación se está ralentizando y vemos menos innovaciones arquitectónicas y más formas de entrenar lo que básicamente son copias de arquitecturas existentes, en conjuntos de datos más grandes (véase GPT-2 de OpenAI).

En primer lugar , sin llegar al segundo orden, cabe mencionar que en Deep Learning ni siquiera se utiliza el descenso de gradiente (mini-batch) en todo su potencial (es decir, no se realiza búsqueda lineal), porque el paso de optimización en la búsqueda lineal sería muy costoso.

Segundo Los métodos de segundo orden son:

• mucho más complejo, es decir, más difícil de implementar sin errores. Los sistemas de DL se están convirtiendo cada vez más en una pequeña parte de enormes conductos de procesamiento de datos. Introducir más complejidad y fragilidad en un sistema complejo sólo es sensato si los beneficios compensan ampliamente los riesgos. A continuación argumentaré que no es así.
• más difícil de optimizar para la computación distribuida en hardware heterogéneo, cada vez más frecuente. Vea cuánto trabajo ha sido necesario para que K-FAC funcione en sistemas distribuidos ( no heterogéneos), y los rendimientos siguen sin ser mejores que los de los mejores métodos de primer orden: https://arxiv.org/pdf/1811.12019.pdf . En cambio, si el simple hecho de pasar a la computación distribuida hace que mi método de primer orden sea tan rápido o más que los métodos de segundo orden, no veo la razón para utilizar un algoritmo de optimización más complicado.
• mucho más caro en términos de iteración coste (número no) y ocupación de memoria, por lo que introducen una sobrecarga considerable. Las arquitecturas actuales (GPU) están más ligadas a la memoria que al cálculo. Como se explica muy bien aquí El aumento del coste de iteración y de la ocupación de memoria es más pronunciado cuanto mayor es la dimensión del problema. La optimización en Deep Learning es posiblemente uno de los más problemas de optimización de alta dimensión, por lo que no está claro que los métodos de segundo orden tengan una clara ventaja en términos de computación. tiempo (no el número de iteraciones, que no es lo que realmente nos importa) en relación con los métodos de primer orden.
• Otro problema de la optimización del aprendizaje profundo son los puntos de inflexión. Cada vez está más claro que los mínimos locales "malos" no son un problema en el aprendizaje profundo, pero los puntos de inflexión sí lo son. El método de Newton tiende a ser atraído por los puntos de silla de montar. . Si no recuerdo mal, los métodos de aproximación hessiana como K-FAC no tienen este problema, pero creo que la prueba depende del tipo de arquitectura, lo que hace que el uso de tales métodos sea frágil.
• no solucionan los problemas que hacen que los profesionales pierdan la mayor parte de su tiempo. Las unidades muertas o saturadas no se solucionan con K-FAC, sino con mejores esquemas de inicialización, así que en eso deberíamos centrarnos, por ejemplo, en Fixup: https://arxiv.org/abs/1901.09321
• otro problema con los métodos de segundo orden es que para la mayoría de las funciones de pérdida comunes, es fácil utilizar minilotes para obtener un estimador que converja al gradiente real. Es mucho más complicado construir un estimador basado en el muestreo para la aproximación a la inversa del hessiano. En otras palabras, los métodos de segundo orden introducen mucha complejidad y ocupación extra de memoria, pero estocástico los métodos de segundo orden introducen aún más complejidad. En contraste con la estocástica primer pedido donde el algoritmo es sólo ligeramente más complicado que el de los métodos deterministas de primer orden.
• por último, tienen muchas piezas móviles, que son difíciles de afinar de la mejor manera. Tu mismo artículo deja muchos detalles por especificar. ¿Necesitamos aún más hiperparámetros extra, o necesitamos métodos de optimización robustos? Ten en cuenta que en Deep Learning, como explica muy bien Shai Shalev-Shwartz, cuando algo va mal, es muy difícil entender cómo arreglarlo https://www.youtube.com/watch?v=1nvf_DBnsxo y más hiperparámetros no ayudan en ese sentido.

Answer 2

En realidad, esto está empezando a cambiar, ya que trabajos recientes están demostrando las ventajas de los métodos de segundo orden, especialmente para los problemas de PNL. Algunos ejemplos son:

1. " ADAHESSIAN: optimizador adaptativo de segundo orden para aprendizaje automático " Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, Michael W. Mahoney

2. " Optimización de segundo orden en la práctica " Rohan Anil, Vineet Gupta, Tomer Koren, Kevin Regan, Yoram Singer

Ha habido una noción incorrecta de que los métodos de segundo orden son poco prácticos porque el coste de formar el hessiano es $O(N^2)$ o que el coste de la inversa del hessiano es $O(N^3)$ . De hecho, nunca se hace nada de esto explícitamente. En la práctica, se utilizan métodos de álgebra lineal aleatoria y aproximaciones libres de matrices que pueden proporcionar buenas aproximaciones al hessiano en $O(N)$ complejidad.

En la actualidad existen múltiples bibliotecas que permiten calcular el espectro hessiano de modelos de gran tamaño (incluso modelos de mil millones de parámetros) en tiempos razonables. A continuación se muestra nuestra implementación:

https://github.com/amirgholami/PyHessian

Actualización: Había una pregunta sobre cómo se puede utilizar el método de Newton sin formar explícitamente el hessiano ( $O(N^2)$ ) y aplicando explícitamente su coste inverso (O(N^3)). La respuesta es que se puede utilizar Gradiente Conjugado para calcular el paso Newton. Vamos a denotar gradiente con $g$ y el hessiano con $H$ . En el método de Newton la actualización de los parámetros $w$ es la siguiente:

$w^{new} = w^{old} - H^{-1}g$

La solución a $H^{-1}g$ puede calcularse resolviendo:

$H\Delta w = g$

Se trata de un sistema de ecuaciones lineales que puede resolverse con Gradiente Conjugado (para un PSD H). Afortunadamente, CG no requiere $H$ formarse explícitamente para encontrar $\Delta w=H^{-1}g$ . Sólo requiere la aplicación de $H$ a un vector dado que puede calcularse en $O(N)$ complejidad. En teoría, necesitará r iteraciones del CG para resolver exactamente las ecuaciones anteriores (donde r es el rango del hessiano). Sin embargo, en la práctica, suelen ser necesarias unas pocas iteraciones, a menos que se necesite precisión de máquina.

Esto se explicó con elegancia en el artículo de Perlmutter de 1994 (véase la sección 5.2):

3. " Multiplicación exacta rápida por el hessiano " BA Perlmutter

También para un análisis más profundo sugiero leer la sección 6 el siguiente documento:

4. " Métodos de optimización para el aprendizaje automático a gran escala " Leon Bottou, Frank E. Curtis, Jorge Nocedal