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

Meisam Razaviyayn, Mingyi Hong, Zhi-Quan Luo

This paper provides a powerful theoretical "umbrella" for a wide range of optimization algorithms used across machine learning, signal processing, and wireless communications. By introducing a unified framework for Block Successive Minimization, the authors prove convergence for algorithms that handle messy, real-world objective functions—specifically those that are nonconvex or nonsmooth.

TL;DR

The authors develop a unified convergence theory for "inexact" Block Coordinate Descent (BCD) methods, where complex objective functions are replaced by simpler local approximations at each step. This framework proves the convergence of several famous algorithms—including Expectation Maximization (EM), Difference of Convex (DC) programming, and WMMSE—while introducing new, more efficient variants for problems like tensor decomposition.

What Problem Does This Paper Address?

Optimization is the engine of modern AI and engineering. A classic engine is Block Coordinate Descent (BCD): to minimize a function of many variables, you fix most of them and optimize one "block" at a time.

However, standard BCD theory has two major "gotchas":

  1. Exactness: It usually requires you to solve the subproblem exactly.
  2. Uniqueness: It often requires the subproblem to have a unique solution to guarantee convergence.

In practice, many problems (like training neural networks or decomposing massive tensors) are nonconvex (full of local pits) or nonsmooth (have sharp kinks). In these cases, solving subproblems exactly is often impossible or computationally ruinous. This paper fills the gap by analyzing inexact BCD, where we minimize a "surrogate" or approximation of the function instead of the function itself.

Methods

The authors propose three main algorithmic frameworks:

  • BSUM (Block Successive Upper-bound Minimization): Instead of minimizing the real function $f$, you minimize a locally tight upper bound $u$. This is the core of major algorithms like EM.
  • MISUM (Maximum Improvement SUM): A "greedy" version of BSUM. Instead of cycling through blocks in order, you pick the block that offers the most improvement. Crucially, this version removes the requirement for unique subproblem solutions, making it much more robust.
  • BSCA (Block Successive Convex Approximation): For cases where finding a global upper bound is too hard, this method uses a local convex approximation combined with an Armijo line search (a way to pick a step size that ensures the function actually goes down).

The paper provides rigorous proofs showing that under mild conditions, these methods will always converge to a stationary point (a point where the slope is zero in all directions).

Datasets

As a theoretical optimization paper, it does not use standard machine learning datasets (like ImageNet). Instead, it evaluates the algorithms using:

  • Simulated Wireless Networks: A $K$-cell network model used to test the WMMSE algorithm for transceiver design.
  • Synthetic Tensor Data: Specifically designed third-order tensors used to test the CANDECOMP/PARAFAC (CP) decomposition, a common task in data mining and multi-way analysis.

Key Insights and Ideas

  • The Power of Surrogates: The "aha" moment is realizing that many famous, seemingly different algorithms are actually doing the same thing: building a local, easy-to-solve upper bound and minimizing it.
  • Curing the "Swamp Effect": In tensor decomposition, algorithms often get stuck in "swamps"—regions where the error barely changes for hundreds of iterations. The authors show that adding a diminishing proximal term (a penalty for moving too far from the current guess that gets smaller over time) can effectively "drain the swamp."
  • Unification: The paper proves that the Expectation Maximization (EM) algorithm and Difference of Convex (DC) programming are just specific flavors of their BSUM framework. This means their new convergence proofs apply to these classic tools as well.

Key Results

  • Theoretical Unification: The authors successfully unified the convergence analysis for BCD, EM, DC, and Proximal Splitting under one mathematical roof.
  • Tensor Decomposition Speedup: In numerical tests for CP decomposition, the authors' "Diminishing Proximal" variant was significantly faster than the industry-standard Alternating Least Squares (ALS).
  • Standard ALS: 277 iterations to converge.
  • Diminishing Proximal BSUM: 78 iterations to converge (a ~3.5x speedup).
  • Robustness: The MISUM variant proved that you can achieve convergence even when subproblems have multiple optimal solutions, a common headache in nonconvex optimization.

Limitations and Future Work

  • Global vs. Local: Like most BCD-style methods, these algorithms converge to stationary points (local minima or saddle points), not necessarily the global minimum. Finding the absolute best solution in a nonconvex landscape remains an open challenge.
  • Requirement for Upper Bounds: BSUM requires finding a global upper bound for the function. While the authors provide a "BSCA" version that relaxes this, BSCA requires the objective function to be smooth (differentiable), which isn't always the case in nonsmooth optimization.
  • Computational Overhead: The "Maximum Improvement" (MISUM) rule requires checking all blocks to see which is best, which can be expensive if there are many blocks. Future work could explore randomized block selection to balance speed and convergence.

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},
}

Loading related content...

Figure