Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
This addresses a theoretical gap for practitioners in machine learning and statistics dealing with non-quadratic low-rank estimation problems, such as one-bit matrix sensing and generalized linear models, though it is incremental as it builds on existing projection-based methods.
The paper tackles the problem of low-rank matrix recovery with non-quadratic losses, which lack favorable properties like restricted strong convexity/smoothness, by introducing a regularity projection oracle to ensure global and linear convergence of a projected gradient method.
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.