Global Optimality in Distributed Low-rank Matrix Factorization

Abstract

We study the convergence of a variant of distributed gradient descent (DGD) on a distributed low-rank matrix approximation problem wherein some optimization variables are used for consensus (as in classical DGD) and some optimization variables appear only locally at a single node in the network. We term the resulting algorithm DGD+LOCAL. Using algorithmic connections to gradient descent and geometric connections to the well-behaved landscape of the centralized low-rank matrix approximation problem, we identify sufficient conditions where DGD+LOCAL is guaranteed to converge with exact consensus to a global minimizer of the original centralized problem. For the distributed low-rank matrix approximation problem, these guarantees are stronger---in terms of consensus and optimality---than what appear in the literature for classical DGD and more general problems.

References in corpus (7)

• Guaranteed Matrix Completion via Non-convex Factorization
• Global Optimality in Low-rank Matrix Optimization
• Gradient Descent Converges to Minimizers
• When Are Nonconvex Problems Not Scary?
• First-order Methods Almost Always Avoid Saddle Points
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation

Cited by in corpus (2)

• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk