Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates

• URL: http://arxiv.org/abs/2107.09802v1
• Date: Tue, 20 Jul 2021 23:19:11 GMT
• Title: Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates
• Authors: Steve Chien, Prateek Jain, Walid Krichene, Steffen Rendle, Shuang Song, Abhradeep Thakurta, Li Zhang
• Abstract summary: We study the problem of differentially private (DP) matrix completion under user-level privacy. We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method.
• Score: 34.023599653814415
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of differentially private (DP) matrix completion under user-level privacy. We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method that achieves: i) (nearly) optimal sample complexity for matrix completion (in terms of number of items, users), and ii) the best known privacy/utility trade-off both theoretically, as well as on benchmark data sets. In particular, we provide the first global convergence analysis of ALS with noise introduced to ensure DP, and show that, in comparison to the best known alternative (the Private Frank-Wolfe algorithm by Jain et al. (2018)), our error bounds scale significantly better with respect to the number of items and users, which is critical in practical problems. Extensive validation on standard benchmarks demonstrate that the algorithm, in combination with carefully designed sampling procedures, is significantly more accurate than existing techniques, thus promising to be the first practical DP embedding model.

Related papers

• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation. We obtain several improved algorithms for private optimization problems, including decomposable submodular and set algorithm cover.
  arXiv  Detail & Related papers  (2024-05-28T19:02:30Z)
• How Private are DP-SGD Implementations? [61.19794019914523]
  We show that there can be a substantial gap between the privacy analysis when using the two types of batch sampling. Our result shows that there can be a substantial gap between the privacy analysis when using the two types of batch sampling.
  arXiv  Detail & Related papers  (2024-03-26T13:02:43Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• Adaptive Differentially Quantized Subspace Perturbation (ADQSP): A Unified Framework for Privacy-Preserving Distributed Average Consensus [6.364764301218972]
  We propose a general approach named adaptive differentially quantized subspace (ADQSP) We show that by varying a single quantization parameter the proposed method can vary between SMPC-type performances and DP-type performances. Our results show the potential of exploiting traditional distributed signal processing tools for providing cryptographic guarantees.
  arXiv  Detail & Related papers  (2023-12-13T07:52:16Z)
• User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates [16.958088684785668]
  We develop new algorithms for user-level DP-SCO that obtain optimal rates for both convex and strongly convex functions in runtime time. Our algorithms are the first to obtain optimal rates for non-smooth functions in time.
  arXiv  Detail & Related papers  (2023-11-07T08:26:51Z)
• Practical Privacy-Preserving Gaussian Process Regression via Secret Sharing [23.80837224347696]
  This paper proposes a privacy-preserving GPR method based on secret sharing (SS) We derive a new SS-based exponentiation operation through the idea of 'confusion-correction' and construct an SS-based matrix inversion algorithm based on Cholesky decomposition. Empirical results show that our proposed method can achieve reasonable accuracy and efficiency under the premise of preserving data privacy.
  arXiv  Detail & Related papers  (2023-06-26T08:17:51Z)
• Robustness Implies Privacy in Statistical Estimation [16.061651295129302]
  We study the relationship between adversarial and differential privacy in high-dimensional statistics. We give the first blackbox reduction from privacy to robustness which can produce private estimators with optimal tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples.
  arXiv  Detail & Related papers  (2022-12-09T18:07:30Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
  We propose a new distributed dynamic safe screening (DDSS) method for sparsity regularized models and apply it on shared-memory and distributed-memory architecture respectively. We prove that the proposed method achieves the linear convergence rate with lower overall complexity and can eliminate almost all the inactive features in a finite number of iterations almost surely.
  arXiv  Detail & Related papers  (2022-04-23T02:45:55Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Private Stochastic Convex Optimization: Efficient Algorithms for Non-smooth Objectives [28.99826590351627]
  We propose an algorithm based on noisy mirror which achieves a first-order descent, inversely in the regime when the privacy parameter is proportional to the number of samples.
  arXiv  Detail & Related papers  (2020-02-22T03:03:43Z)

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.