Open Problem: Tightness of maximum likelihood semidefinite relaxations

Afonso S. Bandeira, Yuehaw Khoo, Amit Singer
Proceedings of The 27th Conference on Learning Theory, PMLR 35:1265-1267, 2014.

Abstract

We have observed an interesting, yet unexplained, phenomenon: Semidefinite programming (SDP) based relaxations of maximum likelihood estimators (MLE) tend to be tight in recovery problems with noisy data, even when MLE cannot exactly recover the ground truth. Several results establish tightness of SDP based relaxations in the regime where exact recovery from MLE is possible. However, to the best of our knowledge, their tightness is not understood beyond this regime. As an illustrative example, we focus on the generalized Procrustes problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-bandeira14, title = {Open Problem: Tightness of maximum likelihood semidefinite relaxations}, author = {Bandeira, Afonso S. and Khoo, Yuehaw and Singer, Amit}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {1265--1267}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/bandeira14.pdf}, url = {https://proceedings.mlr.press/v35/bandeira14.html}, abstract = {We have observed an interesting, yet unexplained, phenomenon: Semidefinite programming (SDP) based relaxations of maximum likelihood estimators (MLE) tend to be tight in recovery problems with noisy data, even when MLE cannot exactly recover the ground truth. Several results establish tightness of SDP based relaxations in the regime where exact recovery from MLE is possible. However, to the best of our knowledge, their tightness is not understood beyond this regime. As an illustrative example, we focus on the generalized Procrustes problem.} }
Endnote
%0 Conference Paper %T Open Problem: Tightness of maximum likelihood semidefinite relaxations %A Afonso S. Bandeira %A Yuehaw Khoo %A Amit Singer %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-bandeira14 %I PMLR %P 1265--1267 %U https://proceedings.mlr.press/v35/bandeira14.html %V 35 %X We have observed an interesting, yet unexplained, phenomenon: Semidefinite programming (SDP) based relaxations of maximum likelihood estimators (MLE) tend to be tight in recovery problems with noisy data, even when MLE cannot exactly recover the ground truth. Several results establish tightness of SDP based relaxations in the regime where exact recovery from MLE is possible. However, to the best of our knowledge, their tightness is not understood beyond this regime. As an illustrative example, we focus on the generalized Procrustes problem.
RIS
TY - CPAPER TI - Open Problem: Tightness of maximum likelihood semidefinite relaxations AU - Afonso S. Bandeira AU - Yuehaw Khoo AU - Amit Singer BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-bandeira14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 1265 EP - 1267 L1 - http://proceedings.mlr.press/v35/bandeira14.pdf UR - https://proceedings.mlr.press/v35/bandeira14.html AB - We have observed an interesting, yet unexplained, phenomenon: Semidefinite programming (SDP) based relaxations of maximum likelihood estimators (MLE) tend to be tight in recovery problems with noisy data, even when MLE cannot exactly recover the ground truth. Several results establish tightness of SDP based relaxations in the regime where exact recovery from MLE is possible. However, to the best of our knowledge, their tightness is not understood beyond this regime. As an illustrative example, we focus on the generalized Procrustes problem. ER -
APA
Bandeira, A.S., Khoo, Y. & Singer, A.. (2014). Open Problem: Tightness of maximum likelihood semidefinite relaxations. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:1265-1267 Available from https://proceedings.mlr.press/v35/bandeira14.html.

Related Material