论文标题
低率矩阵恢复，非二次损失：投影梯度方法和规律性投影Oracle
Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
论文作者
论文摘要
现有的低级别矩阵恢复的结果主要集中在二次损失上，二次损失具有良好的特性，例如受限的强凸/平滑度（RSC/RSM）以及所有低级矩阵的井条件。但是，许多有趣的问题涉及更一般的非二次损失，这些损失无法满足此类特性。对于这些问题，标准的非概念方法，例如受到受限制的预测梯度下降（又称迭代硬阈值）和burer-monteiro分解的方法可能具有较差的经验表现，并且没有令人满意的理论来保证这些算法的全球和封装。 在本文中，我们表明，可证明的低级别恢复和非二次损失的关键组成部分是规律性投影甲骨文。该甲骨文将迭代限制为在适当的有限集中的低级矩阵，在该集合中，损失函数的行为良好，满足了一组近似RSC/RSM条件。因此，我们分析了配备了这种甲骨文的（平均）投射的梯度方法，并证明它在全球和线性上收敛。我们的结果适用于广泛的非二次低级别估计问题，包括一个位矩阵传感/完成，个性化等级聚合以及具有等级约束的更广泛概括的线性模型。
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.
