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

Constantin Philippenko, Kevin Scaman, Laurent Massoulié

TL;DR

This paper introduces a highly communication-efficient algorithm for federated low-rank matrix factorization by combining a global randomized power initialization with local gradient descent. By fixing the global feature matrix upfront, the authors transform a notoriously difficult non-convex problem into a smooth, strongly convex one, enabling linear convergence with minimal—or even a single step of—communication.

What Problem Does This Paper Address?

Low-rank matrix factorization (MF) is a cornerstone of machine learning, widely used for clustering, feature learning, and matrix completion. In a federated learning (FL) setting, data is distributed across multiple clients (e.g., user data on personal devices), and the goal is to learn a global shared feature matrix ($\mathbf{V}$) alongside personalized local matrices ($\mathbf{U}^i$) without centralizing the raw data.

The standard optimization approach for MF is non-convex, which complicates theoretical analysis and often leads to slow convergence rates tied to the condition number of the entire dataset. Furthermore, existing distributed gradient descent methods suffer from massive communication overhead because they require clients to synchronize updates during every single iteration. This paper tackles the challenge of achieving fast, linear convergence while drastically reducing the communication burden.

Methods

The authors propose a two-stage algorithm that bridges the gap between classical power iteration methods and gradient descent:

  1. Distributed Randomized Power Initialization: Clients collaboratively initialize the global matrix $\mathbf{V}$ using a distributed version of the randomized power method. This phase requires a fixed, small number of communication rounds ($\alpha + 1$).
  2. Parallel Local Gradient Descent: Once $\mathbf{V}$ is fixed globally, the objective function becomes smooth and strongly convex with respect to each client's local variable $\mathbf{U}^i$. Clients can then independently run local gradient descent (or Nesterov accelerated gradient descent) to compute their personalized matrices without any further communication.

To prevent poor convergence caused by an ill-conditioned initialization, the algorithm incorporates a "restart strategy" that samples multiple random Gaussian matrices ($\mathbf{\Phi}$) to ensure a well-conditioned $\mathbf{V}$ almost surely.

Datasets

The algorithm was evaluated on both synthetic and real-world datasets:

  • Synthetic Dataset: Generated across 25 clients with a ground-truth rank of 5 and varying levels of Gaussian noise.
  • MNIST: The classic handwritten digits dataset, distributed heterogeneously so that each client only holds images of a single digit.
  • CelebA-200k: A complex face attribute dataset, partitioned heterogeneously (one celebrity per client) to simulate high local complexity.
  • w8a: A tabular dataset split randomly across clients to represent a homogeneous data distribution.

The singular value spectra of these datasets are illustrated below:

Figure 1: Singular values of the four used datasets.

Key Insights and Ideas

  • Convexity via Smart Initialization: The core "aha!" moment is that using a power method to initialize and fix the global matrix $\mathbf{V}$ completely bypasses the non-convexity of matrix factorization. It reduces the remaining local optimization to standard, strongly convex least-squares problems.
  • Embarrassingly Parallel Potential: In low-noise or strictly low-rank regimes, setting $\alpha = 0$ means the algorithm requires only a single communication step at the very beginning, making it completely parallel thereafter.
  • Improved Convergence Bounds: Unlike previous literature where convergence rates degrade based on the ratio of the largest to the absolute smallest singular values ($\sigma_{\max}^2 / \sigma_{\min}^2$), this method's rate depends on $\sigma_{\max} / \sigma_r$ (where $r$ is the target rank). This means the algorithm remains fast even if the underlying data matrix is ill-conditioned.

Key Results

  • Drastic Communication Savings: As shown in the paper's empirical evaluations, to reach a target reconstruction error, the proposed method requires only 1 communication round ($\alpha = 0$) across multiple datasets. In comparison, alternative gradient descent methods in the literature require dozens to upwards of $10^{13}$ communication rounds.
  • Accelerated Local Convergence: By leveraging Nesterov momentum during the local optimization phase, clients achieve significantly faster convergence.

The rapid convergence behavior across the different datasets is displayed in the following plots:

Convergence plot on four datasets.

Limitations and Future Work

  • The $\alpha$ Trade-off: While increasing the power iteration parameter $\alpha$ reduces the final reconstruction error $\epsilon$, it simultaneously increases the condition number of $\mathbf{V}$. If the dataset has a very large $\sigma_{\max} / \sigma_r$ ratio, a higher $\alpha$ can severely slow down the local gradient descent phase.
  • Fully Decentralized Networks: The current framework relies on a central server to perform secure aggregation during the initialization phase. Extending this approach to peer-to-peer, decentralized topologies remains an open challenge.
  • Matrix Completion: The authors note that extending this method to matrix completion (where datasets have missing entries) is non-trivial, as it breaks the structural requirement that $\mathbf{V}$ must lie strictly within the column span of the data matrix.

Summary updated

Abstract

We analyze a distributed algorithm to compute a low-rank matrix factorization on $N$ clients, each holding a local dataset $\mathbf{S}^i \in \mathbb{R}^{n_i \times d}$, mathematically, we seek to solve $min_{\mathbf{U}^i \in \mathbb{R}^{n_i\times r}, \mathbf{V}\in \mathbb{R}^{d \times r} } \frac{1}{2} \sum_{i=1}^N \|\mathbf{S}^i - \mathbf{U}^i \mathbf{V}^\top\|^2_{\text{F}}$. Considering a power initialization of $\mathbf{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, \dots, N\}$, we obtain a global $\mathbf{V}$ in $\mathbb{R}^{d \times r}$ common to all clients and a local variable $\mathbf{U}^i$ in $\mathbb{R}^{n_i \times r}$. We provide a linear rate of convergence of the excess loss which depends on $σ_{\max} / σ_{r}$, where $σ_{r}$ is the $r^{\mathrm{th}}$ singular value of the concatenation $\mathbf{S}$ of the matrices $(\mathbf{S}^i)_{i=1}^N$. This result improves the rates of convergence given in the literature, which depend on $σ_{\max}^2 / σ_{\min}^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.
BibTeX
@inproceedings{philippenko2025depth,
  author = {Constantin Philippenko and Kevin Scaman and Laurent Massoulié},
  title = {{In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=d7dgpcTfNl},
}

Loading related content...

Figure