(Amplified) Banded Matrix Factorization: A unified approach to private training
This work addresses the problem of enhancing privacy-utility-computation tradeoffs for machine learning practitioners, offering a unified approach that is incremental but provides practical gains in federated learning deployments.
The paper tackles the limitations of matrix factorization mechanisms in differential privacy for machine learning by introducing banded matrix factorization, which unifies and outperforms prior state-of-the-art algorithms in both federated and centralized settings across all privacy budgets, demonstrating improved performance over DP-SGD in most scenarios.
Matrix factorization (MF) mechanisms for differential privacy (DP) have substantially improved the state-of-the-art in privacy-utility-computation tradeoffs for ML applications in a variety of scenarios, but in both the centralized and federated settings there remain instances where either MF cannot be easily applied, or other algorithms provide better tradeoffs (typically, as $ε$ becomes small). In this work, we show how MF can subsume prior state-of-the-art algorithms in both federated and centralized training settings, across all privacy budgets. The key technique throughout is the construction of MF mechanisms with banded matrices (lower-triangular matrices with at most $\hat{b}$ nonzero bands including the main diagonal). For cross-device federated learning (FL), this enables multiple-participations with a relaxed device participation schema compatible with practical FL infrastructure (as demonstrated by a production deployment). In the centralized setting, we prove that banded matrices enjoy the same privacy amplification results as the ubiquitous DP-SGD algorithm, but can provide strictly better performance in most scenarios -- this lets us always at least match DP-SGD, and often outperform it.