# Misclassification excess risk bounds for 1-bit matrix completion

arXiv: https://arxiv.org/abs/2312.12945 · HTML: https://mlsanity.com/paper/2312.12945/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 41 references that are in the map.
- First posted on arXiv 20 Dec 2023.

## Builds on (most cited first, 8 of 8)

- [Concentration of tempered posteriors and of their variational approximations](https://mlsanity.com/paper/1706.09293/) (2017)
- [Inference and Uncertainty Quantification for Noisy Matrix Completion](https://mlsanity.com/paper/1906.04159/) (2019)
- [PU Learning for Matrix Completion](https://mlsanity.com/paper/1411.6081/) (2014)
- [A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion](https://mlsanity.com/paper/1309.6013/) (2013)
- [High-dimensional classification by sparse logistic regression](https://mlsanity.com/paper/1706.08344/) (2017)
- [1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation](https://mlsanity.com/paper/1604.04191/) (2016)
- [Adaptive Multinomial Matrix Completion](https://mlsanity.com/paper/1408.6218/) (2014)
- [Collective Matrix Completion](https://mlsanity.com/paper/1807.09010/) (2018)

## Abstract (arXiv)

This study investigates the misclassification excess risk bound in the context of 1-bit matrix completion, a significant problem in machine learning involving the recovery of an unknown matrix from a limited subset of its entries. Matrix completion has garnered considerable attention in the last two decades due to its diverse applications across various fields. Unlike conventional approaches that deal with real-valued samples, 1-bit matrix completion is concerned with binary observations. While prior research has predominantly focused on the estimation error of proposed estimators, our study shifts attention to the prediction error. This paper offers theoretical analysis regarding the prediction errors of two previous works utilizing the logistic regression model: one employing a max-norm constrained minimization and the other employing nuclear-norm penalization. Significantly, our findings demonstrate that the latter achieves the minimax-optimal rate without the need for an additional logarithmic term. These novel results contribute to a deeper understanding of 1-bit matrix completion by shedding light on the predictive performance of specific methodologies.