论文标题
在莫里斯类别的莫里斯类别中使用低级多项式的假设检验
Hypothesis testing with low-degree polynomials in the Morris class of exponential families
论文作者
论文摘要
低级多项式算法的分析是一种强大的，新的最受欢迎的方法，用于预测假设测试问题中的计算阈值。当前技术的一种局限性是它们限制对Bernoulli和Gaussian分布。我们通过对莫里斯类指数家族的假设检验进行低度分析来扩展这种可能性，从而对高斯，泊松，伽马，二项式，二项式，负二项式和广义双曲线分布提供统一的处理。然后，我们提供了几种算法应用程序。 1。在通过指数族家族观察到随机信号的模型中，低度多项式的成功或失败受$ z $ -SCORE重叠的控制，这是$ z $ - 分数向量的内部产品，相对于两个独立信号的独立副本的无效分布。 2。在相同的模型中，低度多项式的测试表现出通道单调性：上述分布允许假设检验的计算成本进行总排序，该标量参数描述了方差如何依赖于指数族中的均值。 3。在具有特定非高斯噪声分布的尖峰矩阵模型中，除非允许在单个矩阵条目中任意较大程度的多项式，否则低度预测是不正确的。这表明，正如Ding，Hopkins和Steurer（2020年）对具有重尾噪声的尖刺矩阵模型最近提出的那样，多项式概括了自我避免的步行及其变体，这是该模型的次优。因此，低级多项式似乎在鲁棒性和对特定模型进行了良好的性能之间提供了权衡，并且可能与需要算法首先检查输入的问题困难，然后使用一些中间计算来从几个推论子例子之一中进行选择。
Analysis of low-degree polynomial algorithms is a powerful, newly-popular method for predicting computational thresholds in hypothesis testing problems. One limitation of current techniques for this analysis is their restriction to Bernoulli and Gaussian distributions. We expand this range of possibilities by performing the low-degree analysis of hypothesis testing for the Morris class of exponential families, giving a unified treatment of Gaussian, Poisson, gamma, binomial, negative binomial, and generalized hyperbolic secant distributions. We then give several algorithmic applications. 1. In models where a random signal is observed through an exponential family, the success or failure of low-degree polynomials is governed by the $z$-score overlap, the inner product of $z$-score vectors with respect to the null distribution of two independent copies of the signal. 2. In the same models, testing with low-degree polynomials exhibits channel monotonicity: the above distributions admit a total ordering by computational cost of hypothesis testing, according to a scalar parameter describing how the variance depends on the mean in an exponential family. 3. In a spiked matrix model with a particular non-Gaussian noise distribution, the low-degree prediction is incorrect unless polynomials with arbitrarily large degree in individual matrix entries are permitted. This shows that polynomials summing over self-avoiding walks and variants thereof, as proposed recently by Ding, Hopkins, and Steurer (2020) for spiked matrix models with heavy-tailed noise, are suboptimal for this model. Thus low-degree polynomials appear to offer a tradeoff between robustness and strong performance fine-tuned to specific models, and may struggle with problems requiring an algorithm to first examine the input and then use some intermediate computation to choose from one of several inference subroutines.
