Block Bregman majorization minimization with extrapolation

DOI10.1137/21M1432661zbMATH Open1486.90154arXiv2107.04395OpenAlexW4205214044MaRDI QIDQ5037560FDOQ5037560

Authors: Le Thi Khanh Hien, Nicolas Gillis, Masoud Ahookhosh, Panagiotis Patrinos, Duy Nhat Phan 

Publication date: 1 March 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: In this paper, we consider a class of nonsmooth nonconvex optimization problems whose objective is the sum of a block relative smooth function and a proper and lower semicontinuous block separable function. Although the analysis of block proximal gradient (BPG) methods for the class of block $L$-smooth functions have been successfully extended to Bregman BPG methods that deal with the class of block relative smooth functions, accelerated Bregman BPG methods are scarce and challenging to design. Taking our inspiration from Nesterov-type acceleration and the majorization-minimization scheme, we propose a block alternating Bregman Majorization-Minimization framework with Extrapolation (BMME). We prove subsequential convergence of BMME to a first-order stationary point under mild assumptions, and study its global convergence under stronger conditions. We illustrate the effectiveness of BMME on the penalized orthogonal nonnegative matrix factorization problem.

Full work available at URL: https://arxiv.org/abs/2107.04395

Recommendations

• Nonconvex nonsmooth optimization via convex-nonconvex majorization-minimization
• A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• A Bregman stochastic method for nonconvex nonsmooth problem beyond global Lipschitz gradient continuity
• Block coordinate proximal gradient methods with variable Bregman functions for nonsmooth separable optimization

zbMATH Keywords

orthogonal nonnegative matrix factorizationmajorization minimizationacceleration by extrapolationinertial block coordinate methodBregman surrogate function

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Factorization of matrices (15A23) Matrix completion problems (15A83) Nonconvex programming, global optimization (90C26) Numerical methods based on nonlinear programming (49M37)

Cites Work

• $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
• A unified convergence analysis of block successive minimization methods for nonsmooth optimization
• Title not available (Why is that?)
• A coordinate gradient descent method for nonsmooth separable minimization
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Iterative hard thresholding for compressed sensing
• A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
• Title not available (Why is that?)
• Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Sparse Approximate Solutions to Linear Systems
• On gradients of functions definable in o-minimal structures
• On the convergence of block coordinate descent type methods
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• A fast patch-dictionary method for whole image recovery
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Novel proximal gradient methods for nonnegative matrix factorization with sparsity constraints
• Lectures on convex optimization
• A globally convergent algorithm for nonconvex optimization based on block coordinate update
• Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems
• First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
• Relatively smooth convex optimization by first-order methods, and applications
• Convex-concave backtracking for inertial Bregman proximal gradient algorithms in nonconvex optimization
• A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
• Nonnegative matrix factorization
• Algorithms for nonnegative matrix factorization with the Kullback-Leibler divergence
• A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano

Cited In (6)

• An inertial ADMM for a class of nonconvex composite optimization with nonlinear coupling constraints
• A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization
• Stochastic variance-reduced majorization-minimization algorithms
• Coordinate descent methods beyond smoothness and separability
• Random Coordinate Descent Methods for Nonseparable Composite Optimization
• Convergence analysis of block majorize-minimize subspace approach

This page was built for publication: Block Bregman majorization minimization with extrapolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5037560)