Globally Convergent Accelerated Block Proximal Method with Adaptive Momentum for Nonconvex Optimization

This paper considers a class of multi-block nonconvex nonsmooth optimization problems, and this class of problems covers many applications of signal processing and machine learning applications. We propose an accelerated block proximal linear method with adaptive momentum (ABPL+) to effectively tackle these challenges. The method evaluates both a proximal gradient step and a linear extrapolation step for updating each block of variables, opting for the one with the lower function value to maintain a monotonic decrease. The advantages of our method compared to previous approaches include: (1) allowing the extrapolation parameter to be independent of other parameters while utilizing an adaptive extrapolation parameter strategy, thereby improving stability and enhancing acceleration; (2) ensuring convergence and global convergence while establishing the convergence rate, even when the extrapolation parameter is independent of other parameters; and (3) permitting the random selection of variable blocks for updates while maintaining global convergence. We evaluate our method by applying it to solve the ℓ0-norm constrained multilayer nonnegative matrix factorization and sparse nonnegative CP decomposition problems, which are known to be NP-hard in general. Numerical results demonstrate that our method outperforms state-of-the-art algorithms, highlighting its effectiveness and potential for broader applications.