Research map / Optimization / Distributed and compressed

Byzantine-Resilient Federated Alternating Gradient Descent and Minimization for Partly-Decoupled Low Rank Matrix Learning

ICML 2025 · Optimization › Distributed and compressed · approach: Byzantine-robust learning

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 Byzantine-resilient federated alternating GD/minimization algorithms (Krum-AltGDmin and GM-AltGDmin) for low rank matrix completion, and extends them with a simple modification to vertically federated LR column-wise sensing and LR phase retrieval.

Problem

Federated low rank matrix learning (matrix completion, column-wise sensing, phase retrieval) where a fraction of nodes are Byzantine adversaries and data is heterogeneous across nodes in a vertical federation.

Approach

Combines alternating GD and minimization with Krum or geometric-median aggregation of node gradients, adds an incoherence-based filtering step so the updated left factor stays row-incoherent, and uses subspace-Krum for initialization; the same scheme extends to LRCS and LRPR by removing filtering and changing initialization.

Key results

• On synthetic LRMC (n=1000, q=500, r=3, L=20, Lbyz=8), Krum-AltGDmin and GM-AltGDmin converge to near machine precision while CWMedian-AltGDmin does not converge.
• Byz-AltGDmin-LRMC converges on federated MovieLens 1M with 40% Byzantine nodes (Lbyz=8, L=20).
• Theorem 2.2 gives exponential decay of subspace distance to a heterogeneity-dependent floor, under Lbyz/L < 0.4 and bounded heterogeneity GB <= c/kappa^2.

Measured effects reported in the paper

Surprising findings

• Coordinate-wise median fails to converge in the synthetic LRMC setting due to its very high sample complexity, though it converges on MovieLens where many samples are available.
• GM-AltGDmin is slower than Krum-AltGDmin in experiments, attributed to the approximate Weiszfeld algorithm and the compute cost of the theoretical GM algorithm.

Limitations

• Guarantees require bounded heterogeneity and incoherence assumptions; heterogeneity causes convergence only to a floor that grows with GB.
• GM guarantee holds only with constant probability and uses an approximate algorithm; GM-AltGDmin is slower in practice.
• Sample-splitting is assumed for the proofs; the algorithm needs many observed entries per node (order nr^2 log q log(1/eps)).

Experimental setup

Datasets: MovieLens 1M synthetic low rank matrices

Benchmarks: MovieLens 1M

Metrics: subspace distance vs time subspace distance vs iteration relative error on observed entries

Baselines: GM-AltGDmin CWMedian-AltGDmin Krum-AltGDmin

Builds on: AltGDmin Krum geometric median AltMin Factorized GD

Closest papers by meaning

• In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting (AAAI 2025 · similarity 0.89)
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent (NeurIPS 2016 · similarity 0.87)
• Byzantine Resilient and Fast Federated Few-Shot Learning (ICML 2024 · similarity 0.87)
• Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.87)
• Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR 2024 · similarity 0.86)
• RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.86)