Analysis of Approximate Message Passing with a Class of Non-Separable Denoisers

Introduction

Approximate message passing (AMP) is a class of low-complexity, scalable algorithms studied to solve the high-dimensional regression task of (1). The performance of AMP depends on a sequence of functions $\{\eta_{t}\}_{t\geq 0}$ used to generate a sequence of estimates $\{\beta^{t}\}_{t\geq 0}$ from auxiliary observation vectors computed in every iteration of the algorithm. A nice property of AMP is that under some technical conditions these observation vectors can be approximated as the input signal $\beta_{0}$ plus independent and identically distributed, or i.i.d., Gaussian noise. This fact allows one to choose functions $\{\eta_{t}\}_{t\geq 0}$ based on statistical knowledge of $\beta_{0}$, for example, a common choice is for $\eta_{t}$ to be the Bayes-optimal estimator of $\beta_{0}$ conditional on the value of the observation vector. For this reason, the functions $\{\eta_{t}\}_{t\geq 0}$ are referred to as ‘denoisers.’

Previous analysis of the performance of AMP only considers denoisers $\{\eta_{t}\}_{t\geq 0}$ that act coordinate-wise when applied to a vector; such functions are referred to as separable. If the unknown signal $\beta_{0}$ has a prior distribution assuming i.i.d. entries, restricting consideration to only separable denoisers causes no loss in performance. However, in many real-world applications, the unknown signal $\beta_{0}$ contains dependencies between entries and therefore a coordinate-wise independence structure is not a good approximation for the prior of $\beta_{0}$. For example, when the signals are images or sound clips , non-separable denoisers outperform reconstruction techniques based on over-simplified i.i.d. models. In such cases, a more appropriate model might be a finite memory model, well-approximated with a Markov chain prior. In this paper, we extend the previous performance guarantees for AMP to a class of non-separable sliding-window denoisers, whose promising empirical performance was shown by Ma et al. , when the unknown signal is produced by a Markov chain starting from its stationary distribution.

and $A^{*}$ denotes the transpose of $A$. We let $\eta^{\prime}_{t}$ denote the partial derivative of $\eta_{t}$ with respect to (w.r.t.) the $(k+1)^{th}$ coordinate, or the center element, assuming the function is differentiable. Quantities with a negative index in (2) and (3) are set to zero.

2 Contributions and Outline

To characterize AMP performance for sliding-window denoisers when the input signal is a Markov chain, we need concentration inequalities for PL functions of Markov chains and sequences of Gaussian vectors that are constructed in a certain way. Specifically, in the constructed sequences, successive elements are successive $(2k+1)$-length overlapping blocks of some original sequences (another Markov chain or Gaussian sequence, respectively), as suggested by the structure of the denoiser $\eta_{t}$ in (3). These concentration results are proved in Lemmas D.5 and D.6 in Appendix D.

The rest of the paper is organized as follows. Section 2 provides model assumptions, state evolution for sliding-window denoisers, and the main performance guarantee (Theorem 1), a concentration result for PL loss functions acting on the AMP estimate from (3) to the state evolution predictions. Section 3 proves Theorem 1 with a proof based on two technical results, Lemma 2 and Lemma 3, which are proved in Section 4.

Main Results

First we include definitions of properties of Markov chains that will be useful to clarify our assumptions on the unknown signal $\beta_{0}$.

where $\mathcal{B}(S)$ is the Borel sigma-algebra on $S$ and $r^{n}(x,dy)$ denotes the $n$-step transition probability measure. In other words, geometrical ergodicity means the chain converges to its stationary distribution $\gamma$ geometrically fast. The chain is said to be reversible if $r(x,dy)\gamma(dx)=r(y,dx)\gamma(dy)$. Moreover, a chain is said to have a spectral gap on $L^{2}(\gamma)$ if

where $\Lambda$ is a set of values for $\lambda$ such that $(\lambda\mathsf{I}-R)^{-1}$ does not exist as a bounded linear operator on $L^{2}(\gamma)$. Note that for a countable state space $S$, $\Lambda$ is the set of all eigenvalues of the transition probability matrix, hence $g_{2}$ is the distance between the largest and the second largest eigenvalues.

It has been proved that a Markov chain has spectral gap on $L^{2}(\gamma)$ if and only if it is reversible and geometrically ergodic . We use the existence of a spectral gap to prove concentration results for PL functions with dependent input, where the dependence is characterized by a Markov chain. Such concentration results are crucial for obtaining the main technical lemma, Lemma 3, and hence our main result, Theorem 1. If the spectral gap does not exist, meaning that $g_{2}=0$, then our proof only bounds the probability of tail events in Lemma 3 by constant 1, which is useless.

With this definition, we now clarify the assumptions under which our result is proved.

Matrix: The entries of the matrix $A$ are i.i.d. $\sim\mathcal{N}(0,1/n)$.

Noise: The entries of the measurement noise vector $w$ are i.i.d. according to some sub-Gaussian distribution $p_{w}$ with mean 0 and finite variance $\sigma^{2}$. The sub-Gaussian assumption implies that for all $\epsilon\in(0,1)$,

2 Performance Guarantee

As mentioned in Section 1, the behavior of the AMP algorithm is predicted by a simple, scalar iteration referred to as state evolution, which we introduce here. Let the stationary distribution $\gamma_{\beta}$ and the transition probability measure $r(x,dy)$ define the prior distribution for the unknown vector $\beta_{0}$ in (1). Let the random variable $\beta\in S$ be distributed as $\gamma_{\beta}$ and the random vector $\underline{\beta}\in S^{2k+1}$ be distributed as $\pi$, where

Theorem 1 provides our main performance guarantee, which is a concentration inequality for pseudo-Lipschitz (PL) loss functions.

(1) The probability in (6) is w.r.t. the product measure on the space of the matrix $A$, signal $\beta_{0}$, and noise $w$.

(2) Theorem 1 shows concentration for the loss when considering only the inner $N-2k$ elements of the signal. This is due to the nature of the sliding-window denoiser, which updates each element of the estimate $\beta^{t}$ using the $k$ elements on either side of that location. In practice, as in Ma et al. , one could run a slightly different algorithm than that given in (2)-(3): instead of setting the end elements, meaning the first $k$ and last $k$ elements, of the estimate $\beta^{t}$ equal to , update these elements using the sliding-window denoiser but with missing input values replaced by the median of the other inputs. Such a strategy shows good empirical performance – even at the end elements – and suggests that the concentration result of Theorem 1 could be extended to show concentration for the loss of the full signal. Proving this requires a delicate handling of the end elements and is left for future research.

(3) The state evolution constants $\{\tau_{t}^{2}\}_{t\geq 0}$ defined in (5) are the sum of $\sigma^{2}$ and two weighted terms, where the weight depends on $k$, the length of the window in the sliding-window denoiser. Since we only estimate the middle $N-2k$ elements of the signal, as $k$ increases the state evolution constants $\{\tau_{t}^{2}\}_{t\geq 0}$ depend more on the second moment of the one-dimensional marginals of the original signal, corresponding to the estimation error in the un-estimated part of the signal.

(4) By choosing PL loss, $\phi(a,b)=(a-b)^{2}$, Theorem 1 gives the following concentration result for the mean squared error of the middle $N-2k$ coordinates of the estimates. For all $t\geq 0$,

with $\tau_{t+1}^{2}$ defined in (5). A numerical example demonstrating that the MSE of the AMP estimates $\{\beta^{t}\}_{t\geq 0}$ is tracked by the state evolution iteration (5) is proved in Section 2.3.

3 A Numerical Example

We now provide a concrete numerical example where AMP is used to estimate $\beta_{0}$ from the linear system (1), when the entries of $\beta_{0}$ form a Markov chain on state space $\{0,1\}$ starting from its stationary distribution. The transition probability measure is $r(0,1)=3/70$ and $r(1,0)=1/10$, which yields a unique stationary distribution $\gamma_{\beta}(1)=1-\gamma_{\beta}(0)=3/10$.

We define the denoiser function $\eta_{t}$ in (3) as the Bayesian sliding-window denoiser. Note that an important key property of AMP is the following: for large $n$ and for $k+1\leq i\leq N-k$, the observation vector $[A^{*}z^{t}+\beta^{t}]_{i-k}^{i+k}$ used as input to the estimation function in (3) is approximately distributed as $\underline{\beta}+\tau_{t}\underline{Z}$, where $\underline{\beta}\sim\pi$ with $\pi(x_{1},...,x_{2k+1}):=\prod_{i=2}^{2k+1}r(x_{i-1},x_{i})\gamma_{\beta}(x_{1}),$ $\underline{Z}\sim\mathcal{N}(0,\textsf{I}_{2k+1})$ independent of $\underline{\beta}$, and $\tau_{t}$ is defined in (5).

where $\underline{\beta}_{k+1}$ denotes the $(k+1)^{th}$ element of $\underline{\beta}$. Figure 1 shows that the mean squared error (MSE) achieved by AMP with the non-separable sliding-window denoiser defined above is tracked by state evolution at every iteration.

Proof of Theorem 1

The proof of Theorem 1 follows the work of Rush and Venkataramanan , with modifications for the dependent structure of the unknown vector $\beta_{0}$ in (1). For this reason, we use much of the same notation. The main ingredients in the proof of Theorem 1 are two technical lemmas corresponding to [9, Lemmas 4 and 5]. We first cover some preliminary results and establish notation used in the proof. We then discuss the lemmas used to prove Theorem 1.

As mentioned above, in order to streamline the proof of our technical lemmas we use notation similar to and consequently to . As in the previous work, the technical lemmas are proved for a more general recursion which we define in the following, with AMP being a specific example of the general recursion as shown below.

with scalar values $\xi_{t}$ and $\lambda_{t}$ defined as

Recall that the unknown vector $\beta_{0}\in S^{N}$ is assumed to have a Markov chain prior with transition probability measure $r(x,dy)$ and stationary probability measure $\gamma_{\beta}$. Let $\beta\in S\sim\gamma_{\beta}$ and $\underline{\beta}\in S^{2k+1}\sim\pi$ where $\pi$ is defined in (4). Note that $\pi$ is the $(2k+1)$-dimension marginal distribution of $\beta_{0}$ and $\gamma_{\beta}$ is the one-dimensional marginal distribution.

and assume that there exist constants $K,\kappa>0$ such that

Define the state evolution scalars $\{\tau_{t}^{2}\}_{t\geq 0}$ and $\{\sigma_{t}^{2}\}_{t\geq 1}$ for the general recursion as follows.

We note that the AMP algorithm introduced in (2) and (3) is a special case of the general recursion introduced (7) and (8). Indeed, define the following vectors recursively for $t\geq 0$, starting with $\beta^{0}=0$ and $z^{0}=y$.

It can be verified that these vectors satisfy (7) and (8) with Lipschitz functions

and so for the AMP algorithm using $f_{t}$ from (14) in (10), assumption (11) is satisfied.

In what follows, the notation matches that of but is repeated here for completeness. In the remaining analysis, the general recursion given in (7) and (8) is used. We can write vector equations to represent the recursion as follows: for all $t\geq 0$,

This yields matrix equations $X_{t}=A^{*}M_{t}$ and $Y_{t}=AQ_{t},$ where we define the individual matrices as

In the above, $[c_{1}\mid c_{2}\mid\ldots\mid c_{k}]$ denotes a matrix with columns $c_{1},\ldots,c_{k}$ and $M_{0}$, $Q_{0}$, $B_{0}$, $H_{0}$, and $\Lambda_{0}$ are defined to be the all-zero vector. From the above matrix definitions we have the following matrix equations $Y_{t}=B_{t}+\Lambda_{t}[0|M_{t-1}]$ and $X_{t}=H_{t}+\Xi_{t}Q_{t}.$

The values $m^{t}_{\|}$ and $q^{t}_{\|}$ are projections of $m^{t}$ and $q^{t}$ onto the column space of $M_{t}$ and $Q_{t}$, with $m^{t}_{\perp}:=m^{t}-m^{t}_{\|},$ and $q^{t}_{\perp}:=q^{t}-q^{t}_{\|}$ being the projections onto the orthogonal complements of $M_{t}$ and $Q_{t}$. Finally, define the vectors

to be the coefficient vectors of the parallel projections, i.e.,

The technical lemma, Lemma 3, shows that for large $n$, the entries of the vectors $\alpha^{t}$ and ${\gamma}^{t}$ concentrate to constant values which are defined in the following section.

2 Concentrating Constants

First define the concentrating values for $\lambda_{t+1}$ and $\xi_{t}$ defined in (8) as

Finally, define the values $(\sigma^{\perp}_{0})^{2}:=\sigma_{0}^{2}$ and $(\tau^{\perp}_{0})^{2}:=\tau_{0}^{2}$, and for $t>0$

The proof can be found in [9, Lemma 4.1].

3 Conditional Distribution Lemma

As mentioned, the proof of Theorem 1 relies on two technical lemmas. The first lemma, presented in this section, provides the conditional distribution of the vectors $h^{t+1}$ and $b^{t}$ given the matrices in (17) as well as $\beta_{0},w$. Lemma 2 shows that these conditional distributions can be represented as the sum of a standard Gaussian vector an a deviation term. Then the second technical lemma, Lemma 3, shows that the deviation terms are small, meaning that their standardized norms concentrate on zero, and also provides concentration results for various inner products involving the other terms in recursion (7), namely $\{h^{t+1},q^{t},b^{t},m^{t}\}$.

Define $\mathscr{S}_{t_{1},t_{2}}$ to be the sigma-algebra generated by the terms

[9, Lemma 4] For vectors $h^{t+1}$ and $b^{t}$ defined in (7), the following conditional distributions hold for $t\geq 1$:

Lemma 2 holds only when $M^{*}_{t}M_{t}$ and $Q^{*}_{t_{1}}Q_{t_{1}}$ are invertible.

4 Main Concentration Lemma

We use the shorthand $X_{n}\doteq c$ to denote the concentration inequality $P(\left\lvert X_{n}-c\right\rvert\geq\epsilon)\leq K_{k,t}e^{-\kappa_{k,t}n\epsilon^{2}}$. As specified in the theorem statement, the lemma holds for all $\epsilon\in(0,1)$, with $K_{k,t},\kappa_{k,t}$ denoting generic constants depending on half window-size $k$ and iteration index $t$, but not on $n$ or $\epsilon$.

With the $\doteq$ notation defined above, the following statements hold for $t\geq 0$.

The random variables $\breve{Z}_{0},\ldots,\breve{Z}_{t}$ are jointly Gaussian with zero mean and covariance given by (21), and are independent of $W\sim p_{w}$.

Let $\textbf{Q}_{t+1}=\frac{1}{n}Q_{t+1}^{*}Q_{t+1}$ and $\textbf{M}_{t}=\frac{1}{n}M_{t}^{*}M_{t}$. Then,

When the inverses of $\textbf{Q}_{t+1}$ and $\textbf{M}_{t}$ exist, for all $0\leq i,j\leq t$ and $0\leq i^{\prime},j^{\prime}\leq t-1$:

where $\hat{\gamma}^{t+1}_{k}$ and $\hat{\alpha}^{t}_{k^{\prime}}$ are defined in (24),

With $\sigma_{t+1}^{\perp},\tau_{t}^{\perp}$ defined in (26),

5 Proof of Theorem 1

The proof is completed by noting from (3) and (13) that $\beta^{t+1}_{i}=\eta_{t}([A^{*}z^{t}+\beta^{t}]_{i-k}^{i+k})=\eta_{t}([\beta_{0}-h^{t+1}]_{i-k}^{i+k})$. ∎

Proof of Lemma 3

We also make use of concentration results that are listed in Appendices A, B, and C. Many of these results and their proofs can be found in Rush and Venkataramanan . Appendix D holds concentration results for dependent random variables that were needed to provide the new results in this paper, such as concentration for psuedo-Lipschitz functions acting on Markovian input.

The proof of Lemma 3. proceeds by induction on $t$. We label as $\mathcal{H}_{t+1}$ the results (33), (35), (37), (39), (41), (43), (45), (47), (49) and similarly as $\mathcal{B}_{t}$ the results (34), (36), (38), (40), (42), (44), (46), (48), (50). The proof consists of four steps: (1) $\mathcal{B}_{0}$ holds; (2) $\mathcal{H}_{1}$ holds; (3) if $\mathcal{B}_{r},\mathcal{H}_{s}$ holds for all $r<t$ and $s\leq t$, then $\mathcal{B}_{t}$ holds; and (4) if $\mathcal{B}_{r},\mathcal{H}_{s}$ holds for all $r\leq t$ and $s\leq t$, then $\mathcal{H}_{t+1}$ holds.

For each step, in parts $(a)$–$(h)$ of the proof, we use $K$ and $\kappa$ to label universal constants, meaning they do not depend on $n$ or $\epsilon$, but may depend on $t$, in the concentration upper bounds.

We wish to show results (a)–(h) in (34), (36), (38), (40), (42), (44), (46), (48), (50) for $t=0$. The proof of these results is the same as in the step $\mathcal{B}_{0}$ of the proof in and therefore is not repeated here.

We wish to show results (a)–(h) in (33), (35), (37), (39), (41), (43), (45), (47), (49) for $t=0$.

(a) The proof of $\mathcal{H}_{1}(a)$ follows as the corresponding proof in .

(b)(i) For $t=0$, the LHS of (35) can be bounded as

where to obtain $(a)$, we use Lemma B.2 and $\mathcal{H}_{1}(a)$.

(c) We first show concentration for $(h^{1})^{*}\beta_{0}/n$. This result follows directly from $\mathcal{H}_{1}(b)$: we can write $\left\lvert(h^{1})^{*}\beta_{0}\right\rvert=\left\lvert\sum_{i=1}^{N}h^{1}_{i}\beta_{0_{i}}\right\lvert\leq\left\lvert\sum_{i=1}^{N/2}h^{1}_{i}\beta_{0_{i}}\right\lvert+\left\lvert\sum_{j=N/2+1}^{N}h^{1}_{j}\beta_{0_{j}}\right\lvert$ and it follows by Lemma A.1,

Next we show concentration for $(h^{1})^{*}q^{0}/n$. Note that

where the last equality follows by definition of $q^{0}$ provided in (10). It follows by Lemma A.1,

(d) The result follows as in $\mathcal{H}_{1}(c)$. We can write $\left\lVert h^{1}\right\rVert^{2}=\sum_{i=1}^{N}(h^{1}_{i})^{2}=\sum_{i=1}^{N/2}(h^{1}_{i})^{2}+\sum_{j=N/2+1}^{N}(h^{1}_{j})^{2}$ and therefore it follows by Lemma A.1,

(e) We prove concentration for $(q^{0})^{*}q^{1}$ first. Notice that

Concentration for $\left\lVert q^{1}\right\rVert^{2}$ follows similarly by applying $\mathcal{H}_{1}(b)$ with the representation

(f) The concentration of $\lambda_{0}$ around $\hat{\lambda}_{0}$ follows from $\mathcal{H}_{1}(b)(i)$ applied to the function $\phi_{h}([h^{1}]_{i-k}^{i+k},[\beta_{0}]_{i-k}^{i+k}):=f_{0}^{\prime}([h^{1}]_{i-k}^{i+k},[\beta_{0}]_{i-k}^{i+k})$. The only other result to prove is concentration for $(h^{1})^{*}q^{1}$. Notice that

In the above, step $(b)$ follows by Fact 2

(g), (h) The proof of $\mathcal{H}_{1}(g),(h)$ follow as the corresponding proofs in .

We wish to show results (a) – (h) in (34), (36), (38), (40), (42), (44), (48), (50) assuming that $\mathcal{B}_{r}$ and $\mathcal{H}_{r+1}$ hold for all $0\leq r\leq t-1$ due to the inductive hypothesis. The proof of these results is the same as in the step $\mathcal{B}_{t}$ of the proof in and therefore is not repeated here.

𝑡1\mathcal{H}_{t+1} holds We wish to show results (a) – (h) in (33), (35), (37), (39), (41), (43), (47), (49) assuming $\mathcal{B}_{r}$ holds for all $0\leq r\leq t$ and $\mathcal{H}_{s+1}$ holds for all $0\leq s\leq t-1$.

The probability statements in the lemma and the other parts of $\mathcal{H}_{t+1}$ are conditioned on the event that the matrices $\mathbf{Q}_{1},\ldots,\mathbf{Q}_{t+1}$ are invertible, but for the sake of brevity, we do not explicitly state the conditioning in the probabilities. The following lemma, whose proof is the same as in , will be used to prove $\mathcal{H}_{t+1}$.

[9, Lemma 8] Let $v:=\frac{1}{n}B^{*}_{t+1}m_{t}^{\perp}-\frac{1}{n}Q_{t+1}^{*}(\xi_{t}q^{t}-\sum_{i=0}^{t-1}\alpha^{t}_{i}\xi_{i}q^{i})$ and $\mathbf{Q}_{t+1}:=\frac{1}{n}Q_{t+1}^{*}Q_{t+1}$. Then for $j\in[t+1]$,

(a) Recall the definition of $\Delta_{t+1,t}$ from Lemma 2 (32). Using Fact 1, we have

where we have used $Q_{t+1}\textbf{Q}_{t+1}^{-1}v=\sum_{j=0}^{t}q^{j}\left[\textbf{Q}_{t+1}^{-1}v\right]_{j+1}$. Applying Lemma A.1,

where $\epsilon_{t}=\frac{\epsilon}{(2t+3)^{2}}$. We now show each of the terms in (55) has the desired upper bound. For $0\leq r\leq t-1$,

where step $(a)$ follows from induction hypotheses $\mathcal{B}_{t}(g)$, $\mathcal{H}_{1}(d)-\mathcal{H}_{t}(d)$, and Lemma A.3. Next, the second term on the right side of (55) can be bounded similarly using induction hypothesis $\mathcal{B}_{t}(h)$, Lemma A.3, and Lemma B.2. Since $\left\lVert m^{t}_{\perp}\right\rVert/\sqrt{n}$ concentrates on $\tau_{t}^{\perp}$ by $\mathcal{B}_{t}(h)$, the third term in (55) can be bounded as

Step $(b)$ uses Lemma A.1 and step $(c)$ Lemma B.1. Using (57) and $\mathcal{B}_{t}(h)$, the RHS of (56) is bounded by $K\exp\{-\kappa n\epsilon\}$. Finally, for $0\leq j\leq t$, the last term in (55) can be bounded by

where step $(d)$ follows from Lemma 4, the induction hypothesis $\mathcal{H}_{t}(e)$, and Lemma A.3. Thus we have bounded each term of (55) as desired.

Then, using the conditional distribution of $h^{t+1}$ from Lemma 2 and Lemma A.1, we have

Label the two terms of (59) as $T_{1}$ and $T_{2}$. To complete the proof we show both are bounded by $Ke^{-\kappa n\epsilon^{2}}$. First consider term $T_{1}$. Using the pseudo-Lipschitz property of $\phi_{h}$, we have

where the last equality is obtained using $\breve{E}_{l,l}=\tau_{l}^{2}$, and by rewriting the double sum as follows:

Using Lemma A.1, let $\epsilon_{t}=\epsilon/(t+t^{2}+2)$,

In step $(a)$, we used induction hypothesis $\mathcal{H}_{1}(d)-\mathcal{H}_{t}(d)$, result (15), and Lemma B.2.

Therefore, using (60), term $T_{1}$ of (59) can be bounded as

In step $(a)$, we used (64), $\mathcal{H}_{t+1}(a)$, and Lemma A.3.

The first term on the RHS of the above has the desired bound using Lemma D.5. We now bound the second term.

which is $PL(2)$ by Lemma C.2. We will now show that

and then the probability in (66) can be upper bounded by $Ke^{-\kappa n\epsilon^{2}}$ using the inductive hypothesis $\mathcal{H}_{t}(b)$. We have

where step $(a)$ follows from (21) and step $(b)$ follows from (63). Therefore, we have showed that the covariance matrix is $\tau_{t}^{2}\textsf{I}$. Next consider (ii), for any $0\leq l\leq(t-1)$, the $(i,j)^{th}$ entry of the covariance matrix is

where step $(a)$ follows from (21). Moreover, notice that $\sum_{r=0}^{t-1}\breve{E}_{l,r}\hat{\alpha}^{t}_{r}=[\breve{C}^{t}\hat{\alpha}^{t}]_{l+1}=\breve{E}_{l,t},$ where the first equality holds because the required sum is the inner product of the $(l+1)^{th}$ row of $\breve{C}^{t}$ and $\hat{\alpha}^{t}$, and the second inequality follows the definition of $\hat{\alpha}^{t}$ in (24).

(c) We first show the concentration of $(h^{t+1})^{*}\beta_{0}/n$. Note, $\left|\sum_{i=1}^{N}h^{t+1}_{i}\beta_{0_{i}}\right|\leq\left|\sum_{i=1}^{N/2}h^{t+1}_{i}\beta_{0_{i}}\right|+\left|\sum_{i=N/2+1}^{N}h^{t+1}_{i}\beta_{0_{i}}\right|$. Then we have

We now show the concentration of $(h^{t+1})^{*}q^{0}/n$. Rewrite $(h^{t+1})^{*}q^{0}$ as

(d) Similar to $\mathcal{H}_{t+1}(c)$, we split the inner product $(h^{r+1})^{*}h^{t+1}$ and then from Lemma A.1,

(e) We first show the concentration of $(q^{0})^{*}q^{t+1}/n$. Recall from (22), for $0\leq r,s\leq t+1$,

Then splitting $(q^{0})^{*}q^{t+1}$ as in $\mathcal{H}_{1}(e)$, we have

Concentration of $(q^{r+1})^{*}q^{t+1}/n$ can be obtained similarly by representing

and using $\mathcal{H}_{t+1}(b)$ as above.

(f) The concentration of $\lambda_{t}$ around $\hat{\lambda}_{t}$ follows $\mathcal{H}_{t+1}(b)$ applied to the function $\phi_{h}([h^{t+1}]_{i-k}^{i+k},[\beta_{0}]_{i-k}^{i+k}):=f_{t+1}^{\prime}([h^{t+1}]_{i-k}^{i+k},[\beta_{0}]_{i-k}^{i+k})$. Next, for $r\leq t$, splitting $(h^{t+1})^{*}q^{r+1}$ as in $\mathcal{H}_{1}(f)$,

(g) (h) The proof of $\mathcal{H}_{t+1}(g),(h)$ is similar to the proof of $\mathcal{B}_{t}(g),(h)$ in .

Appendix A Concentration Lemmas

In the following $\epsilon>0$ is assumed to be a generic constant, with additional conditions specified whenever needed. The proof of the Lemmas in this section can be found in .

If random variables $X_{1},\ldots,X_{M}$ satisfy $P(\left\lvert X_{i}\right\rvert\geq\epsilon)\leq e^{-n\kappa_{i}\epsilon^{2}}$ for $1\leq i\leq M$, then

For random variables $X,Y$ and non-zero constants $c_{X},c_{Y}$, if

then the probability $P\left(\left|XY-c_{X}c_{Y}\right|\geq\epsilon\right)$ is bounded by

Appendix B Gaussian and Sub-Gaussian Concentration

For a standard Gaussian random variable $Z$ and $\epsilon>0$, $P\left(\left\lvert Z\right\rvert\geq\epsilon\right)\leq 2e^{-\frac{1}{2}\epsilon^{2}}$.

For $Z_{i}$, $i\in[n]$ that are i.i.d. $\sim\mathcal{N}(0,1)$, and $0\leq\epsilon\leq 1$,

For all $x>0$, $P(X>x)\vee P(X<-x)\leq e^{-\frac{x^{2}}{2\nu}}$, for all $x>0$.

Appendix C Other Useful Lemmas

where $Z\sim\mathcal{N}(0,1)$, is then also PL(2).

Appendix D Concentration with Dependencies

The sup-norm: $\|f\|_{\infty}:=\sup_{x\in S}|f(x)|$;

The $L^{2}(\pi)$-norm: for measurable function $f$, $\|f\|_{2,\pi}^{2}:=\int_{S}|f(x)|^{2}\pi(dx)$; for signed measure $\nu$,

where the $L^{2}(\pi)$-norm for $\nu\ll\pi$ For two measures $\nu$ and $\gamma$, $\nu\ll\gamma$ denotes that $\nu$ is absolutely continuous w.r.t. $\gamma$, and $\frac{d\nu}{d\gamma}$ denotes the Radon-Nikodym derivative. is induced from the inner-product: for $\mu,\nu\ll\pi$,

The following lemma exists in the literature and is stated here, without proof, for completeness. The proof can be found in the citation. Lemma D.1 tells us that if a Markov chain is reversible and geometrically ergodic as defined in Definition 2.1, then its associated linear operator has a spectral gap, the level of which controls the chain’s mixing time.

[12, Theorem 2.1] Consider a Markov chain with state space $S$, probability transition measure $r(x,dx^{\prime})$, stationary probability measure $\gamma$, and linear operator $R$ associated with $r(x,dx^{\prime})$ such that $\nu R(dx)=\int_{S}r(x^{\prime},dx)\nu(dx^{\prime})$ for measure $\nu$. If the Markov chain is reversible and geometrically ergodic (Definition 2.1), then $R$ has an $L^{2}(\gamma)$ spectral gap. That is, for each signed measure $\nu$ with $\nu(S)=0$ and $\|\nu\|_{2,\gamma}<\infty$, there is a $0<\rho<1$ such that $\|\nu R\|_{2,\gamma}\leq\rho\|\nu\|_{2,\gamma}.$

Notice that the definition of spectral gap above is identical to the definition provided in 2.1. To see this, note that $\gamma$ is an eigen-function of $R$ with eigenvalue 1, $R$ is self-adjoint since the chain is reversible, and the eigen-functions of a self-adjoint operator are orthogonal, hence the rest of the eigen-functions are in the space that is perpendicular to $\gamma$, which is $\left\{\nu\ll\pi\left|\langle\nu,\gamma\rangle_{\gamma}=0\right.\right\},$ where $\langle\nu,\gamma\rangle_{\gamma}=\int_{S}\frac{d\nu}{d\gamma}\frac{d\gamma}{d\gamma}d\gamma=\nu(S)$ by the definition of inner-product in (72).

In the following, Lemmas D.2, D.3, and D.4 are preparations for the proofs of Lemmas D.5 and D.6, which are our new contributions. Lemma D.2 gives a technical result about pseudo-Lipschitz functions with sub-Gaussian input.

which provides the first upper bound in (73). Next,

where step $(a)$ follows pseudo-Lipschitz property and step $(b)$ holds because the odd order terms are zero, along with triangle inequality. Now consider the expectation in the last term in the string given in (74).

In the above step $(c)$ follows from Lemma C.3 and step $(d)$ from another application of Lemma C.3 and Lemma B.3. Now plugging the above back into (74), we find

where step $(e)$ follows from the fact that $2^{k}(k!)^{2}\leq(2k)!$, which can be seen by noting $\frac{(2k)!}{k!}=\prod_{j=1}^{k}(k+j)=k!\prod_{j=1}^{k}\left(\frac{k}{j}+1\right)\geq(k!)2^{k},$ step $(f)$ follows for $0<r<[25L^{2}(d\nu+12d^{2}\nu^{2})]^{-1/2}$ providing the second bound in (73), and step (g) uses the inequality $(1-x)^{-1}\leq e^{2x}$ for $x\in[0,1/2]$ for the final bound in (73). ∎

The reversibility of the coupled chain follows from the reversibility of the individual chains:

where $\mathcal{B}(S\times S)$ is the Borel sigma-algebra on $S\times S$. Notice that

where step $(a)$ used triangle inequality and $0\leq\gamma(A)\leq 1$ for all $A\in\mathcal{B}(S)$. Taking the supremum of both sides of the above,

where step $(a)$ follows from (76), and step $(b)$ since $\gamma$ is the stationary probability measure for $r(x,dx^{\prime})$. Hence, we have verified that $\pi$ is a stationary probability measure for $p(y,dy^{\prime})$.

Take arbitrary $h\in L^{2}_{0}(\pi)$, we have

First consider the numerator of (77). Plugging in the expressions for $p(y,dy^{\prime})$ and $\pi(dy)$ defined in (76), we write the numerator as

Next we consider the denominator of (77).

Finally, let us show $\beta_{R}<1$. By Lemma D.1, we have that for each signed measure $\nu\in L^{2}(\gamma)$ with $\nu(S)=0$, we have

Define $h:=d\nu/d\gamma$, which is well-defined since $\nu\ll\gamma$. By the reversibility, we have

Therefore, (82) can be written as $\int_{S}\left(\int_{S}h(x^{\prime})r(x,dx^{\prime})\right)^{2}\gamma(dx)\leq\rho\int_{S}(h(x))^{2}\gamma(dx),$ for all $\nu$ such that $0=\nu(S)=\int_{S}(\nu(dx)/\gamma(dx))\gamma(dx)=\int_{S}h(x)\gamma(dx)$. Therefore, $\beta_{R}=\sup_{h\in L_{0}^{2}(\gamma)}\frac{\|Rh\|_{2,\gamma}}{\|h\|_{2,\gamma}}\leq\rho<1.$ We have shown the result of (75) by showing that that $\beta_{P}\leq\beta_{R}<1$. ∎

The following three lemmas are the key lemmas for proving Lemma 3 and, therefore, our main result, Theorem 1, as well. The next lemma shows us that a normalized sum of pseudo-Lipschitz functions with Gaussian input vectors concentrate at their expected value.

and the lower-tail bound follows similarly. Together they provide the desired result.

Let $L_{i}$ be the pseudo-Lipschitz parameters associated with functions $f_{i}$ for $i=1,...,n$ and define $L:=\max_{i\in[n]}L_{i}$. In the following, we will show that

where $\kappa^{\prime}$ is any constant that satisfies $\kappa^{\prime}\geq 150L^{2}d(d+12d^{2})$. Then plugging (85) into (84), we can obtain the desired result in (83): $P\left(\frac{1}{n}\sum_{i=1}^{n}f_{i}(Y_{i})\geq\epsilon\right)\leq\exp\{-n(r\epsilon-\kappa^{\prime}r^{2})\}.$ Set $r=\epsilon/(2\kappa^{\prime})$, the choice that maximizes the term $(r\epsilon-\kappa^{\prime}r^{2})$ over $r$ in the exponent in the above. We can ensure that for $\epsilon\in(0,1)$, $r$ falls within the region required in (85) by choosing $\kappa^{\prime}$ large enough.

Now we show (85). Define index sets $I_{j}:=\{j+kd\,|\,k=0,...,\lfloor\frac{n-j}{d}\rfloor\}$ for $j=1,...,d$, let $C_{j}$ denote the cardinality of $I_{j}$. We notice that for any fixed $j$, the $Y_{i}$’s are i.i.d. for $i\in I_{j}$. For example, if $j=1$ then the index set $I_{1}=\{1,1+d,1+2d,\ldots,1+\lfloor\frac{n-1}{d}\rfloor d\}$ and $Y_{1}=(Z_{1},\ldots,Z_{d})$ is independent of $Y_{1+d}=(Z_{1+d},\ldots,Z_{2d})$, which are both independent of $Y_{1+2d}=(Z_{2d+1},\ldots,Z_{3d})$, and so on. Also, we have $[n]=\cup_{j=1}^{d}I_{j}$, and $I_{j}\cap I_{s}=\emptyset$, for $j\neq s$, making the collection $I_{1},I_{2},\ldots,I_{d}$ a partition of $i\in[n]$. Therefore, $\sum_{i=1}^{n}f_{i}(Y_{i})=\sum_{j=1}^{d}\sum_{i\in I_{j}}f_{i}(Y_{i})=\sum_{j=1}^{d}p_{j}\cdot\frac{1}{p_{j}}\sum_{i\in I_{j}}f_{i}(Y_{i}),$ where $0<p_{1},...,p_{d}<1$ are probabilities satisfying $\sum_{j=1}^{d}p_{j}=1$. Using the above,

where step $(a)$ follows from Jensen’s inequality, step $(b)$ from the fact that the $Y_{i}$’s are independent for $i\in I_{j}$, and step $(c)$ from Lemma D.2 noting that the marginal distribution of any element of $Y_{i}$ is Gaussian and therefore sub-Gaussian with variance factor $\nu=1$ and restriction

Let $p_{j}=\sqrt{C_{j}}/C$, where $C=\sum_{j=1}^{d}\sqrt{C_{j}}$ ensuring that $\sum_{j=1}^{d}p_{j}=1$. Then, we have

whenever $\kappa^{\prime}\geq 150dL^{2}(d+12d^{2})$. In the above, step $(a)$ follows from:

where step $(b)$ holds because $C_{1}=\max_{j\in[d]}C_{j}$ and step $(c)$ holds because $C_{1}=\lfloor\frac{n-1}{d}\rfloor+1\leq\frac{n}{d}+2$.

Finally, we consider the effective region for $r$ as required in (87). Notice that $\max_{j}p_{j}=\sqrt{C_{1}}/C>1/d$. Hence, if we require $0<r<[5Ld\sqrt{2d+24d^{2}}]^{-1}$, then (87) is satisfied.

The following lemma shows us that a normalized sum of pseudo-Lipschitz functions with Markov chain input vectors concentrate at its expected value under certain conditions on the Markov chain.

First, we split $\{X_{i}\}_{i\in[n]}$ into $d$ subsequences, each containing every $d^{th}$ term of $\{X_{i}\}_{i\in[n]}$, beginning from $1,2,\ldots,d$. Label these $\{X^{(1)}_{i}\}_{i\in[n_{1}]},...,\{X^{(d)}_{i}\}_{i\in[n_{d}]}$ with $\{X^{(s)}_{i}\}_{i\in[n_{s}]}:=\{X_{s+kd}:k=1,...,n_{s}\}$, where $n_{s}=\lfloor\frac{n-d-s+1}{d}\rfloor$, for $s=1,...,d$.

Notice that $\sum_{i=1}^{n}f(X_{i})=\sum_{s=1}^{d}\sum_{i=1}^{n_{s}}f(X^{(s)}_{i})$. Using Lemma A.1, we have

The lower-tail bound follows similarly, as do the corresponding results for $s=2,3,\ldots,d$. Together using (88) these provide the desired result. Using the Cramér-Chernoff method: for $r>0$,

Define $m(z):=\exp\left(rg(z)\right)$, for all $z\in D$, and so we can represent the expectation that we hope to upper bound in the following way:

To provide an upper bound for (94), we first define a sequence $\{a_{i}\}_{i\in[n_{1}]}$ as $a_{0}=1$ and

Note then that $a_{n_{1}}$ equals the expectation in (94) and we have

Step $(b)$ uses the definition of $a_{n_{1}-1}$ given in (95) and the linear operator defined in (92). Now consider the integral in (97), which we split as in (96) in the following:

Again, our goal is to provide an upper bound for $a_{n_{1}}$ which we can establish through the recursive relationship $a_{n_{1}}=\sum_{i=1}^{n_{1}}b_{i}a_{n_{1}-i}$ if we can upper bound $b_{1},...,b_{n_{1}}$. First consider $b_{1}$. Let $Z\sim\mu$.

Consider the partial sum $\sum_{k=0}^{n}\frac{r^{k}}{k!}(g(Z))^{k}$. Moreover, notice that

Since the constant $\exp\{rM_{g}\}$ is integrable with respect to any proper probability measure, we have

Next we’ll bound $b_{i}$ for $i=2,3,\ldots$. To do this we first establish an upper bound on $\left\lVert m_{i}\right\rVert_{2,\mu}$ with the norm defined in (93).

Step $(a)$ holds since $\sup_{z\in D}m(z)=\sup_{z\in D}\exp\{rg(z)\}\leq\exp\{rM_{g}\}$. Step $(b)$ holds since $E_{\mu}m_{i}=0$, for all $i=1,...,n$ by construction, and so $\|Qm_{i}\|_{2,\mu}\leq\beta_{Q}\|m_{i}\|_{2,\mu}$ by (93). Hence, extending the above result recursively, we find

where step $(c)$ follows Cauchy-Schwarz inequality and step $(d)$ follows from the fact that $\|Qm_{i-1}\|_{2,\mu}\leq\beta_{Q}\|m_{i-1}\|_{2,\mu}$ by (93) and (100). Now let $Z\sim\mu$ and we bound $\|m_{1}\|_{2,\mu}^{2}$ as follows

Therefore, from (99), (101), and (102) we have

Let $\mathsf{b}^{2}=10L^{2}\left(d\textsf{m}_{2}+d^{2}\textsf{m}_{4}+2d^{2}\textsf{m}_{2}^{2}\right)$, $\mathsf{a}=\frac{1}{2}\mathsf{b}^{2}\exp\{rM_{g}\}$, and $\alpha=\beta_{Q}\exp\{rM_{g}\}$. Choose $r<(1-\beta_{Q})/M_{g}$, then we have $0<\alpha<1$ since $1-\beta_{Q}<-\ln\beta_{Q}$. Using these bounds and notation, (103) becomes

We now bound $a_{1},...,a_{n_{1}}$ by induction. We will show $a_{i}\leq[\phi(r)]^{i}$, where $\phi(r)=1+Cr^{2}$ for some $C\geq 4\textsf{a}$ that is independent of $i$. For $i=1$, $a_{1}=b_{1}\leq 1+4\textsf{a}r^{2}.$ Hence, the hypothesis $a_{i}\leq[\phi(r)]^{i}$ is true for $i=1$. Suppose that the hypothesis is true for $i\leq n_{1}-1$, then

where the final inequality in the above follows by (104) and the inductive hypothesis. Consider only the second term on the right side of (105),

where the final inequality follows since $\textsf{a},\alpha>0$. Then plugging the above result into (105), we find

where the final inequality follows since $\phi(r)\geq 1$. Therefore, let $C=4\mathsf{a}(1-\alpha)^{-1}>4\mathsf{a}$, since $0<\alpha<1$, and so $\phi(r)=1+4\textsf{a}r^{2}(1-\alpha)^{-1}$. It follows from the above then,

where the final inequality uses the fact that $\ln(1+x)\leq x$ for $x\geq 0$.

Finally, from (90), (91), and the bound in (106),

where step $(a)$ follows from the fact that $\mathsf{a}=\mathsf{b}^{2}e^{rM_{g}}/2$ and $\alpha=\beta_{Q}e^{rM_{g}}$. Now let us consider the term in the exponent in the above for the cases where (i) $\mathsf{b}^{2}\geq M_{g}$ and (ii) $\mathsf{b}^{2}<M_{g}$ separately, and then combine the results in the two cases to obtain a desired bound for all $\epsilon\in(0,1)$.

First (i) $\mathsf{b}^{2}\geq M_{g}$. Notice for every $0<\epsilon<4\mathsf{b}^{2}/M_{g}$, if we let $r=(1-\beta_{Q})\epsilon/(4\textsf{b}^{2})$, then $r<(1-\beta_{Q})/M_{g}$ as required before. We show whenever $0<\epsilon\leq\mathsf{b}^{2}/M_{g}$, we can obtain a desired bound. Then the condition in the lemma statement, $\epsilon\in(0,1)$, falls within this effective region.

In the above, step $(a)$ by plugging in $r=(1-\beta_{Q})\epsilon/(4\mathsf{b}^{2})$, step $(b)$ holds since $e^{x}\leq 1+4x/3$ for $x\leq 1/2$, and step $(c)$ holds since $\epsilon\leq\mathsf{b}^{2}/M_{g}$, so $(\textsf{b}^{2}-\beta_{Q}M_{g}\epsilon)>0$, and the fact $\mathsf{b}^{2}\geq M_{g}$.

Next consider (ii) $\mathsf{b}^{2}<M_{g}$. In this case, set $r=(1-\beta_{Q})\epsilon/(4M_{g})$. Hence, $r<(1-\beta_{Q})/M_{g}$ for $\epsilon\in(0,1)$, and then