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 i ∈ R n i ×d , mathematically, we seek to solve 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 i in R 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 ) N i=1 . This result improves the rates of convergence given in the literature, which depend on σ 2 max /σ 2 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.