Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique

Guy Bresler, Tianze Jiang
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5850-5889, 2023.

Abstract

Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as detection or recovery, appear to have different computational limits. A detection-recovery gap for PDS was substantiated in the form of a precise conjecture given by Chen and Xu (2014) (based on the parameter values for which a convexified MLE succeeds), and then shown to hold for low-degree polynomial algorithms by Schramm and Wein (2022) and for MCMC algorithms for Ben Arous et al. (2020). In this paper we demonstrate that a slight variation of the Planted Clique Hypothesis with secret leakage (introduced in Brennan and Bresler (2020)), implies a detection-recovery gap for PDS. In the same vein, we also obtain a sharp lower bound for refutation, yielding a detection-refutation gap. Our methods build on the framework of Brennan and Bresler (2020) to construct average-case reductions mapping secret leakage Planted Clique to appropriate target problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-bresler23a, title = {Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique}, author = {Bresler, Guy and Jiang, Tianze}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {5850--5889}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/bresler23a/bresler23a.pdf}, url = {https://proceedings.mlr.press/v195/bresler23a.html}, abstract = {Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as detection or recovery, appear to have different computational limits. A detection-recovery gap for PDS was substantiated in the form of a precise conjecture given by Chen and Xu (2014) (based on the parameter values for which a convexified MLE succeeds), and then shown to hold for low-degree polynomial algorithms by Schramm and Wein (2022) and for MCMC algorithms for Ben Arous et al. (2020). In this paper we demonstrate that a slight variation of the Planted Clique Hypothesis with secret leakage (introduced in Brennan and Bresler (2020)), implies a detection-recovery gap for PDS. In the same vein, we also obtain a sharp lower bound for refutation, yielding a detection-refutation gap. Our methods build on the framework of Brennan and Bresler (2020) to construct average-case reductions mapping secret leakage Planted Clique to appropriate target problems. } }
Endnote
%0 Conference Paper %T Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique %A Guy Bresler %A Tianze Jiang %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-bresler23a %I PMLR %P 5850--5889 %U https://proceedings.mlr.press/v195/bresler23a.html %V 195 %X Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as detection or recovery, appear to have different computational limits. A detection-recovery gap for PDS was substantiated in the form of a precise conjecture given by Chen and Xu (2014) (based on the parameter values for which a convexified MLE succeeds), and then shown to hold for low-degree polynomial algorithms by Schramm and Wein (2022) and for MCMC algorithms for Ben Arous et al. (2020). In this paper we demonstrate that a slight variation of the Planted Clique Hypothesis with secret leakage (introduced in Brennan and Bresler (2020)), implies a detection-recovery gap for PDS. In the same vein, we also obtain a sharp lower bound for refutation, yielding a detection-refutation gap. Our methods build on the framework of Brennan and Bresler (2020) to construct average-case reductions mapping secret leakage Planted Clique to appropriate target problems.
APA
Bresler, G. & Jiang, T.. (2023). Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:5850-5889 Available from https://proceedings.mlr.press/v195/bresler23a.html.

Related Material