This paper is organized as follows. In Section , we show explicitly the reduction of a general weighted MAX-2-SAT problem into an RBM instance with Ising-type coupling [1]}. In Section , we introduce the frustration index [2]} in the context of a gauged RBM, and discuss its connection to the population of local minima. In Section , we introduce the random frustrated loop algorithm and propose a general method for direct control of the frustration index. We also investigate some of its interesting mathematical properties, and discuss the limitations of the algorithm in its original form. In Section , we make improvements on the algorithm by giving the loops certain geometrical structures, and we term the new algorithm structured loop algorithm. We show analytically that the new algorithm has the ability to generate hard instances in the regime of high loop density. In Section , we study empirically how the hardness of the generated instances scale with RBM size, frustration index, and loop density. We observe the hardness peaks [3]} with respect to the loop density for systems of different sizes, and present a double phase transition [4]} driven by the frustration index in the hardness scaling behavior with respect to the system size. We also provide empirical justification of the hardness improvement of the structured loop algorithm over the random counterpart. In Section , we offer a heuristic discussion on some practical applications of this work to the task of pre-training an RBM.
