Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems

Introduction

Consider the following convex optimization problem

Algorithm 1: The Cyclic Block Coordinate Descent (BCD) At each iteration $r+1$, update the variable blocks by: $x^{(r)}_{k}\in\min_{x_{k}\in X_{k}}\;g\left(x_{k},w^{(r)}_{-k}\right)+h_{k}(x_{k}),\;k=1,\cdots,K.\\$ (2)

​where we have used the following short-handed notations:

​The convergence analysis of the BCD has been extensively studied in the literature, see . For example it is known that for smooth problems (i.e. $f$ is continuous differentiable but possibly nonconvex, $h=0$), if each subproblem has a unique solution and $g$ is non-decreasing in the interval between the current iterate and the minimizer of the subproblem (one special case is per-block strict convexity), then every limit point of $\{x^{(r)}\}$ is a stationary point [5, Proposition 2.7.1]. The authors of have derived relaxed conditions on the convergence of BCD. In particular, when problem (1) is convex and the level sets are compact, the convergence of the BCD is guaranteed without requiring the subproblems to have unique solutions . Recently Razaviyayn et al have shown that the BCD converges if each subproblem (2) is solved inexactly, by way of optimizing certain surrogate functions.

Luo and Tseng in have shown that when problem (1) satisfies certain additional assumptions such as having a smooth composite objective and a polyhedral feasible set, then BCD converges linearly without requiring the objective to be strongly convex. There are many recent works on showing iteration complexity for randomized BCGD (block coordinate gradient descent), see and the references therein. However the results on the classical cyclic BCD is rather scant. Saha and Tewari show that the cyclic BCD achieves sublinear convergence for a family of special LASSO problems. Nutini et al show that when the problem is strongly convex, unconstrained and smooth, BCGD with certain Gauss-Southwell block selection rule could be faster than the randomized rule. Recently Beck and Tetruashvili show that cyclic BCGD converges sublinearly if the objective is smooth. Subsequently Hong et al in show that such sublinear rate not only can be extended to problems with nonsmooth objective, but is true for a large family of BCD-type algorithm (with or without per-block exact minimization, which includes BCGD as a special case). When each block is minimized exactly and when there is no per-block strong convexity, Beck proves the sublinear convergence for certain 2-block convex problem (with only one block having Lipschitzian gradient). It is worth mentioning that all the above results on cyclic BCD directly apply to randomly permuted BCD in which the blocks are randomly sampled without replacement in each cycle, since the proof techniques do not require the same order to be used in each cycle. However, we suspect that special proof techniques tailored for randomly permutation are necessary for establishing tight bounds of randomly permuted BCD; in fact, a recent work of Sun et al on randomly permuted ADMM provides some theoretical evidence that the cyclic rule is worse than the random permutation rule.

To illustrate the rates developed for the cyclic BCD algorithm, let us define $X^{*}$ to be the optimal solution set for problem (1), and define the constant

Also assume that $g(\cdot,x_{-k})$ has Lipschitz continuous gradient with respect to each $x_{k}$, i.e.,

Let $L_{\max}:=\max_{k}L_{k}$ and $L_{\min}:=\min_{k}L_{k}$. It is known that the cyclic BCPG has the following iteration complexity Note that the assumptions made in and are slightly different, but the rates derived in both cases have similar dependency on the problem dimension $K$.

where $C>0$ is some constant independent of problem dimension. Similar bounds are provided for cyclic BCD in [7, Theorem 6.1]. In contrast, it is well known that when applying the classical gradient descent (GD) method to problem (1) with the constant stepsize $1/L$, we have the following rate estimate [11, Corollary 2.1.2]

Note that unlike (6), here the constant in front of the $1/(r+4)$ term is independent of the problem dimension. In fact, the ratio of the bound given in (6) and (7) is

which is at least in the order of $K$. For big data related problems with over millions of variables, a multiplicative constant in the order of $K$ can be a serious issue. In a recent work by Saha and Tewari , the authors show that for a LASSO problem with special data matrix, the rate of cyclic BCD (with special initialization) is indeed $K$-independent. Unfortunately, such a result has not yet been extended to any other convex problems. An open question posed by a few authors are: is such a $K$ factor gap intrinsic to the cyclic BCD or merely an artifact of the existing analysis?

In this paper, we provide improved iteration complexity bounds of cyclic block coordinate descent methods for convex composite function minimization. Our analyses do not depend on the update order of block variables inside each cycle, thus our results also apply to BCD methods with random permutation (random sampling without replacement, another popular variant). Recall that $K$ is the number of blocks, $L$ is the global Lipshitz constant of $\nabla g$, and $L_{k}$ is the Lipshitz constant of $\nabla g$ with respect to the $k$-th block.

For minimizing the sum of a convex quadratic function (not necessarily strongly convex) and sepearable non-smooth function (including LASSO as a special case), we prove that the iteration complexity bound of cyclic block coordinate gradient descent (C-BCGD) with a small stepsize $1/L$ matches that of GD (gradient descent) up to an $O(\log^{2}(K))$-factor. When the stepsize for the $k$-th block update is $1/L_{k}$, we establish an iteration complexity bound that is $K$-times better than the existing bound, but still $K$ times worse than GD. We also improve the bound of the exact BCD by an order of $K$ (note that if each block has size $1$, exact CD is equivalent to CGD with stepsize $1/L_{k}$; otherwise, exact BCD is different from BCGD).

For general smooth convex optimization (i.e. $h_{k}=0,\forall k$), we prove a meta iteration complexity bound of cyclic coordinate gradient descent (C-CGD) that is proportional to the spectral norm of a “moving-iterate Hessian”. By an preliminary estimate of this spectral norm, this meta bound implies an iteration complexity bound that, in certain scenarios, matches the bound of GD and $K$-times better than the known bounds. For the quadratic case, the moving-iterate Hessian becomes a constant matrix and the meta bound reduces to the bound mentioned in the first bullet which matches GD up to an $O(\log^{2}{2K})$-factor for small stepsize $1/L$.

For illustration, we summarize the comparison of our main results with other existing bounds in several simple settings in Table 1. For simplicity, we only list the results of BCGD for the smooth case; note that the results listed in the last row for QP also apply to LASSO (or more general, sum of a quadratic function plus separable non-smooth function), and for cyclic exact BCD the results are similar to the last row (see Theorem 3.1). We assume $L_{k}=L_{1},\forall k$ and consider two extreme values of $L/L_{k}$: $L/L_{1}=1$ and $L/L_{1}=K$. The first case represents a separable objective function $g(x)=\frac{L}{2}\sum_{i=1}^{K}\|x_{i}\|^{2}$ with a block diagonal Hessian matrix, and the second case represents a highly non-separable objection function $g(x)=\frac{L}{2K}(\sum_{i=1}^{K}x_{i})^{2}$ with a full Hessian matrix, assuming all $x_{i}$’s have the same size.

Improved Bounds of Cyclic BCPG for Nonsmooth Quadratic Problem

In this section, we consider the following nonsmooth quadratic problem

We consider the following cyclic BCPG algorithm.

Algorithm 2: The Cyclic Block Coordinate Proximal Gradient (BCPG) At each iteration $r+1$, update the variable blocks by: $\displaystyle x^{(r+1)}_{k}$ $\displaystyle=\arg\min_{x_{k}\in X_{k}}\;g(w^{(r+1)}_{k})+\left\langle\nabla_{k}g\left(w^{(r+1)}_{k}\right),x_{k}-x^{(r)}_{k}\right\rangle+\frac{P_{k}}{2}\left\|x_{k}-x^{(r)}_{k}\right\|^{2}+h_{k}(x_{k})$ (9)

Here $P_{k}$ is the inverse of the stepsize for $x_{k}$, which satisfies

Define $P_{\max}:=\max_{k}P_{k}$ and $P_{\min}=\min_{k}P_{k}$. Note that for the least square problem (smooth quadratic minimization, i.e. $h_{k}\equiv 0,\forall\;k$), BCPG reduces to the widely used BCGD method.

The optimality condition for the $k$th subproblem is given by

In what follows we show that the cyclic BCPG for problem (8) achieves a complexity bound that only dependents on $\log^{2}(K)$, and apart from such log factor it is at least $K$ times better than those known in the literature. Our analysis consists of the following three main steps:

Estimate the descent of the objective after each BCPG iteration;

Estimate the cost yet to be minimized (cost-to-go) after each BCPG iteration;

Combine the above two estimates to obtain the final bound.

First we show that the BCPG achieves the sufficient descent.

We have the following estimate of the descent when using the BCPG:

Proof. We have the following series of inequalities

where the second inequality uses the optimality condition (11). Q.E.D.

To proceed, let us introduce two matrices $\widetilde{P}$ and $\widetilde{A}$ given below, which have dimension $K\times K$ and $MK\times NK$, respectively

By utilizing the definition of $P_{k}$ in (10) we have the following inequalities (the second inequality comes from [12, Lemma 1])

​​where $I_{N}$ is the $N\times N$ identity matrix and the notation “$\otimes$” denotes the Kronecker product.

We have the following estimate of the optimality gap when using the BCPG:

Proof. First note that $g(x)$ being convex quadratic implies that its second order Taylor expansion is tight

Using this fact we can estimate $f(x^{(r+1)})-f(x^{*})$ by the following series of inequalities

where in $\rm(i)$ we have used the optimality condition of the subproblem (9) (i.e., (11)); in the last equality we have defined a lower triangular matrix $D_{1}$

where “$\odot$” denotes the Hadamard product; $D_{2}$ is a lower triangular matrix similarly as defined in (31), but of dimension $KN\times KN$. Combining this identity and (25), we have

where $\rm(i)$ uses the Cauchy-Schwartz inequality and the fact that {\mbox{\widetilde{P}}}\otimes I_{N}\succeq{\mbox{\widetilde{A}}}^{T}{\mbox{\widetilde{A}}}; $\rm(iii)$ is true for all $KN\geq 3$. Inequality $\rm(ii)$ is true due to a result on the spectral norm of the triangular truncation operator; see [1, Theorem 1]. In particular, Define

Our third step combines the previous two steps and characterizes the iteration complexity. This is the main result of this section.

The iteration complexity of using BCPG to solve (8) is given below.

When the stepsizes are chosen conservatively as $P_{k}=L,\;\forall~{}k$, we have

When the stepsizes are chosen as $P_{k}=\lambda_{\max}(A_{k}^{T}A_{k})=L_{k},\ \forall~{}k$. Then we have

Proof. For notational simplicity, let us define

Taking a square of the cost-to-go estimate (2.2) and the sufficient descent estimate (12), we obtain

Utilizing a result from [2, Lemma 3.5], the above inequality implies that

When $P_{k}=L$ for all $k$, the bound reduces to

When the problem is smooth and unconstrained, we have

The bounds derived in Theorem 2.1 is again at least $K/\log^{2}(2NK)$ times better than existing bounds of cyclic BCPG. For example, when the problem is smooth and unconstrained, the ratio between our bound (35) and the bound (6) is given by

​​where in the last inequality we have used the fact that $L_{\max}/L_{\min}\geq 1$.

For unconstrained smooth problems, let us compare the bound derived in the second part of Theorem 2.1 (stepsize $P_{k}=L_{k},\forall k$) with that of the GD (7). If $L=KL_{k}$ for all $k$ (problem badly conditioned), our bound is about $K\log^{2}(2NK)$ times worse than that of the GD. This indicates a counter-intuitive phenomenon: by choosing conservative stepsize $P_{k}=L,\forall k$ the iteration complexity of BCGD is $K$ times better compared with choosing a more aggressive stepzise $P_{k}=L_{k},\forall k$. It also indicates that the factor $L/L_{\min}$ may hide an additional factor of $K$.

Improved Bounds of Cyclic BCD for Quadratic Problems

In the previous section, we analyzed an inexact cyclic BCD algorithm, the BCPG algorithm. In this section we analyze the performance of the cyclic BCD algorithm (with exact minimization, cf. (2)), when applied to the quadratic problem (8).

We will divide our analysis into three cases ($\lambda_{\min}$ denotes the minimum eigenvalue):

Each $A_{k}$ has full column rank with $\lambda_{\min}(A^{T}_{k}A_{k})\geq\sigma^{2}_{k}$, where $\sigma_{k}>0$ is some known constant;

Each $A_{k}$ has full row rank with $\lambda_{\min}(A_{k}A^{T}_{k})\geq\gamma_{k}^{2}$, where $\gamma_{k}>0$ is some known constant;

Each $A_{k}$ has neither full column rank nor full row rank.

Note that in the last two cases the subproblems are not strongly convex hence may not have unique solutions. Without uniqueness, the only known iteration complexity bound for the cyclic BCD is developed in , but such bound is at least proportional to $K^{2}$.

Our analysis again follows the three-step approach used in the previous section. To estimate the descent, we have the following lemma.

We have the following estimate of the descent when using the BCD

Proof. We have the following series of inequalities

where in $\rm(i)$ we have used the fact that the second order Taylor expansion of a quadratic problem is exact; in $\rm(ii)$ we have used the optimality of $w_{k+1}^{(r+1)}$; cf. (11). Q.E.D.

The cost-to-go estimate is given by the following lemma.

Let $\sigma_{\min}:=\min_{i}\{\sigma_{i}\}$ and $\gamma_{\min}:=\min_{i}\{\gamma_{i}\}$ . We have the following estimate of the optimality gap when using the cyclic BCD to solve (8).

When each $A_{k}$ has full column rank, we have

When each $A_{k}$ has full row rank, we have

When each $A_{k}$ has neither full column rank nor full row rank, we have

Proof. We again bound $\Delta^{(r+1)}=f(x^{(r+1)})-f(x^{*})$. First we have

​​where in $\rm(i)$ we have used the optimality condition of $w_{k+1}^{(r+1)}$ (cf. (11)); in $\rm(ii)$ $D_{3}$ is the following lower triangular matrix

Below we bound $\|f(x^{(r+1)})-f(x^{*})\|$ for three different cases.

where $D_{2}$ is the $KN\times KN$ lower triangular matrix; in the last inequality we have again used the property of lower triangular truncation operator; see the proof of Lemma 2.2.

where in ${\rm(i)}$ {\mbox{\widetilde{A}}}^{\dagger} is the Moore-Penrose pseudoinverse of $\widetilde{A}$, and we have utilized the fact that when $A_{k}A^{T}_{k}$ is invertible, its Moore-Penrose pseudoinverse is given by $(A_{k}A^{T}_{k})^{-1}A_{k}$; in ${\rm(ii)}$ we again have used the property of lower triangular truncation operator; see the proof of Lemma 2.2.

The third step again combines the previous two steps to derive the final bounds.

The iteration complexity of using cyclic BCD to solve (8) is given below.

When each $A_{k}$ has full column rank, we have

When each $A_{k}$ has full row rank, we have

When each $A_{k}$ has neither full column rank nor full row rank, we have

Proof. First, consider the case where $A_{k}$’s all have full column rank. In this case the descent estimate (39) can be further expressed as

Using this relation and squaring both sides of (40), we obtain

Second, when $A_{k}$’s all have full row rank, we can simply combine (39) and (41) and obtain

Third, when $A_{k}$’s all neither full row rank nor full column rank, we can combine (39) and (42) and obtain

Again by utilizing result from [2, Lemma 3.5] to the recursions (54)–(56) we obtained the desired results. Q.E.D.

Except for the log factor, such bound is again no longer explicitly dependent on $K$, and is about $K/\log^{2}(2NK)$ times better than the existing bound on the cyclic BCD .

Viewing $L/L_{\min}$ and $R_{0}^{2}$ as constants, the bound derived in (35) for BCPG is $\mathcal{O}(\log^{2}(2K){L}/{r})$. An immediate question is: is it possible to further reduce these bounds by an additional order of $K$, i.e. $\mathcal{O}(\log^{2}(2K){L}/{(Kr)})$? The answer is negative at least for $r=1$, as shown below. Note that the analysis below does not exclude the possibility that BCD can achieve an iteration complexity $\mathcal{O}({L}/{r^{2}})$ or $\mathcal{O}(c^{r})$, where $c<1$ is a constant depending on $L$. Finding the iteration complexity lower bound of exact BCD for smooth quadratic minimization remains an interesting open question.

Note that $A^{T}A\succeq 0$, but it is not necessarily full rank. Clearly $x^{*}=[0,\cdots,0]^{T}$ is one of the optimal solutions for problem (58), while is also the the optimal objective value. Further, we know that the maximum eigenvalue for the matrix $A$ is:

which means that $\|A\|_{2}\leq 3$. Therefore the Lipschitz constant of $\nabla g(x)$ is bounded by $L\leq 18$, regardless of the dimension $K$. For the classical gradient decent method, we must have (cf. (7))

​where $A_{k}$ is the $k$th column of $A$. For this block structure, we have $L_{\min}=4$, $L_{\max}=9$, and $L/L_{\min}\leq 5$.

Based upon the above block structure, it is easy to verify that the cyclic BCD with exact minimization generates the same sequence as the cyclic BCPG with stepsizes $\{1/L_{k}\}_{k}$. Therefore our result below holds for both algorithms. Consider problem (67) with $A=[A_{1},\cdots,A_{K}]$ given by (65). Let

We can show through explicit computation that after running cyclic BCD/BCPG for one pass of all blocks, the optimality gap $\Delta^{(1)}$ is bounded below by

The derivation is relegated to the Appendix. This result implies that it is not possible to derive a global complexity bound $\mathcal{O}(\frac{L}{Kr})$ for BCD and BCPG with stepsizes $\{1/L_{k}\}_{k}$

Iteration Complexity for General Convex Problems

In this section, we consider improved iteration complexity bounds of BCD for general unconstrained smooth convex problems. We prove a general iteration complexity result, which includes a result of Beck et al. as a special case. Our analysis for the general case also applies to smooth quadratic problems, but is very different from the analysis in previous sections for quadratic problems. For simplicity, we only consider the case $N=1$ (scalar blocks); the generalization to the case $N>1$ is left as future work.

Let us assume that the smooth objective $g$ has second order derivatives $H_{ij}(x):=\frac{\partial^{2}g}{\partial x_{i}\partial x_{j}}(x)$. When each block is just a coordinate, we assume $|H_{ij}(x)|\leq L_{ij},\forall i,j.$ Then $L_{i}=L_{ii}$ and $L_{ij}\leq\sqrt{L_{i}}\sqrt{L_{j}}$. For unconstrained smooth convex problems with scalar block variables, the BCPG iteration reduces to the following coordinate gradient descent (CGD) iteration:

where $d_{k}=\nabla_{k}g(w^{(r)}_{k})$ and $w^{(r)}_{k}\overset{d_{k}}{\longrightarrow}w^{(r)}_{k+1}$ means that $w^{(r)}_{k+1}$ is a linear combination of $w^{(r)}_{k}$ and $d_{k}e_{k}$ ($e_{k}$ is the $k$-th block unit vector).

The general framework follows the standard three-step approach that combines sufficient descent and cost-to-go estimate; nevertheless, the analysis of the sufficient descent is very different from the methods used in the previous sections.

Proof. Since $w^{r}_{k+1}$ and $w^{r}_{k}$ only differ by the $k$-th block, and $\nabla_{k}g$ is Lipschitz continuous with Lipschitz constant $L_{k}$, we have A stronger bound is $g(w^{r}_{k+1})\leq g(w^{r}_{k})-\frac{1}{2P_{k}}\|\nabla_{k}g(w^{r}_{k})\|^{2}$, where $\hat{P}_{k}=\frac{P_{k}^{2}}{2P_{k}-L_{k}}\leq P_{k},$ but since $P_{k}\leq 2P_{k}-L_{k}\leq 2P_{k}$, the improvement ratio of using this stronger bound is no more than a factor of $2$.

where the last inequality is due to $P_{k}\geq L_{k}$.

by the mean-value theorem, there must exist $\xi_{k}$ such that

where $H_{ij}(x)=\frac{\partial^{2}g}{\partial x_{i}\partial x_{j}}(x)$ is the second order derivative of $g$. Then

Let $D\triangleq\text{Diag}(P_{1},\dots,P_{K})$ and let $H(\xi)$ be defined as in (72), then $V=D^{1/2}+H(\xi)D^{-1/2}$, which implies

Plugging into (79), we obtain the desired result. Q.E.D.

The above lemma provides an estimate of the sufficient descent. The intuition is that CGD can be viewed as an inexact gradient descent method, thus the amount of descent can be bounded in terms of the norm of the full gradient. It would be difficult to further tighten this bound if the goal is to obtain a sufficient descent based on the norm of the full gradient. To further improve this bound, we suspect that either the third order derivatives of $g$ or the relation between $H(\xi)$ and $d_{k}=\nabla_{k}g(w^{r}_{k})$ should be considered (in the derivation of Lemma 4.1 we treat $H(\xi)$ and $d_{k}$ independently).

Having established the sufficient descent in terms of the full gradient $\nabla g(x^{(r)})$, we can easily prove the iteration complexity result, following the standard analysis of GD (see, e.g. [11, Theorem 2.1.13]).

Proof. Denote $\omega=\frac{1}{2}\frac{1}{P_{\max}+\frac{\beta^{2}}{P_{\min}}}$, then (71) becomes

This relation also implies $g(x^{(r)})\leq g(x^{(0)})$, thus by the definition of $R_{0}$ in (3) we have $\|x^{(r)}-x^{*}\|\leq R_{0}$. By the convexity of $g$ and the Cauchy-Schwartz inequality, we have

Let $\Delta^{(r)}=g(x^{(r)})-g(x^{*})$, we obtain

This completes the proof of the claim. Q.E.D.

In the following corollary, we provide an initial estimate of $\beta$ and obtain a more concrete iteration complexity bound.

For CGD with $P_{k}\geq L_{\max},\forall k$, we have $\beta^{2}\leq\min\{KL^{2},(\sum_{k}L_{k})^{2}\}$, thus

Proof. First, from the fact that $H_{kj}(\xi_{k})$ is a scalar bounded above by $|H_{kj}(\xi_{k})|\leq L_{kj}\leq\sqrt{L_{k}L_{j}}$, thus

We provide the second bound of $\|H\|$ below. Let $H_{k}$ denote the $k$-th row of $H$, then $\|H_{k}\|\leq L$. Therefore, we have

Plugging this bound and (84) into (81), we obtain the desired result. Q.E.D.

Let us compare this bound with the bound derived in [4, Theorem 3.1] (replacing the denominator $r+8/K$ by $r$), which is

We have demonstrated that our bound can match GD in some cases, but can possibly be $K$ times worse than $GD$. An interesting question is: for general convex problems can we obtain an $\mathcal{O}(\frac{L}{r})$ bound for cyclic BCGD, matching the bound of GD? Removing the $K$-factor in (85) will lead to an $\mathcal{O}(\frac{L}{r})$ bound for conservative stepsize $P_{k}=L$ no matter how large $L_{k}$ and $L$ are. Unfortunately, our approach which is based on estimating the norm of $H(\xi)$ probably cannot lead to removal of this $K$-factor as it seems unlikely to prove a bound $\|H(\xi)\|\leq L$. Our bound $\|H(\xi)\|\leq\min\{KL^{2},(\sum_{k}L_{k})^{2}\}$ is tight in some cases, but not always tight. A better bound of $\|H(\xi)\|$ (and thus a better iteration complexity bound) may be obtained by answering the following question (below $A_{k}$ represents the Hessian matrix corresponding to $\xi_{k}$, $k=1,\dots,K$, and $B(i,:)$ denotes the $i$’th row of a matrix $B$):

The answer to this question seems to be rather complicated and is left as future work.

We conjecture that an $\mathcal{O}(\frac{L}{r})$ bound for cyclic BCGD cannot be achieved for general convex problems. That being said, we point out that the iteration complexity of cyclic BCGD may depend on other intrinsic parameters of the problem such as $\{L_{k}\}_{k}$ and, possibly, third order derivatives of $g$. Thus the question of finding the best iteration complexity bound of the form $\mathcal{O}(h(K)\frac{L}{r})$, where $h(K)$ is a function of $K$, may not be the right question to ask for BCD type algorithms.

Our complexity results apply directly to a popular variant of the BCD – the permuted BCD, in which the blocks are randomly sampled without replacement. This is because our analysis only depends on the behavior of the algorithm during one iteration in which all blocks are updated once. The order of the block update across different iterations is irrelevant in the analysis. However, we mention that the key research question for permuted BCD is not whether it converges, but rather whether performing the random permutation delivers improved complexity bounds. To our knowledge this is still an open question that worth further investigation.

Conclusion

In this paper, we provide new analysis and improved complexity bounds for cyclic BCD-type methods. Our results also apply to BCD methods with random permutation (random sampling without replacement). For minimizing the sum of a convex quadratic function and separable non-smooth functions, we show that cyclic BCGD with small stepsize $1/L$ has an iteration complexity bound $\mathcal{O}(\log^{2}(2K)\frac{L}{r})$, which is independent of $K$ and matches the bound of GD (except for a mild $O(\log^{2}(2K))$ factor). For general smooth convex problems, we consider cyclic CGD and prove a meta iteration complexity bound that is proportional to the spectral norm of a “moving-iterate Hessian”. This meta bound leads to an iteration complexity bound that is sometimes $K$-times better than existing bound of , and matches the bound of GD for the quadratic case when using small stepsize $1/L$. The derivation of our meta iteration complexity bound is rather tight, but still this bound seems to be worse than the bound of GD in certain scenarios. It remains an interesting open question whether this gap in the general convex case is artificial.

Claim. Consider problem (67) with $A=[A_{1},\cdots,A_{K}]$ given by (65). Let

Then after running BCD/BCPG for one iteration, the optimality gap $\Delta^{(r)}$ is bounded below by

Proof. Assume that we start with a vector $x^{(0)}=\left[x^{(0)}_{1},x^{(0)}_{2},\cdots,x^{(0)}_{K}\right]^{T}$, let us generate the iterate $x^{(1)}$ by using cyclic BCD (assuming that coordinates are picked in the order of $1,2,\cdots,K$). The first variable $x_{1}$ is updated by

Here the second equality is true by the property of the matrix $A$. Clearly we have

The second variable $x_{2}$ is updated by

Similarly, the third variable $x_{3}$ is updated by

In general, for all $k\in[3,K-2]$, we have

Also we have that $x_{K-1}$ is updated by

This means that after the first iteration, the objective becomes

Combining the above result, we see that when applying the BCD/BCPG to the problem (58), the complexity bound is at least

This completes the proof of the claim. Q.E.D.

References