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

Constantin Philippenko, Kevin Scaman, Laurent Massoulié

Abstract

This work presents a novel approach to low-rank matrix factorization in a federated learning context, where multiple clients collaboratively solve a matrix decomposition problem without sharing their local data. The algorithm introduces a power initialization technique for the global factorization matrix and combines it with local gradient descent updates to achieve strong theoretical and practical guarantees. Considering this power initialization, 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. We provide a linear rate of convergence of the excess loss, our results improve the rates of convergence given in the literature. 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.

Introduction

Low-rank matrix factorization (MF) is a fundamental technique in machine learning, underpinning applications such as recommendation systems, clustering, and image denoising. The objective is to approximate a large data matrix $S$ as the product of two lower-rank matrices, $U$ and $V$. In a Federated Learning (FL) environment, the data matrix $S$ is distributed across $N$ clients. The challenge lies in learning a shared global feature matrix $V$ while maintaining personalized local models $U^i$ for each client without centralizing raw data.

Standard MF approaches in FL face significant hurdles: the non-convexity of the joint objective function and the prohibitive communication costs associated with iterative updates between clients and the server. This paper introduces an "embarrassingly parallel" approach that leverages a distributed randomized power iteration for initialization, followed by local gradient descent, ensuring both efficiency and theoretical robustness.

Methodology

The proposed algorithm operates in two distinct stages:

  1. Distributed Randomized Power Iteration: The server and clients collaboratively perform a few initial rounds ($\alpha$) of power iteration using random Gaussian matrices. This step effectively "probes" the data's structure to find a global matrix $V$ that resides in the correct subspace.
  2. Local Gradient Descent: Once the global matrix $V$ is established and broadcasted, the optimization problem for each client becomes smooth and strongly convex with respect to their local matrix $U^i$. This transformation allows clients to independently reach their optimal local solutions using Nesterov-accelerated gradient descent without further communication.

The researchers also employ a "multiple sampling" strategy, selecting the random initialization that yields the best condition number to guarantee fast convergence.

Datasets and Experimental Setup

The effectiveness of the hybrid strategy was evaluated on four diverse datasets, representing various levels of heterogeneity and scale:

  • Synthetic Data: A rank-5 matrix with Gaussian noise.
  • MNIST: Handwritten digits partitioned heterogeneously (one digit type per client).
  • CelebA-200k: Large-scale facial attributes.
  • w8a: Tabular data for web classification, split homogeneously.
Singular value spectrum ($\log_{10}(\sigma_k)$) for the synthetic, MNIST, CelebA, and w8a datasets, illustrating the low-rank structure.

The singular value decay shown in Figure 1 confirms the low-rank nature of these datasets, which is essential for the success of the factorization approach.

Key Results and Insights

The primary breakthrough of this work is the observation that fixing a well-initialized $V$ converts a non-convex joint problem into a strongly convex local problem. This allows for superior convergence guarantees.

Linear Convergence and Communication Efficiency

The algorithm demonstrates a linear rate of convergence, where error decreases exponentially. In empirical tests, the method significantly outperformed existing gradient-descent-based competitors in terms of communication rounds. For instance, on the w8a dataset, the target error was reached in just 1 round, compared to 6 rounds for state-of-the-art alternatives.

Convergence of the reconstruction error across synthetic and real-world datasets, demonstrating the efficiency of the power initialization strategy.

As seen in Figure 2, the error drops rapidly across all tested datasets. Furthermore, the paper provides the first theoretical upper bound for the Frobenius-norm error under power initialization for $\alpha > 0$, filling a critical gap in existing literature.

Theoretical Advancements

Unlike previous studies where convergence rates depended on the ratio of the largest to the smallest singular values ($\sigma_{max}^2/\sigma_{min}^2$), this work proves a rate depending on $\sigma_{max}/\sigma_r$ (where $r$ is the target rank). This makes the algorithm far more stable and applicable to noisy real-world data.

Conclusion and Future Work

The proposed two-stage federated MF algorithm offers a highly efficient path to low-rank approximation with minimal communication overhead. While the current framework relies on a central server for aggregation and assumes full local data blocks, future research will explore fully decentralized (P2P) settings and extensions to matrix completion where data entries may be missing. Additionally, investigating approximate $V$ computation via stochastic methods could further optimize the initialization phase.

Summary updated

Abstract

This work presents a novel approach to low-rank matrix factorization in a federated learning context, where multiple clients collaboratively solve a matrix decomposition problem without sharing their local data. The algorithm introduces a power initialization technique for the global factorization matrix and combines it with local gradient descent updates to achieve strong theoretical and practical guarantees. Considering this power initialization, 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. We provide a linear rate of convergence of the excess loss, our results improve the rates of convergence given in the literature. 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