6 papers
An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs
Pan Peng, Yuyang Wang, Joy Qiping Yang +1
We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\var…
Entropy Equivalence Testing
Clément L. Canonne, Yash Pote, Jonathan Scarlett +1
We introduce the problem of \emph{entropy equivalence testing} for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution tes…
Gaussian Mean Testing under Truncation
Clément L. Canonne, Themis Gouleakis, Yuhao Wang +1
We consider the task of Gaussian mean testing, that is, of testing whether a high-dimensional vector perturbed by white noise has large magnitude, or is the zero vector. This quest…
Asymptotics of Language Model Alignment
Joy Qiping Yang, Salman Salamatian, Ziteng Sun +2
Let denote a generative language model. Let denote a reward model that returns a scalar that captures the degree at which a draw from is preferred. The goal of language…
Simpler Distribution Testing with Little Memory
Clément L. Canonne, Joy Qiping Yang
We consider the question of distribution testing (specifically, uniformity and closeness testing) in the streaming setting, \ie under stringent memory constraints. We improve on th…
Learning bounded-degree polytrees with known skeleton
Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya +1
We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesi…