The usual setting for learning the structure and parameters of a graphical
model assumes the availability of independent samples produced from the
corresponding multivariate probability distribution. However, for many models
the mixing time of the respective Markov chain can be very large and i.i.d.
samples may not be obtained. We study the problem of reconstructing binary
graphical models from correlated samples produced by a dynamical process, which
is natural in many applications. We analyze the sample complexity of two
estimators that are based on the interaction screening objective and the
conditional likelihood loss. We observe that for samples coming from a
dynamical process far from equilibrium, the sample complexity reduces
exponentially compared to a dynamical process that mixes quickly.

该研究探讨了如何从动态过程的相关样本中重构二值图形模型，并分析了基于交互筛选目标和条件似然损失的两个估计器的样本复杂性。我们发现，对于来自远离平衡的动态过程的样本，样本复杂度与混合速度快的动态过程相比呈指数级下降。

学习伊辛模型动力学的样本复杂性指数降低

Exponential Reduction in Sample Complexity with Learning of Ising Model  Dynamics

Reconstruction of structure and parameters of an Ising model from binary
samples is a problem of practical importance in a variety of disciplines,
ranging from statistical physics and computational biology to image processing
and machine learning. The focus of the research community shifted towards
developing universal reconstruction algorithms which are both computationally
efficient and require the minimal amount of expensive data. We introduce a new
method, Interaction Screening, which accurately estimates the model parameters
using local optimization problems. The algorithm provably achieves perfect
graph structure recovery with an information-theoretically optimal number of
samples, notably in the low-temperature regime which is known to be the hardest
for learning. The efficacy of Interaction Screening is assessed through
extensive numerical tests on synthetic Ising models of various topologies with
different types of interactions, as well as on a real data produced by a D-Wave
quantum computer. This study shows that the Interaction Screening method is an
exact, tractable and optimal technique universally solving the inverse Ising
problem.

本文介绍一种名为 Interaction Screening 的新方法，使用本地优化问题准确估计模型参数，这个算法在信息论上优化样本数量的条件下可以实现完美的图形结构恢复，证明了 Interaction Screening 方法是一种准确、可行和最优的通用逆向 Ising 问题解决技术。

Ising 模型的最优结构和参数学习

Optimal structure and parameter learning of Ising models

We consider the problem of learning the underlying graph of an unknown Ising
model on p spins from a collection of i.i.d. samples generated from the model.
We suggest a new estimator that is computationally efficient and requires a
number of samples that is near-optimal with respect to previously established
information-theoretic lower-bound. Our statistical estimator has a physical
interpretation in terms of "interaction screening". The estimator is consistent
and is efficiently implemented using convex optimization. We prove that with
appropriate regularization, the estimator recovers the underlying graph using a
number of samples that is logarithmic in the system size p and exponential in
the maximum coupling-intensity and maximum node-degree.

提出了一种新的，具有物理解释的统计估计量来学习未知 Ising 模型的基础图，该估计量使用凸优化计算速度快，并且在适当的正则化下，可以以对数的速度回复基础图。

交互筛选：高效和样本最优学习 Ising 模型

Interaction Screening: Efficient and Sample-Optimal Learning of Ising  Models

This paper is concerned with the problems of interaction screening and
nonlinear classification in a high-dimensional setting. We propose a two-step
procedure, IIS-SQDA, where in the first step an innovated interaction screening
(IIS) approach based on transforming the original $p$-dimensional feature
vector is proposed, and in the second step a sparse quadratic discriminant
analysis (SQDA) is proposed for further selecting important interactions and
main effects and simultaneously conducting classification. Our IIS approach
screens important interactions by examining only $p$ features instead of all
two-way interactions of order $O(p^2)$. Our theory shows that the proposed
method enjoys sure screening property in interaction selection in the
high-dimensional setting of $p$ growing exponentially with the sample size. In
the selection and classification step, we establish a sparse inequality on the
estimated coefficient vector for QDA and prove that the classification error of
our procedure can be upper-bounded by the oracle classification error plus some
smaller order term. Extensive simulation studies and real data analysis show
that our proposal compares favorably with existing methods in interaction
selection and high-dimensional classification.

本文介绍了一种名为 IIS-SQDA 的方法，该方法通过屏蔽重要交互作用并同时进行分类来解决高维度线性分类问题，并通过 QDA 的系数向量建立了一个稀疏不等式来证明我们的分类方法具有很好的性能。