Global Optimality in Distributed Low-rank Matrix Factorization
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Distributed Low-rank Matrix Factorization With Exact Consensus
Low-rank matrix factorization is a problem of broad importance, owing to the ubiquity of low-rank models in machine learning contexts. In spite of its non- convexity, this problem has a well-behaved geometric landscape, …
Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms, and Applications
Recently, convex formulations of low-rank matrix factorization problems have received considerable attention in machine learning. However, such formulations often require solving for a matrix of the size of the data matr…
Video SegmentationVideo Semantic SegmentationPreconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification
We consider using gradient descent to minimize the nonconvex function $f(X)=\phi(XX^{T})$ over an $n\times r$ factor matrix $X$, in which $\phi$ is an underlying smooth convex cost function defined over $n\times n$ matri…
1-Bit Matrix Completion under Exact Low-Rank Constraint
We consider the problem of noisy 1-bit matrix completion under an exact rank constraint on the true underlying matrix $M^*$. Instead of observing a subset of the noisy continuous-valued entries of a matrix $M^*$, we obse…
Matrix CompletionRankMat : Matrix Factorization with Calibrated Distributed Embedding and Fairness Enhancement
Matrix Factorization is a widely adopted technique in the field of recommender system. Matrix Factorization techniques range from SVD, LDA, pLSA, SVD++, MatRec, Zipf Matrix Factorization and Item2Vec. In recent years, di…
FairnessRecommendation SystemsWord Embeddings