In this paper, we propose a novel method for matrix completion under general non-uniform missing structures. By controlling an upper bound of a novel balancing error, we construct weights that can actively adjust for the non-uniformity in the empirical risk without explicitly modeling the observation probabilities, and can be computed efficiently via convex optimization. The recovered matrix based on the proposed weighted empirical risk enjoys appealing theoretical guarantees. In particular, the proposed method achieves a stronger guarantee than existing work in terms of the scaling with respect to the observation probabilities, under asymptotically heterogeneous missing settings (where entry-wise observation probabilities can be of different orders). These settings can be regarded as a better theoretical model of missing patterns with highly varying probabilities. We also provide a new minimax lower bound under a class of heterogeneous settings. Numerical experiments are also provided to demonstrate the effectiveness of the proposed method.
翻译:在本文中,我们提出了在一般非统一缺失结构下完成矩阵的新方法。通过控制新平衡错误的上限,我们构建了能够积极适应经验风险不一致性的加权,而没有明确地模拟观察概率,并且可以通过曲线优化有效计算。基于拟议加权经验风险的回收矩阵享有令人兴奋的理论保证。特别是,拟议方法在观测概率的尺度方面比现有工作有更强的保障,即:在零星差异缺失环境(即入点观测概率可能不同顺序不同)下,在观察到概率的尺度上(即入点观测概率可能不同),这些加权可以被视为一种更好的缺失模式的理论模型,其概率差异很大。我们还提供了一种新的小缩轴,在多种环境的类别下,我们提供了一种较低的新缩缩缩缩。还提供了数字实验,以证明拟议方法的有效性。