Published on Tue Jul 20 2021

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

Steve Chien, Prateek Jain, Walid Krichene, Steffen Rendle, Shuang Song, Abhradeep Thakurta, Li Zhang

We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method. We provide the first global global convergence analysis of ALS with noise introduced to ensure DP. Extensive validation on standard benchmarks demonstrate that the algorithm is significantly more accurate than existing techniques.

1
0
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.

Thu Dec 28 2017
Machine Learning
Differentially Private Matrix Completion Revisited
Algorithm is based on the Frank-Wolfe method. It consistently estimates the underlying preference matrix as long as the number of users is
0
0
0
Wed Sep 18 2019
Machine Learning
Renyi Differentially Private ADMM for Non-Smooth Regularized Optimization
In this paper we consider the problem of minimizing composite objective functions. We propose two stochastic alternating direction method of multipliers (ADMM) algorithms. Both algorithmsdecompose the original problem into sub-problems that have closed-form solutions.
0
0
0
Mon Mar 01 2021
Machine Learning
Non-Euclidean Differentially Private Stochastic Convex Optimization
Differentially private (DP) stochastic convex optimization (SCO) is a fundamental problem. Algorithms based on noisy stochastic gradient descent (SGD) are known to attain the optimal excess risk in this setting. We give two new algorithms, whose central building block is a novel privacy mechanism.
0
0
0
Sun Sep 06 2020
Machine Learning
A Framework for Private Matrix Analysis
We study private matrix analysis in the sliding window model. We give first in efficient space differentially private algorithms for spectral approximation, principal component analysis, and linear regression. We also show a lower bound on space required to compute low-rank approximation.
0
0
0
Fri May 25 2018
Machine Learning
An end-to-end Differentially Private Latent Dirichlet Allocation Using a Spectral Algorithm
We provide an end-to-end differentially private spectral algorithm for LDA, based on matrix/tensor decompositions. We establish theoretical guarantees on utility/consistency of the estimated model parameters.
0
0
0
Thu Jan 29 2015
Machine Learning
Per-Block-Convex Data Modeling by Accelerated Stochastic Approximation
This paper develops an online and modular learning algorithm for a large class of non-convex data models. The advocated algorithm incurs computational complexity that scales rapidly with the number of unknowns. The merits of the general approach are demonstrated in two online learning setups.
0
0
0
Mon Dec 14 2020
NLP
Extracting Training Data from Large Language Models
Attack on GPT-2, a language model trained on scrapes of the public Internet. We are able to extract hundreds of verbatim text sequences from the model's training data. These extracted examples include names, phone numbers, and email addresses.
21
293
1,445
Fri Jul 01 2016
Machine Learning
Deep Learning with Differential Privacy
Machine learning techniques based on neural networks are achieving remarkable results in a wide variety of domains. Often, the training of models requires large, representative datasets, which may contain sensitive information. The models should not expose private information in these datasets.
4
0
4
Thu Dec 28 2017
Machine Learning
Differentially Private Matrix Completion Revisited
Algorithm is based on the Frank-Wolfe method. It consistently estimates the underlying preference matrix as long as the number of users is
0
0
0
Tue Oct 18 2016
Machine Learning
Membership Inference Attacks against Machine Learning Models
Machine learning models leak information about the individual data records on which they were trained. We focus on the basic membership inference attack. We then investigate the factors that influence this leakage and evaluate mitigation strategies.
0
0
0
Fri Nov 28 2014
Machine Learning
Guaranteed Matrix Completion via Non-convex Factorization
Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization can be solved very efficiently by standard algorithms in practice.
0
0
0
Mon Dec 03 2012
Machine Learning
Low-rank Matrix Completion using Alternating Minimization
Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. This method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix Challenge.
0
0
0