\section{Convergence Analysis}\label{sec:convergence}

In this section, we prove that for sufficiently large number of iterations, the sequence of local iterates generated by QDGD converges to an arbitrarily precise approximation of the optimal solution of Problem~\eqref{eq:main_2} and consequently Problem~(\ref{eq:main}). The following assumptions hold throughout the analysis of the algorithm.

\begin{assumption}\label{assump1}
Local objective functions $f_i$ are differentiable and smooth with parameter $L$, i.e.,

\begin{equation}
    \norm{\gr f_i(\bx) - \gr f_i(\mathbf{y})} \leq L \norm{\bx - \mathbf{y}}, 
\end{equation}

for any $\bx, \mathbf{y} \in \mathbb{R}^{p}$. \footnote{Local objectives may have different smoothness parameters, however, WLOG one can consider the largest smoothness parameter as the one for all the objectives.}
\end{assumption}

\begin{assumption}\label{assump2}
Local objective functions $f_i$ are strongly convex with parameter $\mu$, i.e.,

\begin{equation}
    \langle \gr f_i(\bx) - \gr f_i(\mathbf{y}) , \bx - \mathbf{y} \rangle \geq \mu \norm{\bx - \mathbf{y}}^2, 
\end{equation}

for any $\bx, \mathbf{y} \in \mathbb{R}^{p}$.\footnote{Local objectives may have different strong convexity parameters, however, WLOG one can consider the smallest strong convexity parameter as the one for all the objectives.}

\end{assumption}

\begin{assumption}\label{assump3}
The random quantizer $Q(\cdot)$ is unbiased and has a bounded variance, i.e.,

\begin{equation}
    \bE \left[Q(\bx)| \bx \right]=\bx, \quad \text{ and } \quad \bE \left[ \norm{Q(\bx)-\bx}^2 | \bx \right]\leq \sigma^2,
\end{equation}

for any $\bx \in \mathbb{R}^{p}$; and quantizations are carried out independently on distributed nodes.
\end{assumption}

\begin{assumption}\label{assump4}
The weight matrix $W \in \mathbb{R}^{n\times n}$  with entries $w_{ij}$ satisfies the following conditions 

\begin{equation}
W = W^\top, \quad W \mathbf{1}=\mathbf{1},\quad \text{ and }  \quad \text{null}(I-W)= \text{span}(\mathbf{1}).
\end{equation}


\end{assumption}

The conditions in Assumptions \ref{assump1} and \ref{assump2} imply that the global objective function $f$ is strongly convex with parameter $\mu$ and its gradients are Lipschitz continuous with constant $L$. Assumption \ref{assump3} poses two customary conditions on the quantizer, that are unbiasedness and variance boundedness. Assumption \ref{assump4} implies that weight matrix $W$ is symmetric and  doubly stochastic. The largest eigenvalue of $W$ is $\lambda_1(W)=1$ and all the eigenvalues belong to $(-1,1]$, i.e., the ordered sequence of eigenvalues of $W$ are $1=\lambda_1(W) \geq \lambda_2(W) \geq \cdots \geq \lambda_n(W)  > -1$. We denote by $1-\beta$ the spectral gap associated to the stochastic matrix $W$, where $\beta=\max \left\{|\lambda_2(W)|,|\lambda_n(W)| \right\}$ is the second largest magnitude of the eigenvalues of matrix $W$. It is also customary to assume $\text{rank}(I-W)=n-1$ such that $\text{null}(I-W) = \text{span}(\mathbf{1})$. We let $W_D$ denote the diagonal matrix consisting of the diagonal entries of $W$, i.e. $\{w_{11},\cdots,w_{nn}\}$.

\iffalse
\begin{example}
Let $\gamma \in \mathbb{R}$ and $b \in \mathbb{N}$. The range representable by the tuple $(\gamma,b)$ is
\begin{equation}
\text{dom}(\gamma,b) = \{ -\gamma \cdot 2^{b-1}, \cdots, -\gamma, 0, \gamma, \cdots, \gamma \cdot (2^b-1) \}.
\end{equation}
Let $z$ be the rounded-down quantization of $w$. Then $Q_{(\gamma,b)}$ will round to $z + \gamma$ (the rounded-up quantization of $w$) with probability $\frac{w-z}{\gamma}$, and it will round to $z$ with probability $1-\frac{w-z}{\gamma}$.
For any $w$ in the range, the quantizer is unbiased and variance bounded by constant $\frac{\gamma^2}{4}$.
\end{example}
\fi

In the following theorem we show that the local iterations generated by QDGD converge to the global optima, as close as desired.

\begin{theorem}\label{thm1}
Consider the distributed consensus optimization Problem (\ref{eq:main}) and suppose Assumptions \ref{assump1}--\ref{assump4} hold. Consider $\delta$ as an arbitrary scalar in $(0,1/2)$ and set $\eps=\frac{c_1}{T^{3\delta/2}}$ and $\al = \frac{c_2}{T^{\delta/2}}$ where $c_1$ and $c_2$ are arbitrary positive constants (independent of $T$). Then, for each node $i$, the expected difference between the output of Algorithm~\ref{alg:QDC} after $T$ iterations and the solution of Problem \eqref{eq:main}, i.e. $\widetilde{\bx}^*$ is upper bounded by

\begin{align}\label{eq:main_thm_result}
\bE \Big[\norm{\bx_{i,T} - \widetilde{\bx}^*}^2\Big] &\leq \mathcal{O} \Bigg( \Bigg(  \frac{4n c^2_2 D^2 \left(3+ 2L/\mu\right)^2 }{(1-\beta)^2} \nonumber\\
 &\quad  \quad  \quad   + \frac{2 c_1 { n} \sigma^2 \norm{W\!-\!W_D}^2}{\mu c_2} \Bigg)\frac{1}{T^{\delta}} \Bigg),

\end{align}

if the total number of iterations satisfies $T\geq T_0$, where $T_0$ is a function of $\delta$, $c_1$, $c_2$, $\mu$, $L$, and $\lambda_n(W)$. Moreover,

\begin{align}
	D^2 = 2L  \sum_{i=1}^{n} \left( f_i(0) - f^*_i \right), \quad f^*_i =  \min_{\bx \in \mathbb{R}^p} f_i(\bx).
\end{align}

\end{theorem}


Theorem \ref{thm1} demonstrates that the proposed QDGD provides an approximation solution with vanishing deviation from the optimal solution, despite the fact that the quantization noise does not vanish as the number of iterations progresses. 

By the first glance at the expression in \eqref{eq:main_thm_result} one might suggest to set $\delta=1/2$ to obtain the best possible sublinear convergence rate which is $ \cO \left( \frac{1}{T^{1/2}} \right)$. However, $T_0$, which is a lower bound on the total number of iterations $T$, is an increasing function of $1/(1-2\delta)$, and by choosing $\delta$ very close to $1/2$, the total number of iterations $T$ should be very large to obtain a fast convergence rate close to $ \cO\left( \frac{1}{T^{1/2}}\right)$. Therefore, there is a trade-off between the convergence rate and the minimum number of required iterations. By setting $\delta$ close to $1/2$ we obtain a fast convergence rate but at the cost of running the algorithm for a large number of iterations, and by selecting $\delta$ close to $0$ the lower bound on the total number of iterations becomes smaller at the cost of having a slower convergence rate. {{We will illustrate this trade-off in the numerical experiments.}}

Moreover, note that the result in \eqref{eq:main_thm_result} shows a balance between the variance of quantization and the mixing matrix. To be more precise, if the variance of quantization $\sigma^2$ is small nodes should assign larger weights to their neighbors which decreases $(1-\beta)^{-2}$ and increases $\|W-W_D\|^2$. Conversely, when the variance $\sigma^2$ is large, to balance the terms in \eqref{eq:main_thm_result} nodes should assign larger weights to their local decision variables which decreases the term $\|W-W_D\|^2$ and increases $(1-\beta)^{-2}$. 

\subsection{Proof of Theorem \ref{thm1}}
To analyze the proposed QDGD method, we start by rewriting the update rule (\ref{eq:alg_update}) as follows

\begin{equation} \label{eq:rule2}
    \bx_{i,t+1} = \bx_{i,t}- \eps \Big( (1-w_{ii}) \bx_{i,t} -\sum_{ j \neq i} w_{ij} \bz_{j,t} + \al \gr f_i(\bx_{i,t}) \Big).
\end{equation}

Note that to derive the expression in \eqref{eq:rule2}, we simply use the fact that $w_{ij}=0$ when $j\notin \mathcal{N}_i$. 

The next step is to write the update \eqref{eq:rule2} in a matrix form. To do so, we define the function $F:\mathbb{R}^{np} \to \mathbb{R}$ as $F(\bx)=\sum_{i=1}^{n} f_i(\bx_{i})$ where $\bx_i \in \mathbb{R}^{p}$ and $\bx = [\bx_1;\cdots;\bx_n] \in \mathbb{R}^{np}$ is the concatenation of the local variables $\bx_i$. It is easy to verify that the gradient of the function $F$ is the concatenation of local gradients evaluated at the local variable, that is $\gr F(\bx_t)=[ \gr f_1(\bx_{1,t});\cdots;\gr f_n(\bx_{n,t})]$. We also define the matrix $\bW = W \otimes I \in \mathbb{R}^{np \times np}$ as the Kronecker product of the weight matrix $W \in \mathbb{R}^{n \times n}$ and the identity matrix $I \in \mathbb{R}^{p \times p}$. Similarly, define $\bW_D = W_D \otimes I \in \mathbb{R}^{np \times np}$, where $W_D=[w_{ii}] \in \mathbb{R}^{n \times n}$ denotes the diagonal matrix of the entries on the main diagonal of $W$. For the sake of consistency, we denote by the boldface $\bI$ the identity matrix of size $np$. According to above definitions, we can write the concatenated version of (\ref{eq:rule2}) as follows,
\begin{equation} \label{eq:rule-matrix}
    \bx_{t+1} = \bx_{t} - \eps \Big(  \big(\bI - \bW_D \big) \bx_t+\big(\bW_{D} - \bW\big) \bz_{t}  + \al \gr F(\bx_{t}) \Big).
\end{equation}


As we discussed in Section \ref{sec:problem}, the distributed consensus optimization Problem (\ref{eq:main}) can be equivalently written as Problem (\ref{eq:main_2}). The constraint in the latter restricts the feasible set to the consensus vectors, that is $\{ \bx=[\bx_1;\cdots;\bx_n] : \bx_1=\cdots=\bx_n \}$. According to the discussion on rank of the weight matrix $W$, the null space of the matrix $I-W$ is $\text{null}(I - W)=\text{span}(\mathbf{1})$. Hence, the null space of $\bI-\bW$ is the set of all consensus vectors, i.e., $\bx \in \mathbb{R}^{np}$ is feasible for Problem (\ref{eq:main_2}) if and only if $(\bI-\bW)\bx=0$, or equivalently $(\bI-\bW)^{1/2}\bx=0$. Therefore, the alternative Problem (\ref{eq:main_2}) can be compactly represented as the following linearly-constrained problem,

\begin{equation}\label{eq:Fmin}
\begin{aligned}
& \underset{ \bx \in \mathbb{R}^{np}}{\text{min}}
& & F(\bx) =  \sum_{i=1}^{n} f_i(\bx_i) \\
& \text{subject to}
& & (\bI-\bW )^{1/2}\bx=0.
\end{aligned}
\end{equation}

We denote by $\bx^* =[\widetilde{\bx}^*;\dots;\widetilde{\bx}^*]$ the unique solution to (\ref{eq:Fmin}).


Now, for given penalty parameter $\al > 0$, one can define the quadratic penalty function corresponding to the linearly constraint problem (\ref{eq:Fmin}) as follows,

\begin{equation} \label{eq:h}
    h_{\al}(\bx)= \frac{1}{2} \bx^\top \big(\bI - \bW \big) \bx + \al  F(\bx).
\end{equation}

Since $\bI - \bW$ is a positive semi-definite  matrix and $F$ is $L$-smooth and $\mu$-strongly convex, the function $h_{\al}$ is $L_{\alpha}$-smooth and $\mu_{\alpha}$-strongly convex on $\mathbb{R}^{np}$ having $L_{\al}= 1-\lambda_n(W) + \al L $ and $\mu_{\al} = \al \mu$. We denote by $\bx^*_{\al}$ the unique minimizer of $h_{\al}(\bx)$, i.e.,

\begin{equation} \label{eq:hmin}
    \bx^*_{\al} = \operatorname*{\text{arg}\,\text{min}}_{\bx \in \mathbb{R}^{np}} h_{\al}(\bx) = \operatorname*{\text{arg}\,\text{min}}_{\bx \in \mathbb{R}^{np}} \frac{1}{2} \bx^\top \big(\bI - \bW \big) \bx + \al  F(\bx).
\end{equation}


In the following, we link the solution of Problem (\ref{eq:hmin}) to the local variable iterations provided by Algorithm \ref{alg:QDC}. Specifically, for sufficiently large number of iterations $T$, we demonstrate that for proper choice of step-sizes, the expected squared deviation of $\bx_{T}$ from $\bx^*_{\al}$ vanishes sub-linearly. This result follows from the fact that the expected value of the descent direction in \eqref{eq:rule-matrix} is an unbiased estimator of the gradient of the function $ h_{\al}(\bx)$. 

 \begin{lemma} \label{lemma1}
 Consider the optimization Problem (\ref{eq:hmin}) and suppose Assumptions \ref{assump1}--\ref{assump4} hold. Then, the expected deviation of the output of QDGD from the solution to Problem (\ref{eq:hmin}) is upper bounded by

 \begin{equation}\label{eq:lemma1}
 \Expc \Big[\norm{\bx_T - \bx^*_{\al}}^2 \Big] \leq \mathcal{O} \left( \frac{c_1 { n} \sigma^2 \norm{W\!-\!W_D}^2}{\mu c_2} \frac{1}{T^{\delta}} \right),
 
\end{equation}

for $\eps=\frac{c_1}{T^{3\delta/2}}$, $\al = \frac{c_2}{T^{\delta/2}}$, any $\delta \in (0,1/2)$ and $T \geq T_1$, where $c_1$ and $c_2$ are positive constants independent of $T$, and 
\begin{equation}
 T_1 \coloneqq \text{max} \left\{  e^{e^{\frac{1}{1-2\delta}}},  \left\lceil \left( c_1 c_2 \mu \right)^{\frac{1}{2\delta}} \right\rceil , \left\lceil \left( \frac{c_1 (2+c_2 L)^2}{c_2 \mu} \right)^{\frac{1}{\delta}} \right\rceil \right\}. 
 \end{equation}
 \end{lemma}
\vspace{0.5mm}
 \begin{proof}
 See Appendix \ref{app_proof_of_lemma_1}.
 \end{proof}


Lemma \ref{lemma1} guarantees convergence of the proposed iterations according to the update in (\ref{eq:alg_update}) to the solution of the later-defined Problem (\ref{eq:hmin}). Loosely speaking, Lemma \ref{lemma1} ensures that $\bx_T$ is \textit{close} to $\bx^*_{\al}$ for large $T$. So, in order to capture the deviation of $\bx_T$ from the global optima $\bx^*$, it suffices to show that $\bx^*_{\al}$ is \textit{close} to $\bx^*$, as well. As the problem in \eqref{eq:hmin} is a penalized version of the original constrained program in \eqref{eq:main}, the solutions to these two problems should not be significantly different if the penalty coefficient $\alpha$ is small. We formalize this claim in the following lemma. 


\begin{lemma}\label{lemma2}
Consider the distributed consensus optimization Problem (\ref{eq:main}) and the problem defined in (\ref{eq:hmin}). If Assumptions \ref{assump1}, \ref{assump2} and \ref{assump4} hold, then the difference between the optimal solutions to \eqref{eq:Fmin} and its penalized version \eqref{eq:hmin} is bounded above by

\begin{equation}  
\norm{\bx^*_{\al} - \bx^*} \leq  \cO \left( \frac{\sqrt{2n} c_2 D \left(3+ 2L/\mu\right)}{ 1-\beta}  \frac{1}{T^{\delta/2}} \right),

\end{equation}

for $\al=\frac{c_2}{T^{\delta/2}}$ and $T\geq T_2$, where $c_2$ is a positive constant independent of $T$, $\delta \in (0,1/2)$ is an arbitrary constant, and 
\begin{equation} 
T_2 \coloneqq \text{max} \left\{ \left\lceil \left(\frac{c_2 L}{1+\lambda_n(W)}\right)^{\frac{2}{\delta}} \right\rceil , \left\lceil c^4_2 (\mu + L)^{\frac{2}{\delta}} \right\rceil  \right\}.
\end{equation}
\end{lemma}
\vspace{0.5mm}
 \begin{proof}
 See Appendix \ref{app_proof_of_lemma_2}.
 \end{proof}

The result in Lemma \ref{lemma2} shows that if we set the penalty coefficient $\alpha$ small enough, i.e., $\al=\mathcal{O}(T^{-\delta/2})$, then the distance between the optimal solutions of the constrained problem in \eqref{eq:main} and the penalized problem in \eqref{eq:hmin} is of $\mathcal{O} \left(\frac{\alpha}{1-\beta} \right) $. 


Having set the main lemmas, now it is straightforward to prove the claim of Theorem \ref{thm1}. For the specified step-sizes $\eps$ and $\al$ and large enough iterations $T \geq T_0 \coloneqq \text{max} \left\{ T_1, T_2 \right\}$, Lemmas \ref{lemma1} and \ref{lemma2} are applicable and we have

\begin{align}\label{eq:result}
    \bE \left[\norm{\bx_{T} - \bx^*}^2\right] &= \bE \left[\norm{\bx_T - \bx^*_{\al} + \bx^*_{\al} - \bx^*}^2\right] \nonumber \\
    &\leq 2 \Expc \left[\norm{\bx_T - \bx^*_{\al}}^2 \right] + 2 \norm{\bx^*_{\al} - \bx^*}^2 \nonumber\\
    &\leq \cO\left(\frac{1}{T^{\delta}} \right) + \cO\left(\frac{1}{T^{\delta}} \right) \nonumber \\
    &= \cO\left(\frac{1}{T^{\delta}} \right),
\end{align}

where we used $\norm{\mathbf{a+b}}^2 \leq 2 \big( \norm{\mathbf{a}}^2 + \norm{\mathbf{b}}^2 \big)$ to derive the first inequality; and the constants can be found in the proofs of the two lemmas. Since $ \bE \Big[\norm{\bx_{i,T} - \widetilde{\bx}^*}^2\Big]\leq  \bE \Big[\norm{\bx_{T} - \bx^*}^2\Big]$ for any $i=1,\dots,n$, the inequality in \eqref{eq:result} implies the claim of Theorem~\ref{thm1}. 

 
 \subsection{Extension to more quantizers}
Based on the condition in Assumption~\ref{assump3}, so far we have been considering only unbiased quantizers for which the variance of quantization is bounded by a constant scalar, i.e., $\bE \left[ \|Q(\bx)-\bx\|^2 | \bx \right]\leq \sigma^2$. However, there are widely used representative quantizers where the quantization noise induced on the input is bounded proportionally to the input's magnitude, i.e., $\bE \left[ \|Q(\bx)-\bx\|^2 | \bx \right]\leq \mathcal{O} \left(\|\bx\|^2\right)$ \cite{alistarh2017qsgd}. 

Indeed, this condition is more challenging since the set of iterates norm $\|\bx_t\|$ are not necessarily bounded, and we cannot uniformly bound the variance of  the noise induced by quantization. In this subsection, we show that the proposed algorithm is converging with the same rate for quantizers satisfying this new assumption. Let us first formally state this assumption.

\begin{assumption}\label{assump5}
The random quantizer $Q(\cdot)$ is unbiased and its variance is proportionally bounded by the input's squared norm, that is,

\begin{equation}
    \bE \left[Q(\bx)| \bx \right]=\bx, \quad \text{ and } \quad \bE \left[ \norm{Q(\bx)-\bx}^2 | \bx \right]\leq \eta^2 \norm{\bx}^2,
\end{equation}

for a constant $\eta^2$ and any $\bx \in \mathbb{R}^{p}$; and quantizations are carried out independently on distributed nodes.
\end{assumption}

Before characterizing the convergence properties of the proposed QDGD method under the conditions in Assumption~\ref{assump5}, let us review a subset of quantizers that satisfy this condition. 


\begin{example}[Low-precision quantizer] \label{ex:lp}
Consider the low precision quantizer $ Q^{\text{LP}}: \mathbb{R}^p \rightarrow \mathbb{R}^p$ which is defined as 
\begin{equation}\label{eq:low_per_def}
    Q^{\text{LP}}_i (\bx) = \norm{\bx} \cdot \text{sign}(x_i) \cdot \xi_i(\bx,s),
\end{equation}
where $ \xi_i(\bx,s) $ is a random variable defined as
\begin{equation}\label{eq:low_per_def_2}
    \xi_i(\bx,s) =
\left\{
	\begin{array}{ll}
	\frac{l}{ s}  &\quad \mbox{w.p.} \ \ 1- q\left(\frac{|x_i|}{\norm{\bx}},s\right), \vspace{2mm} \\ 
		\frac{l+1}{s} & \quad \mbox{w.p.} \ \ q\left(\frac{|x_i|}{\norm{\bx}},s\right), 
	\end{array}
\right.
\end{equation}
and $q(a,s)=as-l$ for any $a  \in [0,1]$. In above, the tuning parameter $s$ corresponds to the number of quantization levels and $l \in [0,s)$ is an integer such that $|x_i|/\norm{\bx} \in [l/s, (l+1)/s]$. It is not hard to check that \cite{alistarh2017qsgd}  the low precision quantizer $Q^{\text{LP}}$ defined in \eqref{eq:low_per_def} is an unbiased estimator of the vector $\bx$ and the variance is bounded above by

\begin{equation}\label{eq:low_prec_var}
    \mathbb{E} \left[\norm{ Q^{\text{LP}}(\bx) - \bx }^2  \right] \leq \text{min} \left( \frac{p}{s^2} , \frac{\sqrt{p}}{s} \right) \norm{\bx}^2.
\end{equation}

The bound in \eqref{eq:low_prec_var} illustrates the trade-off between communication cost and quantization variance. Choosing a large $s$ reduces the variance of quantization at the cost of increasing the levels of quantization and therefore increasing the communication cost. 
\end{example}

The following example provides another quantizer which satisfies the conditions in Assumption~\ref{assump5}.


\begin{example}[Gradient sparsifier]
The gradient sparsifier denoted by $ Q^{\text{GS}}: \mathbb{R}^p \rightarrow \mathbb{R}^p$ is defined as 
\begin{equation}
    Q^{\text{GS}}_i (\bx) =
\left\{
	\begin{array}{ll}
		x_i / q_i  & \mbox{w.p. } q_i, \\
		0 & \mbox{otherwise},
	\end{array}
\right.
\end{equation}
where $q_i$ is probability that coordinate $i \in [p]$ is selected. It is easy to verify that this quantizer is unbiased, as for each $i$, $\mathbb{E} \left[Q^{\text{GS}}_i (\bx) \right] = x_i$. Moreover, one can show that the variance of this quantizer is bounded as follows,
\begin{equation}
    \mathbb{E} \left[ \norm{ Q^{\text{GS}}(\bx) - \bx }^2 \right] = \sum_{i=1}^{p} \left( \frac{1}{q_i} - 1\right) x_i^2 \leq \left( \frac{1}{q_\text{min}} - 1\right) \norm{\bx}^2,
\end{equation}
where $q_\text{min}$ denotes the minimum of probabilities $\{q_1,\cdots,q_p\}$. 
\end{example} 


In the following theorem, we extend our result in Theorem~\ref{thm1} to the case that variance of quantizer may not be uniformly bounded and is proportional to the squared norm of quantizer's input.

\begin{theorem}\label{thm2}
Consider the distributed consensus optimization Problem (\ref{eq:main}) and suppose Assumptions \ref{assump1}, \ref{assump2}, \ref{assump4}, \ref{assump5} hold. Then, for each node $i$, the expected squared difference between the output of the QDGD method outlined in Algorithm \ref{alg:QDC} and the optimal solution  of Problem (\ref{eq:main}), i.e. $\widetilde{\bx}^*$ is upper bounded by

\begin{align}\label{thm_2_claim}
\bE \Big[\norm{\bx_{i,T} - \widetilde{\bx}^*}^2\Big] &\leq \mathcal{O} \Bigg( \Bigg(  \frac{4n c^2_2 D^2 \left(3+ 2L/\mu\right)^2 }{(1-\beta)^2} \nonumber\\
 &\quad   \quad   + \frac{4 c_1 {  n}\widetilde{B}^2 \eta^2 \norm{W-W_D}^2}{\mu c_2} \Bigg)\frac{1}{T^{\delta}} \Bigg),
\end{align}

for $\eps=\frac{c_1}{T^{3\delta/2}}$, $\al = \frac{c_2}{T^{\delta/2}}$, any $\delta \in (0,1/2)$ and $T \geq \widetilde{T}_0$, where $c_1$, $c_2$ and $\widetilde{T}_0$ are positive constants independent of $T$, and

\begin{align}
    \widetilde{B}^2 = \frac{4 c^2_2 D^2 \left(3+ 2L/\mu\right)^2 }{(1-\beta)^2} + \frac{4(f_0 - f^*)}{\mu}. 
\end{align}

\end{theorem}


\begin{proof}
See Appendix \ref{app_proof_of_theorem_2}.
\end{proof}


The result in Theorem~\ref{thm2} shows that under Assumption~\ref{assump5}, the proposed QDGD method converges to the optimal solution at a sublinear rate of $ \cO \left( {T^{-\delta}} \right)$ which matches the result in Theorem~\ref{thm1}. However, the lower bound on the total number of iterations $ \widetilde{T}_0$ for the result in Theorem~\ref{thm2} is in general larger than  $ {T}_0$ for the result in Theorem~\ref{thm1}. The exact expression of $ \widetilde{T}_0$ could be found in Appendix \ref{app_proof_of_theorem_2}.

 

\iffalse
 \begin{lemma}
 For fixed $\al$, if we pick $\eps_t=\frac{2}{\mu_{\al}t}$, it holds for every $t \geq t_0 \coloneqq \lceil 2(\frac{L_{\al}}{\mu_{\al}})^2\rceil$ that 
 \begin{equation}\label{eq:lemma1}
 \Expc \Big[\norm{\bx_t - \bx^*_{\al}}^2 \Big] \leq \frac{1}{t} \max \bigg\{ \frac{4 \sigma^2 }{\mu^2_{\al}}\norm{I-W}^2_F , t_0 \Expc \Big[\norm{\bx_{t_0} - \bx^*_{\al}}^2 \Big] \bigg\},
\end{equation}
where $\norm{\cdot}_F$ denotes the Frobenius matrix norm.
 \end{lemma}
\begin{proof}
According to the update rule (\ref{eq:rule-matrix}), we can write for $t\geq 1$
\begin{align}
 \bE \Big[\norm{\bx_{t+1} - \bx^*_{\al}}^2 | \cF^t\Big] &= \bE \Big[\norm{\bx_{t} - \eps_t \widetilde{\gr}h_{\al}(\bx_t) - \bx^*_{\al}}^2 | \cF^t\Big]\\
 &= \norm{\bx_{t} - \bx^*_{\al}}^2 -2 \eps_t \langle \bx_{t} - \bx^*_{\al}, \bE[\widetilde{\gr}h_{\al}(\bx_t)| \cF^t] \rangle + \eps^2_t \bE \Big[\norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\Big]\\
 &= \norm{\bx_{t} - \bx^*_{\al}}^2 -2 \eps_t \langle \bx_{t} - \bx^*_{\al}, {\gr}h_{\al}(\bx_t) \rangle + \eps^2_t \norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\Big]\\
 &\leq (1-2 \mu_{\al} \eps_t)\norm{\bx_{t} - \bx^*_{\al}}^2 + \eps^2_t \bE \Big[\norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\Big] \label{eq:bound1}
\end{align}
Next, we bound the second term in (\ref{eq:bound1}),
\begin{align}
\bE \Big[\norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 \vert \cF^t\Big] &= \bE \Big[\norm{(\bI - \bW) \bz_t + \al \gr F(\bx_t)}^2 \vert \cF^t\Big] \\
&\leq \norm{{\gr}h_{\al}(\bx_t)}^2 + \sigma^2 \norm{I-W}^2_F\\
&\leq L^2_{\al} \norm{\bx_{t} - \bx^*_{\al}}^2 + \sigma^2 \norm{I-W}^2_F \label{eq:bound2}
\end{align}
Plugging (\ref{eq:bound2}) into (\ref{eq:bound1}) yields
\begin{align}
 \bE \Big[\norm{\bx_{t+1} - \bx^*_{\al}}^2 | \cF^t\Big]
 &\leq (1-2 \mu_{\al} \eps_t + \eps^2_t L^2_{\al})\norm{\bx_{t} - \bx^*_{\al}}^2 + \eps^2_t \sigma^2 \norm{I-W}^2_F. \label{eq:bound3}
\end{align}
Let us denote $e_t = \bE \Big[\norm{\bx_{t} - \bx^*_{\al}}^2 \Big]$ for $t \geq 1$. By taking expectation over history $\cF^t$ from (\ref{eq:bound3}), we have
\begin{align}\label{eq:bound4}
 e_{t+1} &\leq  (1-2 \mu_{\al} \eps_t + \eps^2_t L^2_{\al})e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F\\
 &= (1-\eps_t(2 \mu_{\al}  - \eps_t L^2_{\al}))e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F.
\end{align}
Notice that for the specified pick of $\eps_t$, for $t\geq t_0$ we have 
\begin{align}
\eps_t = \frac{2}{\mu_{\al}t} \leq \frac{2}{\mu_{\al}t_0} = \frac{2}{\mu_{\al}{\lceil 2(\frac{L_{\al}}{\mu_{\al}})^2\rceil}} \leq \frac{2}{\mu_{\al}{2(\frac{L_{\al}}{\mu_{\al}})^2}} = \frac{\mu_{\al}}{L^2_{\al}}.
\end{align}
Therefore, (\ref{eq:bound4}) can be written as
\begin{align}
 e_{t+1} &\leq  (1-\eps_t(2 \mu_{\al}  - \eps_t L^2_{\al}))e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F\\
 &\leq (1- \mu_{\al} \eps_t )e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F.
\end{align}
Now, we proceed to prove the claim (\ref{eq:lemma1}) by induction on $t$. Let $M=\max \bigg\{ \frac{4 \sigma^2 }{\mu^2_{\al}}\norm{I-W}^2_F , t_0^{1/3} \Expc \Big[\norm{\bx_{t_0} - \bx^*_{\al}}^2 \Big] \bigg\}$ denote the maximum term in (\ref{eq:lemma1}). As the base of the induction for $t=t_0$, we clearly have $e_{t_0}=\Expc \Big[\norm{\bx_{t_0} - \bx^*_{\al}}^2 \Big] \leq \frac{M}{t_0}$. Assume (\ref{eq:lemma1}) holds for some $t\leq t_0$, i.e. $e_t \leq \frac{M}{t}$. We can write
\begin{align}
\eps_t = \frac{2}{\mu_{\al}t} \leq \frac{2}{\mu_{\al}t_0} = \frac{2}{\mu_{\al}{\lceil 2(\frac{L_{\al}}{\mu_{\al}})^2\rceil}} \leq \frac{2}{\mu_{\al}{2(\frac{L_{\al}}{\mu_{\al}})^2}} = \frac{\mu_{\al}}{L^2_{\al}}.
\end{align}
Therefore, (\ref{eq:bound4}) can be written as
\begin{align}
e_{t+1} &\leq  (1- \mu_{\al} \eps_t )e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F\\
&= (1-\frac{2}{t}) e_t + \frac{4 \sigma^2 }{\mu^2_{\al} t^2}\norm{I-W}^2_F\\
&\leq (1-\frac{2}{t}) \frac{M}{t} + \frac{M}{t^2}\\
&= (\frac{1}{t}-\frac{1}{t^2})M\\
&\leq \frac{M}{t+1},
\end{align}
concluding the claim.
\end{proof}


\begin{lemma}
Consider the sequence of iterates $e_t$ satisfying the inequality 
\begin{equation}\label{eq:recursive_expression}
    e_{t+1}\leq \left(1-\frac{a}{T}\right) e_t +\frac{b}{T^{4/3}},
\end{equation}
where $a$ and $b$ are positive constants, and $T$ is the total number of iterations. Then, after $T$ iterations the iterate $e_T$ satisfies 

\begin{equation}
    e_T \leq \mathcal{O}\left(\frac{1}{T^{1/3}}\right)
\end{equation}

\end{lemma}

\begin{proof}
Use the expression in \eqref{eq:recursive_expression} for steps $t-1$ and $t$ obtain

\begin{align}
    e_{t+1} 
    & \leq \left(1-\frac{a}{T}\right)^2 e_{t-1} +\left(1-\frac{a}{T}\right) \frac{b}{T^{4/3}} +\frac{b}{T^{4/3}}\nonumber\\
    & =  \left(1-\frac{a}{T}\right)^2 e_{t-1} +\left[1+\left(1-\frac{a}{T}\right) \right]\frac{b}{T^{4/3}}
\end{align}

By recursively applying these inequalities for all steps $t\geq 0$ we obtain that  

\begin{align}
    e_{t} 
     &\leq  \left(1-\frac{a}{T}\right)^t e_{0} 
     +\frac{b}{T^{4/3}} \left[1+\left(1-\frac{a}{T}\right) +\dots +\left(1-\frac{a}{T}\right)^{t-1} \right] \nonumber\\
     &\leq  \left(1-\frac{a}{T}\right)^t e_{0} 
     +\frac{b}{T^{4/3}} \left[\sum_{s=0}^{t-1}\left(1-\frac{a}{T}\right)^{s} \right] \nonumber\\
     &\leq  \left(1-\frac{a}{T}\right)^t e_{0} 
     +\frac{b}{T^{4/3}} \left[\sum_{s=0}^{\infty}\left(1-\frac{a}{T}\right)^{s} \right] \nonumber\\
     &=  \left(1-\frac{a}{T}\right)^t e_{0} 
     +\frac{b}{T^{4/3}} \left[\frac{1}{1-(1-\frac{a}{T})} \right] \nonumber\\
     &=  \left(1-\frac{a}{T}\right)^t e_{0} 
     +\frac{b}{aT^{1/3}}  \nonumber\\
\end{align}

Therefore, for the iterate corresponding to step $t=T$ we can write 

\begin{align}
    e_{T} 
     &\leq 
      \left(1-\frac{a}{T}\right)^T e_{0} 
     +\frac{b}{aT^{1/3}}  \nonumber\\
     &\leq 
      (e^{-a}) e_{0} 
     +\frac{b}{aT^{1/3}}  \nonumber\\
\end{align}

\end{proof}


\begin{lemma}
 For $\eps=\frac{2}{\mu t^{2/3}}$ and $\al = \frac{1}{t^{1/3}}$, it holds for every $t \geq t_0 \coloneqq \Big\lceil 8 \Big( \frac{1+L}{\mu} \Big)^6 \Big\rceil$ that
 \begin{equation}\label{eq:lemma1}
 \Expc \Big[\norm{\bx_t - \bx^*_{\al}}^2 \Big] \leq \frac{1}{t^{1/3}} \max \bigg\{ \frac{4 \sigma^2 }{\mu^2_{f}}\norm{I-W}^2_F , t_0^{1/3} \Expc \Big[\norm{\bx_{t_0} - \bx^*_{\al}}^2 \Big] \bigg\},
\end{equation}
where $\norm{\cdot}_F$ denotes the Frobenius matrix norm.
 \end{lemma}
\begin{proof}
According to the update rule (\ref{eq:rule-matrix}), we can write for $t\geq 1$
\begin{align}
 \bE \Big[\norm{\bx_{t+1} - \bx^*_{\al}}^2 | \cF^t\Big] &= \bE \Big[\norm{\bx_{t} - \eps_t \widetilde{\gr}h_{\al}(\bx_t) - \bx^*_{\al}}^2 | \cF^t\Big]\\
 &= \norm{\bx_{t} - \bx^*_{\al}}^2 -2 \eps_t \langle \bx_{t} - \bx^*_{\al}, \bE[\widetilde{\gr}h_{\al}(\bx_t)| \cF^t] \rangle + \eps^2_t \bE \Big[\norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\Big]\\
 &= \norm{\bx_{t} - \bx^*_{\al}}^2 -2 \eps_t \langle \bx_{t} - \bx^*_{\al}, {\gr}h_{\al}(\bx_t) \rangle + \eps^2_t \norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\Big]\\
 &\leq (1-2 \mu_{\al} \eps_t)\norm{\bx_{t} - \bx^*_{\al}}^2 + \eps^2_t \bE \Big[\norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 | \cF^t\Big] \label{eq:bound1}
\end{align}
Next, we bound the second term in (\ref{eq:bound1}),
\begin{align}
\bE \Big[\norm{\widetilde{\gr}h_{\al}(\bx_t)}^2 \vert \cF^t\Big] &= \bE \Big[\norm{(\bI - \bW) \bz_t + \al \gr F(\bx_t)}^2 \vert \cF^t\Big] \\
&\leq \norm{{\gr}h_{\al}(\bx_t)}^2 + \sigma^2 \norm{I-W}^2_F\\
&\leq L^2_{\al} \norm{\bx_{t} - \bx^*_{\al}}^2 + \sigma^2 \norm{I-W}^2_F \label{eq:bound2}
\end{align}
Plugging (\ref{eq:bound2}) into (\ref{eq:bound1}) yields
\begin{align}
 \bE \Big[\norm{\bx_{t+1} - \bx^*_{\al}}^2 | \cF^t\Big]
 &\leq (1-2 \mu_{\al} \eps_t + \eps^2_t L^2_{\al})\norm{\bx_{t} - \bx^*_{\al}}^2 + \eps^2_t \sigma^2 \norm{I-W}^2_F. \label{eq:bound3}
\end{align}
Let us denote $e_t = \bE \Big[\norm{\bx_{t} - \bx^*_{\al}}^2 \Big]$ for $t \geq 1$. By taking expectation over history $\cF^t$ from (\ref{eq:bound3}), we have
\begin{align}\label{eq:bound4}
 e_{t+1} &\leq  (1-2 \mu_{\al} \eps_t + \eps^2_t L^2_{\al})e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F\\
 &= (1-\eps_t(2 \mu_{\al}  - \eps_t L^2_{\al}))e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F.
\end{align}
Notice that for the specified pick of $\eps_t$, for $t\geq t_0$ we have $t^{1/3} \geq t_0^{1/3} \geq  2  \Big( \frac{1+L}{\mu} \Big)^2 $. Therefore, we can write 

\begin{align}
\eps_t &= \frac{2}{\mu t^{2/3}}\\
&\leq \frac{\mu}{(1+L)^2}\cdot \frac{1}{t^{1/3}}\\
&\leq \frac{\mu_{\al}}{ (1-\lambda_n(W) + \al L)^2 }\\
&\leq \frac{\mu_{\al}}{L^2_{\al}}
\end{align}
Therefore, (\ref{eq:bound4}) can be written as
\begin{align}\label{eq:bound5}
 e_{t+1} &\leq  (1-\eps_t(2 \mu_{\al}  - \eps_t L^2_{\al}))e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F\\
 &\leq (1- \mu_{\al} \eps_t )e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F.
\end{align}
Now, we proceed to prove the claim (\ref{eq:lemma1}) by induction on $t$. Let 
\begin{equation}
    M = \max \bigg\{ \frac{4 \sigma^2 }{\mu^2_{f}}\norm{I-W}^2_F , t_0^{1/3} \Expc \Big[\norm{\bx_{t_0} - \bx^*_{\al}}^2 \Big] \bigg\}
\end{equation}
denote the maximum term in (\ref{eq:lemma1}). As the base of the induction for $t=t_0$, we clearly have $e_{t_0}=\Expc \Big[\norm{\bx_{t_0} - \bx^*_{\al}}^2 \Big] \leq \frac{M}{t_0^{1/3}}$. Assume (\ref{eq:lemma1}) holds for some $t\geq t_0$, i.e. $e_t \leq \frac{M}{t^{1/3}}$. We can write
Therefore, (\ref{eq:bound5}) can be written as
\begin{align}
e_{t+1} &\leq  (1- \mu_{\al} \eps_t )e_t + \eps^2_t \sigma^2 \norm{I-W}^2_F\\
&= (1-\frac{2}{t}) e_t + \frac{4 \sigma^2 }{\mu^2_{f} t^{4/3}}\norm{I-W}^2_F\\
&\leq (1-\frac{2}{t}) \frac{M}{t^{1/3}} + \frac{M}{t^{4/3}}\\
&= \Big(\frac{1}{t^{1/3}} -\frac{1}{t^{4/3}}\Big)M\\
&\leq \frac{M}{(t+1)^{1/3}},
\end{align}
concluding the claim.
\end{proof}

\fi
{"config": "arxiv", "file": "1806.11536/4-convergence.tex"}