Optimización estocástica y métodos de gran escala

SGD evalúa una muestra o un grupo pequeño para proponer un paso. Un gradiente completo recorre los N términos, mientras uno individual solo accede a uno.

Comparar métodos exige contar evaluaciones de datos, memoria, comunicación y precisión final. Reducir coste por actualización puede aumentar el número de pasos. Optimizar el objetivo empírico y generalizar a una población son preguntas distintas.

Sea ℱₖ la información antes de elegir la muestra del paso k; xₖ ya está determinado por esa historia.

Pedimos .

El ruido gₖ−∇F(xₖ) tiene media condicional cero.

En un promedio finito, un índice nuevo uniforme da esa identidad exactamente. Para una esperanza de funciones hay que justificar el intercambio de derivación y esperanza. Si el muestreo no es uniforme, se corrigen los pesos o se reconoce que se está siguiendo otro objetivo.

Aunque E[gₖ|ℱₖ]=∇F(xₖ), una realización puede apuntar en dirección desfavorable. También un paso grande puede sobrepasar el mínimo sin ruido.

La cota debe valer en el régimen analizado. Colas pesadas, dependencia o varianza creciente necesitan otro control. No se deduce descenso individual ni descenso esperado con cualquier paso de la identidad de no sesgo.

La media de b estimaciones condicionalmente independientes con media común y varianza escalar σ² tiene varianza σ²/b. En vectores, la covarianza se divide por b y lo mismo ocurre con su traza, bajo esas hipótesis.

Si las estimaciones dependen entre sí aparecen covarianzas. Para muestreo uniforme sin reemplazo de N>1 valores, con varianza poblacional σ² calculada dividiendo por N, la varianza de su media es σ²(N−b)/(b(N−1)). Es otro esquema; también cuesta más cada actualización cuando aumenta b.

Condicionando en la historia y usando no sesgo más la cota de varianza obtenemos .

Para 0<η≤1/L, el término favorable es al menos η||∇F||²/2, pero permanece el término de ruido. Las esperanzas deben estar bien definidas con los momentos necesarios. La desigualdad es condicional, no una promesa sobre cada realización.

En un marco concreto, F es μ-fuertemente convexa y L-suave en ℝᵈ, con mínimo x*, punto inicial de segundo momento finito y ruido condicional centrado de segundo momento ≤σ². Expandir la distancia da .

Con Σηₖ=∞ y Σηₖ²<∞, esa recurrencia lleva a error cuadrático medio cero. Un paso constante con ruido persistente deja en general una escala residual; sin ruido puede converger exactamente. No se traslada este resultado a cualquier función no convexa.

Con F≥ real, L-suavidad, ruido centrado de varianza ≤σ² y paso fijo 0<η≤1/L, sumamos la desigualdad de progreso durante K pasos. Resulta , con punto inicial fijo y las esperanzas pertinentes finitas.

Reducir el lado derecho controla un promedio de gradientes cuadrados. Elegir al azar un índice uniforme independiente entre los visitados da esa misma media esperada. Un gradiente pequeño no certifica mínimo global: puede estar cerca de un máximo o una silla.

Para un promedio finito y un índice nuevo uniforme, el estimador gᵢ(x)=∇fᵢ(x)−∇fᵢ()+∇F() es no sesgado. Si x=, los dos gradientes individuales se cancelan y queda el gradiente completo.

Guardar o recalcular la referencia, memoria, momento, curvatura o reparto entre máquinas añade coste y supuestos. Promediar máquinas con cantidades distintas de datos necesita pesos coherentes con el objetivo. El análisis de SGD simple no justifica automáticamente cualquier combinación de estas técnicas.

En F=x²/2 tomamos gₖ=xₖ+ξₖ, con ruidos independientes de la historia, centrados y de varianza σ².

Si 0<η<2, la media decae geométricamente y el segundo momento satisface E xₖ₊₁²=(1−η)²E xₖ²+η²σ².

Resolver la suma geométrica da un segundo momento límite ησ²/(2−η). Por tanto la pérdida esperada tiende a la mitad de ese valor. No es una cota inferior de cada trayectoria. Un minibatch independiente de tamaño b reemplaza σ² por σ²/b en este modelo.