¿Cómo definir la condición de terminación del descenso del gradiente?

Question

En realidad, quería preguntarle cómo puedo definir la condición de terminación del descenso del gradiente.

¿Puedo detenerlo en base al número de iteraciones, es decir, considerando los valores de los parámetros para, digamos, 100 iteraciones?

O debería esperar de tal manera que el diferente valor de los dos parámetros, "nuevo" y "viejo", sea muy pequeño en el orden de digamos $10^{-6}$ ? Esto definitivamente tomará mucho tiempo.

¿Cuál es la mejor manera? En mi caso, incluso una iteración lleva un tiempo significativo. En esta situación, si espero la segunda condición, puede que incluso tarde semanas, supongo.

Así que, ¿qué enfoque debería usar? ¿Cómo abordar este escenario?

Answer 1

Buena pregunta. He visto muchas reglas de parada en la literatura, y hay ventajas y desventajas en cada una, dependiendo del contexto. El optim La función en R, por ejemplo, tiene al menos tres reglas de parada diferentes:

• maxit es decir, un número máximo predeterminado de iteraciones. Otra alternativa similar que he visto en la literatura es un número máximo de segundos antes del tiempo de salida. Si todo lo que necesitas es una solución aproximada, esto puede ser muy razonable. De hecho, hay clases de modelos (especialmente modelos lineales) para los que la parada temprana es similar a poner un previo gaussiano en los valores de sus parámetros. Un frecuentador diría que tienes una "norma L2" en lugar de un prior, pero también pensaría que es algo razonable. Sólo he desnaturalizado este documento pero habla de la relación entre la parada temprana y la regularización y puede ayudar a apuntarte hacia más información. Pero la versión corta es, Sí, parar temprano puede ser algo perfectamente respetable, dependiendo de lo que te interese.

• abstol es decir, se detiene cuando la función se "acerca lo suficiente" a cero. Esto puede no ser relevante para ti (no suena como si estuvieras esperando un cero), así que me lo saltaré.

• reltol que es como tu segunda sugerencia parar cuando la mejora cae por debajo de un umbral. En realidad no sé cuánta teoría hay sobre esto, pero probablemente tenderás a obtener mínimos más bajos de esta manera que con un pequeño número máximo de iteraciones. Si eso es importante para ti, entonces podría valer la pena ejecutar el código para más iteraciones.

Otra familia de reglas de detención tiene que ver con la optimización de una función de costo en un conjunto de datos de validación (o con validación cruzada) en lugar de en los datos de entrenamiento. Dependiendo de para qué se quiera usar el modelo, es posible que se quiera parar mucho antes de llegar al mínimo local en los datos de entrenamiento, ya que eso podría implicar un sobreajuste. Estoy bastante seguro de que Trevor Hastie ha escrito sobre buenas formas de hacer esto, pero no puedo recordar la cita.

Otras posibles opciones para encontrar mínimos más bajos en un tiempo razonable podrían ser:

• Descenso estocástico de gradientes, que sólo requiere la estimación de los gradientes para una pequeña porción de sus datos a la vez (por ejemplo, un punto de datos para SGD "puro", o pequeños minilotes).

• Funciones de optimización más avanzadas (por ejemplo, métodos de tipo Newton o Gradiente Conjugado), que utilizan la información sobre la curvatura de su función objetivo para ayudarle a apuntar en mejores direcciones y tomar mejores tamaños de paso al moverse cuesta abajo.

• Un término de "impulso" en su regla de actualización, para que su optimizador haga un mejor trabajo de rodar cuesta abajo en lugar de delimitar las paredes del cañón en su función de objetivo.

Todos estos enfoques se analizan en estas notas de la conferencia que encontré en Internet.

¡Espero que esto ayude!

Edita oh, y también puedes intentar obtener mejores valores iniciales (por ejemplo, resolviendo una versión más simple del problema) para que se necesiten menos iteraciones para acercarse al óptimo desde tu "arranque en caliente".