Aproximación estocástica

Consideremos el problema de estimar la media.${\displaystyle \theta ^{*}}$de una distribución de probabilidad a partir de una secuencia de muestras independientes${\displaystyle X_{1},X_{2},\dots }$.

Dejar${\displaystyle N(\theta ):=\theta -X}$, entonces la solución única para${\textstyle \operatorname {E} [N(\theta )]=0}$es la media deseada${\displaystyle \theta ^{*}}$El algoritmo RM nos da$${\displaystyle \theta _{n+1}=\theta _{n}-a_{n}(\theta _{n}-X_{n})}$$Esto es equivalente al descenso de gradiente estocástico con función de pérdida.${\displaystyle L(\theta )={\frac {1}{2}}\|X-\theta \|^{2}}$También equivale a un promedio ponderado:$${\displaystyle \theta _{n+1}=(1-a_{n})\theta _{n}+a_{n}X_{n}}$$En general, si existe alguna función${\displaystyle L}$de tal manera que${\displaystyle \nabla L(\theta )=N(\theta )-\alpha }$Entonces, el algoritmo de Robbins-Monro es equivalente al descenso de gradiente estocástico con función de pérdida.${\displaystyle L(\theta )}$Sin embargo, el algoritmo RM no requiere${\displaystyle L}$existir para converger.

1. Si${\textstyle f(\theta )}$es dos veces continuamente diferenciable, fuertemente convexo y el minimizador de${\textstyle f(\theta )}$pertenece al interior de${\textstyle \Theta }$, entonces el algoritmo de Robbins-Monro alcanzará la tasa de convergencia asintóticamente óptima, con respecto a la función objetivo, siendo${\textstyle \operatorname {E} [f(\theta _ {n})-f^{*}]=O(1/n)}$, dónde${\textstyle f^{*}}$es el valor mínimo de${\textstyle f(\theta )}$encima${\textstyle \theta \in \Theta }$. ^{[ 5 ] [ 6 ]}
2. Por el contrario, en el caso convexo general, donde carecemos tanto del supuesto de suavidad como de la fuerte convexidad, Nemirovski y Yudin ^{[ 7 ]} han demostrado que la tasa de convergencia asintóticamente óptima, con respecto a los valores de la función objetivo, es${\textstyle O(1/{\sqrt {n}})}$También han demostrado que esta tasa no se puede mejorar.

Si bien el algoritmo de Robbins-Monro es teóricamente capaz de lograrlo${\textstyle O(1/n)}$Bajo el supuesto de diferenciabilidad continua doble y fuerte convexidad, su implementación puede resultar bastante deficiente. Esto se debe principalmente a que el algoritmo es muy sensible a la elección de la secuencia de tamaño de paso, y la supuesta política de tamaño de paso asintóticamente óptima puede ser bastante perjudicial al principio. ^{[ 6 ] [ 8 ]}

Chung (1954) ^{[ 9 ]} y Fabian (1968) ^{[ 10 ]} demostraron que lograríamos una tasa de convergencia óptima.${\textstyle O(1/{\sqrt {n}})}$con${\textstyle a_{n}=\bigtriangledown ^{2}f(\theta ^{*})^{-1}/n}$(o${\textstyle a_{n}={\frac {1}{(nM'(\theta ^{*}))}}}$). Lai y Robbins ^{[ 11 ] [ 12 ]} diseñaron procedimientos adaptativos para estimar${\textstyle M'(\theta ^{*})}$de tal manera que${\textstyle \theta _{n}}$tiene una varianza asintótica mínima. Sin embargo, la aplicación de tales métodos óptimos requiere mucha información a priori, la cual es difícil de obtener en la mayoría de las situaciones. Para superar esta deficiencia, Polyak (1991) ^{[ 13 ]} y Ruppert (1988) ^{[ 14 ]} desarrollaron independientemente un nuevo algoritmo óptimo basado en la idea de promediar las trayectorias. Polyak y Juditsky ^{[ 15 ]} también presentaron un método para acelerar el algoritmo de Robbins-Monro para problemas de búsqueda de raíces lineales y no lineales mediante el uso de pasos más largos y el promedio de las iteraciones. El algoritmo tendría la siguiente estructura:$${\displaystyle \theta _{n+1}-\theta _{n}=a_{n}(\alpha -N(\theta _{n})),\qquad {\bar {\theta }}_{n}={\frac {1}{n}}\sum _{i=0}^{n-1}\theta _{i}}$$La convergencia de${\displaystyle {\bar {\theta }}_{n}}$a la raíz única${\displaystyle \theta ^{*}}$depende de la condición de que la secuencia de pasos${\displaystyle \{a_{n}\}}$disminuye suficientemente lento. Es decir

A1)$${\displaystyle a_{n}\rightarrow 0,\qquad {\frac {a_{n}-a_{n+1}}{a_{n}}}=o(a_{n})}$$

Por lo tanto, la secuencia${\textstyle a_{n}=n^{-\alpha }}$con${\textstyle 0<\alpha <1}$satisface esta restricción, pero${\textstyle \alpha =1}$No, de ahí los pasos más largos. Bajo los supuestos descritos en el algoritmo de Robbins-Monro, la modificación resultante dará como resultado la misma tasa de convergencia asintóticamente óptima.${\textstyle O(1/{\sqrt {n}})}$pero con una política de tamaño de paso más robusta. ^{[ 15 ]} Anteriormente, la idea de usar pasos más largos y promediar las iteraciones ya había sido propuesta por Nemirovski y Yudin ^{[ 16 ]} para los casos de resolución del problema de optimización estocástica con objetivos convexos continuos y para problemas de punto de silla convexo-cóncavo. Se observó que estos algoritmos alcanzaban la tasa no asintótica${\textstyle O(1/{\sqrt {n}})}$.

Un resultado más general se presenta en el Capítulo 11 de Kushner y Yin ^{[ 17 ]} definiendo el tiempo interpolado.${\textstyle t_{n}=\sum _{i=0}^{n-1}a_{i}}$, proceso interpolado${\textstyle \theta ^{n}(\cdot )}$y proceso normalizado interpolado${\textstyle U^{n}(\cdot )}$como

$${\displaystyle \theta ^{n}(t)=\theta _{n+i},\quad U^{n}(t)=(\theta _{n+i}-\theta ^{*})/{\sqrt {a_{n+i}}}\quad {\mbox{for}}\quad t\in [t_{n+i}-t_{n},t_{n+i+1}-t_{n}),i\geq 0}$$Sea el promedio de iteración${\displaystyle \Theta _{n}={\frac {a_{n}}{t}}\sum _{i=n}^{n+t/a_{n}-1}\theta _{i}}$y el error normalizado asociado debe ser${\displaystyle {\hat {U}}^{n}(t)={\frac {\sqrt {a_{n}}}{t}}\sum _{i=n}^{n+t/a_{n}-1}(\theta _{i}-\theta ^{*})}$.

Con la suposición A1) y la siguiente A2)

A2) Existe una matriz de Hurwitz${\textstyle A}$y una matriz simétrica y definida positiva${\textstyle \Sigma }$de tal manera que${\textstyle \{U^{n}(\cdot )\}}$converge débilmente a${\textstyle U(\cdot )}$, dónde${\textstyle U(\cdot )}$ es la solución de estasis$${\displaystyle dU=AU\,dt+\Sigma ^{1/2}\,dw}$$dónde${\textstyle w(\cdot )}$es un proceso Wiener estándar.

satisfecho y definir${\textstyle {\bar {V}}=(A^{-1})'\Sigma (A')^{-1}}$Luego, para cada uno${\textstyle t}$,

$${\displaystyle {\hat {U}}^{n}(t){\stackrel {\mathcal {D}}{\longrightarrow }}{\mathcal {N}}(0,V_{t}),\quad {\text{where}}\quad V_{t}={\bar {V}}/t+O(1/t^{2}).}$$

El éxito de la idea del promedio se debe a la separación de escalas de tiempo de la secuencia original.${\textstyle \{\theta _{n}\}}$y la secuencia promedio${\textstyle \{\Theta _{n}\}}$, siendo la escala de tiempo de la primera más rápida.

Supongamos que queremos resolver el siguiente problema de optimización estocástica.$${\displaystyle g(\theta ^{*})=\min _{\theta \in \Theta }\operatorname {E} [Q(\theta ,X)],}$$dónde${\textstyle g(\theta )=\operatorname {E} [Q(\theta ,X)]}$Si es diferenciable y convexa, entonces este problema es equivalente a encontrar la raíz.${\displaystyle \theta ^{*}}$de${\displaystyle \nabla g(\theta )=0}$. Aquí${\displaystyle Q(\theta ,X)}$puede interpretarse como algún costo "observado" en función de lo elegido${\displaystyle \theta }$y efectos aleatorios${\displaystyle X}$. En la práctica, podría ser difícil obtener una forma analítica de${\displaystyle \nabla g(\theta )}$El método de Robbins-Monro logra generar una secuencia${\displaystyle (\theta _{n})_{n\geq 0}}$para aproximar${\displaystyle \theta ^{*}}$si uno puede generar${\displaystyle (X_{n})_{n\geq 0}}$, en la que la expectativa condicional de${\displaystyle X_{n}}$dado${\displaystyle \theta _{n}}$es exactamente${\displaystyle \nabla g(\theta _{n})}$, es decir${\displaystyle X_{n}}$se simula a partir de una distribución condicional definida por

$${\displaystyle \operatorname {E} [H(\theta ,X)|\theta =\theta _{n}]=\nabla g(\theta _{n}).}$$

Aquí${\displaystyle H(\theta ,X)}$es un estimador insesgado de${\displaystyle \nabla g(\theta )}$. Si${\displaystyle X}$depende de${\displaystyle \theta }$En general, no existe una forma natural de generar un resultado aleatorio.${\displaystyle H(\theta ,X)}$que es un estimador insesgado del gradiente. En algunos casos especiales cuando son aplicables los métodos IPA o de razón de verosimilitud, entonces se puede obtener un estimador de gradiente insesgado.${\displaystyle H(\theta ,X)}$. Si${\displaystyle X}$se considera como algún proceso aleatorio subyacente "fundamental" que se genera independientemente de${\displaystyle \theta }$y bajo ciertas condiciones de regularización para operaciones de intercambio de derivadas e integrales, de modo que${\displaystyle \operatorname {E} {\Big [}{\frac {\partial }{\partial \theta }}Q(\theta ,X){\Big ]}=\nabla g(\theta )}$, entonces${\displaystyle H(\theta ,X)={\frac {\partial }{\partial \theta }}Q(\theta ,X)}$proporciona la estimación insesgada del gradiente fundamental. Sin embargo, para algunas aplicaciones tenemos que utilizar métodos de diferencias finitas en los que${\displaystyle H(\theta ,X)}$tiene una expectativa condicional cercana a${\displaystyle \nabla g(\theta )}$pero no exactamente igual.

Al identificar la minimización con el problema de búsqueda de raíces${\displaystyle \nabla g(\theta )=0}$La aproximación estocástica puede aplicarse para definir una solución recursiva para el mínimo, análoga al algoritmo de Robbins-Monro:

$${\displaystyle \theta _{n+1}=\theta _{n}-\varepsilon _{n}H(\theta _{n},X_{n+1}).}$$

1. El algoritmo de Kiefer Wolfowitz requiere que para cada cálculo de gradiente, al menos${\displaystyle d+1}$Se deben simular diferentes valores de parámetros para cada iteración del algoritmo, donde${\displaystyle d}$es la dimensión del espacio de búsqueda. Esto significa que cuando${\displaystyle d}$Si el tamaño es grande, el algoritmo de Kiefer-Wolfowitz requerirá un esfuerzo computacional sustancial por iteración, lo que dará lugar a una convergencia lenta.
   1. Para abordar este problema, Spall propuso el uso de perturbaciones simultáneas para estimar el gradiente. Este método requeriría solo dos simulaciones por iteración, independientemente de la dimensión.${\displaystyle d}$. ^{[ 20 ]}
2. En las condiciones necesarias para la convergencia, puede resultar difícil encontrar un conjunto compacto predeterminado que cumpla con la condición de convexidad (o concavidad) fuerte y que contenga la solución única. En aplicaciones prácticas, si el dominio es muy extenso, estas suposiciones pueden ser bastante restrictivas y poco realistas.