Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms
arXiv:1905.09050
Abstract
Matrix Factorization is a popular non-convex optimization problem, for which alternating minimization schemes are mostly used. They usually suffer from the major drawback that the solution is biased towards one of the optimization variables. A remedy is non-alternating schemes. However, due to a lack of Lipschitz continuity of the gradient in matrix factorization problems, convergence cannot be guaranteed. A recently developed approach relies on the concept of Bregman distances, which generalizes the standard Euclidean distance. We exploit this theory by proposing a novel Bregman distance for matrix factorization problems, which, at the same time, allows for simple/closed form update steps. Therefore, for non-alternating schemes, such as the recently introduced Bregman Proximal Gradient (BPG) method and an inertial variant Convex--Concave Inertial BPG (CoCaIn BPG), convergence of the whole sequence to a stationary point is proved for Matrix Factorization. In several experiments, we observe a superior performance of our non-alternating schemes in terms of speed and objective value at the limit point.
arXiv commentAccepted at NeuRIPS 2019. Paper url: http://papers.nips.cc/paper/8679-beyond-alternating-updates-for-matrix-factorization-with-inertial-bregman-proximal-gradient-algorithms
References in corpus (13)
- Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
- The Why and How of Nonnegative Matrix Factorization
- Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems
- SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
- Variable metric inexact line-search based methods for nonsmooth optimization
- On the convergence of a linesearch based proximal-gradient method for nonconvex optimization
- Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization
- iPiano: Inertial Proximal Algorithm for Non-Convex Optimization
- Efficient Structured Matrix Rank Minimization
- Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization
- Stochastic model-based minimization under high-order growth
- Scalable Robust Matrix Factorization with Nonconvex Loss
- Bregman Proximal Gradient Algorithm with Extrapolation for a class of Nonconvex Nonsmooth Minimization Problems