Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms

Mahesh Chandra Mukkamala(mukkamalamath.uni-sb.de)
Peter Ochs(ochsmath.uni-sb.de)

Abstract: Matrix Factorization is a popular non-convex objective, 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 remedy 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.

Keywords: Composite minimization, proximal gradient algorithms, inertial methods, convex-concave backtracking, non-Euclidean distances, Bregman distance, global convergence, matrix factorization, matrix completion.

Category 1: Convex and Nonsmooth Optimization

Citation:

Download: [PDF]

Entry Submitted: 05/23/2019
Entry Accepted: 05/23/2019
Entry Last Modified: 05/23/2019

Modify/Update this entry