## 2 Centralized Stochastic Approximation Algorithm  
### Probabilistic Martingale Method  
We first give the detailed problem formulation of SAA. Assume that \(f(\cdot):\mathbb{R}^{l}\rightarrow\mathbb{R}^{l}\) is an unknown function with root \(x^{0}\), that is, \(f(x^{0})=0\). At time \(k\), assume that \(x_{k}\) is an estimate of \(x^{0}\) and the measurement of \(f(\cdot)\) at \(x_{k}\) is \(y_{k+1}\), that is,  
\[y_{k+1}=f(x_{k})+\epsilon_{k+1},\ \ k\geq 0, \tag{1}\]  
where \(\epsilon_{k+1}\) is the observation noise. With an arbitrary initial value \(x_{0}\), in [1] a recursive algorithm for searching the root \(x^{0}\) of \(f(\cdot)\) is introduced  
\[x_{k+1}=x_{k}+a_{k}y_{k+1},\ \ k\geq 0, \tag{2}\]  
where \(\{a_{k}\}_{k\geq 1}\) is the stepsize sequence which satisfies  
\[a_{k}>0,\ \ a_{k}\underset{k\rightarrow\infty}{\longrightarrow}0,\ \ \sum_{k=0}^{\infty}a_{k}=\infty. \tag{3}\]  
Assumption (3) requires that the stepsize sequence tends to zero, but the sum of the stepsizes goes to infinity. This indicates that the noise effect can be asymptotically reduced while the algorithm has the ability to search in the whole feasible domain. Example 1: _Assume that at time \(k\), the estimate \(x_{k}\) is very close to the root \(x^{0}\). Then there exists an \(\epsilon>0\) small enough, such that_  
\[\|x_{k}-x^{0}+a_{k}f(x_{k})\|<\epsilon. \tag{4}\] \begin{table}
\begin{tabular}{l c} \hline \(||v||_{r}||A||\) & \(L_{2}\) norm of vector \(v\), matrix \(A\) \\ \hline \(||v||_{1},||A||_{1}\) & \(L_{1}\) norm of vector \(v\), matrix \(A\) \\ \hline \(\mathbf{I}_{m}\) & \(m\times m\) identity matrix \\ \hline \(\mathbf{1}\) & Vector or matrix with all entries equal to \(1\) \\ \hline \(\mathbf{0}\) & Vector or matrix with all entries equal to \(0\) \\ \hline \(X^{T}\) & Transpose of matrix \(\mathbf{X}\) \\ \hline \(\mathrm{col}\{x_{1},\ldots,x_{m}\}\) & \(\mathrm{col}\{x_{1},\ldots,x_{m}\}\triangleq\{x_{1}^{T},\ldots,x_{m}^{T}\}^{T}\), stacks of vectors or matrices \(\{x_{1},\ldots,x_{m}\}\) \\ \hline \(\mathbb{I}_{A}(x)\) & Indicator function, \(\mathbb{I}_{A}(x)=1\) if \(x\in A,\mathbb{I}_{A}(x)=0\) otherwise \\ \hline \(\mathbb{E}[\cdot]\) & Expectation operator \\ \hline \(m(k,T)\) & \(m(k,T)\triangleq\max\{m:\sum_{i=k}^{m}a_{i}\leq T\}\) \\ \hline \(\sigma_{i,k}\) & Truncation number of agent \(i\) at time \(k\) \\ \hline \(\sigma_{i,k}\) & \(\sigma_{i,k}\triangleq\max_{j\in N_{i}(k)}\sigma_{j,k}\), where \(N_{i}(k)\) is the set of neighbors of agent \(i\) at time \(k\) \\ \hline \(\sigma_{k}\) & Largest truncation number of all agents at time \(k\), that is, \\  & \(\sigma_{k}=\max_{i\in\
u}\sigma_{i,k}=\max_{i\in\
u}\hat{\sigma}_{i,k}\) \\ \hline \end{tabular}
\end{table} 
Table 1: Notations. Then,_  
\[\|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}\]  
_From (5) it can be seen that if the stepsize sequence \(\{a_{k}\}_{k\geq 1}\) has a positive lower bound, then for the unbounded noises, such as Gaussian variables, the estimation error will not converge to zero. Thus, for the stepsize sequence \(\{a_{k}\}_{k\geq 1}\), \(a_{k}\underset{k\to\infty}{\longrightarrow}0\) is a necessary condition for convergence of SAA._  
**Example 2**. : _Consider the case \(\varepsilon_{k+1}\equiv 0\). If \(\sum_{k=0}^{\infty}a_{k}<\infty\) and \(f(\cdot)\) is bounded, then_  
\[\sum_{k=0}^{\infty}\|x_{k+1}-x_{k}\|\leq\sum_{k=0}^{\infty}a_{k}\|f(x_{k})\|<\infty. \tag{6}\]  
_If the initial value \(x_{0}\) satisfies \(\|x_{0}-x^{0}\|-\sum_{k=0}^{\infty}a_{k}\|f(x_{k})\|>0\), then from (6) it follows that_  
\[\|x_{k+1}-x^{0}\|=\|x_{k+1}-x_{0}+x_{0}-x^{0}\|\geq\|x_{0}-x^{0}\|-\sum_{k=0}^ {\infty}\|x_{k+1}-x_{k}\|>0, \tag{7}\]  
_and \(\{x_{k}\}_{k\geq 0}\) will not converge to \(x^{0}\). Thus, \(\sum_{k=0}^{\infty}a_{k}=\infty\) is another necessary condition for convergence of SAA._  
We make the following assumptions.