Doctoral Speaking Skills Talk - Jeff Xu June 5, 2025 11:00am — 12:00pm Location: In Person - Gates Hillman 7101 Speaker: JEFF XU , Ph.D. Student, Computer Science Department, Carnegie Mellon University https://www.andrew.cmu.edu/user/sichaoxu/ Smooth Tradoff for Tensor PCA in Polynomial Time Tensor Principal Component Analysis (PCA) is a canonical problem in high-dimensional statistical inferences. Prior works have shown the success of various spectral algorithms essentially matching the conjectured computational thresholds for this problem. It is also known that (at least) in the sub-exponential time regime, similar to random CSP refutation, Tensor PCA exhibits a smooth tradeoff in signal-strength and runtime: increasing run-time allows one to detect a weaker signal. However, it is not clear whether such tradeoff appears in the polynomial-time regime. Recently, the work of Bandeira et al. makes partial progress by establishing a smooth trade-off in a “limited” polytime regime via techniques from free probability. In this talk, we give a self-contained combinatorial argument to establish a smooth tradeoff in the full runtime. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement Add event to Google Add event to iCal
