PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data

Mingyi Hong, Meisam Razaviyayn, Zhi-Quan Luo, Jong-Shi Pang

arXiv:1511.02746v1math.OC

TL;DR

Big-data optimization challenges arise from model complexity, data heterogeneity, and sheer data size. The paper presents BSUM, a generalization of BCD-type algorithms, and emphasizes its flexibility and theoretical convergence guarantees.

Abstract

from arXiv · show

This article presents a powerful algorithmic framework for big data optimization, called the Block Successive Upper bound Minimization (BSUM). The BSUM includes as special cases many well-known methods for analyzing massive data sets, such as the Block Coordinate Descent (BCD), the Convex-Concave Procedure (CCCP), the Block Coordinate Proximal Gradient (BCPG) method, the Nonnegative Matrix Factorization (NMF), the Expectation Maximization (EM) method and so on. In this article, various features and properties of the BSUM are discussed from the viewpoint of design flexibility, computational efficiency, parallel/distributed implementation and the required communication overhead. Illustrative examples from networking, signal processing and machine learning are presented to demonstrate the practical performance of the BSUM framework

I. INTRODUCTION

Big-data applications create optimization problems with massive scale, complex and heterogeneous models, and demands for efficient, accurate, distributed computation. The article introduces BSUM as a flexible framework that unifies block-structured algorithms and examines their theory, implementation, and applications.

Motivation

  • Large-scale problems in areas such as image processing, social-network analysis, computational biology, and wireless communications can involve millions or billions of variables.These applications require fast, accurate solutions and, in some cases, real-time resource-allocation decisions.Source: A. Overview of optimization for big data · p. 2
  • Traditional general-purpose optimization tools are inadequate because of model complexity, data heterogeneity, and sheer data size.The paper motivates algorithms designed specifically for large-scale settings.Source: A. Overview of optimization for big data · p. 2

Algorithmic requirements

  • Big-data optimization methods should use simple computational steps, store intermediate results easily, support distributed or parallel execution, and reach high-quality solutions in few iterations.These requirements are tied to modern multi-core, cluster, and distributed-storage infrastructures.Source: A. Overview of optimization for big data · p. 2

Block Coordinate Descent

  • BCD partitions variables into blocks and optimizes one or a few blocks per iteration while holding the others fixed.The paper presents BCD as simple, intuitive, and applicable to nonsmooth nonconvex problems across signal processing, communications, and machine learning.Source: B. The Block Coordinate Decent Method · pp. 2–3

Article scope

  • The article develops BSUM theory, surveys large-scale algorithms and applications within the framework, and discusses extensions and computational issues such as parallelism, distributed computation, and communication overhead.Examples come from practical problems in networking, signal processing, and machine learning.Source: C. The Block Successive Upper Bound… · p. 4

BSUM framework

  • BSUM generalizes BCD by successively optimizing upper-bound or surrogate functions, thereby covering methods including EM, CCCP, NMF, and interference-management algorithms.The framework is presented as a platform for understanding algorithm design, convergence, computational efficiency, and parallel or distributed implementation.Source: C. The Block Successive Upper Bound… · p. 4

II. BSUM AND ITS THEORETICAL PROPERTIES

BSUM generalizes block-wise optimization by minimizing upper-bound approximations, while encompassing cyclic BCD and supporting flexible block-selection rules. Under stated regularity, approximation, and subproblem conditions, its limit points are stationary, although coordinatewise minima need not be stationary.

The Main Idea

  • Direct BCD subproblem minimization can be difficult for nonconvex objectives and may fail to converge even when exact minimization is possible.These issues motivate the framework’s convergence analysis and its allowance for approximate subproblem solutions.Source: A. The Main Idea · pp. 4, 5, 7
  • BSUM updates selected blocks by approximately minimizing upper-bound functions of the objective at the current iterate.The framework permits multiple selected blocks and approximate solutions to subproblems.Source: A. The Main Idea · p. 5
  • When one cyclic coordinate is selected and no approximation is used, BSUM reduces to classical cyclic BCD.Other coordinate-selection rules are also covered by the framework.Source: A. The Main Idea · p. 5
  • Upper-bound approximations are designed to globally majorize the objective and match its first-order behavior at the approximation point.The stated assumptions include upper-bound and first-order agreement properties.Source: A. The Main Idea · pp. 5–7

Optimality Conditions

  • A coordinatewise minimum need not be stationary, so the analysis focuses primarily on stationary solutions.For the illustrated convex example, (-4, 3) is coordinatewise minimal but not stationary, whereas (0, 0) is the unique stationary and global optimal solution.Source: B. When does the BSUM converge? · p. 9

When does the BSUM converge?

  • With cyclic selection, regular iterates, Assumption A, and suitable unique subproblem solutions, every BSUM limit point is stationary and the sequence can converge to the stationary-point set.The theorem gives the limit-point result under quasi-convex approximations and a stronger set-convergence result under compactness and uniqueness conditions.Source: B. When does the BSUM converge? · p. 10

C. When does BSUM fail?

BSUM can fail to converge or make progress when regularity, feasible-set structure, approximation conditions, or subproblem uniqueness are absent. The examples motivate conservative upper bounds and other modifications to avoid pathological behavior.

Failure modes

  • BSUM can fail to converge to stationary solutions under several missing assumptions, including regularity, Cartesian feasible sets, valid approximation conditions, and unique subproblem solutions.The section presents separate examples for nonconvergence, stagnation, divergence, and cycling.Source: C. When does BSUM fail? · pp. 11–12
  • A coordinatewise minimum need not be stationary and can be far from the only stationary solution, such as (−4, 3) versus (0, 0).The examples distinguish coordinatewise optimality from stationarity.Source: C. When does BSUM fail? · p. 11
  • With a coupled constraint x1 + x2 = 2, BSUM can remain stuck at (0, 2) because changing either single block violates feasibility.The problem's optimal objective value is 2, but the single-block updates cannot move from the initialization.Source: C. When does BSUM fail? · p. 11
  • Without bounded feasible sets, BSUM can diverge, while without unique subproblem solutions, cyclic updates can cycle among six nonstationary points.The cycling example attributes the pathology to multiple optimal solutions in at least two subproblems.Source: C. When does BSUM fail? · p. 12

Remedies

  • The paper recommends less-greedy, conservative block updates through suitable upper bounds; proximal bounds can yield unique solutions, and randomization can address non-uniqueness.For some examples, a generalized BSUM is required; for another, a better upper bound is sufficient.Source: C. When does BSUM fail? · pp. 12–13

D. How fast does the BSUM converge?

Under stated assumptions, BSUM generally achieves sublinear convergence, with faster rates available for stronger structure and selected variants. The analysis also identifies assumption relaxations and acceleration results for particular settings.

General convergence rates

  • Under Assumptions A and B, BSUM finds an ϵ-optimal solution within at most c/ϵ iterations for all coordinate rules in Table II.The constant c depends only on the problem description.Source: D. How fast does the BSUM converge? · p. 14
  • For some special BSUM forms, the constant multiplying 1/ϵ can be refined so it is independent of problem dimension.The paper cites this as a refinement of the general sublinear rate.Source: D. How fast does the BSUM converge? · p. 14
  • For strongly convex objectives or certain special convex structures, BSUM achieves a linear rate of O(log(c/ϵ)) iterations.This rate is described as faster than the general sublinear rate.Source: D. How fast does the BSUM converge? · p. 14

Relaxations and acceleration

  • Dropping per-block strong convexity can still yield O(1/ϵ) sublinear convergence, while removing convexity permits convergence-rate characterizations for stationary solutions.These results relax parts of Assumption B rather than the full framework.Source: D. How fast does the BSUM converge? · p. 14
  • With two variable blocks, cyclic BSUM can achieve O(1/√ϵ) complexity, and randomized selection with quadratic upper bounds can accelerate versions with more than two blocks.The latter result is stated for any n > 2 blocks.Source: D. How fast does the BSUM converge? · p. 14

III. ALGORITHMS COVERED BY THE BSUM FRAMEWORK

BSUM provides a unified upper-bound framework that contains several established optimization algorithms as special cases. Its design choices recover different methods while extending convergence guarantees to settings including block updates and proximal regularization.

Framework connections

BCD

CCCP

  • CCCP is a single-block BSUM method using the linear upper bound, and its updates can also be organized blockwise.The CCCP upper bound is formed from the convex-concave decomposition.Source: B. The Convex-Concave Procedure (CCCP) · p. 15

MM and PPA

EM

E. The Forward-Backward Splitting (FBS) Algorithm

The forward-backward splitting method is represented in BSUM through a quadratic upper bound and extends naturally to block-coordinate problems. Under Assumption B, its block-coordinate form has a sublinear convergence rate.

FBS formulation

  • FBS solves a single-block composite problem with a convex nonsmooth term and a smooth term having Lipschitz-continuous gradient.The method is also called the proximal splitting algorithm.Source: E. The Forward-Backward Splitting… · p. 17

BSUM connection

Block extension

Convergence

  • The BCPG method has a sublinear convergence rate for any coordinate selection rule in Table II when solving problem (5) under Assumption B.The rate follows from the general BSUM convergence-rate result.Source: E. The Forward-Backward Splitting… · p. 18

NMF example

  • NMF multiplicative updates are covered by BSUM when the iterates satisfy the stated positivity conditions.The updates arise from quadratic upper bounds whose block subproblems have unique solutions.Source: F. The Nonnegative Matrix… · pp. 18–19

G. The Iterative Reweighted Least Squares (IRLS) Method

The paper places IRLS and weighted transceiver-design updates within BSUM by constructing tractable upper bounds. These constructions support stationary-point convergence and, in the wireless example, closed-form iteration steps.

IRLS

  • IRLS is a single-block BSUM algorithm because its surrogate is an upper bound for the smooth objective.The paper states that the framework can generalize IRLS to multiple blocks.Source: G. The Iterative Reweighted Least… · p. 20

Wireless communication

  • Wireless transceiver design is formulated as a nonconvex, NP-hard sum-rate optimization problem under user power constraints.The formulation is rewritten using the relationship between SINR and MSE.Source: A. Wireless communication and… · p. 21

WMMSE construction

  • A linear upper bound produces a valid BSUM approximation whose iterations reduce to quadratic programs with closed-form solutions.The optimization variable is the collection of transmit and receive beamformers.Source: A. Wireless communication and… · p. 21

WMMSE results

  • WMMSE converges to a stationary point and typically converges in a few iterations even for large-size problems.WMMSE is the resulting weighted minimization of mean square error algorithm.Source: A. Wireless communication and… · p. 21

1) Abundance Estimation in Modern High-Throughput Sequencing Technologies:

The BSUM framework is illustrated across abundance estimation, tensor decomposition, and dictionary learning. In these applications, upper-bound or proximal choices address computational cost, convergence, or stagnation while retaining practical implementations.

1) Abundance Estimation in Modern High-Throughput Sequencing Technologies:

  • Abundance estimation models transcript levels from noisy sequencing reads and applies an EM-style locally tight upper bound.Jensen’s inequality validates the bound, and its closed-form solution makes each iteration computationally efficient.Source: 1) Abundance Estimation in Modern… · pp. 22–23
  • The abundance-estimation algorithm converges in a few iterations and supports distributed storage and multi-core machines.Reads can be partitioned across processing units, which update global estimates through consensus.Source: 1) Abundance Estimation in Modern… · p. 23

2) Tensor decomposition:

  • ALS applies block coordinate updates to CP decomposition, but convergence is not always guaranteed because block minimizers may be nonunique.The paper also identifies the ALS swamp effect, where the objective remains nearly constant for many iterations.Source: 2) Tensor decomposition · pp. 23–24
  • Proximal upper bounds can reduce ALS’s swamp effect, and the resulting modification remains a BSUM special case with guaranteed theoretical convergence.Figure 5 reports less swamp effect for proximal ALS than for naive ALS.Source: 2) Tensor decomposition · p. 24

Dictionary learning for sparse representation:

  • In dictionary learning, BSUM replaces costly exact sparse-recovery steps with easier locally tight upper-bound minimizations.Quadratic upper bounds with diagonal matrices yield closed-form updates.Source: 1) Dictionary learning for sparse… · p. 25
  • The dictionary-learning algorithm is theoretically guaranteed to converge to stationary solutions and performs favorably for noisy image denoising.It achieves larger PSNR values than K-SVD at high noise levels, with fewer visual artifacts and closed-form steps.Source: 1) Dictionary learning for sparse… · pp. 25–26

2) Sparse linear discriminant analysis:

The section presents stochastic upper-bound minimization for large-scale and streaming optimization, emphasizing SSUM’s almost-sure convergence and lower running time than SAA in a wireless design example.

Stochastic optimization

  • SSUM minimizes successive upper bounds of stochastic objectives, using an approximation that upper-bounds each sample function around the previous iterate.The resulting method is called stochastic successive upper bound minimization.Source: A. Stochastic optimization · p. 28
  • SSUM is guaranteed to converge almost surely to the set of stationary solutions.The guarantee is stated for the resulting SSUM algorithm.Source: A. Stochastic optimization · p. 28
  • Stochastic optimization suits big-data settings where the full data set is unavailable initially and observations arrive over time.The section also notes that very large sum-cost problems make batch processing difficult.Source: A. Stochastic optimization · pp. 28–29
  • In wireless transceiver design with uncertain channel coefficients, applying SSUM to the stochastic counterpart yields the stochastic WMMSE algorithm.The channel coefficients are modeled as random variables, and the upper bound leads to stochastic WMMSE.Source: A. Stochastic optimization · p. 29
  • The SAA algorithm has much longer running time than SSUM in the reported wireless transceiver experiment.SAA requires solving a nonconvex optimization problem at each iteration, whereas the figure compares its running time with SSUM.Source: A. Stochastic optimization · p. 29

B. Coupling constraints

The BSUM framework is extended to linearly coupled constraints through BSUMM, enabling distributed and parallel optimization while retaining convergence under regularity assumptions.

B. Coupling constraints

  • BSUMM replaces augmented-Lagrangian blocks with tight upper bounds and is guaranteed to converge to the global optimum under regularity assumptions.The method is named Block Successive Upper Bound Minimization Method of Multipliers.Source: 1) Linear coupling · pp. 30–31
  • The routing application maximizes the minimum rate across data flows subject to link-capacity and flow-conservation constraints.The resulting formulation is a linear program, with each flow required to meet the minimum-rate variable.Source: 1) Linear coupling · pp. 31–32
  • Replicated link and flow variables decouple subnetworks, allowing BSUMM subproblems to be solved in parallel while equality is enforced asymptotically.The replicated variables are tied to the originals through linear coupling constraints.Source: 1) Linear coupling · pp. 32–33
  • A careful BSUMM implementation allows network controllers to compute asynchronously without coordinating their computation.The section states that this asynchrony has potential to greatly improve computational efficiency.Source: 1) Linear coupling · p. 33
  • For M = 200, asynchronous BSUMM with a small number of network controllers outperforms the other compared algorithms.The numerical results further suggest that network decomposition and asynchronous implementation are critical for fast convergence.Source: 1) Linear coupling · p. 33

2) Nonconvex constraints:

The framework handles nonconvex constraints by iteratively replacing them with locally tight upper bounds, keeping iterates feasible and converging to stationary solutions under constraint qualifications.

2) Nonconvex constraints

  • Nonconvex constraint functions are replaced iteratively by local tight upper bounds in the constraint set.The update imposes the upper-bound functions as the constraints at each iteration.Source: 2) Nonconvex constraints · p. 34
  • The iterative constraint approximation restricts the feasible region, so the algorithm’s iterates remain feasible.This feasibility property is illustrated in Figure 9.Source: 2) Nonconvex constraints · p. 34, Figure 9 · p. 35
  • Under suitable constraint qualification conditions, the resulting algorithm is guaranteed to converge to stationary solutions.The guarantee is stated for the nonconvex constrained problem.Source: 2) Nonconvex constraints · p. 34

C. Parallel version and extensions to game theory

The section develops parallel BSUM extensions, explains their distributed implementation and convergence safeguards, and connects them to multi-agent and game-theoretic optimization.

C. Parallel version and extensions to game theory

  • Naive parallel block-coordinate updates may fail to converge and can produce zig-zagging, oscillation, or divergence.The text gives a convex problem with bounded feasible set whose naive iteration alternates indefinitely.Source: C. Parallel version and extensions to… · p. 35
  • PSCA uses approximation functions to obtain computationally efficient updates for nonconvex objectives in parallel multi-block optimization.PSCA is summarized as a parallel successive convex approximation algorithm.Source: C. Parallel version and extensions to… · pp. 35–36
  • PSCA can model multi-agent optimization and game-theoretic settings in which agents update variables or players use best responses.Convergence is guaranteed for some classes of games under regularity assumptions on utility functions.Source: C. Parallel version and extensions to… · p. 36
  • Parallelization can improve efficiency, but convergence speed does not increase linearly with processor count.Beyond a certain number of processors, convergence becomes slower because of increased communication overhead.Source: C. Parallel version and extensions to… · p. 36
  • In distributed LASSO, each processing core updates one block using local information, while nodes broadcast A_i x_i to form shared quantities.Each node need not possess the complete matrix A.Source: C. Parallel version and extensions to… · pp. 36–37

D. Practical Considerations

BSUM design choices govern convergence, solvability, and parallel efficiency. The framework offers flexibility across update rules and implementations, but performance and convergence depend on problem structure, communication overhead, and constraint type.

Upper-bound choice

  • A good upper bound should ensure convergence, exploit problem structure, and produce easily solvable, preferably closed-form, subproblems.A simple proximal bound may fail to decompose subproblems over variables in transceiver design.Source: D. Practical Considerations · pp. 37–38

Block-update rules

  • Update-rule performance is problem dependent: cyclic, randomized, MBI, and G-So rules can have different convergence behavior across applications.For convex problems, deterministic rules can provide worst-case rates, while randomized rules provide averaged or high-probability convergence guarantees; nonconvex rate theory remains limited.Source: D. Practical Considerations · p. 38

Parallelization

  • Parallelization depends on data structure and algorithm settings, including block availability, submatrix eigenvalues, problem separability, sparsity, and the degree of parallelization.When suitable conditions are absent, alternatives include decomposable upper bounds with stepsize-free updates or diminishing stepsizes.Source: D. Practical Considerations · p. 38

Communication overhead

  • Parallel BSUM convergence does not scale linearly with computational nodes because communication delay can offset additional computation.This motivates analyzing the computation/communication trade-off and choosing the number of cores accordingly; asynchronous implementations are posed as an open direction for reducing waiting overhead.Source: §VI · p. 39

Open research problems

  • Extending block-wise BSUM to nonlinear coupling constraints remains an open problem because naive block-coordinate extensions can fail even for convex problems.Lagrangian approaches typically introduce double-loop algorithms and slow subgradient steps in the dual space.Source: §VI · p. 39

Related papers

Loading 1511.02746v1…