2021/01/15 by Kyriakos Axiotis, Axiotis, Kyriakos, Maxim Sviridenko +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2101.06262
openalex publication_date 2021/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose greedy and local search algorithms for rank-constrained convex optimization, namely solving \undersetrank(A)≤ r^*min R(A) given a convex function R:ℝm× n→ ℝ and a parameter r^*. These algorithms consist of repeating two steps: (a) adding a new rank-1 matrix to A and (b) enforcing the rank constraint on A. We refine and improve the theoretical analysis of Shalev-Shwartz et al. (2011), and show that if the rank-restricted condition number of R is κ, a solution A with rank O(r^*⋅ min\κlog \fracR(0)-R(A^*)ε, κ2\) and R(A) ≤ R(A^*) + ε can be recovered, where A^* is the optimal solution. This significantly generalizes associated results on sparse convex optimization, as well as rank-constrained convex optimization for smooth functions. We then introduce new practical variants of these algorithms that have superior runtime and recover better solutions in practice. We demonstrate the versatility of these methods on a wide range of applications involving matrix completion and robust principal component analysis.