1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Collaborative FilteringLearning TheoryMatrix CompletionSimilar Papers 제목 키워드 기반
Approximate Method of Variational Bayesian Matrix Factorization/Completion with Sparse Prior
We derive analytical expression of matrix factorization/completion solution by variational Bayes method, under the assumption that observed matrix is originally the product of low-rank dense and sparse matrices with addi…
Matrix CompletionOn the properties of variational approximations of Gibbs posteriors
The PAC-Bayesian approach is a powerful set of techniques to derive non- asymptotic risk bounds for random estimators. The corresponding optimal distribution of estimators, usually called the Gibbs posterior, is unfortun…
General ClassificationMatrix CompletionFast Low-Rank Bayesian Matrix Completion with Hierarchical Gaussian Prior Models
The problem of low rank matrix completion is considered in this paper. To exploit the underlying low-rank structure of the data matrix, we propose a hierarchical Gaussian prior model, where columns of the low-rank matrix…
Bayesian InferenceLow-Rank Matrix CompletionMatrix CompletionConcentration of tempered posteriors and of their variational approximations
While Bayesian methods are extremely popular in statistics and machine learning, their application to massive datasets is often challenging, when possible at all. Indeed, the classical MCMC algorithms are prohibitively s…
Collaborative FilteringMatrix CompletionOnline Variational Bayesian Subspace Filtering with Applications
Matrix completion and robust principal component analysis have been widely used for the recovery of data suffering from missing entries or outliers. In many real-world applications however, the data is also time-varying,…
ImputationMatrix Completion