Iteration Complexity Analysis of Block Coordinate Descent Methods

Introduction

Consider the problem of minimizing a nonsmooth convex function $f(x)$ of the form:

A well known family of algorithms for solving (1.1) is the block coordinate descent (BCD) type method whereby, at every iteration a single block of variables is optimized while the remaining blocks are held fixed. One of the best known algorithms in the BCD family is the block coordinate minimization (BCM) algorithm, where at iteration $r$, the blocks are updated by solving the following problem exactly

When problem (1.2) is not easily solvable, a popular variant is to solve an approximate version of problem (1.2), yielding the so-called block coordinate gradient descent (BCGD) algorithm, or the block coordinate proximal gradient (BCPG) algorithm in the presence of nonsmooth function . In particular, at a given iteration $r$, the following problem is solved for each block $k$:

where $L_{k}>0$ is some appropriately chosen constant. Other variants of the BCD-type algorithm include those that solve different subproblems , or those with different block selection rules, such as the Gauss-Seidel (G-S) rule, the Gauss-Southwell (G-So) rule , the randomized rule , the essentially cyclic (E-C) rule , or the maximum block improvement (MBI) rule .

In all the above mentioned variants of BCD method, each step involves solving a simple subproblem of small size, therefore the BCD method can be quite effective for solving large-scale problems; see e.g., and the references therein. The existing analysis of the BCD method requires the uniqueness of the minimizer for each subproblem (1.2), or the quasi convexity of $f$ . Recently, a unified BCD-type framework, termed the block successive upper-bound minimization (BSUM) method, is proposed in . At each iteration of the BSUM method, certain approximate function of the per-block subproblem (1.2) is constructed and optimized. Due to the flexibility in choosing the approximate function, the BSUM includes many BCD-type algorithms as special cases. It is shown in that the method converges to stationary solutions for nonconvex problems and to global optimal solutions for convex problems, as long as certain regularity conditions are satisfied for the per-block subproblems.

In this paper, we provide a unified iteration complexity analysis for $K$-block BCD-type algorithm by utilizing the BSUM framework . Our result covers many different BCD-type algorithms such as BCM, BCPG, and BCGD under a number of deterministic coordinate update rules. First, for a broad class of nonsmooth convex problems, we show that the BSUM algorithm achieves a global sublinear convergence rate of ${\cal{O}}({1}/{r})$, provided that each subproblem is strongly convex. Second, when the number of variable blocks is two, we establish an improved ${\cal{O}}({1}/{r^{2}})$ rate for a particular version of the BSUM algorithm, without the strong convexity of the subproblems, or the gradient Lipschitz continuity of one of the subproblems. Third, for the BCM algorithm (1.2), we show the global convergence rate of ${\cal{O}}({1}/{r})$ without the per-block strong convexity assumption. The main results of this paper are summarized in the following table We have used the following abbreviations: NS=Nonsmooth, C=Constrained, K=K-block, BSC=Block-wise Strongly Convex, G-So=Gauss-Southwell, G-S=Gauss-Seidel, E-C=Essentially Cyclic, MBI=Maximum Block Improvement. The notion of valid upper-bound as well as the function $u_{k}$ will be introduced in Section 2. .

The BSUM Algorithm and Preliminaries

In this paper, we consider a family of block coordinate descent methods (BCD) for solving problem (1.1). The family of the algorithms we consider falls in the general category of block successive upper-bound minimization (BSUM) method, in which certain approximate version of the objective function is optimized one block variable at a time, while fixing the rest of the block variables . In particular, at iteration $r+1$, we first pick an index set {\mbox{\mathcal{C}}}^{r+1}\subseteq\{1,\cdots,K\}. Then the $k$th block variable is updated by

where $u_{k}(\cdot;x^{r+1}_{1},\cdots,x^{r+1}_{k-1},x^{r}_{k},\cdots,x^{r}_{K})$ is an approximation of $g(x)$ at a given iterate $(x^{r+1}_{1},\cdots,x^{r+1}_{k-1},x^{r}_{k},\cdots,x^{r}_{K})$. We will see shortly that by properly specifying the approximation function $u_{k}(\cdot)$ as well as the index set {\mbox{\mathcal{C}}}^{r+1}, we can recover many popular BCD-type algorithms such as the BCM, the BCGD, the BCPG methods and so on.

To simplify notations, let us define a set of auxiliary variables

Clearly we have $w^{r}_{K+1}:=x^{r},\;w^{r}_{1}:=x^{r-1}$. Moreover, at each iteration $r+1$, define a set of new variables $\{\hat{x}_{k}^{r+1}\}_{k=1}^{K}$ as follows

Clearly $\{\hat{x}^{r+1}_{k}\}_{k=1}^{K}$ represents a “virtual” update where all variables are optimized in a Jacobi manner based on $x^{r}$.

The BSUM algorithm is described formally in the following table.

The Block Successive Upper-Bound Minimization (BSUM) Algorithm At each iteration $r+1$, pick an index set {\mbox{\mathcal{C}}}^{r+1}; For $k=1,\cdots,K$, do: x^{r+1}_{k}\left\{\begin{array}[]{ll}\in\min_{x_{k}\in X_{k}}\;u_{k}\left(x_{k};w^{r+1}_{k}\right)+h_{k}(x_{k}),&\mbox{if}\;k\in{\mbox{\mathcal{C}}}^{r+1};\\ =x^{r}_{k},&\mbox{if}\;k\notin{\mbox{\mathcal{C}}}^{r+1}\end{array}\right..\\ End For.

In this paper, we consider four well-known block selection rules, described below:

Gauss-Seidel (G-S) rule: At each iteration $r+1$ all the indices are chosen, i.e., {\mbox{\mathcal{C}}}^{r+1}=\{1,\cdots,K\}. Using this rule, the blocks are updated cyclically with fixed order.

Essentially cyclic (E-C) rule: There exists a given period $T\geq 1$ during which each index is updated at least once, i.e.,

We call this update rule a period-$T$ essentially cyclic update rule. Clearly when $T=1$ we recover the G-S rule.

Gauss-Southwell (G-So) rule: At each iteration $r+1$, {\mbox{\mathcal{C}}}^{r+1} contains a single index $k^{*}$ that satisfies:

Maximum block improvement (MBI) rule: At each iteration $r+1$, {\mbox{\mathcal{C}}}^{r+1} contains a single index $k^{*}$ that satisfies:

2 Main Assumptions

Problem (1.1) is a convex problem, ant its global minimum is attained. The intersection $X\cap\hbox{int}(\hbox{dom }f)$ is nonempty.

The gradient of $g(\cdot)$ is block-coordinate-wise uniformly Lipschitz continuous

where $M_{k}>0$ is a constant. Define $M_{\max}=\max_{k}M_{k}$.

The gradient of $g(\cdot)$ is also uniformly Lipschitz continuous

Next we make the following assumptions regarding the approximation function $u_{k}(\cdot;\cdot)$ in (2.1).

$u_{k}(x_{k};x)=g(x),\quad\forall\;x\in{X},\ \forall\;k,$

$u_{k}(v_{k};x)\geq g(v_{k},x_{-k}),\quad\;\forall\;v_{k}\in{X}_{k},\ \forall\;x\in{X},\ \forall\;k,$

$\nabla u_{k}(x_{k};x)=\nabla_{k}g(x),\quad\;\forall\;x\in X,\;\forall\;k,$

$u_{k}(v_{k};x)$ is continuous in $v_{k}$ and $x$. Further, for any given $x$, it is strongly convex in $v_{k}$

where $\gamma_{k}>0$ is independent of the choice of $x$.

For any given $x$, $u_{k}(v_{k};x)$ has Lipschitz continuous gradient, that is

where $L_{k}>0$ is some constant. Further, we have

Define $L_{\rm max}:=\max_{k}L_{k}$; $G_{\rm max}:=\max_{k}G_{k}$.

We refer to the $u_{k}$’s that satisfy Assumption B as a valid upper-bound.

A few remarks are in order regarding to the assumptions made above.

First of all, Assumption B indicates that for any given $x$, each $u_{k}(\cdot;x)$ is a locally tight upper bound for $g(x)$. When the approximation function is chosen as the original function $g(x)$, then we recover the classic BCM algorithm; cf. (1.2). In many practical applications especially nonsmooth problems, minimizing the approximation functions often leads to much simpler subproblems than directly minimizing the original function; see e.g., . For example, if $h_{k}(\cdot)=0$ for all $k$, and $u_{k}$ takes the following form

then we recover the well known BCGD method , in which $x_{k}$ is updated by

When the nonsmooth components $h_{k}$’s are present, the above choice of $u_{k}(\cdot;\cdot)$ in (2.11) leads to the so-called BCPG method , in which $x_{k}$ is updated by

For other possible choices of the approximation function, we refer the readers to .

Secondly, the strong convexity requirement on $u_{k}(\cdot;x)$ in Assumption B(d) is quite mild, see the examples given in the previous remark (e.g., BCPG and BCGD). When $u_{k}$ is chosen as the original function $g(x)$, this requirement says that $g(x)$ must be block-wise strongly convex (BSC). The BSC condition is in fact satisfied in many practical engineering problems. The following are two interesting examples.

where $I_{n_{r}}$ is the $n_{r}\times n_{r}$ identity matrix. The celebrated iterative water-filling algorithm (IWFA) for solving this problem is simply the BSUM algorithm with exact block minimization (i.e. the BCM algorithm) and G-S update rule. It is easy to verify that when $n_{t}\leq n_{r}$ (i.e., the number of transmit antenna is smaller than that of the receive antenna), and when the channels are generated randomly, then with probability one $H^{T}_{k}H_{k}$ is of full rank, implying that the BSC condition is satisfied. We note that there has been no iteration complexity analysis of the IWFA algorithm for any type of block selection rules.

Note that the BSC property, or more generally the strong convexity assumption on the approximate function $u_{k}$, is reasonable as it ensures that each step of the BSUM algorithm is well-defined and has a unique solution. In the ensuing analysis of the BSUM algorithm, we assume that either the BSC property holds true, or $u_{k}$ is a valid upper-bound. Later in Sections 4 - 6, we will consider the case where the BSC assumption is absent.

Convergence Analysis for BSUM

In this section, we show that under assumptions A and B, the BSUM algorithm with flexible update rules achieves global sublinear rate of convergence.

Let us define $X^{*}$ as the optimal solution set, and let ${x}^{*}\in X^{*}$ be one of the optimal solutions. For the BSUM algorithm, define the optimality gap as

Despite the generality of the BSUM algorithm, our analysis of BSUM only consists of three simple steps: S1) estimate the amount of successive decrease of the optimality gaps; S2) estimate the cost yet to be minimized after each iteration; S3) estimate the rate of convergence.

We first characterize the successive difference of the optimality gaps before and after one iteration of the BSUM algorithm, with different update rules.

(Sufficient Descent) Suppose Assumption A and Assumption B hold. Then

For BSUM with either G-S rule or the E-C rule, we have that for all $r\geq 1$

where the constant $\gamma:=\frac{1}{2}\min_{k}\gamma_{k}>0$.

For BSUM with G-So rule and MBI rule, we have that for all $r\geq 1$

where the constant $\gamma:=\frac{1}{2}\min_{k}\gamma_{k}>0$; For G-So rule, $c_{1}=q$, and for MBI rule, $c_{1}=1$.

Proof. We first show part (1) of the proof. Suppose that k\notin{\mbox{\mathcal{C}}}^{r+1}, then we have the following trivial inequality

as both sides of the inequality are zero.

Suppose k\in{\mbox{\mathcal{C}}}^{r+1}. Then using Assumption B, we have that

where the first inequality is due to Assumption B(a)–B(b); the second inequality is due to Assumption B(d); in the third inequality we have defined $\zeta_{k}^{r+1}\in\partial h_{k}(x^{r+1}_{k})$; the last inequality is due to the fact that $x_{k}^{r+1}$ is the optimal solution for the strongly convex problem

where $\gamma:=\frac{1}{2}\min_{k}\gamma_{k}$.

We then show part (2) of the claim. Suppose k\in{\mbox{\mathcal{C}}}^{r+1}, then we have the following series of inequalities for the G-So rule

Similar steps lead to the result for the MBI rule. Q.E.D.

Next we show the second step of the proof, which estimates the gap yet to be minimized after each iteration of the algorithm. Let us define the following constants:

When assuming that the level set $\{x:f(x)\leq f(x^{1})\}$ is compact, then all the above constants are finite. Clearly we have

Occasionally we need to further make the assumption that the nonsmooth part $h(x)$ is Lipchitz continuous:

(Cost-to-go Estimate) Suppose Assumptions A and B are satisfied. Then

For the BSUM with G-S update rule, we have

For the BSUM with period-$T$ E-C update rule, we have

For the BSUM with G-So and MBI rules, further assume that $h(\cdot)$ is Lipchitz continuous (cf. (3.10)). Then we have

Proof. We first show part (1) of the claim. We have the following sequence of inequalities

Notice that $x^{r+1}_{k}$ is the optimal solution for problem: $\mathop{\rm argmin}_{x_{k}\in X_{k}}u_{k}(x_{k};w^{r+1}_{k})+h_{k}(x_{k})$. It follows from the optimality condition of this problem that there exists some $\zeta_{k}^{r+1}\in\partial\left(h_{k}(x^{r+1}_{k})\right)$ such that

where in the last inequality we have used the definition of subgradient

where in (i) we have used the Cauchy-Schwarz inequality and the Lipchitz continuity of $u_{k}(\cdot;\cdot)$ in (2.9); in (ii) we have used the Lipchitz continuity of $\nabla g(\cdot)$ in (2.8), and that $\nabla_{k}g(x^{r+1})=\nabla_{k}u_{k}(x_{k}^{r+1};x^{r+1})$ (cf. Assumption B(c)).

Next we show part (2) of the claim. Let us define a new index set $\{r_{k}\}$ as follows:

That is, $r_{k}$ is the latest iteration index (up until $r+T$) in which the $k$th variable has been updated. From this definition we have $x^{r_{k}}_{k}=x^{r+T}_{k}$, for all $k$.

We have the following sequence of inequalities

where in $\rm(i)$ we have used the fact that $x^{r+T}_{k}=x_{k}^{r_{k}}$, for all k; in $\rm(ii)$ we have used the optimality of $x^{r_{k}}_{k}$. Taking the square on both sides, we obtain

Finally we show part (3) of the claim. We have the following sequence of inequalities

where step $\rm(i)$ follows from the Lipchitz continuity assumption (3.10) as well as the convexity of $g(\cdot)$. Similar to the proof of (3.12) in part (1), we can show that

Moreover, it follows from Assumption B(c) and B(e) that

Putting the above three inequalities together, we have

We are now ready to prove the $\mathcal{O}\left({1}/{r}\right)$ iteration complexity for the BSUM algorithm when applied to problem (1.1). Our results below are more general than the recent analysis on the iteration complexity for BCD-type algorithms. The generality of our results can be seen from several fronts: 1) The family of algorithms we analyze is broad; it includes the classic BCD, the BCGD method, the BCPG methods as well as their variants based on different coordinate selection rules as special cases, while the existing works only focus on one particular algorithm; 2) When the coordinates are updated in a G-S fashion, our result covers the general multi-block nonsmooth case, where $h_{k}(x)$ can take any proper closed convex nonsmooth function, while existing works only cover some special cases ; 3) When the coordinates are updated using other update rules such as G-So, MBI, E-C fashion, our convergence results appear to be new.

Suppose Assumption A(a) and Assumption B hold true. We have the following.

Let $\{x^{r}\}$ be the sequence generated by the BSUM algorithm with G-S rule. Then we have

Let $\{x^{r}\}$ be the sequence generated by the BSUM algorithm with E-C rule. Then we have

Suppose the Lipchitz continuity assumption (3.10) holds true. Let $\{\mathbf{x}^{r}\}$ be the sequence generated by the BSUM algorithm with G-So and MBI rule. Then we have

Proof. We first show part (1) of the claim by mathematical induction on $r$. From Lemma 3.2 and Lemma 3.1, we have that for the G-S rule, we have

By definition, we have $\Delta^{1}=f(x^{1})-f^{*}$. We first argue that

From (3.27) and the fact that $\Delta^{1}\leq{c}_{1}$, we have

where in the last inequality we have used the fact that ${c}_{1}\geq 4\sigma_{1}-2$. Suppose $4\sigma_{1}-1\geq 0$, then we immediately have $\Delta^{2}\leq\frac{{c}_{1}}{2\sigma_{1}}$. Suppose $4\sigma_{1}-1<0$, then

Next we argue that if $\Delta^{r}\leq\frac{{c}_{1}}{r\sigma_{1}}$, then we must have

Using the condition (3.27) and the inductive hypothesis $\Delta^{r}\leq\frac{{c}_{1}}{r\sigma_{1}}$, we have

where the last inequality is due to the fact that ${c}_{1}\geq 2$, and $r\geq 2$. Consequently, we have shown that for all $r\geq 1$

For the E-C rule, first note that from Lemma 3.1, we have

Then using the similar argument as for the G-S rule, we can obtain the desired result.

Next we show part (3) of the claim. For the G-So rule, we have from Lemma 3.2, the second part of Lemma 3.1, that for all $r\geq 1$

Similar relation can be shown for the MBI rule as well. The rest of the proof follows standard argument, see for example [8, Theorem 1]. Q.E.D.

Below we provide further remarks on some special cases of the BSUM algorithm.

One popular choice of the upper bound function $u_{k}(\cdot,\cdot)$ is

where the constant $L_{k}\geq\rho_{\max}(\nabla^{2}g(x))$, is often chosen to be largest eigenvalue of the Hessian of $g(x)$. In this case, evidently we have $\gamma_{k}=L_{k}=M_{k}\leq M$, for all $k$, and $G_{\max}\leq M$. We can also verify that $G_{k}\leq 2M$ for all $k$. Using this choice of $u_{k}(\cdot;\cdot)$ and $L_{k}$, the first result in Theorem 3.1 reduces to

where $M_{\rm min}:=\min_{k}M_{k}$. Let us compare the order given in (3.36) with the one stated in [5, Theorem 6.1], which is the best known complexity bound for the G-S BCD algorithm for smooth problems (i.e., when $h_{k}$ is not present). The bound derived in for smooth constrained problem (resp. smooth unconstrained problem) is in the order of $\frac{KM^{2}R^{2}}{M_{\min}}\frac{1}{r}$ (resp. $\frac{M_{\max}KM^{2}R^{2}}{M^{2}_{\min}}\frac{1}{r}$). These orders are approximately the same as (3.36). However, our proof covers the general nonsmooth cases, and is simpler. Similarly, when $u_{k}(\cdot;\cdot)$ takes the form (3.35), the bounds for the BSUM with the E-C/G-So/MBI rules shown in Theorem 3.1 can also be simplified.

The results derived in Theorem 3.1 is equally applicable to the BCM scheme (1.2) with various block selection rules discussed above. In particular, we can specialize the upper-bound function $u_{k}$ to be the original smooth function $g$. As long as $g(x_{1},\cdots,x_{K})$ satisfies the BSC property, Theorem 3.1 carries over. As mentioned in Section 2.2, the BSC property is fairly mild and is satisfied in many engineering applications. Nevertheless, we will further relax the BSC condition in the subsequent sections.

The BSUM for Single Block Problem

In this section, we consider the following single-block problem with $K=1$:

In this case the BSUM algorithm reduces to to the so-called successive upper-bound minimization (SUM) algorithm , listed in the following table.

The Successive Upper-Bound Minimization (SUM) Algorithm At each iteration $r+1$, do: $x^{r+1}\in\min_{x\in X}\;u\left(x;x^{r}\right)+h(x).$ (4.2)

Let us make the following assumptions on the function $u(v;x)$.

$u(v;x)\geq g(v),\quad\;\forall\;v\in{X},\ \forall\;x\in{X}.$

$\nabla u(x;x)=\nabla g(x),\quad\;\forall\;x\in X$.

For any given $x$, $u(v;x)$ has Lipschitz continuous gradient, that is

Compared to Assumption B, Assumption C does not require $u(v;x)$ to be strongly convex in $v$, nor $\nabla u(v;x)$ to be Lipschitz continuous over $x$. Notice that the Lipschitz continuity of $\nabla u$ given in (4.3) implies the Lipschitz continuity of $\nabla g$.

Suppose $g(x)$ is convex, and $u(v;x)$ satisfies Assumption C. Then we must have

That is, $\nabla g$ is Lipschitz continuous with the coefficient no larger than $L$.

Proof. Utilizing Assumption C, we must have

Further, using the convexity of $g$ we have

Combining these two inequalities we obtain

Similar to [34, Theorem 2.1.5], we construct the following function

where the first inequality is due to the optimality of $v$ and the second inequality uses (4.5). Plugging in the definition of $\phi(x)$ and $\phi(v)$ we have

Since the above inequality is true for any $x,v\in X$, we can interchange $x$ and $v$ and obtain

Cancelling $\|\nabla g(x)-\nabla g(v)\|$ we arrive at the desired results. Q.E.D.

We remark that this result is only true when both $g(\cdot)$ and $u(\cdot;\cdot)$ are convex functions.

Our main result is that the SUM algorithm converges sublinearly under Assumption C, without the strong convexity of the upper-bound function $u(v;x)$ in $v$. The proof of this claim is an extension of Theorem 3.1, therefore we will only provide its key steps. Observe that the following is true

where $\widetilde{x}^{r+1}$ is the iterate obtained by solving the following auxiliary problem for any $\gamma>0$

In (4.7), $\rm{(i)}$ is true because $u(x;y)$ is an upper-bound function for $g(x)$ satisfying Assumption C(b); $\rm{(ii)}$ is true because $x^{r+1}$ is a minimizer of problem (4.2); $\rm{(iii)}$ is true due to the fact that $\widetilde{x}^{r+1}$ is the optimal solution of (4.8) while $x^{r}$ is a feasible solution.

Then we bound $f(x^{r+1})$ using $f(\widetilde{x}^{r+1})$. We have

where $\rm(i)$ is due to the optimality of $x^{r+1}$ for problem (4.2); $\rm(ii)$ uses the gradient Lipschitz continuity of $u(\cdot;x^{r})$; $\rm(iii)$ uses the fact that $u(x^{r};x^{r})=g(x^{r})$, the gradient Lipschitz continuity of $g(\cdot)$ derived in Proposition 4.1; $\rm{(iv)}$ uses the fact that $\nabla u(x^{r};x^{r})=\nabla g(x^{r})$ (cf. Assumption C(c)); $\rm(v)$ uses the convexity of $g(\cdot)$.

Utilizing this bound, we derive the estimate of the cost-to-go

Here $\rm{(i)}$ is due to the optimality of $\widetilde{x}^{r+1}$ to the problem (4.8); in $\rm{(ii)}$ we have used (4.4), Cauchy-Schwartz inequality and the definition of $R$ (it is easy to show that $f(\widetilde{x}^{r+1})\leq f(x^{r})\leq f(x^{0})$, hence $\|\widetilde{x}^{t+1}-x^{*}\|\leq R$ for all $t$).

Combining the above two inequalities, we obtain

Maximizing over $\gamma$ (with $\gamma=4L$), we have

Using the same derivation as in Theorem 3.1, we obtain

2 Application

To see the importance of the above result, consider the well-known method of Iterative Reweighted Least Squares (IRLS) . The IRLS is a popular algorithm used for solving problems such as sparse recovery and Fermat-Weber problem; see [24, Section 4] for a few applications. Consider the following problem

The IRLS algorithm generates the following iterates

Utilizing such two-block BCM interpretation, the author of shows that the IRLS converges sublinearly when $h(x)$ has Lipschitz continuous gradient; see [24, Theorem 4.1].

Differently from , here we take a new perspective. We argue that the IRLS is in fact the SUM algorithm in disguise, therefore our simple iteration complexity analysis given in Section 4.1 for SUM can be directly applied.

It is clear that $g(x^{r})=u(x^{r};x^{r})$, so Assumption C(a) is satisfied. To verify Assumption C(b), we apply the arithmetic-geometric inequality, and have

Assumptions C(c)-(d) are also easy to verify. Note that the matrices $A_{j}$’s do not necessarily have full column rank, so $u(x;x^{r})$ may not be strongly convex over $x\in X$. Nevertheless, $u(x;x^{r})$ defined in (4.16) is indeed an upper bound function for the smooth function $g(x)$, and we have shown that it satisfies Assumptions C. It follows that the iteration (4.14) corresponds to a single-block BSUM algorithm. Our analysis leading to (4.11) suggests that this algorithm converges in a sublinear rate, even when $h(x)$ is a nonsmooth function. To be more specific, for this problem we have

Note that compared with the result derived in [24, Theorem 4.1] which is based on transforming the IRLS algorithm to the two-block BCM problem (4.15), our analysis is based on the key insight of the equivalence between IRLS and the single block BSUM, and it is significantly simpler. Further we do not require $h(x)$ to be smooth, while the result in [24, Theorem 4.1] additionally requires that the gradient of $h(x)$ is Lipschitz continuous It appears that the proof in [24, Theorem 4.1] can be modified to allow nonsmooth $h$, just that it is not explicitly mentioned in the paper. But as it stands, the bound in [24, Theorem 4.1] is explicitly dependent on the Lipschitz constant of the gradient of $h$, while the bound we derived here in (4.17) is not..

The BSUM for Two Block Problem

In this section, we consider the following two-block problem ($K=2$), which is a special case of problem (1.1):

This problem has many applications, such as the special case of Example 2.1 with two users, the two-block formulation of the IRLS algorithm (4.15) or the example presented in [24, Section 5]. Throughout this section, we assume that Assumption A(a) is true. We make the following additional assumptions about problem (5.1).

The problem $\min_{x_{2}\in X_{2}}f(x_{1},x_{2})$ has a unique solution.

The gradient of $g(x_{1},x_{2})$ with respect to $x_{1}$ is Lipschitz continuous, i.e.,

Note that here we do not require that the gradient of $g(\cdot)$ with respect to the second block to be Lipschitz continuous.

We first show that for this problem BSUM with G-S update rule is able to achieve sublinear rate without the BSC condition or the Lipschitz continuity of $\nabla_{2}g(x_{1},x_{2})$. Under the same assumption, we further show that it is possible to accelerate the BSUM method with G-S rule to get an $\mathcal{O}(1/r^{2})$ iteration complexity.

In table given below we list the two-block BSUM algorithm with G-S update rule.

The G-S 2-block BSUM for problem (5.1) At each iteration $r+1$, update the variable blocks by: \displaystyle\begin{split}x_{2}^{r+1}&=\arg\min_{x_{2}\in X_{2}}u_{2}(x_{2};x^{r}_{1},x^{r}_{2})+h_{2}(x_{2})\\ x_{1}^{r+1}&\in\arg\min_{x_{1}\in X_{1}}u_{1}(x_{1};x^{r}_{1},x^{r+1}_{2})+h_{1}(x_{1}).\end{split} (5.2)

Unfortunately for the problem of interest here the rate analysis provided in Theorem 3.1 is no longer applicable because $\nabla_{2}g(x_{1},x_{2})$ may not be Lipschitz continuous, and both subproblems may not be strongly convex. To analyze the convergence rate, let us consider the following special choices of the upper bound where $u_{1}(x_{1};x)$ satisfies Assumption B(a)-(c) and the Lipschtiz continuous gradient condition (2.9), restated below for convenience

By utilizing the argument in Proposition 4.1, we can show that $L_{1}\geq M_{1}$, therefore the following is true as well

Further we do not use any upper bound for the second block, i.e., we let

This suggests that the $x_{2}$-block is minimized exactly.

To analyze the algorithm, it is convenient to consider an equivalent single-block problem, which only takes $x_{1}$ as its variable:

where the second equality is due to the fact that $u_{1}(x_{1};x)$ is an upper bound function for $g(\cdot,x_{2})$. The last equality is from the definition of $u(\cdot;\cdot)$.

To verify Assumption C(c), recall that by Assumption D the inner problem $\min_{x_{2}\in{X}_{2}}{f}(x_{1},x_{2})$ has a unique solution, or equivalently for any given $x_{1}\in X_{1}$, the mapping $x^{*}_{2}(x_{1})$ is a singleton. By applying [36, Corollary 4.5.2–4.5.3], we obtain

where $\widetilde{x}_{2}=\arg\min_{x_{2}\in X_{2}}f(x_{1},x_{2})$. Therefore, we must have

where the second equality comes from the fact that $u_{1}(\cdot;\cdot)$ satisfies Assumption B(c); the third inequality is because $\widetilde{x}_{2}=x^{*}_{2}(x_{1})$ by definition; the last equality is from (5.8). This verifies Assumption C(c).

The Lipschitz continuous gradient condition (with constant $L_{1}$) in Assumption C(d) can be verified by combining (5.3) and the following equality

At this point it is clear that the 2-block BSUM algorithm with G-S update rule is in fact the SUM algorithm given in Section 4.1, where the iterates are generated by

By applying the argument leading to (4.11), we conclude that the 2-block BSUM in which the second block performs an exact minimization converges sublinearly. Also note that neither subproblems in (5.1) is required to be strongly convex, which suggests that the BCM applied to problem (5.1) converges sublinearly without block strong convexity. The precise statement is given in the following corollary.

Assume that Assumption A(a) and D hold for problem (5.1). Then we have the following.

Suppose that $u_{2}(v_{2};x)=g(x_{1},v_{2})$ for all $v_{2}\in X_{2},\ x\in X$ and that $u_{1}(v_{1};x)$ satisfies Assumption B(a)-(c) and the Lipschtiz continuous gradient condition (2.9). Then the 2-block BSUM algorithm with G-S rule is equivalent to the SUM algorithm and converges sublinearly, i.e.,

where $c_{4}$ and $\sigma_{4}$ is given in (4.11), with $L$ in (4.11) replaced by $L_{1}$.

The BCM algorithm applied to (2.9) converges sublinearly with the same rate, again with $L$ in (4.11) replaced by $L_{1}$.

2 Accelerating the 2-Block BSUM

Next we show that it is possible to accelerate the above G-S BSUM iterations (5.2) to obtain an improved rate. The main idea is again to use the single-block interpretation of the 2-block BSUM.

Let us pick the following upper bound function for $x_{1}$

where $M_{1}$ is the Lipschitz constant for $\nabla_{1}g(x_{1},x_{2})$. Then utilizing the single block interpretation of the 2-block BSUM (5.9) we must have

where the last inequality comes from (5.7).

This observation lends itself to a simple acceleration scheme by applying known Nesterov-type acceleration schemes. The scheme, named Accelerated 2-Block BSUM (A-2BSUM) Algorithm, is described in the following table. The $\mathcal{O}(1/r^{2})$ iteration complexity of the algorithm can be obtained directly from existing analysis for accelerated proximal gradient; see, e.g., . It is interesting to see that for the two block problem (5.1), the acceleration scheme developed here as well as the resulting rate are not dependent on the Lipschitz constant for the gradient of the second block, since we do not require $\nabla_{2}g(x_{1},x_{2})$ to be Lipschitz continuous.

The A-2BSUM Algorithm At any given iteration $r>1$, do the following: S1) Choose $\theta^{r}=\frac{2}{r+1}$; S2) ${v}_{1}^{r}=(1-\theta^{r-1}){x}^{r-1}_{1}+\theta^{r}({w}^{r-1}_{1})$; S3) $x^{r}_{2}=\arg\min_{{x}_{2}\in X_{2}}{f}({v}^{r}_{1},x_{2})$; S4) $x_{1}^{r}=\arg\min_{{x}_{1}\in X_{1}}u_{1}(x_{1};v^{r}_{1},x^{r}_{2})$, where $u_{1}$ is given in (5.11); S5) ${w}^{r}_{1}=x_{1}^{r-1}+\frac{1}{\theta^{r}}(x^{r}_{1}-x^{r-1}_{1})$.

To conclude this section, we note that the schemes and analysis developed in this section are special in the sense that they heavily rely on the fact that $K=2$, and the resulting transformation to the single block problem. It is unclear whether the same sublinear iteration complexity holds for a general $K$ without the BSC condition, or if the algorithm can be accelerated for any $K$; see for related discussions.

Analysis of the BCM without Per-Block Strong Convexity

In this section, we consider the BCM algorithm below, which is the BSUM algorithm without using approximation for each block. We analyze its iteration complexity without the BSC assumption.

The Block Coordinate Minimization (BCM) Algorithm At each iteration $r+1$, pick an index set {\mbox{\mathcal{C}}}^{r+1}; update the variable blocks by: x^{r+1}_{k}\left\{\begin{array}[]{ll}\in\min_{x_{k}\in X_{k}}\;g\left(x_{k},w^{r+1}_{-k}\right)+h_{k}(x_{k}),&\mbox{if}\;k\in{\mbox{\mathcal{C}}}^{r+1};\\ =x^{r}_{k},&\mbox{if}\;k\notin{\mbox{\mathcal{C}}}^{r+1}.\end{array}\right.\\

In the absence of the BSC property, there can be multiple optimal solutions for each subproblem. This makes it tricky to establish the convergence of BCM. Specifically, in the context of the three-step analysis framework presented herein, it is difficult to bound the sufficient descent of the objective using the size of of the successive iterates (as per Lemma 3.1). In this section, we overcome this obstacle by developing several variants of the sufficient descent estimate step. We first show that BCM with MBI, G-S and E-C rules has an iteration complexity of $O(1/r)$ for problem (1.1) without the BSC condition. Further, we argue that for certain special classes of problem (1.1), this sublinear rate can be improved in terms of the dependence on $K$ for the G-S/E-C rules. Throughout this section we will impose Assumption A.

We first consider the MBI rule. We notice that the following is true

where $\bar{x}^{r+1}$ is the iterates obtained by any BSUM algorithm with MBI rule; $\hat{x}^{r+1}$ is defined in (2.3). In the above expression $\rm(ii)$ can be obtained using Lemma 3.1, while $\rm(i)$ is true because we used the exact minimization in each step. Then it is straightforward to establish, using the additional assumption that $h$ is Lipschitz continuous, the same rate stated in part (3) of Theorem 3.1.

Next we show that the BCM algorithm with the G-S and E-C rules also achieves an $\mathcal{O}(1/r)$ iteration complexity, without the BSC assumption.

The main difficulty in analyzing the BCM without the BSC is that the size of the difference of the successive iterates is no longer a good measure of the “sufficient descent”. Indeed, due to the lack of per-block strong convexity, it is possible that a block variable travels a long distance without changing the objective value (i.e., it stays in the per-block optimal solution set).

Below we analyze the iteration complexity of BCM. We need to make use of the following key inequality due to Nesterov ; also see (4.5) for a proof. From Assumption A we know that $g$ is convex and has Lipschitz continuous gradient with constant $M$, then we must have have

Utilizing this inequality, the sufficient descent estimate is given by the following lemma.

Suppose Assumption A holds. Then for BCM with either G-S rule or the E-C rule, we have that for all $r\geq 1$

Proof. Suppose that k\notin{\mbox{\mathcal{C}}}^{r+1}, then we have the following trivial inequality

as both sides of the inequality are zero.

Suppose k\in{\mbox{\mathcal{C}}}^{r+1}. Then by (6.2), we have that

where $\rm{(i)}$ is because $w^{r+1}_{k+1}$ and $w^{r+1}_{k}$ only differs by a single block; $\rm{(ii)}$ is due to the optimality of $x^{t+1}_{k}$. Summing over $k$, we have

This completes the proof of this lemma. Q.E.D.

For the BCM with the G-S update rule, we have

For the BCM with the period-T E-C update rule, we have

Proof. We only show the second part of the claim, as the proof for the first part is simply a special case. Define a new index set $\{r_{k}\}$ as in (3.14). Recall that we have $x_{k}^{r_{k}}=x_{k}^{r+T}$, for all $k$. We have the following series of inequalities

where in ${\rm(i)}$ we have used the optimality of $x_{k}^{r_{k}}$ and $x_{k}^{r_{k}}=x_{k}^{r+T}$, for all $k$. Then taking the square on both sides, we obtain

Combining these two results, and utilizing the technique in Theorem 3.1, we readily have the following main result for BCM.

Suppose Assumption A holds true. We have the following.

Let $\{x^{r}\}$ be the sequence generated by the BCM algorithm with G-S rule. Then we have

Let $\{x^{r}\}$ be the sequence generated by the BCM algorithm with E-C rule. Then we have

2 Special Case: The Constrained Nonsmooth Composite Problem

The rate derived in the previous subsection is inversely proportional to $K^{2}$, which is worse than most of the rates derived so far for problems with the BSC assumption. In the following two subsections we sharpen the above results for two special problems of (1.1).

We first make the following additional assumption on the smooth part of the problem (1.1) (besides Assumption A). Suppose that $g(x)$ takes the following form

where $P^{i}_{k}$ is the Lipschitz constant.

Note that the smooth part $g(x)$ may not be strongly convex with respect to any block $x_{k}$, as $A^{i}_{k}$’s can be rank deficient. Two simple examples covered by this family of problems are provided below.

The sparse logistic regression (SLR) problem with a compact feasible set and the group LASSO problem are special cases of problem (1.1) with composite smooth function in the form of (6.2). More specifically, these problems have the following objective functions, respectively:

Our analysis consists of similar three main steps as before. To simplify presentation, below we only show the analysis and result for BCM with G-S update rule. We first show the sufficient descent property. By using the short-handed notation:

we have the following series of inequalities

It is important to note that the sufficient descent estimate described above is measured by the size of the linearly transformed version of the successive difference of the iterates, as opposed to the size of the successive difference of the iterates given in Lemma 3.1.

Next let us show the cost-to-go estimate. First note that when $g(x)$ is the composite function described above, we have

We have the following series of inequalities

where the second inequality is true due to the optimality of $x^{r+1}_{k}$.

Then by the similar argument as in Theorem 3.1, we have the following result.

Suppose $g(\cdot)$ takes the composite form as expressed in (6.2). Further suppose Assumption A and E hold true. Let $\{\mathbf{x}^{r}\}$ be the sequence generated by the BCM algorithm with G-S rule. Then we have

Our analysis above implies that when using the BCM (or equivalently the IWFA algorithm ) to solve the rate optimization problem given in Example 2.1, a sublinear rate can be obtained regardless of the rank of the channel matrices $\{H_{k}\}$. To see this, we first check Assumption E-(a). Denote $X_{k}:=I_{n_{r}}+\sum_{j\neq k}H_{j}C_{j}H^{T}_{j}\succ 0$, then the $k$th subproblem can be reformulated as

Clearly for any feasible choice of $\{C_{j}\}_{j\neq k}$, we must have

This says that the problem is strongly convex with respect to $H_{k}^{T}X_{k}^{-1}H_{k}C_{k}$. It is also easy to verify that the Lipschitz continuous assumption E-(b) is also satisfied; see for example a related discussion in [39, Section V-A]. Then Corollary 6.1 implies that IWFA converges in a rate $O(1/r)$, regardless of the rank of the channel matrices. Prior to our work, no convergence rate analysis has been done for the IWFA when solving problem (2.14).

3 Special Case: The Constrained Nonsmooth L2-SVM Problem

In this subsection, we assume that $g(x)$ takes the following form (besides Assumption A)

To proceed let us define the following short-handed notations:

For simplicity, let us consider the BCM scheme with G-S update rule, in which the $k$th block is updated by

We can obtain the following series of inequalities

Next we proceed to estimate the cost-to-go. To this end, we first bound $\|\nabla_{k}g(x^{r+1})-\nabla_{k}g(x^{r+1}_{k},w^{r+1}_{-k})\|$. We have the following

Consequently the cost-to-go estimate can be expressed as

Suppose Assumption A holds true, and suppose $g(\cdot)$ takes the form as expressed in (6.19). Let $\{\mathbf{x}^{r}\}$ be the sequence generated by the BCM algorithm with G-S rule. Then we have

To close this section, we mention that the E-C rule also achieves a sublinear rate for both the composite case and the L2-SVM cases. The analysis follows a similar argument as those presented above, therefore it is not repeated here.

4 Extensions

We briefly discuss a few extensions of the results presented so far in this section.

The first extension is to the BSUM algorithm without strongly convex upper bounds. For example, to extend Corollary 6.1, suppose that $g(x)$ is given by (6.2). Further assume that $q_{k}(y_{k};y)$ is an upper bound function for

Second, our analysis can be directly applied to the algorithm with random permutation of the coordinates between the iterations, a strategy that has been found to be effective in practice [40, Section 8.5]. Indeed, the analysis for both BSUM and BCM with the G-S rule only requires that within each iteration the coordinates are chosen cyclically. There is no need to maintain the same order across different iterations.

Third, if the smooth function $g(x)$ is given by the composite form expressed in (6.2), and that the following additional assumptions are satisfied, then the BCM algorithm is capable of linear convergence.

Each $h_{k}$ satisfies either one of the following conditions:

The epigraph of $h_{k}(x_{k})$ is a polyhedral set.

$h_{k}(x_{k})=\lambda_{k}\|x_{k}\|_{1}+\sum_{J}w_{J}\|x_{k,J}\|_{2}$, where $x_{k}=(\cdots,x_{k,J},\cdots)$ is a partition of $x_{k}$ with $J$ being the partition index.

Each $h_{k}(x_{k})$ is the sum of the functions described in the previous two items.

The feasible sets $X_{k}$, $k=1,\cdots,K$ are polyhedral sets.

The key for proving the linear convergence is to show certain error bound condition holds true for different types of problems. We refer the readers to for detailed arguments.

Concluding Remarks

In this paper we have analyzed the iteration complexity of a family of BCD-type algorithms for solving general convex nonsmooth problems of the form (1.1). Using a three-step argument, we show that the family of BCD-type algorithms, which includes BCM, BCGD, BCPG algorithms with G-S, E-C, G-So and MBI update rules, converges globally in a sublinear rate of $\mathcal{O}(1/r)$. It should be noted that in case of the classical BCM algorithm, such sublinear rate can be achieved even without the per-block strong convexity. As a future work, it will be interesting to see whether the three-step approach can be extended to establish the iteration complexity bounds for other first order methods.

References