Always Valid Risk Monitoring for Online Matrix Completion
This work addresses a foundational gap in online statistical learning for matrix completion, benefiting researchers and practitioners in fields like recommendation systems and data analysis.
The paper tackles the challenge of establishing always-valid risk bounds for online matrix completion, which was previously unsolved, by developing a theoretical framework that enables more sample-efficient online algorithm design.
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.