A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization

Meisam Razaviyayn, Mingyi Hong, Zhi‐Quan Luo

Abstract

The block coordinate descent (BCD) method is widely used for minimizing a continuous function $f$ of several block variables. At each iteration of this method, a single block of variables is optimized, while the remaining variables are held fixed. To ensure the convergence of the BCD method, the subproblem to be optimized in each iteration needs to be solved exactly to its unique optimal solution. Unfortunately, these requirements are often too restrictive for many practical scenarios. In this paper, we study an alternative inexact BCD approach which updates the variable blocks by successively minimizing a sequence of approximations of $f$ which are either locally tight upper bounds of $f$ or strictly convex local approximations of $f$. We focus on characterizing the convergence properties for a fairly wide class of such methods, especially for the cases where the objective functions are either non-differentiable or nonconvex. Our results unify and extend the existing convergence results for many classical algorithms such as the BCD method, the difference of convex functions (DC) method, the expectation maximization (EM) algorithm, as well as the alternating proximal minimization algorithm.

Introduction

Optimization serves as the mathematical engine for modern machine learning, signal processing, and engineering. Among the most popular tools in this engine is Block Coordinate Descent (BCD). The logic of BCD is intuitive: to minimize a complex function involving many variables, one fixes most variables and optimizes a single "block" at a time. However, classical BCD theory relies on two restrictive assumptions: the subproblems must be solved exactly, and those solutions must be unique.

In real-world applications—such as training deep neural networks or performing massive tensor decompositions—objective functions are frequently nonconvex (characterized by local minima) or nonsmooth (containing sharp kinks). In these settings, finding exact, unique solutions for every subproblem is often computationally impossible. This paper addresses this gap by providing a unified theoretical framework for inexact BCD, where complex objectives are replaced by simpler local approximations at each step.

The Block Successive Minimization Framework

The authors propose a unified "umbrella" for optimization by analyzing three primary algorithmic frameworks that utilize surrogate functions instead of the original objective $f$:

1. Block Successive Upper-bound Minimization (BSUM)

BSUM is the core of the framework. Instead of minimizing the actual function $f$, the algorithm minimizes a locally tight upper bound $u$. By ensuring that the surrogate $u$ touches $f$ at the current point and stays above it elsewhere, the algorithm guarantees that minimizing $u$ will also decrease $f$. This approach encompasses several famous algorithms, including Expectation Maximization (EM) and Difference of Convex (DC) programming.

2. Maximum Improvement SUM (MISUM)

Standard BCD typically cycles through blocks in a fixed order. MISUM introduces a "greedy" selection rule, picking the block that offers the greatest potential improvement. Crucially, the authors prove that this variant removes the requirement for unique subproblem solutions, making the algorithm significantly more robust for complex nonconvex landscapes.

3. Block Successive Convex Approximation (BSCA)

When finding a global upper bound is mathematically difficult, BSCA offers a local alternative. It uses a local convex approximation of the function combined with an Armijo line search—a technique to determine a step size that ensures a sufficient decrease in the objective function. This allows the framework to handle smooth but non-differentiable problems effectively.

Applications and Empirical Results

While the paper is primarily theoretical, the authors validate their framework using two significant engineering challenges: wireless network design and tensor decomposition.

Wireless Transceiver Design

The researchers applied the framework to the WMMSE (Weighted Minimum Mean Square Error) algorithm in a $K$-cell simulated wireless network. By framing WMMSE as a specific instance of BSUM, they provided the first rigorous convergence proof for this widely used signal processing technique.

Tensor Decomposition and the "Swamp Effect"

In data mining, CANDECOMP/PARAFAC (CP) tensor decomposition is a standard task. However, traditional algorithms like Alternating Least Squares (ALS) often fall into "swamps"—regions where the error stagnates for hundreds of iterations.

The authors introduced a Diminishing Proximal BSUM variant, which adds a penalty for moving too far from the current estimate, with the penalty decreasing over time. This technique effectively "drains the swamp":

  • Standard ALS: Required 277 iterations to converge.
  • Diminishing Proximal BSUM: Required only 78 iterations. This represents a roughly 3.5x speedup in convergence while maintaining theoretical guarantees.

Theoretical Significance

The primary contribution of this work is the unification of disparate algorithms. By proving convergence for the general BSUM framework, the authors simultaneously provided or extended convergence proofs for:

  • Expectation Maximization (EM)
  • Difference of Convex (DC) programming
  • Alternating Proximal Minimization
  • WMMSE

This unified theory allows researchers to develop new, specialized optimization algorithms for nonsmooth or nonconvex problems with the confidence that they will converge to a stationary point.

Limitations and Future Directions

Despite its breadth, the framework has specific boundaries. First, like most BCD-style methods, these algorithms converge to stationary points (local minima or saddle points) rather than global minima. In a nonconvex landscape, the global optimum remains elusive. Second, the BSCA variant requires the objective function to be smooth (differentiable), which limits its use in certain nonsmooth applications. Finally, the greedy selection rule in MISUM can be computationally expensive for problems with a very large number of blocks; future research into randomized block selection could mitigate this overhead.

Summary updated

Abstract

The block coordinate descent (BCD) method is widely used for minimizing a continuous function f of several block variables. At each iteration of this method, a single block of variables is optimized, while the remaining variables are held fixed. To ensure the convergence of the BCD method, the subproblem to be optimized in each iteration needs to be solved exactly to its unique optimal solution. Unfortunately, these requirements are often too restrictive for many practical scenarios. In this paper, we study an alternative inexact BCD approach which updates the variable blocks by successively minimizing a sequence of approximations of f which are either locally tight upper bounds of f or strictly convex local approximations of f. We focus on characterizing the convergence properties for a fairly wide class of such methods, especially for the cases where the objective functions are either non-differentiable or nonconvex. Our results unify and extend the existing convergence results for many classical algorithms such as the BCD method, the difference of convex functions (DC) method, the expectation maximization (EM) algorithm, as well as the alternating proximal minimization algorithm.
BibTeX
@article{razaviyayn2013unified,
  author = {Meisam Razaviyayn and Mingyi Hong and Zhi‐Quan Luo},
  title = {{A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization}},
  journal = {SIAM J. Optim.},
  year = {2013},
  doi = {10.1137/120891009},
}
Figure