A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization
By Meisam Razaviyayn, Mingyi Hong, Zhi-Quan Tom Luo. 2012
1,321 citations recorded by the source corpus.
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 of each block variable needs to be solved to its unique global optimal. Unfortunately, this requirement is 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$. The main contributions of this work include the characterizations of the convergence conditions for a fairly wide class of such methods, especially for the cases where the objective functions are either nondifferentiable or nonconvex. Our results unify and extend the existing convergence results ...
Subfields: Computational Mathematics, Computational Mechanics, Numerical Analysis, Mathematical Optimization
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mathematics
- Andrzej S. Cichocki
- Anh Huy Phan
- Julien Mairal
- Wotao Yin
- Qibin Zhao
- Yangyang Xu
- Danilo P. Mandic
- Zhi-Quan Tom Luo
In Computational Mechanics
- Mingyi Hong
- Francis R. Bach
- Julien Mairal
- Jason D. Lee
- Wotao Yin
- Zhi-Quan Tom Luo
- Peter Richtárik
- Meisam Razaviyayn
In Numerical Analysis
- Julien Mairal
- Zhi-Quan Tom Luo
- Jong-Shi Pang
- Mingyi Hong
- D. P. Palomar
- Wotao Yin
- Francis R. Bach
- Gesualdo Scutari
In Mathematical Optimization
- Julien Mairal
- Zhi-Quan Tom Luo
- D. P. Palomar
- Jong-Shi Pang
- Gesualdo Scutari
- Mingyi Hong
- Francis R. Bach
- Francisco Facchinei
Citations in the corpus
- Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, background): “Alternating optimization converges to a local optimum under mild technical conditions, see (Tseng, 2001; Tseng and Yun, 2009; Razaviyayn et al., 2013).”
- Federated Multi-Task Learning (2017, background): “MOCHA is based on a bi-convex alternating approach, which is guaranteed to converge [17, 45] to a stationary solution of problem (1).”
- Group Knowledge Transfer: Collaborative Training of Large CNNs on the Edge (2020, background): “The essence of GKT is that it reformulates FL as an alternating minimization (AM) approach [14, 15, 16, 17, 18, 19], which optimizes two random variables (the edge model and the server model) by alternatively fixing one and optimizing another.”
- Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “We note that other majorization-minimization algorithms have recently been analyzed, such as block coordinate variants in [34, 42] and stochastic ones in [11, 35, 43].”
- Guaranteed Matrix Completion via Non-Convex Factorization (2014, methodology): “Algorithm 3 belongs to the class of BSUM methods [55].”
- Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization (2014, methodology): “The use of general approximation instead of the linear/proximal approximation offe rs more flexibility and results in efficient algorithms for particular practical problems; se e [21,24] for specific examples.”
- Parallel Selective Algorithms for Nonconvex Big Data Optimization (2014, neutral): “In [14] the authors consider the minimization of a possibly nonsmooth function by Gauss-Seidel methods whereby, at each iteration, a single block of variables is updated by minimizing a global upper convex approximation of the function.”
- Weighted Sum-Rate Maximization for Reconfigurable Intelligent Surface Aided Wireless Networks (2019, methodology): “Specially, low-complexity updating rules for block W and block θ based on the the prox-linear BCD update rule [46] and the SCA method [31], respectively.”
- Group Knowledge Transfer: Federated Learning of Large CNNs at the Edge (2020, background): “The essence of FedGKT is that it reformulates FL as an alternating minimization (AM) approach [13, 14, 15, 16, 17, 18], which optimizes two random variables (the edge model and the server model) by alternatively fixing one and optimizing another.”
- Parallel and Distributed Methods for Constrained Nonconvex Optimization—Part I: Theory (2016, background): “We remark that the proposed parallel and distributed decomposition across the cells naturally matches modern multi-tiers network architectures wherein high-speeds wired links are dedicated to coordination and data exchange among BSs.”
- Support points (2016, background): “Moreover, h is continuous, with its directional derivative h ′ ({xj}j=1,d; {xj}j=1) equal to the directional derivative Ê ({xj}j=1,d) for all feasible directions d ∈ R, which satisfies assumptions (A3) and (A4) in [56].”
- Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning (2017, methodology): “For a comprehensive analysis of the above-described extensions, we refer the reader to [69], [70], [72], and [73].”
- Tensor Decompositions for Signal Processing Applications: From two-way to multiway component analysis (2014, background): “The convergence of ALS is not yet completely understood — it is quasi-linear close to the stationary point [55], while it becomes rather slow for ill-conditioned cases; for more detail we refer to [56], [57].”
- On the Linear Convergence of the Approximate Proximal Splitting Method for Non-smooth Convex Optimization (2014, background): “Other relevant works are [16, 23] which provide the convergence analysis for a general class of inexact BCD methods.”