Optimal structure and parameter learning of Ising models and calibration of the D-Wave quantum computer
Andrey Lokhov, Los Alamos National Laboratory
Reconstruction of structure and parameters of a graphical 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. In this talk, we introduce a new method, Interaction Screening, which accurately estimates the model parameters using local optimization problems. We provide mathematical guarantees that the algorithm achieves perfect graph structure recovery with an information-theoretically optimal number of samples and outperforms state of the art techniques, especially in the low-temperature regime which is known to be the hardest for learning. As an application, we show how the method can be used for an efficient calibration of the D-Wave quantum computer.