Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics
arXiv:2104.00995
Abstract
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.
arXiv commentAccepted to ICML 2021
References in corpus (16)
- Weak pairwise correlations imply strongly correlated network states in a neural population
- Direct-coupling analysis of residue co-evolution captures native contacts across many protein families
- A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
- The Ising Model for Neural Data: Model Quality and Approximate Methods for Extracting Functional Connectivity
- Pairwise maximum entropy models for studying large biological systems: when they can and when they can't work
- Information-Theoretic Implications of Quantum Causal Structures
- Prediction of spatio-temporal patterns of neural activity from pairwise correlations
- Mean Field Theory For Non-Equilibrium Network Reconstruction
- Spin glass models for a network of real neurons
- Faster solutions of the inverse pairwise Ising problem
- The Effect of Nonstationarity on Models Inferred from Neural Data
- Maximum likelihood reconstruction for Ising models with asynchronous updates
- Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models
- Network inference using asynchronously updated kinetic Ising Model
- Inference of the sparse kinetic Ising model using the decimation method
- Learning of couplings for random asymmetric kinetic Ising models revisited: random correlation matrices and learning curves