4 papers
Combinatorial Sparse PCA Beyond the Spiked Identity Model
Syamantak Kumar, Purnamrita Sarkar, Kevin Tian +1
Sparse PCA is one of the most well-studied problems in high-dimensional statistics. In this problem, we are given samples from a distribution with covariance , whose top eigenv…
Attn-QAT: 4-Bit Attention With Quantization-Aware Training
Peiyuan Zhang, Matthew Noto, Wenxuan Tan +4
Achieving reliable 4-bit attention is a prerequisite for end-to-end FP4 computation on emerging FP4-capable GPUs, yet attention remains the main obstacle due to FP4's tiny dynamic…
An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
Siyu Chen, Theodor Misiakiewicz, Ilias Zadik +1
Bandeira et al. (2022) introduced the Franz-Parisi (FP) criterion for characterizing the computational hard phases in statistical detection problems. The FP criterion, based on an…
Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
Xifan Yu, Ilias Zadik, Peiyuan Zhang
We study the computational limits of the following general hypothesis testing problem. Let H=H_n be an \emph{arbitrary} undirected graph on n vertices. We study the detection task…