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.

  • Problem

    Traditional general-purpose optimization tools are inadequate for big-data problems because of model complexity, data heterogeneity, and sheer data size.

  • Method

    BSUM generalizes BCD-type algorithms and provides a framework that accounts for existing large-scale optimization algorithms.

  • Results

    The framework is characterized by flexibility and strong theoretical convergence guarantees, with refined convergence rates available under different assumptions.

  • Takeaways & Limitations

    BSUM offers a flexible framework for analyzing and organizing large-scale optimization algorithms.

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.
  • Motivation: 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.
  • 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.
  • 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.
  • 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.
  • 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.

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.
  • The Main Idea: 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.
  • The Main Idea: 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.
  • The Main Idea: 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.
  • 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.
  • 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.

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.
  • Failure modes: 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.
  • Failure modes: 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.
  • Failure modes: 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.
  • 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.

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.
  • General convergence rates: 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.
  • General convergence rates: 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.
  • 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.
  • Relaxations and acceleration: 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.

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: BSUM connects classic BCD, CCCP, MM, EM, PPA, and related methods through specific upper-bound constructions.The framework emphasizes how the choice of upper bound determines the resulting algorithm.
  • BCD: BCD inherits BSUM’s convergence and rate analysis, including sublinear convergence under Assumptions (B1) and (B2).The result addresses general-form BCD algorithms under the stated assumptions.
  • 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.
  • MM and PPA: MM successively minimizes a majorization function that upper-bounds the objective and is tight at the current iterate, placing MM within BSUM.PPA is likewise represented through a proximal upper bound, while alternating PPA yields unique subproblem solutions and convergence to a stationary solution.
  • EM: EM is a BSUM special case through MM: Jensen’s inequality supplies the upper bound, and the M-step minimizes that bound after sign reversal.The bound satisfies the required equality at the current iterate.

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.
  • BSUM connection: The FBS iteration is equivalent to minimizing the BSUM quadratic upper bound with Φ1 := 1.This identifies the forward-backward step with a BSUM update.
  • Block extension: The FBS construction generalizes to multiple blocks, producing the block coordinate proximal gradient method.BCPG has received attention for certain big-data optimization problems such as LASSO.
  • 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.
  • 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.

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.
  • 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.
  • 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.
  • 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.

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.
  • 1) Abundance Estimation in Modern High-Throughput Sequencing Technologies:: 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.
  • 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.
  • 2) Tensor decomposition:: 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.
  • 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.
  • Dictionary learning for sparse representation:: 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.

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.
  • Stochastic optimization: SSUM is guaranteed to converge almost surely to the set of stationary solutions.The guarantee is stated for the resulting SSUM algorithm.
  • Stochastic optimization: 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.
  • Stochastic optimization: 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.
  • Stochastic optimization: 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.

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.
  • B. Coupling constraints: 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.
  • B. Coupling constraints: 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.
  • B. Coupling constraints: 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.
  • B. Coupling constraints: 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.

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.
  • 2) Nonconvex constraints: The iterative constraint approximation restricts the feasible region, so the algorithm’s iterates remain feasible.This feasibility property is illustrated in Figure 9.
  • 2) Nonconvex constraints: Under suitable constraint qualification conditions, the resulting algorithm is guaranteed to converge to stationary solutions.The guarantee is stated for the nonconvex constrained problem.

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.
  • C. Parallel version and extensions to game theory: 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.
  • C. Parallel version and extensions to game theory: 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.
  • C. Parallel version and extensions to game theory: 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.
  • C. Parallel version and extensions to game theory: 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.

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.
  • 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.
  • 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.
  • 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.
  • 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.
Loading 1511.02746v1…