In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting

2024/09/13 by Philippenko, Constantin, Scaman, Kevin, Massoulié, Laurent · 2 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2409.08771

Abstract

We analyze a distributed algorithm to compute a low-rank matrix factorization on N clients, each holding a local dataset Sⁱ ∈ ℝ^{n_i × d}, mathematically, we seek to solve min_{Uⁱ ∈ ℝ^{ni× r}, V∈ ℝ^{d × r}} (1)/(2) ∑_i=1^N ‖Sⁱ - Uⁱ V^\top‖²_F. 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, …, N\, we obtain a global V in ℝ^{d × r} common to all clients and a local variable Uⁱ in ℝ^{n_i × r}. We provide a linear rate of convergence of the excess loss which depends on σ_max / σ_r, where σ_r is the r^th singular value of the concatenation S of the matrices (Sⁱ)_i=1^N. This result improves the rates of convergence given in the literature, which depend on σ_max² / σ_min². 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.

Cited by

• DeMuon: A Decentralized Muon for Matrix Optimization over Graphs
• Adaptive collaboration for online personalized distributed learning with heterogeneous clients

Related

• Finding Low-Rank Solutions via Non-Convex Matrix Factorization,\n Efficiently and Provably
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• Randomized algorithms for low-rank matrix factorizations: sharp\n performance bounds
• Federated Matrix Factorization: Algorithm Design and Application to Data Clustering
• Accurate and fast matrix factorization for low-rank learning