Provable Exactness for Asymmetric Low-Rank SDP Learning
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917475488104448 |
|---|---|
| author | Hu, Enliang |
| author_facet | Hu, Enliang |
| contents | Low-rank factorization is a standard way to make structured optimization problems in machine learning more tractable by replacing matrix variables with compact factors. For positive semidefinite (PSD) variables, the symmetric Burer--Monteiro factorization (sBMF) writes $Z=XX^\top$ with a single low-rank factor $X$. A recent asymmetric alternative (aBMF) writes $Z=XY^\top$ and adds a quadratic penalty $(γ/2)\|X-Y\|_F^2$ to encourage symmetry. This split is attractive because it yields a biconvex objective with alternating convex subproblems, but its practical value depends strongly on how the penalty parameter $γ$ is chosen.
We study a unified regularized aBMF framework and derive an explicit lower bound on $γ$ that guarantees exactness: under mild assumptions, any $γ$ above this threshold makes aBMF and sBMF share the same critical points. This gives a principled way to use the asymmetric formulation without altering the critical-point structure of the symmetric problem. In particular, it answers the open question of whether an exact penalty exists for asymmetric relaxation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1811_01198 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Provable Exactness for Asymmetric Low-Rank SDP Learning Hu, Enliang Machine Learning Optimization and Control Low-rank factorization is a standard way to make structured optimization problems in machine learning more tractable by replacing matrix variables with compact factors. For positive semidefinite (PSD) variables, the symmetric Burer--Monteiro factorization (sBMF) writes $Z=XX^\top$ with a single low-rank factor $X$. A recent asymmetric alternative (aBMF) writes $Z=XY^\top$ and adds a quadratic penalty $(γ/2)\|X-Y\|_F^2$ to encourage symmetry. This split is attractive because it yields a biconvex objective with alternating convex subproblems, but its practical value depends strongly on how the penalty parameter $γ$ is chosen. We study a unified regularized aBMF framework and derive an explicit lower bound on $γ$ that guarantees exactness: under mild assumptions, any $γ$ above this threshold makes aBMF and sBMF share the same critical points. This gives a principled way to use the asymmetric formulation without altering the critical-point structure of the symmetric problem. In particular, it answers the open question of whether an exact penalty exists for asymmetric relaxation. |
| title | Provable Exactness for Asymmetric Low-Rank SDP Learning |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/1811.01198 |