Exploiting the Limits of Structure Learning via Inherent Symmetry
Peng Ju He, Changshui Zhang · 2014
This theoretical paper is concerned with the structure learning limit for Gaussian Markov random fields from i.i.d. samples. The com-mon strategy is applying the Fano method to a family of restricted ensembles. The effi-ciency of this method, however, depends cru-cially on selected restricted ensembles. To break through this limitation, we analyze the whole graph ensemble from a group theoret-ical viewpoint. The key ingredient of our ap-proach is the invariance of orthogonal group actions on the symmetric Kullback-Leibler divergence. We then establish the connection of the learning limit and eigenvalues of con-centration matrices, which further leads to a sharper structure learning limit. To our best knowledge, this is the first paper to consider the structure learning problem via inheren-t symmetries of the whole ensemble. Final-ly, our approach can be applicable to other graphical structure learning problems. 1