Expander Graph and Communication-Efficient Decentralized Optimization
\IEEEauthorblockN{Yat-Tin Chow$^1$
Wei Shi$^2$
Tianyu Wu$^1$ and Wotao Yin$^1$
In this paper, we discuss how to design the graph topology to reduce the communication complexity of certain algorithms for decentralized optimization. Our goal is to minimize the total communication needed to achieve a prescribed accuracy. We discover that the so-called expander graphs are near-optimal choices. We propose three approaches to construct expander graphs for different numbers of nodes and node degrees. Our numerical results show that the performance of decentralized optimization is significantly better on expander graphs than other regular graphs. %the graphs that are recommended for consensus averaging in the existing literature. In others, the best graphs for consensus averaging are no longer the best choices for general decentralized optimization. %\footnote{Is this last comment "over using the graphs that are recommended for consensus averaging" true? We only compared with regular graphs.
comm_efficient_decentralized_optimization.tex
%


\documentclass[tran,10pt]{IEEEtran}

\input{macros}

% generating a thicker \hline in tables --> command is \hlinewd{2pt}
\makeatletter
\def\hlinewd#1{%
  \noalign{\ifnum0=`}\fi\hrule \@height #1 \futurelet
   \reserved@a\@xhline}

\usepackage{color,hyperref}
\definecolor{darkblue}{rgb}{0.0,0.0,0.4}
\hypersetup{colorlinks,breaklinks,
        linkcolor=darkblue,urlcolor=darkblue,
        anchorcolor=darkblue,citecolor=darkblue}

\makeatother
%%-----------------------------macros definition-------------------------%%
\title{Expander Graph and Communication-Efficient Decentralized Optimization}

\author{\IEEEauthorblockN{Yat-Tin Chow$^1$, Wei Shi$^2$, Tianyu Wu$^1$ and Wotao Yin$^1$\\}
        \vspace{0.4cm}
        \IEEEauthorblockA{$^1$Department of Mathematics, University of California, Los Angeles, CA\\
                $^2$ Department of Electrical \& Computer Engineering, Boston University, Boston, MA
%Coordinated Science Laboratory, University of Illinois, Urbana-Champaign, Campaign, IL
}

\thanks{This work was supported in part by NSF grant ECCS-1462398.  Emails: \{ytchow,wuty11,wotaoyin\}@math.ucla.edu and wilburs@bu.edu}
        }
\renewcommand{\footnoterule}{%
        \kern -1pt
        \hrule width 1.1in height 1.2pt
        \kern 2pt
}

\IEEEoverridecommandlockouts
\begin{document}

\def\helvetica{phvr7t.tfm}
\def\helveticaoblique{phvro7t.tfm}
\def\helveticabold{phvb7t.tfm}
\def\helveticaboldoblique{phvbo7t.tfm}

\def\textcolor{ \footnote}

\def\rev{ }

\font\sfb=\helveticabold
\font\sfbit=\helveticaboldoblique
\maketitle


\begin{abstract}
In this paper, we discuss how to design the graph topology to reduce the  communication complexity of certain algorithms for decentralized optimization. Our goal is to minimize the total communication needed to achieve a prescribed accuracy. We discover that the so-called \emph{expander graphs} are near-optimal choices. 

We propose three approaches to construct expander graphs for different numbers of nodes and node degrees. Our numerical results show that the performance of decentralized optimization is significantly better on expander graphs than  other regular graphs.
%the graphs that are recommended for consensus averaging in the existing literature. In others, the best graphs for consensus averaging are no longer the best choices for general decentralized optimization.

%\footnote{Is this last comment "over using the graphs that are recommended for consensus averaging" true? We only compared with regular graphs.}
\end{abstract}
\begin{IEEEkeywords}
decentralized optimization, expander graphs, Ramanujan graphs, communication efficiency.
\end{IEEEkeywords}


\section{Introduction}
\subsection{Problem and background}
%In this work we attempt achieve nearly optimal communication efficiency for decentralized consensus optimization by choosing the appropriate graph topologies.
Consider the decentralized consensus problem:
\begin{equation}
\Min_{x \in \mathbb{R}^P } f(x) = \frac{1}{M}
 \sum_{i= 1}^M  f_{i}(x)  \,,
\label{important}
\end{equation}
which is defined on a connected network of $M$ agents who cooperatively solve the problem for a common minimizer $x \in \mathbb{R}^P$. Each agent $i$ keeps its private convex function $f_i :  \mathbb{R}^P \rightarrow  \mathbb{R}$.
%To study network design, 
We consider synchronized optimization methods, where all the agents carry out their iterations at the same set of times.

Decentralized algorithms are applied to solve problem \eqref{important} when the data are collected or stored in a distributed network and a fusion center is either infeasible or uneconomical. %so we need multiple agents to collaboratively compute the solution. They 
Therefore, the agents in the network must perform local computing and communicate with one another. Applications of decentralized computing are widely found in sensor network information processing, multiple-agent control,  coordination, distributed machine learning, among others. Some important works include decentralized averaging \cite{EXTRA7, EXTRA15, EXTRA34}, learning \cite{EXTRA9, EXTRA22, EXTRA26}, estimation \cite{EXTRA1, EXTRA2, EXTRA16, EXTRA18}, sparse optimization \cite{EXTRA19, EXTRA35}, and low-rank matrix completion \cite{EXTRA20} problems.

In this paper, we focus on the communication efficiency of certain decentralized algorithms.  Communication is often the  bottleneck of distributed algorithms since it can cost more time or energy than computation, so reducing communication  is a primary concern in distributed computing. % to save resources such as time and energy in decentralized computing.  


Often, there is a trade-off between \emph{communication requirement} and \emph{convergence rates} of a decentralized algorithm. Directly connecting more pairs of agents, for example, generates more communication at each iteration but also tends to make faster progress toward the solution. 
% there is always a trade-off between communication complexity in each iteration and the total number of iterations necessary for a good approximation of the minimizer. 
To reduce the \emph{total} communication for reaching a solution accuracy, therefore, we must find the balance. In this work, we argue that this balance is approximately reached by the so-called Ramanujan graphs, which is a type of expander graph.


\subsection{Problem reformulation}


We first reformulate problem \eqref{important} to include the graph topological information.  Consider an undirected graph $G = (V,E)$ that represents the network topology, where $V$ is the set of vertices and $E$ is the set of edges. Take a symmetric and doubly-stochastic \emph{mixing matrix} $W = \{ W_{e} \}_{e \in E}$, i.e. $ 0 \leq W_{ij} \leq 1$, $\sum_i W_{ij} = 1$ and $W^T = W$.  The matrix $W$ encodes the graph topology since $W_{ij} = 0$ means no  edge between the $i$th and the $j$th agents. 
Following \cite{shi2015extra}, the optimization problem \eqref{important} can be rewritten as:
\begin{equation}
\Min_{\textbf{x} \in \mathbb{R}^{M\times P} } \frac{1}{M} \sum_{i= 1}^M   F_{i}( \textbf{x} )~  \text{ subject to } W \textbf{x} = \textbf{x}  \,,
\label{min3}
\end{equation}
where $\vx=[x_1,...,x_M]^\top$ and the functions $F_{i}$ are defined as $ F_{i}( \textbf{x} ) := f_i(x_i) $.
\subsection{Overview of our approach}\label{sc:overview}
%We mention  several concepts, whose  formal definitions are delayed to the next section to avoid distractions.

Our goal is to design a network of $N$ nodes and a mixing matrix $W$ such that state-of-the-art consensus optimization algorithms that apply multiplication of $W$ in the network, such as EXTRA \cite{shi2015extra,shi2015proximal} and ADMM \cite{ghadimi2014admm,shi2014linear,mota2013d}, can solve problem \eqref{important} with a nearly minimal amount of total communication. Our target accuracy is  $\|z^k-z^*\|<\varepsilon$, where $k$ is the iteration index, $\varepsilon$ is a threshold, and $(z^k)_k$ is the sequence of iterates, and  $z^*$ is its limit. We use $z^k,z^*$ instead of $x^k,x^*$ since EXTRA and ADMM iterate both primal and dual variables. \textbf{Let $U$ be the amount of \emph{communication per iteration}, and $K$ be the number of iterations needed to reach the specified accuracy.} The \emph{total communication} is their product $(UK)$. Apparently, $U$ and $K$ both depend on the network. A dense network usually implies a large $U$ and a small $K$. On the contrary, a highly sparse network typically leads to a small $U$ and a large $K$. (There are special cases such as the \emph{star} network.) The optimal density is typically neither  of them. Hence we shall find the optimal balance. To achieve this, we express $U$ and $K$ in the network parameters that we can tune, along with other parameters of the problem and the algorithm that affect total communication but we do not tune. Then, by finding the optimal values of the tuning parameters, we obtain the optimal network.

The dependence of $U$ and $K$ on the network can be complicated. Therefore, we make a series of simplifications to the problem and the network so that it becomes sufficiently simple to find the minimizer to $(UK)$. We mainly (but are not bound to) consider strongly convex objective functions and decentralized algorithms using fixed step sizes (e.g., EXTRA and ADMM) because they have the linear convergence rate:  $\|z^k-z^*\|\le C^k$ for $C<1$. Given a target accuracy $\varepsilon$, from $C^K=\varepsilon$, we deduce  the sufficient number of iterations $K=\log(\varepsilon^{-1})/\log(C^{-1})$. Since the constant  $C<1$ depends on network parameters, so does $K$. 

We mainly work with three network parameters: the condition number of the graph Laplacian, the first non-trivial eigenvalue of the incidence matrix, and the degree of each node. In this work, we restrict ourselves to the $d$-regular graph, e.g., every node is connected to exactly $d$ other nodes.

We  further (but are not bound to) simplify the problem by assuming that all edges have the same cost of communication. Since most  algorithms perform a fixed number (typically, one or two) of rounds of communication in each iteration along each edge,   $U$ equals a constant times $d$.

So far, we have simplified our problem to minimizing $(Kd)$, which reduces to  choosing $d$, deciding the topology of the $d$-regular graph, as well setting the mixing matrix  $W$. %that the decentralized algorithms will use for passing information over the edges.

For the two algorithms EXTRA\ and ADMM, we deduce (in Section \ref{sc:commcost} from their existing analysis) that $K$ is determined by the mixing matrix $W$ and $\tilde{\kappa}(L_G)$, where $L_G$ denotes the graph Laplacian and $\tilde{\kappa}(L_G)$ is its reduced condition number. %d as in \eqref{cond} below. 
We simplify the formula of $K$ by relating $W$ to $L_G$ (thus eliminating $W$ from the computation).  %by formula \eqref{WW}, which will be discussed in the next section. 
%(A smaller $\tilde{\kappa}(L_G)$ leads to faster convergence for both ADMM\ and EXTRA.) 
Hence, our problem becomes minimizing $(Kd)$, where $K$ only depends on $\tilde{\kappa}(L_G)$ and   $\tilde{\kappa}(L_G)$ further depends on the degree $d$ (same for every node) and the topology of the $d$-regular graph. 

By classical graph theories, a $d$-regular graph satisfies $\tilde{\kappa}(L_G) \le \frac{d+\lambda_1(A)}{d-\lambda_1(A)} $, where $\lambda_1(A)$ is the first non-trivial eigenvalue of the incidence matrix $A$, which we define later. We  minimize $\lambda_1(A)$  to reduce $\frac{d+\lambda_1(A)}{d-\lambda_1(A)}$ and thus $\tilde{\kappa}(L_G)$. Interestingly, $\lambda_1(A)$  is lower bounded by the Alon Boppana formula of $d$ (thus also depends on $d$). The lower bound is nearly attained by Ramanujan graphs, a type of graph with a small number of edges but having high connectivity and good spectral properties! Therefore, given a degree $d$, we shall choose Ramanujan graphs, because they approximately  minimize $\lambda_1(A)$, thus $\tilde{\kappa}(L_G)$, and in turn $(Kd)$ and $(KU)$. 

Unfortunately, Ramanujan graphs are  not known for all values of $(N,d)$. For large $N$, we follow \cite{friedman2008proof} to construct a random network, which has nearly minimal $\lambda_1(A)$.  For small $N$, we apply the Ramanujan Sparsifier \cite{batson2012twice}.
These approaches lead to near-optimal network topologies for a given $d$.

After the above deductions, minimizing the total communication simplifies to choosing the degree $d$. To do this, one must know the cost ratio between computation and communication, which depends on applications. Once these parameters are known, a simple one-dimensional search method will find $d$.

\subsection{Communication reduction}  \label{sec:reduction}

We find that, in different problems, the graph topology affects total communication to different extents. When one function $f_i(x)$ has a big influence to the consensus solution, 
% e.g., $f_i(x)=|x-b_i|$, $i=1,\ldots,N$, with a very large $b_1$, 
 total communication is sensitive to the graph topology. On the other hand, computing the consensus average of a set of similar numbers is insensitive to the graph topology, so  a Ramanujan graph does not make much improvement. Therefore, our proposed graphs work only for the former type of problem and data.  
%effective communication are the most important candidates for our investigation.    In particular, problems that are the most sensitive to one missing functional $f_i(x)$ (usually carring the respective data stored in the $i$-th node), such as optimization problem equivalent to finding maximum entry of the array $\{l_i\}$ (i.e. finding the sup-norm of a vector $l$) where each $l_i$ is stored in one node, will benefit the most from our method to reduce communications.  On the other hand, the ones which benefits the least are thoese which are the least sensitive to the change of one functional ( e.g. those equivalent ot finding an average between data in the nodes/finding the 1-norm of a vector $l$.)
See section \ref{sec:num} for more details and comparison.
%On the other hand, communication-optimizable (c.f. Definition \ref{def:1}) decentralized concensus optimimzation algorithms, such as EXTRA and decentralized ADMM, can benefit the most from our communication reduction method.
\subsection{Limitations and possible resolutions} \label{sec:limitations}
%Our main approach is first derived based on
We assume nodes having the same degree,  edges having the same communication cost, and a special mixing matrix $W$. %We also assumed that each edge has the same communication cost.%let the amount of communication per iteration $U$ be a function of the (average) degree (which is equivalent to saying all edge produces similar cost.)
Despite these assumptions, the Ramanujan graph may still serve as the starting point to  reduce the total communication in more general settings, which is our future work.  
% In fact this assumption is unnecessary if we apply \textbf{Algorithm I} (which will be introduced in section \ref{sec:sparsifier}) to obtain a sparsifier $H$ of a given graph $G$, with $H$ having almost identical spectral property as $G$ (guaranteed to exist by Theorem \ref{imp_sparse}).  With this method, we do NOT need to assume the graph is having a same degree (because only average degree is considered), and we can even handle the cases when some cables are prohibited by the users (by initialize $G$ \textbf{Algorithm I} in some special way that is remarked in section \ref{sec:sparsifier}).  Moreover, the algorithm takes care (in a greedy faction) of the situation when different edges correspond to different cost.  In particular, Step 4.2 in \textbf{Algorithm I} is designed to minimize communication cost in each step by greedily choosing the least costly route when we sparsify the graph (which is different from the original sparsifying algorithm given in \cite{}).  Therefore our solution can be very general, and  \textbf{Algorithm I} can have potential to adapt to different cases to obtain (almost) optimal graphs for effective communication.  This will be subjected to future research.


\subsection{Related work}

Other work that has considered and constructed Ramanujan graphs include \cite{kim2006maximizing,ghosh2006growing}.  %Work that uses Ramanujan graphs for optimization includes \cite{}.
Graph design for optimal convergence rate under decentralized consensus averaging and optimzation is considered in \cite{EXTRA34,xiao2004fast,zhao2012diffusion,boyd2004fastest,yuan2013convergence,tsitsiklis1984problems,chen2012fast}.
%One point to remark is that %in our work, we notice expander graphs serves as a best candidate for optimal communication for communication demanding optimization problems. 
\rev{However, we suspect the mixing matrices $W$ recommended in the above for average consensus might sometimes not be %are often unnecessarily 
the best choices for decentralized optimization, since consensus averaging is a lot less communication demanding than decentralized optimization problems (c.f. Section \ref{sec:reduction}), and it is the least sensitive to adding, removing, or changing one node.
%especially when consensus averaging problem is perhaps among the 
%\emph{least} communication demanding problems: the least sensitive to adding, removing, or changing one node  (See section \ref{sec:reduction}).
On the other hand, we agree for consensus averaging, those matrices recommended serve as the best candidates.} %, especially because it is not benefiting by communication optimisation due to the nature of the problem.)





\section{Communication cost in decentralized optimization}\label{sc:commcost}

As described in Subsection \ref{sc:overview}, we focus on a special class of decentralized algorithm that allows us to optimize its communication cost by designing a suitable graph topology.

For the notational sake, let us recall several definitions and properties of a graph. See \cite{murty2003ramanujan,newman2000laplacian,chung1997spectral} for background. Given a graph $G$, the adjacency matrix $A$ of $G$ is a $|V| \times |V|$ matrix with components
\begin{equation*}
A_{ij} = \begin{cases}  1 \quad \text{ if } (i,j)\in E \,,  \\ 0 \quad \text{ if otherwise.} \end{cases}
\end{equation*}
An equally important (oriented) incidence matrix is defined as is a $|E| \times |V| $ matrix such that
\begin{equation*}
B_{e i} = \begin{cases}  1 \quad &\text{ if } e = (i,j) \text{ for some }j, \text{ where } j>i\,,  \\ -1 \quad &\text{ if } e = (i,j) \text{ for some }j,  \text{ where } j<i\,,  \\  0 \quad &\text{ otherwise.} \end{cases}
\end{equation*}
The degree of a node $i \in E$, denoted as $\deg(i)$, is the number of edges incident to the node.
Every node in a $d$-regular graph has the same degree $d$.
The graph Laplacian of $G$ is:
\begin{equation*}
L_G := D - A = B^T B \,,
\end{equation*}
where $D$ has diagonal entries $D_{ii} = \deg(i)$ and 0 elsewhere. 
The matrix $L_G$ is symmetric and positive semidefinite. The multiplicity of its trivial eigenvalue $0$ is the number of connected components of $G$.  Therefore, we consider its first \emph{nonzero} eigenvalue, denoted as $\widetilde{ \lambda_{\text{min}}} (L_G)$ and its largest eigenvalue, denoted as $\lambda_{\text{max}}(L_G)$.
The reduced condition number of  $L_G$ is defined as:
\begin{equation}
\tilde{\kappa}(L_G) := \lambda_{\text{max}}(L_G) / \widetilde{ \lambda_{\text{min}}} (L_G) \,,
\label{cond}
\end{equation} 
which is of crucial importance to our  exposition.
We  need a weighted graph and its graph Laplacian.  A weighted graph $G = (V,E,w)$ is a graph with nonnegative edge weights $w = (w_e)$.  Its graph Laplacian is defined as
\begin{equation*}
L_{G,w} := B^T \Diag(w) B \,.
\end{equation*}
Its  eigenvalues and condition numbers are similarly defined, e.g., $\tilde{\kappa}(L_{G,w})$ being its reduced condition number.

Next we define a special class of decentralized algorithm, which simplifies the computation of total communication cost.

\begin{definition}
\label{def:1}
We call a first-order decentralized algorithm to solve \eqref{min3} communication-optimizable if any sequence $\{ \textbf{z}^{k} \}$ generated by the algorithm satisfies
\begin{equation}
\label{R}
\|\textbf{z}^{k} - \textbf{z}^* \| \leq R( \Theta, \Gamma_f, \tilde{\kappa}(L_{G,w}), k  ) \,,
\end{equation}
for a certain norm $ \| \cdot \|$ and function $R$, where  $\Theta$ consists of all algorithmic parameters specified by the user, $\Gamma_f$ is a constant depending on the objective function $f$.
%$d$ is the average degree of the graph $G$.
 In addition, $R$ is non-increasing as $\tilde{\kappa}(L_{G,w}) $ decreases or $k$ increases.
\end{definition}

The above definition means that there exists a convergence-speed bound that depends on only $L_{G,w}$ and $k$ while other parameters $\Theta, \mu_f$ are fixed.
This description of convergence rate is met by many algorithms mainly because $\tilde{\kappa}(L_{G,w})$ reflects the connectivity of graph topology.
In fact, if $G$ is $d$-regular and weighted, then we have from \cite{newman2000laplacian,chung1997spectral}:
\begin{equation*}
 \tilde{\kappa}(L_G)  \leq \frac{d + \lambda_1 (A) }{ d - \lambda_1 (A) },
\end{equation*}
where $\lambda_1 (A) \neq d $ is the first non-trivial eigenvalue of the adjacency matrix $A$ (as the eigenvalue $\lambda_0 (A)=d$ is trivial and corresponds to the eigenvalue $0$ of $L_G$) and is  related to the connectivity of $G$ by the Cheeger inequalities  \cite{alon2004probabilistic}:
\begin{equation*}
\tfrac{1}{2} ( d - \lambda_1 (A) ) \leq h(G) \leq \sqrt{ 2 d (d - \lambda_1 (A) )}
\label{eqneqneqn}
\end{equation*}
where $h(G)$ is the Cheeger constant quantifying the connectivity of $G$.  Therefore saying that $R( \Theta, \mu_f, \tilde{\kappa}(L_{G,w}), k  ) $ is nondecreasing with $\tilde{\kappa}(L_{G,w})$ is related to saying that is nonincreasing with the connectivity of $G$. (Higher connectivity lets the algorithm converge faster.) Hence, we  hope to increase the number of edges $E$ of $G$ though a cost is associated. %often an associated cost to link a pair of nodes.


With the help of  $L_{G,w}$, for simplicity we might choose the mixing matrix $W$ to take the form \cite{xiao2004fast,zhao2012diffusion}:
\begin{equation}
W_{L_{G,w}} := I - \frac{2}{ (1+ \Theta_1) \lambda_{\text{max}}(L) } L_{G,w} \, ,  \text{ for  }0 < \Theta_1 <1 \,,
\label{WW}
\end{equation}
where $\Theta_1$ is among the set of algorithmic parameters $\Theta$ mentioned above.  This choice of $W$ is symmetric and doubly stochastic. 
Other  choices are given in \cite{boyd2004fastest,yuan2013convergence,tsitsiklis1984problems,chen2012fast,EXTRA34}.
Under our choice of $W$, there are many examples of communication-optimizable algorithms, where the convergence rate depends only on $\tilde{\kappa}(L_{G,w})$.    The convergence rate of EXTRA \cite{shi2015extra,shi2015proximal}  can be explicitly represented, after some straight-forward simplifications by letting $W = W_{L_{G,w}}$ \eqref{WW}:
\begin{equation*}
\frac{ \|\textbf{z}^{k} - \textbf{z}^* \| }{\|\textbf{z}^{0} - \textbf{z}^* \|} \leq \Big( 1+ \min \big \{ \tfrac{1}{p \,\tilde{\kappa}(L_{G,w}) + q }   , \tfrac{1}{r \tilde{\kappa}(L_{G,w})} \big\}  \Big)^{-\tfrac{k}{2}}\,,
\end{equation*}
for some norm $\| \cdot \|$ (where $\textbf{z}$ is related to $\textbf{x}$), and decentralized ADMM \cite{ghadimi2014admm,shi2014linear,mota2013d}:
\begin{equation*}
\frac{ \|\textbf{z}^{k} - \textbf{z}^* \| }{\|\textbf{z}^{0} - \textbf{z}^* \|} \leq \Big( 1+ \sqrt{ p \, \tilde{\kappa}(L_{G,w})^{-2}   + q } - \sqrt{q} \Big)^{-\tfrac{k}{2} }\,,
\end{equation*}
where $p,q,r$ are some coefficients depending only on $\Theta, \mu_f$.
Apparently, while fixing other parameters, a smaller $\tilde{\kappa} (L_{G,w})$ tends to give faster convergence.   We  see the same in extension of EXTRA, PG-EXTRA \cite{shi2015proximal}, for nonsmooth functions.

In order to consider the communication cost for an optimization
procedure, we need the following two quantities.  The first one is the amount of communication per
iteration $U$: % as the following quantity
\begin{equation}
 U (\mu, W) :=\textstyle  \sum_{e \in E } \mu_{e} |W_{e}|_0 ,
\end{equation}
where $\mu = (\mu_{e})$ the communication cost on each edge $e$ and $|\cdot |_0$ as the 1/0 function that indicates if $e$ is used for communication or not.
When $W$ is related to $L_{G,w}$ via \eqref{WW}, we also write $ U
(\mu, L_{G,w} ) := U (\mu, W_{L_{G,w}} )  $ to represent this quantity.  %Now we are ready to discuss the total communication cost for an optimization procedure.
Next, we introduce the second quantity, the total communication cost for an optimization procedure.  
For this purpose, let us recall that $\Gamma_f$ represents a set of constants depending only on the structure of the target function $f$, and $\Theta$ be a set of parameters not depending on either $f$ of the graph $G$. 
We let $K$ be the number of iterations to achieve the accuracy $\|\textbf{z}^{k} - \textbf{z}^* \|\le \epsilon$,
\begin{equation*}
K=K(\Theta, \Gamma_f,  \tilde{\kappa}(L_{G,w}) , \epsilon),
\end{equation*}
as $K$ clearly depends on $\Gamma_f$ , $\Theta$, $\tilde{\kappa}(L_{G,w}) $, and $\epsilon$. By the definition of $R$ in \eqref{R}, we have
\begin{equation*}
R\big( \Theta, \Gamma_f, \tilde{\kappa}(L_{G,w}), K ( \Theta, \Gamma_f,   \tilde{\kappa}(L_{G,w}) , \epsilon )   \big) = \epsilon \,. 
\end{equation*}
%Once it is defined and its dependence is clarified, we can use $U$ and $K$ instead of $ U(\mu, L_{G,w} )$ and $K(\Theta, \Gamma_f,  \tilde{\kappa}(L_{G,w}) , \epsilon)$. 
\begin{theorem}
The total communication cost for $ ( \textbf{z}^{i} )_{i=0}^{k}$ generated by a communication-optimizable algorithm to satisfy $\|\textbf{z}^{k} - \textbf{z}^* \| \leq \varepsilon $, denoted as $J( \Theta, \Gamma_f, W_{L_{G,w}} , \epsilon )$, satisfies:
\begin{equation}
J( \Theta, \Gamma_f, W_{L_{G,w}} , \epsilon ) \leq
K \big( \Theta, \Gamma_f,   \tilde{\kappa}(L_{G,w}\big) , \epsilon) \cdot
 U\big (\mu, L_{G,w} \big)  \,.
\label{realcost}
\end{equation}
\end{theorem}
The cost consists of two parts, the first part $K$ decreasing with the connectivity of $G$ while the other part $U$ growing with it.

In general, how to optimize $J$ depends on each algorithm (which gives the function $K$) and the weights $\{ \mu_{e}\}$.
Given an additional assumption that $\{\mu_{e}\}$ are uniformly, we can assume
\begin{equation}
 U(\mu, L_{G,w}) \approx F(d^{\text{ave}}) \,,
\end{equation}
where $d^{\text{ave}} = \sum_i \deg(i) / \sum_i 1$ is the average degree, and $F$ a function that increases monotonically w.r.t. $d^{\text{ave}}$.
Therefore, a reasonable approximation of the communication efficiency optimization problem becomes
\begin{equation}
\min_{G} J( \Theta, \Gamma_f, W_{L_{G,w}} , \epsilon ) \\ \approx \min_{d^{\text{ave}}}\left\{    H (d^{\text{ave}})  F (d^{\text{ave}}) \right\}
\label{happy}
\end{equation}
where $H(d^{\text{ave}})$ reads
\begin{equation}
H(d^{\text{ave}}) :=
 \min_{ ( G_{d^{\text{ave}}},w )}
K \big( \Theta, \Gamma_f,   \tilde{\kappa}(L_{G_{d^{\text{ave}}},w}  ) , \epsilon\big),
\label{happy2}
\end{equation}
where $G_{d^{\text{ave}}}$ denotes an unknown graph whose nodes have the same degree.
Optimizing $d^{\text{ave}}$ in \eqref{happy} after knowing $H (d^{\text{ave}}) $ and $F (d^{\text{ave}}) $ can only be done on a problem-by-problem and algorithm-by-algorithm basis. However, the minimum arguments in the expression \eqref{happy2} in the definition of $H (d^{\text{ave}}) $ are always graphs such that $ \tilde{\kappa}(L_{G_{d^{\text{ave}}},w})$ is minimized.  In light of this, we propose to promote communication efficiency by optimizing $ \tilde{\kappa}(L_{G_{d^{\text{ave}}},w} )$ in any case (i.e. whether we know the actual expression of $K$ or not, or even in the case when $\{\mu_e\}$ is not so uniform.)


\section{Graph optimization (of $\tilde{\kappa}(L_{G})$ or $\tilde{\kappa}(L_{G,w})$)}


\subsection{Exact optimizer with specific nodes and degree $(N,d)$: Ramanujan graphs}

For a general $d$-regular graph, it is known from Alon Boppana Theorem in \cite{alon1997edge,alon2001semi,dodziuk1984difference} that
\begin{equation*}
 \lambda_1 (A) \geq 2 \sqrt{d - 1 } - \frac{ 2 \sqrt{d - 1 } -1}{ \lfloor D/2\rfloor}
\end{equation*}
where $D$ is the diameter of $G$.
%Now, we are ready to introduce the definition of Ramanujan graphs.
\begin{definition} \cite{murty2003ramanujan,newman2000laplacian,chung1997spectral,lubotzky1988ramanujan}
A $d$-regular graph $G$ is a Ramanujan graphs if it satisfies
\begin{equation}
 \lambda_1 (A_G) \leq 2 \sqrt{d - 1 },
\end{equation}
where $A_G$ is the adjacency matrix of $G$.
\end{definition}

In fact, a Ramanujan graph serves as an asymptotic minimizer of $\tilde{\kappa}(L_{G_d}) $ for a $d$-regular graph $G_d$. For a Ramanujan graph, the reduced condition number of the Laplacian satisfies:
\begin{equation*}
\tilde{\kappa}(L_{G_d})  \leq \frac{d + 2 \sqrt{d - 1 } }{ d - 2 \sqrt{d - 1 } } \,.
\label{eqLd}
\end{equation*}

%\footnote{ \commws{As one can see that the upper bound of $\tilde{\kappa}$ shown above for regular graphs drops dramatically as $d$ increases (much faster than the function $h(d)=N-d$). This corroborates with the statistical experiments in the decentralized ADMM paper. In the experiments of the ADMM paper, we have observed that for large networks, a relatively small connectivity ratio (translates into $d$ for regular graph) could lead to fast convergence. It is known or maybe obvious that, a (general) undirected graph with the same connectivity ratio/average degree can have bad condition number and slow convergence. But when it comes to Ranmanujan/regular graphs, a natural question would be whether a regular graph with some specific $d$ can have much worse condition number/slower convergence compared to a Ranmanujan graph with the same $d$. In other words, if one draws $\tilde{\kappa}(d)$ for ``worst'' regular graphs and Ramanujan graphs, how much improvement can we see for Ramanujan graphs?} Dear Wei,  It seems to me that the above estimate is satisfied only in the case of a ramanujan graph.}

If we use a Ramanujan graph that minimizes $\tilde{\kappa}(L_{G_d})$, we can then find an approximate minimizer in \eqref{happy2} and thus \eqref{happy} for the total communication cost by further finding $d$ (or $d^{\text{ave}}$).

Explicit constructions of Ramanujan graphs are known only for some special $(N,d)$, as labelled Cayley graphs and the Lubotzky-Phillips-Sarnak construction \cite{lubotzky1986explicit}, with some computation given in \cite{kpsgraph,randy2010} or construction of bipartite Ramanujan graphs
\cite{marcus2013interlacing}.
Interested readers may consult \cite{newman2000laplacian,murty2003ramanujan,hoory2006expander,chung1997spectral,lubotzky1986explicit,lubotzky1988ramanujan} for more references.


\subsection{Optimizer for large $N$: Random $d$-regular graphs}

In some practical situations, however, we encounter pairs $(N,d)$ where an explicit Ramanujan graph is still unknown. When $N$ is very large, we propose a random $d$-regular graph as a solution of optimal communication efficiency, with randomness performed as follows \cite{friedman2008proof} (where $d$ shall be even and $N$ can be an arbitrary integer that is greater than $2$):
choosing independently $d/2$ permutations $\pi_{j}, j = 1,..,d/2 $ of the numbers from $1$ to $n$, with each permutation equally
likely, a graph $G = (V,E)$ with vertices $V = {1,...,n}$ is given by
\begin{equation*}
E = \{ (i, \pi_{j}(i) ), i = 1,...n, j = 1,..., d/2 \}\,.
\end{equation*}
%\commws{Only allowing even $d$ so that $N$ could be arbitrary integer that is greater than $2$? Fine.}
The validity of using random graphs as an approximate optimizer is ensured by the Friedman Theorem as below:
\begin{theorem} \cite{friedman2008proof}
For every $\epsilon>0$,
\begin{equation}
\mathbb{P} (\lambda_1(A) \leq 2 \sqrt{d-1} + \epsilon)
= 1- o_N(1)
\end{equation}
where $G$ is a random $(N,d)$-graph.\footnote{The notion $g(N)=o_N(f(N))$ means $\lim_{N\rightarrow\infty}g(N)/f(N)=0$.}
%\footnote{ \commws{I assume there is a typo here which used $O$ instead of $o$. I've changed it to $o$.} Indeed, it is a typo, I am sorry about that. }.
\end{theorem}
Roughly speaking, this theorem says that for a very large $N$, almost all random $(N,d)$ graphs are Ramanujan, i.e. they are nicely connected. Therefore, it is just fine to adopt a random $(N,d)$ graph when $N$ is too large for a Ramanujan graph or sparsifier to be explicitly computed.

It is possible that some regular graphs are not connected. To address this issue, we first grow a random spanning tree of the underlying graph to ensure connectivity. A random generator for regular graphs is  GGen2 \cite{GGen}. 

%\footnote{
%\commws{Hi Raymond I have a question here. Is a regular graph with large enough $d$ asymptotically optimal %($N\rightarrow\infty$) as an expander? If so, then, the logic of this paper is rather clear for me. For large $N$, we use %asymptotic optimizer as the solution; For small $N$ under which Ramanujan graphs are in hand, we can use Ramanujan graphs directly; For small $N$ under which however Ramanujan graphs are not available, we propose a %heuristic based on Theorems 3-5.}
%Thank you very much. For a fixed $d$, regular graph with large enough $N$ is asymptotically optimal.  What you %described is correct. (I presume a type for $d$ in you question.  For a large enough $d$, the graph will become almost %complete regardless how you design it.)
%}

\subsection{Approximation for small $N$: $2$-Ramanujan Sparsifier} \label{sec:sparsifier}
For some small $N$, an explicit $(N,d)$-Ramanujan graph may still be unavailable. We hope to construct an approximate Ramanujan graph, i.e. expanders which are sub-optimal but work well in practice.  An example is given by the $2$-Ramanujan sparsifier, which is the subgraph $H$ as follows:

\begin{theorem} \cite{batson2012twice}
\label{imp_sparse}
For every $d >1$, every undirected weighted graph $G = (V,E,w)$ on $N$ vertices contains a weighted subgraph
$H = (V,F, w')$ with at most $d(N-1)$ edges (i.e. an average at most $2d$ graph) that satisfies
\begin{equation}
L_{G,w} \preccurlyeq L_{H,w'} \preccurlyeq \frac{d+1 + 2 \sqrt{d}}{d+1 - 2 \sqrt{d}}  \, L_{G,w}
\label{hahahaha}
\end{equation}
where the Loewner partial order relation $A \preccurlyeq B$ indicates that $B-A$ is a positive semidefinite matrix.
\end{theorem}
This theorem allows us to construct a sparsifier from an original graph $G$.  Actually, the proof of the theorem provides us with an explicit algorithm for such a construction \cite{batson2012twice}.

\iffalse
In Section \ref{sec:app}, we propose a new modification of the algorithm in \cite{batson2012twice} to get to a $2$-Ramanujan sparsifier which includes the consideration of cost $\mu = \{\mu_e\}_{e\in E}$, a brief description of the algorithm after some modifications will be given below.  We shall celebrate the fact that the change is minimal, and that the original theorem in \cite{batson2012twice} automatically applies to guarantee the validity of each step in the following algorithm.  Moreover, we also have a theorem to guarantee this weighted graph sparsifier is ``almost'' optimal in the following sense:
\begin{theorem} \cite{batson2012twice}
Let $G$ be the complete graph on vertex set $V$, and let $H =
(V,E,w)$ be any weighted graph with $N$ vertices, and a vertex of degree $d$ such that \eqref{hahahaha} holds. Then
\begin{equation*}
\tilde{\kappa}(L_{H,w}) \geq 1+ \frac{2}{ \sqrt{d}}-O(\frac{\sqrt{d}}{N}).
\end{equation*}
\end{theorem}
To conclude, this  algorithm gives us a simple approach to design an almost optimal topology for communication-efficient decentralized optimization when no optimizer is previously recorded.   Please refer to Section \ref{sec:app} for more details.
\fi


\section{Numerical Experiments} \label{sec:num}

In this subsection, we illustrate the communication efficiency optimization achieved by expander graphs.

Since the focus of our work is not to investigate various methods to produce expander graphs, we did not test \textbf{Algorithm I}.
Rather, our focus is to illustrate that a smaller \emph{reduced condition number} improves communication efficiency and that expander graphs are good choices to reduce communication in decentralized optimization.  Therefore we  compare the difference in communication efficiency using existing graphs with different reduced condition numbers.
We compare the convergence speeds on a family of (possibly non-convex non-smooth) problems which are approximate formulations of finding the sup-norm of a vector $l = (l_1,...,l_M)$ (up to sign).


\noindent \textbf{Example 1}.  We choose $M = P = 1092$.  Our problem is:
\begin{equation*}
\min_{x \in \mathbb{R}^P } f(x) = \tfrac{1}{M}\textstyle
 \sum_{i= 1}^M  f_{i}(x) ,
\end{equation*}
where
\begin{equation*}
f_i(x) = l_i x_i /  ( \| x \|_1 + \varepsilon )
\end{equation*}
for a small $\varepsilon$ chosen as  $\varepsilon = 1 \times 10^{-5}.$
One very important remark is that this optimization problem is non-convex and non-smooth, and the $\varepsilon$-optimizer occupies a tabular neighbourhood of a whole ray $\{ -\lambda e_{n} : \lambda > 0 \}$, where $l_n = \| l \|_{\infty}$ and $e_n$ is the $n$th coordinate vector $(0,0,...,1,....,0)$.

We solve the problem using the EXTRA algorithm \cite{shi2015extra}:
\begin{equation*}
\begin{cases}
\textbf{x}^{1} = W \textbf{x}^{0} - \alpha  \nabla \textbf{f} (\textbf{x}^{0})  \,, \\
\textbf{x}^{k+2} = (W+I ) \textbf{x}^{k+1} - \frac{W+I }{2} \textbf{x}^{k} - \alpha [\nabla \textbf{f} (\textbf{x}^{k+1}) - \nabla \textbf{f} (\textbf{x}^{k})  ] \,.
\end{cases}
\end{equation*}
To compare speeds, we plot the following sequence:
\begin{equation*}
  \delta_k := \tfrac{1}{M} \textstyle\sum_{i= 1}^M   F_{i}( \textbf{x}^k ) - \min_{x} F(x) \,.
\end{equation*}
Figure \ref{EXTRA} shows the sequence $ \delta_k$ under $4$ different graph topologies:
Ramanujan $30$-graph $\LPS(29,13)$, a regular-$30$, a regular-$60$ graph, and a regular-$120$ graph. 
Our regular $d$ graphs (other than $LPS(29,13)$) are generated by joining the $i$th node to the $\left \{ i+ \lfloor \frac{N}{d} \rfloor k  \mod  N \, : \, 0 \leq k < \frac{d}{2} \right\}$th nodes for all $ 0 \leq i \leq N-1 $ (in here we label the nodes from $0$ to $N-1$).
The mixing matrices $W$ that we use are generated as $W_{L_{G,w}}$ as described in \eqref{WW} with $w = (w_e )$ where $w_e = 1$ on all edges $e \in E$.
We clearly see that the convergence rate of the algorithm under Ramanujan $30$-graph $\LPS(29,13)$ is even better than that of a regular-$120$ graph in the first $40$ iterations.   Afterward, the curve of the Ramanujan $30$-graph becomes flat, probably because it already arrived a small tabular neighborhood of the ray of $\varepsilon$-optimizer. Table \ref{EXTRA_table} shows the number of iteration $k_0$ as well as its total communication complexity to achieve $$ \text{stopping rule:}\quad |\delta_{k_0}  -  \delta_{k_0-1}| < 1\times 10^{-3}.$$ 
%to be achieved. 
We see that an expander graph reduces communication complexity.  One can observe the rapid drop of the red curve because of its efficiency to locate the active set.

\begin{figure}
\begin{center}
     \vskip -0.3truecm
           \scalebox{0.35}{\includegraphics{./EXTRA_sup_norm_compare_fn}}
    \vskip -0.5truecm
    \scalebox{0.35}{\includegraphics{./EXTRA_sup_norm_compare_fn_log}}
    \vskip -0.3truecm
     \caption{\small Convergence rate of EXTRA in \textbf{Example 1} over Ramanujan $30$-graph $\LPS(29,13)$ (red, the best), $30$-reg graph (blue), $60$-reg graph (green) and $120$-reg graph (black).}\label{EXTRA}
     \end{center}
\end{figure}

\begin{table}
\begin{tabular}{ c| r | r | r}
\hline
 & $\tilde{\kappa}(L_G)$ & No. of Itr. &             Total comm. complexity \\
\hline
$\LPS(29,13)$  & 1.9538 &          52  &1703520 \\
\hline
Regular $30$ graph &  30.5375  &     444  & 14545440 \\
\hline
Regular $60$ graph &   32.1103   &     494  & 32366880 \\
\hline
Regular $120$ graph &   27.1499 &      454  &  59492160 \\
\hline
\end{tabular}
 \caption{\small Communication complexity in \textbf{Example 1} for Ramanujan $30$-graph $\LPS(29,13)$, $30$-reg, $60$-reg, and$120$-reg graph.}\label{EXTRA_table}
\end{table}


\noindent \textbf{Example 2}.  In this case we again choose $M = 1092$, but $P = 1 $ (i.e. $1$ dimensional problem).  Our problem is
with a similar form as in \textbf{Example 1}, but with
\begin{equation*}
f_i(x) = \chi_{a \geq \sqrt { | l_i | } }(x ) + |x |^2.
\end{equation*}
This is a convex non-smooth problem. We apply  PG-EXTRA \cite{shi2015proximal} to solve this problem.
To proceed, we split $f_i$ as
\begin{equation*}
\begin{cases}
s_i(x) := |x |^2  \\
r_i(x) :=  \chi_{a \geq \sqrt { | l_i | } }(x ) ,
\end{cases}
\end{equation*}
and apply the PG-EXTRA iteration:
\begin{equation*}
\begin{cases}
\textbf{x}^{\frac{1}{2}} = W \textbf{x}^{0} - \alpha  \nabla \textbf{f} (\textbf{x}^{k+1})  \,, \\
\textbf{x}^{1} = \argmin \textbf{r}(\textbf{x}) + \frac{1}{2 \alpha} \| \textbf{x} - \textbf{x}^{\frac{1}{2}}  \|_2^2 \,,\\
\textbf{x}^{k+\frac{3}{2}} = W \textbf{x}^{k+1} + \textbf{x}^{k+\frac{1}{2}} - \frac{W+I }{2} \textbf{x}^{k} - \alpha [\nabla \textbf{s} (\textbf{x}^{k+1}) - \nabla \textbf{s} (\textbf{x}^{k})  ] \,, \\
\textbf{x}^{k+2} = \argmin \textbf{r}(\textbf{x}) + \frac{1}{2 \alpha} \| \textbf{x} - \textbf{x}^{k + \frac{3}{2}}  \|_2^2 \,.\\
\end{cases}
\end{equation*}
To compare speeds, we plot the following sequence:
\begin{equation*}
  \delta_k := \big| \tfrac{1}{M} \textstyle\sum_{i= 1}^M  s_{i}( \textbf{x}_i^k ) - \min_{x} F(x)  \big| \,.
\end{equation*}
and exclude the $r_i(x) $ part.
The mixing matrices that we use are the same as those described in \textbf{Example 1}.
As shown in Figure \ref{PGEXTRA2} the convergence rate of the algorithm under the Ramanujan $30$-graph $\LPS(29,13)$ is still the best though is  less outstanding.
\begin{figure}
\begin{center}
     \vskip -0.3truecm
           \scalebox{0.35}{\includegraphics{./EXTRA_sup_norm_compare_fn_PG_2}}
    \vskip -0.5truecm
    \scalebox{0.35}{\includegraphics{./EXTRA_sup_norm_compare_fn_log_PG_2}}
    \vskip -0.3truecm
        \caption{\small Convergence rate of PG-EXTRA in \textbf{Example 2} over Ramanujan $30$-graph $\LPS(29,13)$ (in red), $30$-reg (in blue), $60$-reg (in green), and $120$-reg graph (in black).}\label{PGEXTRA2}
     \end{center}
\end{figure}
Table \ref{PGEXTRA2_table} shows the numbers of iteration $k_0$ as well as the total communication complexities to achieve $  | \delta_{k_0}  -  \delta_{k_0-1} | < 1\times 10^{-3}$. The expander graph has the clear advantage.
\begin{table}
\begin{tabular}{ c| r | r | r}
\hline
 & $\tilde{\kappa}(L_G)$ & No. of Itr. &             Total comm. complexity \\
\hline
$\LPS(29,13)$  & 1.9538 &          811 &  26568360 \\
\hline
Regular $30$ graph &  30.5375  &     1001  &  32792760 \\
\hline
Regular $60$ graph &  32.1103    &     832  & 54512640 \\
\hline
Regular $120$ graph &  27.1499 &     953 &   124881120 \\
\hline
\end{tabular}
 \caption{\small Communication complexity in \textbf{Example 2} for Ramanujan $30$-graph $\LPS(29,13)$, $30$-reg, $60$-reg  and$120$-reg graphs.}\label{PGEXTRA2_table}
\end{table}

\iffalse
\section{Appendix}  \label{sec:app}

In this section we briefly introduce a modified algorithm (from \cite{batson2012twice}) to get to a $2$-Ramanujan sparsifier that incoperates the information $\mu = \{\mu_e\}_{e\in E}$.
Following \cite{batson2012twice}, for expositional sake, we will introduce a bunch of notations:
For a given $u,l$, we define the upper barrier and lower barrier functions $\Phi^u$ and  $\Phi_l$ as
\begin{equation*}
\begin{cases}
\Phi^u(A) := \text{tr}(uI -A)^{-1} \\
\Phi_l(A) := \text{tr}(A - lI)^{-1}
\end{cases}
\end{equation*}
for all symmetric matrices $A$.
Also, for a given pair of $ \delta_U, \delta_L$, we define
{\small
\begin{equation*}
\begin{cases}
U^{\delta_U}  (A, v) := \frac{v ((l+ \delta_U) I - A  )^{-2}  v }{\Phi^{ u} (A) - \Phi^{ u +  \delta_U  } (A) }  + v ((l+ \delta_U) I - A  )^{-1}  v\\
L_{\delta_L} (A,v) := \frac{v (A - (l+ \delta_L) I)^{-2}  v }{\Phi_{ l+  \delta_L } (A) - \Phi_{ l } (A)}  - v (A - (l+ \delta_L) I)^{-1}  v
\end{cases}
\end{equation*}
}for all symmetric matrices $A$ and vectors $v$.
For notational sake, let us also recall that whenever we write $s = \{s_e\}_{e \in E} $, $s$ denotes a vector formed by $s_e$ for all edges $e$.

Now we are ready to state the following sparsifying algorithm modified from \cite{batson2012twice}:

%\footnote{
%\commws{Dear Raymond, could you forward the citations of Theorems 3-5 and Algorithm 1 to me? Thank you very 
%much.
%}
%I am sorry to have sent the paper late.  The paper is here:
%http://cs-www.cs.yale.edu/homes/spielman/PAPERS/77287.pdf
%I will also send to you by email.  Btw citations you suggested are now in mybibtex.  But I have not put them all in the %paper yet.
%}

\begin{center}
\textbf{Algorithm I} 
\end{center}
\begin{enumerate}
\item
Initialize a weighted graph $G = (V,E,w)$, where $E$ contains all the edges where $d_e \neq \infty$, and $w$ are some original weights that describe an original network (e.g. we may choose $w_e=1$ on all the edges.)
\item
Compute $\{v_e\}$ as column vectors of
\begin{equation*}
V = \sqrt{ L_G^{+} } B^T \sqrt{w} \,.
\end{equation*}
where $B$ is the incidence matrix of $G$.
\item
Initialize
$\epsilon_U =\frac{\sqrt{d} -1}{ d + \sqrt{d}}$, $\epsilon_L = \frac{1}{\sqrt{d}}$  , $u_0 = n/\epsilon_U$,  $l_0 = - n/\epsilon_L$,  $\delta_U =\frac{\sqrt{d} +1}{  \sqrt{d} - 1}$, $\delta_L = 1$, $A^(0) := 0$. Also, for $e = 1,..., | \{ v_e\} |$, initialize $s_e = 0$.
\item
For $q = 1,...,Nd-1$, DO
\begin{itemize}
\item
For $e = 1,..., | \{ v_e\} |$, compute $L_{\delta_L} (A^q,v_e)  $ and $U_{\delta_U} (A^q,v_e) $;
\item
Compute
\begin{equation*}
e= \text{argmin}_{e} \left\{\mu_{e} : L_{\delta_L} (A^{(q)},v_e)  \geq U^{\delta_U} (A^{(q)},v_e) \right \} \,;
\end{equation*}
\item
Let $s_e$ such that
\begin{equation*}
L_{\delta_L} (A^{(q)},v_e)  \geq 1/s_e \geq U^{\delta_U} (A^{(q)},v_e)  \,;
\end{equation*}
\item
Compute $A^{(q+1)} := A^(q) + s_e v_e v_e^T$;
\item
Update $u_0 = u+\delta_U$, $l_0 = u+\delta_L$.
\end{itemize}
\end{enumerate}
Then the new weighted graph $G'= (V,E, sw)$ is the sparsifier of the original graph $G = (V,E,w)$.  %The powerful t
Theorem in \cite{batson2012twice} guarantee the validity of the steps in the algorithm.

%Then we have the following powerful theorem to guarantee the validity of the steps in the algorithm we are going to introduce.
%\begin{theorem} 
%\label{lolzlolz}
%If $\lambda_{\text{max}}  (A) < u$, $\lambda_{\text{max}}  (A) > l$, $\Phi^u(A) \leq  \epsilon_U $  $\Phi_l (A) \leq  \epsilon_L $ and $\epsilon_U , \epsilon_L , \delta_U ,\delta_L$ are some constants satisfying
%\begin{equation*}
%0 \leq \frac{1}{\delta_U} + \epsilon_U \leq \frac{1}{\delta_L} - \epsilon_L\,
%\end{equation*}
%then there exists a vector $v \in \{v_i\} $
%\begin{equation*}
%L_{\delta_L} (A,v)  \geq  U^{\delta_U}  (A, v)
%\end{equation*}
%For such $v$, let $s$ be such that
%\begin{equation*}
%L_{\delta_L} (A,v)  \geq  1/s \geq U^{\delta_U}  (A, v) \,,
%\end{equation*}
%then
%{\small
%\begin{equation*}
%\begin{cases}
%\Phi^{ u + \delta_U }  (A + sv v^T ) \leq \Phi^{ u }(A) \leq \epsilon_U, & \lambda_{\text{max}}  (A + sv v^T )< u + \delta_U %\,, \\
%\Phi_{ l+  \delta_L }  (A + sv v^T ) \leq \Phi_{ l }(A) \leq \epsilon_L , & \lambda_{\text{min}}  (A + sv v^T ) > l+ \delta_L \,.
%\end{cases}
%\end{equation*}
%}
%\end{theorem}

We would like to remark that \textbf{Algorithm I} has taken care of the case when some edges are actually blocked, which is likely to happen in some practical situations when some cables are prohibited by the users.   In order to do so, we may initialize $G = (V,E,w)$ as a graph with all the edges connected except the blocked edges.   Then  \textbf{Algorithm I}  produces a sparsifier $G'= (V,E, sw)$ of $(G,E,w)$, and $G'$ is actually the graph $H$ that satisfies \eqref{imp_sparse}.

How to optimize a graph using this algorithm in a decentralized manner and how we may also incoperate information of the target functional $f(x)$ will be focuses of our future research.
\fi

\bibliographystyle{IEEEbib}
\bibliography{mybibfile}


\end{document}


citations to be organized:

\footnote{\url{http://www.seas.upenn.edu/~jadbabai/ESE680/Laplacian_Thesis.pdf}}


\footnote{\url{http://www.mast.queensu.ca/~murty/ramanujan.pdf} 


\footnote{\url{http://www.mast.queensu.ca/~ctardif/lps/LPSSup.pdf}}


\footnote{\url{http://www.mast.queensu.ca/~ctardif/LPS.html}}


\footnote{\url{http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/S0273-0979-06-01126-8.pdf}}


\footnote{\url{http://cs-www.cs.yale.edu/homes/spielman/PAPERS/77287.pdf}}

[1] Ghadimi, Euhanna, et al. "The ADMM algorithm for distributed averaging: Convergence rates and optimal parameter selection." 2014 48th Asilomar Conference on Signals, Systems and Computers. IEEE, 2014. (about weight selection)

[2] Hoory, Shlomo, Nathan Linial, and Avi Wigderson. "Expander graphs and their applications." Bulletin of the American Mathematical Society 43.4 (2006): 439-561. (about graph chosen)

[3] D-ADMM: A communication-efficient distributed algorithm for separable optimization (general citation, considering saving communication cost)

[4] On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian (about graph placement, related to one of our point considering that the communication cost is proportional to the distance)

[5] A. Ghosh and S. Boyd. Growing well-connected graphs. (This one has been mentioned in our discussion)




This email was automatically sent to you upon submission of Extended
Summary 1166, titled: 'Expander Graph and Communication-Efﬁcient
Decentralized Optimization' to the Asilomar 2016 online submission system.

Please note the following important information:
Paper ID: 1166
Paper Access Password: 53D25035

Invited papers are not required to submit an extended summary, so this
submission is complete (unless this paper is also entered in the Student
Paper Contest).

Submission Timestamp: 4/27/2016 12:38:18 AM

Note to authors submitting papers:

 - No more than four submissions are allowed per contributor, as author or
co-author.
 - At least one author must be registered for the conference.
 - An author must present the paper at the conference. No exception is made
to this policy even if there are travel disruptions or a Visa is not
secured in time.

Thank you for participating in Asilomar 2016.





\noindent \textbf{Example 2}.  In this case we again choose $M = P = 1092$.  Our target functional is now with a similar form as in \textbf{Example 1}, but with
\begin{equation*}
f_i(x) = l_i x_i + \chi_{\| \cdot \|_1 } (x) \,.
\end{equation*}
Now this is a convex but non-smooth functional which is suitable for applying the PG-EXTRA \cite{shi2015proximal} for decentralized optimization:
\begin{equation*}
\begin{cases}
\textbf{x}^{\frac{1}{2}} = W \textbf{x}^{0} - \alpha  \nabla \textbf{f} (\textbf{x}^{k+1})  \,, \\
\textbf{x}^{1} = \argmin \textbf{r}(\textbf{x}) + \frac{1}{2 \alpha} \| \textbf{x} - \textbf{x}^{\frac{1}{2}}  \|_2^2 \,,\\
\textbf{x}^{k+\frac{3}{2}} = W \textbf{x}^{k+1} + \textbf{x}^{k+\frac{1}{2}} - \frac{W+I }{2} \textbf{x}^{k} - \alpha [\nabla \textbf{s} (\textbf{x}^{k+1}) - \nabla \textbf{s} (\textbf{x}^{k})  ] \,, \\
\textbf{x}^{k+2} = \argmin \textbf{r}(\textbf{x}) + \frac{1}{2 \alpha} \| \textbf{x} - \textbf{x}^{k + \frac{3}{2}}  \|_2^2 \,,\\
\end{cases}
\end{equation*}
where $f_i(x)$ are now splitted as the sum of the two following functions
\begin{equation*}
\begin{cases}
s_i(x) :=  l_i x_i  \\
r_i(x) := \chi_{\| \cdot \|_1 } (x) \,.
\end{cases}
\end{equation*}
and $\textbf{r}, \textbf{s}$ are again their vectorizations.

In this case, we plot the following sequence to illustrate the speed of convergence:
\begin{equation*}
  \delta_k := \left| \frac{1}{M} \sum_{i= 1}^M  s_{i}( \textbf{x}_i^k ) - \min_{x} F(x) \right| \,.
\end{equation*}
and not to include the $r_i(x) $ part or otherwise it will get to infinity.
Again the sequences $\delta_k$ for the respective graphs are the plot.
Now as shown in Figure \ref{PGEXTRA1} the convergence rate of the algorithm under Ramanujan $30$-graph $LPS(29,13)$ better still, but it is less outstanding.


\begin{figure}
\begin{center}
     \vskip -0.3truecm
           \scalebox{0.4}{\includegraphics{./EXTRA_sup_norm_compare_fn_PG}}
    \scalebox{0.4}{\includegraphics{./EXTRA_sup_norm_compare_fn_log_PG}}
        \caption{\small Convergence rate of PG-EXTRA in \textbf{Example 2} over Ramanujan $30$-graph $LPS(29,13)$ (in red), a $30$-reg graph (in blue), a average $60$-reg graph (in green) and a random average $120$-reg graph (in black).}\label{PGEXTRA1}
     \end{center}
\end{figure}


 Table \ref{PGEXTRA1_table} shows the number of iteration $k_0$ as well as its total communication complexity in order for $  \delta_{k_0}  -  \delta_{k_0-1} < 1\times 10^{-3}$ to be achieved.  Now, although expander graphs still have an edge, it does not give clear advantage over other graphs.

\begin{table}
\begin{tabular}{ c| r | r | r}
\hline
 & $\tilde{\kappa}(L_G)$ & No. of Itr. &             Total commu. complexity \\
\hline
$LPS(29,13)$  & 1.9538 &          585  &  19164600 \\
\hline
Regular $30$ graph &  30.5375  &     587  &  19230120 \\
\hline
Regular $60 $graph &  32.1103    &     587  & 38460240 \\
\hline
Regular $120$ graph &  27.1499 &      586  &  76789440 \\
\hline
\end{tabular}
 \caption{\small Convergence rate of PG-EXTRA in \textbf{Example 2} over Ramanujan $30$-graph $LPS(29,13)$ (in red), a $30$-reg graph (in blue), a average $60$-reg graph (in green) and a random average $120$-reg graph (in black).}\label{PGEXTRA1_table}
\end{table}




macros.tex

%% macros for commenting
\usepackage{mathtools}
\usepackage[normalem]{ulem} % to use \sout
%\usepackage{algorithm,algorithmic}
%\usepackage{graphicx, subfigure}
\usepackage{subcaption}
%\usepackage{url}
\usepackage{enumerate}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{amsfonts,dsfont}

\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pdfborder={0 0 0},bookmarksnumbered]{hyperref}

%% a light-weight algorithm environment
\newtheorem{algo}{Algorithm}

%% highlighting and commenting
\newcommand{\outline}[1]{{\color{brown}#1}}
\newcommand{\rev}[1]{{\color{blue}#1}}
\newcommand{\commyc}[1]{{\color{red}(#1 -- Yat-Tin)}} % Yat-Tin Chow's comments
\newcommand{\commws}[1]{{\color{red}(#1 -- Wei)}} % Wei Shi's comments
\newcommand{\commwy}[1]{{\color{red}(#1 -- Wotao)}} % Wotao Yin's comments
\newcommand{\remove}[1]{\sout{#1}}      % strike out
\newcommand{\cut}[1]{}  % completely hide (try to avoid, suggest %)

\newcommand{\define}{\stackrel{\Delta}{=}}      % definition =
\renewcommand{\align}[1]{\begin{align}#1\end{align}}    % align environment

%% macros for letters
\newcommand{\va}{{\mathbf{a}}}
\newcommand{\vb}{{\mathbf{b}}}
\newcommand{\vc}{{\mathbf{c}}}
\newcommand{\vd}{{\mathbf{d}}}
\newcommand{\ve}{{\mathbf{e}}}
\newcommand{\vf}{{\mathbf{f}}}
\newcommand{\vg}{{\mathbf{g}}}
\newcommand{\vh}{{\mathbf{h}}}
\newcommand{\vi}{{\mathbf{i}}}
\newcommand{\vj}{{\mathbf{j}}}
\newcommand{\vk}{{\mathbf{k}}}
\newcommand{\vl}{{\mathbf{l}}}
\newcommand{\vm}{{\mathbf{m}}}
\newcommand{\vn}{{\mathbf{n}}}
\newcommand{\vo}{{\mathbf{o}}}
\newcommand{\vp}{{\mathbf{p}}}
\newcommand{\vq}{{\mathbf{q}}}
\newcommand{\vr}{{\mathbf{r}}}
\newcommand{\vs}{{\mathbf{s}}}
\newcommand{\vt}{{\mathbf{t}}}
\newcommand{\vu}{{\mathbf{u}}}
\newcommand{\vv}{{\mathbf{v}}}
\newcommand{\vw}{{\mathbf{w}}}
\newcommand{\vx}{{\mathbf{x}}}
\newcommand{\vy}{{\mathbf{y}}}
\newcommand{\vz}{{\mathbf{z}}}
%
%\newcommand{\ta}{{\tilde{a}}}
%\newcommand{\tb}{{\tilde{b}}}
%\newcommand{\tc}{{\tilde{c}}}
%\newcommand{\td}{{\tilde{d}}}
%\newcommand{\te}{{\tilde{e}}}
%\newcommand{\tf}{{\tilde{f}}}
%\newcommand{\tg}{{\tilde{g}}}
%\newcommand{\th}{{\tilde{h}}}
%\newcommand{\ti}{{\tilde{i}}}
%\newcommand{\tj}{{\tilde{j}}}
%\newcommand{\tk}{{\tilde{k}}}
%\newcommand{\tl}{{\tilde{l}}}
%\newcommand{\tm}{{\tilde{m}}}
%\newcommand{\tn}{{\tilde{n}}}
%\newcommand{\to}{{\tilde{o}}}
%\newcommand{\tp}{{\tilde{p}}}
%\newcommand{\tq}{{\tilde{q}}}
%\newcommand{\tr}{{\tilde{r}}}
%\newcommand{\ts}{{\tilde{s}}}
%\newcommand{\tt}{{\tilde{t}}}
%\newcommand{\tu}{{\tilde{u}}}
\newcommand{\tv}{{\tilde{v}}}
\newcommand{\tw}{{\tilde{w}}}
%\newcommand{\tx}{{\tilde{x}}}
%\newcommand{\ty}{{\tilde{y}}}
\newcommand{\tz}{{\tilde{z}}}
\newcommand{\umu}{\overline{M}}
\newcommand{\lmu}{\underline{M}}

\newcommand{\vA}{{\mathbf{A}}}
\newcommand{\vB}{{\mathbf{B}}}
\newcommand{\vC}{{\mathbf{C}}}
\newcommand{\vD}{{\mathbf{D}}}
\newcommand{\vE}{{\mathbf{E}}}
\newcommand{\vF}{{\mathbf{F}}}
\newcommand{\vG}{{\mathbf{G}}}
\newcommand{\vH}{{\mathbf{H}}}
\newcommand{\vI}{{\mathbf{I}}}
\newcommand{\vJ}{{\mathbf{J}}}
\newcommand{\vK}{{\mathbf{K}}}
\newcommand{\vL}{{\mathbf{L}}}
\newcommand{\vM}{{\mathbf{M}}}
\newcommand{\vN}{{\mathbf{N}}}
\newcommand{\vO}{{\mathbf{O}}}
\newcommand{\vP}{{\mathbf{P}}}
\newcommand{\vQ}{{\mathbf{Q}}}
\newcommand{\vR}{{\mathbf{R}}}
\newcommand{\vS}{{\mathbf{S}}}
\newcommand{\vT}{{\mathbf{T}}}
\newcommand{\vU}{{\mathbf{U}}}
\newcommand{\vV}{{\mathbf{V}}}
\newcommand{\vW}{{\mathbf{W}}}
\newcommand{\vX}{{\mathbf{X}}}
\newcommand{\vY}{{\mathbf{Y}}}
\newcommand{\vZ}{{\mathbf{Z}}}

\newcommand{\cA}{{\mathcal{A}}}
\newcommand{\cB}{{\mathcal{B}}}
\newcommand{\cC}{{\mathcal{C}}}
\newcommand{\cD}{{\mathcal{D}}}
\newcommand{\cE}{{\mathcal{E}}}
\newcommand{\cF}{{\mathcal{F}}}
\newcommand{\cG}{{\mathcal{G}}}
\newcommand{\cH}{{\mathcal{H}}}
\newcommand{\cI}{{\mathcal{I}}}
\newcommand{\cJ}{{\mathcal{J}}}
\newcommand{\cK}{{\mathcal{K}}}
\newcommand{\cL}{{\mathcal{L}}}
\newcommand{\cM}{{\mathcal{M}}}
\newcommand{\cN}{{\mathcal{N}}}
\newcommand{\cO}{{\mathcal{O}}}
\newcommand{\cP}{{\mathcal{P}}}
\newcommand{\cQ}{{\mathcal{Q}}}
\newcommand{\cR}{{\mathcal{R}}}
\newcommand{\cS}{{\mathcal{S}}}
\newcommand{\cT}{{\mathcal{T}}}
\newcommand{\cU}{{\mathcal{U}}}
\newcommand{\cV}{{\mathcal{V}}}
\newcommand{\cW}{{\mathcal{W}}}
\newcommand{\cX}{{\mathcal{X}}}
\newcommand{\cY}{{\mathcal{Y}}}
\newcommand{\cZ}{{\mathcal{Z}}}

\newcommand{\ri}{{\mathrm{i}}}
\newcommand{\rr}{{\mathrm{r}}}


%% macros for math notions and operators

\newcommand{\FF}{\mathbb{F}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\HH}{\mathbb{H}}
\newcommand{\II}{\mathbb{I}}
\newcommand{\JJ}{\mathbb{J}}
\newcommand{\DD}{\mathbb{D}}
\newcommand{\GG}{\mathbb{G}}
\newcommand{\ZZ}{\mathbb{Z}}
\renewcommand{\SS}{{\mathbb{S}}}
\newcommand{\SSp}{\mathbb{S}_{+}}
\newcommand{\SSpp}{\mathbb{S}_{++}}
\newcommand{\sign}{\mathrm{sign}}
\newcommand{\vzero}{\mathbf{0}}
\newcommand{\vone}{{\mathbf{1}}}

%%Probability symbols.
\newcommand{\EE}{\mathbb{E}}
\newcommand{\mkT}{\mathfrak{T}}
\newcommand{\mkS}{\mathfrak{S}}
\newcommand{\mkQ}{\mathfrak{Q}}
\newcommand{\pr}{\mathrm{prod}}

\newcommand{\st}{{\text{s.t.}}} % subject to
\newcommand{\St}{{\mathrm{subject~to}}} % subject to
\newcommand{\op}{{\mathrm{op}}} % subscript for operator norm
\newcommand{\opt}{{\mathrm{opt}}} % subscript for optimal solution
%\newcommand{\supp}{{\mathrm{supp}}} % support
\newcommand{\Prob}{{\mathrm{Prob}}} % probability
\newcommand{\Diag}{{\mathrm{Diag}}} % vector -> diagonal matrix
%\newcommand{\diag}{{\mathrm{diag}}} % matrix diagonal -> vector
\newcommand{\dom}{{\mathrm{dom}}} % domain
\newcommand{\range}{{\mathrm{range}}} % domain
\newcommand{\grad}{{\nabla}}    % gradient
\newcommand{\tr}{{\mathrm{tr}}} % trace
\newcommand{\TV}{{\mathrm{TV}}} % total variation
\newcommand{\Proj}{{\mathrm{Proj}}}
\newcommand{\prj}{{\mathbf{proj}}}
\newcommand{\prox}{\mathbf{prox}}
\newcommand{\reflh}{\refl^{\bH}}
\newcommand{\proxh}{\prox^{\bH}}
\newcommand{\minimize}{\text{minimize}}
\newcommand{\bgamma}{\boldsymbol{\gamma}}
\newcommand{\bsigma}{\boldsymbol{\sigma}}
\newcommand{\bomega}{\boldsymbol{\omega}}
\newcommand{\blambda}{\boldsymbol{\lambda}}
\newcommand{\bH}{\vH}
\newcommand{\bbH}{\mathbb{H}}
\newcommand{\bB}{\boldsymbol{\cB}}
\newcommand{\Tau}{\mathrm{T}}
\newcommand{\tnabla}{\widetilde{\nabla}}
\newcommand{\TS}{{\cT_{\mathrm{3S}}}}
\newcommand{\TFBS}{{\cT_{\mathrm{FBS}}}}
\newcommand{\TBFS}{{\cT_{\mathrm{BFS}}}}
\newcommand{\TDRS}{{\cT_{\mathrm{DRS}}}}
\newcommand{\TPRS}{{\cT_{\mathrm{PRS}}}}
\newcommand{\TFBFS}{{\cT_{\mathrm{FBFS}}}}
\newcommand{\TFDRS}{{\cT_{\mathrm{FDRS}}}}
\newcommand{\TVC}{{\cT_{\textnormal{CV}}}}
\newcommand{\best}{\mathrm{best}}
\newcommand{\kbest}{k_{\best}}
\newcommand{\diff}{\mathrm{diff}}
\newcommand{\xbar}{\bar{x}}
\newcommand{\xgbar}{\bar{x}_g}
\newcommand{\xfbar}{\bar{x}_f}
\newcommand{\xihat}{\hat{\xi}}
\newcommand{\xg}{x_g}
\newcommand{\xf}{x_f}
\newcommand{\du}{\mathrm{d}u}
\newcommand{\dy}{\mathrm{d}y}
\newcommand{\kconvergence}{\stackrel{k \rightarrow \infty}{\rightarrow }}
\newcommand{\Grph}{\mathrm{Grph}}
\DeclareMathOperator{\shrink}{shrink} % shrinkage
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\Min}{minimize}
\DeclareMathOperator*{\Max}{maximize}
\DeclareMathOperator*{\Fix}{Fix}
\DeclareMathOperator*{\zer}{zer}    % the set of zeros of an operator
\DeclareMathOperator*{\nablah}{\nabla^{\bH}}
\DeclareMathOperator*{\gra}{gra}
\DeclarePairedDelimiter{\dotpb}{\langle}{\rangle_{\bH}}
\DeclarePairedDelimiter{\dotpv}{\langle}{\rangle_{\vH}}
\DeclareMathOperator*{\as}{a.s.}
\newcommand{\nops}[2]{\ensuremath{\mathfrak{M}\left[{#1}\mapsto {#2}\right]}}
\newcommand{\LPS}{\mathrm{LPS}}

%% macros for environments math equations

\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}

\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}

\newcommand{\bfl}{\begin{flushleft}}
\newcommand{\efl}{\end{flushleft}}

\newcommand{\bt}{\begin{tabbing}}
\newcommand{\et}{\end{tabbing}}

\newcommand{\beqn}{\begin{align}}
\newcommand{\eeqn}{\end{align}}

\newcommand{\beqs}{\begin{align*}} % no equation numbers
\newcommand{\eeqs}{\end{align*}}  % no equation numbers

%% macros for theorem-like environments, may not necessary based on the documentclass used
\newtheorem{assumption}{Assumption}

\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof}

\newtheorem{condition}{Condition}
\newtheorem{rul}{Rule}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{example}{Example}

%\newtheorem{example}[remark]{Example}




comm_efficient_decentralized_optimization.bbl
\begin{thebibliography}{10}

\bibitem{EXTRA7}
Alexandros~G Dimakis, Soummya Kar, Jose~MF Moura, Michael~G Rabbat, and Anna
  Scaglione,
\newblock ``Gossip algorithms for distributed signal processing,''
\newblock {\em Proceedings of the IEEE}, vol. 98, no. 11, pp. 1847--1864, 2010.

\bibitem{EXTRA15}
Bjorn Johansson,
\newblock ``On distributed optimization in networked systems,''
\newblock 2008.

\bibitem{EXTRA34}
Lin Xiao, Stephen Boyd, and Seung-Jean Kim,
\newblock ``Distributed average consensus with least-mean-square deviation,''
\newblock {\em Journal of Parallel and Distributed Computing}, vol. 67, no. 1,
  pp. 33--46, 2007.

\bibitem{EXTRA9}
Pedro~A Forero, Alfonso Cano, and Georgios~B Giannakis,
\newblock ``Consensus-based distributed support vector machines,''
\newblock {\em The Journal of Machine Learning Research}, vol. 11, pp.
  1663--1707, 2010.

\bibitem{EXTRA22}
Gonzalo Mateos, Juan~Andres Bazerque, and Georgios~B Giannakis,
\newblock ``Distributed sparse linear regression,''
\newblock {\em Signal Processing, IEEE Transactions on}, vol. 58, no. 10, pp.
  5262--5276, 2010.

\bibitem{EXTRA26}
Joel~B Predd, Sanjeev~R Kulkarni, and H~Vincent Poor,
\newblock ``A collaborative training algorithm for distributed learning,''
\newblock {\em Information Theory, IEEE Transactions on}, vol. 55, no. 4, pp.
  1856--1871, 2009.

\bibitem{EXTRA1}
Juan~Andres Bazerque and Georgios~B Giannakis,
\newblock ``Distributed spectrum sensing for cognitive radio networks by
  exploiting sparsity,''
\newblock {\em Signal Processing, IEEE Transactions on}, vol. 58, no. 3, pp.
  1847--1862, 2010.

\bibitem{EXTRA2}
Juan~Andres Bazerque, Gonzalo Mateos, and Georgios~B Giannakis,
\newblock ``Group-lasso on splines for spectrum cartography,''
\newblock {\em Signal Processing, IEEE Transactions on}, vol. 59, no. 10, pp.
  4648--4663, 2011.

\bibitem{EXTRA16}
Vassilis Kekatos and Georgios Giannakis,
\newblock ``Distributed robust power system state estimation,''
\newblock {\em Power Systems, IEEE Transactions on}, vol. 28, no. 2, pp.
  1617--1626, 2013.

\bibitem{EXTRA18}
Qing Ling and Zhi Tian,
\newblock ``Decentralized sparse signal recovery for compressive sleeping
  wireless sensor networks,''
\newblock {\em Signal Processing, IEEE Transactions on}, vol. 58, no. 7, pp.
  3816--3827, 2010.

\bibitem{EXTRA19}
Qing Ling, Zaiwen Wen, and Wotao Yin,
\newblock ``Decentralized jointly sparse optimization by reweighted
  minimization,''
\newblock {\em Signal Processing, IEEE Transactions on}, vol. 61, no. 5, pp.
  1165--1170, 2013.

\bibitem{EXTRA35}
Kun Yuan, Qing Ling, Wotao Yin, and Alejandro Ribeiro,
\newblock ``A linearized bregman algorithm for decentralized basis pursuit,''
\newblock in {\em Signal Processing Conference (EUSIPCO), 2013 Proceedings of
  the 21st European}. IEEE, 2013, pp. 1--5.

\bibitem{EXTRA20}
Qing Ling, Yangyang Xu, Wotao Yin, and Zaiwen Wen,
\newblock ``Decentralized low-rank matrix completion,''
\newblock in {\em Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE
  International Conference on}. IEEE, 2012, pp. 2925--2928.

\bibitem{shi2015extra}
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin,
\newblock ``Extra: An exact first-order algorithm for decentralized consensus
  optimization,''
\newblock {\em SIAM Journal on Optimization}, vol. 25, no. 2, pp. 944--966,
  2015.

\bibitem{shi2015proximal}
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin,
\newblock ``A proximal gradient algorithm for decentralized nondifferentiable
  optimization,''
\newblock {\em 2015 IEEE International Conference on Acoustics, Speech and
  Signal Processing (ICASSP)}, p. 2964–2968, 2015.

\bibitem{ghadimi2014admm}
Euhanna Ghadimi, Andre Teixeira, Michael~G Rabbat, and Mikael Johansson,
\newblock ``The admm algorithm for distributed averaging: Convergence rates and
  optimal parameter selection,''
\newblock in {\em 2014 48th Asilomar Conference on Signals, Systems and
  Computers}. IEEE, 2014, pp. 783--787.

\bibitem{shi2014linear}
Wei Shi, Qing Ling, Kun Yuan, Gang Wu, and Wotao Yin,
\newblock ``On the linear convergence of the admm in decentralized consensus
  optimization,''
\newblock {\em IEEE Transactions on Signal Processing}, vol. 62, no. 7, pp.
  1750--1761, 2014.

\bibitem{mota2013d}
Joao~FC Mota, Joao~MF Xavier, Pedro~MQ Aguiar, and Markus Puschel,
\newblock ``D-admm: A communication-efficient distributed algorithm for
  separable optimization,''
\newblock {\em IEEE Transactions on Signal Processing}, vol. 61, no. 10, pp.
  2718--2723, 2013.

\bibitem{friedman2008proof}
Joel Friedman,
\newblock {\em A proof of Alon's second eigenvalue conjecture and related
  problems},
\newblock American Mathematical Soc., 2008.

\bibitem{batson2012twice}
Joshua Batson, Daniel~A Spielman, and Nikhil Srivastava,
\newblock ``Twice-ramanujan sparsifiers,''
\newblock {\em SIAM Journal on Computing}, vol. 41, no. 6, pp. 1704--1721,
  2012.

\bibitem{kim2006maximizing}
Yoonsoo Kim and Mehran Mesbahi,
\newblock ``On maximizing the second smallest eigenvalue of a state-dependent
  graph laplacian,''
\newblock {\em IEEE transactions on Automatic Control}, vol. 51, no. 1, pp.
  116--120, 2006.

\bibitem{ghosh2006growing}
Arpita Ghosh and Stephen Boyd,
\newblock ``Growing well-connected graphs,''
\newblock in {\em Proceedings of the 45th IEEE Conference on Decision and
  Control}. IEEE, 2006, pp. 6605--6611.

\bibitem{xiao2004fast}
Lin Xiao and Stephen Boyd,
\newblock ``Fast linear iterations for distributed averaging,''
\newblock {\em Systems \& Control Letters}, vol. 53, no. 1, pp. 65--78, 2004.

\bibitem{zhao2012diffusion}
Xiaochuan Zhao, Sheng-Yuan Tu, and Ali~H Sayed,
\newblock ``Diffusion adaptation over networks under imperfect information
  exchange and non-stationary data,''
\newblock {\em IEEE Transactions on Signal Processing}, vol. 60, no. 7, pp.
  3460--3475, 2012.

\bibitem{boyd2004fastest}
Stephen Boyd, Persi Diaconis, and Lin Xiao,
\newblock ``Fastest mixing markov chain on a graph,''
\newblock {\em SIAM review}, vol. 46, no. 4, pp. 667--689, 2004.

\bibitem{yuan2013convergence}
Kun Yuan, Qing Ling, and Wotao Yin,
\newblock ``On the convergence of decentralized gradient descent,''
\newblock {\em arXiv preprint arXiv:1310.7063}, 2013.

\bibitem{tsitsiklis1984problems}
John~Nikolas Tsitsiklis,
\newblock ``Problems in decentralized decision making and computation.,''
\newblock Tech. {R}ep., DTIC Document, 1984.

\bibitem{chen2012fast}
I-An Chen et~al.,
\newblock {\em Fast distributed first-order methods},
\newblock Ph.D. thesis, Massachusetts Institute of Technology, 2012.

\bibitem{murty2003ramanujan}
M~Ram Murty,
\newblock ``Ramanujan graphs,''
\newblock {\em Journal-Ramanujan Mathematical Society}, vol. 18, no. 1, pp.
  33--52, 2003.

\bibitem{newman2000laplacian}
Michael~William Newman,
\newblock {\em The Laplacian spectrum of graphs},
\newblock Ph.D. thesis, University of Manitoba, 2000.

\bibitem{chung1997spectral}
Fan~RK Chung,
\newblock {\em Spectral graph theory}, vol.~92,
\newblock American Mathematical Soc., 1997.

\bibitem{alon2004probabilistic}
Noga Alon and Joel~H Spencer,
\newblock {\em The probabilistic method},
\newblock John Wiley \& Sons, 2004.

\bibitem{alon1997edge}
Noga Alon,
\newblock ``On the edge-expansion of graphs,''
\newblock {\em Combinatorics, Probability and Computing}, vol. 6, no. 02, pp.
  145--152, 1997.

\bibitem{alon2001semi}
Noga Alon, Alexander Lubotzky, and Avi Wigderson,
\newblock ``Semi-direct product in groups and zig-zag product in graphs:
  connections and applications,''
\newblock in {\em Foundations of Computer Science, 2001. Proceedings. 42nd IEEE
  Symposium on}. IEEE, 2001, pp. 630--637.

\bibitem{dodziuk1984difference}
Jozef Dodziuk,
\newblock ``Difference equations, isoperimetric inequality and transience of
  certain random walks,''
\newblock {\em Transactions of the American Mathematical Society}, vol. 284,
  no. 2, pp. 787--794, 1984.

\bibitem{lubotzky1988ramanujan}
Alexander Lubotzky, Ralph Phillips, and Peter Sarnak,
\newblock ``Ramanujan graphs,''
\newblock {\em Combinatorica}, vol. 8, no. 3, pp. 261--277, 1988.

\bibitem{lubotzky1986explicit}
Alexander Lubotzky, Ralph Phillips, and Peter Sarnak,
\newblock ``Explicit expanders and the ramanujan conjectures,''
\newblock in {\em Proceedings of the eighteenth annual ACM symposium on Theory
  of computing}. ACM, 1986, pp. 240--246.

\bibitem{kpsgraph}
``Lubotzky-phillips-sarnak graphs,''
  \url{http://www.mast.queensu.ca/~ctardif/LPS.html},
\newblock Accessed: 2010-09-30.

\bibitem{randy2010}
Randy Elzinga,
\newblock ``Producing the graphs of lubotzky, phillips and sarnak in matlab,''
  \url{http://www.mast.queensu.ca/~ctardif/lps/LPSSup.pdf}, 2010.

\bibitem{marcus2013interlacing}
Adam Marcus, Daniel~A Spielman, and Nikhil Srivastava,
\newblock ``Interlacing families i: Bipartite ramanujan graphs of all
  degrees,''
\newblock in {\em Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual
  Symposium on}. IEEE, 2013, pp. 529--537.

\bibitem{hoory2006expander}
Shlomo Hoory, Nathan Linial, and Avi Wigderson,
\newblock ``Expander graphs and their applications,''
\newblock {\em Bulletin of the American Mathematical Society}, vol. 43, no. 4,
  pp. 439--561, 2006.

\bibitem{GGen}
Wei Shi,
\newblock ``Ggen: Graph generation for network computing simulations,''
  \url{http://home.ustc.edu.cn/~shiwei00/html/GGen.html}, 2014.

\end{thebibliography}
