Timezone: »
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.
Author Information
Steve Chien (Google)
Prateek Jain (Google Research)
Walid Krichene (Google Research)
Steffen Rendle (Google)
Shuang Song (Google)
Abhradeep Guha Thakurta (Google)
Li Zhang (Google)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Oral: Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates »
Thu. Jul 22nd 02:00 -- 02:20 PM Room
More from the Same Authors
-
2021 : Practical and Private (Deep) Learning without Sampling orShuffling »
Peter Kairouz · Hugh B McMahan · Shuang Song · Om Dipakbhai Thakkar · Abhradeep Guha Thakurta · Zheng Xu -
2021 : Differentially Private Model Personalization »
Prateek Jain · J K Rush · Adam Smith · Shuang Song · Abhradeep Guha Thakurta -
2021 : The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space »
Adam Smith · Shuang Song · Abhradeep Guha Thakurta -
2021 : Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates »
Steve Chien · Prateek Jain · Walid Krichene · Steffen Rendle · Shuang Song · Abhradeep Guha Thakurta · Li Zhang -
2022 : DAFT: Distilling Adversarially Fine-tuned teachers for OOD Robustness »
Anshul Nasery · Sravanti Addepalli · Praneeth Netrapalli · Prateek Jain -
2023 Poster: Why Is Public Pretraining Necessary for Private Model Training? »
Arun Ganesh · Mahdi Haghifam · Milad Nasresfahani · Sewoong Oh · Thomas Steinke · Om Thakkar · Abhradeep Guha Thakurta · Lun Wang -
2023 Oral: Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning »
Christopher Choquette-Choo · Hugh B McMahan · J K Rush · Abhradeep Guha Thakurta -
2023 Oral: Inflow, Outflow, and Reciprocity in Machine Learning »
Mukund Sundararajan · Walid Krichene -
2023 Poster: Multi-Task Differential Privacy Under Distribution Skew »
Walid Krichene · Prateek Jain · Shuang Song · Mukund Sundararajan · Abhradeep Guha Thakurta · Li Zhang -
2023 Poster: Multi-User Reinforcement Learning with Low Rank Rewards »
Dheeraj Nagaraj · Suhas Kowshik · Naman Agarwal · Praneeth Netrapalli · Prateek Jain -
2023 Poster: Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning »
Christopher Choquette-Choo · Hugh B McMahan · J K Rush · Abhradeep Guha Thakurta -
2023 Poster: Inflow, Outflow, and Reciprocity in Machine Learning »
Mukund Sundararajan · Walid Krichene -
2022 Poster: Public Data-Assisted Mirror Descent for Private Model Training »
Ehsan Amid · Arun Ganesh · Rajiv Mathews · Swaroop Ramaswamy · Shuang Song · Thomas Steinke · Thomas Steinke · Vinith Suriyakumar · Om Thakkar · Abhradeep Guha Thakurta -
2022 Spotlight: Public Data-Assisted Mirror Descent for Private Model Training »
Ehsan Amid · Arun Ganesh · Rajiv Mathews · Swaroop Ramaswamy · Shuang Song · Thomas Steinke · Thomas Steinke · Vinith Suriyakumar · Om Thakkar · Abhradeep Guha Thakurta -
2021 Poster: Practical and Private (Deep) Learning Without Sampling or Shuffling »
Peter Kairouz · Brendan McMahan · Shuang Song · Om Dipakbhai Thakkar · Abhradeep Guha Thakurta · Zheng Xu -
2021 Poster: Oneshot Differentially Private Top-k Selection »
Gang Qiao · Weijie Su · Li Zhang -
2021 Spotlight: Oneshot Differentially Private Top-k Selection »
Gang Qiao · Weijie Su · Li Zhang -
2021 Spotlight: Practical and Private (Deep) Learning Without Sampling or Shuffling »
Peter Kairouz · Brendan McMahan · Shuang Song · Om Dipakbhai Thakkar · Abhradeep Guha Thakurta · Zheng Xu -
2021 Poster: Optimal regret algorithm for Pseudo-1d Bandit Convex Optimization »
Aadirupa Saha · Nagarajan Natarajan · Praneeth Netrapalli · Prateek Jain -
2021 Spotlight: Optimal regret algorithm for Pseudo-1d Bandit Convex Optimization »
Aadirupa Saha · Nagarajan Natarajan · Praneeth Netrapalli · Prateek Jain -
2018 Poster: Adaptive Sampled Softmax with Kernel Based Sampling »
Guy Blanc · Steffen Rendle -
2018 Oral: Adaptive Sampled Softmax with Kernel Based Sampling »
Guy Blanc · Steffen Rendle