Fast Low-Rank Matrix Estimation without the Condition Number

摘要: In this paper, we study the general problem of optimizing a convex function $F(L)$ over set $p \times p$ matrices, subject to rank constraints on $L$. However, existing first-order methods for solving such problems either are too slow converge, or require multiple invocations singular value decompositions. On other hand, factorization-based non-convex algorithms, while being much faster, stringent assumptions \emph{condition number} optimum. provide novel algorithmic framework that achieves best both worlds: asymptotically as fast factorization methods, requiring no dependency condition number. We instantiate our three important matrix estimation impact several practical applications; (i) \emph{nonlinear} variant affine minimization, (ii) logistic PCA, and (iii) precision in probabilistic graphical model learning. We then derive explicit bounds sample complexity well running time approach, show it possible cases. also an extensive range experimental results, demonstrate algorithm provides very attractive tradeoff between accuracy time.