An Introduction to Development of Centralized and Distributed Stochastic Approximation Algorithm with Expanding Truncations

Abstract

The stochastic approximation algorithm (SAA), starting from the pioneer work by Robbins and Monro in 1950s, has been successfully applied in systems and control, statistics, machine learning, and so forth. In this paper, we will review the development of SAA in China, to be specific, the stochastic approximation algorithm with expanding truncations (SAAWET) developed by Han-Fu Chen and his colleagues during the past 35 years. We first review the historical development for the centralized algorithm including the probabilistic method (PM) and the ordinary differential equation (ODE) method for SAA and the trajectory-subsequence method for SAAWET. Then, we will give an application example of SAAWET to the recursive principal component analysis. We will also introduce the recent progress on SAAWET in a networked and distributed setting, named the distributed SAAWET (DSAAWET).

1. Introduction

SAA was first introduced by Robbins and Monro in 1950s [1] and is also called the RM algorithm in the literature. Since the 1950s, SAA has found successful applications in systems and control, statistics, machine learning, the stochastic arithmetic, and the CESTAC method for numerical calculation [2,3], energy internet [4], and so forth, and there are plenty of studies on various theoretical properties of SAA, including the sample path convergence [1,5,6,7], the weak convergence [8], convergence of time-varying root-searching functions [9,10,11,12], robustness of SAA [13], stable and unstable limit points [14], convergence rate and asymptotic normality [7,15,16,17,18,19,20], and so forth. In this paper, due to space limitations, we will not give an overview of all aspects of SAA, but focus on the sample path analysis of this kind of algorithm, and particularly introduce the centralized and distributed SAAWET developed by Han-Fu Chen and his colleagues during the past 35 years.

At the early stage of SAA, to guarantee the convergence of the algorithm, it usually requires restrictive conditions on the noise ${\{{\epsilon }_k\}}_{k\ge 0}$ and the function $f(·)$, for example, ${\{{\epsilon }_k\}}_{k\ge 0}$ being a martingale difference sequence and $f(·)$ being bounded by a linear function. Then, by tools from the probability theory, such as the martingale theory, the almost sure convergence of SAA can be established and such an analysis method is called the probabilistic method (PM) [1,20]. However, in many situations, the noise ${\{{\epsilon }_k\}}_{k\ge 0}$ may not be a martingale difference sequence, and it may depend on the past estimates generated by SAA itself, which we call the state-dependent noise, and in such cases, PM fails. Towards relaxing the restrictive conditions in PM, in the 1970s a so-called ordinary differential equation (ODE) method was introduced [7,21], which transforms the convergence analysis of SAA into the stability of the equilibrium point of an associated ODE and forms another representative direction for theoretical analysis of SAA. For the ODE method, it a priori assumes that the estimate sequence generated by the algorithm is bounded, which is not easy to be verified in practice. For many theoretical problems, due to the complexity of the system noise and less a priori information on the estimate sequence, neither PM nor the ODE method can be applied.

In order to essentially relax the assumptions required by PM and the ODE method, in the past 35 years an expanding truncation technique was introduced into SAA by Han-Fu Chen and his colleagues, and a so-called stochastic approximation algorithm with expanding truncations (SAAWET) has been developed [22,23]. The key idea of the expanding truncation technique lies in that if the magnitude of the estimate exceeds the truncation bound, then the estimate is reset to the initial value but with a decreased stepsize, and, at the same time, an enlarged truncation bound will be used for the next recursion, while if the magnitude of estimate is smaller than the truncation bound, then SAAWET evolves as the classical SAA in the next recursion and the truncation bound remains unchanged. The expanding truncation technique introduces a way of adaptively choosing the step-sizes of the algorithm and essentially relaxes the conditions on the noises and the root-searching function. Furthermore, to guarantee the convergence of SAAWET, one only needs to verify the noise condition along the index sequence ${\{n_k\}}_{k\ge 0}$ of any convergent subsequence ${\{x_{n_k}\}}_{k\ge 0}$ rather than along the whole sequence ${\{x_k\}}_{k\ge 0}$, which greatly facilitates the application of such an algorithm. The convergence analysis method of SAAWET is accordingly named the trajectory-subsequence (TS) method. In the past 35 years, SAAWET has successfully been applied to recursive identification of a multivariate ARMAX system [24], recursive identification of nonlinear systems [25,26], adaptive regulation of a nonlinear system [27], consensus control of multiagent systems [28], convergence of a distributed randomized PageRank algorithm [29], and so forth. In this paper, we first review the probabilistic method (PM) and the ordinary differential equation (ODE) method for SAA and the trajectory-subsequence method for SAAWET. Then, we will give an application example of SAAWET to the recursive principal component analysis.

All the above algorithms and methods are applied in a centralized situation. In recent years, distributed algorithms have been extensively investigated—for example, the consensus problem [30,31], distributed estimation [32,33], and so on. The distributed algorithms work in a network situation, where there is no central agent collecting and processing the data over the whole network but the agents cooperatively accomplish a global objective by using their local observations and information obtained from communication with their adjacent neighbours [34,35,36,37,38]. Recently, many distributed problems have been solved by SAA-based algorithms, such as distributed estimation [32,39], and distributed convex optimization [34,35]. As a result, the distributed algorithm for SAA has naturally drawn much attention from researchers. Distributed SAA (DSAA) was proposed in [40,41,42,43] and so forth, in which agents cooperatively find roots of a function, being a sum of local functions associated with agents connected in a network. It is noticed that almost all the above DSAA algorithms require restrictive conditions to guarantee convergence; for example, in [41] it requires the global Lipschitz continuity of local functions and the observation noise as a martingale difference sequence. However, these assumptions may not hold for many problems, including the distributed principal component analysis and the distributed gradient-free optimization, and so forth. Aiming at solving the distributed root-seeking problem under weaker conditions compared with those used in [41], a distributed version of SAAWET (DSAAWET) was recently developed [44]. In this paper, we will introduce DSAAWET and its convergence properties and also give some application examples of DSAAWET.

The rest of the paper is arranged as follows. In Section 2, the centralized SAA and PM, as well as the ODE method for its convergence analysis are reviewed. Then, SAAWET is introduced with the conditions for its convergence analysis and its general convergence theorem given. In this paper, SAAWET is also applied to solve the recursive principal component analysis problem. In Section 3, DSAAWET and its convergence properties are introduced, and some application examples are given as well. In Section 4, some concluding remarks are addressed. The notations used in this paper are listed in

Table 1. Notations.

$||v||,||A||$	$L_2$ norm of vector v, matrix A
${||v||}_1{,||A||}_1$	$L_1$ norm of vector v, matrix A
${\mathbf{I}}_m$	$m\times m$ identity matrix
$\mathbf{1}$	Vector or matrix with all entries equal to 1
$\mathbf{0}$	Vector or matrix with all entries equal to 0
$X^T$	Transpose of matrix X
$\mathrm{col}\{x_1,\cdots ,x_m\}$	$\mathrm{col}\{x_1,\cdots ,x_m\}\triangleq {\{x_1^T,\cdots ,x_m^T\}}^T$, stacks of vectors or matrices $\{x_1,\cdots ,x_m\}$
${\mathbb{I}}_A\left(x\right)$	Indicator function, ${\mathbb{I}}_A\left(x\right)=1$ if $x\in A$, ${\mathbb{I}}_A\left(x\right)=0$ otherwise
$\mathbb{E}[·]$	Expectation operator
$m(k,T)$	$m(k,T)\triangleq max\{m:{\sum }_{i=k}^m{a}_i\le T\}$
${\sigma }_{i,k}$	Truncation number of agent i at time k
${\widehat{\sigma }}_{i,k}$	${\widehat{\sigma }}_{i,k}\triangleq {max}_{j\in N_i\left(k\right)}{\sigma }_{j,k}$, where $N_i\left(k\right)$ is the set of neighbors of agent i at time k
${\sigma }_k$	Largest truncation number of all agents at time k, that is, ${\sigma }_k={max}_{i\in \mathcal{V}}{\sigma }_{i,k}={max}_{i\in \mathcal{V}}{\widehat{\sigma }}_{i,k}$

.

2. Centralized Stochastic Approximation Algorithm

2.1. Probabilistic Martingale Method

We first give the detailed problem formulation of SAA.

Assume that $f(·):{\mathbb{R}}^l\to {\mathbb{R}}^l$ is an unknown function with root $x^0$, that is, $f\left(x^0\right)=0$. At time k, assume that $x_k$ is an estimate of $x^0$ and the measurement of $f(·)$ at $x_k$ is $y_{k+1}$, that is,

$$\begin{array}{c}\hfill y_{k+1}=f\left(x_k\right)+{\epsilon }_{k+1},k\ge 0,\end{array}$$

(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(·)$ is introduced

$$\begin{array}{c}\hfill x_{k+1}=x_k+a_k{y}_{k+1},k\ge 0,\end{array}$$

(2)

where ${\{a_k\}}_{k\ge 1}$ is the stepsize sequence which satisfies

$$\begin{array}{c}\hfill a_k>0,a_k\underset{k\to \infty }{⟶}0,\sum _{k=0}^{\infty }{a}_k=\infty .\end{array}$$

(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

$$\begin{array}{c}\hfill \parallel x_k-x^0+a_{k}f\left(x_k\right)\parallel <\epsilon .\end{array}$$

(4)

Then,

$$\begin{array}{c}\hfill \parallel x_{k+1}-x^0\parallel =\parallel x_k-x^0+a_{k}f\left(x_k\right)+a_k{\epsilon }_{k+1}\parallel \ge \parallel a_k{\epsilon }_{k+1}\parallel -\epsilon .\end{array}$$

(5)

From (5) it can be seen that if the stepsize sequence ${\{a_k\}}_{k\ge 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\ge 1}$, $a_k\underset{k\to \infty }{⟶}0$ is a necessary condition for convergence of SAA.

Example 2.

Consider the case ${\epsilon }_{k+1}\equiv 0$. If ${\sum }_{k=0}^{\infty }{a}_k<\infty$ and $f(·)$ is bounded, then

$$\begin{array}{c}\hfill \sum _{k=0}^{\infty }\parallel x_{k+1}-x_k\parallel \le \sum _{k=0}^{\infty }{a}_k\parallel f\left(x_k\right)\parallel <\infty .\end{array}$$

(6)

If the initial value $x_0$ satisfies $\parallel x_0-x^0\parallel -{\displaystyle \sum _{k=0}^{\infty }}{a}_k\parallel f\left(x_k\right)\parallel >0$, then from (6) it follows that

$$\begin{array}{c}\hfill \parallel x_{k+1}-x^0\parallel =\parallel x_{k+1}-x_0+x_0-x^0\parallel \ge \parallel x_0-x^0\parallel -\sum _{k=0}^{\infty }\parallel x_{k+1}-x_k\parallel >0,\end{array}$$

(7)

and ${\{x_k\}}_{k\ge 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.

A2.1

The stepsize sequence ${\{a_k\}}_{k\ge 0}$ satisfies

$$\begin{array}{c}\hfill a_k>0,\sum _{k=0}^{\infty }{a}_k=\infty ,\sum _{k=0}^{\infty }{a}_k^2<\infty .\end{array}$$

(8)

A2.2

There exists a twice-differentiable function $v(·):{\mathbb{R}}^l\to \mathbb{R}$, such that:

(i)

The Hessian matrix of $v(·)$ is bounded.

(ii)

$v\left(x^0\right)=0,v\left(x\right)>0,\forall x\ne x^0$ and $v\left(x\right)\to \infty$ as $\parallel x\parallel \to \infty$.

(iii)

For any $\epsilon >0$, there exists an ${\beta }_{\epsilon }>0$ such that

$$\begin{array}{c}\hfill \underset{\parallel x-x^0\parallel >\epsilon }{sup}▿v{\left(x\right)}^{T}f\left(x\right)=-{\beta }_{\epsilon }<0.\end{array}$$

(9)

A2.3

${\{{\epsilon }_k,{\mathcal{F}}_k\}}_{k\ge 0}$ is an m.d.s., that is, $E[{\epsilon }_{k+1}|{\mathcal{F}}_k]=0,k\ge 0$ and further, ${sup}_{k\ge 0}E{\parallel {\epsilon }_k\parallel }^2<\infty$.

A2.4

There exists a constant $c>0$ such that

$$\begin{array}{c}\hfill {\parallel f\left(x\right)\parallel }^2+E[\parallel {\epsilon }_{k+1}{\parallel }^2|{\mathcal{F}}_k]<c(1+v\left(x\right)),k\ge 0.\end{array}$$

(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(·)$ almost surely, that is,

$$\begin{array}{c}\hfill x_k\underset{k\to \infty }{⟶}{x}^0\mathrm{a}.\mathrm{s}.\end{array}$$

(11)

Proof. 

Here, we list the sketch of the proof.

By using the function $v(·)$ given in A2.2, define $v_{k+1}$:

$$\begin{array}{c}\hfill v_{k+1}\triangleq (1+v\left(x_{k+1}\right))\prod _{i=k+1}^{\infty }(1+a_i^2),\end{array}$$

(12)

By (9), we can obtain

$$\begin{array}{cc}\hfill 0\le & E(v_{k+1}|{\mathcal{F}}_k)\hfill \\ \hfill \le & v_k+a_k▿v{\left(x_k\right)}^{T}f\left(x_k\right)\prod _{i=k+1}^{\infty }(1+a_i^2)\hfill \\ \hfill \le & v_k+a_k▿v{\left(x_k\right)}^{T}f\left(x_k\right)\le v_k.\hfill \end{array}$$

(13)

By the properties of a nonnegative supermartingale, we have that ${\{v_k\}}_{k\ge 0}$ converges almost surely. Noting (8), we further obtain ${\prod }_{i=k+1}^{\infty }(1+a_i^2)\underset{k\to \infty }{⟶}1$ and thus, ${\{v\left(x_k\right)\}}_{k\ge 0}$ converges almost surely.

With an arbitrary $\epsilon >0$, define

$$\begin{array}{c}\hfill G_{\epsilon }\triangleq \{x:\parallel x-x^0\parallel >\epsilon \}\end{array}$$

(14)

and a stopping sequence ${\{{\sigma }_{\epsilon }^i\}}_{i\ge 0}$:

$$\begin{array}{c}\hfill {\sigma }_{\epsilon }^i=min\{t:t>{\sigma }_{\epsilon }^{i-1},x_t\in G_{\epsilon }^c\}.\end{array}$$

(15)

By (13) and (14) and noting (9), we have

$$\begin{array}{c}\hfill E[v_{k+1}|{\mathcal{F}}_k]\le v_k-{\beta }_{\epsilon }{a}_k{I}_{[{\sigma }_{\epsilon }^i>k]}.\end{array}$$

(16)

From (16) and by the properties of the supermartingale, we have

$$\begin{array}{c}\hfill \sum _{k=1}^{\infty }{a}_k{I}_{[{\sigma }_{\epsilon }^i>k]}<\infty \mathrm{a}.\mathrm{s}.\end{array}$$

(17)

By (17) and (8), we can prove that ${\sigma }_{\epsilon }^i$ is finite almost surely, and there exists a subsequence ${\{x_{k_i}\}}_{i\ge 1}$ which satisfies $\parallel x_{k_i}-x^0\parallel \le \epsilon$. Since $\epsilon >0$ can be arbitrarily small, we know that there exists a subsequence of ${\{x_{k_i}\}}_{i\ge 0}$ which converges to $x^0$. By the convergence of ${\{v\left(x_k\right)\}}_{k\ge 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

$$\begin{array}{c}\hfill \underset{\parallel x-x^0\parallel >\epsilon }{inf}▿v{\left(x\right)}^{T}f\left(x\right)={\beta }_{\epsilon }>0,\end{array}$$

(18)

then we can prove the almost sure convergence of the following SAA

$$\begin{array}{c}\hfill x_{k+1}=x_k-a_k{y}_{k+1},k\ge 0.\end{array}$$

(19)

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, ${\epsilon }_{k+1}={\epsilon }_{k+1}\left(x_k\right)$. On the other hand, if we choose $v\left(x\right)=\parallel x-x^0{\parallel }^2$, then from A2.4 we have

$$\begin{array}{c}\hfill {\parallel f\left(x\right)\parallel }^2\le c(1+\parallel x-x^0{\parallel )}^2,\end{array}$$

(20)

which indicates that $f(·)$ is bounded by a linear function. These are restrictions for PM.

2.2. Ordinary Differential Equation Method

We first introduce two technical lemmas.

Lemma 1.

(Arzelà-Ascoli, [47]) Let $\{f_{\lambda }\left(t\right),t\in [0,+\infty ),\lambda \in \Lambda \}$ be a function class satisfying the condition of uniform boundedness and equi-continuity. Then there exists a continuous function $f\left(t\right)$ and a subsequence ${\{f_{{\lambda }_k}\left(t\right)\}}_{k\ge 1}$ such that ${\{f_{{\lambda }_k}\left(t\right)\}}_{k\ge 1}$ converges to $f\left(t\right)$ uniformly on any fixed bounded interval in $[0,+\infty )$.

Remark 3.

For the function class $\{f_{\lambda }\left(t\right),t\in [0,+\infty ),\lambda \in \Lambda \}$, the equi-continuity means that for any $\epsilon >0$, there exists $\delta >0$ such that for any $|t-s|<\delta$,

$$\begin{array}{c}\hfill i{f}_{\lambda }\left(t\right)-f_{\lambda }\left(s\right)|<\epsilon ,\forall \lambda \in \Lambda .\end{array}$$

(21)

The following result is well-known for the Lyapunov stability of ODE.

Lemma 2.

Consider the ODE

$$\begin{array}{c}\hfill \dot{x}\left(t\right)=f\left(x\left(t\right)\right),t\ge 0\end{array}$$

(22)

with an equilibrium point $x^0$, that is, $f\left(x^0\right)=0$. If there exists a continuously differentiable $v\left(x\right)$ such that

(i)

$v\left(x^0\right)=0$;

(ii)

$v\left(x\right)>0,\forall x\ne x^0$; $v\left(x\right)\underset{\parallel x\parallel \to \infty }{⟶}\infty$;

(iii)

$▿v{\left(x\right)}^{T}f\left(x\right)<0,\forall x\ne x^0;$

then $x^0$ is the globally stable solution of (22).

Before introducing the conditions and the results for the ODE method, we first introduce a crucial notation to be used in this paper. For any $T>0$, define

$$\begin{array}{c}\hfill m(n,T)\triangleq max\left\{m:\sum _{i=n}^m{a}_i\le T\right\}.\end{array}$$

(23)

From the definition in (23) we can see that $m(n,T)$ is the maximal number of steps starting from n with the sum of stepsizes not exceeding T. Noting that $a_k\to 0$ as $k\to \infty$, we have that $m(n,T)\to \infty$ as $n\to \infty$.

We make the following assumptions.

A3.1

$a_k>0,a_k{⟶}_{k\to \infty }0,{\sum }_{k=0}^{\infty }{a}_k=\infty .$

A3.2

There exists a twice-differentiable function $v(·):{\mathbb{R}}^l\to \mathbb{R}$ such that

(i)

$v\left(x^0\right)=0$;

(ii)

$v\left(x\right)>0,\forall x\ne x^0$ and $v\left(x\right)\to \infty$ as $\parallel x\parallel \to \infty$;

(iii)

$▿v{\left(x\right)}^{T}f\left(x\right)<0,\forall x\ne x^0.$

A3.3

The noise ${\{{\epsilon }_k\}}_{k\ge 0}$ satisfies

$$\begin{array}{c}\hfill \underset{T\to 0}{lim}\underset{n\to \infty }{lim\; sup}\frac{1}{T}∥\sum _{i=n}^{m(n,T)}{a}_i{\epsilon }_{i+1}∥=0,a_k{\epsilon }_{k+1}\underset{k\to \infty }{⟶}0.\end{array}$$

(24)

A3.4

The function $f(·)$ is continuous.

Remark 4.

If the stepsizes further satisfy ${\sum }_{k=0}^{\infty }{a}_k^2<\infty$ and the noise ${\{{\epsilon }_k,{\mathcal{F}}_k\}}_{k\ge 0}$ is an m.d.s. and ${sup}_{k\ge 0}E[\parallel {\epsilon }_{k+1}{\parallel }^2|{\mathcal{F}}_k]<\infty \mathrm{a}.\mathrm{s}.$, then it can be directly verified that ${\sum }_{k=0}^{\infty }{a}_k{\epsilon }_{k+1}<\infty$, and hence, A3.3 holds. If the noise is not stochastic but satisfies ${\epsilon }_k\underset{k\to \infty }{⟶}0$, then A3.3 also holds. In this regard, (24) is more general compared with A2.3.

We give the following result for the ODE method.

Theorem 2.

([6,7,21]) Consider the sample path ω where A3.3 takes place. If A3.1, A3.2, and A3.4 hold on the sample path ω and ${\{x_k\left(\omega \right)\}}_{k\ge 0}$ is bounded, then

$$\begin{array}{c}\hfill x_k\left(\omega \right)\underset{k\to \infty }{⟶}{x}^0.\end{array}$$

(25)

Proof. 

We sketch the proof.

Define $t_k\triangleq {\sum }_{i=0}^k{a}_i$ with $t_0=0.$ By interpolating the estimates generated from (2), we have a sequence of continuous functions

$$\begin{array}{cc}\hfill & x_t^0\triangleq \frac{t_k-t}{a_k}{x}_{k-1}+\frac{t-t_{k-1}}{a_k}{x}_k,t\in [t_{k-1},t_k],\hfill \end{array}$$

(26)

$$\begin{array}{cc}\hfill & x_k\left(t\right)=x_{t+k}^0,k\ge 1,\hfill \end{array}$$

(27)

which can be proved to be bounded by the boundedness of ${\{x_k\}}_{k\ge 0}$ and uniform continuity by A3.3.

Then by Lemma 1, we can prove that there exists a subsequence ${\{x_{n_k}\left(t\right)\}}_{k\ge 0}$ converging a continuous function $x\left(t\right)$ satisfying the following ODE

$$\begin{array}{c}\hfill \dot{x}\left(t\right)=f\left(x\left(t\right)\right).\end{array}$$

(28)

By A3.2 and Lemma 2 we can further prove that the equilibrium point $x^0$ is globally stable and the estimates ${\{x_k\}}_{k\ge 0}$ converge to $x^0$ on the sample path $\omega$. □

The essential idea of the above proof is to transform the convergence of a recursive algorithm to the stability of an associated ODE, and thus the analysis method is called the ODE method. From assumption A3.3 we can see that the ODE method has a wider application potential than the PM method. However, the boundedness assumption on the estimate sequence is still restrictive. Aiming at removing this condition and further relaxing the technical assumptions on the noise and the root-seeking function, in the next section we will introduce the SAA with expanding truncations (SAAWET) and its general convergence theorem.

2.3. SAAWET and Trajectory-Subsequence Method

We first give an example.

Example 3.([5]) Consider the root-seeking of the function $f\left(x\right)=-{(x-10)}^3$ and assume that the observation noise ${\epsilon }_k\equiv 0$.

(i)

If we choose the initial value $x_0=0$ and the stepsize $a_k=\frac{1}{k+1}$, it can be directly verified that the estimates generated from (2)

$$x_0=0,x_1=1000,x_2=-\mathrm{485,148,500},x_3\approx 3.8\times {10}^{25},\cdots$$

(ii)

If we choose the initial value $x_0=0$ and the stepsize $a_k=\frac{1}{k+{10}^3}$, it can be directly verified that the estimates generated from (2) is convergent, that is, $x_k\underset{k\to \infty }{⟶}10$.

For Example 3, neither the growth rate condition on $f(·)$ used by PM nor the boundedness condition on the estimate sequence used by the ODE method take place. On the other hand, if we can choose the stepsize in an adaptive manner, estimates generated from SAA may still converge. The core idea of SAAWET consists in adaptively choosing the stepsizes. Let us describe it.

Denote by J the root set of an unknown function $f(·):{\mathbb{R}}^l\to {\mathbb{R}}^l$, that is, $f\left(x^0\right)=0$ $\forall x^0\in J$. Choose ${\{M_k\}}_{k\ge 0}$ a positive sequence increasingly diverging to infinity, $M_k\underset{k\to \infty }{⟶}\infty$. With an arbitrary initial value $x_0\in {\mathbb{R}}^l$, the estimate sequence ${\{x_k\}}_{k\ge 1}$ is generated by the following SAAWET:

$$\begin{array}{cc}\hfill x_{k+1}=& (x_k+a_k{y}_{k+1})I_{[\parallel x_k+a_k{y}_{k+1}\parallel \le M_{{\sigma }_k}]}+x^{*}{I}_{[\parallel x_k+a_k{y}_{k+1}\parallel >M_{{\sigma }_k}]},\hfill \end{array}$$

(29)

$$\begin{array}{cc}\hfill {\sigma }_k=& {\sigma }_{k-1}+I_{[\parallel x_{k-1}+a_{k-1}{y}_k\parallel >M_{{\sigma }_{k-1}}]},{\sigma }_0=0,\hfill \end{array}$$

(30)

where

$$\begin{array}{c}\hfill y_{k+1}=f\left(x_k\right)+{\epsilon }_{k+1},\end{array}$$

(31)

$y_{k+1}$ is the observation of $f(·)$ at $x_k$, ${\epsilon }_{k+1}$ is the observation noise, $a_k$ is the stepsize and $x_k$ is the estimate for the root set of $f(·)$ at time k.

From (29) and (30), we can see that if the magnitude of $x_k+a_k{y}_{k+1}$ is located in the truncation bound, then the algorithm evolves as the classical SAA (2), while if the magnitude of $x_k+a_k{y}_{k+1}$ exceeds the truncation bound, then $x_{k+1}$ is pulled back to $x^{*}$ with the truncation bound being enlarged and the stepsize being reduced for the next recursion.

We first list conditions for theoretical analysis.

A4.1

$a_k>0,a_k\underset{k\to \infty }{⟶}0,{\displaystyle \sum _{k=1}^{\infty }}{a}_k=\infty$;

A4.2

There exists a continuously differentiable function $v(·):{\mathbb{R}}^l\to \mathbb{R}$ such that

(i)

$\underset{\delta \le d(x,J)\le \Delta }{sup}▿v{\left(x\right)}^{T}f\left(x\right)<0,\forall 0<\delta <\Delta$,

(ii)

The set $v\left(J\right)\triangleq \{v(x),x\in J\}$ is nowhere dense,

(iii)

For $x^{*}\in {\mathbb{R}}^l$ in (29), there is a $c_0>0$ such that $\parallel x^{*}\parallel <c_0$ and $v\left(x^{*}\right)<\underset{\parallel x\parallel =c_0}{inf}v\left(x\right)$,

A4.3

On the sample path $\omega$, for any convergent subsequence ${\{x_{n_k}\}}_{k\ge 1}$ generated from (29) and (30), it holds that

$$\begin{array}{c}\hfill \underset{T\to 0}{lim}\underset{k\to \infty }{lim\; sup}\frac{1}{T}∥{\displaystyle \sum _{i=n_k}^{m(n_k,T_k)}}{a}_i{\epsilon }_{k+1}∥=0,\forall T_k\in (0,T],\end{array}$$

(32)

with $m(n_k,T_k)\triangleq max\left\{m:{\displaystyle \sum _{i=n_k}^m}{a}_i\le T_k\right\}$;

A4.4

The function $f(·)$ is measurable and locally bounded.

Remark 5.

A set being nowhere dense means that the set of the interior points of its closure is empty. It is clear that a set with a single point is nowhere dense. Note that for the noise condition A3.3, it only requires to verify (32) on a fixed sample path and along the index of any convergent subsequence, which compared with (24) is much easier to be verified in practice. In this regard, the analysis method for SAAWET is called the trajectory-subsequence (TS) method.

Theorem 3.

([5]) For SAAWET (29) and (30), if A4.1, A4.2 and A4.4 hold, then on the sample path ω where A4.3 takes place, it holds that

$$\begin{array}{c}\hfill d(x_k,J)\underset{k\to \infty }{⟶}0,\end{array}$$

(33)

where $d(x_k,J)\triangleq \underset{y\in J}{inf}\parallel x_k-y\parallel$. Denote by $\overline{J}$ the closure of J and by $J^{*}$ the set of the limit points of $\{x_k\}$. It holds that

$$\begin{array}{c}\hfill d(x_k,J^{*})\underset{k\to \infty }{⟶}0,\end{array}$$

(34)

and $J^{*}$ is a closed connected subset of $\overline{J}$.

It is direct to verify that if the root set of $f\left(x\right)=0$ is a singleton, then under the conditions of Theorem 3 we have that $d(x_k,x^0)\underset{k\to \infty }{⟶}0$ and $J^{*}=J=\{x^0\}$.

Proof. 

We outline the proof.

Denote by ${\{x_{n_k}\}}_{k\ge 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,

$$\begin{array}{c}\hfill x_{l+1}=x_l+a_l{y}_{l+1},l\in \{n_k,\cdots ,m(n_k,t)\},\end{array}$$

(35)

and

$$\begin{array}{c}\hfill \parallel x_{l+1}-x_l\parallel \le ct,l\in \{n_k,\cdots ,m(n_k,t)\}.\end{array}$$

(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\ge 0}$. □

Remark 6.

If it is a priori known that estimates ${\{x_k\}}_{k\ge 0}$ generated from (29) and (30) are in a subspace $S(\subset {\mathbb{R}}^l)$, then for the convergence of ${\{x_k\}}_{k\ge 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(·):{\mathbb{R}}^l\to \mathbb{R}$ such that

(i)

$\underset{\delta \le d(x,J\cap S)\le \Delta ,x\in S}{sup}▿v{\left(x\right)}^{T}f\left(x\right)<0,\forall 0<\delta <\Delta$,

(ii)

The set $v(J\cap S)\triangleq \{v(x),x\in J\}$ is nowhere dense,

(iii)

For $x^{*}\in S$ in (29), there exists a constant $c_0>0$ such that $\parallel x^{*}\parallel <c_0$ and $v\left(x^{*}\right)<{inf}_{\parallel x\parallel =c_0}v\left(x\right)$.

Example 4.

Consider the root-seeking problem in Example 3. Assume that $y_{k+1}=f\left(x_k\right)+{\epsilon }_{k+1}$ with ${\epsilon }_{k+1}-0.9{\epsilon }_k=w_{k+1}+0.5w_k$ and ${\{w_k\}}_{k\ge 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}{ccc}{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.

2.4. Recursive Principal Component Analysis Algorithm

Before introducing the recursive algorithm, we first make the following assumption.

A5.1

$\{A,A_k,k\ge 1\}$ are $n\times n$ symmetric matrices. A is unknown and ${\{A_k\}}_{k\ge 1}$ is the observation sequence of A satisfying $A_k\underset{k\to \infty }{⟶}A$.

The principal component analysis algorithm considered in this paper aims at estimating the eigenvalues and eigenvectors based on the observation sequence ${\{A_k\}}_{k\ge 1}$. Since A is unknown, if we perform SVD or QR decomposition for each $A_k,k\ge 1$, it would be rather time-consuming. In the following, we will introduce a SAAWET-based recursive algorithm for solving the problem.

The eigenvectors of matrix A are recursively estimated as follows:

Choose the stepsize $a_k=\frac{1}{k}$ and any initial values $u_0^{\left(1\right)}\in {\mathbb{R}}^n$ with unit modular and define

$$\begin{array}{cc}\hfill {\tilde{u}}_{k+1}^{\left(1\right)}& =u_k^{\left(1\right)}-a_k{A}_k{u}_k^{\left(1\right)}.\hfill \end{array}$$

(37)

If $\parallel {\tilde{u}}_{k+1}^{\left(1\right)}\parallel \ne 0$, then

$$\begin{array}{cc}\hfill u_{k+1}^{\left(1\right)}& ={\tilde{u}}_{k+1}^{\left(1\right)}/\parallel {\tilde{u}}_{k+1}^{\left(1\right)}\parallel .\hfill \end{array}$$

(38)

Otherwise, $\parallel {\tilde{u}}_{k+1}^{\left(1\right)}\parallel =0$ and reset $u_{k+1}^{\left(1\right)}$ as another vector with a unit modular.

Assume that $u_k^{\left(i\right)},i=1,\cdots ,j$ have been well-defined. Next, we inductively define the estimation algorithm for $u_k^{(j+1)}$.

Define the $n\times j$-matrix

$$V_k^{\left(j\right)}\triangleq \left[\begin{array}{cccc}{u}_k^{\left(1\right)}& P_k^{\left(1\right)}{u}_k^{\left(2\right)}& \cdots & P_k^{(j-1)}{u}_k^{\left(j\right)}\end{array}\right],$$

where $P_k^{\left(i\right)}\triangleq I-V_k^{\left(i\right)}{V}_k^{\left(i\right)+},i=1,\cdots ,j-1$ and $V_k^{\left(i\right)+}$ is the pseudo inverse of $V_k^{\left(i\right)}$.

With an arbitrary initial vector $u_0^{(j+1)}$ with a unit modular, define

$$\begin{array}{cc}\hfill {\tilde{u}}_{k+1}^{(j+1)}& =P_k^{\left(j\right)}{u}_k^{(j+1)}-a_k{P}_k^{\left(j\right)}{A}_k{P}_k^{\left(j\right)}·u_k^{(j+1)}.\hfill \end{array}$$

(39)

If $\parallel {\tilde{u}}_{k+1}^{(j+1)}\parallel \ne 0$, then

$$\begin{array}{cc}\hfill u_{k+1}^{(j+1)}& ={\tilde{u}}_{k+1}^{(j+1)}/\parallel {\tilde{u}}_{k+1}^{(j+1)}\parallel .\hfill \end{array}$$

(40)

Otherwise, $\parallel {\tilde{u}}_{k+1}^{(j+1)}\parallel =0$ and reset $u_{k+1}^{(j+1)}$ as another vector denoted still by $u_{k+1}^{(j+1)}$ satisfying $\parallel u_{k+1}^{(j+1)}\parallel =1$ and $V_k^{\left(j\right)\tau }{u}_{k+1}^{(j+1)}=0$.

$\{u_k^{\left(1\right)},\cdots ,u_k^{\left(n\right)}\}$ serve as the estimates for eigenvectors of matrix A.

Based on $\{u_k^{\left(1\right)},\cdots ,u_k^{\left(n\right)}\}$, we introduce the recursive algorithms for estimating eigenvalues of matrix A.

Choose a positive sequence increasingly diverging to infinity, $M_{k+1}>M_k>0$, $M_k\underset{k\to \infty }{⟶}\infty$. With arbitrary initial values ${\lambda }_0^{\left(j\right)}$, ${\{{\lambda }_k^{\left(j\right)}\}}_{k\ge 1},j=1,\cdots ,n$ are generated by the following algorithms:

$$\begin{array}{cc}\hfill {\lambda }_{k+1}^{\left(j\right)}& =\left[{\lambda }_k^{\left(j\right)}-a_k\left({\lambda }_k^{\left(j\right)}-u_k^{\left(j\right)T}{A}_k{u}_k^{\left(j\right)}\right)\right]·I_{\left[\left|{\lambda }_k^{\left(j\right)}-a_k\left({\lambda }_k^{\left(j\right)}-u_k^{\left(j\right)T}{A}_k{u}_k^{\left(j\right)}\right)\right|\le M_{{\sigma }_k\left(j\right)}\right]},\hfill \end{array}$$

(41)

$$\begin{array}{cc}\hfill {\sigma }_k\left(j\right)& ={\displaystyle \sum _{i=1}^{k-1}}{I}_{\left[\left|{\lambda }_i^{\left(j\right)}-a_i\left({\lambda }_i^{\left(j\right)}-u_i^{\left(j\right)T}{A}_i{u}_i^{\left(j\right)}\right)\right|>M_{{\sigma }_i\left(j\right)}\right]},{\sigma }_0\left(j\right)=0,\hfill \end{array}$$

(42)

where ${\lambda }_k^{\left(j\right)}$ is the estimate for the eigenvalue corresponding to the eigenvector which $u_k^{\left(j\right)}$ estimates at time k.

Denote S the unit sphere in ${\mathbb{R}}^n$ and J the set of all eigenvectors with unit modular of matrix A. Denote the set of all eigenvalues of matrix A by $V\left(J\right)$, that is, $V\left(J\right)\triangleq \{{\lambda }^{\left(1\right)},\cdots ,{\lambda }^{\left(n\right)}\}$.

For algorithms (39)–(42), the following result takes place.

Theorem 4.

Assume that A5.1 holds.

(i)

There exists a closed-subset $J_j^{*}$ of J such that

$$\begin{array}{c}\hfill d\left(u_k^{\left(j\right)},J_j^{*}\right)\underset{k\to \infty }{⟶}0.\end{array}$$

(43)

(ii)

There exists ${\lambda }^{\left(j\right)}\in V\left(J\right)$ such that

$$d\left(u_k^{\left(j\right)T}A{u}_k^{\left(j\right)},{\lambda }^{\left(j\right)}\right)\underset{k\to \infty }{⟶}0,$$

and for any $v^{\left(j\right)}\in J_j^{*}$

$$A{v}^{\left(j\right)}={\lambda }^{\left(j\right)}{v}^{\left(j\right)}.$$

(iii)

${\lambda }_k^{\left(j\right)}$ converges to the eigenvalue ${\lambda }^{\left(j\right)}$ of matrix A and the limit set of ${\lambda }_k^{\left(j\right)},j=1,\cdots ,n$ coincides with $V\left(J\right)$.

Proof. 

Noting that ${\{u_k^{\left(j\right)}\}}_{k\ge 0},j=,\cdots ,n$ are with a unit modular, algorithms (39)–(42) are SAAWET. The proof can be obtained by applying Theorem 3 and Remark 5. Due to space limitations, the detailed proof is omitted. □

3. Distributed Stochastic Approximation Algorithm

In this section, we will introduce the distributed version of SAAWET (DSAAWET). The key difference from the existing distributed SAA, see for example, [40], lies in the expanding truncation mechanism that adaptively defines enclosing bounds. The theoretical results of DSAAWET guarantee that estimates generated by DSAAWET for all agents converge almost surely to a consensus set, which is contained in the root set of the sum function.

We first introduce the problem formulation.

Consider the case where all agents in a network cooperatively search the root of the sum function given by

$$\begin{array}{c}f(·)=\frac{1}{N}\sum _{i=1}^N{f}_i(·),\hfill \end{array}$$

(44)

where $f_i(·):{\mathbb{R}}^l\to {\mathbb{R}}^l$ is the local objective function which can only be observed by agent $i.$ Denote the root set of $f(·)$ by $J\triangleq \{x\in {\mathbb{R}}^l:f\left(x\right)=0\}$.

For any $i\in \mathcal{V}$, denote by $x_{i,k}\in {\mathbb{R}}^l$ the estimate for the root of $f(·)$ given by agent i at time k. Since at time $k+1$, agent i only has its local noisy observation

$$O_{i,k+1}=f_i\left(x_{i,k}\right)+{\epsilon }_{i,k+1},$$

(45)

where ${\epsilon }_{i,k+1}$ is the observation noise, to estimate the root of $f(·)$, all agents need to exchange information with adjacent agents via the topology of the network.

The topology of the network at time k is described by a digraph $\mathcal{G}\left(k\right)=\{\mathcal{V},\mathcal{E}(k)\}$, where $\mathcal{V}=\{1,\cdots ,N\}$ is the index set of all agents, and $\mathcal{E}\left(k\right)\subset \mathcal{V}\times \mathcal{V}$ is the edge set with $(j,i)\in \mathcal{E}\left(k\right)$ representing the information flow from agent j to agent i at time k. Denote the adjacency matrix of the network at time k by $W\left(k\right)={\left[{\omega }_{ij}\left(k\right)\right]}_{i,j=1}^N$, where ${\omega }_{ij}\left(k\right)>0$ if, and only if $(j,i)\in \mathcal{E}\left(k\right)$, and ${\omega }_{ij}\left(k\right)=0$, otherwise. Denote by $N_i\left(k\right)=\{j\in \mathcal{V}:(j,i)\in \mathcal{E}\left(k\right)\}$ the set of neighbors of agent i at time k.

We apply the idea of expanding truncation to the distributed estimation. Denote by $x_{i,k}$ the estimate for agent i at time k and by ${\sigma }_{i,k}$ the number of truncations for agent i up to time k. DSAAWET is given by (46)–(49) with any initial values $x_{i,0},$ where $O_{i,k+1}$ is defined by (45), $\{{\gamma }_k\}$ is the stepsize, $x^{*}\in {\mathbb{R}}^l$ is a vector known to all agents, ${\{M_k\}}_{k\ge 0}$ is a positive sequence increasingly diverging to infinity with $M_0\ge \parallel x^{*}\parallel$.

$$\begin{array}{cc}\hfill & {\sigma }_{i,0}=0,{\widehat{\sigma }}_{i,k}\stackrel{\Delta }{=}\underset{j\in N_i\left(k\right)}{max}{\sigma }_{j,k},\hfill \end{array}$$

(46)

$$\begin{array}{cc}\hfill & x_{i,k+1}^{\prime }=\left(\sum _{j\in N_i\left(k\right)}{\omega }_{ij}\left(k\right)(x_{j,k}{I}_{[{\sigma }_{j,k}={\widehat{\sigma }}_{i,k}]}+x^{*}{I}_{[{\sigma }_{j,k}<{\widehat{\sigma }}_{i,k}]})+{\gamma }_k{O}_{i,k+1}\right)I_{[{\sigma }_{i,k}={\widehat{\sigma }}_{i,k}]}+x^{*}{I}_{[{\sigma }_{i,k}<{\widehat{\sigma }}_{i,k}]},\hfill \end{array}$$

(47)

$$\begin{array}{cc}\hfill & x_{i,k+1}=x^{*}{I}_{[\Vert x_{i,k+1}^{\prime }\Vert >M_{{\widehat{\sigma }}_{i,k}}]}+x_{i,k+1}^{\prime }{I}_{[\Vert x_{i,k+1}^{\prime }\Vert \le M_{{\widehat{\sigma }}_{i,k}}]},\hfill \end{array}$$

(48)

$$\begin{array}{cc}\hfill & {\sigma }_{i,k+1}={\widehat{\sigma }}_{i,k}+I_{\left[\Vert x_{i,k+1}^{\prime }\Vert >M_{{\widehat{\sigma }}_{i,k}}\right]},\hfill \end{array}$$

(49)

Denote by

$${\sigma }_k\stackrel{\Delta }{=}\underset{i\in \mathcal{V}}{max}{\sigma }_{i,k}$$

(50)

the largest truncation number among all agents at time k. If $N=1,$ then by denoting ${\widehat{\sigma }}_{i,k}={\sigma }_{i,k}\triangleq {\sigma }_k,x_{i,k}\triangleq x_k,x_{i,k}^{\prime }\triangleq x_k^{\prime },O_{i,k}\triangleq O_k,$ (46)–(49) becomes

$$\begin{array}{cc}\hfill & x_{k+1}^{\prime }=x_k+{\gamma }_k{O}_{k+1},\hfill \\ \hfill & x_{k+1}=x^{*}{I}_{\left[\Vert x_{k+1}^{\prime }\Vert >M_{{\sigma }_k}\right]}+x_{k+1}^{\prime }{I}_{\left[\Vert x_{k+1}^{\prime }\Vert \le M_{{\sigma }_k}\right]},\hfill \\ \hfill & {\sigma }_{k+1}={\sigma }_k+I_{\left[\Vert x_{k+1}^{\prime }\Vert >M_{{\sigma }_k}\right],}\hfill \end{array}$$

which is the SAAWET in the centralized setting.

We first introduce assumptions to be used.

A5.1

${\gamma }_k>0,{\gamma }_k\underset{k\to \infty }{⟶}0$, and ${\sum }_{k=1}^{\infty }{\gamma }_k=\infty$.

A5.2

There exists a continuously differentiable function $v(·):{\mathbb{R}}^l\to \mathbb{R}$ such that

$$\begin{array}{ccc}& \left(\mathrm{a}\right)\underset{\delta \le d(x,J)\le \Delta }{sup}{f}^T\left(x\right)v_x\left(x\right)<0\hfill & \hfill \end{array}$$

(51)

for any $\Delta >\delta >0$, where $v_x(·)$ denotes the gradient of $v(·)$ and $d(x,J)={min}_y\{\Vert x-y\Vert :y\in J\}$,

(b) $v\left(J\right)\triangleq \{v(x):x\in J\}$ is nowhere dense,

(c) $\parallel x^{*}\parallel <c_0\mathrm{and}v\left(x^{*}\right)<{\inf }_{\parallel x\parallel =c_0}v\left(x\right)$ for some positive constant $c_0$, where $x^{*}$ is used in (47) and (48).

A5.3

The local functions $f_i(·)\forall i\in \mathcal{V}$ are continuous.

A5.4

(a) $W\left(k\right)\forall k\ge 0$ are doubly stochastic matrices (A matrix is said to be doubly stochastic if all entries being nonnegative and the sum of entries in each row and each column being 1.);

(b) There exists a constant $0<\eta <1$ such that

$${\omega }_{ij}\left(k\right)\ge \eta \forall j\in {\mathcal{N}}_i\left(k\right)\forall i\in \mathcal{V}\forall k\ge 0;$$

(c) The digraph ${\mathcal{G}}_{\infty }=\{\mathcal{V},{\mathcal{E}}_{\infty }\}$ is strongly connected, where ${\mathcal{E}}_{\infty }$ is the set of edges $(j,i)$ such that j is a neighbor of i which communicates with i infinitely often, that is,

$${\mathcal{E}}_{\infty }=\{(j,i):(j,i)\in \mathcal{E}\left(k\right)\mathrm{for}\mathrm{infinitely}\mathrm{many}\mathrm{indices}k\};$$

(d) There exists a positive integer B such that for every $(j,i)\in {\mathcal{E}}_{\infty }$, agent j sends information to the neighbor i at least once every B consecutive time slots, that is,

$$(j,i)\in \mathcal{E}\left(k\right)\cup \mathcal{E}(k+1)\cup \cdots \cup \mathcal{E}(k+B-1)$$

for all $(j,i)\in {\mathcal{E}}_{\infty }$ and any $k\ge 0.$

Remark 7.

Assumptions A5.1–A5.3 are similar to those conditions used in the centralized SAAWET. Since the DSAAWET is in a distributed setting, assumption A5.4 is a commonly used condition describing the topology of the network [34].

Next, we introduce the condition on the observation noises for each agent.

A5.5

For the sample path $\omega$ under consideration and for each agent i,

(a) ${\gamma }_k{\epsilon }_{i,k+1}\underset{k\to \infty }{⟶}0$, and

(b) ${lim}_{T\to 0}{lim\; sup}_{k\to \infty }\frac{1}{T}\Vert {\sum }_{m=n_k}^{m(n_k,t_k)}{\gamma }_m{\epsilon }_{i,m+1}{I}_{[\Vert x_{i,m}\Vert \le K]}\Vert =0$$\forall t_k\in [0,T]$ along indices $\{n_k\}$ whenever $\{x_{i,n_k}\}$ converges.

We now give the main results of DSAAWET.

Define the vectors $X_k\stackrel{\Delta }{=}\mathrm{col}\{x_{1,k},\cdots ,x_{N,k}\},{\epsilon }_k\stackrel{\Delta }{=}\mathrm{col}\{{\epsilon }_{1,k},\cdots ,{\epsilon }_{N,k}\},F\left(X_k\right)\stackrel{\Delta }{=}\mathrm{col}\{f_1\left(x_{1,k}\right),\cdots ,f_N\left(x_{N,k}\right)\}$. Denote by $X_{\perp ,k}\stackrel{\Delta }{=}{D}_{\perp }{X}_k$ the disagreement vector of $X_k$ with $D_{\perp }\triangleq ({\mathbf{I}}_N-\frac{\mathbf{1}{\mathbf{1}}^T}{N})\otimes {\mathbf{I}}_l$, and by $x_k=\frac{1}{N}{\sum }_{i=1}^N{x}_{i,k}$ the average of the estimates derived at all agents at time k.

Theorem 5.

([44]) Let $\{x_{i,k}\}$ be produced by (46)–(49) with an arbitrary initial value $x_{i,0}$. Assume A5.1–A5.4 hold. Then on the sample path ω where A5.5 holds, the following assertions take place:

(i)

$\{x_{i,k}\}$ is bounded and there exists a positive integer $k_0$ possibly depending on ω such that

$$x_{i,k+1}=\sum _{j\in N_i\left(k\right)}{\omega }_{ij}\left(k\right)x_{j,k}+{\gamma }_k{O}_{i,k+1}\forall k\ge k_0,$$

(52)

or in the compact form:

$$X_{k+1}=\left(W\left(k\right)\otimes {\mathbf{I}}_l\right)X_k+{\gamma }_k(F\left(X_k\right)+{\epsilon }_{k+1})\forall k\ge k_0;$$

(53)

(ii)

$$\begin{array}{ccc}& X_{\perp ,k}\underset{k\to \infty }{⟶}\mathbf{0}andd(x_k,J)\underset{k\to \infty }{⟶}0;\hfill & \hfill \end{array}$$

(54)

(iii)

There exists a connected subset $J^{*}\subset J$ such that

$$d(x_k,J^{*})\underset{k\to \infty }{⟶}0.$$

(55)

Proof. 

The proof can be obtained by first proving the finite number of truncations, then the consensus of estimates, and finally, the convergence of estimates. The detailed proof can be found in [44]. □

DSAAWET provides a likely tool for solving the distributed problems over networks. In fact, DSAAWET has been successfully applied in the following problems:

• Distributed identification of linear systems [48],
• Distributed blind identification of communication channels [49],
• Output consensus of networked Hammerstein and Wiener systems [38].

4. Concluding Remarks

In this paper, we briefly reviewed the historical development of SAA, and in particular, introduced SAAWET and its distributed version (DSAAWET) developed by Han-Fu Chen and his colleagues during the past 35 years. SAAWET and DSAAWET establish general convergence results for the root-seeking problems with noise observations. Since many problems, such as identification, estimation, adaptive control, and optimization can be transformed into the root-seeking problem, SAAWET and DSAAWET can hopefully provide powerful tools for solving such problems.