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.
Seed catalog · Showing the bundled record.
Problem statement
For -spin Ising models with , give a learner only moments for , each to additive accuracy . Determine the smallest permitting coupling/field error at most with stated runtime in table size and precision. Can the sufficient order be improved uniformly over this class, or over its ferromagnetic subclass ? 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
- 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.
- 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.
- 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.