Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2019 | JOURNAL OF MACHINE LEARNING RESEARCH | strong duality,non-convex optimization,matrix factorization,matrix completion,robust principal component analysis,sample complexity |
DocType | Volume | Issue |
Journal | 20 | 102 |
ISSN | Citations | PageRank |
1532-4435 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria-Florina Balcan | 1 | 1445 | 105.01 |
| Yingyu Liang | 2 | 393 | 31.39 |
| Zhao Song | 3 | 177 | 25.62 |
| David P. Woodruff | 4 | 2156 | 142.38 |
| Hongyang Zhang | 5 | 110 | 8.33 |