  Always-valid concentration inequalities are increasingly used as performance
measures for online statistical learning, notably in the learning of generative
models and supervised learning. Such inequality advances the online learning
algorithms design by allowing random, adaptively chosen sample sizes instead of
a fixed pre-specified size in offline statistical learning. However,
establishing such an always-valid type result for the task of matrix completion
is challenging and far from understood in the literature. Due to the importance
of such type of result, this work establishes and devises the always-valid risk
bound process for online matrix completion problems. Such theoretical advances
are made possible by a novel combination of non-asymptotic martingale
concentration and regularized low-rank matrix regression. Our result enables a
more sample-efficient online algorithm design and serves as a foundation to
evaluate online experiment policies on the task of online matrix completion.
