---
abstract: 'We consider coordinate descent (CD) methods with exact line search on convex quadratic problems. Our main focus is to study the performance of the CD method that use random permutations in each epoch and compare it to the performance of the CD methods that use deterministic orders and random sampling with replacement. We focus on a class of convex quadratic problems with a diagonally dominant Hessian matrix, for which we show that using random permutations instead of random with-replacement sampling improves the performance of the CD method in the worst-case. Furthermore, we prove that as the Hessian matrix becomes more diagonally dominant, the performance improvement attained by using random permutations increases. We also show that for this problem class, using any fixed deterministic order yields a superior performance than using random permutations. We present detailed theoretical analyses with respect to three different convergence criteria that are used in the literature and support our theoretical results with numerical experiments.'
author:
- |
    Mert Gürbüzbalaban[^1], Asuman Ozdaglar[^2],\
    Nuri Denizcan Vanli[^3] and Stephen J. Wright[^4]
bibliography:
- 'rpcd.bib'
- 'nips\_ref.bib'
title: Randomness and Permutations in Coordinate Descent Methods
---

Introduction {#sec:main}
============

We consider coordinate descent (CD) methods for solving unconstrained optimization problems of the form $$\label{eq:f}
    \min_{x \in \R^n} \, f(x),$$ where $f:\R^n \to \R$ is smooth and convex. CD methods have a long history in optimization [@luo1992convergence; @bertsekas1989parallel; @ortega2000iterative] and have been used in many applications [@PassCode15; @NesterovCD17; @richtarik2016parallel; @qin2013efficient; @scutari14]. They have seen a resurgence of recent interest because of their scalability and desirable empirical performance in machine learning and large-scale data analysis [@Bertsekas15Book; @Shi16Survey; @Wright2015].

CD methods are iterative algorithms that perform (approximate) global minimizations with respect to a single coordinate (or several coordinates in the case of block CD) at each iteration. Specifically, at iteration $k$, an index $i_k \in \{1,2,\dots,n\}$ is chosen and the decision variable is updated to approximately minimize the objective function in the $i_k$-th coordinate direction (or at least to produce a significant decrease in the objective) [@Bertsekas99nonlinear; @Bertsekas15Book]. The steps of this method are summarized in Algorithm \[alg:cd\], where $e_i = [0,\dots,0,1,0,\dots,0]^T$ is the $i$-th standard basis vector (with the $i$-th entry equal to one). At each iteration $k$, $i_k$-th coordinate of $x$ is selected and a step is taken along the negative gradient direction in this coordinate. The counter $k=\ell n+j$ keeps track of the total number of iterations consisting of outer iterations indexed by $\ell$ and inner iterations indexed by the counter $j$. Each outer iteration is called a “cycle" or an “epoch” of the algorithm.

Choose initial point $x^0 \in \R^n$ Set $k=\ell  n+j$ Choose index $i_k=i(\ell,j) \in \{1,2,\dotsc,n\}$ Choose stepsize $\alpha_k>0$ $x^{k+1} \leftarrow x^k - \alpha_k [\nabla f(x^k)]_{i_k} e_{i_k}$, where $[\nabla f(x^k)]_{i_k} = e_{i_k}^T \nabla f(x^k)$

CD methods use various schemes, both deterministic and stochastic, for choosing the coordinate $i_k$ to be updated at iteration $k$. Prominent schemes include the following.

-   Cyclic CD (CCD): The index $i(\ell,j)$ is chosen in a cyclic fashion over the elements in the set $\{1,2,\dots,n\}$ satisfying $i(\ell,j)=j+1$.

-   Cyclic CD with a given order $\pi$ (CCD-$\pi$): A permutation $\pi$ of the set $\{1,2,\dots,n\}$ is selected. Then, the index $i(\ell,j)$ is chosen as the $(j+1)$-th element of $\pi$ for every epoch $\ell$. (CCD corresponds to the special case of $\pi=(1,2,\dots,n)$.)

-   Randomized CD (RCD): The index $i(\ell,j)$ is chosen randomly with replacement from the set $\{1,2,\dotsc,n\}$ with uniform probabilities (each index has the same probability of being chosen). This method is also known as the *stochastic CD* method.

-   Random Permutations Cyclic CD (RPCD): At the beginning of each epoch $\ell$, a permutation of $\{1,2,\dotsc,n\}$ is chosen, denoted by $\pi_{\ell}$, uniformly at random over all permutations. Then, the index $i(\ell,j)$ is chosen as the $(j+1)$-th element of $\pi_{\ell}$. Each permutation $\pi_{\ell}$ is independent of the permutations used at all previous and later epochs. This approach amounts to sampling indices from the set $\{1,2,\dotsc,n\}$ without replacement for each epoch.

While our focus in this paper will be on CD methods with the aforementioned selection rules, we note that several other variants of CD methods have been studied in the literature, including the Gauss-Southwell rule [@nutini2015coordinate], in which $i_k$ is selected in a greedy fashion to maximize $[\nabla f(x^k)]_i$, and versions of RCD [@nesterov2012efficiency], in which $i_k$ is selected from a non-uniform distribution that may depend on the component-wise Lipschitz constants of $f$.

We are interested in the relative convergence behavior of these different variants of CD. While there have been some recent works that study and compare performances of CCD and RCD (for example, [@nesterov2012efficiency; @WangLinCCD; @TewariSIAM; @beck2013convergence; @sun2015improved; @sun2016worst; @ccd_vs_rcd]); with the exception of a few recent papers (which focus on special quadratic problems, see [@wrightRPCD15; @wrightRPCD17]), there is limited understanding of the effects of random permutations in CD methods.

In this paper, we study convergence rate properties of RPCD for a special class of quadratic optimization problems with a diagonally dominant Hessian matrix, and compare its performance to that of RCD and CCD. Interest in RPCD is motivated by both empirical observations and practical implementation: In many machine learning applications, RPCD is observed numerically to outperform its with-replacement sampling counterpart RCD [@Needell2014a; @Recht2012]. Moreover, without-replacement sampling-based algorithms (such as RPCD and random reshuffling [@mert_RandomReshuffling; @Bertsekas15]) are often easier to implement efficiently than their with-replacement counterparts (such as RCD and stochastic gradient descent) [@Recht2012; @wrightRPCD15] as it requires sequential data access, in contrast to the random data access required by with-replacement sampling (see e.g. [@shamir2016without; @Bottou2012]).

We start by surveying briefly the existing results on the effects of random permutations for CD methods [@sun2016worst; @wrightRPCD15; @wrightRPCD17; @oswald2017random]. Among these, Oswald and Zhou [@oswald2017random] studies the effects of random permutations on the convergence rate of the successive over-relaxation (SOR) method (that is used to solve linear systems) and presents a convergence rate on the expected function value of the iterates generated by the SOR method. The CD method, when applied to quadratic minimization problems, is equivalent to the SOR method (applied to the linear system that represents the first-order optimality condition of the quadratic problem) when the relaxation parameter is chosen as $\omega=1$. Therefore, the convergence rate results in [@oswald2017random] readily extend for RPCD, when applied to quadratic problems. Sun and Ye [@sun2016worst] construct a quadratic problem, for which CCD requires $\bigO(n^2)$ times more iterations compared to RCD in order to achieve an $\epsilon$-optimal solution (that is, a point $x^k$ that satisfies $\E f(x^k) - f(x^*) \leq \epsilon$). For this problem, they also show that the distance of the iterates (to the optimal solution) for CCD decays $\bigO(n^2)$ times slower than the distance of the expected iterates for RPCD and RCD. Lee and Wright [@wrightRPCD15] consider the same problem and present that the expected function values of RPCD and RCD decay with similar rates, while the asymptotic convergence rate of RPCD is shown to be slightly better than for RCD. In a following paper [@wrightRPCD17], the results in [@wrightRPCD15] are generalized to a larger class of quadratic problems through a more elaborate analysis.

Our main results provide convergence rate comparisons with respect to various criteria between RPCD, RCD, and CCD for a class of strongly convex quadratic optimization problems with a diagonally dominant Hessian matrix. In particular, we first provide an exact worst-case convergence rate comparison between RPCD, RCD, and CCD in terms of the distance of the expected iterates to the optimal solution, as a function of a parameter that represents the extent of diagonal dominance of the Hessian matrix. Our results show that, on this problem, CCD is always faster than RPCD, which in turn is always faster than RCD. Furthermore, we show that the relative convergence rate of RPCD to RCD goes to infinity as the Hessian matrix becomes more diagonally dominant. On the other extreme, as the Hessian matrix becomes less diagonally dominant, the ratio of convergence rates converges to a value in $[3/2, \, e-1)$, with the upper bound $e-1$ achieved in the limit as $n \to \infty$. Our second set of results compares the convergence rates of RPCD and RCD with respect to two other criteria that are widely used in the literature: the expected distance of the iterates to the solution and the expected function values of the iterates. For these criteria, we show that RPCD is faster than RCD in terms of the tightest upper bounds we obtain, and the amount of improvement increases as the matrices become more diagonally dominant.

The organization of the paper is as follows. In Section \[sec:prelim\], we discuss the CCD, RCD, and RPCD algorithms in more detail and describe the three criteria that are used for analyzing convergence throughout the paper. In Section \[sec:prior\], we survey known results on the convergence rate of RPCD. We analyze the convergence rates of CCD, RCD, and RPCD with respect to the first convergence criterion in Section \[ssec:lyapunov1\] and the behavior of RCD and RPCD with respect to the second and third convergence criteria in Section \[ssec:lyapunov2and3\]. We validate our theoretical results via numerical experiments in Section \[sec:experiments\] and present conclusions in Section \[sec:conclusion\].

Preliminaries {#sec:prelim}
=============

To study performance of different CD methods, we focus on the special case of problem when $f$ is a strongly convex quadratic function:[^5] $$f(x) = \frac12 x^TAx, \label{eq:obj1}$$ where $A$ is a positive definite matrix. We denote its extreme eigenvalues by \[def-muL\] := \_(A) &gt;0, L := \_(A), and note that $\mu$ is the modulus of convexity for $f$, while $L$ is the Lipschitz constant for $\nabla f$. The problem has a unique solution $x^*= 0$ with optimal value $f(\xs)=0$.

In the remainder of this section, we derive explicit formulas for the iterates of different variants of CD applied to (in terms of matrix operators representing each epoch) and then introduce different convergence criteria for these variants. We show how asymptotic convergence rates can be characterized in terms of the spectral properties of $A$ and the matrix operators for each epoch.

CD Methods
----------

In this section, we describe the variants of the CD method (in particular, CCD, CCD-$\pi$, RCD, and RPCD) when applied to the quadratic problem in . The CD method (cf. Algorithm \[alg:cd\]) with exact line search has the following update rule at each iteration $$\label{eq:cd-exact}
    x^{k+1} = x^k - \frac{1}{A_{i_k i_k}} (Ax^k)_{i_k} e_{i_k},$$ where the update coordinate $i_k$ is determined according to one of the schemes mentioned above.

For the CCD algorithm, each coordinate is processed in a round-robin fashion using the standard cyclic order $(1,2,\dots,n)$. Denoting by $D$ the diagonal part of $A$ and by $-N$ the strictly lower triangular part of $A$, that is, $$A = D - N - N^T, \nonumber$$ the evolution of the iterates over an epoch (of $n$ consecutive iterations) can be written as $$\xc^{(\ell+1)n} = \ccd \, \xc^{\ell n}, \quad \mbox{with} \quad \ccd = (D-N)^{-1}N^T, \label{eq:ccd}$$ where $\ell$ denotes the epoch counter. Note that the update rule in is equivalent to one iteration of the Gauss-Seidel method applied to the first-order optimality condition of , which is the linear system $Ax=0$ [@Wright2015].

For the CCD-$\pi$ algorithm, we let $P_\pi$ denote the permutation matrix corresponding to order $\pi$ and split the permuted Hessian matrix as follows: $$\label{eq:split}
    A_\pi = P_\pi^T A P_\pi = D_\pi - N_\pi  - N_\pi^T,$$ where $-N_\pi$ is a strictly lower triangular matrix and $D_\pi$ is a diagonal matrix. Then, similar to , we have $$\xcpi^{(\ell+1)n} = \ccdpi \, \xcpi^{\ell n}, \quad \mbox{with} \quad \ccdpi = (D_\pi-N_\pi)^{-1}N_\pi^T. \label{eq:ccd-pi}$$ Note that $\ccd$ and $\ccdpi$ are not symmetric matrices as the first column of both matrices are zero, whereas the first row contains nonzero entries.

For the RCD algorithm, the indices $i_k$ are chosen independently at random at each iteration $k$. Denoting by $\xr^k$ the $k$-th iterate generated by RCD, the update rule for RCD over a single iteration can be written as $$\xr^{k+1} = \rcd \, \xr^k, \quad \mbox{with} \quad \rcd = I - \frac{1}{A_{i_k i_k}} e_{i_k} e_{i_k}^T A. \label{eq:rcd-definition}$$ The expectation of $\rcd$ with respect to the random variable $i_k$ is denoted as follows: $$\label{eq:Brcd}
\rcdE = \E_k \rcd,$$ where we note that $\rcdE$ is a symmetric matrix, by symmetry of $A$ and uniform distribution of $i_k$.

For the RPCD algorithm, each coordinate is processed exactly once in each epoch according to a uniformly and independently chosen order. Recalling that $\pi_\ell$ denotes the permutation of coordinates used in epoch $\ell$ and using the iteration matrix corresponding to CCD-$\pi_\ell$ (see ), epoch $\ell$ of RPCD can be written as $$\xp^{(\ell+1)n} = \rpcd \, \xp^{\ell n}, \quad \mbox{with} \quad \rpcd = P_{\pi_\ell}  \ccdpiell P_{\pi_\ell}^T. \label{eq:rpcd}$$ We introduce the following notation for the expected value of $\rpcd$ with respect to permutation $\pi_\ell$: $$\label{eq:Brpcd}
\rpcdE = \E_{\ell} \rpcd,$$ where we note that $\rpcdE$ is a symmetric matrix since $\pi_\ell$ is chosen uniformly at random over all permutations (see Lemma \[lem:wright\_lemma\]).

Convergence Rate Criteria {#ssec:rate_criteria}
-------------------------

We next discuss how to measure and compare the convergence rates of different variants of CD. Three different improvement sequences have been used to measure the performance of CD methods in the literature: $$\begin{aligned}
    & (i)   & \Ly_1(x_\text{CD}^k) & = \norm{\E x_\text{CD}^k-\xs}, & \text{(Distance of expected iterates)} \\
    & (ii)  & \Ly_2(x_\text{CD}^k) & = \E\norm{x_\text{CD}^k-\xs}^2, & \text{(Expected distance of iterates)} \\
    & (iii) & \Ly_3(x_\text{CD}^k) & = \E f(x_\text{CD}^k) - f(\xs). & \text{(Expected function value)} \end{aligned}$$ (see e.g. [@sun2015improved; @sun2016worst; @ccd_vs_rcd; @richtarik2016parallel; @Wright2015; @nesterov2012efficiency; @beck2013convergence]). While these three measures can be related to each other (Jensen’s inequality yields $\Ly_1^2 \leq \Ly_2$ and strong convexity enables lower and upper bounding $\Ly_3$ between constant positive multiples of $\Ly_2$), we will provide different analyses for each of the measures to obtain the tightest estimates.

In the above definitions, expectations can be removed for deterministic algorithms such as CCD. By Jensen’s inequality, we have that $\Ly_1^2(x_\text{CD}^k) \le \Ly_2(x_\text{CD}^k)$ for all $k$. For a strongly convex function $f$, $\Ly_3$ can be lower and upper bounded between constant positive multiples of $\Ly_2$.

To study convergence rate of CCD, RCD, and RPCD with respect to improvement sequence $\Ly_1$, we use the operators derived in the previous section that represent one iterate or one epoch. For CCD and RPCD, we have from and together with that $$\E_\ell x_\text{CD}^{(\ell+1) n} = \cd \, x_\text{CD}^{\ell n},$$ where $\E_\ell$ denotes the expectation with respect to the random variables in epoch $\ell$ given $x_\text{CD}^{\ell n}$. (We have $\cd=\ccd$ for CCD and $\cd=\rpcdE$ for RPCD.) Note that the random variables in each epoch are independent and identically distributed across different epochs for RCD and RPCD. Therefore, by using the law of iterated expectations, we obtain $$\E x_\text{CD}^{(\ell+1) n} = \cd^\ell \, x^0,$$ where $\E$ here denotes the expectation with respect to [*all*]{} random variables arising in the algorithm. Hence, the [*worst-case convergence rate*]{} with respect to $\Ly_1$ can be expressed as $$\sup_{x^0\in\R^n} \left( \frac{\norm{\E x_\text{CD}^{\ell n}}}{\norm{x^0}} \right)^{1/\ell} = \sup_{x^0\in\R^n} \left( \frac{\norm{\cd^\ell \, x^0}}{\norm{x^0}} \right)^{1/\ell} = \norm{\cd^\ell}^{1/\ell}. \label{eq:rmk1}$$ When $\cd$ is a symmetric matrix (as in RPCD), we have $\norm{\cd^\ell}^{1/\ell} = \rho(\cd)$. Hence, yields a [*per-epoch*]{} worst-case convergence rate of $\rho(\rpcdE)$ for RPCD. When $\cd$ is asymmetric (which is the case for CCD), we have by Gelfand’s formula $\lim_{\ell\to\infty}\norm{\cd^\ell}^{1/\ell} = \rho(\cd)$. Thus, $\rho(\ccd)$ represents an [*asymptotic*]{} worst-case convergence rate measure for CCD.

For RCD, a similar derivation involving a single iteration (rather than one epoch) yields from and that $$\E_k x_\text{RCD}^{k+1} = \rcdE \, x_\text{CCD}^k.$$ Similar reasoning to the above yields a [*per-iteration*]{} worst-case convergence rate of $\rho(\rcdE)$, or equivalently a per-epoch rate of $\rho(\rcdE)^n$, for RCD. (Note that, because $\rcdE$ is symmetric, we have $\rho(\rcdE) = \norm{\rcdE}$.)

In our analysis of convergence rate of RCD with respect to improvement sequence $\Ly_2$, it follows from that $$\begin{aligned}
    \E \norm{x_\text{RCD}^{k+1}}^2 & = (x_\text{RCD}^k)^T \E \left[ (\rcd)^T \rcd \right] x_\text{RCD}^k \\
        & \leq \norm{\E \left[ (\rcd)^T \rcd \right]} \norm{x_\text{RCD}^k}^2.\end{aligned}$$ For RPCD, we have similarly from that $$\begin{aligned}
    \E \norm{x_\text{RPCD}^{(\ell+1)n}}^2 & = (x_\text{RPCD}^{\ell n})^T \E \left[ (\rpcd)^T \rpcd \right] x_\text{RPCD}^{\ell n} \\
        & \leq \norm{\E \left[ (\rpcd)^T \rpcd \right]} \norm{x_\text{RPCD}^{\ell n}}^2.\end{aligned}$$ The matrices $\E \left[ (\rcd)^T \rcd \right]$ and $\E \left[ (\rpcd)^T \rpcd \right]$ are both symmetric. Convergence rates be obtained from $\rho \left( \E \left[ (\rcd)^T \rcd \right] \right)$ and $\rho \left( \E \left[ (\rpcd)^T \rpcd \right] \right)$ (or equivalently from the norms of these matrices), the first being a per-iteration convergence rate for RCD under criterion $\Ly_2$, and the second being a per-epoch rate for RPCD under the same criterion. Results along these lines appear in Section \[ssec:lyapunov2and3\].

Finally, in our analysis of convergence rate of RCD with respect to $\Ly_3$, iteration yields $$\begin{aligned}
    \E f(x_\text{RCD}^{k+1}) & = (x_\text{RCD}^k)^T \E_k \left[ (\rcd)^T A \rcd \right] x_\text{RCD}^k \\
        & = (A^{1/2} x_\text{RCD}^k)^T \E_k \left[ A^{-1/2} (\rcd)^T A \rcd A^{-1/2} \right] A^{1/2} x_\text{RCD}^k \\
        & \leq \norm{\E_k \left[ A^{-1/2} (\rcd)^T A \rcd A^{-1/2} \right]} \norm{A^{1/2} x_\text{RCD}^k}^2.\end{aligned}$$ A similar analysis applied to the RPCD update formula yields $$\E f(x_\text{RPCD}^{(\ell+1)n})  \leq \norm{\E_{\ell} \left[ A^{-1/2} (\rpcd)^T A \rpcd A^{-1/2} \right]} \norm{A^{1/2} x_\text{RPCD}^{\ell n}}^2.$$ We will show that the matrices in these two bounds are symmetric. Thus, our convergence rate characterizations for RCD and RPCD with respect to $\Ly_3$ (see Section \[ssec:lyapunov2and3\]) will involve the norms (equivalently, the spectral radii) of these two matrices.

Note that for improvement sequence $\Ly_1$, the asymptotic worst-case convergence rate of the algorithm can be simply computed as the spectral radius of the expected iteration matrix. Furthermore, this bound is tight in the sense that there can be no smaller contraction rate $c_1$, for which an inequality of the type $\Ly_1(x_\text{CD}^{\ell n}) \leq c_1^\ell \, \Ly_1(x^0)$ asymptotically holds for all $x^0\in\R^n$. Therefore, in Section \[ssec:lyapunov1\], we compare the worst-case convergence rates of CCD, RCD and RPCD with respect to $\Ly_1$ through a tight analysis (in Proposition \[thm:ccd\]). We analyze the ratio of the convergence rates of RCD and RPCD in Proposition \[thm-monotonic-rpcd-speedup\]. On the other hand, for improvement sequences $\Ly_2$ and $\Ly_3$, we consider per-iteration and per-epoch upper bounds that are not necessarily asymptotically tight. Using a similar argument to , we can formulate the worst-case contraction factors for $\Ly_2$ and $\Ly_3$, but they would involve computation of powers of matrices (e.g., $\E \left[ (\cdk^\ell)^T \cdk^\ell \right]$ and $\E \left[ A^{-1/2} (\cdk^\ell)^T A \cdk^\ell A^{-1/2} \right]$), which does not admit a closed form characterization. Hence, in Section \[ssec:lyapunov2and3\], we compare the convergence rates of RCD and RPCD based on per-iteration and per-epoch improvement rates, as has been done previously in the literature [@sun2016worst; @wrightRPCD15; @wrightRPCD17].

Prior work on CD methods with random permutations {#sec:prior}
=================================================

In this section, we survey the known results on the performance of RPCD. There are several recent works that study the effects of random permutations in the convergence behavior of CD methods [@oswald2017random; @wrightRPCD15; @wrightRPCD17; @sun2016worst]. To unify the randomization parameters (in RCD and RPCD) and the component-wise Lipschitz constants in different papers, we (without loss of generality) make the following assumption throughout the rest of the paper $$\label{eq:unit-diag}
    A_{ii} = 1, \quad \mbox{for all} \quad i\in\{1,2,\dots,n\}.$$ This can always be satisfied by scaling the optimization variable, i.e., by setting $x = D^{-1/2}\tilde{x}$ in and minimizing over $\tilde{x} \in \R^n$ (see e.g. [@wrightRPCD17; @ccd_vs_rcd]).

Recently, Oswald and Zhou [@oswald2017random] analyzed the effects of random permutations for the successive over-relaxation (SOR) method, which is equivalent to the CD method with exact line search for a particular choice of algorithm parameter. They consider quadratic problems whose Hessian matrix is positive semidefinite and present convergence guarantees for SOR iterations with random permutations, which implies the following guarantee on the performance of RPCD.

\[theo-oswald\][@oswald2017random Theorem 4] Let $f$ be a quadratic function of the form , where the Hessian matrix $A$ has unit diagonals. Then, for any solution $x^*$, the RPCD algorithm enjoys the following guarantee $$\label{eq:oswald_rpcd}
    \E f(\xp^{\ell n}) - f(x^*) \leq  \left (1 - \frac{\mu}{(1+L)^2}\right)^{\ell} \left(f(x^0) - f(x^*)\right).$$

Theorem \[theo-oswald\] provides a convergence rate guarantee on the performance of RPCD for general quadratic functions. Under the same assumptions in Theorem \[theo-oswald\], the best known upper bound on the performance of RCD is given by [@nesterov2012efficiency Theorem 5]: $$\E \left[ \frac{1}{2} \norm{\xr^k-\xs}^2 + f(\xr^k) - f(x^*) \right] \leq\left( 1- \frac{2 \mu}{n(1+\mu)} \right)^k \left( \frac{1}{2} \norm{x^0-\xs}^2 + f(x^0) - f(x^*) \right). \label{eq:rcd.rate.R}$$ This shows that the the upper bound on the performance of RCD per-epoch is approximately $\left( 1-\frac{2\mu}{n(1+\mu)} \right)^n \approx 1-\frac{2\mu}{1+\mu}$, whereas it follows from that the upper bound on the performance of RPCD can be as large as $1-\frac{\mu}{(1+n)^2}$ since $L \leq \tr{A} = n$. These bounds suggest that RPCD may require $\bigO(n^2)$ times more iterations than RCD to guarantee an $\epsilon$-optimal solution. However, empirical results show that RPCD often outperforms RCD in machine learning applications [@Recht2012; @Bottou2009]. Furthermore, it has been conjectured that the expected performance of RPCD should be no worse than the expected performance of RCD [@Recht2012] (see also [@Ward16AMGM; @Zhang14AMGM] for related work on this conjecture). This motivates to derive tight bounds for the convergence rate of RPCD and compare them with the known bounds on the convergence rate of RCD.

A similar phenomenon has been observed for CCD in comparison to RCD. In particular, the tightest known convergence rate results on the performance of CCD (see [@beck2013convergence; @sun2016worst; @sun2015improved]) suggest that CCD may require $\bigOt(n^2)$ times more iterations than RCD to guarantee an $\epsilon$-optimal solution. To understand this gap in the convergence rate bounds, Sun and Ye [@sun2016worst] focused on the quadratic problem in with the following permutation invariant[^6] Hessian matrix $$\label{eq:Ainvariant}
    A = \ddd I + (1-\ddd) \bfone \bfone^T, \quad \mbox{where} \quad \delta \in (0,n/(n-1)).$$ In particular, the authors considered a worst-case initialization and the case when $\delta$ is close to $0$, for which $L=\bigO(n)$.[^7] For this problem, they showed that CCD with the worst-case initialization indeed requires $\bigO(n^2)$ times more iterations than RCD to return an $\epsilon$-optimal solution. They also provided rate comparisons between RPCD and CCD without providing a comparison between RPCD and RCD, which is presented in the following theorem.

\[prop: slower, iterates\] [@sun2016worst Proposition 3.4] Let $K_{\mathrm{CCD}}(\epsilon)$, $K_{\mathrm{RCD}}(\epsilon) $ and $K_{\mathrm{RPCD}}(\epsilon)$ be the minimum number of epochs for CCD, RCD and RPCD (respectively) to achieve (expected) relative error $$\frac{  \| \E(x_{\text{CD}}^k) - x^* \| }{ \|x^0 - x^* \| } \leq \epsilon,$$ for initial point $x^0\in\R^n$ (for CCD, the expectation operator can be ignored). There exists a quadratic problem, whose Hessian matrix $A$ satisfies for some $\delta$ around zero, such that

\[ite, compare CD with others\] $$\begin{aligned}
    %  \frac{ K_{\mathrm{CCD} }(\epsilon ) }{ K_{\mathrm{GD} }(\epsilon ) }     &   \geq \frac{n}{2 \pi^2 } \approx \frac{n}{20},   \label{compare GD with CD, coro}  \\
      \frac{ K_{\mathrm{CCD} }(\epsilon ) }{ K_{\mathrm{RCD} }(\epsilon ) }    &   \geq \frac{n^2 }{ 2 \pi^2 } \approx \frac{n^2}{20}, \label{compare CD with RCD, coro} \\
      \frac{ K_{\mathrm{CCD} }(\epsilon ) }{ K_{\mathrm{RPCD} }(\epsilon ) }   &   \geq \frac{n (n+1) }{ 2 \pi^2 } \approx \frac{n(n+2)}{20}.
 \end{aligned}$$

Theorem \[prop: slower, iterates\] shows that the worst-case performance (in improvement sequence $\Ly_1$) of RPCD and RCD is $\bigO(n^2)$ times faster than that of CCD. In a follow-up work, Lee and Wright [@wrightRPCD15] considered the same problem as [@sun2016worst] (see ) for the small $\delta$ case and presented asymptotic and non-asymptotic analyses of RPCD with respect to improvement sequence $\Ly_3$, presented in the following theorem.

\[thm-rpcd-ima\][@wrightRPCD15 Theorem 3.3] Consider the quadratic problem with the Hessian matrix $A$ given by , where $\delta\in(0, 0.4)$ and $n \geq 10$. For any $x^0\in\R^n$, RPCD has the following non-asymptotic convergence guarantee $$\E f(\xp^{\ell n}) - f(\xs) \leq (1-2\delta+4\delta^2)^\ell R_0,$$ where $R_0$ is a constant depending on $x_0$ and $\delta$. Furthermore, RPCD iterates enjoy an asymptotic convergence rate of $$\lim_{\ell\to\infty} \left( \E f(\xp^{\ell n}) - f(\xs) \right)^{1/\ell}  = 1-2\ddd - \frac{2\ddd}{n} + 2\ddd^2 + \bigO\left(\frac{\ddd^2}{n}\right) + \bigO(\ddd^3).$$

Theorem \[thm-rpcd-ima\] shows that for the particular class of quadratic problems whose Hessian matrix satisfies , the convergence rate (in improvement sequence $\Ly_3$) of RPCD is faster than that of RCD in in terms of the best known upper bounds. This is the first theoretical evidence that supports the empirical results showing RPCD often outperforms RCD [@Recht2012]. In a follow-up work [@wrightRPCD17], Lee and Wright generalize the results of Theorem \[thm-rpcd-ima\] to quadratic problems, whose Hessian matrix satisfies $$\label{eq:Ainvariant-generalized}
    A = \ddd I + (1-\ddd) u u^T, \quad \mbox{where} \quad \ddd \in (0,n/(n-1)),$$ where $u\in\R^n$ is a vector with elements of size $\bigO(1)$ (this generalizes that corresponds to $u=\bfone$). The conclusions are similar to [@wrightRPCD15], but the analysis is different because $A$ is no longer a permutation-invariant matrix.

Performance of RPCD vs RCD on a class of diagonally dominant matrices {#sec:4}
=====================================================================

As described in the previous section, the existing works [@sun2016worst; @wrightRPCD15] analyze the performance of RPCD for quadratic problems, whose Hessian satisfies for small $\delta$. Here, we consider the other extreme, i.e., the $\delta>1$ case, and provide tight convergence rate comparisons between RPCD, RCD and CCD with respect to all there improvement sequences defined in Section \[ssec:rate\_criteria\]. In deriving convergence rate guarantees, we do not resort to the tools that are used in the earlier works on RPCD [@sun2016worst; @wrightRPCD15; @wrightRPCD17]. Instead, we present a novel analysis based on Perron-Frobenius theory that enables us to compute convergence rate bounds for all three criteria. For notational simplicity, we introduce the reformulation $\alpha=\delta-1$, which yields $$\label{def-An}
    A = (1+\alpha)I - \alpha \ones \ones^T, \quad \mbox{where} \quad \alpha \in (0,1/(n-1)).$$ It is simple to check that $A$ has one eigenvalue at $1-(n-1)\alpha$ with the corresponding eigenvector $\ones$ and other $n-1$ eigenvalues equal to $1+\alpha$. In particular, as $\alpha$ goes to zero, the condition number of $A$ gets smaller and in the limit $A$ is the identity matrix. On the other hand, as $\alpha\to \frac{1}{n-1}$, the matrix gets ill-conditioned. Therefore, the parameter t:=\_i = (n-1) (0,1) \[eq:t-definition\] is a measure of diagonal dominance. In the remainder of this section, we analyze the performance of RPCD, RCD and CCD in improvement sequence $\Ly_1$ and the performance of RPCD and RCD in improvement sequences $\Ly_2$ and $\Ly_3$ with respect to this diagonal dominance measure.

Convergence rates of RPCD, RCD and CCD in improvement sequence $\Ly_1$ {#ssec:lyapunov1}
----------------------------------------------------------------------

In this section, we compare convergence rates of RPCD, RCD and CCD, where improvement sequence $\Ly_1(x^k) = \norm{\E x^k -\xs}$ is chosen as the convergence criterion (as in Theorem \[prop: slower, iterates\]). As we highlighted in Section \[ssec:rate\_criteria\], we first compute the expected iteration matrices of the RPCD and RCD algorithms, and show that they are symmetric. Then, we compute their spectral radii to conclude the per-epoch worst-case convergence rate of RPCD and RCD, and analyze their ratio in Proposition \[thm-monotonic-rpcd-speedup\]. We also show that the asymptotic worst-case convergence rate of CCD is faster than that of RPCD and RCD in Proposition \[thm:ccd\].

We begin our discussion by writing the expected RPCD iterates (see and ) as follows $$\label{eq:CCDEqualsCCDpi}
    \E_\ell \xp^{(\ell+1)n} = \rpcdE \, \xp^{\ell n}.$$ Note that since the Hessian matrix $A$ is permutation invariant, the iteration matrix of the CCD-$\pi$ algorithm for any cyclic order $\pi$ is equal to the iteration matrix of the standart CCD algorithm, i.e., $\ccd=\ccdpi$ for all orders $\pi$. Therefore, we have $\rpcdE = \E_\pi [P_\pi \ccd P_\pi^T] = \E_P [P \ccd P^T]$, where we drop the subscript $\pi$ from the matrices for notational simplicity. In order to obtain a formula for $\rpcdE$, we first reformulate the CCD iteration matrix in as follows $$\ccd = (I-N)^{-1}N^T = I - (I-N)^{-1}(I-N-N^T) =   I - \Gamma^{-1} A,$$ where $\Gamma = I-N$. Using this reformulation, the expected iteration matrix of RPCD can computed as follows $$\rpcdE = \E_P \left[ P \ccd P^T \right] =  \E_P \left[ P(I - \Gamma^{-1} A)P^T \right] = I - \E_P \left[ P\Gamma^{-1}P^T \right] A,$$ where we used the fact that $PP^T = I$ and $AP^T = P^TA$. For the case the Hessian matrix $A$ satisfies , $\Gamma^{-1}$ can be explicitly computed as $$\begin{aligned}
 \label{eqn-gamma-inv}
    \Gamma^{-1} = \mbox{toeplitz} (c,r),\end{aligned}$$ where $\mbox{toeplitz} (c,r)$ denotes the Toeplitz matrix with the first column $c$ and the first row $r$, which are given by $$\begin{aligned}
        c = \begin{bmatrix} 1, & \alpha, & \alpha(1+\alpha), & \alpha(1+\alpha)^2, & \dots, & \alpha(1+\alpha)^{n-2}  \end{bmatrix}^T,  \quad
        r = [1, 0 , 0, \dots, 0].\end{aligned}$$ In order to compute $\E_P \left[ P\Gamma^{-1}P^T \right]$, we use the following lemma, which states that expectation over all permutations separately averages the diagonal and off-diagonal entries of the permuted matrix.

[@wrightRPCD15 Lemma 3.1]\[lem:wright\_lemma\] Given any matrix $Q \in \R^{n\times n}$ and permutation matrix $P$ selected uniformly at random from the set of all permutations, we have $$\E_P[P Q P^T] = \tau_1 I + \tau_2 \bfone\bfone^T,$$ where $$\label{eq:wright-lemma}
\tau_2 = \frac{\bfone^T Q \bfone - \trace(Q)}{n(n-1)} \quad \mbox{and} \quad \tau_1 = \frac{\trace (Q)}{n} - \tau_2.$$

Letting $Q=\Gamma^{-1}$ in Lemma \[lem:wright\_lemma\], we observe that the matrix $\E_P [P\Gamma^{-1}P^T]$ has diagonals equal to one and all the off-diagonal entries equal to each other: $$\label{eq:expected-gamma-inverse-matrix}
    \E_P [P\Gamma^{-1}P^T] = (1-\gamma) I + \gamma \bfone\bfone^T,$$ where $\gamma$ can be found as the average of the off-diagonal entries of $\Gamma^{-1}$. The following lemma (whose proof is given in Appendix \[app:lemm-gamma-proof\]) provides an explicit expression for $\gamma$.

\[lemm-gamma\] For any $\alpha \in (0,1/(n-1))$, we have $$\gamma = \frac{(1+\alpha)^n - \alpha n - 1}{\alpha n(n-1)},$$ where $\gamma$ denotes the off-diagonal entries of $\E_P [P\Gamma^{-1}P^T]$ in .

Using Lemma \[lemm-gamma\], it follows from the definition of $A$ in and equation that $$\rpcdE = I - \E_P [P\Gamma^{-1}P^T] A = ((n-1)\gamma-\beta) I + \beta \bfone\bfone^T,$$ where = - + (n-2). Since $\rpcdE$ is a symmetric matrix, then by , it suffices to compute the spectral radius of $\rpcdE$ to obtain the worst-case performance of RPCD with respect to improvement sequence $\Ly_1$. To this end, we note that for any $\alpha \in (0,1/(n-1))$, $\rpcdE >0$ since $\rpcdE = \E_P [P \ccd P^T]$ and $\ccd\geq0$ with at least one strictly positive entry in both the diagonal and off-diagonal parts (see also for an explicit formula of $\ccd$). Then, by the Perron-Frobenius Theorem [@varga2009matrix Lemma 2.8], we have $$\begin{aligned}
    \rho(\rpcdE) & = \sum_{j=1}^n [\rpcdE]_{ij}, \quad \mbox{for all $i\in[n]$} \\
        & = (n-1) (\gamma \alpha + \beta) \\
        & = (n-1) (\alpha - \gamma + \alpha \gamma (n-1)) \\
        & = 1 - \left[\left(1-\alpha(n-1)\right) \left(1+\gamma(n-1)\right)\right].\end{aligned}$$ Substituting the formula for $\gamma$ from Lemma \[lemm-gamma\] above, we obtain the spectral radius of the RPCD iteration matrix as follows $$\label{eq-rho-RPCD}
    \rho(\rpcdE) = 1 - \left(1-\alpha(n-1)\right) \frac{(1+\alpha)^n  - 1}{\alpha n} = 1 - \frac{1-t}{n} \left( \frac{\left(1+\frac{t}{n-1}\right)^n  - 1}{\frac{t}{n-1}} \right),$$ where $t=\alpha(n-1)$ denotes the diagonal dominance factor (as defined in ).

For the RCD algorithm, on the other hand, we have (by and ) the following expected iterates $$\E_k \xr^{k+1} = \rcdE \, \xr^k, \quad \mbox{where} \quad \rcdE = I-\frac{1}{n}A.$$ Since $A$ is a symmetric matrix, then by , the per-epoch worst-case asymptotic rate of RCD with respect to improvement sequence $\Ly_1$ can be found as $$\rho(\rcdE)^n = \left(1-\frac{1}{n}\lambda_{\min}(A)\right)^n =  \left( 1-\frac{1-t}{n} \right)^n.$$ In Proposition \[thm-monotonic-rpcd-speedup\], we compare the performance of RPCD and RCD with respect to improvement sequence $\Ly_1$. To this end, we define $$s(t,n) = \frac{-\log \rho (\rpcdE)}{-\log \rho(\rcdE)^n}, \label{eq:s-definition}$$ (where $\log$ denotes the natural logarithm), which is equal to the ratio between the number of epochs required to guarantee $\norm{\E x^{\ell n}-\xs}\leq\epsilon$ for RCD and RPCD algorithms. In particular $s(t,n)>1$ implies RPCD has a faster worst-case convergence rate than RCD. In the following theorem, we show that RPCD is faster than RCD for any $t\in(0,1)$ and $n\geq2$, and quantify the rate of improvement.

\[thm-monotonic-rpcd-speedup\] The following statements are true:

-   The function $s(t,n)$ is strictly decreasing in $t$ over $(0,1)$.

-   $\lim_{t\to 0}s(t,n) = \infty.$

-   Let $g(n):= \lim_{t\to 1} s(t,n)$. We have $g(n) \in [3/2,e-1)$, for any $n\geq 2$. Furthermore, $g(n)$ is strictly increasing in $n\geq2$ satisfying $$g(2)=3/2 \quad \mbox{and} \quad \lim_{n\to\infty} g(n) = e-1.$$

![Plot of $s(t,n)$ and $\tilde{s}(t,n)$ versus $t\in(0,1)$ for different values of $n$.[]{data-label="fig:s"}](s.eps){width="\textwidth"}

![Plot of $s(t,n)$ and $\tilde{s}(t,n)$ versus $t\in(0,1)$ for different values of $n$.[]{data-label="fig:s"}](s_tilde.eps){width="\textwidth"}

A consequence of Proposition \[thm-monotonic-rpcd-speedup\] is that RPCD is faster than RCD in the worst-case, for every $t \in (0,1)$ by a factor $s(t,n) > 1$. Furthermore, the amount of acceleration $s(t,n)$ goes to infinity as $\alpha\to0$ for any $n$ fixed. This shows that as the matrix $A$ becomes more and more well-conditioned (as $\alpha \to 0$), the amount of speed-up $s(t,n)$ we obtain with RPCD with respect to RCD goes to infinity. This is consistent with the observation that cyclic orders work well for diagonal-like matrices that are well-conditioned (see e.g. [@varga2009matrix]). Proposition \[thm-monotonic-rpcd-speedup\] is illustrated in Figure \[fig:s\] (left panel), where we plot the parameter $s(t,n)$ as a function of $t$ for different values of $n$.

We next compare the convergence rate of CCD with respect to RPCD and RCD. To this end, as we discuss in Section \[ssec:rate\_criteria\] (cf. ), we use $\rho(\ccd)$ as the asymptotic per epoch worst-case convergence rate of CCD, whereas for comparison to RCD, we use a per-epoch rate of $\rho(\rcdE)^n$. Note that as discussed in , $\ccd=\ccdpi$ for all $\pi$, and hence $\rho(\ccd)=\rho(\ccdpi)$ for all $\pi$. Although, explicit calculation of $\rho(\ccd)$ appears to be challenging, we prove that the known upper bounds [@ccd_vs_rcd Theorem 4.12] on $\rho(\ccd)$ is tighter than $\rho(\rpcdE)$, which together with Proposition \[thm-monotonic-rpcd-speedup\] imply the following result.

\[thm:ccd\] Let $f$ be a quadratic function of the form , whose Hessian matrix given by . Then, the expected iteration matrices of CCD, RPCD and RCD satisfy $$\rho(\ccd) < \rho(\rpcdE) < \rho(\rcdE)^n,$$ for any $\alpha\in(0,1/(n-1))$ and $n\geq2$.

Convergence rates of RPCD and RCD in improvement sequences $\Ly_2$ & $\Ly_3$ {#ssec:lyapunov2and3}
----------------------------------------------------------------------------

In this section, we compare the rate of RPCD and RCD with respect to improvement sequences $\Ly_2$ and $\Ly_3$. When the Hessian matrix $A$ satisfies , the smallest eigenvalue of $A$ can be found as follows $$\label{eq:mu-definition}
    \mu = 1-t = 1-\alpha (n-1).$$ Plugging this value in the convergence guarantee of RCD in , we can obtain a convergence guarantee on both improvement sequences $\Ly_2$ and $\Ly_3$ as the left hand-side of upper bounds both $2\Ly_2$ and $\Ly_3$. However, for the particular problem class we consider in this paper, we derive a tighter convergence rate guarantee for RCD in the next proposition, whose proof is deferred to Appendix \[app:rcd-bound\].

\[lemma-rcd-upper bound\] Let $f$ be a quadratic function of the form , whose Hessian matrix given by . Then, RCD iterations satisfy $$\E \|\xr^{k} - x^*\|^2 \leq \left(1-\frac{2\mu}{n} + \frac{\mu^2}{n} \right)^{k} \|x^0 - x^*\|^2, \label{eq:upper bound-rcd norm square}$$ and $$\E \left( f(\xr^{k}) - f(x^*) \right) \leq \left(1-\frac{\mu}{n} \right)^{k} \left( f(x^0) - f(x^*) \right). \label{eq:upper bound-rcd subopt}$$

![Tightness of the bounds in Proposition \[lemma-rcd-upper bound\] when $n=1000$ and $\alpha=\frac{0.9}{n-1}$: Left figure for and right figure for .](lem2_norm_tightness.eps){width="\textwidth"}

![Tightness of the bounds in Proposition \[lemma-rcd-upper bound\] when $n=1000$ and $\alpha=\frac{0.9}{n-1}$: Left figure for and right figure for .](lem2_f_tightness.eps){width="\textwidth"}

We observe that the upper bound in is smaller (tighter) than the upper bound in for any $\alpha \in (0,1/(n-1))$ because $$1-\frac{2\mu}{n} + \frac{\mu^2}{n} < 1-\frac{2\mu}{n} + \frac{2\mu^2}{n} = 1-\frac{2\mu(1-\mu)}{n} = 1-\frac{2\mu(1-\mu^2)}{n(1+\mu)} < 1 - \frac{2\mu}{n(1+\mu)},$$ where the inequalities are due to the fact that $\mu = 1-\alpha (n-1) \in (0,1)$.

We next analyze the performance of RPCD in the following proposition and show that the convergence rate guarantee of RPCD is tighter than the convergence rate guarantee of RCD in Proposition \[lemma-rcd-upper bound\]. The proof of Proposition \[theo-subopt-rpcd\] is given in Appendix \[app:pot6\].

\[theo-subopt-rpcd\] Let $f$ be a quadratic function of the form , whose Hessian matrix given by . Then, RPCD iterations satisfy $$\label{eq:upper bound-rpcd norm square}
    \E \|\xp^{\ell n} - x^*\|^2 \leq \left( 1 - \frac{2\mu}{n} \left( \frac{(1+\alpha)^n - 1}{\alpha} \right) +  \frac{\mu^2}{n} \left( \frac{(1+\alpha)^{2n} - 1}{\alpha(\alpha+2)}\right) \right)^\ell \, \|x^0 - x^*\|^2,$$ and $$\label{eq:rpcd-f-upper-bound}
    \E f(\xp^{\ell n}) - f(x^*) \leq \left( 1- \frac{\mu}{n} \left( \frac{(1+\alpha)^{2n}-1}{\alpha(\alpha+2)} \right) \right)^\ell \left( f(x^0) - f(x^*) \right).$$

![Tightness of the bounds in Proposition \[theo-subopt-rpcd\] when $n=1000$ and $\alpha=\frac{0.9}{n-1}$: Left figure for and right figure for .](thm5_norm_tightness.eps){width="\textwidth"}

![Tightness of the bounds in Proposition \[theo-subopt-rpcd\] when $n=1000$ and $\alpha=\frac{0.9}{n-1}$: Left figure for and right figure for .](thm5_f_tightness.eps){width="\textwidth"}

We next compare the convergence rates we derive for the RCD and RPCD algorithms. In particular, we consider the convergence rate of both algorithms in improvement sequence $\Ly_2$ since we obtain tighter upper bounds for it. Comparing the convergence rate bounds for RCD and RPCD in and , respectively, we can observe that RPCD is faster (in terms of the best known rate guarantees) than RCD by a factor of $$\tilde{s}(t,n) := \frac{-\log\left( 1 - \frac{2\mu}{n} \left( \frac{(1+\alpha)^n - 1}{\alpha} \right) +  \frac{\mu^2}{n} \left( \frac{(1+\alpha)^{2n} - 1}{\alpha(\alpha+2)}\right) \right)}{-n\log\left( 1- \frac{2\mu}{n} + \frac{\mu^2}{n} \right)},$$ which is plotted in Figure \[fig:s\] (right panel) in the interval $t\in(0,1)$ for different values of $n$. We observe from this figure that the convergence rate bound for RPCD is better than than the one for RCD for all $t\in(0,1)$ and $n\geq2$. Furthermore, the difference in convergence rate bounds increases as $t$ gets smaller, i.e., as the Hessian matrix becomes more diagonally dominant. We can also show that $\tilde{s}(t,n)$ behaves similar to $s(t,n)$ as $t\to 1$, where the limiting values can be found in Proposition \[thm-monotonic-rpcd-speedup\].

Numerical Experiments {#sec:experiments}
=====================

Here we compare the performance of CCD, RPCD, and RCD for the quadratic problem with Hessian matrix . In Figure \[fig:worst\], we use a worst-case initialization $x^0=\bfone$, for $n\in\{1000,10000\}$ and $\alpha \in\left\{ \frac{0.01}{n-1},\frac{0.50}{n-1},\frac{0.99}{n-1} \right\}$. We observe that CCD is the faster than RPCD, which is faster than RCD. This behavior is in accordance with the theoretical results in Propositions \[thm:ccd\]-\[theo-subopt-rpcd\]. Furthermore, as $\alpha$ decreases, we can see that the ratio between the convergence rates of RPCD and RCD increases, consistent with Proposition \[thm-monotonic-rpcd-speedup\] (see also Figure \[fig:s\]). We can also observe from the right column in Figure \[fig:worst\] that when $\alpha$ is close to $1/(n-1)$, the ratio between the convergence rates of RPCD and RCD is close to the theoretical limits obtained in Proposition \[thm-monotonic-rpcd-speedup\] (see part [*(iii)*]{}, which shows that the ratio is in the interval $[3/2,\,e-1)$). Figure \[fig:random\] plots similar results to Figure \[fig:worst\], but for a random initialization rather than worst-case initialization. Convergence rates depicted in Figure \[fig:random\] are similar to those of Figure \[fig:worst\], due to the fact that $x^{\ell n}$ becomes colinear with the vector of ones as $\ell$ increases (as $\bfone$ is the leading eigenvector of the expected iteration matrix), so that the worst-case convergence rate dictates the performance of the algorithms.

![CCD vs RPCD vs RCD with worst-case initialization for $n=1000$ (top row) and $n=10000$ (bottom row): $\alpha=\frac{0.01}{n-1}$ in the left column, $\alpha=\frac{0.50}{n-1}$ in the middle column, and $\alpha=\frac{0.99}{n-1}$ in the right column.[]{data-label="fig:worst"}](worst-n1k-a01.eps){width="\textwidth"}

![CCD vs RPCD vs RCD with worst-case initialization for $n=1000$ (top row) and $n=10000$ (bottom row): $\alpha=\frac{0.01}{n-1}$ in the left column, $\alpha=\frac{0.50}{n-1}$ in the middle column, and $\alpha=\frac{0.99}{n-1}$ in the right column.[]{data-label="fig:worst"}](worst-n1k-a50.eps){width="\textwidth"}

![CCD vs RPCD vs RCD with worst-case initialization for $n=1000$ (top row) and $n=10000$ (bottom row): $\alpha=\frac{0.01}{n-1}$ in the left column, $\alpha=\frac{0.50}{n-1}$ in the middle column, and $\alpha=\frac{0.99}{n-1}$ in the right column.[]{data-label="fig:worst"}](worst-n1k-a99.eps){width="\textwidth"}

![CCD vs RPCD vs RCD with worst-case initialization for $n=1000$ (top row) and $n=10000$ (bottom row): $\alpha=\frac{0.01}{n-1}$ in the left column, $\alpha=\frac{0.50}{n-1}$ in the middle column, and $\alpha=\frac{0.99}{n-1}$ in the right column.[]{data-label="fig:worst"}](worst-n10k-a01.eps){width="\textwidth"}

![CCD vs RPCD vs RCD with worst-case initialization for $n=1000$ (top row) and $n=10000$ (bottom row): $\alpha=\frac{0.01}{n-1}$ in the left column, $\alpha=\frac{0.50}{n-1}$ in the middle column, and $\alpha=\frac{0.99}{n-1}$ in the right column.[]{data-label="fig:worst"}](worst-n10k-a50.eps){width="\textwidth"}

![CCD vs RPCD vs RCD with worst-case initialization for $n=1000$ (top row) and $n=10000$ (bottom row): $\alpha=\frac{0.01}{n-1}$ in the left column, $\alpha=\frac{0.50}{n-1}$ in the middle column, and $\alpha=\frac{0.99}{n-1}$ in the right column.[]{data-label="fig:worst"}](worst-n10k-a99.eps){width="\textwidth"}

![CCD vs RPCD vs RCD with random initialization for $n=1000$: $\alpha=\frac{0.01}{n-1}$ (left figure), $\alpha=\frac{0.50}{n-1}$ (middle figure), and $\alpha=\frac{0.99}{n-1}$ (right figure).[]{data-label="fig:random"}](random-n1k-a01.eps){width="\textwidth"}

![CCD vs RPCD vs RCD with random initialization for $n=1000$: $\alpha=\frac{0.01}{n-1}$ (left figure), $\alpha=\frac{0.50}{n-1}$ (middle figure), and $\alpha=\frac{0.99}{n-1}$ (right figure).[]{data-label="fig:random"}](random-n1k-a50.eps){width="\textwidth"}

![CCD vs RPCD vs RCD with random initialization for $n=1000$: $\alpha=\frac{0.01}{n-1}$ (left figure), $\alpha=\frac{0.50}{n-1}$ (middle figure), and $\alpha=\frac{0.99}{n-1}$ (right figure).[]{data-label="fig:random"}](random-n1k-a99.eps){width="\textwidth"}

Conclusion {#sec:conclusion}
==========

In this paper, we surveyed the known results on the performance of RPCD for special cases of strongly convex quadratic objectives and add to these results by presenting a class of convex quadratic problems with diagonally dominant Hessians. Using the distance of the expected iterates to the optimal solution as the convergence criterion, we compared the ratio between the performances of RPCD and RCD with respect to a parameter that represents the extent of diagonal dominance. We illustrated that as the Hessian matrix becomes more diagonally dominant, this ratio goes to infinity, whereas as it gets smaller it goes to a constant in the interval $[3/2, \, e-1)$. We also showed that CCD outperforms both RPCD and RCD for this class of problems. When expected distance of the iterates or expected function value of the iterates is used as the convergence criterion, we presented that the worst-case convergence rate bounds derived for RPCD are tighter compared to the ones for RCD. This is in accordance with our first set of results, i.e., when distance of the expected iterates is used as the convergence criterion. Computational experiments validate our theoretical results, which fill a gap between the theoretical guarantees for RPCD and its empirical performance.

[^1]: Department of Management Science and Information Systems, Rutgers University, 100 Rockafellar Road, Piscataway, NJ 08854. `mg1366@rutgers.edu`.

[^2]: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139. `asuman@mit.edu`.

[^3]: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139. `denizcan@mit.edu`.

[^4]: Department of Computer Sciences and Wisconsin Institute for Discovery, University of Wisconsin - Madison, 1210 West Dayton Street, Madison, WI 53706. `swright@cs.wisc.edu`.

[^5]: The results can be generalized for quadratic functions of the form $f(x) = \frac12 x^TAx - b^Tx$; however, for simplicity and compatibility with the earlier results in the literature, we consider the case $b=0$.

[^6]: $A$ is a permutation invariant matrix if $PAP^T=A$, for any permutation matrix $P$.

[^7]: Since $A$ has two eigenvalues: $\delta+n(1-\delta)$ with multiplicity $1$ and $\delta$ with multiplicity $n-1$, the Lipschitz constant becomes $L=\delta+n(1-\delta)$, for $\delta\leq1$; and as $\delta\to0$, $L \to n$.
