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

Constantin Philippenko, Kevin Scaman, Laurent Massoulié

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$, we obtain a global $\mathbf{V}$ common to all clients and a local variable $\mathbf{U}^i$. We provide a linear rate of convergence of the excess loss which depends on $\sigma_{\max} / \sigma_{r}$, improving upon literature rates depending on $\sigma_{\max}^2 / \sigma_{\min}^2$. We provide an upper bound on the Frobenius-norm error of reconstruction and complete our analysis with experiments on both synthetic and real data.

Introduction

Low-rank matrix factorization (MF) is a fundamental tool in machine learning, essential for tasks like recommendation systems and dimensionality reduction. In federated learning (FL) scenarios, data is distributed across multiple clients, introducing significant challenges: the non-convexity of the standard MF objective and the high communication costs associated with synchronizing large matrices. Existing methods often struggle with either slow convergence due to poor conditioning or high communication overhead.

Methodology

The proposed approach addresses these challenges through a two-stage strategy:

  1. Distributed Randomized Power Iteration: The server and clients collaborate to initialize a global shared matrix $V$ (the right-basis). By using randomized Gaussian projections, the data is mapped into a lower-dimensional space. This stage requires only a small, fixed number of communication rounds ($\alpha$).
  2. Local Gradient Descent: Once $V$ is fixed, the local optimization for each client's matrix $U^i$ becomes a smooth and strongly convex problem. This allows clients to independently reach exact local solutions using Nesterov acceleration without further communication.

This hybrid approach bridges randomized linear algebra and traditional optimization, using power methods to "warm up" the problem geometry so that local gradient descent can converge linearly.

Experimental Evaluation

The algorithm was tested on four datasets: Synthetic (controlled noise), MNIST (heterogeneous digit distribution), CelebA-200k (face attributes), and w8a (tabular data).

Convergence of the proposed algorithm across synthetic and real-world datasets.

As shown in the convergence plots above, the error drops exponentially relative to the number of local iterations, confirming the theoretical linear convergence rate across diverse data types.

Key Results

The primary advantage of this method is its communication efficiency. In many regimes, high accuracy is achieved with just one or two communication steps, making it "embarrassingly parallel."

Comparison of communication rounds required to reach target error levels across different algorithms.

The table above demonstrates that the proposed method ($\alpha=0$) significantly outperforms state-of-the-art competitors like WK2023 and YD2021. For instance, on the w8a dataset, the proposed method reaches the target error in a single round, whereas WK2023 requires 6 rounds and YD2021 fails to converge efficiently (requiring $\ge 10^{20}$ rounds). Furthermore, the analysis provides new Frobenius-norm error bounds, which are more practically relevant than the spectral norm bounds common in prior literature.

Conclusion

This work provides a robust theoretical and empirical foundation for federated low-rank matrix factorization. By leveraging power initialization to transform a non-convex problem into a locally convex one, the algorithm achieves superior communication efficiency and linear convergence. Future research will explore fully decentralized architectures and extensions to matrix completion problems where data entries are missing.

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 $\sigma_{\max} / \sigma_{r}$, where $\sigma_{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 $\sigma_{\max}^2 / \sigma_{\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},
}
Figure