Robust Matrix Completion with Heavy-tailed Noise
This paper studies low-rank matrix completion in the presence of heavy-tailed
and possibly asymmetric noise, where we aim to estimate an underlying low-rank
matrix given a set of highly incomplete noisy entries. Though the matrix
completion problem has attracted much attention in the past decade, there is
still lack of theoretical understanding when the observations are contaminated
by heavy-tailed noises. Prior theory falls short of explaining the empirical
results and is unable to capture the optimal dependence of the estimation error
on the noise level. In this paper, we adopt an adaptive Huber loss to
accommodate heavy-tailed noise, which is robust against large and possibly
asymmetric errors when the parameter in the loss function is carefully designed
to balance the Huberization biases and robustness to outliers. Then, we propose
an efficient nonconvex algorithm via a balanced low-rank Burer-Monteiro matrix
factorization and gradient decent with robust spectral initialization. We prove
that under merely bounded second moment condition on the error distributions,
rather than the sub-Gaussian assumption, the Euclidean error of the iterates
generated by the proposed algorithm decrease geometrically fast until achieving
a minimax-optimal statistical estimation error, which has the same order as
that in the sub-Gaussian case. The key technique behind this significant
advancement is a powerful leave-one-out analysis framework. The theoretical
results are corroborated by our simulation studies.