(Amplified) Banded Matrix Factorization: A unified approach to private training

• URL: http://arxiv.org/abs/2306.08153v2
• Date: Thu, 2 Nov 2023 03:15:14 GMT
• Title: (Amplified) Banded Matrix Factorization: A unified approach to private training
• Authors: Christopher A. Choquette-Choo, Arun Ganesh, Ryan McKenna, H. Brendan McMahan, Keith Rush, Abhradeep Thakurta, and Zheng Xu
• Abstract summary: Matrix factorization (MF) mechanisms for differential privacy (DP) have substantially improved the state-of-the-art in privacy-utility-computation tradeoffs for ML applications. We show how MF can subsume prior state-of-the-art algorithms in both federated and centralized training settings.
• Score: 15.922315074913255
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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 $\epsilon$ 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.

Related papers

• DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning using Packed Secret Sharing [51.336015600778396]
  Federated Learning (FL) has gained lots of traction recently, both in industry and academia. In FL, a machine learning model is trained using data from various end-users arranged in committees across several rounds. Since such data can often be sensitive, a primary challenge in FL is providing privacy while still retaining utility of the model.
  arXiv  Detail & Related papers  (2024-10-21T16:25:14Z)
• A Hassle-free Algorithm for Private Learning in Practice: Don't Use Tree Aggregation, Use BLTs [4.736297244235246]
  This paper extends the recently introduced Buffered Linear Toeplitz (BLT) mechanism to multi-participation scenarios. Our BLT-DP-FTRL maintains the ease-of-use advantages of tree aggregation, while essentially matching matrix factorization in terms of utility and privacy.
  arXiv  Detail & Related papers  (2024-08-16T17:52:22Z)
• Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy [47.997934291881414]
  Existing mean estimation schemes are usually optimized for $L_infty$ geometry and rely on random rotation or Kashin's representation to adapt to $L$ geometry. We introduce a novel privacy accounting method for the sparsified Gaussian mechanism that incorporates the randomness inherent in sparsification into the DP. Unlike previous approaches, our accounting algorithm directly operates in $L$ geometry, yielding MSEs that fast converge to those of the Gaussian mechanism.
  arXiv  Detail & Related papers  (2024-05-02T03:48:47Z)
• Privacy Amplification for Matrix Mechanisms [18.13715687378337]
  "MMCC" is the first algorithm to analyze privacy amplification via sampling for any generic matrix mechanism. We show it leads to significant improvement in the privacy-utility trade-offs for DP-FTRL algorithms on standard benchmarks.
  arXiv  Detail & Related papers  (2023-10-24T05:16:52Z)
• Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning [18.55306294638515]
  We introduce new differentially private (DP) mechanisms for computation-based machine learning (ML) with multiple passes (epochs) over a dataset. We formalize the problem of DP mechanisms for adaptive streams with multiple participations and introduce a non-trivial extension of online matrix factorization DP mechanisms.
  arXiv  Detail & Related papers  (2022-11-12T00:41:11Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
  arXiv  Detail & Related papers  (2022-08-02T01:49:31Z)
• Improved Matrix Gaussian Mechanism for Differential Privacy [29.865497421453917]
  Differential privacy (DP) mechanisms are conventionally developed for scalar values, not for structural data like matrices. Our work proposes Improved Matrix Gaussian Mechanism (IMGM) for matrix-valued DP, based on the necessary and sufficient condition of $ (varepsilon,delta) $-differential privacy. Among the legitimate noise distributions for matrix-valued DP, we find the optimal one turns out to be i.i.d. Experiments on a variety of models and datasets also verify that IMGM yields much higher utility than the state-of-the-art mechanisms at the same privacy guarantee
  arXiv  Detail & Related papers  (2021-04-30T07:44:53Z)
• Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
  Symmetric nonnegative factor matrix (SNMF) has demonstrated to be a powerful method for data clustering. Inspired by ensemble clustering that aims to seek better clustering results, we propose self-supervised SNMF (S$3$NMF) We take advantage of the sensitivity to code characteristic of SNMF, without relying on any additional information.
  arXiv  Detail & Related papers  (2021-03-02T12:47:40Z)
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization [71.57324258813674]
  We show that PSDMF algorithms can be designed based on phase retrieval (PR) and affine rank minimization (ARM) algorithms. Motivated by this idea, we introduce a new family of PSDMF algorithms based on iterative hard thresholding (IHT)
  arXiv  Detail & Related papers  (2020-07-24T06:10:19Z)
• A High-Performance Implementation of Bayesian Matrix Factorization with Limited Communication [10.639704288188767]
  Matrix factorization algorithms can quantify uncertainty in their predictions and avoid over-fitting. They have not been widely used on large-scale data because of their prohibitive computational cost. We show that the state-of-the-art of both approaches to scalability can be combined.
  arXiv  Detail & Related papers  (2020-04-06T11:16:30Z)
• Meta Matrix Factorization for Federated Rating Predictions [84.69112252208468]
  Federated recommender systems have distinct advantages in terms of privacy protection over traditional recommender systems. Previous work on federated recommender systems does not fully consider the limitations of storage, RAM, energy and communication bandwidth in a mobile environment. Our goal in this paper is to design a novel federated learning framework for rating prediction (RP) for mobile environments.
  arXiv  Detail & Related papers  (2019-10-22T16:29:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.