## 2 Centralized Stochastic Approximation Algorithm
### Probabilistic Martingale Method
A2.1 The stepsize sequence \(\{a_{k}\}_{k\geq 0}\) satisfies  
\[a_{k}>0,\ \ \sum_{k=0}^{\infty}a_{k}=\infty,\ \ \sum_{k=0}^{\infty}a_{k}^{2}<\infty. \tag{8}\]  
A2.2 There exists a twice-differentiable function \(v(\cdot):\mathbb{R}^{l}\to\mathbb{R}\), such that:  
1. The Hessian matrix of \(v(\cdot)\) is bounded. 2. \(v(x^{0})=0,\ v(x)>0,\ \forall\ x\
eq x^{0}\) and \(v(x)\to\infty\) as \(\|x\|\to\infty\). 3. For any \(\varepsilon>0\), there exists an \(\beta_{\varepsilon}>0\) such that \[\sup_{\|x-x^{0}\|>\varepsilon}\triangledown v(x)^{T}f(x)=-\beta_{\varepsilon}<0.\] (9)  
A2.3 \(\{\varepsilon_{k},\mathcal{F}_{k}\}_{k\geq 0}\) is an m.d.s., that is, \(E[\varepsilon_{k+1}|\mathcal{F}_{k}]=0,\ k\geq 0\) and further, \(\sup_{k\geq 0}E\|\varepsilon_{k}\|^{2}<\infty\). A2.4 There exists a constant \(c>0\) such that \[\|f(x)\|^{2}+E[\|\varepsilon_{k+1}\|^{2}|\mathcal{F}_{k}]<c(1+v(x)),\ \ k\geq 0.\] (10)  
**Theorem 1**. : _([20, 45, 46]) Assume that A2.1-A2.4 hold. Then, with an arbitrary initial value \(x_{0}\), estimates generated from (2) converge to the root \(x^{0}\) of \(f(\cdot)\) almost surely, that is,_  
\[x_{k}\underset{k\to\infty}{\longrightarrow}x^{0}\ \ \text{a.s.} \tag{11}\]  
Proof. : Here, we list the sketch of the proof. By using the function \(v(\cdot)\) given in A2.2, define \(v_{k+1}\):  
\[v_{k+1}\triangleq(1+v(x_{k+1}))\prod_{i=k+1}^{\infty}(1+a_{i}^{2}), \tag{12}\]By (9), we can obtain  
\[0\leq E(v_{k+1}|\mathcal{F}_{k})\] \[\|x_{k+1}-x^{0}\|=\|x_{k}-x^{0}+a_{k}f(x_{k})+a_{k}\varepsilon_{k+1}\|\geq\|a_{k }\varepsilon_{k+1}\|-\varepsilon. \tag{5}\]0 \[\|x_{k+1}-x^{0}\|=\|x_{k}-x^{0}+a_{k}f(x_{k})+a_{k}\varepsilon_{k+1}\|\geq\|a_{k }\varepsilon_{k+1}\|-\varepsilon. \tag{5}\]1  
By the properties of a nonnegative supermartingale, we have that \(\{v_{k}\}_{k\geq 0}\) converges almost surely. Noting (8), we further obtain \(\prod_{i=k+1}^{\infty}(1+a_{i}^{2})\underset{k\to\infty}{\longrightarrow}1\) and thus, \(\{v(x_{k})\}_{k\geq 0}\) converges almost surely. With an arbitrary \(\varepsilon>0\), define  
\[\|x_{k+1}-x^{0}\|=\|x_{k}-x^{0}+a_{k}f(x_{k})+a_{k}\varepsilon_{k+1}\|\geq\|a_{k }\varepsilon_{k+1}\|-\varepsilon. \tag{5}\]2  
and a stopping sequence \(\{\sigma_{\varepsilon}^{i}\}_{i\geq 0}\):  
\[\|x_{k+1}-x^{0}\|=\|x_{k}-x^{0}+a_{k}f(x_{k})+a_{k}\varepsilon_{k+1}\|\geq\|a_{k }\varepsilon_{k+1}\|-\varepsilon. \tag{5}\]3  
By (13) and (14) and noting (9), we have  
\[\|x_{k+1}-x^{0}\|=\|x_{k}-x^{0}+a_{k}f(x_{k})+a_{k}\varepsilon_{k+1}\|\geq\|a_{k }\varepsilon_{k+1}\|-\varepsilon. \tag{5}\]4  
From (16) and by the properties of the supermartingale, we have  
\[\|x_{k+1}-x^{0}\|=\|x_{k}-x^{0}+a_{k}f(x_{k})+a_{k}\varepsilon_{k+1}\|\geq\|a_{k }\varepsilon_{k+1}\|-\varepsilon. \tag{5}\]5  
By (17) and (8), we can prove that \(\sigma_{\varepsilon}^{i}\) is finite almost surely, and there exists a subsequence \(\{x_{k_{i}}\}_{i\geq 1}\) which satisfies \(\|x_{k_{i}}-x^{0}\|\leq\varepsilon\). Since \(\varepsilon>0\) can be arbitrarily small, we know that there exists a subsequence of \(\{x_{k_{i}}\}_{i\geq 0}\) which converges to \(x^{0}\). By the convergence of \(\{v(x_{k})\}_{k\geq 0}\), we can finally prove (11). The above proof is based on the convergence of the nonnegative supermartingale, and the analysis method is accordingly named the probabilistic method (PM). **Remark 1**. : _If A2.2 is changed to_  
\[\|x_{k+1}-x^{0}\|=\|x_{k}-x^{0}+a_{k}f(x_{k})+a_{k}\varepsilon_{k+1}\|\geq\|a_{k }\varepsilon_{k+1}\|-\varepsilon. \tag{5}\]6  
_then we can prove the almost sure convergence of the following SAA_  
\[\|x_{k+1}-x^{0}\|=\|x_{k}-x^{0}+a_{k}f(x_{k})+a_{k}\varepsilon_{k+1}\|\geq\|a_{k }\varepsilon_{k+1}\|-\varepsilon. \tag{5}\]7  
**Remark 2**. : _From A2.3 we can see that it requires the observation noise being an m.d.s. In many problems, the observation noise may contain complicated state-dependent uncertainties, for example, \(\varepsilon_{k+1}=\varepsilon_{k+1}(x_{k})\).