Computational implications of reducing data to sufficient statistics

DOI10.1214/15-EJS1059zbMath1336.62037arXiv1409.3821MaRDI QIDQ887274

Andrea Montanari

Publication date: 28 October 2015

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.3821

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Sufficient statistics and fields (62B05) Graphical methods in statistics (62A09)

Related Items

Spectral bounds for the Ising ferromagnet on an arbitrary given graph ⋮ Towards optimal estimation of bivariate isotonic matrices with unknown permutations ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Counting in two-spin models on \(d\)-regular graphs
• High-dimensional structure estimation in Ising models: local separation criterion
• High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
• The geometry of exponential families
• The ellipsoid method and its consequences in combinatorial optimization
• Consistent estimation of the basic neighborhood of Markov random fields
• High-dimensional graphs and variable selection with the Lasso
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Improved Greedy Algorithms for Learning Graphical Models
• Inapproximability after Uniqueness Phase Transition in Two-Spin Systems
• The Complexity of Distinguishing Markov Random Fields
• Information, Physics, and Computation
• The computational complexity of two‐state spin systems
• Entropy, optimization and counting
• Computational Complexity
• Neural networks and physical systems with emergent collective computational abilities.
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• The Random-Cluster Model
• Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms

This page was built for publication: Computational implications of reducing data to sufficient statistics