机器学习与数据科学博士生系列论坛（第四十四期）—— Low-Degree Polynomial for Predicting computational hardness of Hypothesis Testing
报告人：Yang Xu (PKU)
时间：2023-3-3 16:00-17:00
地点：腾讯会议 723 1564 5542
摘要：
Many classical problems in statistics, such as the planted clique problem and the spiked tensor model, are believed to exhibit the information-computation gap. The low-degree polynomial method, originated in the study of the sum-of-squares (SoS) hierarchy of convex programs, provides an understanding of computational hardness in average-case problems through low-degree likelihood ratio (LDLR).
In this talk, we will briefly introduce the low-degree polynomial method based on the note of Kunisky et al. [2019]. The low-degree polynomial method for estimation task [Schramm and Wein, 2020] will also be discussed.
