← All AI/ML open problems

Statistical inference · Statistical learning theory · Data-efficient learning / Open question

How Many Correlations Are Enough?

The information that determines a model need not be information an algorithm can use efficiently. Higher-order observations may trade measurement cost for computational tractability.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

For nn-spin Ising models with max⁡i(∣hi∣+∑j≠i∣Jij∣)≤γ\max_i(|h_i|+\sum_{j\ne i}|J_{ij}|)\leq\gamma, give a learner only moments mS=E∏i∈SXim_S=\mathbb E\prod_{i\in S}X_i for ∣S∣≤D|S|\leq D, each to additive accuracy τ\tau. Determine the smallest DD permitting coupling/field error at most ε\varepsilon with stated runtime in table size and precision. Can the sufficient order O(γ+log⁡(1/ε))O(\gamma+\log(1/\varepsilon)) be improved uniformly over this class, or over its ferromagnetic subclass Jij≥0J_{ij}\geq0? Seek matching computational lower bounds with their complexity assumptions explicit.

Assumptions and scope

  • The learner receives only a declared collection of approximate moments, with simultaneous error at most tau; it does not have hidden access to full configurations.
  • State the model family, parameter accuracy, smallest nonzero coupling when recovering structure, and allowed time/oracle complexity as functions of width, moment order and precision.
  • Charge table size and data acquisition separately: moments from one fully observed dataset and separately measured small subsets have different total costs. First/second moments are already statistically sufficient; the issue is computational access, not uniqueness alone.

What would settle it?

A sharper moment-order/precision/runtime trade-off for a declared family, or a computational lower bound in a precise moment-oracle model. A generic improvement must account for the cost of obtaining and reading the moments.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

The 2026 paper explicitly leaves the gap between order-two sufficient statistics and its width-dependent sufficient order unresolved. It already handles known-neighborhood priors using local moments; that special case is a baseline. Its runtime is polynomial in table size and polynomial in spin count when width and accuracy are fixed, not uniformly polynomial in all parameters. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Jayakumar, Shukla, Vuffray, Lokhov and Misra — Computationally Sufficient Statistics for Ising Models ↗problem statement · source checked 2026-11-19

    PDF Sections 2.1–2.4, Theorem 1 and Conclusion p.10 checked: order O(gamma + log(1/epsilon)) moment tables suffice, with runtime polynomial in table size. Lower moment orders and restricted families are explicit future directions. Shared full-sample and separate restricted-measurement costs differ.

  2. Vuffray, Misra, Lokhov and Chertkov — Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models ↗partial theory · source checked 2026-11-19

    Primary abstract checked: convex regularized local screening gives graph recovery with logarithmic system-size dependence and exponential coupling/degree dependence under full independent samples. Basic inverse-Ising recovery is established.

  3. Vuffray, Misra and Lokhov — Efficient Learning of Discrete Graphical Models ↗partial theory · source checked 2026-11-19

    Primary abstract checked: GRISE generalizes screening to discrete alphabets, arbitrary bases and multi-body factors under an identifiability condition. High-order model representation can still have a large computational cost.