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

Abstract

We analyze a distributed algorithm to compute a low-rank matrix factorization on NNN clients, each holding a local dataset Si∈Rni×dSi∈Rni×d mathbfStextasciicircum i in mathbbRtextasciicircumn_i times d, mathematically, we seek to solve minUi∈Rni×r,V∈Rd×r12∑Ni=1∥Si−UiV⊤∥2FminUi∈Rni×r,V∈Rd×r12∑i=1N‖Si−UiV⊤‖F2min_ 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 VV 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 iii in 1,…,N1,…,N1, dots, N, we obtain a global VV mathbfV in Rd×rRd×r mathbbRtextasciicircumd times r common to all clients and a local variable UiUi mathbfUtextasciicircum i in Rni×rRni×r mathbbRtextasciicircumn_i times r. We provide a linear rate of convergence of the excess loss which depends on σmax/σrσmax/σr sigma_ max / sigma_r, where σrσr sigma_r is the rthrthrtextasciicircum mathrmth singular value of the concatenation SS mathbfS of the matrices (Si)Ni=1(Si)i=1N( mathbfStextasciicircum i)i=1textasciicircum N. This result improves the rates of convergence given in the literature, which depend on σ2max/σ2minσmax2/σmin2 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.