Estas son las pruebas que en realidad se originan a partir de filtro adaptativo de la teoría.
Historia: filtros Adaptativos están en línea-algoritmos de optimización que ganó popularidad en los campos de Procesamiento de la Señal (por ejemplo, de cancelación de ruido) y de comunicaciones (por ejemplo, el canal de la estimación). El algoritmo que se describe en su pregunta se refiere a como la Menos Mean Square (LMS) algoritmo en el área de procesamiento de la señal.
Desde sus datos $x^{(t)}$ es asumido estocástico, sólo podemos demostrar la convergencia en el estáticas sentido. Por ejemplo, sólo podemos demostrar la convergencia en la media o media-cuadrado. Como la prueba de la media de los cuadrados de convergencia es un poco más complicado, voy a incluir la prueba de la media de la convergencia.
Supongamos que el algoritmo está tratando de converger a una óptima vector de parámetros $\theta^{*}$.
Su gradiente estocástico algoritmo de descenso:
$$\theta^{(t+1)} = \theta^{(t)} + \eta (y^{(t)} - \theta^{(t)}x^{(t)} )x^{(t)}$$
Tenga en cuenta que yo no suponga un invariante en el tiempo del tamaño de paso, $\eta$.
Aquí está la parte interesante: Porque se supone que hay un óptimo vector de parámetros $\theta^{*}$, se puede decir que su objetivo deseado, $y^{(t)}$ se genera el formulario de la esta $\theta^{*}$ y sus características $x^{(t)}$ como el siguiente:
$$y^{(t)} = \theta^{*}x^{(t)} + \epsilon^{(t)} $$ where $\epsilon^{(t)} $ is a zero-mean white noise process that is independent to your features $x^{(t)}$. The noise factor $\epsilon^{(t)}$ es añadido para denotar nuestra incertidumbre en el modelo.
La sustitución de este modelo de datos de $y^{(t)}$ nuevo en su SGD actualización queation da
$$\theta^{(t+1)} = \theta^{(t)} + \eta \big(\theta^{*}x^{(t)} + \epsilon^{(t)} - \theta^{(t)}x^{(t)}\big )x^{(t)}$$
En lugar de buscar en el parámetro de actualización, ahora se convierte en útil para estudiar el error en la estimación del parámetro $v^{(t)} = \theta^{*} -\theta^{(t)} $. Restar el vector óptimo $\theta^{*}$ desde la izquierda y la derecha lados de la parte de arriba te da
$$ \begin{align}
v^{(t+1)} = {} & v^{(t)} - \eta \big( v^{(t)}x^{(t)} +\epsilon^{(t)} \big )x^{(t)} \\
= {} & v^{(t)} - \eta v^{(t)}(x^{(t)})^2 -\eta\epsilon^{(t)}x^{(t)}
\end{align}
$$
Aplicando ahora la expectativa estadística operador da
$$ \begin{align}
\mathbb{E}[v^{(t+1)}] = {} & \mathbb{E}[v^{(t)}] - \eta \mathbb{E}[v^{(t)}(x^{(t)})^2] -\eta \mathbb{E}[\epsilon^{(t)}x^{(t)}]
\end{align}
$$
- Desde el valor cero ruido $\epsilon$ es independiente de las características $x^{(t)}$, $\mathbb{E}[\epsilon^{(t)}x^{(t)}] = \mathbb{E}[\epsilon^{(t)}]\mathbb{E}[x^{(t)}] = 0$
- También desde $v^{(t)}$ es sólo función de los valores pasados de $x^{(t)}$ es decir
$v^{(t)} = \mathcal{F}(x^{(t-1)}, \ldots, x^0)$, y suponemos que $x^{(t)}$ es independiente de su pasado, los valores de $x^{(t-1)},\ldots, x^{(0)} $ podemos decir que el $ \mathbb{E}[v^{(t)}(x^{(t)})^2] = \mathbb{E}[v^{(t)}] \mathbb{E}[(x^{(t)})^2]$.
Esto nos da
$$
\mathbb{E}[v^{(t+1)}] = (1 - \eta \mathbb{E}[(x^{(t)})^2])\mathbb{E}[v^{(t)}]
$$
Si decimos que la varianza de las características es $\mathbb{E}[(x^{(t)})^2] = \sigma^2_x$, podemos escribir la media de error de la evolución como
$$\mathbb{E}[v^{(t+1)}] = \underbrace{(1 - \eta \sigma^2_x}_{= \alpha} )\mathbb{E}[v^{(t)}]
$$
Para que el algoritmo de convergencia, $|\alpha| < 1 $. Si $|\alpha|$ es mayor que 1, en cada iteración el error se amplifica (Creo $v^{(t+1)} = 2v^{(t)}$). El $|\alpha| < 1 $ está satisfecho si la tasa de aprendizaje está delimitada por:
$$ 0 < \eta < \frac{2}{\sigma^2_x}
$$
Esto completa la prueba de convergencia para el SGD algoritmo.
En su caso le puede casi decir que mientras $\eta_t < \frac{2}{\sigma^2_x} \forall t$, su algoritmo de convergencia.
Descargo de responsabilidad: tenga en cuenta que esto sólo es una garantía para la media de la convergencia - en la práctica, su tamaño de paso sería mucho menor que el de este. La media de la plaza de la condición de convergencia, por ejemplo, le daría una mayor enlazado.
Consejo rápido: Desde mi experiencia, es mucho más limpio y un infierno de mucho más rápido si usted escribe su tiempo de índices como subíndices sin corchetes por ejemplo,$\theta_{t+1} = \theta_t + \eta_t(y_t - \theta_tx_t)x_t$. ;)
