How is Distributed ADMM Affected by Network Topology?

I Introduction

Optimization methods are at the core of statistics and machine learning. In this current age of ever-larger datasets, traditional in-memory methods do not scale, so distributed algorithms play a fundamental role. The Alternating Direction Method of Multipliers (ADMM) is one such excellent example since it is extremely robust, for instance does not assume differentiability of the objective function, it is often easy to implement, and easily distributed Boyd . Moreover, ADMM attains global linear convergence for separable and convex functions Hong2017 , and is guaranteed to converge even for several non-convex problems Wang , and empirically for many others Bento1 ; Bento2 ; Tom . Nevertheless, its convergence rate is still, in general, not fully understood. Most existing results only provide upper bounds on its asymptotic convergence rate without tightness guarantees. For more precise results, strong-convexity is usually assumed, even in centralized settings FrancaBento ; Jordan ; giselsson2017linear ; Deng2016 . Among practitioners ADMM also has a fame of being hard to tune.

In this paper we analyze how the exact and optimally tuned asymptotic convergence rate of a distributed implementation of over-relaxed ADMM depends on the topology of an underlying network. Through this network, several agents solving local problems share messages to one another with the common goal of solving a large optimization problem. One of our motivations is to understand, in a quantitative way, if ADMM is more or less sensitive to the network topology than distributed Gradient Descent (GD). We focus on a non-strongly-convex quadratic consensus problem not previously analyzed under ADMM.

Our goal is to provide a precise answer on how the convergence rate of ADMM when solving problem (1) depends on properties of $\mathcal{G}$. We also want to compare the convergence rate of ADMM with the convergence rate of GD when solving the same consensus problem.

The optimization problem (1) is deceptively simple, having the trivial solution $x_{i}=x_{j}$ if $i$ and $j$ belong to the same connected component of $\mathcal{G}$. However, it is not immediately obvious to which of these infinitely many possible solutions a given distributed algorithm will converge to. Different agents of the distributed implementation have to communicate to agree on the final solution, and the speed at which they reach consensus is a non-trivial problem. For instance, if we solve (1) through ADMM we have one agent per term of the objective function, and each agent has local copies of all the variables involved. The final solution is a vector where each component equals the average of the initial values of these local variables. Therefore, unsuspectingly, we have solved a distributed-average consensus problem, although in different form than typically studied, see e.g. erseghe2011fast ; Ghadimi2014averaging . Moreover, the objective function (1) naturally appears in several interesting problems. A classical example is the graph interpolation problem zhu2003semi , where one solves (1) subject to $z_{i}=c_{i}$ for $i\in\mathcal{V}^{\prime}$ where $\mathcal{V}^{\prime}\subset\mathcal{V}$ and $c_{i}$ is a fixed constant. The final solution has values on each node of $\mathcal{G}$ such that the nodes in $\mathcal{V}^{\prime}$ have the pre-assigned values, and the remaining nodes in $\mathcal{V}\backslash\mathcal{V}^{\prime}$ have values close to the values of their neighboring nodes depending on the topology of $\mathcal{G}$. Our analysis of ADMM to (1) may provide insights into other problems such as graph interpolation. Furthermore, it can give insights on how one can optimally split a decomposable objective function for a given optimization problem.

Let us formalize our problem. Define the asymptotic convergence rate, $\tau$, of an algorithm by

where $t$ is the iteration time, and $\bm{z}^{\star}$ is a minimizer of (1) that the iterate $\bm{z}^{t}$ converges to. Denote $\tau_{A}$ and $\tau_{G}$ be the convergence rates of ADMM and GD, respectively. We want to obtain the dependence $\tau_{A}=\tau_{A}(\mathcal{G})$ and $\tau_{G}=\tau_{G}(\mathcal{G})$, and also be able to compare the optimal rates, $\tau^{\star}_{A}$ and $\tau^{\star}_{G}$, when the parameters of both algorithms are optimally chosen.

The present work is motivated by an interesting idea recently proposed in FrancaBentoMarkov , which relates distributed ADMM to lifted Markov chains. It was shown that (i) ADMM is related to a quasi-Markov chain $\hat{\mathcal{M}}$, (ii) GD is related to a Markov chain $\mathcal{M}$, and (iii) $\hat{\mathcal{M}}$is a lifting of $\mathcal{M}$. In general, a lifted Markov chain $\hat{\mathcal{M}}$ is obtained from the base Markov chain $\mathcal{M}$ by expanding its state space in such a way that it is possible to collapse $\hat{\mathcal{M}}$ into $M$ and $\hat{\pi}$ into $\pi$, where $\hat{\pi}$ and $\pi$ are the respective stationary distributions (see chen1999lifting for details). The hope is that if $\mathcal{M}$ is slow mixing one can sample from $\pi$ by collapsing samples from $\hat{\pi}$, where $\hat{\mathcal{M}}$ mixes faster than $\mathcal{M}$. A measure of the time required for $\mathcal{M}$ to reach stationarity is given by the mixing time, denoted by $\mathcal{H}$. For many useful cases, the mixing time of the lifted chain, $\hat{\mathcal{H}}$, is smaller than $\mathcal{H}$. However, the achievable speedup is limited. For example, if $\mathcal{M}$ is irreducible then $\hat{\mathcal{H}}\geq C\sqrt{\mathcal{H}}$ for some constant $C\in(0,1)$, and there are several cases that actually achieve the lower bound, $\hat{\mathcal{H}}\approx C\sqrt{\mathcal{H}}$. The gain can be marginal if both $\mathcal{M}$ and $\hat{\mathcal{M}}$ are reversible, where one has $\hat{\mathcal{H}}\geq C\mathcal{H}$. Furthermore, for some graphs, for example graphs with low conductance, lifting never produces a significant speedup.

In FrancaBentoMarkov the quantity $(1-\tau_{A})^{-1}$ plays the role of $\hat{\mathcal{H}}$, while $(1-\tau_{G})^{-1}$ plays the role of $\mathcal{H}$. Based on the lifting relations between ADMM and GD, and the many cases where $\hat{\mathcal{H}}\approx C\sqrt{\mathcal{H}}$, it was conjectured that

for some constant $C$. Above, $\tau^{\star}$ denotes the optimal convergence rate, attained under optimal parameter selection. It is important that both algorithms are optimally tuned since a poorly tuned ADMM can be slower than a well-tuned GD. The inequality (3) was supported by empirical evidence but its proof remains lacking. As pointed out FrancaBentoMarkov , the inequality (3) is much stronger than the analogous relation in lifted Markov chains theory. The claim is that it holds for any graph $\mathcal{G}$, even the ones whose Markov chains do not accelerate via lifting.

The rest of the paper is organized as follows. In Section II we mention related work and point out the differences and novelty in our approach. In Section III we introduce important notation and concepts by explicitly writing distributed over-relaxed ADMM as a message passing algorithm. We then present our main contributions, which in short are: (i) in Section IV, we prove a relation between the spectrum of a nonsymmetric matrix related to the evolution of ADMM and the spectrum of the transition matrix of a random walk on $\mathcal{G}$. This relates ADMM to random walks on $\mathcal{G}$, capturing the topology of the graph. (ii) We also prove explicit formulas for optimal parameter selection, yielding interesting relations to the second largest eigenvalue of the transition matrix of the graph $\mathcal{G}$ and the spectral gap. (iii) In Section V, we resolve the conjectured inequality (3), and moreover, provide an upper bound. The proofs of our main results are in the Appendix.

II Related Work

Although problem (1) is simple our results cannot be directly derived from any of the many existing results on the convergence of ADMM. First of all, we compute the exact asymptotic convergence rate when distributed ADMM is optimally tuned, while the majority of previous works only compute non-optimal upper bounds for the global convergence rate. Second, our convergence rate is linear, and most works able to prove tight linear convergence assume strong convexity of at least some of the functions in the objective; see for instance shi2014linear ; giselsson2014diagonal ; giselsson2017linear ; Deng2016 . It is unclear if we can cast our non-strongly-convex problem in their form and recover our results from their bounds, given especially that most of these results are not simple or explicit enough for our purposes. These bounds often have a complex dependency on problem’s parameters, but can be numerically optimized as suggested by giselsson2014diagonal ; giselsson2017linear . It is also unknown if these numerical procedures lead to optimal rates of convergence. Linear convergence rates were proven without strong convexity Hong2017 , but these bounds are too general and not tight enough for our purposes. Moreover, many results not requiring strong convexity focus on the convergence rate of the objective function, as opposed to this paper which studies the convergence rate of the variables; see for example davis2014convergence ; davis2017faster .

In erseghe2011fast ; Ghadimi2014averaging ADMM is applied to the consensus problem $f(\bm{z})=\sum_{i\in\mathcal{V}}\sum(z_{i}-c_{i})^{2}$, subject to $z_{i}=z_{j}$ if $(i,j)\in\mathcal{E}$, where $c_{i}>0$ are constants. This problem, which is related to several optimization-based distributed averaging algorithms, is strongly-convex and not equivalent to (1). Several papers consider $f(\bm{z})=\sum_{i}f_{i}(\bm{z})$ with ADMM updates that are insensitive to whether or not $f_{i}(\bm{z})$ depends on a subset of the components of $\bm{z}$; see wei2012distributed ; ling2015dlm ; makhdoumi2014broadcast ; makhdoumi2017convergence ; ling2016communication and references therein. In our setting, distributed ADMM is a message-passing algorithm where the messages between agents $i$ and $j$ are related only to the variables shared by functions $f_{i}$ and $f_{j}$. Thus, our implementation is fully local, and not only the processing but also the data is distributed. These papers solve $\min_{\bf z}\sum_{i}f_{i}(\bm{z})$ over a communication network by recasting the problem as $\min\sum_{i}f_{i}(\bm{x}_{i})$ subject to $\bm{x}_{i}=\bm{x}_{j}$ if $(i,j)$ are edges in the network. Slight variations of this transformation and the definition of the communication network exist. Several of these works try to understand how topology of the network affects convergence, for instance ling2015dlm ; makhdoumi2014broadcast ; makhdoumi2017convergence ; ling2016communication . The results of makhdoumi2014broadcast ; makhdoumi2017convergence are applicable to non-strongly-convex objectives but linear convergence rates are not proven. An interesting adaptive ADMM for a general convex consensus problem was recently proposed TomConsensus , with a sublinear convergence guarantee. However, no dependence on the underlying graph was considered. It is important to note that, even for GD, the dependency of the convergence rate on $\mathcal{G}$ for variants of problem (1) have only being studied in the past decade olfati2004consensus ; tron2008distributed ; tron2013riemannian .

For quadratic problems there are explicit results on convergence rate and optimal parameters teixeira2013optimal ; ghadimi2015optimal ; iutzeler2014linear ; iutzeler2016explicit . However, the required assumptions do not hold for the distributed consensus problem considered in this paper. Moreover, there are very few results comparing the optimal convergence rate of ADMM as a function of the optimal convergence rate of GD. An explicit comparison is provided in FrancaBento , but assumes strong convexity and considers a centralized setting. The authors in mokhtari2015decentralized study a variant of the ADMM where the iterations deal with the second order expansion of the objective, and strong-convexity is assumed. In raghunathan2014optimal ; raghunathan2014admm bounds on the convergence rate were proven, which are subsequently tuned for ADMM applied to a quadratic program of the kind $\min_{\bf z}{\bf z}^{\top}Q{\bf z}+c^{\top}{\bf z}$ subject to $A{\bf z}=b$, and also assume strong convexity. The work boley2013local focuses on quadratic programs that are not necessarily strongly-convex. To the best of our knowledge, this is the only work that, just like we do here, analyzes ADMM for quadratic problems in a setting where the important eigenvalues of the transition matrix might be complex numbers. However, no optimal bounds explicitly dependent on $\mathcal{G}$ are provided. The authors of han2013local also study ADMM for quadratic programs that might not be strongly-convex. They define their error rate in a different way compared to us, and it is not clear if they are comparable. Also, their bounds are generic and are not optimally tuned.

The problem of determining optimal rates of convergence is related to optimal parameter selection. Apart from the tuning rules mentioned above, several adaptive schemes exist, and some of these come with convergence guarantees he2000alternating ; Boyd ; xu2016adaptive ; xu2017adaptive . However, these are designed for very general problems and do not recover our results. We consider ADMM’s parameters fixed across iterations.

Our work makes connections between ADMM, GD, and Markov chains. In particular, lifted Markov chains were previously employed to speedup convergence of distributed averaging and gossip algorithms jung2007fast ; li2010location ; jung2010distributed , but these algorithms are not related to ADMM. Finally, the present work is highly motivated by FrancaBentoMarkov where a close relation between ADMM and lifted Markov chains was proposed. The main outcome was conjecture (3), which is inspired by the speedup on the mixing time of several lifted Markov chains. This inequality will be proven in this paper as a consequence of our main analysis.

III Distributed ADMM as a Message Passing Algorithm

Let us start by introducing the factor graph $\bar{\mathcal{G}}$ associated to the base graph $\mathcal{G}$ of problem (1). The factor graph $\bar{\mathcal{G}}=(\bar{\mathcal{F}},\bar{\mathcal{V}},\bar{\mathcal{E}})$ is a bipartite and undirected graph, where the edges in $\bar{\mathcal{E}}$ can only connect vertices in $\bar{\mathcal{F}}$ to vertices in $\bar{\mathcal{V}}$. The $a$th vertex in $\bar{\mathcal{F}}$ is the $a$th term $f_{a}$ in the objective (1). In other words, we have a function vertex $f_{a}$ for every edge in $\mathcal{E}$. Vertices in $\bar{\mathcal{F}}$ are called function nodes. The $b$th vertex in $\bar{\mathcal{V}}$ is the $b$th component $z_{b}$ of $\bm{z}$. We have a variable vertex per dimension of $\bm{z}$. Vertices in $\bar{\mathcal{V}}$ are called variable nodes. The edges in $\bar{\mathcal{E}}$ are of the form $(f_{a},z_{b})$. The crucial point in defining $\bar{\mathcal{G}}$ is that the edge $(f_{a},z_{b})$ is present in $\bar{\mathcal{E}}$ if and only if $f_{a}$ depends on the $z_{b}$ component of $\bm{z}$. To simplify the notation, sometimes we interchangeably refer to vertices and edges only by their labels, thus we might write $(f_{a},z_{b})=(a,b)$ with $a\in\bar{\mathcal{F}}$ and $b\in\bar{\mathcal{V}}$. Therefore, $\bar{\mathcal{V}}=\mathcal{V}$ and $|\bar{\mathcal{E}}|=2|\mathcal{E}|$. We refer to Fig. 1 for an illustration.

where $Q$ is a block diagonal matrix with blocks in the form $Q_{a}=\left(\begin{smallmatrix}+1&-1\\ -1&+1\end{smallmatrix}\right)$, and adding the constraint

The idea is that the ADMM can exploit this decoupled objective function and solve problem (1) in a distributed manner, by coordinating local messages that are computed only based on each $f_{a}$.

Above, $\gamma\in(0,2)$ is the over-relaxed parameter, $\rho>0$ is the penalty parameter, and $t$ is the iteration time. One can check that (7) is consistent with the standard non-distributed over-relaxed ADMM updates Boyd . We can see the above updates as a message passing algorithm as illustrated in Fig. 1b. The only messages shared through the network are $m_{ab}$ and $n_{ab}$, and every node keeps and updates a copy of the components of $\bm{u}$ corresponding to edges incident on itself. All the updates only require local information. This scheme is on the same lines as the one proposed in Bento1 ; Bento2 .

Replacing the decoupled objective (5) explicitly into the updates (7), and introducing the variable $\bm{s}=S\bm{z}$, the above scheme can be written in the following matrix form:

where $S$ is defined in (4) and we have introduced the operators

Note that $B=B^{\top}$ is symmetric and moreover $B^{2}=B$, thus it is an orthogonal projection operator. Its orthogonal complement is denoted by $B^{\perp}\equiv I-B$, satisfying $BB^{\perp}=B^{\perp}B=0$.

Although the updates (8) have a total of $5\times|\bar{\mathcal{E}}|$ dimensions, a result from FrancaBentoMarkov shows that these can be reduced to the following linear system in only $|\bar{\mathcal{E}}|$ dimensions:

where all the other variables in (8) depend only on $\bm{n}^{t}$.

We are interested in computing the convergence rate $\tau$ defined in (2). A straightforward adaptation of standard results from Markov chain theory gives us the following.

Consider the linear system $\bm{\xi}^{t+1}=T\bm{\xi}^{t}$, and let $\bm{\xi}^{\star}$ be a fixed point. If the spectral radius is $\rho(T)=1$ and it is attained by the eigenvalue $\lambda_{1}(T)=1$ with multiplicity one, then $\bm{\xi}^{t}=T^{t}\bm{\xi}^{0}$ converges to $\bm{\xi}^{\star}$ and satisfies $\|\bm{\xi}^{t}-\bm{\xi}^{\star}\|=\Theta(|\lambda_{2}|^{t})$, where $\lambda_{2}=\lambda_{2}(T)$ is the second largest eigenvalue of $T$ in absolute value (the largest is $\lambda_{1}(T)=1$).

Since $T_{A}$ in (10) is nonsymmetric, its eigenvalues can be complex. We thus order them by magnitude:

When the order of a particular eigenvalue is not important, we drop the index and simply write $\lambda(T_{A})$.

Notice that the optimization problem (1) is convex and has solution $\bm{z}^{\star}=c\bm{1}$ for any constant $c$, which spans a linear space of dimension one. It is straightforward to check that $\lambda_{1}(T_{A})=1$ is unique (with eigenvector being the all-ones vector) and every other eigenvalue satisfies $|\lambda_{n}(T)|<1$, for $n=2,\dotsc,|\bar{\mathcal{E}}|$. Due to Theorem 1, the asymptotic convergence rate of ADMM is thus determined by the second largest eigenvalue $\tau_{A}=|\lambda_{2}(T_{A})|$.

IV Computing the Spectrum of ADMM

As explained above, our problem boils down to finding the spectrum of $T_{A}$. First, we write this operator in a more convenient form (the proof can be found in Appendix A).

The matrix $T_{A}$ defined in (10) can be written as

with $\widetilde{B}=\widetilde{B}^{\top}=2B-I$, $\Omega=\widetilde{B}R$, and $R=R^{\top}=I-Q$. In particular, $\Omega$ is orthogonal, i.e. $\Omega^{\top}\Omega=\Omega\,\Omega^{\top}=I$, and the other symmetric matrices satisfy $\widetilde{B}^{2}=I$ and $R^{2}=I$.

Notice that the spectrum of $T_{A}$ can be easily determined once we know the spectrum of $U$. In particular, if $\rho=0$ then $U=\Omega$ is orthogonal and its eigenvalues lie on the unit circle in the complex plane. Thus, we may expect that for $\rho$ sufficiently small, the eigenvalues of $U$ lie in a perturbation of this circle. It turns out that, in general, the eigenvalues of $U$ either lie on a circle in the complex plane, with center at $1-\gamma/2$ and radius $\tfrac{\gamma}{2}\sqrt{(2-\rho)/(2+\rho)}$, or on the real line. Furthermore, by exploring properties of the matrices of Lemma 2 we can calculate the spectrum of $U$ exactly for any $\rho>0$ in terms of the spectrum of the original graph $\mathcal{G}$. This is one of our main results, whose proof is in Appendix B.

Let $\mathcal{W}=\mathcal{D}^{-1}\mathcal{A}$ be the probability transition matrix of a random walk on the graph $\mathcal{G}$, where $\mathcal{D}$ is the degree matrix and $\mathcal{A}$ the adjacency matrix. For each eigenvalue $\lambda(\mathcal{W})\in(-1,1)$, the matrix $T_{A}$ in (12) has a pair of eigenvalues given by

Conversely, any eigenvalue $\lambda(T_{A})$ is of the form (13) for some $\lambda(\mathcal{W})$.

In general, the eigenvalues of $T_{A}$ are complex. However, $T_{A}$ always has the largest eigenvalue $\lambda_{1}(T_{A})=1$, which can also be obtained from (13) if we replace $\lambda_{1}(\mathcal{W})=1$ and pick the negative sign in (13). Another important real eigenvalue is the following (see Appendix C).

The matrix $T_{A}$ has eigenvalue $\lambda(T_{A})=1-\gamma$ if and only if the graph $\mathcal{G}$ has a cycle of even length.

In the results to follow we assume that $T_{A}$ has the eigenvalue $1-\gamma$ since this encloses the most interesting cases. We can still carry out the analysis when this is not the case, however we omit these results for conciseness and simplicity.

Henceforth, we always assume that $\mathcal{G}$ has at least one cycle of even length. Observe that, for many families of randomly generated graphs, this occurs with overwhelming probability. Consider sampling $\mathcal{G}$ from an Erdös-Rényi model with $n$ vertices and edge probability $p$. There are $C(n,k)=\left(\begin{smallmatrix}n\\ k\end{smallmatrix}\right)$ ways of choosing $k$ vertices, and the probability that each set of $k$ nodes forms a cycle is at least $p^{k}$. Therefore, the probability that there will be no $k$-cycle in $\mathcal{G}$ is upper bounded by $(1-p^{k})^{C(n,k)}$ which is extremely small.

A few observations about $\mathcal{W}$ are in order. It is known that the eigenvalues of $\mathcal{W}$ are in the range $\lambda(\mathcal{W})\in$. The second largest eigenvalue of $\mathcal{W}$, denoted by $w^{\star}\equiv\lambda_{2}(\mathcal{W})$, and the corresponding eigenvalue of $T_{A}$ from formula (13), play an important role in computing the optimal convergence rate $\tau^{*}_{A}$. Moreover, the second largest eigenvalue $w^{\star}$ is related to the mixing time of the Markov chain associated to $\mathcal{W}$, and also to the conductance $\Phi\in$ of the graph $\mathcal{G}$ by the Cheeger bound Cheeger :

The conductance $\Phi$ tells us whether or not $\mathcal{G}$ has bottlenecks, and higher $\Phi$ implies a fast mixing chain lovasz1999faster . The conductance of $\mathcal{G}$ is defined by

where $d_{i}$ is the degree of node $i$ and $C(\mathcal{S})$ is cut-value induced by $\mathcal{S}$, i.e. the number of edges that cross from $\mathcal{S}$ to $\mathcal{V}\backslash\mathcal{S}$.

In the context of FrancaBentoMarkov , which motivated this paper, the most interesting cases are Markov chains that have low conductance and are known to not speedup via lifting. Therefore, we will present our results for graphs $\mathcal{G}$ where the second largest eigenvalue of the transition matrix $\mathcal{W}$ lies in the range $0\leq\omega^{\star}<1$, which is implied by $\Phi\leq 1/2$.

We now discuss the behaviour of the eigenvalues of $T_{A}$. From the formula (13) we just need to analyse the complex eigenvalues of the operator $U$, defined in (12), which are given by $\lambda(U)=\lambda(\mathcal{W})\pm i\sqrt{1-\rho^{2}/4-\lambda^{2}(\mathcal{W})}$. Therefore, $\lambda(U)$ lies on a circle of radius $\sqrt{1-\rho^{2}/4}$, and each eigenvalue becomes real when $\rho^{2}/4+\lambda^{2}(\mathcal{W})\geq 1$. All eigenvalues become real when $\rho>2$. When $\rho=0$ the circle has unit radius, and as $\rho$ increases the radius of the circle shrinks. Note that only the imaginary part of $\lambda(U)$ changes with $\rho$, so every complex conjugate pair of eigenvalues move vertically downwards until they fall on the real line, one moving to the left and the other to the right. We illustrate this behaviour in Fig. 2 where we show the corresponding eigenvalues of $T_{A}$. The eigenvalues marked in red move on the vertical dashed line as we increase $\rho$. Notice also from (13) that as $\rho\to\infty$ all eigenvalues tend to either $\lambda(T_{A})\to 1$ or $\lambda(T_{A})\to 1-\gamma$.

To tune ADMM we need to minimize the second largest, in absolute value, eigenvalue of $T_{A}$. The minimum will come from either the conjugate pairs in (13) with $\omega^{\star}=\lambda_{2}(\mathcal{W})$, marked in red in Fig. 2, or from the real eigenvalue $1-\gamma$ of Lemma 4, marked in green in Fig. 2. We can keep increasing $\rho$ to make the radius of the circle the smallest possible, which happens when these complex eigenvalues have vanishing imaginary part. This determines the best parameter $\rho^{\star}$. Now we can fix $\gamma^{\star}$ by making $|1-\gamma|$ the same size as the norm of the previous complex conjugate eigenvalues. Using these ideas we obtain our next result, whose proof is contained in Appendix C.

Assume that the graph $\mathcal{G}$ has at least one cycle of even length, and conductance $\Phi\leq 1/2$. Let $\mathcal{W}=\mathcal{D}^{-1}\mathcal{A}$ be the transition matrix of a random walk on $\mathcal{G}$, and denote its second largest eigenvalue by $\omega^{\star}=\lambda_{2}(\mathcal{W})\in(0,1)$. Let $\lambda_{2}(T_{A})$ be the second largest, in absolute value, eigenvalue of $T_{A}$. The best possible convergence rate of ADMM is thus given by

The above theorem provides optimal parameter selection for over-relaxed ADMM in terms of the second largest eigenvalue $\omega^{\star}=\lambda_{2}(\mathcal{W})$ of the transition matrix, which captures the topology of $\mathcal{G}$. Recall that $\omega^{\star}$ is also related to the well-known spectral gap.

We can still solve the analogous of Theorem 5 when the graph $\mathcal{G}$ does not have even length cycles, or $\mathcal{G}$ has high conductance. However, this does not introduces new insights and slightly complicates the analysis. To be concrete, we just state one of such cases below.

Consider a case where $\mathcal{G}$ does not have a cycle of even length, for example when $\mathcal{G}$ is a tree, thus $\lambda(T_{A})=1-\gamma$ does not exist. The most interesting case is for slow mixing chains, $\Phi\leq 1/2$, and analogously to Theorem 5 we obtain the following result.

Assume that the graph $\mathcal{G}$ has no cycles of even length, and has conductance $\Phi\leq 1/2$. Let $\mathcal{W}=\mathcal{D}^{-1}\mathcal{A}$ be the transition matrix of a random walk on $\mathcal{G}$. Denote the second largest eigenvalue of the transition matrix $\mathcal{W}$ by $\omega^{\star}\in(0,1)$, and $\bar{\omega}$ its smallest eigenvalue different than $-1$. Assume that $|\bar{\omega}|\geq\omega^{*}$. Let $\lambda_{2}(T_{A})$ be the second largest, in absolute value, eigenvalue of $T_{A}$. The best possible convergence rate of ADMM is given by

Notice that if we replace $\bar{\omega}=-1$ in the above formulas we recover the results from Theorem 5. Furthermore, a straightforward calculation shows that the rate (16) is always an upper bound for the rate (18). In fact, we can show that (16) is always an upper bound for $\tau^{*}_{A}$ regardless of the topology of $\mathcal{G}$. We omit these results for simplicity, as well as a proof of Theorem 6 since it is analogous to the proof of Theorem 5.

IV.2 Numerical examples

We provide some numerical experiments illustrating our theoretical results by considering the graphs shown in Table 1. The second largest eigenvalue of the transition matrix, $\omega^{\star}$, is determined by the graph. The conductance $\Phi$ is computed by direct inspection of $\mathcal{G}$ and (15). The other quantities are computed from our theoretical predictions, e.g. Theorem 5 and Theorem 6. For each graph, in Fig. 3 we show the corresponding convergence rates from a numerical computation of the second largest eigenvalue of $T_{A}$, denoted by $\lambda_{2}$. We fix several values of $\gamma$ and plot $|\lambda_{2}|$ versus $\rho$. The solid blue lines in the plots correspond to our theoretical prediction for the optimal convergence rate $\tau_{A}^{\star}$, whose values are in Table 1. The red lines show the convergence rate as function of $\rho$ for optimal $\gamma=\gamma^{*}$ from a numerical computation. Both curves touch under optimal parameter tuning, confirming our theoretical predictions. The remaining curves show suboptimal rates.

For the graphs in (a) and (b) of Table 1 the assumptions of Theorem 5 hold, thus we can find optimal parameters through the formulas (16) and (17), whose values are indicated. In Fig. 3a and Fig. 3b we can see that the optimal numerical rates (red lines) match the prediction of formula (16) (blue lines). We also included two other curves using the values $\gamma=1.3$ and $\gamma=1.6$ to show that the rates becomes suboptimal if $(\rho,\gamma)\neq(\rho^{*},\gamma^{*})$.

For the graph in (c) the assumptions of Theorem 5 do not hold since the conductance $\Phi>1/2$. A similar analysis as of Theorem 5 shows that, for all graphs with even cycles and high conductance we have $\tau^{*}_{A}=1/3$, $\gamma^{*}=4/3$ and $\rho^{*}=2$, which are the values indicated in Table 1. We omit this proof for simplicity of presentation. In Fig. 3c we show that a numerical calculation matches this prediction (blue and red lines). The curves with $\gamma_{1}=1.2$ and $\gamma_{2}=1.5$ give suboptimal rates. A misapplication of Theorem 5 gives $\rho_{3}\approx 1.886$, $\gamma_{3}\approx 1.414$ and $\tau_{A}^{(3)}\approx 0.414$, which still gives an upper bound on the optimal $\tau_{A}^{\star}=1/3$. Using the value of $\gamma_{3}$ to numerically compute $\lambda_{2}(\rho)$ yields the curve shown in dashed line.

Theorem 6 holds to the case of the graph in item (d), whose predictions are shown in Table 1. These agree with the numerical results shown in Fig. 3d. A misapplication of Theorem 5 yields $\rho_{3}\approx 1.351$, $\gamma_{3}\approx 1.563$ and $\tau_{A}^{(3)}\approx 0.659$, which still upper bounds $\tau_{A}^{\star}\approx 0.536$. Using $\gamma_{3}$ to compute $\lambda_{2}(\rho)$ yields the suboptimal rate shown in dashed line.

V Comparison with Gradient Descent

We now compare the optimal convergence rates of distributed ADMM and GD, denoted by $\tau_{A}^{\star}$ and $\tau_{G}^{\star}$, respectively. Let us first recall that the convergence rate of GD is related to eigenvalues of the graph Laplacian. We can write the objective function (1) explicitly as

where $N_{i}$ is the neighboring set of node $i\in\mathcal{V}$, and $d_{i}$ is its degree. Using the component form of GD update, $z_{k}^{t+1}=z_{k}^{t}-\alpha\partial_{z_{k}}f(z^{t})$, and noticing that the last term of (20) does not contribute since $i\neq j$, we obtain z_{k}^{t+1}=z_{k}^{t}-\alpha\big{(}d_{k}z_{k}^{t}-\sum_{j\in N_{k}}z_{j}^{t}\big{)}. Notice also that $\sum_{j\in N_{k}}z_{j}=\sum_{j\in\mathcal{V}}\mathcal{A}_{kj}z_{j}$, where $\mathcal{A}$ is the adjacency matrix of $\mathcal{G}$. Therefore, writing this result in matrix form we have

where $L\equiv\mathcal{D}-\mathcal{A}$ is the Laplacian of $\mathcal{G}$. Since the eigenvalues of $L$ are real, we assume the following ordering: $\lambda_{1}(L)\geq\lambda_{2}(L)\geq\dotsc\geq\lambda_{|\mathcal{E}|-1}(L)\geq\lambda_{|\mathcal{E}|}(L)=0.$

To relate this result with the transition matrix $\mathcal{W}$, note that $\mathcal{D}^{1/2}\mathcal{W}\mathcal{D}^{-1/2}=\mathcal{D}^{-1/2}\mathcal{A}\mathcal{D}^{-1/2}\equiv I-\mathcal{L}$, where $\mathcal{L}$ is the normalized Laplacian of $\mathcal{G}$. Thus, both operators have the same eigenvalues, $\lambda(\mathcal{W})=1-\lambda(\mathcal{L}),$ which are all real. We now use the following bounds (zumstein2005comparison, , Lemmas 2.12 and 2.21):

Assume that the graph $\mathcal{G}$ has an even length cycle and $\Phi\leq 1/2$, such that Theorem 5 holds. Then, there is C=1-\mathcal{O}\big{(}\sqrt{\delta}\big{)} such that

where $\Delta=d_{\textnormal{max}}/d_{\textnormal{min}}$ is the ratio of the maximum to the minimum degree of $\mathcal{G}$. Here $\delta=1-\omega^{\star}$ is the spectral gap.

The lower bound in (24) provides a proof of conjecture (3), proposed in FrancaBentoMarkov . Notice that the upper bound in (24) implies that ADMM cannot improve much more than this square root factor. However, this upper bound becomes more loose for very irregular graphs, which have $\Delta\gg 1$, compared to regular graphs, which have $\Delta=1$. Moreover, as briefly mentioned before, since Theorem 5 provides an upper bound on $\tau_{A}^{\star}$ regardless of the topology of $\mathcal{G}$, the lower bound in (24) still remains valid for any graph. Numerical results illustrating the lower bound in (24) were already provided in FrancaBentoMarkov .

VI Final Remarks

We provided a thorough analysis of distributed over-relaxed ADMM when solving the non-strongly-convex consensus problem (1) in terms of spectral properties of the underlying graph $\mathcal{G}$; see Theorem 3. The exact asymptotic convergence rate of ADMM depends on the second largest eigenvalue of the transition matrix of $\mathcal{G}$. This result directly relates distributed ADMM to a Markov chain. We also provided explicit formulas for optimal parameter selection; see Theorem 5 and Theorem 6. Comparing the optimal convergence rates of distributed ADMM and GD, we were able to prove a recent conjecture based on a close analogy with lifted Markov chains FrancaBentoMarkov . We showed that, for problem (1) over any graph $\mathcal{G}$, when both algorithms are optimally tuned, distributed ADMM always provides a speedup given by a square root factor compared to GD; see Theorem 7.

We believe that our results and methods may shed a new light into distributed optimization, in particular for ADMM. For instance, it provides the first steps towards a better understanding of how distributed ADMM behaves when splitting a decomposable objective function. It would be certainly desirable, and interesting, to extend our analysis to more general settings. We hope the results presented here motivate future research in this direction.

Appendix A Proof of Lemma 2

We repeat, then prove, the statement of Lemma 2 in the main text below.

The matrix $T_{A}$ defined in (10) can be written as

with $\widetilde{B}=\widetilde{B}^{\top}=2B-I$, $\Omega=\widetilde{B}R$, and $R=R^{\top}=I-Q$. In particular, $\Omega$ is orthogonal, i.e. $\Omega^{\top}\Omega=\Omega\,\Omega^{\top}=I$, and the other symmetric matrices satisfy $\widetilde{B}^{2}=I$ and $R^{2}=I$.

Due to the block diagonal structure of $Q$, the matrix $A$ in (9) can be written as

Write $Q=I-R$, where $R$ is block diagonal with each block in the form $R_{a}=\left(\begin{smallmatrix}0&1\\ 1&0\end{smallmatrix}\right)$ for $a\in\bar{\mathcal{F}}$. We therefore have

Replacing this expression into (10) it is possible to reorganize the terms in the form (12). ∎

Appendix B Proof of Theorem 3

We first present several intermediate results that will be necessary to establish Theorem 3 from the main text.

Let $U$ be a nonsingular matrix, and let $V\equiv\tfrac{1}{2}\left(U+\eta\,U^{-1}\right)$ for some constant $\eta$. If $v$ is an eigenvalue of $V$, then $U$ has at least one of the following eigenvalues:

Conversely, every eigenvalue of $U$ has the form (28) for either $u^{+}$, $u^{-}$ or both, for some eigenvalue $v$ of $V$.

We have $\det\left(V-vI\right)=0$ if and only if $v$ is an eigenvalue of $V$. From the definition of $V$ we can this write as

Since $\det U^{-1}\neq 0$ by assumption, at least one of the other determinants must vanish, showing that either $u^{+}$ or $u^{-}$ (or both) are eigenvalues of $U$.

For the second part, consider the eigenvalue equation $U\bm{u}=u\,\bm{u}$. It follows that $V\bm{u}=(U+\eta U^{-1})\bm{u}=\left(\tfrac{1}{2}\left(u+\eta\,u^{-1}\right)\right)\bm{u}$, thus for every eigenvalue $u$ we have that $v=\tfrac{1}{2}\left(u+\eta\,u^{-1}\right)$ is an eigenvalue of $V$, or equivalently, $u$ satisfy the quadratic equation $u^{2}-2vu+\eta=0$ for some eigenvalue $v$ of $V$. The roots of this equation are given by (28), thus $u$ must be equal to at least one of these roots. ∎

where $\Omega\equiv\widetilde{B}R$ is orthogonal, $\widetilde{B}\equiv 2B-I$, and the symmetric operators $\widetilde{B}$ and $\widetilde{R}$ both satisfy $\widetilde{B}^{2}=I$ and $R^{2}=I$. The inverse of $U$ is given by

We also have the following relation for the symmetric part of $\Omega$:

This can be checked by direct substitution. ∎

The eigenvalues of $\Omega_{S}$ are in the range $$.

This follows trivially from (32) and orthogonality of $\Omega$. The eigenvalues of $\Omega$ have the form $\lambda(\Omega)=e^{i\theta}$ for $\theta\in(-\pi,\pi]$. Since $\Omega^{\top}=\Omega^{-1}$, we have $\lambda(\Omega_{S})=\cos\theta\in$. ∎

From Lemma 9 and Lemma 10 we immediately know that all eigenvalues of (30) have the form (28) with $v\to\lambda(\Omega_{S})$ and $\eta\to 1-\rho^{2}/4$, for either $u^{+}$ or $u^{-}$. Now if we exclude the extremes of the interval where $\lambda(\Omega_{S})$ lie, according to Lemma 11, we have a stronger version of this result.

If $w_{S}\in(-1,1)$ is an eigenvalue of $\Omega_{S}$, then the operator (30) has a pair of eigenvalues given by

Lemma 9 already implies that $U$ have eigenvalues (33) for at least one of the choices $u^{\pm}$. It remains to show that both occur if $w_{S}\in(-1,1)$. First, consider the case where $\rho=0$. We have $u^{\pm}=w_{S}\pm i\sqrt{1-(w_{S})^{2}}$, and since $|w_{S}|<1$, both $u^{\pm}$ are a complex conjugate pair. Since $U$ is real, its complex eigenvalues always occur in conjugate pairs, thus both $u^{\pm}$ are eigenvalues of $U$.

For small enough $\rho>0$ the eigenvalues $u^{\pm}$ in (33) are also complex, so both must be eigenvalues of $U$. Therefore, for small enough $\rho$, the characteristic polynomial of $U$ has a factor of the form

Now $\det(U-uI)$ is a polynomial in both $u$ and $\rho$, and since a polynomial is uniquely determined by its coefficients, the same factors in (34) will be present in the characteristic polynomial of $U$ for any $\rho$, implying that both $u^{\pm}$ are eigenvalues of $U$ for any $\rho>0$. ∎

We will show that, if we restrict ourselves to the interval $(-1,1]$, the eigenvalues $w_{S}$ of $\Omega_{S}$ are the same as the eigenvalues of the transition matrix $\mathcal{W}$ of the original graph $\mathcal{G}$. This establishes the connection with the graph topology. However, we first need several intermediate results. We recall that $B$ and $R$ are defined by

where $S$ is a row stochastic matrix defined in (4), and the blocks of $R$ have the form $R_{a}=\left(\begin{smallmatrix}0&1\\ 1&0\end{smallmatrix}\right)$. Also, $S^{\top}S=\mathcal{D}$ is the degree matrix of $\mathcal{G}$. Moreover, $B^{2}=B$ and $R^{2}=I$.

If $\omega$ is an eigenvalue of the transition matrix $\mathcal{W}$, then $\omega$ is also an eigenvalue of the operator $BR$. Conversely, if $\omega\neq 0$ is an eigenvalue of $BR$, then $\omega$ is also an eigenvalue of $\mathcal{W}$.

The matrix $S$ defined in (4) has independent columns, therefore its left pseudo-inverse is $S^{+}=(S^{\top}S)^{-1}S^{\top}=\mathcal{D}^{-1}S^{\top}$, where $\mathcal{D}$ is the degree matrix of $\mathcal{G}$. Note that $B=SS^{+}$, and also that the adjacency matrix of $\mathcal{G}$ is given by $\mathcal{A}=S^{\top}RS$. Hence $\mathcal{W}\equiv\mathcal{D}^{-1}\mathcal{A}=S^{+}RS$, and we obtain the identity

Consider the eigenvalue equation $\mathcal{W}\bm{\omega}=\omega\,\bm{\omega}$, where $\bm{\omega}\neq\bm{0}$. Acting with (36) on $\bm{\omega}$ we have $BR(S\bm{\omega})=S\mathcal{W}\bm{\omega}=\omega(S\bm{\omega})$. Since the columns of $S$ are independent we have that $S\bm{\omega}\neq\bm{0}$, therefore $\omega$ is also an eigenvalue of $BR$.

Consider the eigenvalue equation $\bm{v}^{\top}(BR)=b\,\bm{v}^{\top}$, where $b\neq 0$ and $\bm{v}\neq\bm{0}$. Since $R=R^{-1}$ is invertible, $\bm{v}^{\top}B=b\,\bm{v}^{\top}R\neq\bm{0}$. Now $B$ is a projection onto the columns of $S$, thus we also have $\bm{v}^{\top}S\neq\bm{0}^{\top}$. Multiplying (36) by $\bm{v}^{\top}$ on the left we conclude that $\bm{v}^{\top}BRS=b(\bm{v}^{\top}S)=(\bm{v}^{\top}S)\mathcal{W}$, and $b$ is also an eigenvalue of $\mathcal{W}$. ∎

We have that $\omega\notin\{-1,0,1\}$ is an eigenvalue of $BR$ if and only if it is an eigenvalue of $\Omega_{S}$.

We claim, and later prove, the following two facts:

$\omega\neq 0$ is an eigenvalue of $BRB$ if and only if it is an eigenvalue of $BR$.

$\omega\notin\{-1,0,1\}$ is an eigenvalue of $BRB$ if and only if it is an eigenvalue of $-B^{\perp}RB^{\perp}$.

We first prove that if $\omega$ is an eigenvalue of $\Omega_{S}$, then $\omega$ is also an eigenvalue of $BR$. From (32), and recalling that $\widetilde{B}=2B-I$ and $B+B^{\perp}=I$, we can write

where $B$ and $B^{\perp}$ are projectors onto orthogonal subspaces. From (37) and using the identity $\bm{v}=B\bm{v}+B^{\perp}\bm{v}$, the eigenvalue equation $\Omega_{S}\bm{v}=\omega\bm{v}$ (where $\bm{v}\neq{\bf 0}$) is equivalent to

Since $\bm{v}\neq 0$, either $B\bm{v}\neq{\bf 0}$ or $B^{\perp}\bm{v}\neq{\bf 0}$ (or both). Thus, if $\omega$ is an eigenvalue of $\Omega_{S}$, then $\omega$ is an eigenvalue of $BRB$ or an eigenvalue of $-B^{\perp}RB^{\perp}$ (or both). Assuming $\omega\notin\{-1,0,1\}$, by the fact 2 above the operators $BRB$ and $-B^{\perp}RB^{\perp}$ have the same eigenvalues. Therefore, if $\omega$ is an eigenvalue of $\Omega_{S}$, then it is also an eigenvalue of $BRB$, and by fact 1 it is also an eigenvalue of $BR$.

Now we prove the reverse. If $\omega^{\prime}\neq 0$ is an eigenvalue of $BR$, then by fact 1 it is also an eigenvalue of $BRB$, i.e. $BRB\bm{v}^{\prime}=\omega^{\prime}\bm{v}^{\prime}$ for some $\bm{v}^{\prime}\neq{\bf 0}$. Acting on this equality with $B$ on both sides we conclude that $B\bm{v}^{\prime}=\bm{v}^{\prime}$. Hence, using (37) and $B^{\perp}\bm{v}^{\prime}={\bf 0}$ we obtain $\Omega_{S}\bm{v}^{\prime}=BRB\bm{v}^{\prime}=\omega^{\prime}\bm{v}^{\prime}$, i.e. $\omega^{\prime}$ is an eigenvalue of $\Omega_{S}$.

The above two paragraphs proves the claim, now we finally finally show that the above two facts hold.

Let $\omega\neq 0$ be such that $BRB\bm{v}=\omega\bm{v}$ for some $\bm{v}\neq 0$. Dividing this expression by $\omega$ we conclude that $\bm{v}$ is in the range of $B$. Since $B$ is an orthogonal projection, $B\bm{v}=\bm{v}$. The same argument holds if $\omega\neq 0$ is an eigenvalue of $BR$. Therefore, $BRB\bm{v}=BR\bm{v}=\omega\bm{v}$, as claimed.

Proof of Fact 2.

We first argue that if $\omega\notin\{-1,0,1\}$ is an eigenvalue of $BRB$, then $\omega$ is an eigenvalue of $B^{\perp}RB^{\perp}$. The argument for the other direction is the same with $B$ and $B^{\perp}$ switched. Let $BRB\bm{v}=\omega\bm{v}$ for some $\bm{v}\neq{\bf 0}$. Since $\omega\neq 0$, we have that $B\bm{v}=\bm{v}$. Let $\bm{u}\equiv B^{\perp}R\bm{v}$. We show that $\bm{u}$ is an eigenvector of $-B^{\perp}RB^{\perp}$ with eigenvalue $\omega$. We have $B^{\perp}RB^{\perp}\bm{u}=B^{\perp}RB^{\perp}R\bm{v}=B^{\perp}R(I-B)R\bm{v}=B^{\perp}\bm{v}-B^{\perp}RBR\bm{v}=-B^{\perp}RBR\bm{v}=-B^{\perp}RBRB\bm{v}=-\omega(B^{\perp}R\bm{v})=-\omega\bm{u}$. In addition, $\bm{u}=B^{\perp}R\bm{v}=R\bm{v}-BR\bm{v}=R\bm{v}-BRB\bm{v}=(R-\omega I)\bm{v}$. The eigenvalues of $R$ are $\pm 1$, thus $(R-\omega I)$ is non singular and it follows that $\bm{u}\neq 0$. ∎

The transition matrix $\mathcal{W}$ is singular if and only if the operator $\Omega_{S}$ is singular.

From the proof of Lemma 13 we know that $\mathcal{W}=S^{+}RS$. Suppose $\mathcal{W}$ is singular, i.e. there is $\bm{u}\neq\bm{0}$ such that $\mathcal{W}\bm{u}=S^{+}RS\bm{u}=\bm{0}$. Since the columns of $S$ are independent and $R$ is invertible, $\bm{v}\equiv RS\bm{u}\neq\bm{0}$, and therefore $S^{+}\bm{v}=\bm{0}$. Using (32) we can write $\Omega_{S}=BR-R+RB$, and noticing that $R^{2}=I$ and $BS=SS^{+}S=S$, we obtain $\Omega_{S}\bm{v}=RB\bm{v}=RS(S^{+}\bm{v})=\bm{0}$, implying that $\Omega_{S}$ is also singular.

Suppose $\Omega_{S}$ is singular, i.e. there is $\bm{v}\neq\bm{0}$ such that $\Omega_{S}\bm{v}=\bm{0}$. From (37) and noticing that $B$ and $B^{\perp}$ project onto orthogonal subspaces we have

Consider two separate cases. First, if $B\bm{v}=\bm{0}$ then $B^{\perp}\bm{v}=\bm{v}\neq\bm{0}$, and from equation (39) we have $B^{\perp}RB^{\perp}\bm{v}=B^{\perp}R\bm{v}=R\bm{v}-BR\bm{v}=\bm{0}$, or $R\bm{v}=S\bm{u}$ where $\bm{u}=S^{+}R\bm{v}\neq\bm{0}$. Therefore, $\mathcal{W}\bm{u}=S^{+}RS\bm{u}=S^{+}\bm{v}=\bm{0}$ showing that $\mathcal{W}$ is singular, where we have used $R^{2}=I$ and $B\bm{v}=\bm{0}$ if and only if $S^{+}\bm{v}=\bm{0}$. Second, suppose $B\bm{v}\neq\bm{0}$, and let $\bm{u}\equiv S^{+}\bm{v}\neq\bm{0}$. From the first equation in (39) we have $S\mathcal{W}\bm{u}=SS^{+}RSS^{+}\bm{v}=BRB\bm{v}=\bm{0}$, but since $S$ has independent columns we must have $\mathcal{W}\bm{u}=\bm{0}$, which shows that $\mathcal{W}$ is singular. ∎

We have that $\omega\in(-1,1]$ is an eigenvalue of the transition matrix $\mathcal{W}$ if and only if it is an eigenvalue of the symmetric operator $\Omega_{S}$.

Combining Lemma 13 and Lemma 14 it follows that $\omega\notin\{-1,0,1\}$ is an eigenvalue of $\mathcal{W}$ if and only if it is an eigenvalue of $\Omega_{S}$. By Lemma 15 we can extend this to $\omega=0$. Finally, $\mathcal{W}$ and $\Omega_{S}$ always have an eigenvalue $\omega=1$ with eigenvector being the all-ones vector. ∎

Finally, we are ready to show one of our main results, which relates the spectrum of ADMM to the spectrum of random walks on $\mathcal{G}$. We first repeat the statement of Theorem 3 in the main text for convenience.

Let $\mathcal{W}=\mathcal{D}^{-1}\mathcal{A}$ be the probability transition matrix of a random walk on the graph $\mathcal{G}$, where $\mathcal{D}$ is the degree matrix and $\mathcal{A}$ the adjacency matrix. For each eigenvalue $\lambda(\mathcal{W})\in(-1,1)$ the matrix $T_{A}$ in (12) has a pair of eigenvalues given by

Conversely, any eigenvalue $\lambda(T_{A})$ is of the form (40) for some $\lambda(\mathcal{W})$.

The first part is an immediate consequence of Corollary 12 and Lemma 16. The second part is a consequence of Lemma 9. ∎

Appendix C Proof of Theorem 5

To establish Theorem 5, which involves graphs with even length cycles and low conductance, several intermediate results will be needed.

The operator $U$, defined in (30), and also the symmetric operator $\Omega_{S}$ are diagonalizable. Moreover, $U$ and $\Omega_{S}$ commute and have a common eigenbasis.

It is obvious that $\Omega_{S}=\frac{\Omega+\Omega^{\top}}{2}$ is diagonalizable since it is symmetric and real. Let $U=PJP^{-1}$ be a decomposition in terms of a Jordan canonical form $J=\operatorname{diag}(J_{1},J_{2},\dotsc)$, where $J_{i}$ is the Jordan block associated to eigenvalue $\lambda_{i}$. From Lemma 10 we have $\Omega_{S}=\tfrac{1}{2}(U+\eta U^{-1})=\tfrac{1}{2}P(J+\eta J^{-1})P^{-1}$. For every Jordan block $J_{i}$ there is a corresponding Jordan block of the same dimension in $J+\eta J^{-1}$ with corresponding eigenvalue $\lambda_{i}+\eta\lambda_{i}^{-1}$. Therefore, we can decompose $J+\eta J^{-1}=FZF^{-1}$, where $Z$ is in Jordan form and has the same set of Jordan-block-dimensions as $J$, except that the diagonal values are different. To mention an example, consider

Thus, we can write $\Omega_{S}=\tfrac{1}{2}(HF)Z(HF)^{-1}$. The Jordan form of a matrix is unique, and $\Omega_{S}$ is diagonalizable, therefore, all blocks in $Z$ must have dimension $1$, and so does $J$, which means that $U$ is diagonalizable.

It is obvious that $U$ and $\Omega_{S}$ commute due to (32). Two diagonalizable matrices that commute can be simultaneous diagonalizable, thus they share a common eigenbasis. ∎

If $w_{S}\in\{-1,1\}$ is an eigenvalue of $\Omega_{S}$ with corresponding eigenvector $\bm{v}$, then

if $B\bm{v}\neq\bm{0}$, then $B\bm{v}$ is also an eigenvector of $\Omega_{S}$ and of $R$ with eigenvalue $w_{S}$, i.e. $\Omega_{S}(B\bm{v})=w_{S}(B\bm{v})$ and $R(B\bm{v})=w_{S}(B\bm{v})$.

if $B^{\perp}\bm{v}\neq\bm{0}$, then $B^{\perp}\bm{v}$ is also an eigenvector of $\Omega_{S}$ with eigenvalue $w_{S}$ and of $R$ with eigenvalue $-w_{S}$, i.e. $\Omega_{S}(B^{\perp}\bm{v})=w_{S}(B^{\perp}\bm{v})$ and $R(B^{\perp}\bm{v})=-w_{S}(B^{\perp}\bm{v})$.

Let $\Omega_{S}\bm{v}=w_{S}\bm{v}$ where $w_{S}\in\{-1,1\}$ and $\bm{v}\neq{\bf 0}$. From (37) we have

Assuming $B\bm{v}\neq\bm{0}$ we have $\Omega_{S}(B\bm{v})=BR(B\bm{v})=w_{S}(B\bm{v})$, which shows that $B\bm{v}$ is an eigenvector of $\Omega_{S}$ with eigenvalue $w_{S}$. Taking the norm on each side of this equation and using $|w_{S}|=1$ implies

Since $B$ is a projection operator, if $RB{\bm{v}}$ is not in the span of $B$ then we must have $\|B(RB{\bm{v}})\|<\|RB{\bm{v}}\|\leq\|B{\bm{v}}\|$, where the last inequality follows by using $\|R\|\leq 1$. However, this contradicts (42). Therefore, $RB\bm{v}$ must be in the span of $B$ and as a consequence $R(B{\bm{v}})=BRB{\bm{v}}=w_{S}(B{\bm{v}})$, where we used the first equation in (41). This shows that $B{\bm{v}}$ is an eigenvector of $R$ with eigenvalue $w_{S}$ and completes the proof of the first claim.

The proof of the second claim is analogous. Assuming $B^{\perp}\bm{v}\neq\bm{0}$ we obtain $\Omega_{S}(B^{\perp}\bm{v})=-B^{\perp}RB^{\perp}\bm{v}=w_{S}(B^{\perp}\bm{v})$, where in the last passage we used the second equation in (41). This shows that $B^{\perp}\bm{v}$ is an eigenvector of $\Omega_{S}$ with eigenvalue $w_{S}$. Taking the norm of this last equality yields

Assuming that $RB^{\perp}\bm{v}$ is not in the span of $B^{\perp}$ we conclude that $\|B^{\perp}RB^{\perp}\bm{v}\|<\|B^{\perp}\bm{v}\|$, which contradicts (43). Therefore, we must have $B^{\perp}RB^{\perp}\bm{v}=R(B^{\perp}\bm{v})=-w_{S}(B^{\perp}\bm{v})$, where we used (41). This shows that $B^{\perp}\bm{v}$ is an eigenvector of $R$ with eigenvalue $-w_{S}$. ∎

If $B\bm{v}\neq\bm{0}$ is an eigenvector of $R$ with eigenvalue $-1$, then the graph $\mathcal{G}$ does not have odd-length cycles. If $B^{\perp}\bm{v}\neq\bm{0}$ is an eigenvector of $R$ with eigenvalue $1$, then the graph $\mathcal{G}$ has cycles.

Let us consider the first statement. From the eigenvalues and eigenvectors of $R$, for every pair of edges $e_{i},e_{j}\in\bar{\mathcal{E}}$ incident on a given function node $a\in\bar{\mathcal{F}}$ we have

for some constant $c_{a}$. Now $B\bm{x}=\bm{x}\neq{\bf 0}$, thus for every set of edges $\{e_{1},e_{2},\dotsc,e_{k}\}$ incident on a variable node $b\in\bar{\mathcal{V}}$ we have

where $c_{b}$ is a constant. Since the graph $\mathcal{G}$, and consequently its corresponding factor graph $\bar{\mathcal{G}}$, is connected, we must have

Now assume that $\mathcal{G}$ has an odd cycle. This cycle must traverses an odd number of variable nodes $a\in\bar{\mathcal{F}}$, but each pair of edges incident on $a\in\bar{\mathcal{F}}$ must have the same absolute value and opposite signs due to (44), while each pair of edges incident on a variable node $b\in\bar{\mathcal{V}}$ must have equal signs due to (45). This implies that $c_{a}=c_{b}$ and $c_{a}=-c_{b}$ for some $(a,b)\in\bar{\mathcal{E}}$, whose solution is $c_{a}=c_{b}=0$. From (45) this implies that for all $e_{i}\sim b$ we have $x_{e_{i}}=0$, which in turn by (46) implies that $c_{a}=0$ for all $a$ incident upon these edges $e_{i}$, $i=1,\dotsc,k$, and so forth. This yields $\bm{x}=\bm{0}$, which contradicts our assumption. Therefore, $\mathcal{G}$ cannot have odd-length cycles. See Fig. 4a for an example.