Learning One Convolutional Layer with Overlapping Patches

Introduction

Developing provably efficient algorithms for learning commonly used neural network architectures continues to be a core challenge in machine learning. The underlying difficulty arises from the highly non-convex nature of the optimization problems posed by neural networks. Obtaining provable guarantees for learning even very basic architectures remains open.

The main contribution of this paper is a simple, stochastic update algorithm Convotron (Algorithm 1) for provably learning the above convolutional architecture. The algorithm has the following properties:

Works for general classes of overlapping patches and requires mild distributional conditions.

Proper recovery of the unknown weight vector.

Stochastic in nature with a “gradient-like” update step.

Requires no special/random initialization scheme or tuning of the learning rate.

Tolerates noise and succeeds in the probabilistic concept model of learning.

Logarithmic convergence in $1/\epsilon$, the error parameter, in the realizable setting.

This is the first efficient algorithm for learning general classes of overlapping patches (and the first algorithm for any class of patches that succeeds under mild distributional assumptions). Prior work has focused on analyzing SGD in the realizable/noiseless setting with the caveat of requiring either disjoint patches [BG17, DLT+17b] with Gaussian inputs or technical conditions linking the underlying true parameters and the “closeness of patches” [DLT17a].

In contrast, our conditions depend only on the patch structure itself and can be efficiently verified. Commonly used patch structures in computer vision applications such as 1D/2D grids satisfy our conditions. Additionally, we require only that the underlying distribution on samples is symmetric and induces a covariance matrix on the patches with polynomially bounded condition numberBrutzkus and Globerson [BG17] proved that the problem, even with disjoint patches, is NP-hard in general, and so some distributional assumption is needed for efficient learning.. All prior work handles only continuous distributions. Another major difference from prior work is that we give guarantees using purely empirical updates. That is, we do not require an assumption that we have access to exact quantities such as the population gradient of the loss function.

We further show that in the commonly studied setting of Gaussian inputs and non-overlapping patches, updating with respect to a single non-overlapping patch is sufficient to guarantee convergence. This indicates that the Gaussian/no-overlap assumption is quite strong.

2 Our Approach

Our approach is to exploit the monotonicity of the activation function instead of the strong convexity of the loss surface. We use ideas from isotonic regression and extend them in the context of convolutional networks. These ideas have been successful for learning generalized linear models [KKSK11], improperly learning fully connected, depth-three neural networks [GK17b], and learning graphical models [KM17].

3 Related Work

It is known that in the worst case, learning even simple neural networks is computationally intractable. For example, in the non-realizable (agnostic) setting, it is known that learning a single ReLU (even for bounded distributions and unit norm hidden weight vectors) with respect to square-loss is as hard as learning sparse parity with noise [GKKT16], a notoriously difficult problem from computational learning theory. For learning one hidden layer convolutional networks, Brutzkus and Globerson [BG17] proved that distribution-free recoverability of the unknown weight vector is NP-hard, even if we restrict to disjoint patch structures.

As such, a major open question is to discover the mildest assumptions that lead to polynomial-time learnability for simple neural networks. In this paper, we consider the very popular class of convolutional neural networks (for a summary of other recent approaches for learning more general architectures see [GK17a]). For convolutional networks, all prior research has focused on analyzing conditions under which (Stochastic) Gradient Descent converges to the hidden weight vector in polynomial-time.

Along these lines, Brutzkus and Globerson [BG17] proved that with respect to the spherical Gaussian distribution and for disjoint (non-overlapping) patch structures, gradient descent recovers the weight vector in polynomial-time. Zhong et al. [ZSD17] showed that gradient descent combined with tensor methods can recover one hidden layer involving multiple weight vectors but still require a Gaussian distribution and non-overlapping patches. Du et al. [DLT+17b] proved that gradient descent recovers a hidden weight vector involved in a type of two-layer convolutional network under the assumption that the distribution is a spherical Gaussian, the patches are disjoint, and the learner has access to the true population gradient of the loss function.

We specifically highlight the work of Du, Lee, and Tian [DLT17a], who proved that gradient descent recovers a hidden weight vector in a one-layer convolutional network under certain technical conditions that are more general than the Gaussian/no-overlap patch scenario. Their conditions involve a certain “alignment” of the unknown patch structure, the hidden weight vector, and the (continuous) marginal distribution. However, it is unclear which concrete patch-structure/distributional combinations their framework captures. We also note that all of the above results assume there is no noise; i.e., they work in the realizable setting.

Other related works analyzing gradient descent with respect to the Gaussian distribution (but for non-convolutional networks) include [Sol17, GLM17, ZSJ+17, Tia16, LY17, ZPSR17].

In contrast, we consider an alternative to gradient descent, namely Convotron, that is based on isotonic regression. The exploration of alternative algorithms to gradient descent is a feature of our work, as it may lead to new algorithms for learning deeper networks.

Preliminaries

$||\cdot||$ corresponds to the $l_{2}$ -norm for vectors and the spectral norm for matrices. The identity matrix is denoted by $I$. We denote the input-label distribution by $\mathcal{D}$ over input drawn from $\mathcal{X}$ and label drawn from $\mathcal{Y}$. The marginal distribution on the input is denoted by $\mathcal{D}_{\mathcal{X}}$ and the corresponding probability density function is denoted by $P_{\mathcal{X}}$.

We study the problem of learning the teacher network under the square loss, that is, we wish to find a $w$ such that

Distribution: The marginal distribution on the input space $\mathcal{D}_{\mathcal{X}}$ is a symmetric distribution about the origin, that is, for all $x$, $P_{\mathcal{X}}(x)=P_{\mathcal{X}}(-x)$.

Activation Function: The activation function has the following form:

The distributional assumption includes common assumptions such as Gaussian inputs, but is far less restrictive. For example, we do not require the distribution to be continuous nor do we require it to have identity covariance. In Section 4, we show that commonly used patch schemes from computer vision satisfy our patch requirements. The assumption on activation functions is satisfied by popular activations such as ReLU ($\alpha=0$) and leaky ReLU ($\alpha>0$).

The activations we consider in this paper have the following useful property:

The loss function can be upper bounded by the $l_{2}$-norm distance of weight vectors using the following lemma.

The Gershgorin Circle Theorem, stated below, is useful for bounding the eigenvalues of matrices.

For a $n\times n$ matrix $A$, define $R_{i}:=\sum_{j=1,j\neq i}^{n}|A_{i,j}|$. Each eigenvalue of $A$ must lie in at least one of the disks $\{z:|z-A_{i,i}|\leq R_{i}\}$.

Note: The proofs of lemmas in this section have been deferred to the Appendix.

The Convotron Algorithm

In this section we describe our main algorithm Convotron and give a proof of its correctness. Convotron is an iterative algorithm similar in flavor to SGD with a modified (aggressive) gradient update. Unlike SGD (Algorithm 3), Convotron comes with provable guarantees and also does not need a good initialization scheme for convergence.

The following theorem describes the convergence rate of our algorithm:

Define $S_{t}=\{(x_{1},y_{1}),\ldots,(x_{t},y_{t})\}$ The dynamics of Convotron can be expressed as follows:

We need to bound the RHS of the above equation. We have,

Combining the above equations and taking expectation over $S_{t-1}$, we get

We set $\eta=\beta\min\left(\frac{1}{\gamma},\frac{\epsilon||w_{*}||^{2}}{B}\right)$ and break the analysis to two cases:

since at initialization $||w_{1}-w_{*}||=||w_{*}||$. Setting $T=O\left(\frac{1}{\eta\beta}\log\left(\frac{1}{\epsilon\delta}\right)\right)$ and using Markov’s inequality, with probability $1-\delta$, over the choice of $S_{T}$,

By using Lemma 2, we can get a bound on $L(w_{T})\leq\epsilon||w_{*}||^{2}$ by appropriately scaling $\epsilon$.

For the realizable (no noise) setting, that is, for all $(x,y)\sim\mathcal{D}$, $y=f_{w_{*}}(x)$, for some unknown $w_{*}$, Convotron achieves faster convergence rates.

Observe that the dependence of $\epsilon$ in the convergence rate is $\log(1/\epsilon)$ for the realizable setting, compared to the $1/\epsilon$ dependence in the noisy setting.

Which Patch Structures are Easy to Learn?

In this section, we will show that the commonly used convolutional filters in practice (“patch and stride”) have good eigenvalues giving us fast convergence by Theorem 2. We will start with the 1D case and then subsequently extend the result for the 2D case.

Here we formally describe a patch and stride convolution in the one-dimensional setting. Consider a 1D image of dimension $n$. Let the patch size be $r$ and stride be $d$. Let the patches be indexed from 1 and let patch $i$ start at position $(i-1)d+1$ and be contiguous through position $(i-1)d+r$. The matrix $P_{i}$ of dimension $r\times n$ corresponding to patch $i$ looks as follows,

where $0_{a\times b}$ indicates a matrix of dimension $a\times b$ with all zeros and $I_{a}$ indicates the identity matrix of size $a$.

Thus, the total number of patches is $k=\lfloor\frac{n-r}{d}\rfloor+1$. We will assume that $n\geq 2r-1$ and $r\geq d$. The latter condition is to ensure there is some overlap, non-overlapping case, which is easier, is handled in the next section.

We will bound the extremal eigenvalues of $P=\sum_{i,j=1}^{k}P_{i}P_{j}^{T}$. Simple algebra gives us the following structure for $P$,

For understanding, we show the matrix structure for $d=1$ and $n\geq 2r$.

The following lemmas bound the extremal eigenvalues of $P$.

Maximum eigenvalue of $P$ satisfies $\lambda_{\max}(P)\leq k(p+1)-(p-p_{2})(p_{2}+1)=O(kp)$ where $p=\lfloor\frac{r-1}{d}\rfloor$ and $p_{2}=\lfloor\frac{p}{2}\rfloor$.

Using Theorem 1, we have $\lambda_{\max}(P)\leq\max_{i}\left(P_{i,i}+\sum_{j\neq i}|P_{i,j}|\right)=\max_{i}\sum_{j=1}^{k}P_{i,j}$. Observe that $P$ is bisymmetric thus $\sum_{j=1}^{k}P_{i,j}=\sum_{j=1}^{k}P_{r-i+1,j}$ and we can restrict to the top half of the matrix. The structure of $P$ indicates that in a fixed row, the diagonal entry is maximum and the non-zero entries decrease monotonically by 1 as we move away from the diagonal. Also, there can be at most $p+1$ non-zero entries in any row. Thus the sum is maximized when there are $p+1$ non-zero entries and the diagonal entry is the middle entry, that is at position $p_{2}d+1$. By simple algebra,

Minimum eigenvalue of $P$ satisfies $\lambda_{\min}(P)\geq 0.5$.

We break the analysis into following two cases:

Case 1: $d<r/2$ We can show that $\lambda_{\max}(P^{-1})\geq 2$ using the structure of $P$ (see Lemma 1 and 2). Since $\lambda_{\min}(P)=1/\lambda_{\max}(P^{-1})$, we have $\lambda_{\min}(P)\geq 0.5$.

Case 2: $d\geq r/2$ In this case we directly bound the minimum eigenvalue of $P$. Using Theorem 1, we know that $\lambda_{\min}(P)\geq\min_{i}\left(P_{i,i}-\sum_{j\neq i}|P_{i,j}|\right)$. For $P_{i,j}\neq 0$, $|i-j|=ad$ for some $a$. The maximum value that $|i-j|$ can take is $r-1$ and since $d\geq r/2$, $a$ must be either 0 or 1. Also, for any $i$, there exists a unique $j$ such that $|i-j|=d$ since $r/2\leq d<r$, thus there are exactly 2 non-zero entries in each row of $P$, $P_{i,i}$. This gives us, for each $i$, $\sum_{j\neq i}P_{i,j}=k-1$. Thus, we get that $\lambda_{\min}(P)\geq\min_{i}\left(P_{i,i}-\left|\sum_{j\neq i}P_{i,j}\right|\right)=k-(k-1)=1$.

Combining both, we get the required result. ∎

1.2 Learning Result for 1D

Augmenting the above analysis with Theorem 2 gives us learnability of 1D convolution filters.

Combining the above Lemmas gives us that $\lambda_{\max}(P)=O(pk)=O(nr/d^{2})$ and $\lambda_{\min}(P)=\Omega(1)$. Observe that $\lambda_{\min}(P_{\Sigma})\geq\lambda_{\min}(P)\lambda_{\min}(\Sigma)$. Substituting these values in Theorem 2 gives us the desired result. ∎

Comparing with SGD, [BG17] showed that even for $r=2$ and $d=1$, Gradient descent can get stuck in a local minima with probability $\geq 1/4$.

2 2D Convolution

Here we formally define stride and patch convolutions in two dimensions. Consider a 2D image of dimension $n_{1}\times n_{2}$. Let the patch size be $r_{1}\times r_{2}$ and stride in both directions be $d_{1},d_{2}$ respectively. Enumerate patches such that patch $(i,j)$ starts at position $((i-1)d_{1}+1,(j-1)d_{2}+1)$ and is a rectangle with diagonally opposite point $((i-1)d_{2}+r_{1},(j-1)d_{2}+r_{2})$. Let $k_{1}=\lfloor\frac{n_{1}-r_{1}}{d_{1}}\rfloor+1$ and $k_{2}=\lfloor\frac{n_{2}-r_{2}}{d_{2}}\rfloor+1$. Let us vectorize the image row-wise into a $n_{1}n_{2}$ dimension vector and enumerate each patch row-wise to get a $r_{1}r_{2}$ dimensional vector.

Let $Q_{(i,j)}$ be the indicator matrix of dimension $r_{1}r_{2}\times n_{1}n_{2}$ with 1 at $(a,b)$ if the $a$th location of patch $(i,j)$ is $b$. More formally, $(Q_{(i,j)})_{a,b}=1$ for all $a=pr_{2}+q+1$ for $0\leq p<r_{1}$, $0\leq q<r_{2}$, and $b=((i-1)d_{1}+p)n_{2}+jd_{2}+q+1$ else 0. Note that there are $k_{1}\cdot k_{2}$ patches in total with the corresponding patch matrices being $Q_{(i,j)}$ for $1\leq i\leq k_{1},1\leq j\leq k_{2}$.

We will bound the extremal eigenvalues of $Q=\sum_{i,p=1}^{k_{1}}\sum_{j,q=1}^{k_{2}}Q_{(i,j)}Q_{(p,q)}^{T}$. Let $P^{(1)}_{i}$’s be the patch matrices corresponding to the 1D convolution for parameters $n_{1},r_{1},d_{1}$ defined as in the previous section and let $P^{(1)}=\sum_{i,j=1}^{k_{1}}P^{(1)}_{i}(P^{(1)}_{j})^{T}$. Define $P^{(2)}_{i}$’s for $1\leq i\leq k_{2}$ and $P^{(2)}$ similarly with parameters $n_{2},r_{2},d_{2}$ instead of $n_{1},r_{1},d_{1}$.

$Q_{(i,j)}=P^{(1)}_{i}\otimes P^{(2)}_{j}$.

Intuitively $P^{(1)}_{i}$ and $P^{(2)}_{j}$ give the indices corresponding to the row and column of the 2D patch and the Kronecker product vectorizes it to give us the $(i,j)$th patch. More formally, we will show that $(Q_{(i,j)})_{a,b}=1$ iff $(P^{(1)}_{i}\otimes P^{(2)}_{j})_{a,b}=1$.

Let $a=pr_{2}+q+1$ with $0\leq p<r_{1}$, $0\leq q<r_{2}$ and $b=rn_{2}+s+1$ with $0\leq r<n_{1}$, $0\leq s<n_{2}$. Then, $(P^{(1)}_{i}\otimes P^{(2)}_{j})_{a,b}=1$ iff $(P^{(1)}_{i})_{p,r}=1$ and $(P^{(2)}_{j})_{q,s}=1$. We know that $(P^{(1)}_{i})_{p,r}=1$ iff $r=(i-1)d_{1}+p+1$ and $(P^{(2)}_{j})_{q,s}=1$ iff $s=(j-1)d_{2}+q+1$. This gives us that $b=((i-1)d_{1}+p)n_{1}+(j-1)d_{2}+q+1$, which is the same condition for $(Q_{(i,j)})_{a,b}=1$. Thus $Q_{(i,j)}=P^{(1)}_{i}\otimes P^{(2)}_{j}$. ∎

We have $\lambda_{\min}(Q)\geq 0.25$ and $\lambda_{\max}(Q)=O(k_{1}p_{1}k_{2}p_{2})$ where $p_{1}=\lfloor\frac{r_{1}-1}{d_{1}}\rfloor$ and $p_{2}=\lfloor\frac{r_{2}-1}{d_{2}}\rfloor$.

Since $Q=P^{(1)}\otimes P^{(2)}$ and $Q,P^{(1)},P^{(2)}$ are positive semi-definite, $\lambda_{\min}(Q)=\lambda_{\min}(P)\lambda_{\min}(P^{(2)})$ and $\lambda_{\max}(Q)=\lambda_{\max}(P^{(1)})\lambda_{\max}(P^{(2)})$. Using the lemmas from the previous section gives us the required result. ∎

Note that this technique can be extended to higher dimensional patch structures as well.

2.2 Learning Result for 2D

Similar to the 1D case, combining the above analysis with Theorem 2 gives us learnability of 2D convolution filters.

Lemma 5 gives us that $\lambda_{\max}(Q)=O(n_{1}n_{2}r_{1}r_{2}/(d_{1}d_{2})^{2})$ and $\lambda_{\min}(P)=\Omega(1)$. Observe that $\lambda_{\min}(P_{\Sigma})\geq\lambda_{\min}(P)\lambda_{\min}(\Sigma)$. Substituting these values in Theorem 2 gives us the desired result. ∎

Non-overlapping Patches are Easy

In this section, we will show that if there is one patch that does not overlap with any patch and the covariance matrix is identity then we can easily learn the filter even if the other patches have arbitrary overlaps. This includes the commonly used Gaussian assumption. WLOG we assume that $P_{1}$ is the patch that does not overlap with any other patch implying $P_{1}P_{j}^{T}=P_{j}^{T}P_{1}=0$ for all $j\neq 1$.

Observe that the algorithm ignores the directions of all other patches and yet succeeds. This indicates that with respect to a Gaussian distribution, in order to have an interesting patch structure (for one layer networks), it is necessary to avoid having even a single disjoint patch. The following theorem shows the convergence of Convotron-No-Overlap.

The proof follows the outline of the Convotron proof very closely. We use the same definitions as in the previous proof. We have,

The last equality follows since $P_{i}^{T}P_{1}=0$ for all $i\neq 1$ and $P_{1}^{T}P_{1}$ is a permutation of identity.

Following the rest of the analysis for $\eta$ and $T$ as in the theorem statement gives us the required result. ∎

Experiments: SGD vs Convotron

To further support our theoretical findings, we empirically compare the performance of SGD (Algorithm 3) with our algorithm Convotron. We measure performance based on the failure probability, that is, the fraction of runs the algorithm fails to converge on randomly initialized runs (the randomness is over both the choice of initialization for SGD and the draws from the distribution). More formally, we say that the algorithm fails if the closeness in $l_{2}$-norm of the difference of the final weight vector obtained $(w_{T})$ and the true weight parameter ($w_{*}$), that is, $||w_{T}-w_{*}||$ is greater than a threshold $\theta$. We choose this measure because in practice, due to the high computation time of training neural networks, random restarts are expensive.

In the experiments, given a fixed true weight vector, for varying learning rates (increments of $0.01$), we choose 50 random initializations and run the two algorithms with them as starting points. We plot the failure probability ($\theta=0.1$) with varying learning rate. Note that the lowest learning rate we use is $0.01$ as making the learning rate too small requires high number of iterations for convergence for both algorithms.

We first test the performance on a simple 1D convolution case with $(n,k,d,T)=(8,4,1,6000)$ and 2D case with $(n_{1},n_{2},k_{1},k_{2},d_{1},d_{2},T)=(5,5,3,3,1,1,15000)$ on inputs drawn from a normalized ($l_{2}$ norm 1) Gaussian distribution with identity covariance matrix. We adversarially choose a fixed weight vectorWe take the vector to be $$in the 1D case and normalize. This weight vector can be viewed as an edge detection filter, that is, counting the number of times image goes from black (negative) to white (positive). ($l_{2}$-norm 1). Figure 3 (Top) shows that SGD has a small data dependent range where it succeeds but may fail with almost$0.5$probability outside this region whereas Convotron always returns a good solution for small enough$\eta$ chosen according to Theorem 2. The failure points observed for SGD show the prevalence of bad local minima where SGD gets stuck.

For the second experiment, we choose a fixed weight vector for which SGD performs well with very high probability on a normalized Gaussian input distribution with identity covariance matrix (see Figure 3 (Bottom-left)). However, on choosing a different covariance matrix with higher condition number $\sim 60$, the performance of SGD worsens whereas Convotron always succeeds (see Figure 3 (Bottom-Right)). The covariance matrix is generated by choosing random matrices followed by symmetrizing them and adding $cI$ for $c>0$ to make the eigenvalues positive.

These experiments demonstrate that techniques for fine-tuning SGD’s learning rate are necessary, even for very simple architectures. In contrast, no fine-tuning is necessary for Convotron: the correct learning rate can be easily computed given the learner’s desired patch structure and estimate of the covariance martix.

Acknowledgments

We thank Jessica Hoffmann and Philipp Krähenbühl for useful discussions.

References

Appendix A Omitted Proofs

Since $x$ is drawn from a symmetric distribution we have $E_{x\sim\mathcal{D}}[F(x)]=E_{x\sim\mathcal{D}}[F(-x)]$ for any function $F$. Thus, we have

Observe that $\sigma(c)-\sigma(-c)=\frac{(1-\alpha)|c|+(1+\alpha)c}{2}-\frac{(1-\alpha)|a|-(1+\alpha)c}{2}=(1+\alpha)c$. Substituting this in the above, we get the required result $2T_{1}=(1+\alpha)T_{2}$.

A.2 Proof of Lemma 2

The first equality follows from using Lemma 1 and the last follows since for all $i$, $P_{i}P_{i}^{T}$ is a permutation of the identity matrix by definition.

Using monotonicity of $\sigma$ and Jensen’s inequality, we also have,

Combining the two above lemmas, we get the required result.

A.3 Proof of Lemma 3

The first inequality follows from using Jensen’s, the second inequality follows from the 1-Lipschitz property of $\sigma$, the third follows from observing that $P_{i}P_{i}^{T}$ is a PSD matrix and the last inequality follows since for all $i$, $\lambda_{\max}(P_{i}P_{i}^{T})=1$ since $P_{i}P_{i}^{T}$ is a permutation of the identity matrix.

Appendix B Properties of Patch Matrix P𝑃P

Let $r=pd+q$ for some $p\geq 0$ and $1\leq q\leq d$.

For $d<r/3$, $P^{-1}$ has the following form:

where $\alpha_{0}=\beta+0.5$, $\alpha_{1}=\phi+0.5$, $\beta=\frac{0.5}{2k-p}$ and $\phi=\frac{0.5}{2k-p-1}$. Also, $\lambda_{\max}(P^{-1})\leq 2$.

We need to show that $A=PP^{-1}=I$. Observe that $P$ and $P^{-1}$ are bisymmetric, thus $A$ is centrosymmetric implying $A_{i,j}=A_{r-1-i,r-1-j}$. Hence, we need to only prove that the lower triangular matrix matches $I$. We show the result for $p>2$, as the same ideas apply for the other case.

To verify this, consider each diagonal entry,

$d\leq i\leq\lceil d/2\rceil$: $A_{i,i}=-0.5(k-1)+k-0.5(k-1)=1$.

$i\in\{1,\ldots,q\}$: $A_{i,i}=\alpha_{0}k-0.5(k-1)+\beta\left(k-p\right)=1$.

$i\in\{q+1,\ldots,d\}$: $A_{i,i}=\alpha_{1}k-0.5(k-1)+\phi\left(k-p-1\right)=1$.

For non-diagonal entries, that is, $j\neq i$,

$d\leq j\leq\lceil d/2\rceil$: $A_{i,j}=-0.5P_{i,j-d}+P_{i,j}-0.5P_{i,j+d}$. If $|i-j|=ad$ then $A_{i,j}=-0.5\left(k-a-1\right)+k-a-0.5\left(k-a+1\right)=0$, else $P_{i,j}=P_{i,j-d}=P_{i,j+d}=0\implies A_{i,j}=0$.

$j\in\{1,\ldots,q\}$: $A_{i,j}=\alpha_{0}P_{i,j}-0.5P_{i,j+d}+\beta P_{i,j+pd}$. Now if $i-j=ad$, then $A_{i,j}=\alpha_{0}(k-a)-0.5(k-a+1)+\beta(k-p+a)=0$ else $P_{i,j}=P_{i,j+d}=P_{i,j+pd}=0\implies A_{i,j}=0$.

$j\in\{q+1,\ldots,d\}$: $A_{i,j}=\alpha_{1}P_{i,j}-0.5P_{i,j+d}+\beta P_{i,j+pd}$. Now if $i-j=ad$, then $A_{i,j}=\alpha_{1}(k-a)-0.5(k-a+1)+\phi(k-p+a+1)=0$ else $P_{i,j}=P_{i,j+d}=P_{i,j+pd}=0\implies A_{i,j}=0$.

Using Theorem 1, we have $\lambda_{\max}(P^{-1})=\max_{i}\left(P^{-1}_{i,i}+\sum_{j\neq i}|P^{-1}_{i,j}|\right)$. If $q<d$, then $\lambda_{\max}(P^{-1})=\max(\alpha_{0}+0.5+\beta,\alpha_{1}+0.5+\phi,1+0.5+0.5)=\max(2\beta+1,2\phi+1,2)=2$ as $\beta,\phi\leq 0.5$ which follows from $2k-p-1\geq 1$. Similarly, when $q=d$, $\lambda_{\max}(P^{-1})=\max(\alpha_{0}+0.5+\beta,1+0.5+0.5)=\max(2\beta+1,2)=2$. ∎

For $r/3\leq d<r/2$, $P^{-1}$ has the following form:

where $\alpha_{0}=\beta+0.5$, $\alpha_{1}=\frac{k}{2k-1}$, $\beta=\frac{0.5}{2k-2}$ and $\phi=-\frac{k-1}{2k-1}$. Also, $\lambda_{\max}(P^{-1})\leq 2$.

Similar to the previous lemma, to verify this, consider each diagonal entry,

$d\leq i\leq\lceil d/2\rceil$: $A_{i,i}=-0.5(k-1)+k-0.5(k-1)=1$.

$i\in\{1,\ldots,q\}$: $A_{i,i}=\alpha_{0}k-0.5(k-1)+\beta\left(k-p\right)=1$.

$i\in\{q+1,\ldots,d\}$: $A_{i,i}=\alpha_{1}k+\phi(k-1)=1$.

For non-diagonal entries, that is, $j\neq i$,

$d\leq j\leq\lceil d/2\rceil$: $A_{i,j}=-0.5P_{i,j-d}+P_{i,j}-0.5P_{i,j+d}$. If $|i-j|=ad$ then $A_{i,j}=-0.5\left(k-a-1\right)+k-a-0.5\left(k-a+1\right)=0$, else $P_{i,j}=P_{i,j-d}=P_{i,j+d}=0\implies A_{i,j}=0$.

$j\in\{1,\ldots,q\}$: $A_{i,j}=\alpha_{0}P_{i,j}-0.5P_{i,j+d}+\beta P_{i,j+2d}$. Now if $i-j=ad$, then $A_{i,j}=\alpha_{0}(k-a)-0.5(k-a+1)+\beta(k-2+a)=0$ else $P_{i,j}=P_{i,j+d}=P_{i,j+pd}=0\implies A_{i,j}=0$.

$j\in\{q+1,\ldots,d\}$: $A_{i,j}=\alpha_{1}P_{i,j}+\phi P_{i,j+d}$. Now if $i-j=ad$, then $a=1$, implying $A_{i,j}=\alpha_{1}(k-1)+\phi k=0$ else $P_{i,j}=P_{i,j+d}=0\implies A_{i,j}=0$.

Similar to the previous lemma, we have $\lambda_{\max}(P^{-1})=\max(\alpha_{0}+0.5+\beta,\alpha_{1}+|\phi|,1+0.5+0.5)=\max(2\beta+1,1,2)=2$ as $\alpha_{1}+|\phi|=1$ and $\beta\leq 0.5$ which follows from $2k-p-1\geq 1$. ∎