Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing

arXiv:2403.07862v1 Announce Type: cross
Abstract: We study when low coordinate degree functions (LCDF) -- linear combinations of functions depending on small subsets of entries of a vector -- can hypothesis test between high-dimensional probability measures. These functions are a generalization, proposed in Hopkins' 2018 thesis but seldom studied since, of low degree polynomials (LDP), a class widely used in recent literature as a proxy for all efficient algorithms for tasks in statistics and optimization. Instead of the orthogonal polynomial decompositions …

abstract algorithms arxiv computational cs.ds functions hypothesis linear low math.pr math.st probability small stat.ml stat.th study subsets test testing thesis type vector