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

We analyze a distributed algorithm to compute a low-rank matrix factorization on N clients, each holding a local dataset Sⁱ ∈ R^ni×d, mathematically, we seek to solve min_Ui_∊Rn_i×r_V∊_Rd×r¹₂^PN_i=1 ∥Sⁱ−UⁱV^T∥²_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 R^d×^r common to all clients and a local variable Uⁱ in R^ni×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ⁱ)^N_i=1. 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.