1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation

Abstract

Due to challenging applications such as collaborative filtering, the matrix completion problem has been widely studied in the past few years. Different approaches rely on different structure assumptions on the matrix in hand. Here, we focus on the completion of a (possibly) low-rank matrix with binary entries, the so-called 1-bit matrix completion problem. Our approach relies on tools from machine learning theory: empirical risk minimization and its convex relaxations. We propose an algorithm to compute a variational approximation of the pseudo-posterior. Thanks to the convex relaxation, the corresponding minimization problem is bi-convex, and thus the method behaves well in practice. We also study the performance of this variational approximation through PAC-Bayesian learning bounds. On the contrary to previous works that focused on upper bounds on the estimation error of M with various matrix norms, we are able to derive from this analysis a PAC bound on the prediction error of our algorithm. We focus essentially on convex relaxation through the hinge loss, for which we present the complete analysis, a complete simulation study and a test on the MovieLens data set. However, we also discuss a variational approximation to deal with the logistic loss.

References in corpus (2)

• On the properties of variational approximations of Gibbs posteriors
• A Bayesian Approach for Noisy Matrix Completion: Optimal Rate under General Sampling Distribution

Cited by in corpus (17)

• User-friendly introduction to PAC-Bayes bounds
• Consistency of Variational Bayes Inference for Estimation and Model Selection in Mixtures
• Pseudo-Bayesian Quantum Tomography with Rank-adaptation
• Improving application performance with biased distributions of quantum states
• Logistic principal component analysis via non-convex singular value thresholding
• A Generalization Bound for Online Variational Inference
• From bilinear regression to inductive matrix completion: a quasi-Bayesian analysis
• A reduced-rank approach to predicting multiple binary responses through machine learning
• High-dimensional sparse classification using exponential weighting with empirical hinge loss
• Concentration properties of fractional posterior in 1-bit matrix completion
• Misclassification bounds for PAC-Bayesian sparse deep learning
• An efficient adaptive MCMC algorithm for Pseudo-Bayesian quantum tomography
• Tight Risk Bound for High Dimensional Time Series Completion
• One-Bit Matrix Completion with Differential Privacy
• Misclassification excess risk bounds for 1-bit matrix completion
• Cluster Developing 1-Bit Matrix Completion
• Simulation comparisons between Bayesian and de-biased estimators in low-rank matrix completion