In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting
Not on the map. Why?
Abstract (arXiv)
We analyze a distributed algorithm to compute a low-rank matrix factorization on N clients, each holding a local dataset Si ∈ ℝni × d, mathematically, we seek to solve min_Ui ∈ ℝni× r, V∈ ℝd × r frac12 sumi=1N |Si - Ui V^top|2F. Considering a power initialization of V, we rewrite the previous smooth non-convex problem into a smooth strongly-convex problem that we solve using a parallel Nesterov gradient descent potentially requiring a single step of communication at the initialization step. For any client i in 1, dots, N, we obtain a global V in ℝd × r common to all clients and a local variable Ui in ℝni × r. We provide a linear rate of convergence of the excess loss which depends on σmax / σr, where σr is the rth singular value of the concatenation S of the matrices (Si)i=1N. This result improves the rates of convergence given in the literature, which depend on σmax2 / σmin2. We provide an upper bound on the Frobenius-norm error of reconstruction under the power initialization strategy. We complete our analysis with experiments on both synthetic and real data.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 18 of its 51 references that are in the map. First posted on arXiv 13 Sep 2024.
Builds on
18 of 51 references.
References · 18
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
- 2014Deep Learning Face Attributes in the Wildcited by 3,679
- 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
- 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
- 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
- 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
- 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
- 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
- 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 37
- 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
- 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
- 2023Matrix Compression via Randomized Low Rank and Low Precision Factorizationcited by 25
6 more
- 2015Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squarerootcited by 15
- 2020Communication-Efficient Distributed SVD via Local Power Iterationscited by 12
- 2023Convergence of Alternating Gradient Descent for Matrix Factorizationcited by 12
- 2017Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysiscited by 10
- 2020The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularizationcited by 7
- 2016Dictionary Learning for Massive Matrix Factorizationcited by 4
Built on by
Citing papers per year: 2025: 2.
2 papers.