Low-rank matrix recovery with non-quadratic loss: projected gradient
  method and regularity projection oracle
  Existing results for low-rank matrix recovery largely focus on quadratic
loss, which enjoys favorable properties such as restricted strong
convexity/smoothness (RSC/RSM) and well conditioning over all low rank
matrices. However, many interesting problems involve more general,
non-quadratic losses, which do not satisfy such properties. For these problems,
standard nonconvex approaches such as rank-constrained projected gradient
descent (a.k.a. iterative hard thresholding) and Burer-Monteiro factorization
could have poor empirical performance, and there is no satisfactory theory
guaranteeing global and fast convergence for these algorithms.
  In this paper, we show that a critical component in provable low-rank
recovery with non-quadratic loss is a regularity projection oracle. This oracle
restricts iterates to low-rank matrices within an appropriate bounded set, over
which the loss function is well behaved and satisfies a set of approximate
RSC/RSM conditions. Accordingly, we analyze an (averaged) projected gradient
method equipped with such an oracle, and prove that it converges globally and
linearly. Our results apply to a wide range of non-quadratic low-rank
estimation problems including one bit matrix sensing/completion, individualized
rank aggregation, and more broadly generalized linear models with rank
constraints.
