## 2 Centralized Stochastic Approximation Algorithm
### SAAWET and Trajectory-Subsequence Method
: _([5]) For SAAWET (29) and (30), if A4.1, A4.2 and A4.4 hold, then on the sample path \(\omega\) where A4.3 takes place, it holds that_  
\[d(x_{k},J)\mathop{\longrightarrow}\limits_{k\to\infty}0, \tag{33}\]  
_where \(d(x_{k},J)\triangleq\inf\limits_{y\in J}\|x_{k}-y\|\). Denote by \(\overline{J}\) the closure of \(J\) and by \(J^{*}\) the set of the limit points of \(\{x_{k}\}\). It holds that_  
\[d(x_{k},J^{*})\mathop{\longrightarrow}\limits_{k\to\infty}0, \tag{34}\]  
_and \(J^{*}\) is a closed connected subset of \(\overline{J}\)._It is direct to verify that if the root set of \(f(x)=0\) is a singleton, then under the conditions of Theorem 3 we have that \(d(x_{k},x^{0})\underset{k\to\infty}{\longrightarrow}0\) and \(J^{*}=J=\{x^{0}\}\). Proof. : We outline the proof. Denote by \(\{x_{n_{k}}\}_{k\geq 1}\) a convergent subsequence generated by (29) and (30). **Step 1. ** By A4.3, prove that for all \(k\) large enough and \(t>0\) small enough, there is no truncation for \(x_{l},\ l\in\{n_{k},\cdots,m(n_{k},t)\}\), that is,  
\[x_{l+1}=x_{l}+a_{l}y_{l+1},\ \ l\in\{n_{k},\cdots,m(n_{k},t)\}, \tag{35}\]  
and  
\[\|x_{l+1}-x_{l}\|\leq ct,\ \ \ l\in\{n_{k},\cdots,m(n_{k},t)\}. \tag{36}\]  
**Step 2. ** By the stability condition A4.2 and (35) and (36), prove that for SAAWET, the number of truncations is finite, that is, algorithms (29) and (30) evolve as the classical SAA after a finite number of steps. **Step 3. ** To establish the convergence of \(\{x_{k}\}_{k\geq 0}\). **Remark 6**. : _If it is a priori known that estimates \(\{x_{k}\}_{k\geq 0}\) generated from (29) and (30) are in a subspace \(S(\subset\mathbb{R}^{l})\), then for the convergence of \(\{x_{k}\}_{k\geq 0}\), we only need to verify the stability condition in \(J\cap S\) and in such a case assumption A4.2 is formulated as follows: A4.2 There exists a continuously differentiable function \(v(\cdot):\mathbb{R}^{l}\to\mathbb{R}\) such that_  
1. \(\sup_{\delta\leq d(x,l\cap S)\leq\Delta,\ x\in S}\triangledown v(x)^{T}f(x)<0, \ \ \ \forall\ 0<\delta<\Delta,\)__
2. _The set_ \(v(\int\cap S)\triangleq\{v(x),x\in J\}\) _is nowhere dense,_
3. _For_ \(x^{*}\in S\) _in (_29_), there exists a constant_ \(c_{0}>0\) _such that_ \(\|x^{*}\|<c_{0}\) _and_ \(v(x^{*})<\inf_{\|x\|=c_{0}}v(x)\)_._  
**Example 4**. : _Consider the root-seeking problem in Example 3. Assume that \(y_{k+1}=f(x_{k})+\varepsilon_{k+1}\) with \(\varepsilon_{k+1}-0.9\varepsilon_{k}=w_{k+1}+0.5w_{k}\) and \(\{w_{k}\}_{k\geq 1}\) being a sequence of iid Gaussian variables \(w_{k}\sim N(0,0.1^{2})\). In (29) and (30), choose \(M_{k}=2^{k+1},\ x^{*}=0.5\). By a direct calculation, it obtains that_  
\[ \begin{array}{llll}x_{10}=0.5&x_{50}=7.76&x_{100}=9.26\\ x_{200}=9.46&x_{300}=9.52&x_{400}=9.61.\end{array} \]  
From the above sections, we can see that SAAWET does not require that the observation noise is purely stochastic or the estimate sequence is bounded. In fact, it can be shown that conditions for convergence of SAAWET are the weakest possible in a certain sense [5]. In the next section, we will apply SAAWET to give a recursive algorithm for principal component analysis.