Convergencia del descenso gradiente estocástico en función del tamaño del conjunto de entrenamiento

Question

Estoy repasando el siguiente apartado del libro de (Goodfellow et al., 2016), y no lo entiendo del todo bien.

El descenso de gradiente estocástico tiene muchos usos importantes fuera del contexto del aprendizaje profundo. Es la principal forma de entrenar grandes modelos lineales en conjuntos de datos muy grandes. Para un tamaño de modelo fijo, el coste por SGD no depende del tamaño del conjunto de entrenamiento $m$ . En la práctica, a menudo modelo a medida que aumenta el tamaño del conjunto de entrenamiento, pero no estamos obligados a hacerlo. obligados a hacerlo. El número de actualizaciones necesarias para alcanzar la convergencia suele aumentar con el tamaño del conjunto de entrenamiento. Sin embargo como $m$ se aproxima a infinito, el modelo acabará convergiendo a su mejor error de prueba antes de que SGD haya muestreado todos los del conjunto de entrenamiento. Aumentar $m$ más no prolongará el tiempo de formación necesario para alcanzar el mejor error de prueba posible del modelo. Desde este punto de vista, se puede argumentar que el coste asintótico de entrenar un con SGD es $O(1)$ en función de $m$ .

Apartado 5.9, p.150

1. "El número de actualizaciones necesarias para alcanzar la convergencia suele aumentar con el tamaño del conjunto de entrenamiento". No puedo evitar esto. En el descenso de gradiente normal, resulta costoso calcular el gradiente en cada paso a medida que aumenta el número de ejemplos de entrenamiento. Pero no entiendo por qué el número de actualizaciones aumenta con el tamaño del entrenamiento.
2. "Sin embargo, como $m$ se acerca a la innidad, el modelo acabará convergiendo a su mejor error de prueba posible antes de que SGD haya muestreado todos los ejemplos del conjunto de entrenamiento. Aumentando $m$ no prolongará más el tiempo de entrenamiento necesario para alcanzar el mejor error de prueba posible del modelo". Yo tampoco entiendo esto

¿Puede aportar alguna intuición o argumento para los dos casos anteriores?

Goodfellow, Ian, Yoshua Bengio y Aaron Courville. Deep learning (Aprendizaje profundo). MIT press, 2016.

Answer 1

En la primera parte se habla de la convergencia de SGD a gran escala en la práctica y en la segunda de resultados teóricos sobre la convergencia de SGD cuando el problema de optimización es convexo.

---

"El número de actualizaciones necesarias para alcanzar la convergencia suele aumentar con el tamaño del conjunto de entrenamiento".

Esta afirmación me ha parecido confusa, pero como ha señalado amablemente @DeltaIV en los comentarios, creo que se refieren a consideraciones prácticas para un modelo fijo, ya que el tamaño del conjunto de datos es diferente. $m \rightarrow \infty$ . Creo que hay dos fenómenos relevantes:

1. las compensaciones de rendimiento cuando se intenta hacer SGD distribuido, o
2. rendimiento en un problema real de optimización no convexo

Compromisos computacionales para el SGD distribuido

En un escenario de gran volumen y alta tasa de datos, es posible que desee intentar implementar una versión distribuida de SGD (o más probablemente minibatch SGD). Lamentablemente, crear una versión distribuida y eficiente de SGD es difícil, ya que es necesario compartir con frecuencia el estado de los parámetros. $w$ . En concreto, se incurre en un gran coste de sincronización entre ordenadores, lo que incentiva el uso de minilotes más grandes. La siguiente figura de (Li et al., 2014) lo ilustra muy bien

SGD aquí es minibatch SGD y las otras líneas son algoritmos que proponen.

Sin embargo, también se sabe que, en el caso de los problemas convexos, los minilotes tienen un coste computacional que ralentiza la convergencia al aumentar el tamaño del minilote. Al aumentar el tamaño de los minilotes $m'$ hacia el tamaño del conjunto de datos $m$ se vuelve cada vez más lento hasta que sólo estás haciendo el descenso de gradiente por lotes normal. Esta disminución puede ser un poco drástica si se utiliza un gran tamaño de mini-lotes. Una vez más, esto se ilustra muy bien en (Li et al, 2014):

Aquí se representa el valor objetivo mínimo que han encontrado en el conjunto de datos KDD04 tras utilizar $10^7$ puntos de datos.

Formalmente, si $f$ es una función fuertemente convexa con un óptimo global $w^*$ y si $w_t$ es la salida de SGD en el $t^{th}$ iteración. Entonces usted puede demostrar que en la expectativa que tiene: $$\mathbb{E}[f(w_t) - f(w^*)] \leq \mathcal{O}(\frac{1}{\sqrt{t}}).$$ Tenga en cuenta que esto no depende del tamaño del conjunto de datos (esto es relevante para su siguiente pregunta). Sin embargo, para SGD minilotes con tamaño de lote $b$ la convergencia al óptimo se produce a un ritmo de $\mathcal{O}(\frac{1}{\sqrt{bt}} + \frac{1}{bt})$ . Cuando se dispone de una cantidad muy grande de datos (Li et al., 2014) señalan que:

Dado que el número total de ejemplos examinados es $bt$ mientras que sólo hay a $\sqrt{b}$ de mejora, la velocidad de convergencia se degrada con con el aumento del tamaño del minilote.

Existe un equilibrio entre el coste de sincronización de los minilotes pequeños y la penalización de rendimiento si aumenta el tamaño del minilote. Si se paraleliza ingenuamente el SGD (minilotes), se paga una cierta penalización y la velocidad de convergencia disminuye a medida que aumenta el tamaño de los datos.

No convexidad del problema de optimización empírica

Esto es básicamente lo que ha señalado @dopexxx. Es bien sabido que el problema de optimización que se quiere resolver en la práctica para las redes neuronales profundas no es convexo. En particular, puede tener las siguientes malas propiedades:

• mínimos locales y puntos de inflexión
• regiones de meseta
• curvatura muy variable

En general, se considera que la forma sobre la que se intenta optimizar es un colector y, hasta donde yo sé, todo lo que se puede decir sobre la convergencia es que se va a converger a (una bola de ruido alrededor de) un punto estacionario. Parece razonable pensar que cuanto mayor sea la variedad de datos del mundo real, más complicada será esta multiplicidad. Debido a que el gradiente real es más complicado como $m$ aumentar necesita más muestras para aproximar $\nabla f$ con SGD.

---

"Sin embargo, a medida que m se acerca a la infinidad, el modelo acabará convergiendo a su mejor error de prueba posible antes de que SGD haya muestreado todos los ejemplos del conjunto de entrenamiento. Aumentar m aún más no ampliará la cantidad de tiempo de entrenamiento necesario para alcanzar el mejor error de prueba posible del modelo".

(Goodfellow et al., 2016) afirman esto con un poco más de precisión en la discusión de la sección 8.3.1, donde afirman:

La propiedad más importante del SGD y de la optimización relacionada basada en minilotes o gradientes en línea es que el tiempo de cálculo por actualización no crece con el número de ejemplos de entrenamiento. Esto permite la convergencia incluso cuando el número de ejemplos de entrenamiento es muy grande. Para un conjunto de datos suficientemente grande, SGD puede converger dentro de una tolerancia fija de su error final en el conjunto de prueba antes de haber procesado todo el conjunto de datos de entrenamiento.

(Bottou et al., 2017) ofrecen la siguiente explicación clara:

A nivel intuitivo, la SG emplea la información de forma más eficiente que un método por lotes. Para verlo, consideremos una situación en la que un conjunto de entrenamiento, llamémoslo $S$ consta de diez copias de un conjunto $S_{sub}$ . Un minimizador del riesgo empírico para el conjunto mayor S viene dado claramente por un minimizador para el conjunto menor $S_{sub}$ pero si se aplicara un enfoque por lotes para minimizar $R_n$ en $S$ entonces cada iteración sería diez veces más cara que si sólo se tuviera una copia de $S_{sub}$ . Por el Por otro lado, SG realiza los mismos cálculos en ambos escenarios, en el sentido de que los cálculos del gradiente estocástico implican la elección de e gradiente estocástico consiste en elegir elementos de $S_{sub}$ con las mismas probabilidades.

donde $R_n$ es el riesgo empírico (esencialmente la pérdida de formación). Si se deja que el número de copias sea arbitrariamente grande, el SGD convergerá sin duda antes de haber muestreado todos los puntos de datos.

Creo que esto concuerda con mi intuición estadística. Se puede conseguir $|x^{\text{opt}} - x_k| < \epsilon$ en la iteración $k$ antes de muestrear necesariamente todos los puntos de su conjunto de datos, porque su tolerancia al error $\epsilon$ determina realmente la cantidad de datos que hay que consultar, es decir, cuántas iteraciones de SGD hay que completar.

La primera parte del artículo de (Bottou et al., 2017) me ha parecido bastante útil para entender mejor el SGD.

Referencias

Bottou, Léon, Frank E. Curtis y Jorge Nocedal. "Optimization methods for large-scale machine learning". arXiv preprint arXiv:1606.04838 (2016). https://arxiv.org/pdf/1606.04838.pdf

Li, Mu, et al. "Efficient mini-batch training for stochastic optimization". Actas de la 20ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos. ACM, 2014. https://www.cs.cmu.edu/~muli/file/minibatch_sgd.pdf

Answer 2

1. En SGD se utilizan minilotes de tamaño fijo, llamémoslo $d$ . Así que si usted tiene, por ejemplo: $m=1024$ y $d=8$ se necesitan 128 actualizaciones para recorrer todo el conjunto de entrenamiento. Si aumenta el tamaño del conjunto de entrenamiento a $m=2048$ necesitará 256 actualizaciones. Esto significa que el número de actualizaciones aumentado.

   Otra cosa es que, si hay más datos, se necesita más tiempo para converger (porque el modelo tiene que aprender más). Es de esperar que también debe converger a un punto mejor.

   Así pues, los autores quieren decir que más tiempo en este caso significa más actualizaciones (al contrario que en GD, donde el número de actualizaciones sigue siendo el mismo, pero son más largas).

2. Sólo dice que añadir datos al conjunto de entrenamiento no aumentará infinitamente el rendimiento del modelo. En la práctica, esto significa que si el conjunto de datos de entrenamiento es muy grande, el rendimiento del modelo estará limitado por el propio modelo y no por el tamaño del conjunto de datos de entrenamiento.

Answer 3

El hecho de que como $m\to\infty$ el número de iteraciones $N$ necesario para un determinista algoritmo de optimización para alcanzar el mismo valor de pérdida aumenta, es bastante intuitivo. Recordemos que el argumento de Goodfellow et al.

Para un modelo de tamaño fijo[..]

Esto significa que está aumentando $m$ pero el número de pesos $n_w$ permanece igual. Está claro que, con un modelo de complejidad fija, cada vez es más difícil ajustarlo a un conjunto de entrenamiento mayor.

El segundo punto, es decir, el hecho de que en lugar de $N$ para la SGD alcanza un máximo y luego se estabiliza, puede entenderse de la siguiente manera. Como $m$ crece indefinidamente pero el modelo sigue siendo el mismo, se llegará a un punto en el que $m$ es suficientemente mayor que la capacidad del modelo (digamos, una vez que $m$ es suficientemente mayor que la dimensión VC del modelo). En este punto ni siquiera necesitamos examinar todos los ejemplos del conjunto de entrenamiento, antes de que el modelo haya alcanzado su error mínimo en el conjunto de prueba, porque el modelo no es capaz de sobreajustar el conjunto de entrenamiento de todos modos. Mostrar al modelo más ejemplos aleatorios del conjunto de entrenamiento (que es lo que hace SGD) sólo hará que el error del conjunto de entrenamiento y el error del conjunto de prueba oscilen en torno a un valor mínimo, pero ninguno de ellos disminuirá significativamente.

Answer 4

Lo que creo que significa es que el número de iteraciones GD necesarias no crece linealmente con $m$ . Imagina que intentas estimar unos $\theta$ con un solo vector de datos $x$ : Empiezas con una suposición, luego tienes una mejor estimación basada en $x_1$ . a continuación, tiene una estimación aún mejor, basada en $x_1$ y $x_2$ . Cuantas más observaciones tengas, más te acercarás al objetivo. A medida que aumenta el número de observaciones, el peso de cada una de ellas disminuye y, por tanto, el impacto relativo de cada observación adicional se reduce. Suponiendo que no tenga valores atípicos (espere un segundo con esto), o bien converge al objetivo o llega a fluctuaciones minúsculas dentro de un número de pasos que es casi constante. Si tienes valores atípicos, se observará un aumento, pero después volverás a converger hacia el objetivo (cada valor atípico requeriría una cantidad de pasos adicionales para cubrirlo). Hasta ahí puedo llegar con mi intuición, basada tanto en el modelo como en mi experiencia con él. Sin embargo, no puedo proporcionarte fuentes.

Answer 5

1. Un conjunto de entrenamiento más amplio implica casi inevitablemente una mayor variabilidad de ejemplos. Por lo tanto, sacar lotes aleatorios durante el entrenamiento producirá en promedio, una entropía más alta (entre lotes, no dentro). Y así la función que intentas aproximar se vuelve más compleja y necesitas entrenar durante más tiempo para converger.
2. Imagina que quieres resolver un problema de clasificación estándar, como reconocer animales a partir de imágenes. Digamos que su conjunto de datos comprende $10^9$ imágenes e imagina este conjunto de imágenes $1cm$ pila alta. La cantidad de imágenes discerniblemente diferentes está en el rango de $10^{40}$ siendo la pila $9.98 \times 10^{25} km$ que extiende el diámetro del universo que es de alrededor de $8.85 \times 10^{23} km$ . (Vi este cálculo en ICCV 2017; para más detalles, véase la diapositiva nº. 3 aquí ). Ahora, imagine que se entrena en este vasto conjunto de datos ( $m:=10^{40}$ ). Aunque fuera computacionalmente factible, en algún momento ya no le ayudaría a clasificar correctamente las imágenes de sus animales. Es decir, durante el entrenamiento se daría cuenta de que después de haber visto sólo $n<m$ muestras su algoritmo no mejora más y puesto que $n\ll m$ se puede argumentar válidamente que el coste de formación asintótico está en $\mathcal{O}(1)$