Optimización Estocástica

La optimización estocástica minimiza un objetivo utilizando estimaciones ruidosas de su gradiente o valor, actualizando los parámetros a partir de subconjuntos aleatorios de datos o perturbaciones aleatorias en lugar del objetivo completo y exacto.

Definition

La optimización estocástica es una familia de métodos iterativos que actualizan las estimaciones de los parámetros utilizando estimaciones aleatorias e insesgadas de un objetivo o su gradiente, lo que permite la optimización cuando el objetivo completo es demasiado costoso de evaluar o solo se observa con ruido.

Scope

Este tema abarca la aproximación estocástica en la tradición de Robbins-Monro, el descenso de gradiente estocástico y sus variantes de mini-lotes y momento, los programas de tamaño de paso (tasa de aprendizaje) que controlan la convergencia, la compensación entre ruido y costo computacional, y las garantías de convergencia. Se enfatiza su papel en el ajuste de modelos estadísticos y de aprendizaje automático a gran escala.

Core questions

• ¿Cómo pueden las estimaciones de gradiente ruidosas impulsar la convergencia hacia un óptimo?
• ¿Qué programas de tamaño de paso garantizan la convergencia en el marco de Robbins-Monro?
• ¿Cómo compensa el mini-lote el ruido con el costo computacional por paso?
• ¿Por qué la optimización estocástica es esencial para conjuntos de datos muy grandes?

Key concepts

• Aproximación estocástica
• Gradiente de mini-lote
• Programa de tasa de aprendizaje
• Estimación de gradiente insesgada
• Decaimiento del tamaño de paso
• Convergencia casi segura

Key theories

Aproximación estocástica

El esquema de Robbins-Monro encuentra la raíz de una función desconocida a partir de mediciones ruidosas, dando pequeños pasos cuyo tamaño disminuye a una tasa prescrita, convergiendo casi con seguridad bajo ciertas condiciones en la secuencia del tamaño de paso.

Métodos de gradiente estocástico

Reemplazar el gradiente completo por una estimación insesgada de un subconjunto de datos aleatorio produce actualizaciones económicas cuya trayectoria promediada desciende el objetivo, con programas de tasa de aprendizaje que equilibran la velocidad de convergencia con la varianza del ruido.

Clinical relevance

Los métodos de gradiente estocástico permiten ajustar modelos a conjuntos de datos demasiado grandes para procesar de una sola vez, y son la estrategia de optimización dominante para entrenar redes neuronales y regresión a gran escala, donde calcular el gradiente completo en cada paso sería prohibitivo.

History

Robbins y Monro introdujeron la aproximación estocástica en 1951 para encontrar raíces a partir de observaciones ruidosas, y Kiefer y Wolfowitz la adaptaron a la optimización poco después; la explosión del aprendizaje automático a gran escala revivió estas ideas como el descenso de gradiente estocástico y sus muchas variantes modernas.

Key figures

• Herbert Robbins
• Sutton Monro
• Harold Kushner
• Jack Kiefer

Seminal works

• robbins1951
• kushner2003

Frequently asked questions

¿Por qué usar gradientes ruidosos en lugar del gradiente exacto?

Calcular el gradiente exacto sobre millones de puntos de datos es costoso. Un gradiente estimado a partir de un pequeño lote aleatorio es mucho más económico y, aunque ruidoso, sigue apuntando cuesta abajo en promedio, por lo que muchos pasos ruidosos y económicos pueden superar a unos pocos exactos.

¿Por qué el tamaño del paso suele disminuir con el tiempo?

Disminuir el tamaño del paso amortigua el ruido del gradiente a medida que las iteraciones se acercan al óptimo, lo cual es lo que requieren las condiciones de Robbins-Monro para la convergencia. Un tamaño de paso que se mantiene demasiado grande hace que la estimación oscile alrededor de la solución.