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

Meisam Razaviyayn; Mingyi Hong; Zhi-Quan Luo

Source-linked AI summary

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

Meisam Razaviyayn, Mingyi Hong, Zhi-Quan Luo

arXiv:1209.2385v1Sep 11, 2012math.OC

TL;DR

Exact BCD updates can require restrictive unique-subproblem solutions, particularly for nonsmooth or nonconvex objectives. The paper analyzes inexact BCD methods based on successive upper-bound or convex local approximations and unifies convergence results across several classical algorithms.

Problem
Exact BCD convergence can require uniquely solving each block subproblem, requirements that are restrictive for practical nonsmooth and nonconvex problems.
Method
The paper studies inexact BCD methods that successively minimize locally tight upper bounds or convex local approximations using several block-update rules.
Results
The framework provides convergence analysis for both successive approximation strategies and unifies and extends results for BCD, DC, EM, and alternating proximal minimization algorithms.
Takeaways & Limitations
Successive minimization of carefully chosen approximations offers a common convergence framework for a broad class of inexact BCD algorithms.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper develops a unified convergence analysis for inexact BCD methods that successively optimize approximations of nonsmooth and nonconvex objectives. This framework addresses restrictive exact-subproblem requirements and unifies convergence results for several classical algorithms.

BCD updates one variable block at a time while holding the remaining blocks fixed.
Convergence of classical BCD typically requires a unique block minimizer or quasi-convexity, and without these assumptions iterates may avoid stationary points.
These requirements can be restrictive because some practical block subproblems are nonconvex and nondifferentiable, including tensor decomposition and wireless-network sum-rate maximization.
The proposed inexact BCD framework successively minimizes approximate objective functions rather than requiring exact solutions of the original block subproblems.
Two approximation strategies are analyzed: locally tight upper bounds and convex local approximations, together with cyclic, Gauss-Southwell, and overlapping essentially cyclic updates.
The analysis unifies and extends convergence results for BCD, DC, EM, and alternating proximal minimization methods.

III. SUCCESSIVE UPPER-BOUND MINIMIZATION (SUM)

SUM minimizes successive approximations of the objective, using global upper bounds that are tight and locally first-order consistent with the original function. Under mild assumptions, its limit points are stationary, and compact level sets yield global convergence to the stationary-point set.

Algorithm: SUM groups all variables into one block and minimizes a sequence of approximate objective functions instead of directly solving the original problem.The approach is intended for objectives that may be nonconvex or nonsmooth.
Approximation conditions: The approximation is chosen as a global upper bound of the objective, with tightness and matching first-order behavior imposed through regularity conditions.Continuity and sufficient conditions for decomposing smooth and nonsmooth parts support these requirements.
Relation to prior methods: SUM handles nonsmooth objectives, unlike the compared inner approximation algorithm, which is described as applicable only to smooth objectives.The paper also states that the assumptions used for SUM are weaker than those used for convergence of the inner approximation algorithm.
Convergence: Every limit point of the iterates generated by SUM is a stationary point under Assumption 1.The proof uses the upper-bound and tightness conditions together with first-order consistency.
Convergence: If the initial level set is compact, the SUM iterates converge globally to the set of stationary points.The result is obtained under compactness of the level set and Assumption 1.

IV. THE BLOCK SUCCESSIVE UPPER-BOUND MINIMIZATION ALGORITHM

BSUM extends successive upper-bound minimization to block-structured variables by updating one block at a time with a locally tight upper bound. Under quasi-convexity or compact-level-set conditions and suitable uniqueness and regularity assumptions, its limit behavior reaches coordinatewise minima or stationary points.

Algorithm: BSUM exploits a decomposition of the optimization variable into blocks and updates a selected block while holding the others fixed.The method uses cyclic updates, with convergence results extendable to essentially cyclic rules.
Approximation conditions: Each block subproblem minimizes an approximation that upper-bounds the original objective in that block and matches its directional derivative along block directions.A sufficient construction separates a continuously differentiable component from a directionally differentiable component.
Convergence results: With quasi-convex block approximations, unique subproblem solutions, and Assumption 2, every limit point is a coordinatewise minimum; regularity makes it stationary.This is the first convergence part of the BSUM result.
Convergence results: With compact level sets, unique solutions for at least n −1 blocks, and regularity on the stationary-point set, the iterates converge to that set.The convergence is stated as lim r→∞ d(xr, X ∗) = 0.
Connections: The BSUM convergence result extends existing block coordinate descent results and implies global convergence for algorithms including EM and DC methods under Gauss-Seidel updates.These implications are stated for several existing algorithms discussed later in the paper.

V. THE MAXIMUM IMPROVEMENT SUCCESSIVE UPPER-BOUND MINIMIZATION ALGORITHM

MISUM relaxes BSUM’s unique-subproblem requirement by updating the block with maximum improvement, while retaining convergence guarantees under the stated assumptions.

The uniqueness assumption is identified as necessary even for the simple BCD method, while related maximum-improvement updating permits multiple per-block solutions.
MISUM updates the block providing the maximum improvement and uses approximate subproblem solutions.It is presented as a more general alternative to the MBI method.
Every MISUM limit point is a coordinatewise minimum, and it is stationary when f is regular at that point.
The MISUM convergence proof establishes coordinatewise optimality through non-increasing objective values and blockwise first-order conditions.
Unlike BSUM, MISUM does not require unique subproblem minimizers, but it minimizes over all blocks at each iteration.This makes each iteration more expensive, although all block minimizations can be performed simultaneously with parallel units.

VI. SUCCESSIVE CONVEX APPROXIMATION OF A SMOOTH FUNCTION

BSCA minimizes strictly convex block approximations and uses an Armijo step size rule when direct approximation minimization may not decrease the objective.

The approximation functions need not be global upper bounds when they satisfy the stated first-order approximation condition.
BSCA constructs a search direction by minimizing a strictly convex approximation for the selected block and applies Armijo step-size selection.The resulting algorithm is named Block Successive Convex Approximation.
Directly optimizing local approximations may fail to decrease the objective, so BSCA combines the resulting minimizer with a search direction and sufficient-decrease step.
Every limit point generated by BSCA is stationary when f is continuously differentiable and the approximation is strictly convex and continuous.
BSCA allows more general strictly convex approximations than coordinate gradient descent but covers only smooth objectives.

VII. OVERLAPPING ESSENTIALLY CYCLIC RULE

The overlapping essentially cyclic rule updates nonempty groups of blocks over a fixed period, extending convergence results for BSUM and BSCA.

At each iteration, a nonempty group of variable blocks is selected, and the update rule is essentially cyclic with period T.
The rule is more general than the essentially cyclic rule because updated blocks may overlap.
For BSUM, every limit point is a coordinatewise minimum and becomes stationary when f is regular with respect to the updated blocks.
Under compact level sets and the stated assumptions, BSUM iterates converge to the set of stationary points: lim r→∞ d(xr, X ∗) = 0.
For BSCA, every limit point remains stationary under smoothness, the first-order approximation condition, strict convexity, and the overlapping rule.
The overlapping essentially cyclic rule does not apply to MISUM’s improvement-based ordering, although MISUM’s convergence proof still extends to overlapping blocks.

VIII. APPLICATIONS

The paper states that this section provides applications of the algorithms proposed in the preceding sections.

The section provides several applications of the algorithms proposed in the previous sections.

A. Linear Transceiver Design in Cellular Networks

The BSUM approach transforms cellular sum-rate maximization into an equivalent formulation and applies block updates that converge to a stationary solution despite shared power constraints.

The cellular-network problem seeks transmit beamformers that optimize users’ sum rates under per-base-station transmit-power constraints.
The original problem is NP-hard, so the analysis targets a stationary solution rather than a globally optimal one.
Users sharing a base station create a common power constraint, preventing straightforward cyclic BSUM updates because blockwise constraint separability fails.
An equivalent reformulation introduces mean-square-error variables and upper bounds, enabling application of the BSUM algorithm.
The resulting WMMSE algorithm converges to a stationary solution of the reformulated problem.
Each BSUM iteration decomposes into K independent convex subproblems, solvable in closed form subject to an efficient bisection search.

B. Proximal Minimization Algorithm

The alternating proximal minimization algorithm resolves nonunique block subproblems by adding strictly convex proximal terms, and the unified analysis establishes convergence under broader conditions.

When blockwise objectives are convex but not strictly convex, ordinary BCD may fail to find a stationary solution because subproblems can have multiple solutions.
Alternating proximal minimization adds a proximal term so each block subproblem has a unique solution through strict convexity.
The proximal minimization procedure is a SUM instance because its surrogate is an upper bound satisfying the required assumptions.
The method converges to a stationary solution of problem (49).
The result extends prior alternating proximal-minimization analysis to nonsmooth objectives and iteration-dependent proximal coefficients.

C. Proximal Splitting Algorithm

The forward-backward splitting method is represented as a SUM or BSUM procedure through upper-bound surrogates, yielding stationary-solution convergence for single- and multi-block problems.

The two-function problem assumes a closed convex feasible set, a convex lower-semicontinuous term, and a convex term with Lipschitz-continuous gradient.
For a composite objective, the forward-backward iteration can be rewritten through the proximal operator and an upper-bound surrogate.
Under these assumptions, forward-backward splitting is a special case of the SUM algorithm.
The block forward-backward extension uses blockwise Lipschitz constants and admissible stepsizes γ ∈[ǫ_i, 2/β_i −ǫ_i].
The block forward-backward splitting algorithm converges to a stationary solution of problem (56).

D. CANDECOMP/PARAFAC Decomposition of Tensors

The BSUM framework is applied to CP tensor decomposition to address ALS stagnation, showing that a diminishing proximal coefficient can accelerate convergence while preserving guarantees.

CP decomposition represents a tensor as a sum of rank-one tensors, and ALS cyclically updates its factor blocks through least-squares subproblems.
A known ALS drawback is the swamp effect, in which the objective remains nearly constant for many iterations before decreasing.
Adding proximal terms to the factor updates can reduce the swamp effect, and decreasing the proximal weight λ during iterations can improve convergence.
The proposed λ update substantially reduces the swamp effect and significantly improves ALS convergence in numerical experiments.
Theorem 2 guarantees convergence even when the proximal coefficient changes during iterations, beyond the scope of the earlier result in.
Figure 6 compares objective value against iteration number for ALS, Constant Proximal, Diminishing Proximal, MBI, and MISUM.
Table I reports average iterations to reach objective value ϵ = 10^-5 over 1000 Monte-Carlo runs with different initializations.
The experiments show that adding a diminishing proximal term significantly improves ALS convergence speed.

E. Expectation Maximization Algorithm

The paper places EM within the SUM framework and extends the convergence perspective to block-coordinate EM updates. It also relates CCCP and its block-coordinate form to SUM and BSUM convergence results.

EM is a special case of the SUM algorithm, so the SUM results imply convergence for EM.The connection follows from the stated smoothness assumption and Proposition 1.
The convergence result also applies to EM with Gauss-Seidel or coordinatewise updates under Theorem 2’s assumptions.In block coordinate EM, only one parameter block is updated at each M-step.
Block coordinate EM updates are motivated by the difficulty of solving EM’s full M-step when the corresponding per-block problems are easier.
The paper states that the block coordinate EM algorithm and its convergence behavior had not been analyzed previously.
CCCP uses a tight convex upper bound and is therefore a special case of SUM; block-coordinate CCCP is likewise a special case of BSUM.The paper states that Theorem 1 guarantees CCCP convergence under certain assumptions, while Theorem 2 guarantees convergence for its block-coordinate form.