Research map / Learning theory and algorithms / Matrix and tensor methods
In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a federated low-rank matrix factorization method that uses a distributed randomized power initialization of a shared V followed by local (accelerated) gradient descent on each client's U, with linear convergence depending on sigma_max/sigma_r and a Frobenius-norm reconstruction bound.
Problem
Low-rank matrix factorization of data split across N clients, each holding a local matrix, where a global V must be shared and local U^i kept private, with minimal communication and guaranteed convergence in the Frobenius norm.
Approach
Use a distributed randomized power initialization of the global V so that the per-client objective becomes smooth and strongly convex in U^i, then solve each local problem with (Nesterov-accelerated) gradient descent without further communication; the rate depends on sigma_max/sigma_r rather than sigma_max^2/sigma_min^2, and multiple Gaussian samples of Phi are drawn to improve conditioning.
Key results
- On the synthetic low-rank setting the method recovers epsilon=0 up to machine precision, and with alpha=1 reaches an error around 5^-37 after two communications versus about 5^-7 for alpha=0 (theoretical example).
- Table of communications to reach target error: the proposed alpha=0 method needs 1 communication on synth, w8a, mnist and celeba, versus 26, 6, 35, 58 for WK2023 and at least 10^13 to 10^21 for YD2021.
- Frobenius-norm error bound with power initialization and a bound of the condition number kappa(V)^2 holding with high probability, improving the dependence from sigma_max^2/sigma_min^2 to sigma_max/sigma_r.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use power initialization with α=0 instead of WK2023 | Federated matrix factorization · Synthetic | communications to reach error: 26 -> 1 | Helped |
| Use power initialization with α=0 instead of WK2023 | Federated matrix factorization · w8a | communications to reach error: 6 -> 1 | Helped |
| Use power initialization with α=0 instead of WK2023 | Federated matrix factorization · mnist | communications to reach error: 35 -> 1 | Helped |
| Use power initialization with α=0 instead of WK2023 | Federated matrix factorization · celeba | communications to reach error: 58 -> 1 | Helped |
| Use power initialization with α=0 instead of YD2021 | Federated matrix factorization · Synthetic | communications to reach error: ≥10^{13} -> 1 | Helped |
| Use power initialization with α=0 instead of YD2021 | Federated matrix factorization · w8a | communications to reach error: ≥10^{20} -> 1 | Helped |
| Use power initialization with α=0 instead of YD2021 | Federated matrix factorization · mnist | communications to reach error: ≥10^{20} -> 1 | Helped |
| Use power initialization with α=0 instead of YD2021 | Federated matrix factorization · celeba | communications to reach error: ≥10^{21} -> 1 | Helped |
| Increase power iterations from α=0 to α=1 (ablation) | Federated matrix factorization with local gradient descent · w8a | condition number κ(V): 4 -> 120 | Hurt |
| Increase power iterations from α=0 to α=1 (ablation) | Federated matrix factorization with local gradient descent · mnist | condition number κ(V): 10 -> 5000 | Hurt |
| Increase power iterations from α=0 to α=1 (ablation) | Federated matrix factorization with local gradient descent · celeba-200k | condition number κ(V): 20 -> 20000 | Hurt |
| Increase power iterations α (ablation) | Federated matrix factorization · Full-rank data with small σmax/σr* | reconstruction error ε | Helped |
Surprising findings
- Increasing the power-iteration count alpha can slow gradient descent convergence when sigma_max/sigma_r is large, since the condition number of V grows (e.g. kappa(V) from 4 to 120 on w8a for alpha 0 to 1).
Limitations
- Bound on the Frobenius error grows with sigma_max/sigma_r and with r^2, and the alpha=0 bound from prior work is better in that regime.
- Requires a central server with secure aggregation; decentralized setting not covered.
- Gradient descent convergence can be slow when alpha>=1 in regimes with large sigma_max/sigma_r.
Experimental setup
Datasets: MNIST CelebA-200k w8a synthetic Gaussian-noise matrices
Benchmarks: MNIST CelebA w8a synthetic
Metrics: Frobenius-norm loss vs iterations number of communications to reach error condition number kappa(V)
Baselines: WK2023 YD2021 centralized SVD (scipy.linalg.svd)
Builds on: Randomized SVD (Halko et al.) Distributed Randomized Power Iteration (Wang and Krishnan 2023 / WK2023) LocalPower (Yu and Dong 2021 / YD2021)
Closest papers by meaning
- Distributed Low-rank Matrix Factorization With Exact Consensus (NeurIPS 2019 · similarity 0.92)
- On the Crucial Role of Initialization for Matrix Factorization (ICLR 2025 · similarity 0.90)
- Creating Coherence in Federated Non-Negative Matrix Factorization (AAAI 2025 · similarity 0.89)
- Byzantine-Resilient Federated Alternating Gradient Descent and Minimization for Partly-Decoupled Low Rank Matrix Learning (ICML 2025 · similarity 0.89)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.88)
- Federated Binary Matrix Factorization Using Proximal Optimization (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.