A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing

By Mingyi Hong, Meisam Razaviyayn, Zhi-Quan Tom Luo, Jong-Shi Pang. 2015

402 citations recorded by the source corpus.

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) method, the convex-concave procedure (CCCP) method, the block coordinate proximal gradient (BCPG) method, the nonnegative matrix factorization (NMF) method, the expectation maximization (EM) method, etc. 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.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Ji Liu
2. Cho-Jui Hsieh
3. Xiangru Lian
4. Huan Zhang
5. Mingyi Hong
6. Albert S. Berahas
7. Rui Zhang
8. Qingqing Wu

In Computational Mathematics

1. Rui Zhang
2. Qingqing Wu
3. Yong Zeng
4. Cho-Jui Hsieh
5. Mingyi Hong
6. Albert S. Berahas
7. Ji Liu

In Computational Mechanics

1. Ji Liu
2. Xiangru Lian
3. Albert S. Berahas
4. Mingyi Hong
5. Cho-Jui Hsieh
6. Yijun Huang
7. Huan Zhang
8. Rui Zhang

Citations in the corpus

• Deep Learning for Distributed Optimization: Applications to Wireless Resource Management (2019, background): “For instance, a successive approximation framework [2] for a non-convex problem requires a proper convex approximation, which usually lacks a generic design technique.”
• A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, background): “One of core theoretical questions is how much speedup (or benefit) the asynchronous parallelization can bring us.”
• Accessing From the Sky: A Tutorial on UAV Communications for 5G and Beyond (2019, methodology): “[144] M.”
• Intelligent Reflecting Surface Enhanced Wireless Networks: Two-Timescale Beamforming Optimization (2019, methodology): “In the outer loop, we update the dual variable associated with the constraint v = u and the penalty parameter (as will be introduced later in this subsection), while in the inner loop, we apply the block successive upper-bound minimization (BSUM) method [37] to iteratively optimize the primal variab”
• Prox-PDA: The Proximal Primal-Dual Algorithm for Fast Distributed Nonconvex Optimization and Learning Over Networks (2017, background): “Such a finite sum problem plays a central role in machine learning and signal/information processing (Cevher et al., 2014; Hong et al., 2016).”
• Common Throughput Maximization in UAV-Enabled OFDMA Systems With Delay Consideration (2018, methodology): “Note that the conventional block coordinate descent method alternately optimizes one block of optimization variables in each iteration while keeping other blocks of optimization variables fixed, until the convergence is achieved [31], [32].”
• Intelligent Resource Slicing for eMBB and URLLC Coexistence in 5G and Beyond: A Deep Reinforcement Learning Based Approach (2020, neutral): “An -optimal solution is defined as (x∗,p∗, z∗) ∈ {x,p, z|x ∈ X ,p ∈ P , z ∈ Z,G(x,p, z) − G(x̄, p̄, z̄)}, where G(x̄, p̄, z̄) is globally optimal [28].”
• Intelligent Reflecting Surface Meets OFDM: Protocol Design and Rate Maximization (2019, background): “Moreover, the obtained solution to (P1) can be shown to be at least a locally optimal solution based on [22].”
• Joint Trajectory and Communication Design for Multi-UAV Enabled Wireless Networks (2017, methodology): “In the following, we propose an efficient iterative algorithm for the relaxed problem (16) by applying the block coordinate descent [30] and successive convex optimization techniques.”
• Balancing Communication and Computation in Distributed Optimization (2017, methodology): “Coordinate descent type methods, in either primal or dual space, have also been used in the distributed setting [31]–[33].”
• Constrained Deep Learning for Wireless Resource Management (2019, background): “For several decades, there have been significant progresses in nonconvex optimization techniques for signal processing and wireless communication systems [1], [2].”
• Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions (2016, neutral): “, 2011), and proximal gradient descent methods (Parikh and Boyd, 2014) (see also (Cevher et al., 2014; Hong et al., 2016) and references therein).”
• A Stochastic Large-scale Machine Learning Algorithm for Distributed Features and Observations (2018, neutral): “Block successive upper bound minimization (BSUM)Hong et al. (2015) is one of the methods working for datasets with distributed features, where the master node spreads all parameters and each worker node conducts parameter updates on a randomly chosen and non-overlapping subset of the feature vector.”