Semi-Random Noisy and One-Bit Matrix Completion via Nonconvex Optimization

Xing Gao, Binhao Chen, Yu Cheng
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:2161-2169, 2026.

Abstract

We study low-rank matrix completion in the \textit{semi-random model}, where each entry $(i, j)$ is observed independently with an unknown probability $p_{i,j} \ge p$, in contrast to the standard model with a uniform probability $p$. While prior work has shown that nonconvex approach succeeds in the semi-random model for exact observations [CG18], it remains unclear whether similar guarantees extend to more general observation model, such as noisy or one-bit measurements. In this paper, we give a unified framework for semi-random matrix recovery applicable to a broad family of observation models. Our approach builds on the preprocessing step of [CG18] to restore regularity conditions that are violated under adversarial sampling, and leverages the primal-dual framework of [ZWYG18] to obtain near-optimal recovery guarantees. As concrete corollaries, we show that for both noisy and one-bit matrix completion in the semi-random model, after the preprocessing step, every local minimum of the non-convex objective yields an approximate recovery of the ground-truth matrix.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-gao26b, title = { Semi-Random Noisy and One-Bit Matrix Completion via Nonconvex Optimization }, author = {Gao, Xing and Chen, Binhao and Cheng, Yu}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {2161--2169}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/gao26b/gao26b.pdf}, url = {https://proceedings.mlr.press/v300/gao26b.html}, abstract = { We study low-rank matrix completion in the \textit{semi-random model}, where each entry $(i, j)$ is observed independently with an unknown probability $p_{i,j} \ge p$, in contrast to the standard model with a uniform probability $p$. While prior work has shown that nonconvex approach succeeds in the semi-random model for exact observations [CG18], it remains unclear whether similar guarantees extend to more general observation model, such as noisy or one-bit measurements. In this paper, we give a unified framework for semi-random matrix recovery applicable to a broad family of observation models. Our approach builds on the preprocessing step of [CG18] to restore regularity conditions that are violated under adversarial sampling, and leverages the primal-dual framework of [ZWYG18] to obtain near-optimal recovery guarantees. As concrete corollaries, we show that for both noisy and one-bit matrix completion in the semi-random model, after the preprocessing step, every local minimum of the non-convex objective yields an approximate recovery of the ground-truth matrix. } }
Endnote
%0 Conference Paper %T Semi-Random Noisy and One-Bit Matrix Completion via Nonconvex Optimization %A Xing Gao %A Binhao Chen %A Yu Cheng %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-gao26b %I PMLR %P 2161--2169 %U https://proceedings.mlr.press/v300/gao26b.html %V 300 %X We study low-rank matrix completion in the \textit{semi-random model}, where each entry $(i, j)$ is observed independently with an unknown probability $p_{i,j} \ge p$, in contrast to the standard model with a uniform probability $p$. While prior work has shown that nonconvex approach succeeds in the semi-random model for exact observations [CG18], it remains unclear whether similar guarantees extend to more general observation model, such as noisy or one-bit measurements. In this paper, we give a unified framework for semi-random matrix recovery applicable to a broad family of observation models. Our approach builds on the preprocessing step of [CG18] to restore regularity conditions that are violated under adversarial sampling, and leverages the primal-dual framework of [ZWYG18] to obtain near-optimal recovery guarantees. As concrete corollaries, we show that for both noisy and one-bit matrix completion in the semi-random model, after the preprocessing step, every local minimum of the non-convex objective yields an approximate recovery of the ground-truth matrix.
APA
Gao, X., Chen, B. & Cheng, Y.. (2026). Semi-Random Noisy and One-Bit Matrix Completion via Nonconvex Optimization . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:2161-2169 Available from https://proceedings.mlr.press/v300/gao26b.html.

Related Material