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

Résumé

We analyze a distributed algorithm to compute a low-rank matrix factorization on $N$ clients, each holding a local dataset $ mathbfStextasciicircum i in mathbbRtextasciicircumn_i times d$, mathematically, we seek to solve $min_ mathbfUtextasciicircum i in mathbbRtextasciicircumn_i times r, mathbfV in mathbbRtextasciicircumd times r frac12 sum_i=1textasciicircum N | mathbfStextasciicircum i - mathbfUtextasciicircum i mathbfVtextasciicircum top |textasciicircum 2_ textF$. Considering a power initialization of $ mathbfV$, 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 $ mathbfV$ in $ mathbbRtextasciicircumd times r$ common to all clients and a local variable $ mathbfUtextasciicircum i$ in $ mathbbRtextasciicircumn_i times r$. We provide a linear rate of convergence of the excess loss which depends on $ sigma_ max / sigma_r$, where $ sigma_r$ is the $rtextasciicircum mathrmth$ singular value of the concatenation $ mathbfS$ of the matrices $( mathbfStextasciicircum i)i=1textasciicircum N$. This result improves the rates of convergence given in the literature, which depend on $ sigma maxtextasciicircum 2 / sigma_ mintextasciicircum 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.