The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization
Open accessAbstract
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 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 block forward-backward splitting algorithm, all of which are popular for large scale optimization problems involving big data.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Maximum Likelihood from Incomplete Data Via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444
Algorithm AS 136: A K-Means Clustering Algorithm
Hartigan, J. A., & Wong, M. A. (1979) · Applied Statistics · doi:10.2307/2346830 · Cited by 14,523
Tensor Decompositions and Applications
Kolda, T. G., & Bader, B. W. (2009) · SIAM Review · doi:10.1137/07070111x · Cited by 10,301
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Carroll, J. D., & Chang, J.-J. (1970) · Psychometrika · doi:10.1007/bf02310791 · Cited by 4,678
The expectation-maximization algorithm
Moon, T. K. (1996) · IEEE Signal Processing Magazine · doi:10.1109/79.543975 · Cited by 3,181
Signal Recovery by Proximal Forward-Backward Splitting
Combettes, P. L., & Wajs, V. R. (2005) · Multiscale Modeling & Simulation · doi:10.1137/050626090 · Cited by 2,678
Harshman, R. A. (1970) · Cited by 2,255
Proximal Splitting Methods in Signal Processing
Combettes, P. L., & Pesquet, J.-C. (2011) · Springer Optimization and Its Applications · doi:10.1007/978-1-4419-9569-8_10 · Cited by 2,183
Shi, Q., Razaviyayn, M., Luo, Z.-Q., & He, C. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2147784 · Cited by 2,129 · cited 3×
“Define In iteration 2 r + 1 , the algorithm solves the following problem In iteration 2 r + 2 , the algorithm solves the following (unconstrained) problem The above BSUM algorithm for solving (40) is called WMMSE algorithm in the reference [28].”
Self-citationConvergence of a Block Coordinate Descent Method for Nondifferentiable Minimization
Tseng, P. (2001) · Journal of Optimization Theory and Applications · doi:10.1023/a:1017501703105 · Cited by 1,989
Attouch, H., Bolte, J., & Svaiter, B. F. (2013) · Mathematical Programming · doi:10.1007/s10107-011-0484-9 · Cited by 1,414
Xu, Y., & Yin, W. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/120887795 · Cited by 1,160
Yuille, A. L., & Rangarajan, A. (2003) · Neural Computation · doi:10.1162/08997660360581958 · Cited by 1,151
Technical Note—A General Inner Approximation Algorithm for Nonconvex Mathematical Programs
Marks, B. R., & Wright, G. P. (1978) · Operations Research · doi:10.1287/opre.26.4.681 · Cited by 985
Dynamic Spectrum Management: Complexity and Duality
Luo, Z.-Q., & Zhang, S. (2008) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.914876 · Cited by 929
Self-citationPower Control By Geometric Programming
Chiang, M., Tan, C. W., Palomar, D. P., O'neill, D., & Julian, D. (2007) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2007.05960 · Cited by 886
Shi, Q., Razaviyayn, M., Luo, Z.-Q., & He, C. (2011) · 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2011.5946304 · Cited by 873
Self-citationA coordinate gradient descent method for nonsmooth separable minimization
Tseng, P., & Yun, S. (2009) · Mathematical Programming · doi:10.1007/s10107-007-0170-0 · Cited by 728
On the convergence of the block nonlinear Gauss–Seidel method under convex constraints
Grippo, L., & Sciandrone, M. (2000) · Operations Research Letters · doi:10.1016/s0167-6377(99)00074-7 · Cited by 678
Håstad, J. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90014-6 · Cited by 584
Estimation of Parameters for a Mixture of Normal Distributions
Hasselblad, V. (1966) · Technometrics · doi:10.1080/00401706.1966.10490375 · Cited by 492
A comparison of algorithms for fitting the PARAFAC model
Tomasi, G., & Bro, R. (2006) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2004.11.013 · Cited by 372
On search directions for minimization algorithms
Powell, M. J. D. (1973) · Mathematical Programming · doi:10.1007/bf01584660 · Cited by 338
Optimal Resource Allocation for MIMO Ad Hoc Cognitive Radio Networks
Kim, S.-J., & Giannakis, G. B. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2120270 · Cited by 301
Low-Complexity Distributed Algorithms for Spectrum Balancing in Multi-User DSL Networks
Papandriopoulos, J., & Evans, J. (2006) · 2006 IEEE International Conference on Communications · doi:10.1109/icc.2006.255311 · Cited by 283
A new algorithm for the solution of multi-state dynamic programming problems
Howson, H. R., & Sancho, N. G. F. (1975) · Mathematical Programming · doi:10.1007/bf01580431 · Cited by 153
Monotonic convergence of distributed interference pricing in wireless networks
Shi, C., Berry, R., & Honig, M. L. (2009) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2009.5205801 · Cited by 86
Local interference pricing for distributed beamforming in MIMO networks
Shi, C., Berry, R., & Honig, M. L. (2009) · IEEE Military Communications Conference (MILCOM) · doi:10.1109/milcom.2009.5379907 · Cited by 25
Hong, M., & Luo, Z.-Q. T. (2012) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2012.6288532 · Cited by 13
Self-citation
Cited by
Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning
Sun, Y., Babu, P., & Palomar, D. P. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2601299 · Cited by 1,820
Tensor Decomposition for Signal Processing and Machine Learning
Sidiropoulos, N. D., De Lathauwer, L., Fu, X., Huang, K., Papalexakis, E. E., & Faloutsos, C. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2690524 · Cited by 1,617
Wright, S. J. (2015) · Mathematical Programming · doi:10.1007/s10107-015-0892-3 · Cited by 1,438
Cichocki, A., Mandic, D., De Lathauwer, L., Zhou, G., Zhao, Q., Caiafa, C., & PHAN, H. A. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2013.2297439 · Cited by 1,384
Xu, Y., & Yin, W. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/120887795 · Cited by 1,160
Metadata
- Authors
- Razaviyayn, M., Hong, M., & Luo, Z.-Q.
- Venue
- SIAM Journal on Optimization
- Published
- 2013-01
- Volume
- 23
- Issue
- 2
- Pages
- 1126-1153
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2050968963
- Cited by
- 1,304
- References
- 31
- FWCI
- 79.31
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.