  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.
