Non-Convex Matrix Completion and Related Problems via Strong Duality

被引:0
作者
Balcan, Maria-Florina [1 ]
Liang, Yingyu [2 ]
Song, Zhao [3 ,4 ]
Woodruff, David P. [1 ]
Zhang, Hongyang [1 ,5 ]
机构
[1] Carnegie Mellon Univ, Pittsburgh, PA 15213 USA
[2] Univ Wisconsin, Madison, WI USA
[3] UT Austin, Austin, TX USA
[4] Harvard Univ, Cambridge, MA 02138 USA
[5] TTIC, Chicago, IL 60637 USA
关键词
strong duality; non-convex optimization; matrix factorization; matrix completion; robust principal component analysis; sample complexity; RANK; OPTIMIZATION; INCOHERENCE;
D O I
暂无
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and the dual have the same optimum. This has been well understood for convex optimization, but little was known for non-convex problems. We propose a novel analytical framework and prove that under certain dual conditions, the optimal solution of the matrix factorization program is the same as that of its bi-dual and thus the global optimality of the non-convex program can be achieved by solving its bi-dual which is convex. These dual conditions are satisfied by a wide class of matrix factorization problems, although matrix factorization is hard to solve in full generality. This analytical framework may be of independent interest to non-convex optimization more broadly. We apply our framework to two prototypical matrix factorization problems: matrix completion and robust Principal Component Analysis. These are examples of efficiently recovering a hidden matrix given limited reliable observations. Our framework shows that exact recoverability and strong duality hold with nearly-optimal sample complexity for the two problems.
引用
收藏
页数:56
相关论文
共 94 条
[1]   NOISY MATRIX DECOMPOSITION VIA CONVEX RELAXATION: OPTIMAL RATES IN HIGH DIMENSIONS [J].
Agarwal, Alekh ;
Negahban, Sahand ;
Wainwright, Martin J. .
ANNALS OF STATISTICS, 2012, 40 (02) :1171-1197
[2]   Finding Approximate Local Minima Faster than Gradient Descent [J].
Agarwal, Naman ;
Allen-Zhu, Zeyuan ;
Bullins, Brian ;
Hazan, Elad ;
Ma, Tengyu .
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, :1195-1199
[3]   Blind Deconvolution Using Convex Programming [J].
Ahmed, Ali ;
Recht, Benjamin ;
Romberg, Justin .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2014, 60 (03) :1711-1732
[4]   INAPPROXIMABILITY RESULTS FOR MAXIMUM EDGE BICLIQUE, MINIMUM LINEAR ARRANGEMENT, AND SPARSEST CUT [J].
Ambuehl, Christoph ;
Mastrolilli, Monaldo ;
Svensson, Ola .
SIAM JOURNAL ON COMPUTING, 2011, 40 (02) :567-596
[5]  
Anandkumar A, 2014, J MACH LEARN RES, V15, P2773
[6]  
[Anonymous], ARXIV170206525
[7]  
[Anonymous], INNOVATIONS THEORETI
[8]  
[Anonymous], 2015, ADV NEURAL INFORM PR, DOI DOI 10.2991/978-94-6239-102-4_114
[9]  
[Anonymous], 2017, C LEARNING THEORY
[10]  
[Anonymous], 2017, J MACHINE LEARNING R