# A globally convergent algorithm for nonconvex optimization based on block coordinate update arXiv: https://arxiv.org/abs/1410.1386 · HTML: https://mlsanity.com/paper/1410.1386/ ## Key facts - Cited by 29 papers in the map (data through 14 Oct 2026). - First posted on arXiv 6 Oct 2014. ## Built on by (most cited first, 29 of 29) - [Block Policy Mirror Descent](https://mlsanity.com/paper/2201.05756/) (2022) - [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022) - [Fast and Structured Block-Term Tensor Decomposition For Hyperspectral Unmixing](https://mlsanity.com/paper/2205.03798/) (2022) - [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023) - [Block Alternating Bregman Majorization Minimization with Extrapolation](https://mlsanity.com/paper/2107.04395/) (2021) - [Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent](https://mlsanity.com/paper/2107.12416/) (2021) - [A Framework of Inertial Alternating Direction Method of Multipliers for Non-Convex Non-Smooth Optimization](https://mlsanity.com/paper/2102.05433/) (2021) - [A consistent and flexible framework for deep matrix factorizations](https://mlsanity.com/paper/2206.10693/) (2022) - [An Accelerated Block Proximal Framework with Adaptive Momentum for Nonconvex and Nonsmooth Optimization](https://mlsanity.com/paper/2308.12126/) (2023) - [Structured Sparse Non-negative Matrix Factorization with L20-Norm for scRNA-seq Data Analysis](https://mlsanity.com/paper/2104.13171/) (2021) - [Multi-Tensor Network Representation for High-Order Tensor Completion](https://mlsanity.com/paper/2109.04022/) (2021) - [Personalized On-Device E-health Analytics with Decentralized Block Coordinate Descent](https://mlsanity.com/paper/2112.09341/) (2021) - [Graph Regularized NMF with L20-norm for Unsupervised Feature Learning](https://mlsanity.com/paper/2403.10910/) (2024) - [Attentive Gaussian processes for probabilistic time-series generation](https://mlsanity.com/paper/2102.05208/) (2021) - [On Model Compression for Neural Networks: Framework, Algorithm, and Convergence Guarantee](https://mlsanity.com/paper/2303.06815/) (2023) - [Learning Attributed Graphlets: Predictive Graph Mining by Graphlets with Trainable Attribute](https://mlsanity.com/paper/2402.06932/) (2024) - [Nonlinear Sparse Generalized Canonical Correlation Analysis for Multi-view High-dimensional Data](https://mlsanity.com/paper/2502.18756/) (2025) - [A Versatile Framework for Designing Group-Sparse Adversarial Attacks](https://mlsanity.com/paper/2510.16637/) (2025) - [Rethinking Coupled Tensor Analysis for Hyperspectral Super-Resolution: Recoverable Modeling Under Endmember Variability](https://mlsanity.com/paper/2512.19489/) (2025) - [Learning DNN networks using un-rectifying ReLU with compressed sensing application](https://mlsanity.com/paper/2101.06940/) (2021) - [Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints](https://mlsanity.com/paper/2201.07657/) (2022) - [Globally Convergent Accelerated Algorithms for Multilinear Sparse Logistic Regression with ℓ0-constraints](https://mlsanity.com/paper/2309.09239/) (2023) - [Matrix Completion via Nonsmooth Regularization of Fully Connected Neural Networks](https://mlsanity.com/paper/2403.10232/) (2024) - [Convergence of the majorized PAM method with subspace correction for low-rank composite factorization model](https://mlsanity.com/paper/2406.04588/) (2024) - [Orthogonal Constrained Minimization with Tensor ℓ2,p Regularization for HSI Denoising and Destriping](https://mlsanity.com/paper/2407.03605/) (2024) - [Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion](https://mlsanity.com/paper/2409.19550/) (2024) - [An Inertial Block Proximal Linearized Method with Adaptive Momentum for Nonconvex and Nonsmooth Optimization](https://mlsanity.com/paper/2608.05502/) (2026) - [Predicting Block-Coordinate Performance via Cross-Curvature](https://mlsanity.com/paper/2609.33489/) (2026) - [Generalized Geometry Block Proximal Linearized Method for Multiblock Nonconvex and Nonsmooth Optimization](https://mlsanity.com/paper/2609.39301/) (2026) ## Abstract (arXiv) Nonconvex optimization problems arise in many areas of computational science and engineering and are (approximately) solved by a variety of algorithms. Existing algorithms usually only have local convergence or subsequence convergence of their iterates. We propose an algorithm for a generic nonconvex optimization formulation, establish the convergence of its whole iterate sequence to a critical point along with a rate of convergence, and numerically demonstrate its efficiency. Specially, we consider the problem of minimizing a nonconvex objective function. Its variables can be treated as one block or be partitioned into multiple disjoint blocks. It is assumed that each non-differentiable component of the objective function or each constraint applies to one block of variables. The differentiable components of the objective function, however, can apply to one or multiple blocks of variables together. Our algorithm updates one block of variables at time by minimizing a certain prox-linear surrogate. The order of update can be either deterministic or randomly shuffled in each round. We obtain the convergence of the whole iterate sequence under fairly loose conditions including, in particular, the Kurdyka-Lojasiewicz (KL) condition, which is satisfied by a broad class of nonconvex/nonsmooth applications. We apply our convergence result to the coordinate descent method for non-convex regularized linear regression and also a modified rank-one residue iteration method for nonnegative matrix factorization. We show that both the methods have global convergence. Numerically, we test our algorithm on nonnegative matrix and tensor factorization problems, with random shuffling enable to avoid local solutions.