Abstract: We prove bounds on statistical distances between high-dimensional exchangeable mixture distributions (which we call \emph{permutation mixtures}) and their i.i.d. counterparts. Our results are based on a novel method for controlling $\chi^2$ divergences between exchangeable mixtures, which is tighter than the existing methods of moments or cumulants. At a technical level, a key innovation in our proofs is a new Maclaurin-type inequality for elementary symmetric polynomials of variables that sum to zero and an upper bound on permanents of doubly stochastic positive semidefinite matrices.

Our results imply a de Finetti-style theorem (in the language of Diaconis and Freedman, 1987) and a capacity upper bound for the noisy permutation channel. In particular, when applied to compound decision problems, we tighten the efficiency result of simple decisions in Greenshtein and Ritov (2009) and use empirical Bayes methods to close the gap for competitive distribution estimation in Orlitsky and Suresh (2015).

Based on joint work with Jonathan Niles-Weed (NYU), Yandi Shen (CMU), and Yihong Wu (Yale).

Bio: Yanjun Han is an assistant professor of mathematics and data science at the Courant Institute of Mathematical Sciences and the Center for Data Science, New York University. He received his Ph.D. in Electrical Engineering from Stanford University in Aug 2021, under the supervision of Tsachy Weissman. After that, he spent one year as a postdoctoral scholar at the Simons Institute for the Theory of Computing, UC Berkeley, and another year as a Norbert Wiener postdoctoral associate in the Statistics and Data Science Center at MIT, mentored by Sasha Rakhlin and Philippe Rigollet. His research interests include high-dimensional and nonparametric statistics, interactive decision making, and information theory.