# Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization

arXiv: https://arxiv.org/abs/2012.03503 · HTML: https://mlsanity.com/paper/2012.03503/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2020.

## Built on by (most cited first, 9 of 9)

- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [Supervised Dictionary Learning with Auxiliary Covariates](https://mlsanity.com/paper/2206.06774/) (2022)
- [Block Majorization Minimization with Extrapolation and Application to β-NMF](https://mlsanity.com/paper/2401.06646/) (2024)
- [Design Optimization of NOMA Aided Multi-STAR-RIS for Indoor Environments: A Convex Approximation Imitated Reinforcement Learning Approach](https://mlsanity.com/paper/2406.13280/) (2024)
- [Interpolating between Clustering and Dimensionality Reduction with Gromov-Wasserstein](https://mlsanity.com/paper/2310.03398/) (2023)
- [A latent linear model for nonlinear coupled oscillators on graphs](https://mlsanity.com/paper/2311.14910/) (2023)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms](https://mlsanity.com/paper/2405.03073/) (2024)
- [Learning nonnegative matrix factorizations from compressed data](https://mlsanity.com/paper/2409.04994/) (2024)

## Abstract (arXiv)

Block majorization-minimization (BMM) is a simple iterative algorithm for constrained nonconvex optimization that sequentially minimizes majorizing surrogates of the objective function in each block while the others are held fixed. BMM entails a large class of optimization algorithms such as block coordinate descent and its proximal-point variant, expectation-minimization, and block projected gradient descent. We first establish that for general constrained nonsmooth nonconvex optimization, BMM with ρ-strongly convex and Lg-smooth surrogates can produce an ε-approximate first-order optimal point within widetildeO((1+Lg+ρ-1)ε-2) iterations and asymptotically converges to the set of first-order optimal points. Next, we show that BMM combined with trust-region methods with diminishing radius has an improved complexity of widetildeO((1+Lg) ε-2), independent of the inverse strong convexity parameter ρ-1, allowing improved theoretical and practical performance with `flat' surrogates. Our results hold robustly even when the convex sub-problems are solved as long as the optimality gaps are summable. Central to our analysis is a novel continuous first-order optimality measure, by which we bound the worst-case sub-optimality in each iteration by the first-order improvement the algorithm makes. We apply our general framework to obtain new results on various algorithms such as the celebrated multiplicative update algorithm for nonnegative matrix factorization by Lee and Seung, regularized nonnegative tensor decomposition, and the classical block projected gradient descent algorithm. Lastly, we numerically demonstrate that the additional use of diminishing radius can improve the convergence rate of BMM in many instances.