mlsanityData to 14 Oct 2026

Efficient Federated Low Rank Matrix Completion

arXiv 2405.06569 ↗First posted 10 May 2024cs.LG eess.SPcited by 0

Not on the map. Why?

Abstract (arXiv)

In this work, we develop and analyze a Gradient Descent (GD) based solution, called Alternating GD and Minimization (AltGDmin), for efficiently solving the low rank matrix completion (LRMC) in a federated setting. LRMC involves recovering an n × q rank-r matrix Xstar from a subset of its entries when r ll min(n,q). Our theoretical guarantees (iteration and sample complexity bounds) imply that AltGDmin is the most communication-efficient solution in a federated setting, is one of the fastest, and has the second best sample complexity among all iterative solutions to LRMC. In addition, we also prove two important corollaries. (a) We provide a guarantee for AltGDmin for solving the noisy LRMC problem. (b) We show how our lemmas can be used to provide an improved sample complexity guarantee for AltMin, which is the fastest centralized solution.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 16 of its 46 references that are in the map. First posted on arXiv 10 May 2024.

Builds on

16 of 46 references.

References · 16

  1. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  2. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  3. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 112
  4. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 82
  5. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  6. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  7. 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
  8. 2017GIANT: Globally Improved Approximate Newton Method for Distributed Optimizationcited by 44
  9. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 39
  10. 2016Fast Algorithms for Robust PCA via Gradient Descentcited by 39
  11. 2013Understanding Alternating Minimization for Matrix Completioncited by 32
  12. 2020Distributed Newton Can Communicate Less and Resist Byzantine Workerscited by 20
4 more
  1. 2014Fast matrix completion without the condition numbercited by 17
  2. 2014Fast Exact Matrix Completion with Finite Samplescited by 15
  3. 2016Nearly-optimal Robust Matrix Completioncited by 13
  4. 2023Convergence of Alternating Gradient Descent for Matrix Factorizationcited by 12

Built on by

Not cited yet.