Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912960403734528 |
|---|---|
| author | Bertsimas, Dimitris Cory-Wright, Ryan Lo, Sean Pauphilet, Jean |
| author_facet | Bertsimas, Dimitris Cory-Wright, Ryan Lo, Sean Pauphilet, Jean |
| contents | Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible. Unfortunately, existing methods for matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not provide an instance-wise certificate of optimality. We reexamine matrix completion with an optimality-oriented eye. We reformulate low-rank matrix completion problems as convex problems over the non-convex set of projection matrices and implement a disjunctive branch-and-bound scheme that solves them to certifiable optimality. Further, we derive a novel and often near-exact class of convex relaxations by decomposing a low-rank matrix as a sum of rank-one matrices and incentivizing that two-by-two minors in each rank-one matrix have determinant zero. In numerical experiments, our new convex relaxations decrease the optimality gap by two orders of magnitude compared to existing attempts, and our disjunctive branch-and-bound scheme solves $n \times m$ rank-$k$ matrix completion problems to certifiable optimality or near optimality in hours for $\max \{m, n\} \leq 2500$ and $k \leq 5$. Moreover, this reduction in the training error translates into an average $2\%$--$50\%$ reduction in the test set error compared with alternating minimization-based methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_12292 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion Bertsimas, Dimitris Cory-Wright, Ryan Lo, Sean Pauphilet, Jean Machine Learning Optimization and Control Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible. Unfortunately, existing methods for matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not provide an instance-wise certificate of optimality. We reexamine matrix completion with an optimality-oriented eye. We reformulate low-rank matrix completion problems as convex problems over the non-convex set of projection matrices and implement a disjunctive branch-and-bound scheme that solves them to certifiable optimality. Further, we derive a novel and often near-exact class of convex relaxations by decomposing a low-rank matrix as a sum of rank-one matrices and incentivizing that two-by-two minors in each rank-one matrix have determinant zero. In numerical experiments, our new convex relaxations decrease the optimality gap by two orders of magnitude compared to existing attempts, and our disjunctive branch-and-bound scheme solves $n \times m$ rank-$k$ matrix completion problems to certifiable optimality or near optimality in hours for $\max \{m, n\} \leq 2500$ and $k \leq 5$. Moreover, this reduction in the training error translates into an average $2\%$--$50\%$ reduction in the test set error compared with alternating minimization-based methods. |
| title | Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2305.12292 |