PaperlayerView exact revision on arXiv

Source-linked AI summary

Iteration Complexity Analysis of Block Coordinate Descent Methods

Mingyi Hong, Xiangfeng Wang, Meisam Razaviyayn, Zhi-Quan Luo

arXiv:1310.6957v2math.OCstat.ME

TL;DR

The paper studies iteration complexity for BCD methods on general nonsmooth convex problems, including settings without strong convexity or error-bound conditions. It unifies BCM, BCGD, and BCPG through BSUM and establishes global sublinear rates, including an accelerated two-block case.

  • Problem

    For more general nonsmooth convex problems lacking strong convexity and error-bound conditions, the iteration complexity of BCD methods requires analysis.

  • Method

    The paper uses the BSUM framework to analyze BCM, BCGD, and BCPG under deterministic coordinate update rules, including Gauss-Seidel and essentially cyclic updates.

  • Results

    The analyzed BCD family achieves a global sublinear rate of O(1/r); BCM attains this rate without per-block strong convexity, while a special two-block BSUM method reaches O(1/r^2).

  • Takeaways & Limitations

    The analysis provides unified complexity guarantees for several BCD methods and shows that two-block structure permits acceleration under weaker conditions.

  • Takeaways & Limitations

    The accelerated schemes and analysis rely heavily on K = 2, and it remains unclear whether the same guarantees or acceleration extend to general K without the BSC condition.

Abstract

from arXiv · show

In this paper, we provide a unified iteration complexity analysis for a family of general block coordinate descent (BCD) methods, covering popular methods such as the block coordinate gradient descent (BCGD) and the block coordinate proximal gradient (BCPG), under various different coordinate update rules. We unify these algorithms under the so-called Block Successive Upper-bound Minimization (BSUM) framework, and show that for a broad class of multi-block nonsmooth convex problems, all algorithms covered by the BSUM framework achieve a global sublinear iteration complexity of $O(1/r)$, where r is the iteration index. Moreover, for the case of block coordinate minimization (BCM) where each block is minimized exactly, we establish the sublinear convergence rate of $O(1/r)$ without per block strong convexity assumption. Further, we show that when there are only two blocks of variables, a special BSUM algorithm with Gauss-Seidel rule can be accelerated to achieve an improved rate of $O(1/r^2)$.

1 Introduction

The paper studies nonsmooth convex block-coordinate optimization and unifies several BCD variants under BSUM to analyze their iteration complexity. Its main results establish O(1/r) rates broadly, with stronger results for exact minimization and two-block acceleration.

  • Problem and algorithms: BCD methods optimize one block at a time while holding the remaining blocks fixed, including exact BCM and approximate BCGD or BCPG variants.
  • Problem and algorithms: Different coordinate-selection rules include Gauss-Seidel, Gauss-Southwell, randomized, essentially cyclic, and maximum block improvement updates.
  • Research gap: Existing complexity results cover several BCD settings, but iteration-complexity analysis remains scarce for traditional deterministic G-S, G-So, and E-C updates.
  • Contributions: The BSUM framework unifies K-block BCD-type algorithms, including BCM, BCGD, and BCPG, under different deterministic coordinate rules.
  • Contributions: O(1/r) is established for broad nonsmooth convex problems, while BCM needs no per-block strong convexity and a special two-block method reaches O(1/r^2).

2 The BSUM Algorithm and Preliminaries

BSUM updates selected variable blocks by minimizing valid upper-bound approximations while fixing the others. The framework recovers common BCD methods and supports multiple update rules under convexity and regularity assumptions.

  • BSUM framework: At each iteration, BSUM selects an index set and minimizes an approximate block objective for selected variables while retaining unselected variables.
  • Update rules: The framework includes G-S, E-C, G-So, and MBI rules for choosing which blocks to update.
  • Assumptions: The main assumptions include convexity, attained global minima, Lipschitz gradient conditions, and continuity plus strong convexity of approximation functions.
  • Approximation functions: A valid upper-bound is locally tight and can simplify subproblems compared with directly minimizing the original objective.
  • Special cases: Choosing the original smooth function recovers BCM, while a linearized upper bound yields BCGD or BCPG when nonsmooth terms are present.
  • Applications and motivation: BCM instantiated with G-S gives the iterative water-filling algorithm, while deterministic BCD complexity bounds were previously unavailable for general-data LASSO.

3 Convergence Analysis for BSUM

The convergence analysis uses a three-step argument: bound successive gap decrease, estimate the remaining cost to minimize, and derive iteration rates. Under the stated assumptions, BSUM achieves global sublinear complexity across several update rules.

  • General result: Under the main assumptions, BSUM with flexible update rules achieves a global sublinear convergence rate.
  • Proof strategy: The analysis proceeds by estimating optimality-gap decrease, the cost-to-go after each iteration, and the resulting convergence rate.
  • Update-rule rates: O(1/r) holds for BSUM with G-S and E-C rules under the theorem’s assumptions.
  • Update-rule rates: G-So and MBI rates require an additional Lipschitz-continuity assumption on the nonsmooth component.
  • Scope: The results cover BCM, BCGD, BCPG, and variants using G-S, E-C, G-So, and MBI rules.
  • BCM specialization: The bounds also apply to BCM with various block-selection rules and can be specialized using the original smooth function as the upper bound.

4 The BSUM for Single Block Problem

For a single-block problem, BSUM reduces to SUM, whose sublinear analysis does not require strong convexity of the upper-bound function. The framework applies this result to IRLS, including cases with nonsmooth h(x).

  • The SUM Algorithm: SUM is the single-block specialization of BSUM, using an upper-bound function updated and minimized iteratively.The algorithm is presented as the Successive Upper-Bound Minimization method.
  • The SUM Algorithm: Assumption C requires Lipschitz continuity of the upper-bound gradient but does not require strong convexity in its minimized variable.It also does not require the upper-bound gradient to be Lipschitz continuous over the reference point x.
  • The SUM Algorithm: SUM converges sublinearly under Assumption C without strong convexity of the upper-bound function u(v; x).This extends the preceding BSUM complexity analysis to the single-block setting.
  • Application to IRLS: IRLS can be viewed either as a two-block BCM method or as a single-block SUM algorithm through its upper-bound construction.The paper uses the latter equivalence to apply the simpler SUM iteration-complexity analysis.
  • Application to IRLS: The IRLS application allows h(x) to be convex and nonsmooth, unlike the cited prior analysis requiring Lipschitz-continuous gradients for h(x).The paper characterizes its analysis as significantly simpler than transforming IRLS into a two-block BCM problem.

5 The BSUM for Two Block Problem

For two-block problems, the paper analyzes Gauss-Seidel BSUM through a single-block reformulation, obtaining sublinear convergence without requiring strong convexity or Lipschitz continuity for the second-block gradient. A Nesterov-type acceleration further improves the rate to O(1/r^2).

  • 5.2 Accelerating the 2-Block BSUM: The accelerated method achieves an iteration complexity of O(1/r^2) without depending on the second block’s gradient Lipschitz constant.This independence follows because Lipschitz continuity of the second-block gradient is not required.
  • 5.1 Iteration Complexity for 2-Block BSUM: The two-block analysis targets cases where the second-block gradient may not be Lipschitz continuous and neither subproblem may be strongly convex.The paper explicitly identifies these conditions as obstacles to directly applying the general rate theorem.
  • 5.1 Iteration Complexity for 2-Block BSUM: The Gauss-Seidel BSUM method uses an upper bound for the first block while minimizing the second block exactly.The resulting method is analyzed through an equivalent single-block problem involving the minimized second-block objective.
  • Scope: The two-block schemes rely on transforming the problem into a single-block problem, and extension to general K-block problems remains unclear.The paper also leaves open whether acceleration applies for arbitrary K.
  • 5.1 Iteration Complexity for 2-Block BSUM: The two-block Gauss-Seidel BSUM algorithm converges sublinearly under the stated upper-bound and Lipschitz-gradient assumptions.The corresponding BCM method has the same sublinear rate and does not require per-block strong convexity.
  • 5.2 Accelerating the 2-Block BSUM: The accelerated two-block BSUM algorithm applies a Nesterov-type scheme to the single-block interpretation.Its analysis is inherited from accelerated proximal-gradient methods.

6 Analysis of the BCM without Per-Block Strong Convexity

This section establishes iteration-complexity guarantees for exact block coordinate minimization without per-block strong convexity, including O(1/r) rates for several update rules and sharper special-case analyses.

  • General BCM analysis: BCM is analyzed without the block strong convexity condition, despite possible nonunique solutions to individual block subproblems.The absence of strong convexity makes successive-iterate distances unreliable for measuring sufficient descent.
  • General BCM analysis: O(1/r) iteration complexity holds for BCM with maximum block improvement, Gauss-Seidel, and essentially cyclic update rules without per-block strong convexity.The paper develops alternative sufficient-descent estimates to overcome the nonuniqueness obstacle.
  • General BCM analysis: The Gauss-Seidel and essentially cyclic BCM results are formalized under the standing assumptions in Theorem 6.1.Separate statements are given for the two update rules.
  • Special composite problems: The composite-case BCM rate can be sharpened because it depends explicitly on problem parameters.The analysis covers sparse logistic regression and group LASSO as special cases.
  • Special composite problems: For composite smooth objectives, sufficient descent is measured using a linearly transformed difference between successive iterates.This differs from measuring descent directly by the norm of the iterate difference.
  • Special composite problems: The analysis implies an O(1/r) rate for the IWFA algorithm regardless of the rank of the channel matrices.The paper notes that no convergence-rate analysis for IWFA had previously been established for any block-selection rule.
  • Special composite problems: The E-C rule also achieves a sublinear rate for the composite and L2-SVM cases.The paper states that the proof follows the preceding arguments and is omitted.

7 Concluding Remarks

The paper unifies iteration-complexity analysis for several BCD methods within BSUM and establishes global sublinear rates across multiple update rules.

  • Main conclusions: The analyzed family includes BCM, BCGD, and BCPG methods under Gauss-Seidel, essentially cyclic, Gauss-Southwell, and maximum block improvement rules.These methods are treated for general convex nonsmooth problems using a three-step argument.
  • Main conclusions: O(1/r) global sublinear convergence holds for the covered BCD-type methods and update rules.For classical BCM, this rate remains available without per-block strong convexity.
  • Future work: Extending the three-step approach to iteration-complexity bounds for other first-order methods is identified as future work.
Loading 1310.6957v2…