PaperlayerView exact revision on arXiv

Source-linked AI summary

Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira

arXiv:1907.11636v1math.STcs.CCcs.DSstat.ML

TL;DR

High-dimensional inference problems can be statistically solvable yet computationally difficult, and existing evidence does not uniformly quantify these tradeoffs. The notes develop the low-degree method, using the low-degree likelihood ratio to predict computational thresholds, and report agreement with established behavior including sharp tensor-PCA lower bounds while identifying scope limitations in spectral and prior-specific settings.

  • Problem

    High-dimensional inference problems may exhibit gaps between information-theoretic feasibility and bounded-computation feasibility, motivating methods that predict computational thresholds.

  • Method

    The notes survey a self-contained low-degree method that uses the second moment of the low-degree likelihood ratio to predict the power of computationally bounded tests.

  • Results

    The method reproduces widely believed average-case hardness patterns, including a sharp computational transition for spiked Wigner and a soft statistical-versus-runtime tradeoff for spiked tensors.

  • Takeaways & Limitations

    Low-degree calculations provide a simple framework for studying polynomial through nearly-exponential computational regimes and can yield sharp subexponential-time lower-bound predictions for tensor PCA.

  • Takeaways & Limitations

    The framework uses polynomial degree rather than coordinate degree, and its spectral-method connection has unresolved runtime and negative-eigenvalue issues; some sparse-prior regimes are not covered.

Abstract

from arXiv · show

These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensional inference problems. In short, the method posits that a certain quantity -- the second moment of the low-degree likelihood ratio -- gives insight into how much computational time is required to solve a given hypothesis testing problem, which can in turn be used to predict the computational hardness of a variety of statistical inference tasks. While this method originated in the study of the sum-of-squares (SoS) hierarchy of convex programs, we present a self-contained introduction that does not require knowledge of SoS. In addition to showing how to carry out predictions using the method, we include a discussion investigating both rigorous and conjectural consequences of these predictions. These notes include some new results, simplified proofs, and refined conjectures. For instance, we point out a formal connection between spectral methods and the low-degree likelihood ratio, and we give a sharp low-degree lower bound against subexponential-time algorithms for tensor PCA.

Overview

The notes introduce the low-degree method as a broadly applicable way to predict computational hardness in average-case inference. It offers a self-contained alternative perspective related to SoS and reproduces widely believed results across several time-complexity regimes.

  • Overview: The broader motivation is a collection of high-dimensional problems believed to exhibit statistical-versus-computational gaps, including planted structures, component recovery, and random constraint problems.Existing evidence for hardness includes failures of several algorithmic approaches and lower bounds in multiple computational models.
  • Overview: The low-degree method uses the second moment of the low-degree likelihood ratio to study computational hardness in average-case problems.The method is presented as a conjectural computational analogue of classical statistical reasoning.
  • Overview: Its predictions can address polynomial, quasipolynomial, and nearly-exponential runtime regimes.The method is intended to capture an interpretable structural feature associated with problem difficulty rather than posit a single optimal algorithm.
  • Overview: The method emerged from SoS-related work and has been used to capture sharp computational thresholds such as the Kesten–Stigum threshold.The notes situate the method historically within pseudo-calibration and subsequent explicit formulations.
  • Overview: The notes provide a self-contained introduction while largely avoiding technical dependence on the sum-of-squares hierarchy.The connection to SoS is discussed separately rather than required as background.

1 Towards a Computationally-Bounded Decision Theory

This section frames hypothesis testing as deciding between null and alternative distributions, then asks how computational limits alter classical statistical decision theory. It motivates the low-degree likelihood ratio as a way to predict computational thresholds and stat-comp gaps.

  • 1.1 Statistical-to-Computational Gaps in Hypothesis Testing: Hypothesis testing observes data from one of two distributions and seeks a test that identifies the generating distribution with high probability.The notes focus on strong distinguishability, where success probability tends to one.
  • 1.1 Statistical-to-Computational Gaps in Hypothesis Testing: Computational testing restricts distinguishers to functions computable in polynomial time, while later analysis considers other runtime restrictions.This creates a computationally bounded analogue of statistical distinguishability.
  • 1.1 Statistical-to-Computational Gaps in Hypothesis Testing: A stat-comp gap occurs when statistical distinguishability begins at λstat but computational distinguishability is conjectured only above a larger λcomp.The planted clique example illustrates this transition from statistical possibility to computational difficulty.
  • 1.2 Classical Statistical Decision Theory: The likelihood-ratio test is statistically optimal under the Neyman–Pearson tradeoff between type I and type II errors.Thresholding the likelihood ratio maximizes power among tests meeting a specified type I error constraint.
  • 1.3 Basics of the Low-Degree Method: The low-degree conjecture proposes that bounded low-degree likelihood-ratio norms indicate the absence of polynomial-time strong distinguishers, while divergence predicts algorithms with runtime roughly n^D.This extends the classical second-moment perspective from statistical distinguishability to computationally bounded testing.

2 The Additive Gaussian Noise Model

The additive Gaussian noise model compares a signal-plus-noise distribution with a pure-noise null and supports explicit likelihood-ratio calculations. Hermite expansions then express the low-degree likelihood-ratio norm through moments of independent signal replicas.

  • 2 The Additive Gaussian Noise Model: Under the additive Gaussian noise model, the planted distribution observes Y = X + Z, while the null observes Y = Z.The signal X follows a prior Pn and Z has independent standard Gaussian entries.
  • 2 The Additive Gaussian Noise Model: Low-rank matrix and tensor priors produce important instances, including the spiked Wigner matrix model with signal X = λxx⊤.The corresponding task distinguishes a rank-one signal-plus-noise matrix from pure Gaussian noise.
  • 2 The Additive Gaussian Noise Model: The likelihood ratio and its L2 norm can be computed explicitly for the additive Gaussian model.The second-moment calculation rewrites a squared expectation using two independent signal replicas and evaluates a Gaussian moment-generating function.
  • 2 The Low-Degree Likelihood Ratio: The low-degree likelihood ratio is obtained by projecting the likelihood ratio onto polynomials of degree at most D in the Hermite basis.The resulting coefficients are moments of the prior, and the norm admits a replica representation involving X1 and X2.
  • 2 The Low-Degree Likelihood Ratio: The low-degree norm has a simple expression involving a degree-D truncation of exp(⟨X1, X2⟩), distinct from truncating in the monomial basis.The notes distinguish Taylor truncation of the exponential from projection onto the Hermite polynomial subspace.
  • 2 The Low-Degree Likelihood Ratio: Three Hermite-polynomial identities provide alternative proofs that low-degree likelihood-ratio coefficients equal prior moments.The proofs use Gaussian evaluation identities, integration by parts, and generating functions.

3 Examples: Spiked Matrix and Tensor Models

The notes analyze spiked Gaussian tensor and Wigner models with the low-degree method, revealing a soft runtime–signal tradeoff for tensors and a sharp computational threshold for Wigner matrices. These predictions align with known algorithms and lower-bound evidence across polynomial, subexponential, and nearly-exponential regimes.

  • 3.1 The Spiked Tensor Model: For p ≥ 3, tensor PCA exhibits a soft tradeoff between statistical power and runtime extending through the subexponential-time regime.The analysis gives a sharper characterization than previous low-degree analyses.
  • 3.1 The Spiked Tensor Model: The order-p spiked tensor model adds Gaussian noise to a rank-one signal λx^⊗p, with the notes focusing on Rademacher spikes and strong hypothesis testing.The null observes pure Gaussian noise, while the planted model contains the tensor signal.
  • 3.1 The Spiked Tensor Model: λ ≫ n^-p/4D(2-p)/4 predicts an n^O(D)-time tensor distinguisher, whereas λ ≪ n^-p/4D(2-p)/4 predicts no such algorithm under the low-degree proxy.These predictions match established polynomial-time thresholds at λ ≫ n^-p/4.
  • 3.1 The Spiked Tensor Model: λ ≫ n^-p/4-δ(p-2)/4 supports algorithms with runtime exp(Õ(n^δ)), interpolating between polynomial-time and exhaustive-search regimes.The statistical impossibility scale is λ ≪ n^(1-p)/2, which forms the terminal signal level for computational questions.
  • 3.2 The Spiked Wigner Matrix Model: For p = 2, the model becomes spiked Wigner, where PCA succeeds sharply when λ̂ > 1 and fails when λ̂ ≤ 1.For i.i.d. Gaussian or Rademacher priors, the statistical and computational thresholds both equal 1, so there is no statistical–computational gap.
  • 3.2 The Spiked Wigner Matrix Model: For broad spike-prior classes satisfying the stated regularity conditions, the low-degree analysis predicts nearly-exponential hardness below the PCA threshold.The formal result considers λ̂ < 1 and degrees D=o(n/log n), while sparse Rademacher priors with vanishing density are an uncovered exception.

4 More on the Low-Degree Method

The notes examine what the low-degree likelihood ratio can establish about computationally bounded hypothesis tests. They discuss both polynomial proxies and broader efficient-algorithm conjectures, supported by heuristic and formal evidence.

  • 4 More on the Low-Degree Method: The low-degree analysis asks whether the D-LDLR controls the distinguishing power of degree-D polynomials.This restricts classical decision-theoretic analysis to computationally bounded tests.
  • 4 More on the Low-Degree Method: The notes also ask whether the LDLR controls whether any efficient algorithm can distinguish the planted and null distributions.This is presented as a broader conjectural connection between low-degree quantities and computational complexity.

4.1 The LDLR and Thresholding Polynomials

This section examines when the low-degree likelihood-ratio norm predicts distinguishability by thresholding degree-D polynomials. For natural problems and reasonable D, the heuristic is supported, while formal results connect polynomial distinguishability to exponential norm growth.

  • Counterexamples and scope: Artificial counterexamples show that rare bad events or dilution can break naive implications between statistical distinguishability and low-degree norm behavior.The notes therefore suggest restricting positive conjectures to sufficiently homogeneous planted measures and reasonable degree growth.
  • Evidence from natural problems: For natural high-dimensional problems, low-degree norm divergence typically appears only when a corresponding n^Õ(D)-time distinguisher exists or D is unreasonably large.In sparse PCA, the latter means D greatly exceeds the exponent of a trivial exhaustive-search runtime.
  • Overall interpretation: The notes conclude that smoothness of low-degree polynomials generally regularizes the low-degree likelihood ratio, despite artificial counterexamples.This regularization is suggested to be related to hypercontractivity.
  • Questions: The central questions ask whether bounded or diverging low-degree likelihood-ratio norms govern distinguishability by thresholding degree-D polynomials.The first direction asks whether bounded norm rules out such distinguishers; the converse asks whether diverging norm implies one.
  • Formal converse: A formal theorem shows that distinguishing by thresholding low-degree polynomials implies exponential growth of the low-degree likelihood-ratio norm.The result applies when the null distribution has i.i.d. Gaussian or Rademacher coordinates and the planted measure is absolutely continuous with respect to it.
  • Formal converse: Hypercontractivity supplies the proof mechanism by showing that evaluations of low-degree polynomials under weakly dependent distributions are well concentrated.The stated quantitative theorem requires δ ≤ 1/2 · 3^-4kd rather than merely δ = o(1), and its assumptions are most readily available for Gaussian or Rademacher nulls.

4.2 Algorithmic Implications of the LDLR

The notes connect low-degree polynomials and spectral methods to computationally bounded hypothesis testing, while identifying important exceptions and conjectural boundaries. They present evidence that the method predicts algorithmic tradeoffs across testing, estimation, and recovery, but also document limitations and counterexamples.

  • Polynomial Algorithms: Low-degree polynomials serve as a bridge between the low-degree likelihood ratio and computationally bounded algorithms, with degree-D polynomials evaluable in time n^O(D).Special structure can permit faster evaluation, including sparse representations and spectral methods.
  • Robustness and Limitations: A major limitation is random 3-XOR-SAT: Gaussian elimination solves it in polynomial time, even though low-degree, SoS, statistical-query, and cavity methods predict hardness in an intermediate regime.This shows that the method’s hardness predictions are not universally reliable.
  • Spectral Methods: Spectral methods build data-dependent matrices and threshold their largest eigenvalues, often matching the best known polynomial-time performance.This connection motivates interpreting low-degree spectral structure as evidence about algorithmic feasibility.
  • Spectral Methods: SoS success can imply a low-degree spectral method whose maximum positive eigenvalue succeeds, although an uncontrolled negative eigenvalue may prevent polynomial-time execution.The resulting connection is therefore useful but not fully formal.
  • Subexponential Time: For subexponential time exp(n^δ), the conjectured correspondence is degree-n^δ polynomials rather than the larger degree suggested by some direct spectral constructions.Tensor PCA and sparse PCA provide supporting examples for this conjectured runtime-degree relationship.
  • Evidence and Conjectures: The low-degree method has repeatedly matched believed computational thresholds and can predict both sharp transitions and smooth tradeoffs between runtime and statistical power.The notes cite applications including planted clique, community detection, spiked tensors, and related inference problems.
  • Extensions: Low-degree evidence for hard hypothesis testing often extends heuristically to recovery, but testing and recovery have no formal equivalence and can have different thresholds.The notes state that non-trivial estimation typically shares statistical and computational thresholds with strong distinguishing, while warning of exceptions.

A.1 Neyman-Pearson Lemma

The Neyman–Pearson argument reduces optimal simple hypothesis testing to choosing a rejection region based on the likelihood ratio. Under a fixed type-I error constraint, thresholding that ratio maximizes test power.

  • Optimization: A statistical test is determined by its rejection region, and its power can be written as an integral of the likelihood ratio over that region.The optimization constrains the null probability of the rejection region.
  • Optimal Test: The likelihood-ratio threshold region R⋆ := {Y : L(Y) > η} maximizes power among rejection regions satisfying the same null-probability constraint.This is the operational content of the Neyman–Pearson lemma in the notes.

A.2 Equivalence of Symmetric and Asymmetric Noise Models

The notes show that asymmetric Gaussian noise models can be converted to standard symmetric models without changing the statistical task. The equivalences are established by explicit symmetrization, noise completion, and averaging constructions.

  • Spiked Wigner: An asymmetric spiked Wigner observation can be symmetrized into the standard symmetric model by replacing Y with 1/2(Y + Y^⊤).The resulting matrix has the stated symmetric Gaussian diagonal and off-diagonal variances.
  • Spiked Wigner: The standard symmetric Wigner model can be converted back by adding an independent skew-symmetric Gaussian component, yielding a matrix distributed as the asymmetric model.The added component restores the skew-symmetric noise absent from the symmetric observation.
  • Spiked Tensor: For tensors, k independent observations x + N(0,1) are equivalent to one observation x + N(0,1/k) obtained by averaging.The converse uses simplex vectors and an independent Gaussian vector to reconstruct jointly distributed samples.

A.3 Low-Degree Analysis of Spiked Wigner Above the PCA Threshold

The spiked Wigner low-degree analysis uses a moment bound to show divergence of the low-degree likelihood-ratio norm above the PCA threshold. Choosing a growing but sublinear degree establishes the claimed asymptotic behavior.

  • Moment Bound: For any degree d ≤ D, the proof applies the standard moment bound to control the low-degree likelihood-ratio calculation.The argument follows the proof strategy used for the analogous spiked tensor result.
  • Above Threshold: When λ̂ > 1, the relevant quantity diverges as n → ∞ for a degree satisfying ω(1) ≤ d ≤ o(n).Thus, a growing sublinear degree suffices above the PCA threshold.

B Hermite Polynomials

This section defines univariate and multivariate Hermite polynomials and establishes their completeness and orthonormality under Gaussian measure. It also proves integration-by-parts, translation, and generating-function identities used to analyze the low-degree likelihood ratio.

  • Definitions and basic properties: Hermite polynomials are orthogonal with respect to the standard Gaussian measure and are defined recursively in the univariate case.The normalized univariate family is introduced as a complete orthonormal system for L2(N(0,1)).
  • Multivariate extension: The normalized N-variate Hermite polynomials form a complete orthonormal system for L2(N(0, I_N)).The multivariate polynomials are constructed as products of univariate Hermite polynomials indexed by multi-indices.
  • Identities: The integration-by-parts identity is proved by induction using the Hermite recursion and the base cases h_0(y)=1 and h_1(y)=y.The proof assumes the function and its derivatives grow no faster than O(exp(|x|^α)) for α∈(0,2).
  • Identities: The translation identity is established for every degree k≥0 and shift μ∈R by induction and Gaussian integration by parts.The recursion reduces the degree-k case to the degree-(k−1) hypothesis.
  • Identities: The generating-function identity is derived by expanding a fixed-x function in the Hermite basis and computing its coefficients with Gaussian integration by parts.The expectation of the function under a standard Gaussian is evaluated using the Gaussian moment-generating function.

C Subgaussian Random Variables

This section defines subgaussian random variables through moment-generating-function bounds and records their basic examples and moment estimates. It then proves that standardized i.i.d. subgaussian spike priors satisfy a local Chernoff bound in the spiked Wigner model.

  • Definitions and examples: A random variable is σ^2-subgaussian when it is centered and its moment-generating function is bounded by exp(σ^2t^2/2) for every t∈R.The parameter σ^2 is a variance proxy and need not equal the variable’s variance.
  • Definitions and examples: Gaussian variables, bounded variables, and Rademacher variables provide standard examples of subgaussian laws, and independent sums scale the variance proxy linearly.A distribution supported on [a,b] is (b−a)^2/4-subgaussian, while Rademacher variables are 1-subgaussian.
  • Moment bounds: Subgaussian variables admit absolute-moment bounds expressed using the gamma function and its standard inequalities.The section records a gamma-function ratio property used in these bounds.
  • Local Chernoff bounds: If π is σ^2-subgaussian with E[π]=0 and E[π^2]=1, then the i.i.d. spike prior generated from π admits a local Chernoff bound.This result applies to the spike prior used in the spiked Wigner model and assumes π does not depend on n.
  • Local Chernoff bounds: The proof uses subexponentiality of π^2 and the moment-generating function of Π=ππ′ to control the relevant sum near zero.The argument establishes finite moments and local upper bounds, then applies a symmetric argument to the opposite tail.
  • Local Chernoff bounds: The resulting tail estimate holds in a neighborhood whose size is restricted by the local parameter δ.The positive-tail argument requires α≤δ, with the negative tail handled analogously.

D Formal Consequences of the Low-Degree Method

This section develops formal consequences of low-degree predictions using hypercontractivity, the Paley–Zygmund inequality, and the variational property of the low-degree likelihood ratio. It applies these tools to lower bounds against thresholding polynomials and spectral methods.

  • D Formal Consequences of the Low-Degree Method: The proofs of Theorems 4.3 and 4.4 show that low-degree predictions imply specific failures for polynomial thresholding and low-degree spectral methods.Hypercontractivity is introduced as the key ingredient in both arguments.
  • D.1 Hypercontractivity: For Gaussian or Rademacher inputs, the Bonami lemma controls moments of degree-k polynomials, while Paley–Zygmund supplies a second-moment lower bound.These results combine into a corollary controlling how much a low-degree polynomial’s second moment can concentrate on a rare event.
  • D.1 Hypercontractivity: A rough consequence is that a degree-k polynomial’s second moment cannot be dominated by an event with probability much smaller than roughly 3^-2k.This interpretation summarizes the concentration scale supplied by the hypercontractive bound.
  • D.2 Lower Bound Against Thresholding Polynomials: The thresholding lower-bound proof applies Jensen’s inequality and hypercontractivity to a degree-2kd polynomial, then invokes the LDLR’s variational property.The proof splits according to whether the 4k-th moment is at most B^4k and otherwise chooses a corresponding Paley–Zygmund parameter.
  • D.3 Lower Bound Against Spectral Methods: The spectral lower-bound proof uses f(Y)=Tr(M^2k), where M’s eigenvalues are ordered by decreasing absolute value.The same moment comparison, case split, hypercontractive control, and LDLR variational property drive the argument.
  • D.3 Lower Bound Against Spectral Methods: For the spectral argument, the trace polynomial aggregates the eigenvalues through their 2k-th powers before the low-degree bound is applied.The proof separately handles the case where E_Q[f(Y)^2] is at most L^2B^4k and the complementary case.
Loading 1907.11636v1…