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

Code

• github.com/philipco/matrix_factorization
  Officialnone★ 1

Abstract

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 min_U^i R^n_i r, V R^d r 12 _i=1^N \|S^i - U^i V^\|^2_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^i in R^n_i r. We provide a linear rate of convergence of the excess loss which depends on _ / _r, where _r is the r^th singular value of the concatenation S of the matrices (S^i)_i=1^N. This result improves the rates of convergence given in the literature, which depend on _^2 / _^2. 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.

Reproductions