  Matrix factorization (MF) has been widely used to discover the low-rank
structure and to predict the missing entries of data matrix. In many real-world
learning systems, the data matrix can be very high-dimensional but sparse. This
poses an imbalanced learning problem, since the scale of missing entries is
usually much larger than that of observed entries, but they cannot be ignored
due to the valuable negative signal. For efficiency concern, existing work
typically applies a uniform weight on missing entries to allow a fast learning
algorithm. However, this simplification will decrease modeling fidelity,
resulting in suboptimal performance for downstream applications.
  In this work, we weight the missing data non-uniformly, and more generically,
we allow any weighting strategy on the missing data. To address the efficiency
challenge, we propose a fast learning method, for which the time complexity is
determined by the number of observed entries in the data matrix, rather than
the matrix size. The key idea is two-fold: 1) we apply truncated SVD on the
weight matrix to get a more compact representation of the weights, and 2) we
learn MF parameters with element-wise alternating least squares (eALS) and
memorize the key intermediate variables to avoid repeating computations that
are unnecessary. We conduct extensive experiments on two recommendation
benchmarks, demonstrating the correctness, efficiency, and effectiveness of our
fast eALS method.
