  Reconstruction of interaction network between random events is a critical
problem arising from statistical physics and politics to sociology, biology,
and psychology, and beyond. The Ising model lays the foundation for this
reconstruction process, but finding the underlying Ising model from the least
amount of observed samples in a computationally efficient manner has been
historically challenging for half a century. By using the idea of sparsity
learning, we present a approach named SIMPLE that has a dominant sample
complexity from theoretical limit. Furthermore, a tuning-free algorithm is
developed to give a statistically consistent solution of SIMPLE in polynomial
time with high probability. On extensive benchmarked cases, the SIMPLE approach
provably reconstructs underlying Ising models with global optimality. The
application on the U.S. senators voting in the last six congresses reveals that
both the Republicans and Democrats noticeably assemble in each congresses;
interestingly, the assembling of Democrats is particularly pronounced in the
latest congress.
