Global Optimality in Distributed Low-rank Matrix Factorization
This provides improved convergence assurances for distributed optimization in machine learning, though it is incremental as it builds on known DGD variants.
The paper tackles the problem of ensuring global optimality and exact consensus in distributed low-rank matrix factorization, showing that their DGD+LOCAL algorithm converges to a global minimizer under sufficient conditions, with stronger guarantees than existing methods.
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.