Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems

Yash Deshpande, Andrea Montanari
Proceedings of The 28th Conference on Learning Theory, PMLR 40:523-562, 2015.

Abstract

Given a large data matrix A∈\mathbbR^n\times n, we consider the problem of determining whether its entries are i.i.d. from some known marginal distribution A_ij∼P_0, or instead A contains a principal submatrix A_\sf Q,\sf Q whose entries have marginal distribution A_ij∼P_1≠P_0. As a special case, the hidden (or planted) clique problem is finding a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided |\sf Q|\ge C \log n for a suitable constant C. However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when |\sf Q| = o(\sqrtn). Recently, \citemeka2013association proposed a method to establish lower bounds for the hidden clique problem within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree-4 SOS relaxation, and study the construction of \citemeka2013association to prove that SOS fails unless k\ge C\,n^1/3/\log n. An argument presented by \citeBarakLectureNotes implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moment method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erdös-Renyi random graph.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Deshpande15, title = {Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems}, author = {Deshpande, Yash and Montanari, Andrea}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {523--562}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Deshpande15.pdf}, url = {https://proceedings.mlr.press/v40/Deshpande15.html}, abstract = {Given a large data matrix A∈\mathbbR^n\times n, we consider the problem of determining whether its entries are i.i.d. from some known marginal distribution A_ij∼P_0, or instead A contains a principal submatrix A_\sf Q,\sf Q whose entries have marginal distribution A_ij∼P_1≠P_0. As a special case, the hidden (or planted) clique problem is finding a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided |\sf Q|\ge C \log n for a suitable constant C. However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when |\sf Q| = o(\sqrtn). Recently, \citemeka2013association proposed a method to establish lower bounds for the hidden clique problem within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree-4 SOS relaxation, and study the construction of \citemeka2013association to prove that SOS fails unless k\ge C\,n^1/3/\log n. An argument presented by \citeBarakLectureNotes implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moment method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erdös-Renyi random graph. } }
Endnote
%0 Conference Paper %T Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems %A Yash Deshpande %A Andrea Montanari %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Deshpande15 %I PMLR %P 523--562 %U https://proceedings.mlr.press/v40/Deshpande15.html %V 40 %X Given a large data matrix A∈\mathbbR^n\times n, we consider the problem of determining whether its entries are i.i.d. from some known marginal distribution A_ij∼P_0, or instead A contains a principal submatrix A_\sf Q,\sf Q whose entries have marginal distribution A_ij∼P_1≠P_0. As a special case, the hidden (or planted) clique problem is finding a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided |\sf Q|\ge C \log n for a suitable constant C. However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when |\sf Q| = o(\sqrtn). Recently, \citemeka2013association proposed a method to establish lower bounds for the hidden clique problem within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree-4 SOS relaxation, and study the construction of \citemeka2013association to prove that SOS fails unless k\ge C\,n^1/3/\log n. An argument presented by \citeBarakLectureNotes implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moment method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erdös-Renyi random graph.
RIS
TY - CPAPER TI - Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems AU - Yash Deshpande AU - Andrea Montanari BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Deshpande15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 523 EP - 562 L1 - http://proceedings.mlr.press/v40/Deshpande15.pdf UR - https://proceedings.mlr.press/v40/Deshpande15.html AB - Given a large data matrix A∈\mathbbR^n\times n, we consider the problem of determining whether its entries are i.i.d. from some known marginal distribution A_ij∼P_0, or instead A contains a principal submatrix A_\sf Q,\sf Q whose entries have marginal distribution A_ij∼P_1≠P_0. As a special case, the hidden (or planted) clique problem is finding a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided |\sf Q|\ge C \log n for a suitable constant C. However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when |\sf Q| = o(\sqrtn). Recently, \citemeka2013association proposed a method to establish lower bounds for the hidden clique problem within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree-4 SOS relaxation, and study the construction of \citemeka2013association to prove that SOS fails unless k\ge C\,n^1/3/\log n. An argument presented by \citeBarakLectureNotes implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moment method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erdös-Renyi random graph. ER -
APA
Deshpande, Y. & Montanari, A.. (2015). Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:523-562 Available from https://proceedings.mlr.press/v40/Deshpande15.html.

Related Material