  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.
