Consider the stochastic iterative updates \begin{align} \theta_{t+1} \leftarrow \theta_t + \alpha_t \cdot h(\theta_t) + M_t, \end{align} where $\theta_t \in \mathrm{R}^d$, $h \colon \mathrm{R} ^d \rightarrow \mathrm{R}^d$ is Lipschitz continuous, $M_t$ is a martingale difference. Here the stepsize $\alpha_t $ satisfies \begin{align} \sum_{t\geq 0} \alpha_t = \infty, ~~~~\sum_{t \geq 0} \alpha_t^2 < \infty. \end{align} Standard stochastic approximation results suggest that $\{ \theta_t \}_{t\geq 0}$ converges to the limit point of an ODE \begin{align} \dot \theta(t) = h( \theta(t) ). \end{align} Moreover, under the assumption that the ODE has an unique global equilibrium $\theta^*$, it can be shown that $\theta_t \rightarrow \theta^*$ as $t$ goes to infinity.

However, one interesting question is whether $\{ \theta_t\}_{t\geq 0}$ converges if $h$ has multiple zeros. That is, there exists multiple $\bar \theta$'s such that $h( \bar \theta) = 0$. Under what condition can we show that the algorithm converges to any one of these $\bar \theta$'s (equilibria)? Moreover, under what conditions can we show that the algorithm only converges to a locally stable equilibrium?

Consider the stochastic iterative updates \begin{align} \theta_{t+1} \leftarrow \theta_t + \alpha_t \cdot \left [ h(\theta_t) + M_t \right ], \end{align} where $\theta_t \in \mathrm{R}^d$, $h \colon \mathrm{R} ^d \rightarrow \mathrm{R}^d$ is Lipschitz continuous, $M_t$ is a martingale difference. Here the stepsize $\alpha_t $ satisfies \begin{align} \sum_{t\geq 0} \alpha_t = \infty, ~~~~\sum_{t \geq 0} \alpha_t^2 < \infty. \end{align} Standard stochastic approximation results suggest that $\{ \theta_t \}_{t\geq 0}$ converges to the limit point of an ODE \begin{align} \dot \theta(t) = h( \theta(t) ). \end{align} Moreover, under the assumption that the ODE has an unique global equilibrium $\theta^*$, it can be shown that $\theta_t \rightarrow \theta^*$ as $t$ goes to infinity.

However, one interesting question is whether $\{ \theta_t\}_{t\geq 0}$ converges if $h$ has multiple zeros. That is, there exists multiple $\bar \theta$'s such that $h( \bar \theta) = 0$. Under what condition can we show that the algorithm converges to any one of these $\bar \theta$'s (equilibria)? Moreover, under what conditions can we show that the algorithm only converges to a locally stable equilibrium?

Consider the stochastic iterative updates \begin{align} \theta_{t+1} \leftarrow \theta_t - \alpha_t \cdot h(\theta_t) + M_t, \end{align} where $\theta_t \in \mathrm{R}^d$, $h \colon \mathrm{R} ^d \rightarrow \mathrm{R}^d$ is Lipschitz continuous, $M_t$ is a martingale difference. Here the stepsize $\alpha_t $ satisfies \begin{align} \sum_{t\geq 0} \alpha_t = \infty, ~~~~\sum_{t \geq 0} \alpha_t^2 < \infty. \end{align} Standard stochastic approximation results suggest that $\{ \theta_t \}_{t\geq 0}$ converges to the limit point of an ODE \begin{align} \dot \theta(t) = h( \theta(t) ). \end{align} Moreover, under the assumption that the ODE has an unique global equilibrium $\theta^*$, it can be shown that $\theta_t \rightarrow \theta^*$ as $t$ goes to infinity.

However, one interesting question is whether $\{ \theta_t\}_{t\geq 0}$ converges if $h$ has multiple zeros. That is, there exists multiple $\bar \theta$'s such that $h( \bar \theta) = 0$. Under what condition can we show that the algorithm converges to any one of these $\bar \theta$'s (equilibria)? Moreover, under what conditions can we show that the algorithm only converges to a locally stable equilibrium?

Consider the stochastic iterative updates \begin{align} \theta_{t+1} \leftarrow \theta_t + \alpha_t \cdot h(\theta_t) + M_t, \end{align} where $\theta_t \in \mathrm{R}^d$, $h \colon \mathrm{R} ^d \rightarrow \mathrm{R}^d$ is Lipschitz continuous, $M_t$ is a martingale difference. Here the stepsize $\alpha_t $ satisfies \begin{align} \sum_{t\geq 0} \alpha_t = \infty, ~~~~\sum_{t \geq 0} \alpha_t^2 < \infty. \end{align} Standard stochastic approximation results suggest that $\{ \theta_t \}_{t\geq 0}$ converges to the limit point of an ODE \begin{align} \dot \theta(t) = h( \theta(t) ). \end{align} Moreover, under the assumption that the ODE has an unique global equilibrium $\theta^*$, it can be shown that $\theta_t \rightarrow \theta^*$ as $t$ goes to infinity.

However, one interesting question is whether $\{ \theta_t\}_{t\geq 0}$ converges if $h$ has multiple zeros. That is, there exists multiple $\bar \theta$'s such that $h( \bar \theta) = 0$. Under what condition can we show that the algorithm converges to any one of these $\bar \theta$'s (equilibria)? Moreover, under what conditions can we show that the algorithm only converges to a locally stable equilibrium?